We study the complexity of the bribery problem with distance restrictions. In particular, in the bribery problem, we are given an election and a distinguished candidate p, and are asked whether we can make p win/not win the election by bribing at most k voters to recast their votes. In the bribery problem with distance restrictions, we require that the votes recast by the bribed voters are close to their original votes. To measure the closeness between two votes, we adopt the prevalent Kendall-Tau distance and the Hamming distance. We achieve a wide range of complexity results for this problem under a variety of voting correspondences, including the Borda, Condorcet, Copeland for every 0 ≤ α ≤ 1 and Maximin.
展开▼
机译：我们研究了距离限制的贿赂问题的复杂性。 In particular, in the bribery problem, we are given an election and a distinguished candidate p, and are asked whether we can make p win/not win the election by bribing at most k voters to recast their votes.在距离限制的贿赂问题中，我们要求贿赂选民的投票重新入门靠近原始选票。为了测量两张选票之间的亲密关系，我们采用普遍的肯德尔 - Tau距离和汉明距离。我们在各种投票通话中实现了各种复杂性结果，包括Borda，Condorcet，Copeland每0≤α≤1和Maximin。
展开▼
