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

 esimeses grupis leidub element A, mis eelistab endaga sobitatud elemendile elementi B teisest grupist, ja
 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.

Ajalugu

 

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.

2012. aastal anti Shapleyle ja Alvin Rothile Nobeli majandusauhind "stabiilse jaotuse teooria ja turu planeerimise ellurakendamise eest". Roth on stabiilse sobitamise probleemi ja Gale'i-Shapley algoritmi printsiipe käsitlenud keskkoolidesse kandideerimise, meditsiinitudengite residentuuri määramise jaelundidoonorite patsientidega sobitamise võtmes.

Teooria

Gale ja Shapley sõnastasid probleemi järgnevalt:

Valdkonnad
1952. aastal loodi USAs meditsiinitudengite 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 tudengite vastastikuseid eelistusi. 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.

Gale ja Shapley toovad oma artiklis "Vastuvõtud kolledžitesse ja abielu püsivus" näiteks kolledžitesse kandideerimise. 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.

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.

Vaata ka

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

Viited

Mänguteooria
Majandusteadus