2020/10/07 by Shen, Yiheng, Tang, Pingzhong, Deng, Yuan
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2010.03372
The Borda voting rule is a positional scoring rule for z candidates such that in each vote, the first candidate receives z-1 points, the second z-2 points and so on. The winner in the Borda rule is the candidate with highest total score. We study the manipulation problem of the Borda rule in a setting with two non-manipulators while one of the non-manipulator's vote is weighted. We demonstrate a sharp contrast on computational complexity depending on the weight of the non-manipulator: the problem is NP-hard when the weight is larger than 1 while there exists an efficient algorithm to find a manipulation when the weight is at most 1.