EnglishНа русском

Переглянути у форматі pdf

ТЕОРІЯ МАТЧИНГУ В ЕКОНОМІЦІ: ПРИКЛАДНІ АСПЕКТИ ЗАСТОСУВАННЯ
В. В. Зубова

Назад

DOI: 10.32702/2306-6792.2019.13.53

УДК: 330.46

В. В. Зубова

ТЕОРІЯ МАТЧИНГУ В ЕКОНОМІЦІ: ПРИКЛАДНІ АСПЕКТИ ЗАСТОСУВАННЯ

Анотація

У статті розглянуто основні питання теорії матчингу та проаналізовано основні прикладні аспекти застосування цієї теорії в економіці. Реалізація алгоритму Гейла-Шеплі дозволяє знайти оптимальні поєднання в ситуаціях, коли для кожного члена однієї групи необхідно знайти відповідну пару в іншій групі. У статті наведено визначення поняття "матчинг", "індивідуально раціональний матчинг", "стійкий матчинг". Окремо висвітлено алгоритм Гейла-Шеплі, який дозволяє застосовувати теорію матчингу в прикладних дослідженнях. Прикладні аспекти застосування теорії матчингу: модель фірми-працівники, ринок молодих лікарів, задача про вибір коледжу, задача про розподіл стипендій між студентами. В рамках проведеного дослідження було побудовано та описано блок-схему реалізації алгоритму Гейла-Шеплі, що є праобразом для подальшої програмної реалізації теорії матчингу.

Ключові слова: матчинг; стійкий матчинг; алгоритм Гейла-Шеплі; модель мар'яжу; модель фірми-працівники; ринок молодих лікарів; задача про вибір коледжу; задача про розподіл стипендій між студентами.

Література

1. Gale D.; Shapley L.S. College Admissions and the Stability of Marriage. The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), 9—15.
2. Balinski M. and Sonmez T. A tale of two mechanism: Student placement. J. Econom. Theory, 84 (1): 73—94, 1999.
3. Gale D. and Sotomayor M. Some remarks on the stable matching problem. Discrete Applied Mathematics, Vol. 11, pp. 223—232, 1985.
4. Serrano R. Cooperative games: core and Shapley value. In Encyclopedia of Complexity and Systems Science. Edited by R. Meyers. New York: Springer, 2009.
5. Stable matching: Theory, evidence and practical design. Material of the Royal Sweden Academy of sciences. The prize in economic sciences 2012.
6. Roberto-Medina A. Implementation of stable solution in a restricted matching market. Review of Economic Design, 3 (2): 137—147, 1998.
7. Halldorsson M.M., Iwana K., Miyazaki S. and Yanagisawa H. Randomized approximation of the stable marriage problem. Theoretical Computer Science, Vol. 325, No. 3, pp. 439—465, 2004.
8. Демонстраційна версія алгоритму Гейла-Шеплі. Каліфорнійський університет. // http://mathsite.math.berkeley.edu/smp/smp.html
9. Демонстраційна версія алгоритму на JavaScript Бартона ван Ноута // http://sephlietz.com/gale-shapley/
10. Dubins L.E., Freedman D.A. Machiavelli and the Gale-Shapley Algorithm. The American Mathematical Monthly, Vol. 88, No. 7 (Aug-Sep., 1981), pp. 485—494.
11. Boros E., Gurvich V., Jastar S. and Krasner. Stable matching in three-sided systems with cyclic preferences. Discrete Mathematics, Vol. 289, pp. 1—10, 2004.
12. Biro Peter. Student Admissions in Hungary as Gale and Shapley Envisaged. Technical Report. Department of Computing Science. University of Glasgow, UK. Glasgow G12 8QQ, TR-2008-291. October 2008.
13. Braun S., Dwenger N., and Kubler D. Telling the truth may not pay off: An empirical study of centralized university admission in Germany. 2007. SFB 649 Discussion Paper 2007-070.
14. Roth A.E. and Sotomayor M. Two-sided matching, volume 18 of Econometric Society Monographs. Cambridge University Press, Cambridge, 1990. A study in game-theoretic modeling and analysis, With a foreword by Robert Aumann.
15. Roth A.E. Deferred Acceptance Algorithms: History, Theory, Practice, and Open questions. Internat. J. Game Theory, 36, 2008.
16. Abdulkadiroglu A., Pathak P.A., Roth A.E. and Sonmez T. The Boston public school match. American Economics Review, Papers and Proceedings, 95(2): 368—371, 2005.
17. Abdulkadiroglu A., Pathak P.A., Roth A.E. The New York City high school match. American Economics Review, Papers and Proceedings, 95(2): 364—367, 2005.

V. Zubova

MATHING THEORY IN THE ECONOMY: APPLICABLE ASPECTS OF APPLICATION

Summary

