Zasada stabilnej dopasowywania: algorytm Gale-Shapleya

Problem: nie ma miejsca na lustrzane spojrzenia

Załóżmy dwie równoliczne grupy — np. n kandydatów i n szpitali — każda z rankingu preferencji nad drugą stroną. Dopasowanie połącza każdego członka jednej grupy dokładnie z jednym członkiem drugiej. Jest stabilne, jeśli nie ma blokujących par: dwóch osób, które nie są dopasowane do siebie, ale obie by się lepiej dopasowały do siebie niż do swoich bieżących partnerów. Jeśli istnieje blokująca para, dopasowanie jest niewytrzymałe — te dwie mają motywację, aby sprecyzować wspólnie, niezależnie od oficjalnej przypisanej ról. David Gale i Lloyd Shapley udowodnili w 1962 roku, że dla dowolnego zestawu preferencji istnieje zawsze stabilne dopasowanie, a podali konstruktywny algorytm do jego znalezienia — praca ta, rozszerzona przez Alvina Rotha do projektowania rynków rzeczywistych, dodała Shapleyowi i Rothowi Nobla wady ekonomiczne w 2012 roku.

Krok po kroku zanieczyszczonej akceptacji

Algorytm działa w rundach. Każdy niezajęty proponujący (np., kandydat) propozycję najbardziej cenionemu odbiorcy (szpitalowi), do którego jeszcze nie propozował. Każdy odbiorca sprawdza wszystkie proponujące mu osoby z tej rundy oraz tych, którym już tentatywnie jest przydzielony, i zachowuje tylko swoją najbardziej cenioną ofertę, odrzucając resztę — nawet jeśli to oznacza odrzucenie kandydata akceptowanego w poprzedniej rundzie. Odrzucone proponujące usuną się z listy i propozycję przesłają swojej kolejnej wybranicy w kolejnej rundzie. Ten proces powtarza się, aż każdy proponujący jest tentatywnie przydzielony przez odbiorcę, co oznacza, że wszystkie tentatywne umowy stały się końcowe.

jeżeli istnieje wolny proponujący p i nie propozował do wszystkich: r = najbardziej ceniony odbiorca p, do którego p jeszcze nie propozował p propozuje do r jeśli r jest wolny: r tentatywnie akceptuje p lub jeśli r preferuje p nad swoim obecnym tentatywnym pasjonatem p': r odrzuca p', tentatywnie akceptuje p // p' ponownie staje się wolny w przeciwnym razie: r odrzuca p // p próbuje swojej kolejnej wybranej osoby zwrot tentatywnych pasji — teraz końcowe i stabilne Słowo zanieczyszczone jest kluczowym pomysłem: akceptacja odbiorcy jest zawsze tymczasowa, aż do momentu końca, więc proponujący może być „zastąpiony” lepszą ofertą na dowolnym etapie. Jednak odbiorca nigdy nie czynnie zobowiązuje się, dopóki nie przestanie przychodzić lepsze propozycje. To dokładnie dlaczego proces nie może zawsze cykliczny — każda odrzucenie usunąłoby na zawsze jedną parę proponujący-odbiorca z rozważań, a jest tylko n² takich par, więc algorytm zakończy się w najwyżej n² propozycjach.

while some proposer p is free and has not proposed to everyone:
    r = p's most-preferred receiver not yet proposed to
    p proposes to r
    if r is free:
        r tentatively accepts p
    elif r prefers p to its current tentative match p':
        r rejects p', tentatively accepts p     // p' becomes free again
    else:
        r rejects p                              // p tries its next choice
return the tentative matches — now final and stable

Dlaczego wynik nie ma blokujących par

Ponieważ kandydat A kończy się zgodnie z przypisaniem do szpitala H, ale na самом деле factum, A bardziej lubi inny szpital H′. Algorytm gwarantuje, że A w pewnym momencie przed osiągnięciem H zaproponował H′ (przeprowadzający zawsze kandydaty po swojej liście), a H′ odrzuciła A – co możliwe tylko wtedy, gdy H′ już (tymczasowo lub na koniec) posiadała kogoś, kogo bardziej lubiła niż A. Ponieważ przyjęty przez odbioracza partner może tylko poprawiać się z czasem, H′ nadal lepiej ocenił swój końcowy partner niż A na końcu. Stąd A i H′ nie mogą tworzyć blokujących par: każda z nich, która ocenia potencjalny wymiana nieludzko, blokuje ją. Przeanalizowanie tego argumentu dla każdego kandydata dowodzi, że końcowe przypisanie jest stabilne.

Proposer-optimal, receiver-pessimal

Algorytm nie jest symetryczny, a nierównowaga ma rzeczywiste konsekwencje. Strona, która proponuje, kończy z najlepszym partnerem, jakiego mógłby osiągnąć w dowolnej stabilnej przypisanej pare, podczas gdy strona odbierająca kończy z najgorszym stabilnym partnerem. Przestawienie roli między tych stron jest ogólnie spowoduje inny — nadal stabilny — dopasowanie, lepsze dla nowych proposerów i gorsze dla nowych receiverów. To nie jest notka: kiedy Program Stabilnej Przydzielania Młodych Lekarzy w Stanach Zjednoczonych przystosował swoje algorytmy w latach 90., decyzja o tym, aby studentami medycznymi (a nie szpitalami) była stroną proponującą, była świadomym wyborzem, mającym na celu uzyskanie wyników bardziej korzystnych dla kandydatów.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Stable Matching i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.