Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems

Abstract

WHEN A COLLEGE GRADUATE decides to pursue a higher degree at a particular institution, one of the first challenges she faces is finding an apartment. Most institutions have on-campus housing available that is often subsidized and hence more appealing than its alternatives. Usually there are several types of on-campus housing and the attractiveness of each type changes from person to person. Therefore housing offices need to find 44mechanisms" to allocate available housing among the applicants who might have various preferences. In this paper we deal with this class of problems to which we refer as house allocation problems.2 Formally, there are n agents who collectively own n indivisible objects, say houses, and each agent has preferences over objects.3 An allocation is a matching of houses to agents and a matching mechanism is a systematic procedure to select a matching for each problem.