Problem stabilnego małżeństwa: Modele matematyczne i sposoby rozwiązania

Problem stabilnego małżeństwa (ang. Stable Marriage Problem, SMP) to klasyczny problem kombinatoryczny z zakresu teorii gier i algorytmiki. Polega on na znalezieniu stabilnego sposobu kojarzenia par w grupie mężczyzn i kobiet (lub bardziej ogólnie, w dwóch zbiorach), gdzie każdy uczestnik ma uporządkowane preferencje wobec potencjalnych partnerów. Stabilność oznacza, że nie istnieje para, która preferuje siebie nawzajem bardziej niż swoje aktualne przydziały.

Formalizacja matematyczna

Niech mamy dwa zbiory o jednakowej liczebności \( n \):

• \( M = {m_1, m_2, \dots, m_n} \) (zbiór mężczyzn),
• \( W = {w_1, w_2, \dots, w_n} \) (zbiór kobiet).

Każdy mężczyzna i kobieta ma uporządkowaną listę preferencji dotyczącą drugiego zbioru.

Dopasowanie \( μ \) to funkcja, która przypisuje każdemu mężczyźnie kobietę i na odwrót. Dopasowanie \( μ \) jest stabilne, jeśli nie istnieje para \( (m, w) \), która wolałaby siebie nawzajem bardziej niż swoje obecne dopasowania.

Algorytm Gale’a-Shapleya

Najbardziej znanym sposobem rozwiązania SMP jest algorytm Gale’a-Shapleya (1962), zwany algorytmem propozycyjnym. Działa on w następujący sposób:

1. Każdy mężczyzna składa propozycję pierwszej kobiecie z jego listy preferencji.
2. Każda kobieta wybiera najlepszego (jej zdaniem) kandydata spośród tych, którzy jej się oświadczyli, odrzucając resztę.
3. Odrzuceni mężczyźni składają propozycję kolejnym kobietom z ich list.
4. Proces powtarza się, aż wszyscy uczestnicy zostaną sparowani.

Dowód poprawności algorytmu Gale’a-Shapleya

Dowiedziemy, że algorytm Gale’a-Shapleya zawsze prowadzi do stabilnego dopasowania.

Twierdzenie

Algorytm Gale’a-Shapleya zawsze znajduje stabilne dopasowanie w czasie \( O(n^2) \).

Dowód

• Zbieżność algorytmu: W każdym kroku algorytmu co najmniej jeden mężczyzna składa propozycję nowej kobiecie, a zatem w każdym kroku proces posuwa się naprzód. Ponieważ liczba możliwych propozycji jest ograniczona przez \( n^2 \), algorytm musi zakończyć się w skończonym czasie.
• Brak cykli: Ponieważ każda kobieta może przyjąć tylko najlepszego (według siebie) kandydata spośród tych, którzy jej się oświadczyli, nie może dojść do cofania się w decyzjach.
• Stabilność: Załóżmy, że w wyniku algorytmu powstaje niestabilne dopasowanie, czyli istnieje para \( (m, w) \), która preferuje siebie nawzajem bardziej niż swoje obecne dopasowanie. To oznacza, że \( m \) musiał złożyć propozycję \( w \), ale został odrzucony na rzecz lepszego kandydata. Zatem \( w \) powinno być sparowane z kimś, kogo preferuje bardziej niż \( m \), co jest sprzecznością.

Z powyższych argumentów wynika, że algorytm zawsze znajduje stabilne dopasowanie.

Przykład

Rozważmy następujące preferencje dla trzech mężczyzn i trzech kobiet:

MĘŻCZYŹNI:

• \( m_1 \): \( w_1 > w_2 > w_3 \)
• \( m_2 \): \( w_2 > w_3 > w_1 \)
• \( m_3 \): \( w_3 > w_1 > w_2 \)

KOBIETY:

• \( w_1 \): \( m_2 > m_1 > m_3 \)
• \( w_2 \): \( m_3 > m_2 > m_1 \)
• \( w_3 \): \( m_1 > m_3 > m_2 \)

Po zastosowaniu algorytmu Gale’a-Shapleya otrzymujemy stabilne dopasowanie: \( (m_1, w_1), (m_2, w_2), (m_3, w_3) \).

Rozszerzenia problemu

Problem stabilnego małżeństwa może być rozszerzony na:

• SMP z nierównymi zbiorami – gdy liczba mężczyzn i kobiet jest różna,
• SMP z ograniczeniami – gdy niektóre pary są niedozwolone,
• SMP dla wielu stron – rozszerzenie na wiele grup zamiast dwóch.

Podsumowanie

Problem stabilnego małżeństwa to ważne zagadnienie matematyczne o szerokich zastosowaniach, m.in. w alokacji miejsc w szpitalach dla rezydentów medycznych czy dopasowaniu uczniów do szkół. Algorytm Gale’a-Shapleya stanowi efektywne rozwiązanie, choć może być modyfikowany w zależności od warunków problemu.