The computational complexity of random serial dictatorship

Haris Aziz, Felix Brandt and Markus Brill

Economics Letters, 2013, vol. 121, issue 3, 341-345

Abstract: 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.

Keywords: Social choice theory; Random serial dictatorship; Random priority; Computational complexity; Assignment problem (search for similar items in EconPapers)
JEL-codes: C63 C70 C71 C78 (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165176513004138
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ecolet:v:121:y:2013:i:3:p:341-345

DOI: 10.1016/j.econlet.2013.09.006

Access Statistics for this article

Economics Letters is currently edited by Economics Letters Editorial Office

More articles in Economics Letters from Elsevier
Bibliographic data for series maintained by Catherine Liu ().