Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Optimal manipulation of voting rules
Obraztsova S., Elkind E.  AAMAS 2012 (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, Jun 4-8, 2012)619-626.2012.Type:Proceedings
Date Reviewed: Feb 28 2013

More than 20 years ago, a series of papers by Bartholdi, Tovey, and Trick started a line of intense study of the computational complexity of two types of attacks on elections--control and manipulation. In manipulation, one has non-manipulative voters, who come in with preferences, and one or a coalition of manipulative voters, who come in as blank slates; one asks if there is some setting of the manipulative voters such that a designated candidate wins the election (that is, wins under the given voting rule). Far more recently, a type of attack known as bribery was introduced [1], in which each voter comes in with preferences, and one asks whether by a given “amount” of bribing one can make a designated candidate win the election. Existing work studies both the case where the amount is the number of voters one bribes, and where one pays by adding up some notion of the distance of the change one made in each vote.

This paper in some sense connects these two lines of investigation. Like non-coalitional manipulation, it fixes as part of the input a single voter of interest. However, like bribery, that voter has an initial preference and the goal is highly distance sensitive. In particular, the question asked in this paper is whether the given voter has a vote that is not more than a certain distance from his or her initial vote, and that makes a certain designated candidate the winner.

The paper studies this problem for a number of election systems and for a number of notions of distance. The paper obtains polynomial-time algorithms, NP-completeness results, and inapproximability results (holding if P does not equal NP). In particular, the paper shows that this problem is computationally easy for scoring rules and for Bucklin elections, but gives intractability and inapproximability results for Copeland and maximin elections. The paper’s results are interesting, and its fresh direction is natural and attractive.

Reviewer:  Lane A. Hemaspaandra Review #: CR140972 (1306-0549)
1) Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. How hard is bribery in elections?. J. Artificial Intelligence Research 35, 1(2009), 485–532.
Bookmark and Share
  Reviewer Selected
 
 
Distributed Artificial Intelligence (I.2.11 )
 
 
General (F.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Distributed Artificial Intelligence": Date
Artificial life playhouse
Prata S., Waite Group Press, Corte Madera, CA, 1993. Type: Book (9781878739322)
Jan 1 1995
Cooperation in industrial multi-agent systems
Jennings N. (ed), World Scientific Publishing Co., Inc., River Edge, NJ, 1994. Type: Book (9789810216528)
Jun 1 1996
Rules of encounter
Rosenschein J., Zlotkin G., MIT Press, Cambridge, MA, 1994. Type: Book (9780262181594)
Jul 1 1995
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy