标题：How Hard Is Bribery with Distance Restrictions?
作者：Yang, Yongjie; Shrestha, Yash Raj; Guo, Jiong
作者机构：[Yang, Yongjie; Guo, Jiong] Shandong Univ, Jinan, Peoples R China.; [Yang, Yongjie] Univ Saarland, D-66123 Saarbrucken, Germany.; [Shrestha, Yash 更多
会议名称：22nd European Conference on Artificial Intelligence (ECAI)
会议日期：AUG 29-SEP 02, 2016
来源：ECAI 2016: 22ND EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE
摘要：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(alpha) for every 0 <= alpha <= 1 and Maximin.