Grafy a teoria stabilnych alokacji

Kozioł-Kaczorek, Dorota; Pietrych, Łukasz

doi:10.15611/ekt.2016.3.08

Author

Kozioł-Kaczorek Dorota (Szkoła Główna Gospodarstwa Wiejskiego w Warszawie), Pietrych Łukasz (Szkoła Główna Gospodarstwa Wiejskiego w Warszawie)

Title

Grafy a teoria stabilnych alokacji
Graphs and Theory of Stable Allocation

Source

Ekonometria / Uniwersytet Ekonomiczny we Wrocławiu, 2016, nr 3 (53), s. 102-114, rys., tab., bibliogr. 15 poz.
Econometrics / Uniwersytet Ekonomiczny we Wrocławiu

Keyword

Grafy, Ekonometria, Teoria odroczonej akceptacji
Graphs, Econometrics, Theory of deferred acceptance

Note

streszcz., summ.

Abstract

W pracy omówiono model procesu kojarzenia zaproponowany przez dwóch amerykańskich matematyków: D. Gale'a i L.S. Shapleya. Podstawowym zdefiniowanym przez nich pojęciem był przydział stabilny, który można osiągnąć za pomocą tzw. algorytmu odroczonej akceptacji. W artykule dokonano analizy problematyki poruszanej przez teorię stabilnych alokacji na gruncie teorii grafów. Studia literatury wykazały, że zagadnienia po-ruszane przez tę teorię można analizować za pomocą grafów dwudzielnych i sieci ważonych. Sformułowano również warunki, jakie należy spełnić, aby problem kojarzenia miał rozwiązanie. Odwołano się do rynku pracy, gdyż poruszane zagadnienie ma zastosowanie w praktyce, szczególnie w projektowaniu systemów rekrutacji pracowników do firm. Celem artykułu było przedstawienie problemu dwustronnych skojarzeń za pomocą języka teorii grafów oraz wskazanie możliwości aplikacyjnych w obszarze poszukiwań i dopasowań osób poszukujących pracy i pracodawców.(abstrakt oryginalny)

The paper discusses a model of matching process which was proposed by two American mathematicians: David Gale and Lloyd S. Shapley. The basic concept defined by them was the stable allocation, which can be achieved with so-called deferred acceptance algorithm. The article analyzes the problems discussed by the theory of stable allocations on the basis of graph theory. It has been shown that the issues raised by this theory can be ana-lyzed using bipartite graphs and networks weighted. They also formulated conditions which should be met in purpose to solve a problem of matching. References relate to the labor market, as a discussed issue is applicable in practice, especially in the design of systems of recruitment companies. The aim of the article is to present the problem of bilateral associa-tions with the use of the language of graph theory and an indication of possible applications in the area of search and match of job seekers and employers.(original abstract)

Accessibility

The Main Library of the Cracow University of Economics
The Library of Warsaw School of Economics
The Library of University of Economics in Katowice
The Main Library of Poznań University of Economics and Business
The Main Library of the Wroclaw University of Economics

Full text

Bibliography

Baïou M., 2016, A note on many-to-many matchings and stable allocations, Discrete Applied Math-ematics, 222, s. 181-184.
Baïou M., Balinski M., 2007, Characterizations of the optimal stable allocation mechanism, Opera-tion Research Letters, 35, s. 392-402.
Biró P., Fleiner T., 2010, Integral stable allocation problem on graphs, Discrete Optimization, 7, s. 64-73.
Bronsztejn I.N., Siemiendiajew K.A., Musiol G., Mühlig, 2013, Nowoczesne kompendium matematy-ki, Wydawnictwo Naukowe PWN, Warszawa.
Halmos P.R., Vaughan H.E., 1950, The marriage problem, American Journal of Mathematics, vol. 72, no. 1, s. 214-215.
Lovász L., Plummer M.D., 1986, Matching Theory, North-Holland, Amsterdam.
Roth A.E., 1984, The evolution of the labor market for medical interns and residents: A case study in game theory, Journal of Political Economy, no. 92, s. 991-1016.
Roth A.E., 2002, The economist as engineer: Game theory, experimentation, and computation as tools for design economics, Econometrica, vol. 70, no. 4, s. 1341-1378.
Roth A.E., Sotomayor M.A., 1992 Two-sided matching. A study in game theoretic modeling and analysis, http://web.stanford.edu/~alroth/papers/92_HGT_Two-SidedMatching.pdf (10.12.2015).
Ruohonen K., 2013, Graph theory, Tampere University of Technology, http://math.tut.fi/~ruohonen/ GT_English.pdf (15.01.2016).
Shapley L.S., Gale D., 1962, College admissions and the stability of marriage, The American Math-ematical Monthly, vol. 69, s. 9-15.
Stankiewicz W., 2013, Kolejny sukces teorii gier: nobliści z ekonomii 2012, Ekonomia i Prawo, tom XII, nr 1/2013, s. 33-45.
Świtalski Z., 2008, O kojarzeniu małżeństw i rekrutacji kandydatów do szkół, Rocznik Polskiego Towarzystwa Matematycznego, Seria II: Wiadomości Matematyczne, XLIV, s. 35-46.
Wilson R.J. 2012, Wprowadzenie do teorii grafów, Wydawnictwo Naukowe PWN, Warszawa.
Wojciechowski J., Pieńkosz K., 2013, Grafy i sieci, Wydawnictwo Naukowe PWN, Warszawa.

Cited by

ISSN

1507-3866

Language

pol

URI / DOI

BazEkon - The Main Library of the Cracow University of Economics

Main menu