wikipedia

Alvin E. Roth

wikipedia

Lloyd S. Shapley, 1980

Co prawda, niekiedy Komitet Noblowski mimowolnie sugerował, że ekonomia wciąż pozostaje niedojrzała, przyznając w tym samym roku nagrody badaczom głoszącym poglądy wzajemnie sprzeczne (vide Hayek i Myrdal w 1974 czy Kahneman i Smith w 2002). W tym roku, na szczęście, uniknięto tego bolesnego wrażenia. Przeciwnie, Roth bardzo silnie opiera swoje badania na wynikach starszego o blisko trzydzieści lat kolegi. Decyzję trudno także uznać za zaskakującą – oba nazwiska pojawiały się na noblowej „giełdzie” od lat, a że Shapley przekroczył dziewięćdziesiątkę, rosła obawa, iż Komitet nie zdąży go uhonorować. Rozstrzygnięcie należy też pochwalić z tego względu, że nagrodzone wyniki to jeden ze stosunkowo niewielu w ekonomii przykładów pozornie abstrakcyjnej, suchej, formalnej, a przy tym wcale niebanalnej teorii, która ma bardzo praktyczne zastosowania.

Czego dotyczą więc badania Shapley’a i Rotha (oczywiście, te nagrodzone, bo np. Shapley ma ogromne zasługi w innych obszarach teorii gier)? Ogólnie rzecz biorąc, tzw. matching markets, a więc sytuacji, w których dwie strony „rynku” mają silne preferencje co do tego, z kim konkretnie po drugiej stronie wejdą w interakcję. Cechy tej nie ma np. rynek cebuli – gdy idę na targ, jest mi zasadniczo wszystko jedno, od którego ze sprzedawców ją kupię. Jeśli natomiast zamierzam się ożenić, to, z kim połączy mnie „mechanizm rynkowy”, jest absolutnie kluczowe. Podobnie, jeżeli wybieram się na studia, mogę mieć swój porządek uczelni czy poszczególnych kierunków od najlepszych do najgorszych (i porządek ten może być inny dla każdego z kandydatów). Oczywiście, także uczelnie mają swoje listy pożądanych studentów.

W systemie obecnie stosowanym w Polsce może zdarzyć się, że pewną Martę przyjmą na uczelnię  ale ona wolałaby iść na uczelnię  lecz na  znalazła się dopiero na liście rezerwowej. Nie składa więc matury na  tylko czeka, skutkiem czego  ją skreśla. Tymczasem nie ma wcale gwarancji, że na  doczeka się przyjęcia, więc ostatecznie może skończyć np. na uczelni  Zatem  zamiast Marty przyjmuje z listy rezerwowej pewnego Jana, choć wolałaby przyjąć Martę, a i Marta wolałaby  względem  na którym kończy. Co gorsza, może być nawet tak, że  (stosując inne kryteria niż ) przyjęło tegoż Jana w pierwszym rzucie, ale on wolał np. uczelnię  i był tam na liście rezerwowej, zatem odrzucił ofertę  i czekał na  lecz tam się nie dostał i dlatego właśnie skończył na ! Czyli gdybyśmy zamienili Martę i Jana miejscami, to zarówno oboje zainteresowanych kandydatów, jak i obie uczelnie skorzystałyby!

Korzystając z aparatu formalnego stworzonego przez Shapley’a, powiemy, że rozwiązanie jest niestabilne, a (Marta, ) jest parą blokującą – obie strony przedkładałyby bycie połączonymi nad aktualną sytuację (tj. Marta chciałaby zastąpić  przez  a  byłaby gotowa wymienić na Martę Jana, a – być może – także inne przyjęte osoby). Oczywiście, (Jan, ) też jest parą blokującą. Na „rynku” małżeńskim przypadek pary blokującej – preferującej siebie nawzajem wobec aktualnych współmałżonków – potocznie możemy nazwać romansem. Intuicyjnie widać więc, że lepiej, by procedura dawała rozwiązanie stabilne, co podnosi satysfakcję uczestników i pozwala uniknąć kosztownych dostosowań ex post; badania faktycznie pokazują, że mechanizmy gwarantujące taką alokację są lepiej oceniane i dłużej pozostają w mocy.

Shapley (we współpracy z Davidem Gale’em) udowodnił, że rozwiązanie stabilne (a więc takie, gdzie nie ma ani jednej pary blokującej) musi istnieć i pokazał, jak go szukać. W szczególności zaproponował algorytm odroczonej akceptacji. Gdy skorzystamy z terminologii „rynku” małżeńskiego, jedna z jego wersji polega na tym, że w pierwszej rundzie każdy z panów oświadcza się pani, która jest najwyżej na jego liście akceptowalnych partnerek. Każda z pań „roboczo” przyjmuje oświadczyny tego z jej adoratorów, którego ceni najwyżej (o ile którykolwiek jest do przyjęcia). Każdy odrzucony pan wykreśla z listy preferencji panią, która go odtrąciła i w kolejnej rundzie mechanizm zostaje powtórzony z tak skróconymi listami. Pan, który wykreśli wszystkie akceptowalne partnerki, przestaje się oświadczać. Mechanizm kończy się, gdy w kolejnej rundzie nikt nie zostanie odtrącony, a  „roboczo” przyjęte w niej oświadczyny wyznaczają ostatecznie utworzone pary (przy czym niektórzy mogą pozostać samotni).

