Talks and Poster Presentations (with Proceedings-Entry):
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-30; in: "Algorithmic Decision Theory, 4th International Conference, ADT 2015 Lexington, KY, USA, September 27 - 30, 2015 Proceedings",
T. Walsh (ed.);
Lecture Notes in Computer Science Volume 9346
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.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Project Head Stefan Woltran:
Created from the Publication Database of the Vienna University of Technology.