Random mechanisms for house allocation with existing tenants

Abstract

We study the house allocation problem with existing tenants: n houses (stand for "indivisible objects") are to be allocated to n agents; each agent needs exactly one house and has strict preferences; k houses are initially unowned; k agents initially do not own houses; the remaining n - k agents (the so-called "existing tenants") initially own the remaining n - k houses (each owns one). In this setting, we consider various randomized allocation rules under which voluntary participation of existing tenants is assured and the randomization procedure either treats agents equally or discriminates against some (or all) of the existing tenants. We obtain two equivalence results, which generalize the equivalence results in Abdulkadiroglu and Sonmez (1999) and Sonmez and Unver (2005).