The Computational Complexity of Random Serial Dictatorship
arXiv:1304.3169 · doi: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.
11 pages
Cited by in corpus (18)
- Possible and Necessary Allocations via Sequential Mechanisms
- The Impossibility of Extending Random Dictatorship to Weak Preferences
- Competitive Equilibrium For Almost All Incomes: Existence and Fairness
- Egalitarianism of Random Assignment Mechanisms
- Random assignment with multi-unit demands
- Equilibria Under the Probabilistic Serial Rule
- Dominate or Delete: Decentralized Competing Bandits in Serial Dictatorship
- A pessimist's approach to one-sided matching
- Strategic aspects of the probabilistic serial rule for the allocation of goods
- Average-case Analysis of the Assignment Problem with Independent Preferences
- Participation Incentives in Randomized Social Choice
- Social Welfare in One-Sided Matching Mechanisms
- Bounded Incentives in Manipulating the Probabilistic Serial Rule
- Investigating the Characteristics of One-Sided Matching Mechanisms Under Various Preferences and Risk Attitudes
- Structure and complexity of ex post efficient random assignments
- Parametrized Algorithms for Random Serial Dictatorship
- A Comment on the Averseness of Random Serial Dictatorship to Stochastic Dominance Efficiency
- Assigning Course Schedules: About Preference Elicitation, Fairness, and Truthfulness