  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 $\theta\in[0,1]$, as a function of $\theta$.
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.
