Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
G. Erdélyi, M. Lackner, A. Pfandler:
"Computational Aspects of Nearly Single-Peaked Electorates";
Vortrag: Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13),
Bellevue, Washington, USA;
14.07.2013
- 18.07.2013; in: "Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13)",
AAAI Press,
(2013),
S. 283
- 289.
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 systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra (2011b) studied the complexity of dishonest behavior in nearly single-eaked 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 NP-complete in many cases. For one case we present a polynomial-time algorithm. Furthermore, we explore the relations between several notions of nearly singlepeakedness.
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.