On the likelihood of single-peaked preferences

DOI10.1007/S00355-017-1033-0zbMATH Open1392.91026arXiv1505.05852OpenAlexW2122315855WikidataQ41878098 ScholiaQ41878098MaRDI QIDQ1704048FDOQ1704048

Authors: Marie-Louise Lackner, Martin Lackner 

Publication date: 8 March 2018

Published in: Social Choice and Welfare (Search for Journal in Brave)

Abstract: This paper contains an extensive combinatorial analysis of the single-peaked domain restriction and investigates the likelihood that an election is single-peaked. We provide a very general upper bound result for domain restrictions that can be defined by certain forbidden configurations. This upper bound implies that many domain restrictions (including the single-peaked restriction) are very unlikely to appear in a random election chosen according to the Impartial Culture assumption. For single-peaked elections, this upper bound can be refined and complemented by a lower bound that is asymptotically tight. In addition, we provide exact results for elections with few voters or candidates. Moreover, we consider the P'{o}lya urn model and the Mallows model and obtain lower bounds showing that single-peakedness is considerably more likely to appear for certain parameterizations.

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

Recommendations

• The likelihood of single-peaked preferences under classic and new probability distribution assumptions
• Modeling single-peakedness for votes with ties
• Preferences Single-Peaked on a Circle
• The single-peaked domain revisited: a simple global characterization
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates

zbMATH Keywords

domain restrictioncombinatorial analysissingle-peaked preferences

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Individual preferences (91B08) Voting theory (91B12)

Cites Work

• Probability models on rankings
• NON-NULL RANKING MODELS. I
• Mixtures of distance-based models for ranking data
• Title not available (Why is that?)
• Restricted permutations
• On hypergeometric functions and Pochhammer \(k\)-symbol
• Title not available (Why is that?)
• Generalized median voter schemes and committees
• The impact of voters' preference diversity on the probability of some electoral outcomes
• Single-peaked orders on a tree
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• How the size of a coalition affects its chances to influence an election
• Manipulation of Voting Schemes: A General Result
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Generating trees and the Catalan and Schröder numbers
• Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates
• Where are the hard manipulation problems?
• 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
• On the computation of fully proportional representation
• The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem
• Top monotonicity: a common root for single peakedness, single crossing and the median voter result
• Are there any nicely structured preference profiles nearby?
• A Possibility Theorem on Majority Decisions
• Condorcet’s Paradox
• Borda rule, Copeland method and strategic manipulation.
• On asymptotic strategy-proofness of classical social choice rules
• The Simple Majority Decision Rule
• A characterization of the single-peaked domain
• Condorcet's paradox and the likelihood of its occurrence: Different perspectives on balanced preferences
• Bounded single-peaked width and proportional representation
• Recognizing one-dimensional Euclidean preference profiles
• On asymptotic strategy-proofness of the plurality and the run-off rules
• A new record for \(1324\)-avoiding permutations
• The one-dimensional Euclidean domain: finitely many obstructions are not enough
• A characterization of the single-crossing domain
• Computational aspects of nearly single-peaked electorates

Cited In (21)

• Eliciting single-peaked preferences using comparison queries
• Single-peaked compatible preference profiles: Some combinatorial results
• The likelihood of single-peaked preferences under classic and new probability distribution assumptions
• The plurality majority converse under single peakedness
• On the number of single-peaked narcissistic or single-crossing narcissistic preference profiles
• Incomplete preferences in single-peaked electorates
• Approximate efficiency and strategy-proofness for moneyless mechanisms on single-dipped policy domain
• Enhancing the connections between patterns in permutations and forbidden configurations in restricted elections
• Patterns in Shi tableaux and Dyck paths
• Structure of single-peaked preferences
• Unified approach to fractional calculus images involving the pathway transform of extended \(k\)-gamma function and applications
• Modeling single-peakedness for votes with ties
• Small one-dimensional Euclidean preference profiles
• Combinatorics of Election Scores
• Majority judgment vs. approval voting
• Preferences Single-Peaked on a Circle
• Flexible level-1 consensus ensuring stable social choice: analysis and algorithms
• The largest Condorcet domain on 8 alternatives
• Structured preferences: a literature survey
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• A characterization of the single-peaked single-crossing domain

This page was built for publication: On the likelihood of single-peaked preferences

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