Ponieważ w każdej nie-ostatniej rundzie przynajmniej jedna pani zostaje skreślona z przynajmniej jednej listy, mechanizm faktycznie doprowadzi do pewnej alokacji w skończonej liczbie kroków. Co istotniejsze, będzie to alokacja stabilna. Przypuśćmy przeciwnie, że pewna para (Piotr, Anna) jest parą blokującą. Oznacza to, że Piotr oświadczył się kiedyś Annie (skoro jest ona wyżej na jego liście niż jego docelowa żona) i został odrzucony (skoro nie są razem). Zauważmy jednak, że mechanizm ten gwarantuje, iż sytuacja każdej z pań z rundy na rundę może się tylko poprawić, bo odrzuca oświadczyny, które przyjęła roboczo w poprzedniej rundzie, tylko jeśli w nowej oświadczył się ktoś atrakcyjniejszy (a nieodrzucone oświadczyny zostaną powtórzone). Stąd wniosek, że Anna daje pierwszeństwo swojemu docelowemu mężowi przed Janem, zatem (Piotr, Anna) parą blokującą nie jest. Zauważmy, że w opisanym wyżej polskim systemie przyjęć na studia było inaczej, tj. Marta słusznie żałowała, że odrzuciła była „oświadczyny”  bowiem ostatecznie zaczęła studia na mniej preferowanej uczelni.

Oczywiście, równie dobrze moglibyśmy rozważać analogiczny mechanizm, w którym oświadczałyby się panie. Na ogół doprowadzi on do innej konfiguracji par. Co ciekawe, Gale i Shapley udowodnili, że mechanizm odroczonej akceptacji jest najlepszy dla strony oświadczającej się i najgorszy dla drugiej strony. Oznacza to, że w sytuacji, gdy mężczyźni się oświadczają, każdy mężczyzna otrzyma najlepszą z żon, jaką mógłby otrzymać w dowolnym rozwiązaniu stabilnym, a każda kobieta – najgorszego z mężów. Nic dziwnego, że w tradycyjnym społeczeństwie, dającym więcej władzy mężczyznom, to właśnie oni się oświadczali!

Choć akurat zcentralizowane rynki doboru w pary małżeńskie mogą budzić nasz sprzeciw, łatwo stwierdzić, że zastosowanie mechanizmu odroczonej akceptacji przy rekrutacji na studia pozwoliłoby uniknąć opisanego wyżej paradoksu, zredukowało obciążenia administracyjne dla uczelni i znacznie przyspieszyło proces rekrutacji – otrzymawszy listy preferowanych uczelni od kandydatów i kryteria doboru (np. wagi poszczególnych przedmiotów maturalnych) od uczelni, dobrze napisany program komputerowy przeprowadziłby opisaną przez nas procedurę w ciągu kilku sekund.

Istotnie, spektakularnym osiągnięciem Rotha są liczne praktyczne zastosowania algorytmów łączenia dwóch stron rynku. Oczywiście, różnica między teorią a praktyką jest taka, że w teorii nie ma różnicy, a w praktyce jest. Przykładowo, implementując algorytmy odroczonej akceptacji do problemu doboru absolwentów szkół medycznych do szpitali w Stanach Zjednoczonych (National Resident Matching Program), Roth stanął przed problemem związanym m.in. z parami małżeńskimi, w których preferencje co do szpitali nie były niezależne – małżonkowie woleli na ogół pracować możliwie blisko siebie. W swych pracach teoretycznych Roth pokazał, że tego rodzaju modyfikacje rujnują wspomniane wyniki – w tym przypadku alokacja stabilna może wcale nie istnieć!

Noblista zaproponował jednak pewne (znacznie bardziej skomplikowane niż algorytm odroczonej akceptacji) mechanizmy, które, jak pokazał, korzystając z symulacji komputerowych opartych o historyczne dane, prawie zawsze dadzą stabilne rozwiązanie.

Innym, wdrożonym przez Rotha praktycznym zastosowaniem algorytmów rozważanych wcześniej przez Shapley’a, jest problem wymiany nerek do przeszczepu pochodzących od żyjących dawców. Przeszczep nerki jest zbawieniem dla osób cierpiących na ciężką niewydolność tych organów, a człowiek zdrowy może zasadniczo bez trwałej szkody dla zdrowia oddać jedną ze swoich nerek. Niemniej, jest to istotne poświęcenie, które większość osób jest gotowa podjąć tylko dla kogoś bliskiego. Niestety, nawet jeśli krewny czy przyjaciel chorego zgodzi się oddać mu swoją nerkę, często okazuje się, że jest ona nieodpowiednia ze względów medycznych, np. pacjentowi o grupie krwi 0 można przeszczepić tylko nerkę pochodzącą od osoby o tejże grupie. Z kolei rynek, na którym można by po prostu kupić stosowną nerkę, większość ludzi uważa za nieetyczny i prawodawstwo niemal wszystkich krajów świata wyklucza takie transakcje. Roth wziął jednak udział w tworzeniu systemów „łańcuchowej” wymiany. W uproszczeniu działają one tak, że np. ktoś gotowy do oddania nerki żonie z niewydolnością, której nie może jednak bezpośrednio pomóc z powodu niewłaściwej grupy krwi, oddaje nerkę na rzecz innej, nieznanej sobie osoby, w chwili gdy z kolei jego żonie pomaga ktoś inny, kto ma krewnego z niewydolnością nerki itd. To chyba rzadki przypadek, gdy badania nagrodzone Noblem, ale wcale nie z medycyny, bezpośrednio ratują ludzkie życie.

Popularna piosenka powiada, że money makes this world go’round. Przesada. Centralnym pojęciem ekonomii jest efektywność, a nie pieniądz. Rynki projektowane przez Rotha świetnie radzą sobie (prawie) bez niego.