Problem trwałego małżeństwa

Problem trwałego małżeństwa (również model dwustronnego dopasowywania lub SPM) – zagadnienie z ekonomii, matematyki i informatyki polegające na znalezieniu stabilnego dopasowania między dwoma rozłącznymi zbiorami elementów o jednakowych rozmiarach, przy ustalonej sekwencji preferencji dla każdego elementu. Dopasowanie jest odwzorowaniem (bijekcją) elementów z jednego zestawu do elementów drugiego zestawu. Dopasowanie nie jest stabilne, jeśli:

• Istnieje element A pierwszego dopasowanego zestawu, który preferuje dany element B drugiego dopasowanego zestawu nad elementem, do którego A jest już dopasowany, oraz

• B również woli A od elementu, do którego B jest już dopasowane.

Innymi słowy, dopasowanie jest stabilne, gdy nie pozostawi elementów po przeciwnych stronach, które nie są do siebie dobrane, ale wolałyby być.

Problem trwałego małżeństwa został określony w następujący sposób:

Biorąc pod uwagę n mężczyzn i kobiet, gdzie każda osoba uszeregowała wszystkich członków płci przeciwnej w określonej sekwencji preferencji, dopasuj w pary małżeństw kobiety i mężczyzn, tak aby nie było dwóch osób przeciwnej płci, które wolałyby mieć siebie nawzajem zamiast obecnych partnerów. Gdy nie ma takich par, zbiór małżeństw uznaje się za stabilny.

Zastosowania

Algorytmy znajdowania rozwiązań problemu stabilnego małżeństwa mają wiele różnych zastosowań między innymi w analizie decyzji i badaniach operacyjnych np. przy rekrutacji do szkół, przydziału stażystów do szpitali, a nawet kojarzenia dawców organów z biorcami przeszczepów. Wykorzystywane są również w różnych dziedzinach inżynierii i ekonomii, takich jak podział pracy czy alokacja zasobów.

Ważnym zastosowaniem na dużą skalę problemu stabilnego małżeństwa jest przydzielanie użytkowników do serwerów w dużej rozproszonej usłudze internetowej. Miliardy użytkowników uzyskuje dostęp do stron internetowych, filmów i innych usług w Internecie, co wymaga, żeby każdy użytkownik był dopasowany do jednego z (potencjalnie) setek tysięcy serwerów na całym świecie, które oferują tę usługę. Użytkownik preferuje serwery, które są wystarczająco blisko, żeby zapewnić krótszy czas odpowiedzi na żądaną usługę, co powoduje (częściowe) preferencyjne porządkowanie serwerów dla każdego użytkownika. Każdy serwer woli obsługiwać użytkowników przy niższych kosztach, co powoduje (częściowe) preferencyjne porządkowanie użytkowników dla każdego serwera. Content delivery networks (CND), które dystrybuują większość światowych treści i usług, rozwiązują ten duży i złożony problem stabilnego małżeństwa między użytkownikami i serwerami co kilkadziesiąt sekund, aby umożliwić miliardom użytkowników dopasowanie się do serwerów, które mogą udostępniać żądane strony internetowe, filmy lub inne usługi.

Różne stabilne dopasowania

Może istnieć wiele różnych stabilnych dopasowań. Załóżmy na przykład, że są trzej mężczyźni (A, B, C) i trzy kobiety (X, Y, Z) o następujących preferencjach:

A: YXZ B: ZYX C: XZY

X: BAC Y: CBA Z: ACB

Istnieją trzy stabilne rozwiązania tego układu:

• mężczyźni wybierają pierwszą pozycję w rankingu, a kobiety trzecią – (AY, BZ, CX);

• wszyscy uczestnicy wybierają drugą pozycję – (AX, BY, CZ);

• kobiety wybierają pierwszą pozycję, a mężczyźni trzecią – (AZ, BX, CY).

