Are there any nicely structured preference profiles nearby?

DOI10.1016/J.MATHSOCSCI.2015.11.002MaRDI QIDQ2634484zbMATH OpenOpenAlexFDO

Authors Robert Bredereck, Jiehua Chen, Gerhard J. Woeginger

Publication date 9 February 2016

Published in Mathematical Social Sciences (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Individual preferences (91B08) Social choice (91B14) Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12)

Abstract: We investigate the problem of deciding whether a given preference profile is close to having a certain nice structure, as for instance single-peaked, single-caved, single-crossing, value-restricted, best-restricted, worst-restricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted to make the profile a nicely structured one. Our results classify the problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial-time solvable) and computationally intractable (NP-hard) questions.

Recommendations

• Structured preferences: a literature survey
• Computational aspects of nearly single-peaked electorates
• Preferences Single-Peaked on a Circle
• Incomplete preferences in single-peaked electorates
• Preferences single-peaked on a tree: multiwinner elections and structural results

Cites work

• scientific article; zbMATH DE number 5556709 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3345350 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• A Possibility Theorem on Majority Decisions
• A characterization of the single-crossing domain
• A characterization of the single-peaked domain
• Acyclic sets of linear orders via the Bruhat orders
• An Exploration in the Theory of Optimum Income Taxation
• Bounded single-peaked width and proportional representation
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Combinatorial voter control in elections
• Extending Condorcet's rule
• Fundamentals of parameterized complexity
• Generalized median voter schemes and committees
• How Large are Transitive Simple Majority Domains?
• Independence of clones as a criterion for voting rules
• Introduction to algorithms.
• Metric rationalisation of social choice functions according to principles of social choice
• On the computation of fully proportional representation
• Parameterized algorithms
• Parametrized complexity theory.
• Rationalizations of Condorcet-consistent rules via distances of Hamming type
• Recognizing 1-Euclidean preferences: an alternative approach
• Recognizing one-dimensional Euclidean preference profiles
• Stable matching with preferences derived from a psychological model
• Strategy-proof division of a private good when preferences are single-dipped
• The Simple Majority Decision Rule
• The complexity of fully proportional representation for single-crossing electorates
• The complexity of manipulative attacks in nearly single-peaked electorates
• The one-dimensional Euclidean domain: finitely many obstructions are not enough
• The shield that never was: societies with single-peaked preferences are more open to manipulation and control
• Voting schemes for which it can be difficult to tell who won the election

Cited in

(14)

• Parameterized complexity of voter control in multi-peaked elections
• Structured preferences: a literature survey
• Small one-dimensional Euclidean preference profiles
• Campaign management under approval-driven voting rules
• The control complexity of \(r\)-Approval: from the single-peaked case to the general case
• The likelihood of single-peaked preferences under classic and new probability distribution assumptions
• Where do preferences come from?
• The one-dimensional Euclidean domain: finitely many obstructions are not enough
• Recognizing when a preference system is close to admitting a master list
• On the likelihood of single-peaked preferences
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• Testing a mixture model of single-peaked preferences
• Measuring nearly single-peakedness of an electorate: some new insights
• On the number of single-peaked narcissistic or single-crossing narcissistic preference profiles

This page was built for publication: Are there any nicely structured preference profiles nearby?

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