Abstract:
In a housing market of Shapley and Scarf (1974), each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that for strict preferences the unique strong core allocation "respects improvement'': if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We obtain similar results for the domain of weak preferences. Respecting improvements is an important property for applications of the housing markets model such as kidney exchange: it incentivises each patient to bring the best possible set of donors to the market. We conduct computer simulations using markets that resemble the pools of kidney exchange programmes. We compare the game-theoretical solutions with current techniques (maximum size and maximum weight allocations) in terms of price of fairness, number of blocking cycles, and number of violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements and they do so at a low efficiency cost. As a stepping-stone for our simulations, we provide novel integer programming formulations for computing core, strong core, and competitive allocations.