Stable marriage problem

Document Type : Promotional Paper

Authors

1 Department of Industrial Engineering, Faculty of Computer and Industrial Engineering, Birjand university of technology, Birjand, Iran

2 Department of Mathematics, Faculty of Modern Sciences and Technologies, University of Advanced Industrial and Technology, Kerman, Iran

3 Department of Mathematics, Faculty of Science, University of Birjand, Birjand, Iran

Abstract

Stable assignment is a concept of stability in the solution of optimization problems. Using this concept, various problems can be formulated, including the Stable Marriage Problem. These problems have numerous real-world applications to the extent that an article on the applications of stable allocation in the field of economics has succeeded in receiving the Nobel Prize in Economics. In this paper, we introduce the Stable Marriage Problem and several other related problems that use the concept of stable assignment. We also discuss their formulation and solution methods.

Keywords

Main Subjects

References

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, New York, 1988.
[2] H. Aziz, P. Biró, S. Gaspers, R. de Haan, N. Mattei and B. Rastegari, Stable matching with uncertain linear preferences, Algo-rithmica, 82 (2020) 1410–1433.
[3] S. Bikhchandani, Stability with one-sided incomplete information, Journal of Economic Theory, 168 (2017) 372–399.
[4] G. Chalkiadakis, E. Elkind and M. Wooldridge, Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, Williston, 2011.
[5] Y. K. Che, J. Kim and F. Kojima, Stable matching in large economies, Econometrica, 87 (2019) 65–110.
[6] A. Cseh and K. Heeger, The stable marriage problem with ties and restricted edges, Discrete Optim., 36 (2020).
[7] K. Dong, Z. Qin and T. Wan, Many-to-One Stable Matching for Prediction in Social Networks, in International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, Springer, New York, 2020, 345–356.
[8] D. Gale and L. S. Shapley, College admissions and the stability of marriage, Amer. Math. Monthly, 69 (1962) 9–15.
[9] R. P. Gilles, The Cooperative Game Theory of Networks and Hierarchies, Springer, New York, 2010.
[10] D. Goldfarb, On the complexity of the simplex method, in Advances in Optimization and Numerical Analysis, S. Gomez and J. P. Hennart, eds., Springer, Dordrecht, 1994, 25–38.
[11] M. Greinecker and C. Kah, Pairwise stable matching in large economies, Econometrica (to appear).
[12] R. W. Irving, An efficient algorithm for the “stable roommates” problem, J. Algorithms, 6 (1985) 577–595.
[13] R. W. Irving, Stable marriage and indifference, Discrete Appl. Math., 48 (1994) 261–272.
[14] C. K. Lam, Algorithms for stable matching with indifferences, Doctoral dissertation, The University of Texas at Austin, 2019.
[15] Q. Liu, G. J. Mailath, A. Postlewaite and L. Samuelson, Stable matching with incomplete information, Econometrica, 82 (2014) 541–587.
[16] D. F. Manlove, The structure of stable marriage with indifference, Discrete Appl. Math., 122 (2002) 167–181.
[17] J. Masso, The theory of stable allocations and the practice of market design, The Nobel Prize in Economics 2012 for Alvin E. Roth and Lloyd S. Shapley, Contributions to Science, 11 (2015) 103–112.
[18] U. G. Rothblum, Characterization of stable matchings as extreme points of a polytope, Math. Program., 54 (1992) 57–67.
[19] T. Tullis, How game theory helped improve New York City’s high school application process, The New York Times, 2014.
Mathematics and Society
Volume 5, Issue 4
December 2020
Pages 1-12

Files

History

  • Receive Date: 28 March 2021
  • Revise Date: 02 October 2021
  • Accept Date: 02 October 2021
  • Publish Date: 19 February 2021

Share

How to cite

Statistics