Computational aspects of nearly single-peaked electorates

DOI10.1613/JAIR.5210MaRDI QIDQ2962574zbMATH OpenOpenAlexFDO

Authors Gábor Erdélyi, Martin Lackner, Andreas Pfandler

Publication date 17 February 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.2627

zbMATH Keywords

computational complexityNP-completenesselectionvoting rules

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Abstract: Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting rules are, in the general case, computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these rules suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the computational complexity of strategic 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 NP-complete in many cases. For one case we present a polynomial-time algorithm. In case the single-peaked axis is given, we show that determining the distance is always possible in polynomial time. Furthermore, we explore the relations between the new notions introduced in this paper and existing notions from the literature.

Recommendations

• The complexity of manipulative attacks in nearly single-peaked electorates
• Manipulation of k-Approval in Nearly Single-Peaked Electorates
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• On the complexity of constructive control under nearly single-peaked preferences
• Modeling single-peakedness for votes with ties

Cited in

(15)

• Parameterized complexity of voter control in multi-peaked elections
• The control complexity of \(r\)-Approval: from the single-peaked case to the general case
• On the likelihood of single-peaked preferences
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• Are there any nicely structured preference profiles nearby?
• The complexity of manipulative attacks in nearly single-peaked electorates
• Modeling single-peakedness for votes with ties
• Group control for consent rules with consecutive qualifications
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Recognizing and eliciting weakly single crossing profiles on trees
• Toward Computing the Margin of Victory in Single Transferable Vote Elections
• Measuring nearly single-peakedness of an electorate: some new insights
• On the complexity of constructive control under nearly single-peaked preferences
• Structured preferences: a literature survey
• Manipulation of k-Approval in Nearly Single-Peaked Electorates

This page was built for publication: Computational aspects of nearly single-peaked electorates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2962574)