AAAI Publications, Thirty-First AAAI Conference on Artificial Intelligence

Font Size: 
Preferences Single-Peaked on a Circle
Dominik Peters, Martin Lackner

Last modified: 2017-02-10


We introduce the domain of preferences that are single-peaked on a circle, which is a generalization of the well-studied 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 polynomial-time 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


social choice; voting; single-peaked preferences; winner determination; consecutive ones

Full Text: PDF