Are there any nicely structured preference profiles nearby?

DOI10.1016/J.MATHSOCSCI.2015.11.002zbMATH Open1347.91128arXiv1509.04595OpenAlexW2293830771MaRDI QIDQ2634484FDOQ2634484

Jiehua Chen, Gerhard J. Woeginger, Robert Bredereck

Publication date: 9 February 2016

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)