Loading...
Please wait, while we are loading the content...
Similar Documents
The Computational Complexity of Choice Sets
| Content Provider | CiteSeerX |
|---|---|
| Author | Fischer, Felix Harrenstein, Paul Brandt, Felix |
| Abstract | Social choice rules are often evaluated and compared by inquiring whether they satisfy 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, 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Hardness Result Copeland Set Choice Set Von Neumann-morgenstern Stable Set Social Choice Rule Bank Set Pairwise Majority Relation Entire Class Condorcet Criterion Certain Desirable Criterion Slater Set Reasonable Alternative Schwartz Set Smith Set Computational Complexity |
| Content Type | Text |
