Stability 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 number of schools, $m$, and the number of students, $n$, satisfy the relation $m \ln m \ll n$, and we provide an example showing that this result is sharp. We differ significantly from prior work in the mechanism design literature in our use of analytic tools from randomized algorithms and discrete probability, which allow us to show concentration of the RSD lottery probabilities and cutoffs even against adversarial student preferences.
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…
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. …
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,…
Allocating Indivisible Items in Categorized Domains
We formulate a general class of allocation problems called categorized domain allocation problems (CDAPs), where indivisible items from multiple categories are allocated to agents without monetary transfer and each agent…
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…