Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Manipulation under voting rule uncertainty
Elkind E., Erdélyi G.  AAMAS 2012 (Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, Jun 4-8, 2012)627-634.2012.Type:Proceedings
Date Reviewed: Jan 10 2013

There is a long line of research studying the computational complexity of manipulating elections. This line dates back to seminal papers of Bartholdi, Orlin, Tovey, and Trick from two decades ago. The paper reviewed here adds an interesting new twist to that well-established line. The authors study the complexity of determining whether, on a given input, the manipulator, or a manipulative coalition, has a move that is guaranteed to achieve its goal regardless of which of a particular collection of election systems is used. The paper models cases where the manipulators want to achieve their goal even if the choice of election system from the given collection is made by an actor seeking to prevent the coalition from succeeding.

This paper obtains results for many natural systems and explores the range of possible behaviors. In particular, if the collection consists of two election systems, and if for both individually the manipulation problem is easy, can the problem mentioned above be easy (that is, be in polynomial time)? Can it be hard (that is, be NP-hard)? Also of interest are the analogous questions for the cases when both listed systems are hard to manipulate on their own, and for the cases when one is hard and one is easy. This paper shows that every one of the six potential behaviors can occur. Not all of the examples are natural. For example, to show that two hard systems can be easy, the authors take a known hard system and pair it with itself. It is modified in a particular way to pick a candidate other than the one it would normally pick (except when there is exactly one candidate). Therefore, when there are two or more candidates, no candidate ever wins under either system, so the manipulation problem is trivially easy (and when there is one candidate, it is also trivially easy).

However, the important thing to keep in mind is that the paper uses such constructions to explore what behaviors are possible. This is a natural and important goal; this paper fully achieves it while also giving very broad insights into many types of concrete election systems in this setting.

Reviewer:  Lane A. Hemaspaandra Review #: CR140817 (1304-0324)
Bookmark and Share
  Reviewer Selected
 
 
General (F.2.0 )
 
 
Games (I.2.1 ... )
 
 
Multiagent Systems (I.2.11 ... )
 
 
Applications (G.2.3 )
 
 
Process Management (D.4.1 )
 
 
Public Policy Issues (K.4.1 )
 
Would you recommend this review?
yes
no
Other reviews under "General": Date
Algorithms in C
Sedgewick R., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990. Type: Book (9780201514254)
Sep 1 1991
Algorithms from P to NP (vol. 1)
Moret B., Shapiro H. (ed), Benjamin-Cummings Publ. Co., Inc., Redwood City, CA, 1991. Type: Book (9780805380088)
May 1 1992
The design and analysis of algorithms
Kozen D. (ed), Springer-Verlag New York, Inc., New York, NY, 1992. Type: Book (9780387976877)
Sep 1 1992
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