PL 
EnglishDomyślny
Українська💍 Stabilne skojarzenia
Prześledź algorytm odroczonej akceptacji Gale'a–Shapleya krok po kroku: oświadczyny, wstępne zaręczyny i odrzucenia prowadzą do stabilnego skojarzenia bez par blokujących.
💍 Stabilne dopasowanie — algorytm Gale’a-Shapleya
Obserwuj algorytm odroczonej akceptacji łączący członków Grupy A z Grupą B. Wolni proponujący w każdej rundzie oświadczają się swojemu kolejnemu ulubionemu wyborowi; odbiorcy tymczasowo zatrzymują najlepszą ofertę i odrzucają resztę, dopóki każda para nie stanie się stabilna i nikt nie będzie chciał zamiany.
🔬 Co pokazuje
Algorytm odroczonej akceptacji Gale’a-Shapleya zawsze kończy się stabilnym dopasowaniem: żadna para mężczyzna-kobieta nie wolałaby siebie nawzajem od swoich obecnych partnerów. Animacja pokazuje tymczasowe dopasowania (fiolet), odrzucenia (czerwony, zanikający) oraz ostateczny stabilny wynik (zielony).
🎮 Jak korzystać
Ustaw liczbę par (N) i naciśnij „Nowe losowe preferencje”, aby wygenerować świeże listy preferencji. Kliknij „Krok”, aby przejść o jedną rundę propozycji, albo „Auto-run”, aby obserwować przebieg z wybraną prędkością aż do osiągnięcia stabilnego dopasowania.
💡 Czy wiesz, że?
Ten dokładny algorytm przydziela każdego roku ponad 40 000 rezydentów medycznych do szpitali w Stanach Zjednoczonych poprzez National Resident Matching Program, a jego warianty przydzielają uczniów do szkół publicznych w miastach takich jak Nowy Jork i Boston.
O algorytmie stabilnego dopasowania Gale’a-Shapleya
Ta symulacja modeluje problem stabilnego małżeństwa, sformalizowany w 1962 roku przez matematyków Davida Gale’a i Lloyda Shapleya w artykule „College Admissions and the Stability of Marriage”. Mając N członków Grupy A i N członków Grupy B, z których każdy ma uszeregowaną listę preferencji dotyczącą drugiej strony, dopasowanie jest „stabilne”, jeśli nie istnieje para, która wolałaby siebie nawzajem od swoich przydzielonych partnerów. Algorytm odroczonej akceptacji konstruuje takie dopasowanie, każąc proponującym wielokrotnie składać oświadczyny kolejnemu, jeszcze nieodrzucającemu ich, ulubionemu wyborowi, podczas gdy odbiorcy tymczasowo zatrzymują najlepszą jak dotąd otrzymaną ofertę i odrzucają resztę — proces trwa, aż każdy proponujący zostanie dopasowany.
Poza swoją elegancką matematyką stabilne dopasowanie leży u podstaw jednych z najbardziej doniosłych algorytmów współczesnego życia: przydziela rezydentów medycznych do szpitali poprzez National Resident Matching Program, przydziela uczniów do szkół publicznych w miastach takich jak Nowy Jork i Boston oraz napędza programy wymiany nerek, które znajdują łańcuchy zgodnych par dawca-biorca. Za tę pracę Lloyd Shapley i projektant rynków Alvin Roth otrzymali w 2012 roku Nagrodę Nobla w dziedzinie ekonomii „za teorię stabilnych alokacji i praktykę projektowania rynków”.
Najczęściej zadawane pytania
Czym jest stabilne dopasowanie?
Stabilne dopasowanie to połączenie dwóch grup o równej liczebności, w których każdy członek ma uszeregowaną listę preferencji dotyczącą drugiej strony, takie że żadne dwie niepowiązane osoby nie wolałyby siebie nawzajem od swoich obecnych partnerów. Taka niestabilna para nazywana jest „parą blokującą”. Twierdzenie Gale’a-Shapleya dowodzi, że stabilne dopasowanie zawsze istnieje dla dowolnego zestawu list preferencji i można je znaleźć za pomocą algorytmu odroczonej akceptacji, niezależnie od struktury preferencji.
Jak działa algorytm odroczonej akceptacji?
Każdy niedopasowany członek grupy proponującej (Grupy A) proponuje najwyżej ocenianemu członkowi Grupy B, któremu jeszcze nie proponował. Każdy członek Grupy B porównuje wszystkie propozycje otrzymane w danej rundzie (plus partnera, którego aktualnie trzyma) i tymczasowo akceptuje tę, którą ocenia najwyżej, odrzucając resztę. Odrzuceni proponujący przechodzą do swojego kolejnego wyboru w następnej rundzie. Powtarza się to, dopóki każdy proponujący nie zostanie dopasowany — nikt nigdy nie jest akceptowany na stałe aż do samego końca, stąd „odroczona” akceptacja.
Jak korzystać z tej symulacji?
Wybierz liczbę par suwakiem „Pary (N)” i kliknij „Nowe losowe preferencje”, aby wygenerować świeże, losowe listy preferencji dla obu grup. Naciśnij „Krok”, aby przejść dokładnie o jedną rundę propozycji, obserwując fioletowe linie tworzące tymczasowe dopasowania i czerwone przerywane linie migające przy odrzuceniach, albo naciśnij „Auto-run”, by pozwolić algorytmowi działać automatycznie z wybraną prędkością aż do osiągnięcia stabilnego dopasowania (pokazanego na zielono).
Jakie systemy w rzeczywistości korzystają z tego algorytmu?
Najsłynniejszym zastosowaniem jest National Resident Matching Program, który od lat 50. XX wieku przydzielił ponad milion nowych lekarzy do programów rezydentury w amerykańskich szpitalach (algorytm został niezależnie odkryty przez ekonomistę Alvina Rotha jako blisko przypominający mechanizm, którego szpitale już wcześniej używały). Warianty tego algorytmu obsługują też systemy wyboru szkół w Nowym Jorku, Bostonie i innych okręgach, dopasowując uczniów do szkół, a programy wymiany nerek wykorzystują pokrewną teorię dopasowań, by znajdować długie łańcuchy zgodnych przeszczepów od żywych dawców, ratując tysiące istnień.
Jaki jest związek z Nagrodą Nobla z 2012 roku?
Lloyd Shapley, który współtworzył algorytm z Davidem Gale’em w 1962 roku wyłącznie jako matematyczną ciekawostkę, oraz ekonomista Alvin Roth, który później zastosował go do projektowania rzeczywistych rynków dopasowań, takich jak wymiana nerek i systemy wyboru szkół, wspólnie otrzymali w 2012 roku Nagrodę Nobla w dziedzinie ekonomii „za teorię stabilnych alokacji i praktykę projektowania rynków”. Pozostaje to fundamentalnym przykładem tego, jak abstrakcyjna matematyka po dziesięcioleciach od odkrycia znajduje bezpośrednie, ratujące życie zastosowanie praktyczne.
Dlaczego wynik nazywany jest „optymalnym dla proponujących”?
Gdy to Grupa A składa oświadczyny, wynikowe stabilne dopasowanie jest dowiedlnie najlepszym możliwym stabilnym wynikiem jednocześnie dla każdego członka Grupy A — żadne inne stabilne dopasowanie nie mogłoby dać żadnemu proponującemu bardziej preferowanego partnera. Symetrycznie jest to najgorszy stabilny wynik dla każdego członka Grupy B, ponieważ odbiorcy mogą być dopasowani jedynie z kimś co najmniej tak dobrym, jak ich wynik przy dowolnym innym stabilnym dopasowaniu. To, która strona składa oświadczyny, ma więc realne konsekwencje dystrybucyjne, mimo że każde stabilne dopasowanie jest „sprawiedliwe” w sensie braku par blokujących.
Czy odroczona akceptacja jest odporna na strategiczne manipulacje?
Tak, dla strony proponującej: dla każdego członka Grupy A strategią dominującą jest zgłoszenie swojej prawdziwej, szczerej listy preferencji, ponieważ żadne strategiczne zafałszowanie nigdy nie może dać proponującemu lepszego wyniku niż mówienie prawdy w tym algorytmie. Ta sama gwarancja nie obowiązuje jednak dla strony odbierającej (Grupy B) — w niektórych przypadkach odbiorca mógłby teoretycznie uzyskać lepszego partnera, strategicznie odrzucając propozycję, którą zaakceptowałby przy szczerych preferencjach, choć wymaga to szczegółowej znajomości preferencji wszystkich pozostałych, co w praktyce jest rzadko dostępne.
Co się dzieje przy nierównych rozmiarach grup lub preferencjach z remisami?
Gdy Grupa A i Grupa B mają różne rozmiary, algorytm nadal wytwarza stabilne dopasowanie, ale w większej grupie z konieczności pewni członkowie pozostają niedopasowani. Gdy jednostki mają remisy na swoich listach preferencji (obojętność między dwiema lub więcej opcjami), klasyczna gwarancja stabilności może osłabnąć, a badacze opracowali kilka wariantów rozstrzygania remisów — silną, słabą i super-stabilność — z których każda ma inne właściwości istnienia i złożoności, co stanowi aktywny obszar dzisiejszych badań w algorytmicznej teorii gier.