Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
From MaRDI portal
Publication:2109969
DOI10.1007/978-3-030-57980-7_19zbMATH Open1506.91047arXiv2004.13602OpenAlexW3090676755MaRDI QIDQ2109969FDOQ2109969
Olivier Spanjaard, Magdaléna Tydrichová, Bruno Escoffier
Publication date: 21 December 2022
Abstract: This paper is devoted to a study of single-peakedness on arbitrary graphs. Given a collection of preferences (rankings of a set of alternatives), we aim at determining a connected graph G on which the preferences are single-peaked, in the sense that all the preferences are traversals of G. Note that a collection of preferences is always single-peaked on the complete graph. We propose an Integer Linear Programming formulation (ILP) of the problem of minimizing the number of edges in G or the maximum degree of a vertex in G. We prove that both problems are NP-hard in the general case. However, we show that if the optimal number of edges is m-1 (where m is the number of candidates) then any optimal solution of the ILP is integer and thus the integrality constraints can be relaxed. This provides an alternative proof of the polynomial-time complexity of recognizing single-peaked preferences on a tree. We prove the same result for the case of a path (an axis), providing here also an alternative proof of polynomiality of the recognition problem. Furthermore, we provide a polynomial-time procedure to recognize single-peaked preferences on a pseudotree (a connected graph that contains at most one cycle). We also give some experimental results, both on real and synthetic datasets.
Full work available at URL: https://arxiv.org/abs/2004.13602
Recommendations
- Recognizing single-peaked preferences on a tree
- Unanimous and strategy-proof probabilistic rules for single-peaked preference profiles on graphs
- Single-peaked compatible preference profiles: Some combinatorial results
- A characterization of single-peaked preferences via random social choice functions
- Single-peaked preferences over multidimensional binary alternatives
- Recognizing top-monotonic preference profiles in polynomial time
- Sorting out single-crossing preferences on networks
- On the likelihood of single-peaked preferences
- Eliciting single-peaked preferences using comparison queries
- Constrained allocation problems with single-peaked preferences: an axiomatic analysis
Cited In (7)
- Single-peaked compatible preference profiles: Some combinatorial results
- Sorting out single-crossing preferences on networks
- Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
- A MIP-based approach to learn MR-sort models with single-peaked preferences
- Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results
- Recognizing single-peaked preferences on a tree
- Structured preferences: a literature survey
This page was built for publication: Recognizing single-peaked preferences on an arbitrary graph: complexity and algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109969)
