Frugal Bribery in Voting
In computational social choice, bribery refers to an external agent trying to influence the election outcome by persuading a certain targeted set of agents to vote in favor of some particular candidate. This work studies frugal bribers who will persuade only those (vulnerable) voters who themselves also prefer the new election outcome that results if the briber succeeds in the mission. Our key result is seemingly surprising: the computational problem of frugal bribery, that is which vulnerable voters report what preferences so that the candidate favored by the briber wins the election, is intractable. Our results establish that elections typically are more robust against bribery compared to other types of election controls such as manipulation.
Reference:
Palash Dey, Neeldhara Misra, and Yadati Narahari. “Frugal Bribery in Voting”. Theoretical Computer Science, volume 676, pp. 15-32, May 2017. A preliminary version of this work appeared in Proc. 30th AAAI Conference on Artificial Intelligence (AAAI-16).