Stabiilse sobitamise probleem

Stabiilse sobitamise probleem on matemaatikas, majandusteaduses ja informaatikas esinev probleem, kus tuleb kahe ühesuuruse grupi vahel moodustada paarid nii, et tekkinud sobitus oleks stabiilne ehk ei esineks olukorda, kus

1. esimeses grupis leidub element A, mis eelistab endaga sobitatud elemendile elementi B teisest grupist, ja
2. element B eelistab endaga sobitatud elemendile elementi A.

Stabiilse sobitamise probleemi sõnastasid 1962. aastal USA matemaatikud ja majandusteadlased David Gale ja Lloyd Shapley, kes esitasid probleemile ka lahenduse: Gale'i-Shapley algoritmi.^[1]

Ajalugu

David Gale

Lloyd Shapley

1962. aastal avaldasid USA matemaatikud ja majandusteadlased David Gale ja Lloyd Shapley ajakirjas American Mathematics Monthly artikli "Vastuvõtud kolledžitesse ja abielu püsivus". Nad sõnastasid stabiilse sobitamise probleemi ning pakkusid sellele välja lahenduse Gale'i-Shapley algoritmi näol. Lisaks tõid nad välja, et isegi stabiilne sobitus võib soosida üht osapoolt.^[1]

2012. aastal anti Shapleyle ja Alvin Rothile Nobeli majandusauhind "stabiilse jaotuse teooria ja turu planeerimise ellurakendamise eest".^[2] Roth on stabiilse sobitamise probleemi ja Gale'i-Shapley algoritmi printsiipe käsitlenud keskkoolidesse kandideerimise^[3], meditsiiniüliõpilaste residentuuri määramise^[4][5] jaelundidoonorite patsientidega sobitamise^[6] võtmes.

Teooria

Gale ja Shapley sõnastasid probleemi järgnevalt^[1]:

„

Kogukonnas elavad ${\displaystyle n}$ meest ja ${\displaystyle n}$ naist. Igaüks järjestab vastassoo esindajad vastavalt oma eelistustele abikaasa leidmisel. Me otsime rahuldavat viisi kõigi kogukonna liikmete paari panemiseks. [...] Nimetame sedasi tekkinud abielude hulga ebastabiilseks [...], kui leiduvad üks mees ja üks naine, kes pole abielus, aga eelistavad teineteist oma tegelikele kaasadele. KÜSIMUS. Kas mistahes eelistuste komplekti jaoks on võimalik leida stabiilset abielude hulka?

“

Valdkonnad

1952. aastal loodi USAs meditsiiniüliõpilaste residentuuri määramiseks programm NRMP (National Resident Matching Program). Selle tarbeks lõid John Stalknaker ja F. J. Mullen IBM-i seadmetele kirjutatud algoritmi, mis võttis arvesse nii haiglate kui ka üliõpilaste vastastikuseid eelistusi.^[7] 1984. aastal näitas Roth, et süsteemi teoreetilised alused olid samad, mis Gale'i ja Shapley kaheksa aastat hiljem avaldatud artiklis, ning 1999. aastal täiendas süsteemi, tagamaks stabiilseid sobitusi ka juhul, kui arvesse võtta abielupaaride soovi töötada lähestikku.^[5][8]

Gale ja Shapley toovad oma artiklis "Vastuvõtud kolledžitesse ja abielu püsivus" näiteks kolledžitesse kandideerimise.^[1] 2003. aastal võttis NYCDOE (New York City Department of Education) õpilaste New Yorgi keskkoolides jaotamiseks kasutusele uue, Gale'i-Shapley algoritmist lähtuva ning õpilasi soosiva süsteemi.^[3]

Stabiilse sobitamise probleemina käsitletakse ka kasutajate sobitamist veebiserveritega. Kasutaja eelistusjärjekord kujuneb serveri läheduse põhjal ja serveri eelistusjärjekord kujuneb kasutaja ressursinõudlikkuse (jõudlus, mälu, signaali ribalaius) põhjal.^[9]

Vaata ka

• David Gale
• Lloyd Shapley
• Gale'i-Shapley algoritm
• Alvin Roth
• Stabiilsete toakaaslaste probleem
• Kolledžisse vastuvõtu probleem
• Nashi tasakaal

Viited

1. Gale, D.; Shapley, L. S. (1962). "College Admissions and the Stability of Marriage". American Mathematical Monthly. 69: 9–14. DOI:10.2307/2312726. JSTOR 2312726.
2. "The Prize in Economic Sciences 2012". nobelprize.org (inglise). Vaadatud 17. aprill 2017.
3. Abdulkadiroglu, A.; Pathak, P. A.; Roth, A. E. "The New York City High School Match" (PDF) (inglise). Originaali (PDF) arhiivikoopia seisuga 10. detsember 2015. Vaadatud 17. aprill 2017.
4. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design" (PDF) (inglise). Vaadatud 17. aprill 2017. {{netiviide}}: eiran teksti "Autor: Roth, A. E., Peranson, E." (juhend)
5. 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. 92: 991–1016.
6. Roth, Alvin E.; Tayfun Sonmez; Utku Unver (2005). "Pairwise kidney exchange". Journal of Economic Theory. 125 (2): 151–188.
7. Gusfield, D.; Irving, R. W. (1989). The Stable Marriage Problem: Structure and Algorithms. The MIT Press. ISBN 0-262-07118-5.
8. Roth, Alvin E. Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions, International Journal of Game Theory, Special Issue in Honor of David Gale on his 85th birthday, 36, märts 2008, 537–569.
9. Maggs, Bruce M.; Sitaraman, Ramesh K. (juuli 2015). "Algorithmic nuggets in content delivery". SIGCOMM Computer Communication Review. New York, NY, USA: ACM. 45 (3): 52–66. DOI:10.1145/2805789.2805800.