The Library
The computational complexity of random serial dictatorship
Tools
Aziz, Haris, Brandt, Felix and Brill, Markus (2013) The computational complexity of random serial dictatorship. Economics Letters, 121 (3). pp. 341-345. doi:10.1016/j.econlet.2013.09.006 ISSN 0165-1765.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.econlet.2013.09.006
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.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Journal or Publication Title: | Economics Letters | ||||||||
Publisher: | Elsevier | ||||||||
ISSN: | 0165-1765 | ||||||||
Official Date: | December 2013 | ||||||||
Dates: |
|
||||||||
Volume: | 121 | ||||||||
Number: | 3 | ||||||||
Page Range: | pp. 341-345 | ||||||||
DOI: | 10.1016/j.econlet.2013.09.006 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |