Review of the Theory of Stable Matchings and Contract Systems

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

A review of works devoted to the theory of stable matchings or, more generally, of stable networks of contracts is given. A set (network) of contracts is called stable if no coalition has an available contract that gives all coalition members strictly more than the proposed set. In a special case, this concept was introduced in 1962 by Gale and Shapley and has since gone a long way in its development both theoretically (theorems, structures, and algorithms) and in the field of applications in economics, physics, biology, and mathematics.

About the authors

V. I. Danilov

Central Economics and Mathematics Institute, Russian Academy of Sciences

Author for correspondence.
Email: vdanilov43@mail.ru
117418, Moscow, Russia

References

  1. Айзерман М.А., Алескеров Ф.Т. Выбор вариантов: основы теории. М.: Наука, 1990.
  2. Алескеров Ф.Т., Кисельгоф С.Г. Лауреаты Нобелевской премии – 2012: Ллойд Шепли и Элвин Рот // Экономический журнал ВШЭ. 2012. Т. 16. № 4. С. 433–343.
  3. Ловас Л., Пламмер М. Прикладные задачи теории графов. М.: Мир, 1998. (Lovasz L. Plummer M. Matching theory. Budapest, 1986).
  4. Васин А.А., Гурвич В.А. Примиримые наборы коалиций для игр в нормальной форме // В сб. “Численные методы оптимизации.” Иркутск: СЭИ. 1978.
  5. Данилов В.И. О теореме Скарфа // Экономика и матем. методы. 1999. Т. 35 (3). С. 137–139.
  6. Данилов В.И. Стабильные системы гибких договоров // Ж. новой экономической ассоциации. 2021. Т. 3 (51). С. 32–49.
  7. Кисельгоф С.Г. Моделирование приемной кампании: вузы различного качества и абитуриенты с квадратичной функцией полезности // Проблемы управления. 2012. Т. 5. С. 33–40.
  8. Abdulkadiroglu A., Sonmez T. School choice: A mechanism design approach // Amer Economic Review. 2003. V. 93. P. 729–747.
  9. Abeledo H.G., Blum Y., Rothblum U.G. Canonical monotone decompositions of fractional stable matchings // Int. J. Game Theory. 1996. V. 25. P. 161–176.
  10. Abeledo H., Isaak G. A characterization of graphs that ensure the existence of stable matchings // Mathematical Social Sciences. 1991. V. 22. P. 93–96.
  11. Abraham D., Biró P., Manlove D. ‘Almost stable’ matchings in the roommates problem // In Approximation and online algorithms, volume 3879 of Lecture Notes in Comput. Sci. Springer. Berlin. 2006. P. 1–14.
  12. Ágoston K., Biró P., McBride I. Integer programming methods for special college admissions problems // J. of Combinatorial Optimization. 2016. V. 32. P. 1371–1399.
  13. Adachi H. On a characterization of stable matchings // Economics Letters. 2000. V. 68. P. 43–49.
  14. Aharoni R., Fleiner T. On a lemma of Scarf // J. Combin. Theory Ser. B. 2003. V. 87 (1). P. 72–80.
  15. Aldershof B., Carducci O., Lorenc D. Refined inequalities for stable marriage // Constraints. 1999. V. 4 (3). P. 281–292.
  16. Alimudin A., Ishida Y. Matching-Updating Mechanism: A Solution for the Stable Marriage Problem with Dynamic Preferences // Entropy. 2022. V. 24. P. 263.
  17. Alkan A. Nonexistence of stable threesome matchings // Math. Soc. Sci. 1988. V. 16 (2). P. 207–209.
  18. Alkan A., Gale D. The core of the matching game // Game and economic behavior. 1990. V. 2. P. 203–212.
  19. Alkan A., Gale D. Stable schedule matching under revealed preference // J. Economic Theory. 2003. V. 112 (2). P. 289–306.
  20. Atay A., Nuñez M. Multi-sided assignment games on -partite graphs // UB Economics Working Papers 2017/357.
  21. Azevedo E.M., Hatfield J.W. Existence of Equilibrium in Large Matching Markets with Complementarities // Available at SSRN 3268884 (2018). https://doi.org/10.2139/ssrn.3268884
  22. Aziz H., Biró P., Gaspers S., de Haan R., Mattei N., Rastegari B. Stable Matching with Uncertain Linear Preferences // Algorithmica. 2020. V. 82. P. 1410–1433.
  23. Aziz H., Klaus B. Random matching under priorities: stability and no envy concepts // Social Choice and Welfare. 2019. V. 53(2). P. 213–259.
  24. Baïou M., Balinski M. Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry) // Discrete Appl. Math. 2000. V. 101 (1–3). P. 1–12.
  25. Baïou M., Balinski M. The stable allocation (or ordinal transportation) problem // Math. Oper. Res. 2002. V. 27(3). P. 485–503.
  26. Balinski M., Gale D. On the Core of the Assignment Game // In: Game Theory and Applications. Economic Theory, Econometrics, and Mathematical Economics. 1990. P. 373–374.
  27. Balinski M., Ratier G. Graphs and Marriages // The American Mathematical Monthly. 1998. V. 105. № 5. P. 430–445.
  28. Bando K., Hirai T. Stability and venture structures in multilateral matching // J. of EconomicTheory. 2021. V. 196. 105292.
  29. Bansal V., Agrawal A., Malhotra V.S. Stable marriages with multiple partners: efficient search for an optimal solution // Proc. ICALP. 2003. LNCS 2719. P. 527–542.
  30. Bhatnagar A., Gambhir V., Thakur M. A new perspective to stable marriage problem in profit maximization of matrimonial websites // J. Inform. Process. Syst. 2018. V. 14 (4). P. 961–979.
  31. Benjamin A.T., Converse C., Krieger H.A. How do I marry thee? Let me count the ways // Discrete Applied Mathematics. 1995. V. 59. P. 285–292.
  32. Biró P. The stable matching problem and its generalizations: an algorithmic and game theoretical approach // PhD Thesis. Budapest 2007.
  33. Biró P., Fleiner T. Fractional solutions for capacitated NTU-games, with applications to stable matchings // Discrete Optimization. 2016. V. 22. Part A. P. 241–254.
  34. Biró P., Klijn F. Matching with couples: A multidisciplinary survey // International Game Theory Review. 2013. V. 15. 1340008.
  35. Biró P., McDermid E. Three-Sided Stable Matchings with Cyclic Preferences // Algorithmica. 2010. V. 58. P. 5–18.
  36. Blair C. Every Finite Distributive Lattice is a Set of Stable Matchings // J. of Combinatorial Theory, Series A. 1984. V. 37. P. 353–356.
  37. Blair C. The lattice structure of the set of stable matchings with multiple partners // Math. Oper. Res. 1988. V. 13 (4). 619–628.
  38. Boros E., Gurvich V., Jastar S., Krasner D. Stable matchings in three-sided systems with cyclic preferences // Discrete Mathematics. 2006. V. 289. P. 1–10.
  39. Boros E., Gurvich V., Vasin A. Stable families of coalitions and normal hypergraphs // Mathematical Social Sciences. 1997. V. 34. P. 107–123.
  40. Caldarelli G., Capocci A. Beauty and distance in the stable marriage problem // Physica A. 2001. V. 300 (1–2) C. 325–331.
  41. Cantala D. Matching Markets: The Particular Case of Couples // Economics Bulletin. 2004. V. 3. P. 1–11.
  42. Chambers C.P. Consistency in the probabilistic assignment model // J. of Mathematical Economics. 2004. V. 40. P. 953–962.
  43. Chambers C.P., Yenmez M.B. Choice and Matching // American Economic Journal: Microeconomics. 2017. V. 9 (3). P. 126–147.
  44. Cechlárová K., Fleiner T. On a generalization of the stable roommates problem // ACM Trans. Algorithms. 2005. V. 1 (1). P. 143–156.
  45. Che Y.-K., Kim J., Kojima F. Stable matching in large economies // Econometrica. 2019. V. 87 (1). P. 65–110.
  46. Chowdhury S. Matching theory for cognitive radio networks: An overview // ICT Express. 2019. V. 5 (1). P. 12–15.
  47. Chung K. On the Existence of Stable Roommate Matchings // Games and Economic Behavior. 2000. V. 33. P. 206–230.
  48. Celik O., Knoblauch V. Marriage Matching with Correlated Preferences // Working papers University of Connecticut, Department of Economics. 2007. No 2007–16.
  49. Cooper F. Fair and large stable matchings in the stable marriage and student-project allocation problems // Thesis for Doctor of Philosophy. 2020.
  50. Cui L., Jia W. Cyclic stable matching for three-sided networking services // Comput. Netw. 2013. V. 57 (1). P. 351–363.
  51. Danilov V., Koshevoy G., Lang C. Gross substitution, discrete convexity, and submodularity // Discrete Applied Mathematics. 2003. V. 131 (2). P. 283–298.
  52. Danilov V.I. Existence of stable matchings in some three-sided systems // Math. Social Sci. 2003. V. 46 (2). P. 145–148.
  53. Danilov V.I. Choice functions on posets // выxoдит в Order, cм. arXiv:2101.11965[math.CO].
  54. Danilov V.I., Koshevoy G.A. Stable sets of contracts in two-sided markets // arXiv:2108.06786 [math.CO].
  55. Danilov V.I., Karzanov A.V. Stable and metastable contract networks // arXiv:2202.13089 [math.CO].
  56. Dean B.C., Munshi S. Faster Algorithms for Stable Allocation Problems // Algorithmica. 2010. V. 58. P. 59–81.
  57. Delorme M., Garcia S., Gondzio J., Kalcsics J., Manlove D., Pettersson W. Mathematical models for stable matching problems with ties and incomplete lists // European Journal of Operational Research. 2019. V. 277. P. 426–441.
  58. Demange G., Gale D., Sotomayor M. A furter note on the stable matching priblem // Discrete Applied Mathematics. 1987. V. 16. P. 217–222.
  59. Drgas-Burchardt E., Switalski Z. A number of stable matchings in models of the Gale-Shapley type // Discrete Appl. Math. 2013. V. 161 (18). P. 2932–2936.
  60. Dubins L., Freedman D. Machiavelli and the Gale-Shapley algorithm // Amer. Math. Monthly. 1981. V. 88 (7). P. 485–494.
  61. M. Dzierzawa M., Oméro M.-J. Statistics of stable marriages // Physica A. 2000. V. 287 (1-2). P. 321–333.
  62. Echenique F., Oviedo J. A Theory of Stability in Many-To-Many Matching Markets // Theoretical Economics. 2006. V. 1. P. 233–273.
  63. Echenique F., Yenmez B. A Solution to Matching with Preferences Over Colleagues // Games and Economic Behavior. 2007. V. 59. P. 46–71.
  64. Eeckhout J. On the uniqueness of stable marriage matchings // Economics Letters. 2000. V. 69. P. 1–8.
  65. Eguchi A., Fujishige S., Tamura A. A generalized Gale-Shapley algorithm for a discrete-concave stable-marriage model // In Algorithms and computation. volume 2906 of Lecture Notes in Comput. Sci. 2003. P. 495–504. Springer, Berlin.
  66. Eirinakis P., Magos D., Mourtos I., Miliotis P. Polyhedral Aspects of Stable Marriage // Mathematics of Operations Research. 2014. V. 39 (3). P. 656–671.
  67. Eirinakis P., Magos D., Mourtos I. The stable -matching polytope revisited // Discrete Appl. Math. 2018. V. 250. P. 186–201.
  68. Eriksson K., Sjostrand J., Strimling P. Threedimensional stable matching with cyclic preferences // Mathematical Social Sciences. 2006. V. 52. P. 77–87.
  69. Eriksson K., Karlander J. Stable outcomes of the roommate game with transferable utility // Internat. J. Game Theory. 2000. V. 29 (4). P. 555–569.
  70. Everaere P., Morge M., Picard G. Minimal concession strategy for reaching fair, optimal and stable marriages // in: Proc. of the 2013 International Conference on Autonomous Agents and Multi-Agent Systems. Citeseer. 2013. P. 1319–1320.
  71. Farooq R., Fleiner T., Tamura A. Matching with partially oedered contracts // Japan J. Industrial and Applied Mathematics. 2012. V. 29. 401–417.
  72. Feder T. A New Fixed Point Approach for Stable Networks and Stable Marriages // J. of computer and system sciences. 1992. V. 45. P. 233–284.
  73. Fenoaltea E., Baybusinov I., Zhao J., Zhou L., Zhang Y.-C. The Stable Marriage Problem: An interdisciplinary review from the physicist’s perspective // Physics Reports. 2021. V. 917. P. 1–79.
  74. Fleiner T. A fixed-point approach to stable matchings and some applications // Math. Oper. Res. 2003. V. 28 (1). P. 103–126.
  75. Fleiner T. On the stable -matching polytope // Math. Social Sci. 2003. V. 46 (2). P. 149–158.
  76. Fleiner T. The stable roommate problem with choice functions // Algorithmica. 2010. 58. P. 82–101.
  77. Fleiner T. On stable matchings and flows // Algorithms. 2014. V. 7. P. 1–14.
  78. Fleiner T., Jagadeesan R., Janko Z., Teytelboym A. Trading networks with frictions // Econometrica. 2019. V. 87. № 5. P. 1633–1661.
  79. Fujishige S., Tamura A. A general two-sided matching market with discrete concave utility functions // Discrete Appl. Math. 2006. V. 154 (6). P. 950–970.
  80. Gale D. The two-sided matching problem: origin, development and current issues // International Game Theory Review. 2001. V. 3. № 2-3. P. 237–252.
  81. Gale D., Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly. 1962. V. 69 (1). P. 9–15.
  82. Gale D., Sotomayor M. Ms. Machiavelli and the stable matching problem // Amer. Math. Monthly. 1985. V. 92 (4). P. 261–268.
  83. Gale D., Sotomayor M. Some remarks on the stable matching problem // Discrete Appl. Math. 1985. V. 11 (3). P. 223–232.
  84. Gelain M., Pini M. Rossi F., Venable K., Walsh T. Procedural fairness in stable marriage problems // Proc. of 10th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2011). Tumer, Yolum, Sonenberg and Stone (eds.). 2011. 2–6. Taipei. Taiwan. P. 1209–1210.
  85. Giannakopoulos I., Karras P., Tsoumakos D., Doka K., Koziris N. An equitable solution to the stable marriage problem // in: 27th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE. 2015. P. 989–996.
  86. Gonczarowski Y., Nisan N., Ostrovsky R., Rosenbaum W. A stable marriage requires communication// Games and Economic Behavior. 2019. V. 118. Issue C. P. 626–647.
  87. Goyal A., Dubinkina V., Maslov S. Multiple stable states in microbial communities explained by the stable marriage problem // ISME Journal. 2018. V. 12 (12). P. 2823–2834.
  88. Gul F., Stacchetti E. Walras equilibrium with gross substitutes // J. of Economic Theory. 1999. V. 87. P. 95–124.
  89. Gusfield D., Irving R.W. The Stable Marriage Problem: Structure and Algorithms. Boston: MIT Press. MA. 1989.
  90. Gusfield D., Irving R., Leather P., Saks M. Every finite distributive lattice is a set of stable matchings for a small stable marriage instance // J. of Combinatorial Theory, Series A. 1987. V. 44. Issue 2. P. 304–309.
  91. Halldórsson M.M., Irving R.W., Iwama K., Manlove D.F., Miyazaki S., Morita Y., Scott S. Approximability Results for Stable Marriage Problems with Ties // Theoretical Computer Science. 2003. V. 306. P. 431–447.
  92. Halldórsson M.M., Iwama K., Miyazaki S., Yanagisawa H. Randomized approximation of the stable marriage problem // Theoretical Computer Science. 2004. V. 325. № 3. P. 439–465.
  93. Halldórsson M.M., Iwama K., Miyazaki S., Yanagisawa H. Improved approximation results of the stable marriage problem // ACM Transactions on Algorithms. 2007. V. 3. Issue 3. Article No. 30.
  94. Hatfield J., Milgrom P. Matching with Contracts // Amer. Econ. Rev. 2005. V. 95 (4). P. 913–935.
  95. Hatfield J., Kojima F. Substitutes and stability for matching with contracts // Journal of Economic Theory. 2010. V. 145 (5). P. 1704–1723.
  96. Hatfield J.W., Kominers S.D. Matching in Networks With Bilateral Contracts // American Economic Journal: Microeconomics. 2012. V. 4. P. 176–208.
  97. Hatfield J.W., Kominers S.D. Multilateral Matching // J. of Economic Theory. 156. issue C. P. 175–206.
  98. Hatfield J.W., Kominers S.D. Contract Design and Stability in Many-to-Many Matching // Games and Economic Behavior. 2017. V. 101. P. 78–97.
  99. Hatfield W., Scott D., Nichifor A., Ostrovsky M., Westkamp A. Stability and competitive equilibrium in trading networks // J. of Political Economy. 2013. V. 121(5). P. 966–1005.
  100. Henderson D. On marriage, kidneys and the Economics Nobel // Wall Street J. 2012. Oct. 15.
  101. Hidakatsu J. Structure of the Stable Marriage and Stable Roommate Problems and Applications // Tesis. University of South Carolina. 2016.
  102. Huang C.-C. Two’s company, three’s a crowd: Stable family and threesome roommates problems // in: European Symposium on Algorithms. Springer. 2007. P. 558–569.
  103. Huang C. Stable matching: an integer programming approach // arXiv:2103.03418v1 [econ.TH].
  104. Huang C. Unidirectional substitutes and complements // arXiv:2108.12572v1 [econ.TH].
  105. Huang C.-C. Classified Stable Matching // Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms. 2010. P. 1235–1253.
  106. Irving R., Leather P., Gusfield D. An efficient algorithm for the “optimal” stable marriage // J. of the ACM. 1987. V. 34. № 3. P. 532–543.
  107. Irving R., Manlove D., Scott S. The hospitals/residents problem with ties // in: Scandinavian Workshop on Algorithm Theory. Springer. 2000. P. 259–271.
  108. Irving R. An efficient algorithm for the “stable roommates” problem // J. Algorithms. 1985. V. 6 (4). P. 577–595.
  109. Irving R. Stable marriage and indifference // Discrete Applied Mathematics. 1994. V. 48. P. 261–272.
  110. Irving R. The cycle roommates problem: a hard case of kidney exchange // Inform. Process. Lett. 2007. V. 103 (1). P. 1–4.
  111. Irving R., Manlove D. The stable roommates problem with ties // J. Algorithms. 2002. V. 43 (1). P. 85–105.
  112. Irving R., Leather P. The complexity of counting stable marriages // SIAM J. Comput. 1986. V. 15 (3). P. 655–667.
  113. Irving R., Scott S. The stable fixtures problem – A many-to-many extension of stable roommates // Discrete Applied Mathematics. 2007. V. 155. P. 2118–2129.
  114. Iwama K., Miyazaki S., Okamoto K. Stable roommates problem with triple rooms // Proc. 10th KOREA–JA-PAN Joint Workshop on Algorithms and Computation (WAAC 2007). 2007. P. 105–112.
  115. Ishida Y. Antibody-based computing: an application to the stable marriage problem // Artif. Life Robot. 2008. V. 12 (1-2). P. 125–128.
  116. Iwama K., Miyazaki S. A survey of the stable marriage problem and its variants // in: International Conference on Informatics Education and Research for Knowledge-Circulating Society. ICKS. 2008. P. 131–136.
  117. Jackson M., Watts A. Equilibrium Existence in Bipartite Social Games: A Generalization of Stable Matchings // Article in Economics Bulletin. 2008. V. 3. № 12. P. 1–8.
  118. Kamiyama N. A New Approach to the Pareto Stable Matching Problem // Mathematics of Operations Research. 2014. V. 39. № 3. P. 851–862.
  119. Kanade V., Leonardos N., Magniez F. Stable Matching with Evolving Preferences.//In LIPICS (Leibniz International Proceedings in Informatics). V. 60. P. 36:1–36:13.
  120. Kaneko M., Wooders M.H. Cores of partitioning games // Math. Soc. Sci. 1982. V. 3 (4). P. 313–327.
  121. Karlin A., Gharan S., Weber R. A simply exponential upper bound on the maximum number of stable matchings // in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. 2018. P. 920–925.
  122. Karzanov A.V. On stable flows and preflows // arXiv:2209.00614 [math.CO] Sep 2022.
  123. Kelso A., Crawford V. Job matching, coalition formation, and gross substitutes // Econometrica. 1982. V. 50. № 6. P. 1483–1504.
  124. Király T., Pap J. Kernels, stable matchings, and Scarf’s Lemma // Egerváry Research Group, TR-2008-13, 2008.
  125. Kiselgof S. Matchings with interval order preferences: efficiency vs strategy-proofness // Procedia Computer Science. 2014. V. 31. P. 807–813.
  126. Klaus B., Walzl M. Stable many-to-many matchings with contracts // J. of Mathematical Economics. 2009. V. 45. P. 422–434.
  127. Klijn F., Yazici A. A Many-to-Many ‘Rural Hospital Theorem’ // J. of mathematical economics. 2014. V. 54. P. 63–73.
  128. Knoblauch V. Marriage Matching: A Conjecture of Donald Knuth // University of Connecticut. Working Paper 2007-15.
  129. Knuth D. Mariages Stables. Les Presses de L’Université de Montréal. 1976. (English translation: Stable Marriage and its Relation to Other Combinatorial Problems. Providence, R.I. : American Mathematical Society. 1997.)
  130. Kojima F. Finding all stable matchings with couples // J. of Dynamics and Games. 2015. V. 2 (2). P. 321–330.
  131. Komornik V., Komornik Z., Viauroux C. Stable schedule matchings by a fixed point method // Acta Mathematica Hungarica. 2012. V. 135. P. 67–79.
  132. Kujansuu E., Lindberg T., Mokinen E. The stable roommates problem and chess tournament pairings // Divulg. Mat. 1999. V. 7 (1). P. 19–28.
  133. Lage-Castellanos A., Mulet R. The marriage problem: From the bar of appointments to the agency // Physica A. 2006. V. 364. P. 389–402.
  134. Lam C.-K., Plaxton C.G. On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences. // Theory of Computing Systems. 2022. V. 66 (2). P. 679–695.
  135. Lerner E.Yu., Lerner R.E. Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences // arXiv:2101.08223 [math.CO].
  136. Lovász L. Normal hypergraphs and the perfect graph conjecture // Discrete Math. 1972. V. 2 (3). P. 253–267.
  137. Malhotra V.S. On the stability of multiple partner stable marriages with ties // Proc. ESA. 2004. LNCS 3221. P. 508–519.
  138. Manlove D.F. Stable marriage with ties and unacceptable partners // University of Glasgow, Computing Science Department Research Report. 1999. TR-1999-29.
  139. Manlove D., Irving R., Iwama K., Miyazaki S., Morita Y. Hard variants of stable marriage // Theoret. Comput. Sci. 2002. V. 276 (1-2). P. 261–279.
  140. Martinez R., Masso J., Neme A., Oviedo J. An algorithm to compute the full set of many-to-many stable matchings // Math. Social Sci. 2004. V. 47 (2). P. 187–210.
  141. McVitie D., Wilson L. The stable marriage problem // Commun. ACM. 1971. V. 14 (7). P. 486–490.
  142. Neme P., Oviedo J. A note on the lattice structure for matching markets via linear programming // J. of Dynamics and Games. 2021. V. 8. 1. P. 61–67.
  143. Ng C., Hirschberg D. Three-dimensional stable matching problems // SIAM J. Discrete Math. 1991. V. 4 (2). P. 245–252.
  144. Nuñez M., Rafels C. A survey on assignement markets // J. of Dynamics and Games. 2015. V. 2. Num-ber 3–4. P. 227–256.
  145. Oméro M.-J., Dzierzawa M., Marsili M., Zhang Y.-C. Scaling Behavior in the Stable Marriage Problem // ar-Xiv:cond-mat/9708181v1. 1997.
  146. Ostrovsky M. Stability in supply chain network // Amer. Econ. Rev. 2006. V. 98. P. 897–923.
  147. Ostrovsky R., Rosenbaum W. It’s not easy being three: The approximability of three-dimensional stable matching problems // 2014. ArXiv preprint arXiv:1412.1130.
  148. Panchal N., Sharma S. An Efficient Algorithm for Three Dimensional Cyclic Stable Matching // International Journal of Engineering Research & Technology. 2014. V. 3. Issue 4. P. 2539–2544.
  149. Pittel B. The “stable roommates” problem with random preferences // Ann. Probab. 1993. V. 21. № 3. P. 1441–1477.
  150. Pittel B. The average number of stable matchings // SIAM J. Discrete Math. 1989. V. 2 (4). P. 530–549.
  151. Pittel B. On likely solutions of the stable matching problem with unequal numbers of men and women // Math. Oper. Res. 2019. V. 44 (1). P. 122–146.
  152. Plott C. Path independence, Rationality, and social choice // Econometrica. 1973. V. 41. P. 1075–1091.
  153. Prosser P. Stable roommates and constraint programming // In: 11-th International Conference. CPAIOR. 2014. Cork. Ireland. P. 15–28.
  154. Pycia M. Stability and preference alignment in matching and coalition formation // Econometrica. 2012. V. 80(1). P. 323–362.
  155. Ratier G. On the stable marriage polytope // Discrete Mathematics. 1996. V. 148. P. 141–159.
  156. Ronn E. NP-Complete stable matching problems // J. Algorithms. 1990. V. V. 11 (2). P. 285–304.
  157. Rostek M., Yoder N. Matching with complementary contracts // Econometrica. 2020. V. 88 (5). P. 1793–1827.
  158. Roth A. Stability and polarization of interests in job matching // Econometrica. 1984. V. 52. P. 47–57.
  159. Roth A. On the allocation of residents to rural hospitals: a general property of two-sided matching markets // Econometrica. 1986. V. 54. P. 425–427.
  160. Roth A., Sotomayor M. Two-sided Matching: A Study in Game-theoretic Modeling and Analysis. Cambridge: Cambridge University Press. 1991.
  161. Roth A., Sönmez T., Ünver M. Kidney exchange // Quart. J. Econ. 2004. V. 119 (2). P. 457–488.
  162. Roth A., Sönmez T., Ünver M. Pairwise kidney exchange // J. Economic Theory. 2005. V. 125 (2). P. 151–188.
  163. Roth A., Vande Vate J. Random paths to stability in two-sided matching // Econometrica. 1990. V. 58. P. 475–1480.
  164. Roth A., Rothblum U.G., Vande Vate J. Stable matchings, optimal assignments, and linear programming // Math. Oper. Res. 1993. V. 18. P. 803–828.
  165. Scott S. A Study of Stable Marriage Problems with Ties // Ph.D. thesis. University of Glasgow, 2005.
  166. Shapley L., Shubik M. The assignment game. I. The core // Internat. J. Game Theory. 1972. V. 1(2). P. 111–130.
  167. Shi G.-Y., Kong Y., Chen B., Yuan G., Wu R. Instability in stable marriage problem: Matching unequally numbered men and women // Complexity. 2018. Article ID 7409397.
  168. Sotomayor M. Three remarks on the many-to-many stable matching problem // Math. Soc. Sci. 1999. V. 38 (1). P. 55–70.
  169. Sotomayor M. My encounters with David Gale // Games and Economic Behavior. 2009. V. 66. P. 643–646.
  170. Stuart H. The supplier-firm-buyer game and its -sided generalization // Mathematical Social Sciences. 1997. V. 34. P. 21–27.
  171. Subramanian A. A new approach to stable matching problems // SIAM J. Comput. 1994. V. 23 (4). P. 671–700.
  172. Szestopalow M. Properties of Stable Matchings // Thesis Waterloo, Ontario, Canada. 2010.
  173. Tan J. A necessary and sufficient condition for the existence of a complete stable matching // J. Algorithms. 1991. 12(1). P. 154–178.
  174. Teo C-P., Sethuraman J. The geometry of fractional stabe matchings and its applications // Mathematics of Operations Research. 1998. V. 23. № 4. P. 874–891.
  175. Teo C.-P., Sethuraman J., Tan W.-P. Gale-Shapley stable marriage problem revisited: Strategic issues and applications // Manage. Sci. 2001. V. 47 (9). P. 1252–1267.
  176. Thurber E. Concerning the maximum number of stable matchings in the stable marriage problem // Discrete Math. 2002. V. 248 (1–3). P. 195–219.
  177. Tong H., Liang H., Bai F. The multi-dimensional stable marriage problem and its application in chemistry. 2015.
  178. Vande Vate J. Linear programming brings marital bliss // Operations Research Letters. 1989. V. 8. Issue 3. P. 147–153.
  179. Wilson L. An analysis of the stable marriage assignment algorithm // BIT Numer. Math. 1972. V. 12 (4). P. 569–575.
  180. Xu H., Li B. Seen as stable marriages // in: 2011 Proceedings IEEE INFOCOM, IEEE. 2011. P. 586–590.
  181. Zhou L. On a Conjecture by Gale about One-Sided Matching Problems // J. of Economic Theory. 1990. V. 52. P. 123–135.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download
2.

Download (13KB)
Indexing metadata
3.

Download (10KB)
Indexing metadata

Copyright (c) 2023 В.И. Данилов

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies