Jak to działa?

Algorytm Gale’a-Shapleya, znany również jako algorytm stabilnego małżeństwa, został zaproponowany w 1962 roku przez Davida Gale’a i Lloyda Shapleya. Służy do znajdowania stabilnego dopasowania pomiędzy dwoma równolicznymi zbiorami, np. mężczyznami i kobietami w kontekście kojarzenia par lub studentami i uczelniami w procesie rekrutacyjnym.

Definicje

• Stabilne dopasowanie – sytuacja, w której nie istnieje żadna para (mężczyzna, kobieta), która preferowałaby siebie nawzajem bardziej niż swoje obecne dopasowania.
• Preferencje – każdy element jednego zbioru ma uporządkowaną listę preferencji względem elementów drugiego zbioru.

Opis algorytmu

1. Każdy mężczyzna składa propozycję oświadczyn najwyżej preferowanej kobiecie, która go jeszcze nie odrzuciła.
2. Każda kobieta rozważa wszystkie otrzymane propozycje i:
   • Akceptuje najlepszą spośród nich (zgodnie ze swoją listą preferencji), ale nie składa ostatecznej decyzji.
   • Odrzuca pozostałych kandydatów.
3. Odrzuceni mężczyźni składają propozycje kolejnym kobietom z ich listy preferencji.
4. Proces powtarza się, aż każda kobieta będzie miała dokładnie jednego "narzeczonego".
5. Powstałe dopasowanie jest stabilne i kończy algorytm.

Złożoność obliczeniowa

Algorytm działa w czasie \(O(n^2)\), gdzie \(n\) to liczba elementów w każdym ze zbiorów. W najgorszym przypadku każdy mężczyzna może złożyć propozycję wszystkim kobietom.

Własności

• Algorytm gwarantuje stabilność dopasowania.
• Wynik jest optymalny dla strony proponującej (np. dla mężczyzn, jeśli to oni składają propozycje).
• Może być niesprawiedliwy dla drugiej strony, która otrzymuje propozycje.

Przykład

Rozważmy zbiór trzech mężczyzn (M1, M2, M3) i trzech kobiet (K1, K2, K3) z następującymi preferencjami:

Preferencje mężczyzn:

• M1: K2, K1, K3
• M2: K1, K2, K3
• M3: K1, K3, K2

Preferencje kobiet:

• K1: M2, M1, M3
• K2: M1, M2, M3
• K3: M1, M2, M3

Proces działania algorytmu:

1. M1 oświadcza się K2, M2 oświadcza się K1, M3 oświadcza się K1.
2. K1 otrzymuje propozycje od M2 i M3 – wybiera M2 (zgodnie z preferencjami) i odrzuca M3.
3. M3 składa propozycję K3, która go akceptuje.
4. W kolejnej iteracji dopasowanie jest już stabilne: (M1, K2), (M2, K1), (M3, K3).

Zastosowania

• Kojarzenie par w systemach matrymonialnych.
• Dopasowanie studentów do uczelni (np. system rekrutacyjny do szkół wyższych).
• Systemy przydzielania rezydentur medycznych.
• Alokacja organów do przeszczepów.

Ograniczenia portalu

• algorytm obsługuje tylko kontakty między mężczyzną a kobietą i nie obsługuje innych kontaktów
• algorytm bazuje tylko na preferencjach na bazie pięciogwiazdkowego systemu polubień drugiej osoby
• system może sparować maksymalnie 100 osób łącząc je w 50 par ze względu na wydajność i moc obliczeniową

Podsumowanie

Algorytm Gale’a-Shapleya to skuteczna metoda znajdowania stabilnego dopasowania w wielu rzeczywistych problemach. Choć gwarantuje stabilność, jego wynik może faworyzować stronę składającą propozycje. Jego prostota i efektywność sprawiają, że jest szeroko stosowany w różnych dziedzinach życia.