Restricted preference domains in social choice: two perspectives

Conference item

Preference aggregation is a challenging task: Arrow’s famous impossibility theorem [1] tells us that there is no perfect voting rule. One of the best-known ways to circumvent this difficulty is to assume that voters’ preferences satisfy a structural constraint, such as, e.g., being single-peaked. Indeed, under this assumption many impossibility results in social choice disappear. Restricted preference domains also play an important role in computational social choice: for instance, there are voting rules that are NP-hard to compute in general, but admit efficient winner determination algorithms when voters’ preferences belong to a restricted domain. However, restricted domains that have nice social choice-theoretic properties are not necessarily attractive from an algorithmic perspective, and vice versa. In this note, we will discuss some domain restrictions that have proved to be useful from a computational perspective, and compare the use of restricted domains in computational and classic social choice theory.

Authors: Elkind, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer International Publishing
• Host title: SAGT 2018: Algorithmic Game Theory
• Journal: Restricted preference domains in social choice: two perspectives
• Volume: 11059
• Pages: 12-18
• Series: Lecture Notes in Computer Science
• Publication date: 2018-08-27
• Acceptance date: 2018-06-19
• DOI: 10.1007/978-3-319-99660-8_2
• ISSN: 0302-9743
• ISBN: 9783319996592