Conference item icon

Conference item

Preferences single-peaked on a circle

Abstract:
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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions

  • Cite

  • Print

Access Document

Files:

Authors

More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author

Publisher:
AAAI Press
Host title:
Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI'17)
Journal:
AAAI 17: Thirty-First AAAI Conference on Artificial Intelligence More from this journal
Pages:
649-655
Publication date:
2017-01-01
Acceptance date:
2016-11-12
ISSN:
2159-5399

Keywords:
Pubs id:
pubs:664940
UUID:
uuid:0bdc432c-4e53-49c9-8d93-ca2da6e85387
Local pid:
pubs:664940
Source identifiers:
664940
Deposit date:
2016-12-12
ARK identifier:

Terms of use

Views and Downloads





If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP