Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

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

Published Online:12 Oct 2023https://doi.org/10.1287/moor.2022.0092

References

  • [1] Abbassi Z, Haghpanah N, Mirrokni V (2015) Exchange market mechanisms without money. Working paper, Columbia University.Google Scholar
  • [2] Abdulkadiroğlu A, Che YK (2010) The role of priorities in assigning indivisible objects: A characterization of top trading cycles. Working paper, Duke University.Google Scholar
  • [3] Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
  • [4] Abraham DJ, Blum A, Sandholm T (2007) Clearing algorithms for barter exchange markets: Enabling nationwide kidney exchanges. Proc. Eighth ACM Conf. Electronic Commerce (ACM, New York), 295–304.Google Scholar
  • [5] Ágoston KC, Biró P, McBride I (2016) Integer programming methods for special college admissions problems. J. Combin. Optim. 32(4):1371–1399.Crossref, Google Scholar
  • [6] Ágoston KC, Biró P, Szántó R (2018) Stable project allocation under distributional constraints. Oper. Res. Perspect. 5:59–68.Crossref, Google Scholar
  • [7] Andersson T, Kratz J (2020) Pairwise kidney exchange over the blood group barrier. Rev. Econom. Stud. 87(3):1091–1133.Crossref, Google Scholar
  • [8] Ashlagi I, Roth AE (2021) Kidney exchange: An operations perspective. Management Sci. 67(9):5455–5478.Link, Google Scholar
  • [9] Baïou M, Balinski M (2000) The stable admissions polytope. Math. Programming 87(3):427–439.Crossref, Google Scholar
  • [10] Balbuzanov I (2020) Short trading cycles: Paired kidney exchange with strict ordinal preferences. Math. Social Sci. 104:78–87.Crossref, Google Scholar
  • [11] Balinski M, Sönmez T (1999) A tale of two mechanisms: Student placement. J. Econom. Theory 84(1):73–94.Crossref, Google Scholar
  • [12] Biró P (2007) The stable matching problem and its generalizations: An algorithmic and game theoretical approach. Unpublished PhD thesis, BME, Mathematics and Computer Science Doctoral School, Budapest.Google Scholar
  • [13] Biró P, Cechlárová K (2007) Inapproximability of the kidney exchange problem. Inform. Processing Lett. 101(5):199–202.Crossref, Google Scholar
  • [14] Biró P, McDermid E (2010) Three-sided stable matchings with cyclic preferences. Algorithmica 58(1):5–18.Crossref, Google Scholar
  • [15] Biró P, Manlove DF, McBride I (2014) The hospitals/residents problem with couples: Complexity and integer programming models. Internat. Sympos. Experiment. Algorithms (Springer, New York), 10–21.Google Scholar
  • [16] Biró P, Haase-Kromwijk B, Andersson T, Ásgeirsson EI, Baltesová T, Boletis I, Bolotinha C, et al. (2019) Building kidney exchange programmes in Europe—An overview of exchange practice and activities. Transplantation 103(7):1514–1522.Crossref, Google Scholar
  • [17] Biró P, van de Klundert J, Manlove D, Pettersson W, Andersson T, Burnapp L, Chromy P, et al. (2021) Modelling and optimisation in European kidney exchange programmes. Eur. J. Oper. Res. 291(2):447–456.Crossref, Google Scholar
  • [18] Carvalho M, Lodi A, Pedroso JP, Viana A (2017) Nash equilibria in the two-player kidney exchange game. Math. Programming 161(1–2):389–417.Crossref, Google Scholar
  • [19] Cechlárová K, Fleiner T (2010) Housing markets through graphs. Algorithmica 58(1):19–33.Crossref, Google Scholar
  • [20] Constantino M, Klimentova X, Viana A, Rais A (2013) New insights on integer-programming models for the kidney exchange problem. Eur. J. Oper. Res. 231(1):57–68.Crossref, Google Scholar
  • [21] Delorme M, García S, Gondzio J, Kalcsics J, Manlove DF, Pettersson W (2019) Mathematical models for stable matching problems with ties and incomplete lists. Eur. J. Oper. Res. 277(2):426–441.Crossref, Google Scholar
  • [22] Dickerson JP, Manlove DF, Plaut B, Sandholm T, Trimble J (2016) Position-indexed formulations for kidney exchange. Proc. 2016 ACM Conf. Economics and Computation (Association for Computing Machinery, New York), 25–42. Google Scholar
  • [23] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
  • [24] Gurobi Optimization (2022) Gurobi optimizer reference manual. Accessed March 23, 2023, http://www.gurobi.com.Google Scholar
  • [25] Hatfield JW, Kojima F, Narita Y (2016) Improving schools through school choice: A market design approach. J. Econom. Theory 166:186–211.Crossref, Google Scholar
  • [26] Huang CC (2010) Circular stable matching and 3-way kidney transplant. Algorithmica 58(1):137–150.Crossref, Google Scholar
  • [27] Klimentova X, Viana A, Pedroso JP, Santos N (2021) Fairness models for multi-agent kidney exchange programs. Omega 102:102333.Crossref, Google Scholar
  • [28] Klimentova X, Biró P, Viana A, Costa V, Pedroso JP (2023) Novel integer programming models for the stable kidney exchange problem. Eur. J. Oper. Res. 307(3):1391–1407.Crossref, Google Scholar
  • [29] Kominers SD (2019) Respect for improvements and comparative statics in matching markets. Working paper, Harvard University.Google Scholar
  • [30] Kuhn HW (1955) The Hungarian method for the assignment problem. Naval Res. Logist. Quart. 2(1–2):83–97.Crossref, Google Scholar
  • [31] Kwanashie A, Manlove DF (2014) An integer programming approach to the hospitals/residents problem with ties. Oper. Res. Proc. (Springer), 263–269.Google Scholar
  • [32] Mak-Hau V (2017) On the kidney exchange problem: Cardinality constrained cycle and chain problems on directed graphs: A survey of integer programming approaches. J. Combin. Optim. 33(1):35–59.Crossref, Google Scholar
  • [33] Manlove D (2013) Algorithmics of Matching Under Preferences, vol. 2 (World Scientific, Singapore).Google Scholar
  • [34] Mincu RS, Biró P, Gyetvai M, Popa A, Verma U (2021) IP solutions for international kidney exchange programmes. Central Eur. J. Oper. Res. 29:403–423.Crossref, Google Scholar
  • [35] Ng C, Hirschberg DS (1991) Three-dimensional stable matching problems. SIAM J. Discrete Math. 4(2):245–252.Crossref, Google Scholar
  • [36] Nicolò A, Rodríguez-Álvarez C (2012) Transplant quality and patients’ preferences in paired kidney exchange. Games Econom. Behav. 74(1):299–310.Crossref, Google Scholar
  • [37] Nicolò A, Rodríguez-Álvarez C (2013) Incentive compatibility and feasibility constraints in housing markets. Soc. Choice Welfare 41(3):625–635.Crossref, Google Scholar
  • [38] Nicolò A, Rodríguez-Álvarez C (2017) Age-based preferences in paired kidney exchange. Games Econom. Behav. 102:508–524.Crossref, Google Scholar
  • [39] Quint T, Wako J (2004) On houseswapping, the strict core, segmentation, and linear programming. Math. Oper. Res. 29(4):861–877.Link, Google Scholar
  • [40] Roth AE, Postlewaite A (1977) Weak vs. strong domination in a market with indivisible goods. J. Math. Econom. 4(2):131–137.Crossref, Google Scholar
  • [41] Roth AE, Sönmez T, Ünver MU (2004) Kidney exchange. Quart. J. Econom. 119(2):457–488.Crossref, Google Scholar
  • [42] Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
  • [43] Roth AE, Sönmez T, Ünver MU (2007) Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. Amer. Econom. Rev. 97(3):828–851.Crossref, Google Scholar
  • [44] Saidman SL, Roth AE, Sönmez T, Ünver MU, Delmonico FL (2006) Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation 81(5):773–782.Crossref, Google Scholar
  • [45] Santos N, Tubertini P, Viana A, Pedroso JP (2017) Kidney exchange simulation and optimization. J. Oper. Res. Soc. 68(12):1521–1532.Crossref, Google Scholar
  • [46] Schlotter I, Biró P, Fleiner T (2021) The core of housing markets from an agent’s perspective: Is it worth sprucing up your home? Internat. Conf. Web Internet Econom. (Springer, New York), 244–261.Google Scholar
  • [47] Shapley LS, Scarf H (1974) On cores and indivisibility. J. Math. Econom. 1(1):23–37.Crossref, Google Scholar
  • [48] Sönmez T, Ünver MU, Yenmez MB (2020) Incentivized kidney exchange. Amer. Econom. Rev. 110(7):2198–2224.Crossref, Google Scholar
  • [49] Sotomayor M (2005) An elementary non-constructive proof of the non-emptiness of the core of the housing market of Shapley and Scarf. Math. Social Sci. 50(3):298–303.Crossref, Google Scholar
  • [50] Wako J (1984) A note on the strong core of a market with indivisible goods. J. Math. Econom. 13(2):189–194.Crossref, Google Scholar
  • [51] Wako J (1991) Some properties of weak domination in an exchange market with indivisible goods. Econom. Stud. Quart. 42(4):303–314.Google Scholar
  • [52] Wako J (1999) Coalition-proofness of the competitive allocations in an indivisible goods market. Fields Inst. Comm. 23:277–283.Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree