TY - GEN
T1 - The computational complexity of random serial dictatorship
AU - Aziz, Haris
AU - Brandt, Felix
AU - Brill, Markus
PY - 2013
Y1 - 2013
N2 - In social choice settings with linear preferences, random dictatorship is known to be the only social decision scheme satisfying strategyproofness and ex post efficiency. When also allowing indifferences, random serial dictatorship (RSD) is a well-known generalization of random dictatorship that retains both properties. RSD has been particularly successful in the special domain of random assignment where indifferences are unavoidable. While executing RSD is obviously feasible, we show that computing the resulting probabilities is #P-complete and thus intractable, both in the context of voting and assignment.
AB - In social choice settings with linear preferences, random dictatorship is known to be the only social decision scheme satisfying strategyproofness and ex post efficiency. When also allowing indifferences, random serial dictatorship (RSD) is a well-known generalization of random dictatorship that retains both properties. RSD has been particularly successful in the special domain of random assignment where indifferences are unavoidable. While executing RSD is obviously feasible, we show that computing the resulting probabilities is #P-complete and thus intractable, both in the context of voting and assignment.
UR - http://www.scopus.com/inward/record.url?scp=84893081119&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-45046-4_3
DO - 10.1007/978-3-642-45046-4_3
M3 - Conference contribution
AN - SCOPUS:84893081119
SN - 9783642450457
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 24
EP - 25
BT - Web and Internet Economics - 9th International Conference, WINE 2013, Proceedings
T2 - 9th International Conference on Web and Internet Economics, WINE 2013
Y2 - 11 December 2013 through 14 December 2013
ER -