Preferences Single-Peaked on a Circle

We introduce the domain of preferences that are singlepeaked on a circle, which is a generalization of the wellstudied single-peaked domain. This preference restriction is useful, e. g. , for scheduling decisions, and for one-dimensional decisions in the presence of extremist preferences. We give a fast recognition algorithm of this domain, provide a characterisation by finitely many forbidden subprofiles, and show that many popular single- and multi-winner voting rules are polynomialtime computable on this domain. In contrast, Kemeny’s rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles that are single-peaked on a circle.

Authors

• Dominik Peters CNRS, LAMSADE, Université Paris Dauphine - PSL
• Martin Lackner Univ. of Applied Sciences St. Pölten

Keywords

No keywords are indexed for this paper.