Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
G. Erdély, M. Lackner, A. Pfandler:
"The Complexity of Nearly Single-Peaked Consistency";
Vortrag: International Workshop on Computational Social Choice (COMSOC),
Krakow, Poland;
11.09.2012
- 13.09.2012; in: "Proceedings of fourth int. conference on Computational Social Choice",
F. Brandt, P. Faliszewski (Hrg.);
(2012),
12 S.
Kurzfassung englisch:
Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are in the general case computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these problems
suddenly become easy to solve. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra [FHH11] studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance
measure.
In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is in many cases NPcomplete. Furthermore, we explore the relations between several notions of nearly singlepeakedness.
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.