The one-dimensional Euclidean domain: Finitely many obstructions are not enough

2015/06/11 by Jiehua Chen, Kirk Pruhs, Chen, Jiehua +3 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Computer Science and Game Theory (cs.GT) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1506.03838

openalex publication_date 2015/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We show that one-dimensional Euclidean preference profiles can not be characterized in terms of finitely many forbidden substructures. This result is in strong contrast to the case of single-peaked and single-crossing preference profiles, for which such finite characterizations have been derived in the literature.

Citations

• On the Rationale of Group Decision-making

Cited by

• How Hard is it to Explain Preferences Using Few Boolean Attributes?
• Diversity of Structured Domains via k-Kemeny Scores

Related

• Small One-Dimensional Euclidean Preference Profiles
• Euclidean preferences in the plane under ℓ₁, ℓ₂ and ℓ_∞ norms
• Recognising Multidimensional Euclidean Preferences
• Error in the Euclidean Preference Model
• 2-Dimensional Euclidean Preferences