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-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.
English abstract:
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)
http://dx.doi.org/10.1007/978-3-319-23114-3_5
Related Projects:
Project Head Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.