The computational complexity of choice sets

Felix Brandt, Felix Fischer, Paul Harrenstein

Research output: Contribution to conferencePaperpeer-review

14 Scopus citations

Abstract

Social choice rules are often evaluated and compared by inquiring whether they fulfill certain desirable criteria such as the Condorcet criterion, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise majority relation. These sets include the Copeland set, the Smith set, the Schwartz set, von Neumann-Morgenstern stable sets (a concept originally introduced in the context of cooperative game theory), the Banks set, and the Slater set. We investigate the relationships between these sets and completely characterize their computational complexity which allows us to obtain hardness results for entire classes of social choice rules. In contrast to most existing work, we do not impose any restrictions on individual preferences, apart from the indifference relation being reflexive and symmetric. This assumption is motivated by the fact that many realistic types of preferences in computational contexts such as incomplete or quasi-transitive preferences may lead to general pairwise majority relations that need not be complete.

Original languageEnglish
Pages82-91
Number of pages10
DOIs
StatePublished - 2007
Externally publishedYes
Event11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007 - Brussels, Belgium
Duration: 25 Jun 200727 Jun 2007

Conference

Conference11th Conference on Theoretical Aspects of Rationality and Knowledge, TARK 2007
Country/TerritoryBelgium
CityBrussels
Period25/06/0727/06/07

Fingerprint

Dive into the research topics of 'The computational complexity of choice sets'. Together they form a unique fingerprint.

Cite this