Voting with Restricted Preferences
Edith Elkind ( University of Oxford )
- 14:00 18th February 2014 ( week 5, Hilary Term 2014 )Lecture Theatre B
Arrow's famous impossibility theorem (1951) states that there is no
perfect voting rule: for three or more candidates, no voting rule can
satisfy a small set of very appealing axioms. However, this is no
longer the case if we assume that voters' preferences satisfy certain
restrictions, such as being single-peaked or single-crossing. In this
talk, we introduce several restricted preference domains and discuss
their properties and associated algorithmic questions. In particular,
we will present efficient algorithms for detecting whether a given
election belongs to one of these domains and for selecting the best
committee (a set of winners) for elections in these domains. No
background in social choice theory is required.