Parametrized algorithms for random serial dictatorship

Haris Aziz and Julián Mestre

Mathematical Social Sciences, 2014, vol. 72, issue C, 1-6

Abstract: Voting and assignment are two of the most fundamental settings in social choice theory. For both settings, random serial dictatorship (RSD) is a well-known rule that satisfies anonymity, ex post efficiency, and strategyproofness. Recently, it was shown that computing the resulting probabilities is #P-complete both in the voting and assignment setting. In this paper, we present efficient parametrized algorithms to compute the RSD probabilities for parameters such as the number of agent types, alternatives, or objects. When the parameters are small, then the respective algorithms are considerably more efficient than the naive approach of going through all permutations of agents.

Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0165489614000584
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:matsoc:v:72:y:2014:i:c:p:1-6

DOI: 10.1016/j.mathsocsci.2014.07.002

Access Statistics for this article

Mathematical Social Sciences is currently edited by J.-F. Laslier

More articles in Mathematical Social Sciences from Elsevier
Bibliographic data for series maintained by Catherine Liu ().