Asymptotic welfare performance of Boston assignment algorithms
We make a detailed analysis of three key algorithms (Serial Dictatorship and the naive and adaptive variants of the Boston algorithm) for the housing allocation problem, under the assumption that agent preferences are chosen iid uniformly from linear orders on the items. We compute limiting distributions (with respect to some common utility functions) as $n\to \infty$ of both the utilitarian welfare and the order bias. To do this, we compute limiting distributions of the outcomes for an arbitrary agent whose initial relative position in the tiebreak order is $θ\in[0,1]$, as a function of $θ$. The results for the Boston algorithms are all new, and we expect that these fundamental results on the stochastic processes underlying these algorithms will have wider applicability in future. Overall our results show that the differences in utilitarian welfare performance of the three algorithms are fairly small but still important. However, the differences in order bias are much greater. Also, Naive Boston beats Adaptive Boston, which beats Serial Dictatorship, on both utilitarian welfare and order bias.