Algorytm Gale’a-Shapleya
- Autor metody
- David Gale, Lloyd Shapley
- Rok
- 1962
- Typ
- algorithm
- Rodzina
- Game-theoretic
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Algorytm Gale’a-Shapleya rozwiązuje problem stabilnego małżeństwa: jak dopasować dwie grupy (np. rezydentów medycznych do szpitali, studentów do szkół) w taki sposób, aby żadna para nie preferowała siebie nawzajem bardziej niż swoich przydzielonych partnerów.
Wprowadzony przez Davida Gale’a i Lloyda Shapleya w 1962 roku algorytm gwarantuje stabilne dopasowanie w czasie wielomianowym poprzez proces odroczonej akceptacji, w którym jedna strona sekwencyjnie proponuje, a druga strona odpowiada, korygując wybory w miarę pojawiania się lepszych opcji.
Intuicja stojąca za metodą
Wyobraźmy sobie dopasowywanie lekarzy do szpitali. Algorytm działa jak gra w "gorące krzesła": każdy lekarz proponuje szpitalowi, który preferuje najbardziej; każdy szpital wstępnie akceptuje najlepszego dostępnego lekarza. W miarę otrzymywania lepszych propozycji szpitale korygują swoje wybory, potencjalnie odrzucając wcześniejsze akceptacje. Lekarze, którzy zostali odrzuceni, proponują kolejnemu preferowanemu szpitalowi. Proces trwa, dopóki żaden lekarz nie chce dalej proponować i żaden szpital nie chce wymieniać swojego obecnego dopasowania. Wynik jest stabilny: żadna para lekarz-szpital nie wolałaby być dopasowana do siebie nawzajem niż do swoich przydzielonych partnerów.
Historia
David Gale i Lloyd Shapley opublikowali swoje rozwiązanie problemu stabilnego małżeństwa w 1962 roku, dowodząc, że stabilne dopasowania zawsze istnieją dla rynków dwustronnych. Ich algorytm zapoczątkował obszerną literaturę na temat teorii dopasowań z zastosowaniami obejmującymi medycynę, edukację i rynki pracy. W 2012 roku Alvin Roth otrzymał Nagrodę Nobla w dziedzinie ekonomii za swoje prace eksperymentalne i teoretyczne, stosujące teorię dopasowań do projektowania rzeczywistych rynków, co potwierdziło praktyczne znaczenie ram Gale’a-Shapleya.
Kiedy stosować
Zastosuj algorytm Gale’a-Shapleya do dopasowywania rynków dwustronnych, gdzie stabilność jest kluczowa: przydział rezydentów medycznych, przydział studentów do szkół, wymiana nerek, dopasowywanie na rynku pracy lub rynki randek online. Użyj, gdy istnieje ryzyko niestabilności dopasowania (par blokujących), która mogłaby zniweczyć dopasowanie po przydziale. Algorytm jest idealny, gdy jedna strona może działać jako pierwsza, uzyskując strategiczną przewagę.
Ograniczenia i uwagi
- Brak optymalności Pareto: dopasowanie może nie maksymalizować całkowitego dobrobytu; mogą istnieć zablokowane pary, które mogłyby odnieść korzyści z wymiany partnerów
- Podatność strategiczna: strona proponująca może zyskać, fałszywie przedstawiając preferencje, podczas gdy strona odpowiadająca jest prawdomówna
- Asymetria: wyniki w dużym stopniu zależą od tego, która strona proponuje jako pierwsza
- Nie obsługuje ograniczeń: trudno jest uwzględnić złożone preferencje (np. pary, preferencje regionalne) bez modyfikacji algorytmicznej
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Gwarantowana stabilność: w końcowym dopasowaniu nie istnieją pary blokujące
- Czas wielomianowy: złożoność O(n^2), co czyni go wydajnym dla dużych populacji
- Prosta implementacja: łatwy do wykonania w praktyce dzięki przejrzystemu zbieraniu preferencji
- Strategiczne zachęty: strona proponująca ma strategiczną przewagę, preferując wczesne propozycje od późniejszych
- Uniwersalnie stosowalny: działa dla dowolnych profili preferencji bez zakładania wypukłości czy przechodniości
Zastosowania
- Dopasowanie rezydentury medycznej: łączenie absolwentów szkół medycznych z programami rezydentur szpitalnych za pośrednictwem NRMP
- Wybór szkoły: przydzielanie uczniów do szkół publicznych na podstawie preferencji i ograniczeń pojemności
- Wymiana nerek: dopasowywanie dawców i biorców organów w celu maksymalizacji zgodnych przeszczepów
- Dopasowanie na rynku pracy: łączenie osób poszukujących pracy z pracodawcami na dwustronnych rynkach pracy
- Randki online: dopasowywanie użytkowników na platformach randkowych w celu poprawy stabilności dopasowań i satysfakcji użytkowników
Jak to działa
Jak to działa
Utwórz listy preferencji dla wszystkich osób w obu grupach, reprezentujące ich ranking drugiej strony.
W każdej rundzie każda niedopasowana osoba ze strony proponującej proponuje osobie o najwyższym rankingu po drugiej stronie, której jeszcze nie proponowała.
Każda osoba po stronie otrzymującej wstępnie akceptuje propozycję, jeśli jest niedopasowana, lub jeśli proponujący ma wyższy ranking niż jej obecny partner, w którym to przypadku odwołuje poprzednie zaręczyny.
Algorytm zatrzymuje się, gdy każda osoba jest dopasowana i nie ma dalszych propozycji, co daje stabilne dopasowanie.
Częste pułapki
- Zakładanie, że sama stabilność jest wystarczająca dla sprawiedliwości lub dobrobytu; stabilne dopasowania mogą być silnie skrzywione na korzyść jednej strony
- Mylenie stabilności z optymalnością; stabilne dopasowanie niekoniecznie maksymalizuje dobrobyt
- Przeoczenie strategicznej przewagi strony proponującej: członkowie strony proponującej mają tendencję do dopasowywania się do wyżej ocenianych partnerów
- Zapominanie, że algorytm zakłada kompletne listy preferencji; niekompletne preferencje wymagają modyfikacji
Najczęściej zadawane pytania
Dlaczego stabilność jest ważna w dopasowywaniu?
Bez stabilności dopasowane pary mogłyby później odkryć, że preferują siebie nawzajem bardziej niż swoich przydzielonych partnerów, co stworzyłoby motywację do zerwania dopasowania. Stabilne dopasowania zapobiegają takim parom blokującym, zapewniając trwałość dopasowania bez renegocjacji.
Czy algorytm Gale’a-Shapleya zawsze generuje to samo dopasowanie?
Nie. Różne listy preferencji lub kolejności propozycji mogą prowadzić do różnych stabilnych dopasowań. Zawsze jednak istnieje stabilne dopasowanie "optymalne dla mężczyzn" (najlepsze dla wszystkich proponujących) i stabilne dopasowanie "optymalne dla kobiet" (najlepsze dla wszystkich odpowiadających).
Jak Gale-Shapley radzi sobie z preferencjami dotyczącymi grup (np. par)?
The standard algorithm does not directly handle couples or other constraints. Extensions like the couples algorithm exist but are more complex and may not guarantee stability for all preference profiles.
Pokrewne metody
Źródła
Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15.
Otwórz odnośnik DOISkopiowano.Roth, A. E. (1984). The economics of matching: Stability and incentives. Mathematics of Operations Research, 7(4), 617-628.
Otwórz odnośnik DOISkopiowano.