Redakcja: Na czym polegała teoria „stabilnych alokacji” Lloyda S. Shapleya?

Dr Marcin Malawski: To się nazywa po angielsku stable allocations, ale może powinno się raczej mówić nie o stabilnych alokacjach, tylko o pewnym rodzaju alokacji, a mianowicie o skojarzeniach. Alokacja polega na tym, że jeśli chcę nabyć np. akcje KGHM-u, to kupuję ich 100 i jest mi wtedy wszystko jedno, które to akcje i od kogo je kupiłem. Skojarzenie polega natomiast na tym, że element po jednej stronie rynku zostaje skojarzony z pewnym elementem po drugiej jego stronie i to stanowi pewien bardzo szczególny rodzaj alokacji, który kieruje się innymi prawami niż taka alokacja w sensie dóbr konsumpcyjnych.

Teoria wywodzi się od pracy, którą napisał Lloyd Shapley wspólnie z Davidem Gale’em na początku lat 60. Jej tytuł w tłumaczeniu na polski brzmiał „Przyjęcia do szkół i stabilne małżeństwa”. Warto w tym miejscu wyjaśnić, na czym polegał model opracowany przez Gale’a i Shapleya. Celem jest, aby osoby spośród pewnej grupy mężczyzn i równolicznej grupy kobiet połączyć w pary, które będziemy nazywali małżeństwami. Tu powstaje pytanie, jak dokonać dobrych skojarzeń i co w ogóle w tym przypadku znaczy dobre? Otóż, minimalnym wymaganiem jest stabilność, a pewien układ małżeństw jest stabilny, kiedy nie istnieje para, która by ten układ zerwała. Innymi słowy, nie ma pary niebędącej małżeństwem, w której mężczyzna woli inną kobietę od swojej aktualnej żony, a kobieta woli tego mężczyznę od swojego aktualnego męża. To jest minimalne, ale całkiem rozsądne wymaganie. Kolejne pytanie, jakie tutaj się pojawia to, czy stabilne układy skojarzeń w ogóle istnieją? Otóż Gale i Shapley dali na to odpowiedź twierdzącą i co więcej, udowodnili to efektywnie, pokazując algorytm, który do takiego układu prowadzi. Głównym ich osiągnięciem w tej pracy, a przynajmniej takim, które uzyskało największy oddźwięk jest właśnie stworzenie tego algorytmu.

Sam algorytm jest prosty. W modelu mamy tę samą liczbę mężczyzn i kobiet, każdy mężczyzna posiada swoją preferencję na zbiorze dostępnych kobiet, a każda kobieta na zbiorze dostępnych mężczyzn. I teraz algorytm przebiega następująco, każdy mężczyzna oświadcza się tej kobiecie, która jest na szczycie jego preferencji, każda zaś kobieta, której ktokolwiek się oświadczył zachowuje na liście oczekujących najlepszego spośród nich, a odrzuca wszystkich pozostałych. W następnym kroku wszyscy mężczyźni, którzy zostali odrzuceni, oświadczają się drugiej z kolei pod względem swojej preferencji kobiecie. No i znowu, każda kobieta, która dostała jakiekolwiek propozycje, ustawia sobie na liście oczekujących najlepszego z mężczyzn, jacy się jej oświadczyli. Proszę zauważyć, że ten najlepszy mógł się w międzyczasie zmienić, ponieważ ona mogła odrzucić tego, kto się do niej zgłosił jako pierwszy, bo w następnym kroku mógł się zgłosić ktoś, kogo uznała za lepszego. Ten algorytm skończy się w momencie, kiedy żaden mężczyzna nie będzie chciał zgłosić nowej propozycji małżeństwa żadnej kobiecie, to znaczy, kiedy wszyscy będą już sparowani.

Powstał więc pewien układ par, który nazywamy stabilnym układem skojarzeń. Ten algorytm okazuje się zaskakująco dobry i uniwersalny w stosowaniu. Badacze na koniec swojej pracy wygłosili nadzieję, że ten teoretyczny wynik, przy całej swej prostocie, może okazać się w przyszłości stosowalny do rzeczywistych zagadnień. I teraz proszę zwrócić uwagę na drugą część tytułu pracy, mianowicie na college admissions – przyjęcia do szkół. Tam sytuacja jest trochę podobna. Naukowcy uważali, że algorytm mógłby równie dobrze pracować w ten sposób, że to potencjalni uczniowie zgłaszają się do szkół, a szkoła jest w stanie przyjąć ich pewną ilość. Tu pojawia się różnica, bo każda kobieta może wyjść tylko za jednego mężczyznę, a szkoła jest w stanie przyjąć uczniów wielu. Algorytm działa jednak dokładnie w ten sam sposób, jedynie z poprawkami na to, że szkoła ma pewną określoną liczbę uczniów, którą jest w stanie przyjąć. Analogicznie uzyskuje się tu skojarzenia stabilne w tym sensie, że nie ma żadnego ucznia, który wolałby się przenieść do innej szkoły, a jednocześnie ta inna szkoła wolałaby przyjąć jego niż któregoś ze swoich przyjętych uczniów.

Jednym z pytań, które powstają w związku z algorytmem Gale’a-Shapeleya jest to, które zadałyby od razu feministki i które ma w sumie sens, a mianowicie, dlaczego to faceci mają składać propozycje, a nie kobiety? Przecież równie dobrze ten algorytm powinien działać w sytuacji, kiedy propozycje składają panny. Oczywiście jest to prawda, ponieważ algorytm działa również w takiej wersji, choć wówczas jego wynik może być inny. W tym przypadku znowu dostaniemy zbiór stabilnych skojarzeń, ale ponadto da się udowodnić pewne interesujące twierdzenie. Jeżeli propozycje składają mężczyźni, to układ, który w efekcie powstaje jest z punktu widzenia mężczyzn najlepszy. Gdyby z kolei propozycje składały kobiety i założylibyśmy, że istnieje więcej niż jeden układ stabilnych skojarzeń, to układ wygenerowany w ten sposób okazałby się najkorzystniejszy dla kobiet spośród wszystkich, jakie są możliwe.

Oglądaj całość