Asymptotic welfare performance of Boston assignment algorithms

Geoffrey Pritchard and Mark C. Wilson

Papers from arXiv.org

Abstract: 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.

Date: 2022-05
New Economics Papers: this item is included in nep-upt
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2205.15418 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2205.15418

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().