[Back]

G. Erdélyi, M. Lackner, A. Pfandler:
"Manipulation of k-Approval in Nearly Single-Peaked Electorates";
Talk: 4th International Conference on Algorithmic Decision Theory, ADT 2015, Lexington, Kentucky, USA; 2015-09-27 - 2015-09-30; in: "Algorithmic Decision Theory, 4th International Conference, ADT 2015 Lexington, KY, USA, September 27 - 30, 2015 Proceedings", T. Walsh (ed.); Springer, Lecture Notes in Computer Science Volume 9346 (2015), ISBN: 978-3-319-23113-6; 71 - 85.

For agents it can be advantageous to vote insincerely in order to change the outcome of an election. This behavior is called manipulation. The Gibbard-Satterthwaite theorem states that in principle every non-trivial voting rule with at least three candidates is susceptible to manipulation. Since the seminal paper by Bartholdi, Tovey, and Trick in 1989, (coalitional) manipulation has been shown NP-hard for many voting rules. However, under single-peaked preferences - one of the most influential domain restrictions - the complexity of manipulation often drops from NP-hard to P.

In this paper, we investigate the complexity of manipulation for the k-approval and veto families of voting rules in nearly single-peaked elections, exploring the limits where the manipulation problem turns from P to NP-hard. Compared to the classical notion of single-peakedness, notions of nearly single-peakedness are more robust and thus more likely to appear in real-world data sets.

http://dx.doi.org/10.1007/978-3-319-23114-3_5

Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

Project Head Stefan Woltran:
START