The article deals with the main questions of the matching theory and the main applied aspects of the application of this theory in the economy were analyzed. The implementation of the Gail-Sheply algorithm allows to find optimal combinations in situations where for each member of the same group one needs to find the corresponding pair in another group. The article defines the concept of "match", "individually rational match", "stable match". Separately covered by the Gail-Sheply algorithm, which allows applying the theory of match in applied research. The model of firm-workers, the market of young doctors, the task of choosing a college, the problem of the distribution of scholarships among students were considered as applied aspects of the application of the matching theory. The problem of effective distribution was considered on the example of finding graduates of schools of nominal scholarships of universities according to the results of the EIT. Each university has only 1 scholarship for each specialty. The task of bilateral one-to-one matchmaking (1«1) is realized in the same way. To solve the problem, authors formed a set of search engines (graduates of schools that enter universities) and a set of elected specialities. Each of these positions — a pair of "specialty-university", was called "uni-speciality". In the framework of this research, a block diagram of the implementation of the Gail-Sheply algorithm was constructed and described, which is a prototype for further program implementation of the matching theory. An important quality criterion is to ensure equitable access to high-quality higher education on a competitive basis and to ensure that those who can successfully study in a particular direction and have a motivational factor are selected for the higher education institutions. The consistent implementation of these principles is possible on the basis of modern scientific methods, innovative approaches, which allow to effectively solve applied problems.

Keywords: matching; stable match; Gail-Shepel's algorithm; a model of a marriage; a model of firm-workers; a market for young doctors; the task of choosing a college; the task of distributing scholarships among students.

References

1. Gale, D. and Shapley, L.S. (1962), "College Admissions and the Stability of Marriage", The American Mathematical Monthly, vol. 69, pp. 9—15.
2. Balinski, M. and Sonmez, T. (1999), "A tale of two mechanism: Student placement", J. Econom. Theory, vol. 84 (1), pp. 73—94.
3. Gale, D. and Sotomayor, M. (1985), "Some remarks on the stable matching problem", Discrete Applied Mathematics, vol. 11, pp. 223—232.
4. Serrano, R. (2009), Cooperative games: core and Shapley value. In Encyclopedia of Complexity and Systems Science, Springer, New York, USA.
5. Material of the Royal Sweden Academy of sciences (2012), "Stable matching: Theory, evidence and practical design", available at: https://www.nobelprize.org/uploads/2018/06/popular-economicsciences2012.pdf (Accessed 16 June 2019).
6. Roberto-Medina, A. (1998), "Implementation of stable solution in a restricted matching market. Review of Economic Design", EconPapers, vol. 3 (2), pp. 137—147.
7. Halldorsson, M.M. Iwana, K. Miyazaki, S. and Yanagisawa, H. (2004), "Randomized approximation of the stable marriage problem", Theoretical Computer Science, vol. 325 (3), pp. 439—465.
8. MathSite (2019), "Stable Marriage Problem", available at: http://mathsite.math.berkeley.edu/smp/smp.html (Accessed 16 June 2019).
9. Sephlietz (2019), "Gale-Shapley Algorithm Demonstration", available at: http://sephlietz.com/gale-shapley/ (Accessed 16 June 2019).
10. Dubins, L.E. and Freedman, D.A. (1981), "Machiavelli and the Gale-Shapley Algorithm", The American Mathematical Monthly, vol. 88 (7), pp. 485—494.
11. Boros, E. Gurvich, V. Jastar, S. and Krasner, D. (2004), "Stable matching in three-sided systems with cyclic preferences", Discrete Mathematics, vol. 289, pp. 1—10.
12. Biro, P. (2008), Student Admissions in Hungary as Gale and Shapley Envisaged. Department of Computing Science, University of Glasgow, UK.
13. Braun, S. Dwenger, N. and Kuble, D. (2007), "Telling the truth may not pay off: An empirical study of centralized university admission in Germany", SFB 649, Germany.
14. Roth, A.E. and Sotomayor, M. (1990), "Two-sided matching. Econometric and Society Monographs", Cambridge University Press, Cambridge, UK.
15. Roth, A.E. (2008), "Deferred Acceptance Algorithms: History, Theory, Practice and Open questions", Internat. J. Game Theory, vol. 36.
16. Abdulkadiroglu, A. Pathak, P.A. Roth, A.E. and Sonmez, T. (2005), "The Boston public school match", American Economics Review, Papers and Proceedings, vol. 95 (2), pp. 368—371.
17. Abdulkadiroglu, A. Pathak, P.A. and Roth, A.E. (2005), "The New York City high school match", American Economics Review, Papers and Proceedings, vol. 95 (2), pp. 364—367.

№ 13-14 2019, стор. 53 - 59

Дата публікації: 2019-07-24

Кількість переглядів: 59

Відомості про авторів

В. В. Зубова

викладач кафедри економічної кібернетики та прикладної економікиХарківський національний університет імені В.Н. Каразіна

V. Zubova

Lecturer, V.N. Karazin Kharkiv National University, Kharkiv

ORCID:

0000-0002-5310-0932

Як цитувати статтю

Зубова В. В. Теорія матчингу в економіці: прикладні аспекти застосування. Агросвіт. 2019. № 13-14. С. 53–59. DOI: 10.32702/2306-6792.2019.13-14.53

Zubova, V. (2019), “Mathing theory in the economy: applicable aspects of application”, Agrosvit, vol. 13-14, pp. 53–59. DOI: 10.32702/2306-6792.2019.13-14.53

Creative Commons License

Стаття розповсюджується за ліцензією
Creative Commons Attribution 4.0 Міжнародна.