Solver Problemu Stabilnych Małżeństw

O Solver Problemu Stabilnych Małżeństw

Solver Problemu Stabilnych Małżeństw to interaktywna implementacja algorytmu odroczonej akceptacji Gale'a-Shapleya. Jest to algorytm dopasowania z 1962 roku, o którym David Gale i Lloyd Shapley udowodnili, że zawsze generuje stabilne parowanie między dwiema grupami o równej wielkości, biorąc pod uwagę pełny ranking preferencji każdego członka. Narzędzie to pobiera listy preferencji, uruchamia algorytm krok po kroku i pokazuje wynik w postaci stabilnego dopasowania, animowanej wizualizacji dwudzielnej, map cieplnych preferencji oraz zweryfikowanego dowodu na brak par blokujących.

Czym Jest Problem Stabilnych Małżeństw?

Mając dwa rozłączne zbiory równej wielkości — powiedzmy n mężczyzn i n kobiet lub n kandydatów i n stanowisk — oraz kompletną listę preferencji od każdego członka rankinguje każdego członka drugiej strony, dopasowanie to parowanie jeden do jednego między tymi dwoma zbiorami. Dopasowanie nazywa się stabilnym, jeśli nie istnieje żadna para (a, b) spoza dopasowania, która wolałaby być razem, niż pozostać ze swoimi przypisanymi partnerami.

Formalnie, dopasowanie M jest stabilne, jeśli nie istnieje para blokująca — para (a, b), gdzie a jest dopasowane do b', a b do a', taka że:

Jeśli oba warunki są spełnione, zarówno a, jak i b porzuciliby swoich obecnych partnerów, co destabilizuje dopasowanie. Stabilne dopasowanie to takie, w którym żadna taka para nie istnieje.

Algorytm Gale'a-Shapleya

Gale i Shapley udowodnili — konstruktywnie — że stabilne dopasowanie zawsze istnieje dla dowolnego zestawu preferencji i podali wydajny algorytm do jego znalezienia. Algorytm przebiega w rundach:

1. Każdy wolny proponujący składa propozycję najwyżej ocenianemu odbiorcy na swojej liście, który jeszcze go nie odrzucił.
2. Każdy odbiorca, który otrzymał jedną lub więcej propozycji, wybiera tę, którą preferuje najbardziej (porównując ją z obecnym tymczasowym narzeczonym) i wstępnie akceptuje; wszyscy inni zostają odrzuceni.
3. Odrzuceni proponujący stają się ponownie wolni i przechodzą do swojego następnego wyboru w kolejnej rundzie.
4. Algorytm kończy się, gdy każdy proponujący jest zajęty — co gwarantuje się, że nastąpi w maksymalnie n² propozycjach.

Kluczowe Właściwości Teoretyczne

Istnienie i Unikalność

Stabilne dopasowanie zawsze istnieje (Gale i Shapley, 1962), ale niekoniecznie jest unikalne. Dla danego zestawu preferencji może istnieć wiele stabilnych dopasowań, które tworzą kratę uporządkowaną według wspólnych preferencji.

Optymalność dla Proponującego

Gdy jedna strona proponuje, algorytm Gale'a-Shapleya generuje stabilne dopasowanie optymalne dla proponujących: każdy proponujący otrzymuje najlepszego partnera, z jakim mógłby być sparowany w jakimkolwiek stabilnym dopasowaniu. Przez symetryczny argument jest to również dopasowanie najgorsze dla przyjmującego — strona przyjmująca otrzymuje swojego najgorszego stabilnego partnera. Zmiana strony proponującej w tym kalkulatorze często zmienia wynik.

Odporność na Strategię dla Proponujących

W algorytmie Gale'a-Shapleya proponujący nie mają motywacji do fałszowania swoich preferencji: mówienie prawdy jest dla nich strategią dominującą. Odbiorcy mogą jednak czasami zyskać na strategicznym fałszowaniu — jest to jeden z powodów, dla których rynek rezydentur medycznych w USA jest zaprojektowany tak, by studenci byli stroną proponującą.

Twierdzenie o Szpitalach Wiejskich (Rural Hospitals Theorem)

Zbiór niedopasowanych agentów jest identyczny we wszystkich stabilnych dopasowaniach. Zatem jeśli Twoja instancja ma nierówne rozmiary (co wykracza poza zakres tego klasycznego narzędzia), te same osoby pozostaną niedopasowane w każdym stabilnym rozwiązaniu.

Format Danych Wejściowych

Ten kalkulator oczekuje jednego wiersza na członka, z imieniem, po którym następuje dwukropek i pełna lista rankingowa preferencji oddzielona przecinkami:

Wymagania:

• Obie grupy muszą mieć dokładnie taką samą liczbę członków.
• Każdy członek musi rankingować każdego członka drugiej grupy — nie dopuszcza się list częściowych.
• Imiona mogą zawierać litery, cyfry, podkreślenia, myślniki, spacje i popularne znaki Unicode.
• Obsługiwane jest do 15 członków na stronę w celu zapewnienia płynnej animacji interaktywnej.

Jak Korzystać z Tego Kalkulatora

