## Abstract

Perhaps the most influential result in social choice theory is Arrow’s impossibility theorem, which states that a seemingly modest set of desiderata cannot be satisfied when aggregating preferences [1]. While Arrow’s theorem might appear rather negative, it can also be interpreted in a positive way by identifying what can be achieved in preference aggregation. In this talk, I present a number of variations of Arrow’s theorem–such as those due to Mas-Colell and Sonnenschein [8] and Blau and Deb [2]–in their choice-theoretic version. The critical condition in all these theorems is the assumption of a rationalizing binary relation or equivalent notions of choice-consistency. The bulk of my presentation contains three escape routes from these results. The first one is to ignore consistency with respect to a variable set of alternatives altogether and require consistency with respect to a variable electorate instead. As Smith [12] and Young [14] have famously shown, this essentially characterizes the class of scoring rules, which contains plurality and Borda’s rule. For the second escape route, we factorize choice-consistency into two parts, contraction-consistency and expansions-consistency [11]. While even the mildest dose of the former has severe consequences on the possibility of choice, varying degrees of the latter characterize a number of appealing social choice functions, namely the top cycle, the uncovered set, and the Banks set [3,9,4]. Finally, I suggest to redefine choice-consistency by making reference to the set of chosen alternatives rather than individual chosen alternatives [6]. It turns out that the resulting condition is a weakening of transitive rationalizability and can be used to characterize the minimal covering set and the bipartisan set. Based on a two decades-old conjecture due to Schwartz [10], the tournament equilibrium set can be characterized by the same condition or, alternatively, by a weak expansion-consistency condition from the second escape route. Whether Schwartz’s conjecture actually holds remains a challenging combinatorial problem as well as one of the enigmatic open problems of social choice theory. Throughout the presentation I will discuss the algorithmic aspects of all considered social choice functions. While some of the mentioned functions can be easily computed, other ones do not admit an efficient algorithm unless P equals NP [13,5,7].

Original language | English |
---|---|

Title of host publication | Relational and Algebraic Methods in Computer Science - 12th International Conference, RAMICS 2011, Proceedings |

Editors | Harrie de Swart |

Publisher | Springer Verlag |

Pages | 50-51 |

Number of pages | 2 |

ISBN (Print) | 9783642210693 |

DOIs | |

State | Published - 2011 |

Event | 12th International Conference on Relational and Algebraic Methods in Computer Science, RAMICS 2011 - Rotterdam, Netherlands Duration: 30 May 2011 → 3 Jun 2011 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 6663 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 12th International Conference on Relational and Algebraic Methods in Computer Science, RAMICS 2011 |
---|---|

Country/Territory | Netherlands |

City | Rotterdam |

Period | 30/05/11 → 3/06/11 |