Parametrized algorithms for random serial dictatorship

DOI10.1016/J.MATHSOCSCI.2014.07.002zbMATH Open1308.91052arXiv1403.0974OpenAlexW2171419939MaRDI QIDQ477775FDOQ477775

Authors: Haris Aziz, Julián Mestre 

Publication date: 9 December 2014

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

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• A new solution to the random assignment problem.
• Scheduling with Opting Out: Improving upon Random Priority
• Queue allocation of indivisible goods
• Majority and Positional Voting in a Probabilistic Framework
• Manipulation of Schemes that Mix Voting with Chance
• The computational complexity of random serial dictatorship
• Social welfare in one-sided matching markets without money

Cited In (4)

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

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)