Towards a Characterization of Random Serial Dictatorship
Random serial dictatorship (RSD) is a randomized assignment rule that - given a set of $n$ agents with strict preferences over $n$ houses - satisfies equal treatment of equals, ex post efficiency, and strategyproofness. For $n \le 3$, Bogomolnaia and Moulin (2001) have shown that RSD is characterized by these axioms. Extending this characterization to arbitrary $n$ is a long-standing open problem. By weakening ex post efficiency and strategyproofness, we reduce the question of whether RSD is characterized by these axioms for fixed $n$ to determining whether a matrix has rank $n^2 n!^n$. We provide computer-generated counterexamples to show that two other approaches for proving the characterization (using deterministic extreme points or restricted domains of preferences) are inadequate.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Paired Course and Dorm Allocation
Consider a university administrator who must assign students to both courses and dorms and runs (random) serial dictatorship independently in each market. While serial dictatorship is efficient for each individual matchi…
Efficiency in Random Resource Allocation and Social Choice
We study efficiency in general collective choice problems where agents have ordinal preferences and randomization is allowed. We explore the structure of preference profiles where ex-ante and ex-post efficiency coincide,…
Justified Fairness in House Allocation Problems: two Characterizations of Strategy-proof Mechanisms
We consider the house allocation problems with strict preferences, where monetary transfers are not allowed. We propose two properties in the spirit of justified fairness. Interestingly, together with other well-studied …
FairnessStability and Efficiency of Random Serial Dictatorship
This paper establishes non-asymptotic convergence of the cutoffs in Random serial dictatorship in an environment with many students, many schools, and arbitrary student preferences. Convergence is shown to hold when the …
Random Serial Dictatorship versus Probabilistic Serial Rule: A Tale of Two Random Mechanisms
For assignment problems where agents, specifying ordinal preferences, are allocated indivisible objects, two widely studied randomized mechanisms are the Random Serial Dictatorship (RSD) and Probabilistic Serial Rule (PS…