Algorytm Gale’a-Shapleya do doboru par

Algorytm Gale’a-Shapleya, znany również jako algorytm stabilnego dopasowania (Stable Marriage Algorithm), został opracowany w 1962 roku przez Davida Gale’a i Lloyda Shapleya. Rozwiązuje on problem stabilnego dopasowania, czyli parowania dwóch grup obiektów w taki sposób, aby żadna para nie miała motywacji do zerwania istniejącego dopasowania i stworzenia nowego.

Algorytm ten znajduje szerokie zastosowanie w rzeczywistości, m.in. w procesie przyjmowania studentów na studia medyczne w USA (National Resident Matching Program) oraz w systemach rekomendacyjnych.

Problem stabilnego dopasowania

Rozważmy scenariusz klasycznego problemu stabilnego dopasowania, w którym mamy dwie grupy osób: \(n\) mężczyzn i \(n\) kobiet. Każda osoba posiada uporządkowaną listę preferencji względem osób z przeciwnej grupy. Celem algorytmu jest utworzenie dopasowania, które jest stabilne, co oznacza, że:

1. Każdy mężczyzna i każda kobieta są w związku z dokładnie jedną osobą.
2. Nie istnieje para (mężczyzna, kobieta), którzy woleliby być razem niż z osobami, z którymi są obecnie dopasowani.

Jeśli istnieje taka para, mówimy o niestabilnym dopasowaniu, ponieważ mogliby się oni zbuntować i stworzyć nową parę, co psuje obecne rozwiązanie.

Opis algorytmu

Algorytm Gale’a-Shapleya działa w sposób iteracyjny, gdzie jedna grupa (np. mężczyźni) proponuje, a druga (np. kobiety) akceptuje lub odrzuca propozycje.

1. Każdy niezaręczony mężczyzna proponuje małżeństwo pierwszej kobiecie na swojej liście preferencji.
2. Każda kobieta rozpatruje wszystkie otrzymane propozycje i:
   • Jeśli nie jest jeszcze zaręczona, akceptuje najlepszą propozycję zgodnie ze swoją listą preferencji.
   • Jeśli jest już zaręczona, porównuje swojego obecnego narzeczonego z nową propozycją. Jeśli nowa propozycja jest lepsza, zrywa obecne zaręczyny i akceptuje nową.
3. Proces powtarza się, dopóki wszyscy nie zostaną zaręczeni.

Gwarantuje to, że algorytm zakończy się w skończonej liczbie iteracji i zwróci stabilne dopasowanie.

Przykład działania

Rozważmy następujący przykład z trzema mężczyznami i trzema kobietami. Ich preferencje są następujące:

Iteracja 1:

• A proponuje X, B proponuje Y, C proponuje X.
• X ma dwie propozycje: od A i C. Wybiera A (bo A > C według jej preferencji), C zostaje odrzucony.

Iteracja 2:

• C, który został odrzucony, proponuje Y.
• Y ma dwie propozycje: od B i C. Wybiera C (bo C > B według jej preferencji), B zostaje odrzucony.

Iteracja 3:

• B, który został odrzucony, proponuje X.
• X ma teraz propozycje od A i B. Wybiera B (bo B > A według jej preferencji), A zostaje odrzucony.

Iteracja 4:

• A, który został odrzucony, proponuje Y.
• Y ma już partnera (C) i nadal preferuje C nad A, więc A zostaje odrzucony.

Koniec:

• A zostaje sparowany z Z, B z X, a C z Y.
• Dopasowanie: (A, Z), (B, X), (C, Y)

Własności algorytmu

• Złożoność czasowa – Algorytm działa w czasie \(O(n^2)\), ponieważ każda osoba może być odrzucona co najwyżej \(n-1\) razy.
• Optymalność dla proponującej grup – Algorytm zwraca dopasowanie optymalne dla mężczyzn (jeśli to oni proponują), ale niekoniecznie dla kobiet.
• Jednoznaczność rozwiązania – Chociaż może istnieć wiele stabilnych dopasowań, algorytm zawsze zwraca jedno z nich.

Zastosowania

Algorytm Gale’a-Shapleya jest stosowany w różnych dziedzinach:

• Dopasowanie rezydentów do szpitali – w systemie NRMP, gdzie lekarze-stażyści i szpitale mają swoje preferencje.
• Systemy rekomendacyjne – np. platformy randkowe czy systemy dobierania studentów do mentorów.
• Przydział miejsc w szkołach i uczelniach – np. w niektórych krajach systemy rekrutacyjne do szkół średnich i uczelni wykorzystują warianty tego algorytmu.

Podsumowanie

Algorytm Gale’a-Shapleya to klasyczne rozwiązanie problemu stabilnego dopasowania. Jest prosty, efektywny i znajduje zastosowanie w realnym świecie. Choć może nie być optymalny dla obu stron, zawsze zapewnia stabilność dopasowania, co jest kluczowe w wielu sytuacjach praktycznych.