Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange

Ana Viana, Xenia Klimentova, Péter Biró and Flip Klijn
Authors registered in the RePEc Author Service: Péter Biró

No 1235, Working Papers from Barcelona School of Economics

Abstract: In a housing market of Shapley and Scarf [48], 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 extend this result to weak preferences for both the strong core (conditional on non-emptiness) and the set of competitive allocations (using probabilistic allocations and stochastic dominance). There are no counterparts of the latter two results in the two-sided matching literature. We provide examples to show how our results break down when there is a bound on the length of exchange cycles. 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 violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements, even when exchange cycles are bounded, and they do so at a low efficiency cost. As a steppingstone for our simulations, we provide novel integer programming formulations for computing core, competitive, and strong core allocations.

Keywords: core; competitive allocations; housing market; respecting improvement; integer programming; kidney exchange programmes (search for similar items in EconPapers)
JEL-codes: C61 C63 C71 C78 D63 (search for similar items in EconPapers)
Date: 2021-02
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://bw.bse.eu/wp-content/uploads/2021/02/1235-file.pdf (application/pdf)

Related works:
Working Paper: Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange (2021)
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:bge:wpaper:1235

Access Statistics for this paper

More papers in Working Papers from Barcelona School of Economics Contact information at EDIRC.
Bibliographic data for series maintained by Bruno Guallar ().