1. Wprowadź preferencje dla Grupy A w lewym polu tekstowym — jeden wiersz na członka, pełna lista rankingowa.
2. Wprowadź preferencje dla Grupy B w prawym polu tekstowym — jeden wiersz na członka, ten sam format.
3. Wybierz stronę proponującą. Wybierz Grupę A lub Grupę B. Wypróbuj obie, aby porównać wyniki optymalne dla A i optymalne dla B.
4. Kliknij „Rozwiąż Stabilne Dopasowanie”. Kalkulator uruchomi algorytm Gale'a-Shapleya i wygeneruje stabilne pary, statystyki, animację oraz dowód stabilności.
5. Przeglądaj animację za pomocą przycisków odtwarzania / kroku / resetu, aby zobaczyć każdą propozycję, akceptację, zamianę i odrzucenie w kolejności.
6. Sprawdź mapę cieplną. Każda komórka pokazuje rangę; komórki z żółtym obramowaniem tworzą ostateczne dopasowanie — zobacz, jak wysoko lub nisko znajdują się te komórki, aby ocenić „szczęście” każdej ze stron.

Przykład — Klasyczne 3×3

Mężczyźni: Alex, Bryan, Chris. Kobiety: Bea, Claire, Diana. Preferencje:

Uruchomienie algorytmu Gale'a-Shapleya z mężczyznami jako proponującymi daje pary Alex–Bea, Bryan–Claire, Chris–Diana w jednej rundzie (każdy mężczyzna dopasowuje się do swojego pierwszego wyboru z kobietą, której pierwszym wyborem jest ktoś inny — brak konfliktu). Dopasowanie jest stabilne: żadna para mężczyzna-kobieta nie byłaby w lepszej sytuacji po zamianie partnerów, więc nie ma pary blokującej.

Zastosowania w Świecie Rzeczywistym

Dlaczego Lloyd Shapley Otrzymał Nagrodę Nobla

W 2012 roku Królewska Szwedzka Akademia Nauk przyznała Nagrodę Nobla w dziedzinie ekonomii Lloydowi Shapleyowi (za teorię, wraz z Davidem Gale'em, który zmarł wcześniej) oraz Alvinowi Rothowi (za zastosowanie teorii na rzeczywistych rynkach, w tym przeprojektowanie systemu dopasowania rezydentur medycznych w USA i sieci wymiany nerek). W uzasadnieniu wskazano na „teorię stabilnych alokacji i praktykę projektowania rynków”.

Często Zadawane Pytania

Czym jest problem stabilnych małżeństw?

Problem stabilnych małżeństw stawia pytanie: mając dwie grupy o równej liczbie członków, w których każdy członek rankinguje wszystkich członków drugiej grupy od najbardziej do najmniej preferowanych, czy możemy połączyć wszystkich w pary tak, aby żadne dwie osoby nie wolały opuścić swoich obecnych partnerów dla siebie nawzajem? Takie połączenie nazywa się stabilnym dopasowaniem. Algorytm Gale'a-Shapleya rozwiązuje ten problem w czasie O(n²) i zawsze znajduje stabilne dopasowanie.

Jak działa algorytm Gale'a-Shapleya?

Algorytm odroczonej akceptacji Gale'a-Shapleya przebiega w rundach. W każdej rundzie każdy obecnie wolny proponujący składa propozycję najwyżej ocenianemu odbiorcy na swojej liście, który jeszcze go nie odrzucił. Każdy odbiorca wstępnie akceptuje najlepszą otrzymaną dotąd propozycję i odrzuca pozostałe; każdy zastąpiony proponujący staje się ponownie wolny. Algorytm kończy się, gdy żaden proponujący nie jest wolny, co następuje w maksymalnie n² propozycjach.

Czy stabilne dopasowanie jest unikalne?

Nie. Instancja problemu stabilnego małżeństwa może mieć wiele stabilnych dopasowań. Jednak gdy jedna strona proponuje, Gale-Shapley zawsze generuje stabilne dopasowanie optymalne dla proponujących: każdy proponujący otrzymuje najlepszego partnera, jakiego mógłby dostać w jakimkolwiek stabilnym dopasowaniu. Przez symetrię jest to również dopasowanie najgorsze dla odbiorcy. Zmiana strony proponującej często daje inne stabilne dopasowanie.

Co to jest para blokująca?

Para blokująca to para (a, b), która nie jest obecnie dopasowana, gdzie a woli b od swojego partnera ORAZ b również woli a od swojego partnera. Jeśli taka para istnieje, dopasowanie jest niestabilne. Stabilne dopasowanie nie ma par blokujących, co ten kalkulator weryfikuje automatycznie.

Jakie są rzeczywiste zastosowania stabilnego dopasowania?

Algorytm Gale'a-Shapleya napędza systemy takie jak NRMP w USA (staże lekarzy), systemy wyboru szkół w Bostonie i Nowym Jorku, rekrutację na uczelnie, łańcuchy wymiany nerek oraz przydział współlokatorów.

Czy obie grupy muszą być tej samej wielkości?

W klasycznej wersji tak. Obie strony muszą mieć tę samą liczbę członków i pełne rankingi. Istnieją warianty dla grup o różnych rozmiarach, ale wymagają one innych algorytmów. Ten kalkulator obsługuje wariant klasyczny.

Dalsza Lektura

• Problem stabilnych małżeństw — Wikipedia
• Algorytm Gale'a-Shapleya — Wikipedia
• National Resident Matching Program — Wikipedia
• Nagroda Nobla w dziedzinie ekonomii 2012 — Shapley i Roth