Stability and Efficiency of Random Serial Dictatorship (opens in new tab)

arXiv:2110.07024v2 Announce Type: replace-cross Abstract: 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...