Algorytm odroczonej akceptacji
Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale’a-Shapleya) jest algorytmem, którego celem jest znalezienie rozwiązania dla problemu trwałego małżeństwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zależności od sposobu użycia algorytm pozwala on znaleźć optymalne rozwiązania dla jednej z dwóch grup uczestników.
W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla dowolnej, ale takiej samej liczby mężczyzn i kobiet jest zawsze możliwe znalezienie takiego rozwiązania dla problemu trwałego małżeństwa, aby sprawić, że wszystkie małżeństwa będą trwałe, stabilne[1][2].
Algorytm w sposób uproszczony został przedstawiony poniżej:
1. Każdy z mężczyzn prosi o rękę tę kobietę, którą preferuje względem innych.
2. Każda kobieta notuje otrzymane propozycje w swoim karnecie.
3. W momencie, gdy każdy mężczyzna złożył propozycje swoim faworytkom, wszystkie kobiety odmawiają wszystkim mężczyznom, od których dostały propozycję, poza jednym, którego preferują ponad innych (nie jest to jednak jeszcze równoznaczne z akceptacją przez kobietę tego preferowanego mężczyzny – chyba że jest to także zalotnik najwyżej w jej rankingu wszystkich potencjalnych kandydatów).
4. Niewybrani mężczyźni oświadczają się następnej kobiecie w ich rankingu.
5. Powrót do punktu numer 2 lub koniec algorytmu, jeżeli każda kobieta odnalazła swojego preferowanego, przyszłego męża[3].
Algorytm zawsze prowadzi do powstania stabilnych par. Aby to udowodnić załóżmy, że – przeciwnie do stwierdzenia zawartego w poprzednim zdaniu – jeden mężczyzna, preferuje inną kobietę względem swojej obecnej partnerki. W takim przypadku oświadczył się jej przed poproszeniem o rękę swojej obecnej narzeczonej. Jednakże gdyby ta kobieta również preferowałaby go względem swojego obecnego partnera, to nie przyjęłaby wcześniej oświadczyn swojego obecnego narzeczonego.
Wynikiem algorytmu odroczonej akceptacji są zawsze najlepsze możliwe stabilne pary z punktu widzenia mężczyzn. Oznacza to, że żaden mężczyzna nie zmieniłby swojej pary względem jakiegokolwiek innego stabilnego dopasowania. Odwrócenie ról mężczyzn i kobiet doprowadziłoby do powstania stabilnego dopasowania, które byłoby preferowane przez kobiety[3][4].
Algorytm zapewnia, że:
- Każdy weźmie ślub
Ostatecznie nie może zaistnieć taka sytuacja, że zarówno mężczyzna, jak i kobieta nie są zaręczeni, ponieważ w pewnym momencie ten mężczyzna musiał się oświadczyć tej kobiecie (ostatecznie mężczyzna musiał się oświadczyć każdej kobiecie, jeśli było to konieczne), więc ostatecznie musiała ona przyjąć jego oświadczyny.
- Małżeństwo będzie trwałe
Niech kobieta A i mężczyzna B będą zaręczeni, ale nie ze sobą nawzajem. Od zakończenia algorytmu nie jest możliwe, żeby A i B preferowali siebie nawzajem względem swoich obecnych partnerów. Jeśli B wolałby A względem swojej aktualnej partnerki, to musiałby oświadczyć się A przed poproszeniem o rękę swojej obecnej partnerki. Jeśli A przyjęła jego oświadczyny, a ostatecznie nie jest z nim zaręczona, to musiała z nim zerwać na rzecz kogoś, kogo woli, a tym samym preferuje swojego obecnego partnera od mężczyzny B. Jeśli A odrzuciła oświadczyny B, to znaczy, że już była zaręczona z kimś, kogo woli od B.
Algorytm ma zastosowanie w rekrutacji do szkół w Nowym Jorku oraz Bostonie, przy przydziale stażystów do szpitali w USA, a nawet do kojarzenia dawców organów z biorcami przeszczepów.
Przypisy
edytuj- ↑ D. Gale, L.S. Shapley, „College Admissions and the Stability of Marriage”. American Mathematical Monthly, 1962, s. 9–14 [zarchiwizowane z adresu 2020-01-22].
- ↑ Harry Mairson, „The Stable Marriage Problem”, The Brandeis Review 12 [online], 1992.
- ↑ a b Hal R.Varian, Mikroekonomia. Kurs średni – ujęcie nowoczesne, 2013.
- ↑ Kazuo Iwama, „A Survey of the Stable Marriage Problem and Its Variants”. International Conference on Informatics Education and Research for Knowledge-Circulating Society (ICKS 2008). IEEE [online], 2008, s. 131–136.
Bibliografia
edytuj- Hal R. Varian, Mikroekonomia. Kurs średni. Ujęcie nowoczesne.