Algorytm odroczonej akceptacji

Algorytm odroczonej akceptacji

Algorytm odroczonej akceptacji, znany również jako algorytm Gale’a-Shapleya, ma na celu rozwiązanie problemu trwałego małżeństwa. Jego działanie prowadzi do tworzenia stabilnych par. W zależności od kontekstu, algorytm ten może dostarczyć optymalne rozwiązania dla jednej z dwóch grup uczestników.

W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla każdej grupy mężczyzn i kobiet o tej samej liczbie, zawsze istnieje możliwość znalezienia rozwiązania problemu trwałego małżeństwa, które zapewni, że wszystkie małżeństwa będą trwałe i stabilne.

Algorytm w uproszczonej formie prezentuje się następująco:

• Każdy mężczyzna składa propozycję ręki kobiecie, którą preferuje najbardziej.
• Każda kobieta zapisuje wszystkie propozycje, które otrzymała.
• Gdy wszyscy mężczyźni złożą swoje propozycje, kobiety odrzucają wszystkich mężczyzn oprócz jednego, którego preferują ponad innych (nie oznacza to jednak, że akceptują tego mężczyznę, chyba że jest on na szczycie ich rankingu potencjalnych kandydatów).
• Niewybrani mężczyźni proponują się następnej kobiecie według swojego rankingu.
• Powracamy do punktu drugiego lub kończymy algorytm, jeśli każda kobieta znalazła swojego preferowanego, przyszłego męża.

Algorytm zawsze prowadzi do powstania stabilnych par. Aby to udowodnić, załóżmy, że jeden mężczyzna woli inną kobietę niż swoją aktualną partnerkę. W takim przypadku musiałby oświadczyć się jej przed złożeniem propozycji swojej obecnej narzeczonej. Jednak gdyby ta kobieta również preferowała go względem swojego obecnego partnera, to nie przyjęłaby wcześniej oświadczyn swojego aktualnego narzeczonego.

Wynikiem algorytmu odroczonej akceptacji są zawsze najlepsze możliwe stabilne pary z perspektywy mężczyzn. Oznacza to, że żaden mężczyzna nie zmieniłby swojej pary na rzecz jakiegokolwiek innego stabilnego dopasowania. Gdyby role mężczyzn i kobiet zostały odwrócone, powstałoby stabilne dopasowanie preferowane przez kobiety.

Algorytm gwarantuje, że:

• Każdy weźmie ślub.
• Nie może zaistnieć sytuacja, w której zarówno mężczyzna, jak i kobieta nie są zaręczeni, ponieważ w pewnym momencie mężczyzna musiał się oświadczyć tej kobiecie (konieczne było, aby mężczyzna złożył propozycję każdej kobiecie, jeśli to było wymagane), więc ostatecznie musiała ona przyjąć jego oświadczyny.
• Małżeństwo będzie trwałe.

Weźmy na przykład kobietę A i mężczyznę B, którzy są zaręczeni, ale nie ze sobą nawzajem. Po zakończeniu algorytmu nie jest możliwe, aby A i B preferowali siebie nawzajem w stosunku do swoich obecnych partnerów. Jeśli B wolałby A względem swojej aktualnej partnerki, musiałby oświadczyć się A przed złożeniem propozycji swojej obecnej partnerce. Jeśli A przyjęła jego oświadczyny, a ostatecznie nie jest z nim zaręczona, musiała z nim zerwać na rzecz kogoś, kogo bardziej woli, co oznacza, że preferuje swojego obecnego partnera nad B. Jeśli A odrzuciła oświadczyny B, to oznacza, że już była zaręczona z kimś, kogo woli od B.

Algorytm znajduje zastosowanie w rekrutacji do szkół w Nowym Jorku oraz Bostonie, przy przydziale stażystów do szpitali w USA, a także w kojarzeniu dawców organów z biorcami przeszczepów.

Przypisy

Bibliografia

Hal R. Varian, Mikroekonomia. Kurs średni. Ujęcie nowoczesne.