Parametrized algorithms for random serial dictatorship

DOI10.1016/J.MATHSOCSCI.2014.07.002MaRDI QIDQ477775zbMATH OpenOpenAlexFDO

Authors Haris Aziz, Julián Mestre

Publication date 9 December 2014

Published in Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.0974

Mathematics Subject Classification ID

Social choice (91B14) Analysis of algorithms and problem complexity (68Q25)

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 study RSD from a parametrized complexity perspective. More specifically, we present efficient algorithms to compute the RSD probabilities under the condition that the number of agent types, alternatives, or objects is bounded.

Recommendations

• Efficient rules for probabilistic assignment
• On the consistency of random serial dictatorship
• A solution to the random assignment problem on the full preference domain

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A new solution to the random assignment problem.
• Fundamentals of parameterized complexity
• Majority and Positional Voting in a Probabilistic Framework
• Manipulation of Schemes that Mix Voting with Chance
• Queue allocation of indivisible goods
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Scheduling with Opting Out: Improving upon Random Priority
• Social welfare in one-sided matching markets without money

Cited in

(3)

• A note on the serial dictatorship with project closures
• The complexity of computing the random priority allocation matrix
• Counting houses of Pareto optimal matchings in the house allocation problem

This page was built for publication: Parametrized algorithms for random serial dictatorship

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477775)