E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
Journal:
Artificial Intelligence
-
ISSN:
0004-3702
-
Date (published):
24-Jun-2020
-
Number of Pages:
40
-
Peer reviewed:
Yes
-
Keywords:
Artificial Intelligence
-
Abstract:
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, certain facility location problems, 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 particular, we prove that Proportional Approval Voting can be computed in polynomial time for profiles that are single-peaked on a circle. In contrast, Kemeny's rule remains hard to evaluate, and several impossibility results from social choice theory can be proved using only profiles in this domain.