مسئله ازدواج پایدار

نوع مقاله : مقاله ترویجی

نویسندگان

1 گروه مهندسی صنایع، دانشکده مهندسی کامپیوتر و صنایع، دانشگاه صنعتی بیرجند، بیرجند، ایران

2 گروه ریاضی، دانشکده علوم و فناوری‌های نوین، دانشگاه تحصیلات تکمیلی صنعتی و فناوری پیشرفته، کرمان، ایران

3 گروه ریاضی، دانشکده علوم، دانشگاه بیرجند، بیرجند، ایران

چکیده

تخصیص پایدار نوعی مفهوم پایداری در جواب مسائل بهینه‌سازی است. با استفاده از این مفهوم می‌توان مسائل متنوعی از جمله مسئله ازدواج پایدار را مطرح کرد. این مسائل کاربردهای زیادی در جهان واقعی دارند تا جایی که مقاله‌ای با موضوع کاربردهای تخصیص پایدار در حوزه اقتصاد موفق به دریافت جایزه نوبلِ اقتصاد شده است. در این مقاله، مسئله ازدواج پایدار و چند مسئله مرتبط دیگر را که از مفهوم تخصیص پایدار استفاده می‌کنند معرفی و در مورد فرمول‌بندی و روش‌ حل ‌آن‌ها بحث می‌کنیم.

کلیدواژه‌ها

موضوعات


[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.