Wszystkie trzy rozwiązania są stabilne, ponieważ niestabilność wymaga, żeby obie osoby z pary były bardziej zadowolone z alternatywnego dopasowania. Wybór przez jedną grupę pierwszych pozycji z preferencji spowoduje, że dopasowania będą stabilne, ponieważ elementy grupy nie byłyby zadowolone z żadnego innego proponowanego dopasowania – podobnie w sytuacji, gdy wszyscy wybiorą drugą pozycję z grupy, do której są dopasowywani. Ogólnie rzecz biorąc, rodzinie rozwiązań dowolnego przypadku problemu stabilnego małżeństwa można nadać strukturę skończonej sieci dystrybucyjnej, a ta struktura prowadzi do wydajnych algorytmów dla problemów dotyczących stabilnych małżeństw.

Algorytm odroczonej akceptacji

W 1962 r. David Gale i Lloyd Shapley udowodnili, że dla każdej równej liczby mężczyzn i kobiet zawsze można rozwiązać SMP i zapewnić stabilność wszystkich małżeństw. Przedstawili algorytm, zwany algorytmem odroczonej akceptacji (deferred acceptance algorithm), który można streścić w następujących punktach:

Punkt 1. Każdy mężczyzna oświadcza się kobiecie, która znajduje się na najwyższej pozycji w jego rankingu

Punkt 2. Każda kobieta notuje otrzymywane propozycje.

Punkt 3. Gdy wszyscy mężczyźni złożyli propozycje swoim wybrankom, każda kobieta, która odmawia (uprzejmie) wszystkim zapisanym wcześniej mężczyznom z wyjątkiem tego, który znajduje się najwyżej w jej rankingu. Nie oznacza to jednak jeszcze akceptacji przez kobietę tego zalotnika, który jest najbardziej preferowany spośród wszystkich zapisanych zalotników – chyba że jest to również mężczyzna najbardziej preferowany spośród wszystkich potencjalnych kandydatów.

Punkt 4. Odrzuceni zalotnicy składają propozycję następnej kobiecie w ich rankingu.

Punkt 5. Przejdź do punktu 2 lub zakończ algorytm, jeżeli każda kobieta otrzymała propozycję małżeństwa.

Algorytm zwraca najlepsze możliwe stabilne dopasowanie z punktu widzenia mężczyzn w tym sensie, że każdy mężczyzna preferuje wynik tego procesu kojarzenia w pary względem jakiegokolwiek innego stabilnego dopasowania. Oczywiście, gdybyśmy odwrócili rolę mężczyzn i kobiet, otrzymalibyśmy stabilne dopasowanie, które byłoby najlepsze dla kobiet.

Powiązane problemy

Problem stabilnych współlokatorów jest podobny do problemu stabilnych małżeństw, ale różni się tym, że wszyscy uczestnicy należą do jednej grupy (zamiast być podzieleni na równą liczbę „mężczyzn” i „kobiet”).

Problem szpitali / rezydentów – znany również jako problem przyjęć na uniwersytet – różni się od problemu stabilnego małżeństwa tym, że szpital może pomieścić wielu mieszkańców. Podobnie uniwersytet może przyjąć więcej niż jednego studenta. Algorytmy rozwiązywania problemu szpitala / rezydenta mogą być zorientowane na szpital lub na rezydenta. Problem ten został rozwiązany za pomocą algorytmu z tego samego oryginalnego artykułu Gale’a i Shapleya, w którym rozwiązano również problem stabilnego małżeństwa.

Problem dopasowania do umów stanowi uogólnienie problemu dopasowania, w którym uczestnicy mogą być dopasowani do różnych warunków umowy. Ważnym szczególnym przypadkiem umów jest dopasowywanie się do elastycznych wynagrodzeń.

Implementacja w pakietach oprogramowania

R: Algorytm Gale’a-Shapleya (znany również jako algorytm odroczonej akceptacji) dla problemu stabilnego małżeństwa jest zaimplementowany w pakiecie MatchMarkets.

Python: Algorytm Gale-Shapley jest zawarty w pakiecie QuantEcon / MatchingMarkets.py wraz z kilkoma innymi algorytmami dla ogólnych problemów z dopasowaniem.

API: MatchingTools API zapewnia algorytm Gale-Shapley poprzez bezpłatny interfejs programowania.