Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms

DOI10.1016/j.dam.2024.02.009OpenAlexW3023935713MaRDI QIDQ6124439

Magdaléna Tydrichová, Olivier Spanjaard, Bruno Escoffier

Publication date: 27 March 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2024.02.009

zbMATH Keywords

single-peaked preferencesstructured preferences

Mathematics Subject Classification ID

Integer programming (90C10) Linear programming (90C05) Individual preferences (91B08) Experimental work for problems pertaining to game theory, economics, and finance (91-05)

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of manipulative attacks in nearly single-peaked electorates
• The structure of strategy-proof social choice. I: General characterization and possibility results on median spaces
• Recognizing single-peaked preferences on a tree
• Single-peaked orders on a tree
• Stable matching with preferences derived from a psychological model
• Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
• Are there any nicely structured preference profiles nearby?
• On the Computation of Fully Proportional Representation
• Bypassing Combinatorial Protections: Polynomial-Time Algorithms for Single-Peaked Electorates
• Computational Aspects of Nearly Single-Peaked Electorates
• A Polynomial Time Algorithm for Unidimensional Unfolding Representations
• Ranking Median Regression: Learning to Order through Local Consensus
• Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
• Preferences Single-Peaked on a Circle

This page was built for publication: Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms