Sobota 20. január. Meniny má Vincent

Nobelova cena: Teória stabilnej alokácie na príklade partnerských vzťahov, voľby lekárov a transplantácie obličiek

Ako sme už informovali, k nositeľom ceny Švédskej ríšskej banky za ekonomické vedy na pamiatku Alfreda Nobela sa tento rok zaradili Alvin Roth a Lloyd Shapley so svojou teóriu stabilných alokácií. Ich práca siaha od abstraktných teórií, cez empirické výskumy až k neustálemu úsiliu o nájdenie praktických riešení reálnych problémov. Príkladmi použitia ich teórie priradenie nových lekárov do nemocníc, študentov do škôl či ľudských orgánov na transplantáciu ich príjemcom.

Lloyd Shapley vyvinul v 60. rokoch počiatočné teoretické príspevky, ktoré si o dve desaťročia neskôr nečakane osvojil Alvin Roth, keď robil prieskum na trhu lekárov v USA. Jeho zistenia vygenerovali ďalší analytický vývoj, rovnako ako aj praktický dizajn trhových inštitúcií.

V čom bola analýza týchto dvoch ekonómov odlišná? Tradičné ekonomické analýzy študujú trhy, kde sa cena prispôsobuje tak, aby sa ponuka rovnala dopytu. Trhy fungujú v mnohých prípadoch dobre, v niektorých situáciách však štandardný trhový mechanizmus naráža na problémy. Existujú aj prípady, kedy sa cena na alokáciu zdrojov nemôže použiť vôbec. Napríklad mnohé školy a univerzity nesmú vyberať školné alebo v prípade priraďovania ľudských orgánov na transplantácie sú peňažné platby vylúčené z etických dôvodov. Napriek tomu aj v týchto prípadoch pridelenie musí byť vykonané. Ako tieto procesy vlastne fungujú a kedy je výsledok efektívny?

Teória párovania: Algoritmus Galea-Shapleyho

Analýza mechanizmov alokácie sa opiera o trochu abstraktnú myšlienku. Ak sa rozumní ľudia (t.j. tí, ktorí poznajú svoje najlepšie záujmy a správajú sa podľa toho) zapoja do neobmedzeného vzájomného obchodu, potom by mal byť výsledok efektívny. Ak by tomu tak nebolo, niektorí jedinci by sa zapojili do nových obchodov, ktoré by pre nich boli výhodnejšie. Potom môžeme predpokladať, že také alokácie, kde žiadni jedinci nezískajú už dodatočné zisky z ďalšieho obchodu, sa nazývajú stabilné. Pojem stability je ústredným konceptom v rámci spolupracujúcej teórie hier, abstraktnej oblasti matematickej ekonómie, ktorá sa snaží zistiť, ako by ktorékoľvek zoskupenie racionálnych jedincov mohlo spolupracovať a vybrať alokáciu.

Neobmedzené obchodovanie je taktiež kľúčovým predpokladom, ktorý tvorí základ konceptu stability. Hlavným architektom tohto smeru v rámci teórie hier bol Lloyd Shapley, ktorý vyvinul jeho základný koncept už v rokoch 1950 až 1960. V roku 1962 aplikoval Shapley myšlienku stability na osobitný prípad. V krátkom článku v spolupráci s Davidom Galeom skúmal prípad párových priraďovaní: ako môžu byť jednotlivci spárovaní, keď všetci majú rozdielne názory na to, s kým budú tvoriť najlepší pár?

Praktický príklad: Muži si vyberajú ženy  

Gale a Shapley analyzovali párovanie na všeobecnej úrovni a používali manželstvo ako jeden zo svojich ilustratívnych príkladov. Ako by teda desať žien a desať mužov malo byť spárovaných pri rešpektovaní ich individuálnych preferencií? Hlavná výzva zahŕňala návrh jednoduchého mechanizmu, ktorý by viedol k stabilnému spojeniu ľudí do párov, v ktorých by sa žiadne z dvojíc nerozchádzali a nevytvárali nové páry, aby im bolo lepšie. Riešením bol Galeov-Shapleyov algoritmus „odloženého prijatia“, teda súbor jednoduchých pravidiel, ktoré vždy viedli rovno k stabilnému párovaniu.

Tento algoritmus možno nasadiť dvomi alternatívnymi spôsobmi: buď sú muži navrhnutí ženám alebo ženy navrhnuté mužom. Popíšeme si druhý prípad. Proces sa začína tým, že každá žena dá mužovi návrh, ktorý sa jej páči najviac. Muži si následne prejdú návrhy, ktoré dostali (ak nejaké dostali) a ponechávajú si ten, ktorý považujú za najatraktívnejší (ale odložia jeho prijatie) a odmietajú ostatné. Ženy, ktoré boli v prvom kole zamietnuté, dajú potom návrh ich druhej najlepšej voľbe, zatiaľ čo muži si zasa ponechávajú svoju najlepšiu ponuku a zvyšok odmietajú. Tento postup sa opakuje, až kým žiadna žena už nechce urobiť ďalší návrh. Keď každý z mužov potom prijme návrh, ktorý si ponechal, proces sa chýli ku koncu.

Gale a Shapley aj matematicky dokázali, že tento algoritmus vždy vedie k stabilnému párovaniu. Nastavenie algoritmu však ukázalo, že má významné distribučné dôsledky: je veľký rozdiel, či právo návrhu je dané ženám – ako v našom príklade – alebo mužom. Ak majú toto právo ženy, výsledok je pre ne vždy lepší, než keby to robili muži; pretože niektoré ženy skončia s mužmi, ktorí sa im páčia viac a žiadna žena nie je na tom horšie, než keby muži dostali právo návrhu. Naopak reverzný algoritmus – kde muži navrhujú – vedie z pohľadu žien k najhorším výsledkom. Jasnosť a elegancia Gale-Shapleyovho algoritmu ho dostali do zoznamu na akademické čítanie pre študentov ekonómie po celom svete, ale jeho relevantnosť v reálnom svete bola uznaná až oveľa neskôr. Na začiatku 80. rokov bol Alvin Roth vyslaný študovať veľmi praktický problém alokácie: trh lekárov – absolventov.

Dôkazy: Trhy nových lekárov

V USA sú absolventi medicíny typicky zamestnávaní ako stážisti v nemocniciach, kde tvoria významnú časť pracovnej sily. Od roku 1900 bol tento trh do značnej miery decentralizovaný. Počas roka 1940 však súťaž o vzácnych študentov medicíny donútila nemocnice ponúkať stáže študentom čoraz skôr, niekedy aj niekoľko rokov pred ukončením štúdia.

Priraďovania do nemocníc boli robené predtým, než mohli študenti predložiť doklady o svojej kvalifikácii a dokonca aj pred tým, než vôbec vedeli, akému odboru medicíny sa chcú venovať. Keď bola ponuka nemocnice odmietnutá, bolo často už príliš neskoro na ponuky pre iných kandidátov.

Trh riadený s takýmito problémami neprodukoval stabilné priradenia, pretože nebolo možné vykonať dostatok ponúk včas tak, aby boli zaistené vzájomne prospešné obchody. Aby sa stihlo urobiť viac ponúk, uložili nemocnice prísne lehoty odpovedí na ponuky. Toto potom nútilo študentov urobiť rýchle rozhodnutia bez toho, aby vedeli, aké iné možnosti by mali k dispozícii neskôr.

V nadväznosti na tieto problémy bol začiatkom 50. rokov predstavený tzv. „National Resident Matching Program (MRMP)“, teda národný rezidenčný priraďovací program. V dokumente z roku 1984 Alvin Roth študoval algoritmus použitý v tomto programe a zistil, že bol veľmi úzko spätý s algoritmom Galea-Shapleya. Roth predpokladal, že hlavným dôvodom úspechu NRMP bolo to, že produkoval stabilné priradenia.

Praktický dizajn: Párovanie lekárov a nemocníc

Napriek svojim úspechom program NRMP stále zápasil s problémami. Počet žien – študentiek medicíny rástol a stalo sa bežné, že lekárske páry hľadali stáže v rovnakom regióne. Mechanizmus NRMP nemohol uspokojiť tieto požiadavky, preto sa mnohí uchádzači rozhodli nepoužiť ho – bolo to znamenie, že nie je stabilný. Tento program, v ktorom nemocnice ponúkali pozície pre študentov, bol tiež kritizovaný za systematické uprednostňovanie nemocníc pred študentmi. Vidíme tu príklad toho, čo Gale a Shapley ukázali teoreticky, t.j. že ponúkajúca strana trhu (v tomto prípade nemocnice) je systematicky uprednostňovaná.

V roku 1995 bol Roth požiadaný o pomoc pri navrhnutí lepšieho algoritmu, ktorý by odstránil tieto problémy. Spolu s Elliottom Peransonom vytvorili algoritmus, postavený na návrhoch uchádzačov a navrhnutý tak, aby uspokojil aj páry. Nový algoritmus, ktorý si NRMP osvojil v roku 1997, fungoval dobre a odvtedy bolo pomocou neho spárovaných viac ako 20 000 pozícií s uchádzačmi za rok.

Ilustračný príklad procesu párovania lekárov a nemocníc

nobel-prize

zdroj: www.nobelprize.org.

Matching doctors and hospitals. When the doctors make offers, they all first choose hospital which accepts doctors 1 (the hospital´s first choice). In a second stage, doctors 2 makes an offer to hospital b. and doctor 3 to hospital c. which gives a stable matching. When the hospitals have the right to make offers, the result is instead that doctor 2 is matched with hospital c and 3 with b.

Alokácia lekárov a nemocníc. Keď lekári predkladajú ponuky, všetci si najprv vyberú nemocnicu, ktorá prijíma lekára 1 (v nemocnici je prvá voľba). V ďalšej fáze sa lekár 2 ponúkne do nemocnice B a lekár 3 do nemocnice C, čo dáva stabilnú zhodu. Keď by dávali ponuky nemocnice, výsledkom by bolo, že lekár 2 sa dohodne s nemocnicou C a lekár 3 s nemocnicou B.

Párovanie študentov a škôl

Algoritmus Galea-Shapleyho sa osvedčil aj pri výbere stredných škôl. Až do roku 2003 boli uchádzači o verejné stredné školy žiadaní, aby urobili zoznamy s poradím svojich piatich najviac preferovaných škôl, ktoré boli následne odosielané do škôl. Školy potom rozhodli, ktorých študentov príjmu, ktorých odmietnu alebo umiestnia na čakacej listine. Proces sa opakoval v ďalších dvoch kolách a študenti, ktorí neboli priradení do žiadnej školy po treťom kole boli pridelení prostredníctvom administratívneho procesu.

Avšak toto neposkytlo uchádzačom dostatok príležitostí na vyjadrenie svojich preferencií a školy taktiež nemali dostatok príležitostí, aby predložili ponuky. Výsledkom bolo, že asi 30 000 študentov ročne končilo na školách, ktoré nemali vo svojich preferenčných zoznamoch uvedené. Navyše proces dával priestor k skresľovaniu preferencií. V roku 2003 Roth a jeho kolegovia pomohli pretvoriť tento prijímací proces, ktorý postavili na návrhoch uchádzačov (druhej verzii Gale-Shapleyovho algoritmu). Nový algoritmus sa ukázal byť úspešný. Počet študentov, zaradených do škôl, ktorým nevyjadrili žiadnu preferenciu sa znížil o 90 percent. Dnes rastúci počet amerických metropolitných oblastí používa v tejto oblasti niektorý variant Galeovho-Shapleyovho algoritmu.

Párovanie obličiek a pacientov

Priraďovanie, ktoré sme popísali doteraz, zahŕňalo vždy dve strany, z ktorých obe sa aktívne rozhodovali. Niektoré situácie z reálneho sveta sú však jednostranné v tom zmysle, že druhá strana je úplne pasívna.

Praktickým príkladom je priraďovanie obličiek či iných ľudských orgánov pacientom, ktorí potrebujú transplantáciu. Ako sa to dá uskutočniť efektívne? Tento problém študovali Shapley a jeho kolegovia, opäť v abstraktnom ponímaní, založenom na stabilite. Navrhnutý algoritmus – tzv. top cyklus obchodovania – je v skutočnosti veľmi jednoduchý. Je založený na počiatočnej alokácii objektov a následnom vymieňaní.

Výzvou v prípade ľudských orgánov je to, že niektoré priradené obličky nemusia byť s pacientom kompatibilné a že komplexné mnohostranné výmeny môžu byť dosť časovo náročné. Tu bola opäť využitá kombinácia teórie a experimentálnej práce na porovnanie rôznych verzií top obchodovania. V mnohých štátoch USA sú v dôsledku toho teraz používané stále zložitejšie reťazce obličkových darov.

Rozširovanie na nové trhy

Dominantnou črtou vyššie uvedených príkladov je, že ceny nie sú súčasťou procesu. Obmedzuje absencia cenového mechanizmu v základnom algoritme Galea-Shapleya jeho použiteľnosť? Nie nevyhnutne.

Shapley skúmal rozšírenie pôvodného modelu, ktoré umožňujú cenám (na trhu lekárov platy), stať sa súčasťou ponúk. Algoritmy zahrňujúce cenu práce fungujú v podstate rovnakým spôsobom a produkujú stabilné priradenia s veľmi podobnými vlastnosťami. Párovanie s cenami je v skutočnosti úzko späté s aukciami, kde sú objekty párované s kupujúcimi a kde ceny sú rozhodujúce.

Na záver môžeme povedať, že tohtoročná cena odmeňuje prosperujúcu oblasť výskumu, kde sa teórie, dôkazy a dizajn interaktívne používajú. Lloyd Shapley a Alvin Roth pracovali síce nezávisle od seba, ale úspech ich výskumu priniesla práve kombinácia teoretických výsledkov Shapleya s pohľadmi Rotha na ich praktickú hodnotu. Táto oblasť výskumu naďalej rastie a má veľký prísľub aj do budúcnosti.

Spracované podľa www.nobelmuseum.se, www.nobelprize.org, ilustračné foto: sxc.hu. 

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *