ROCZNIKI POLSKIEGO TOWARZYSTWA MATEMATYCZNEGO
Seria II: WIADOMOÅšCI MATEMATYCZNE XLIV (2008)
Zbigniew Świtalski (Zielona Góra)
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół
Co ma wspólnego kojarzenie małżeństw z rekrutacją kandydatów do
szkół? Okazuje się, że ma i to dużo. Jako pierwsi zauważyli to matema-
tycy amerykańscy David Gale i Lloyd Stowell Shapley, którzy w 1962 roku
opublikowali w American Mathematical Monthly swój słynny artykuł College
admissions and the stability of marriage [GS62]. Gale i Shapley przedstawili
prosty formalny model procesu rekrutacji, zdefiniowali pojęcie optymalnego
przydziału kandydatów do szkół i podali elegancki dowód istnienia przy-
działu optymalnego. Swoje rozważania ilustrowali właśnie modelem koja-
rzenia małżeństw, który można traktować jako pewną uproszczoną wersję
modelu rekrutacji (zob. p. 2). We współczesnej literaturze oba modele wcho-
dzÄ… w zakres rozbudowanej teorii kojarzenia z dwustronnymi preferencjami
(two-sided matching theory). Warto bliżej przyjrzeć się tej ciekawej i mającej
wiele zastosowań praktycznych problematyce, zwłaszcza że jest ona jeszcze
mało spopularyzowana w polskiej literaturze matematycznej (zob. [Świ05],
[ADG03], [Kas07]).
W dalszej części artykułu omówię problemy, jakie pojawiają się przy sto-
sowaniu tradycyjnych metod rekrutacji, opiszę krótko model Gale a-Shap-
leya, przedstawię kilka ciekawych zagadnień teoretycznych związanych z tym
modelem, a na zakończenie wspomnę o możliwych zastosowaniach prezen-
towanej teorii.
1. Proces rekrutacji. Gale a i Shapleya zainspirował artykuł, który
opublikował New Yorker 10 września 1960 roku [Gal01]. Autor artykułu
przedstawiał problemy związane z rekrutacją kandydatów do Uniwersytetu
Yale. Ponieważ kandydaci mogli zgłaszać się jednocześnie do wielu uczelni,
Uniwersytet miał problem z ustaleniem, którzy kandydaci spośród zgłaszają-
cych się (i przyjętych) ostatecznie podejmą naukę. Trudno było też wymagać
od kandydatów, aby podawali informację o swoich preferencjach (np. o tym,
czy Uniwersytet Yale majÄ… na pierwszym, czy na dalszym miejscu swojej
listy preferencji), gdyż kandydaci mogli obawiać się tego, że jeśli wskażą
inne uczelnie jako lepsze od Uniwersytetu Yale, to zmniejszÄ… swoje szanse
na przyjęcie.
36 Z. Åš w i t a l s k i
Niektóre z problemów opisywanych przez Gale a i Shapleya pojawiły
się po 40 latach w Polsce, w momencie wprowadzania systemów rekrutacji
opartych na zewnętrznych testach kompetencji. Dotyczyło to szkół średnich
(ponadgimnazjalnych), do których rozpoczęto przyjmowanie na podstawie
testów kończących gimnazjum w 2000 roku oraz szkół wyższych, w których
wprowadzono systemy rekrutacji oparte na wynikach nowej matury w 2005
roku.
Sytuacja w szkołach ponadgimnazjalnych wyglądała następująco1.
W roku 2000 każdy kandydat kończący gimnazjum mógł zgłosić się tylko
do jednej szkoły ponadgimnazjalnej. Kandydatom, którzy nie dostali się do
wybranych szkół (było wśród nich wielu z wysoką punktacją z testów, którzy
nie dostali się do najbardziej obleganych szkół) pozostawało poszukiwanie
miejsc w szkołach nisko notowanych w rankingach (bo tylko w takich zostały
jeszcze wolne miejsca). Rodziło to wiele frustracji wśród kandydatów i rodzi-
ców, a wprowadzony system był powszechnie krytykowany (zob. [Paw00]).
W roku 2002 dopuszczono możliwość składania podań do dowolnej liczby
szkół (w roku 2001, ze względu na reformę oświatową i wprowadzenie 3-
letnich liceów rekrutacji nie przeprowadzono). Skutek był taki, że wszystkie
miejsca w najlepszych liceach zostały zajęte w 1. etapie rekrutacji przez
najlepszych kandydatów. Wszyscy pozostali kandydaci (była ich większość)
musieli z niepokojem oczekiwać na stopniowe zwalnianie się miejsc i możli-
wość dostania się do jakiejkolwiek szkoły (wielu z nich musiało podejmować
trudne decyzje czy pozostać w szkole, w której zwolniło się szybciej miej-
sce, czy czekać dłużej na zwolnienie się miejsc w innych, lepszych szkołach).
W roku 2003 ograniczono liczbę szkół, do których można było się zgłaszać
do trzech, a jednocześnie rozpoczęto wprowadzanie (w dużych miastach)
komputerowych systemów rekrutacji, które skutecznie rozwiązały większość
problemów związanych z niedoskonałościami mechanizmów rekrutacji.
Szkoły wyższe rozpoczęły rekrutację według nowego systemu w 2005
roku. Pojawiły się tutaj te same problemy, które można było zaobserwować
przy rekrutacji do szkół średnich w 2002 roku. Zgodnie z działającym do
tej pory systemem, kandydaci mogą składać podania jednocześnie na wiele
kierunków, w wyniku czego w pierwszym etapie rekrutacji bardzo często
dobrzy kandydaci dostają się na kilka kierunków, a słabsi na żaden. Kandy-
daci przyjęci na kilka kierunków stopniowo wycofują swoje zgłoszenia, a na
wolne miejsca dostajÄ… siÄ™ kandydaci z list oczekujÄ…cych. Uczelnie przeprowa-
dzają rekrutację w dwóch lub nawet trzech etapach. Rodzi to wiele proble-
mów organizacyjnych, a żadna uczelnia do końca nie wie, którzy z przyjętych
kandydatów podejmą naukę, a którzy w ostatniej chwili (nawet po rozpo-
częciu roku akademickiego) zrezygnują. Jednocześnie większość kandydatów
1
Informacje, które przedstawiam dotyczą szkół średnich w Poznaniu. W innych dużych
miastach systemy rekrutacji działały podobnie.
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół 37
trzymana jest przez długi czas w niepewności, nie wiedząc, gdzie w końcu
zostaną przyjęci (i czy w ogóle gdzieś zostaną przyjęci).
Podane przykłady pokazują, że tradycyjny, zdecentralizowany system re-
krutacji (tzn. taki, w którym każda szkoła samodzielnie przyjmuje kandyda-
tów) może działać w sposób bardzo nieefektywny, rodząc wiele uciążliwości
zarówno dla kandydatów, jak i dla szkół.
Gale i Shapley po przeczytaniu artykułu w New Yorkerze zaczęli zastana-
wiać się, czy możliwy jest sposób rekrutacji, który za jednym zamachem
likwidowałby te wszystkie problemy i który bez specjalnego zamieszania,
bez uciążliwości i niepewności automatycznie przydzielałby kandydatów do
szkół tak, aby w jak największym stopniu zaspokoić oczekiwania zarówno
kandydatów, jak i szkół (każdy kandydat chciałby się dostać do możliwie jak
najlepszej ze swojego punktu widzenia szkoły, a każda szkoła chciałaby
mieć jak najlepszych kandydatów).
Rozwiązanie, które znalezli autorzy artykułu [GS62] okazało się bardzo
proste, a jednocześnie matematycznie eleganckie. Wszystko sprowadza się
do odpowiedniego zdefiniowania przydziału optymalnego, a następnie wy-
kazania (za pomocą konstrukcji specjalnego algorytmu), że zawsze istnieje
dokładnie jeden przydział optymalny. Przedstawię teraz konstrukcję Gale a-
Shapleya.
2. Formalny model systemu rekrutacji. Zakładamy, że dany jest
skończony zbiór kandydatów K = {K1, K2, ..., Kn} i skończony zbiór szkół
S = {S1, S2, ..., Sm}2. Dla każdego kandydata Ki określony jest ostry liniowy
porzÄ…dek P (Ki) wzbiorze S odpowiadajÄ…cy jego preferencjom (tzn. kandy-
dat Ki jest w stanie ustawić wszystkie szkoły w kolejności od najlepszej do
najgorszej, przy czym żadne dwie różne szkoły nie mogą być tak samo do-
bre). Z kolei każda szkoła jest w stanie ustawić kandydatów w kolejności od
najlepszego do najgorszego, tzn. dla szkoły Sj w zbiorze K określony jest
ostry liniowy porzÄ…dek P (Sj)3.
Przy rekrutacji do szkół średnich lub wyższych w Polsce porządek P (Sj)
najczęściej wyznaczony jest za pomocą odpowiedniej punktacji (punkty
2
Pojęcie szkoły należy tutaj traktować bardzo szeroko. Szkołą może być kierunek
lub wydział na uczelni, może też być klasa o określonym profilu, do której prowadzona
jest osobna rekrutacja.
3
Często zakłada się (tak też zrobili Gale i Shapley [GS62]), że kandydat Ki określa
porzÄ…dek P (Ki) jedynie w pewnym podzbiorze S(Ki) zbioru S. Elementy zbioru S(Ki)
można interpretować jako szkoły akceptowalne przez Ki, tzn. takie, w których gotowy
jest on podjąć naukę. Założenie to jest bardzo naturalne, gdyż na ogół kandydaci składają
podania tylko do kilku wybranych szkół. Podobnie można zakładać, że preferencje szkół
są określone w pewnych podzbiorach zbioru K (każda szkoła może ustalić pewne wstępne
warunki, które musi spełnić kandydat chcący uczyć się w tej szkole). Podany tutaj model
można traktować jako model podstawowy. O różnych jego uogólnieniach będzie mowa
wp. 3.
38 Z. Åš w i t a l s k i
przyznawane są za wyniki testów gimnazjalnych, wyniki nowej matury
lub inne osiągnięcia kandydata)4. Zakładamy też, że każdy kandydat może
być przyjęty do co najwyżej jednej szkoły, a każda szkoła Sj może przyjąć
co najwyżej qj kandydatów (qj będę nazywał limitem szkoły Sj). Chcemy
znalezć przydział kandydatów do szkół tak, aby liczba kandydatów w szkole
Sj nie przekroczyła qj (przy czym niektórzy kandydaci być może nie znajdą
się w żadnej szkole). Używając języka teorii grafów możemy powiedzieć, że
szukamy grafu dwudzielnego łączącego zbiory wierzchołków K i S i takiego,
że każdy wierzchołek ze zbioru K ma stopień co najwyżej 1, a każdy wierz-
chołek Sj ze zbioru S stopień co najwyżej qj.
Aby zdefiniować pojęcie przydziału optymalnego warto posłużyć się nieco
prostszym modelem kojarzenia małżeństw, którym posługiwali się właśnie
Gale i Shapley. W modelu tym mamy n kobiet ze zbioru K = {K1, K2, ...,
Kn} i n mężczyzn ze zbioru M = {M1, M2, ..., Mn}. Każda kobieta porząd-
kuje mężczyzn w kolejności od najlepszego do najgorszego, a każdy męż-
czyzna określa kolejność zgodną ze swoimi preferencjami w zbiorze kobiet.
Chcemy utworzyć n par małżeńskich postaci KiMj (symbolem KiMj ozna-
czam parę nieuporządkowaną {Ki, Mj}). Szukamy więc skojarzenia5 zawie-
rającego n krawędzi w grafie dwudzielnym pełnym łączącym K i M (od-
wołując się do poprzedniego modelu można powiedzieć, że tutaj wszystkie
limity qj są równe 1).
Kluczowym pojęciem w teorii Gale a-Shapleya jest pojęcie przydziału
(lub skojarzenia) stabilnego. Dla danego skojarzenia s oznaczmy symbolem
s(Ki) męża kobiety Ki, a symbolems(Mj) żonę mężczyzny Mj.
Definicja 1 . Mówimy, że para KiMj blokuje skojarzenie s, jeśli kobieta
Ki woli mężczyznę Mj od swojego męża s(Ki), a mężczyzna Mj woli kobietę
Ki od swojej żony s(Mj).
Para blokująca dla s oczywiście nie może być parą małżeńską (zakła-
damy, że relacja x woli y jest antyzwrotna). Jest to para, w której kobieta
i mężczyzna mają się ku sobie chociaż nie są małżeństwem. Mężczyzni
i kobiety z takich par będą mieli tendencję do zdradzania swoich partnerów,
a więc każdy układ małżeństw zawierający pary blokujące może się szybko
rozsypać . Stabilność oznacza właśnie trwałość układu małżeńskiego, czyli
brak tendencji do rozsypywania się takiego układu. Naturalna jest wobec
tego następna definicja.
4
Założenie o liniowości porządku P (Sj) w tej sytuacji często nie będzie spełnione, gdyż
może się zdarzyć (i zdarza się), że niektórzy kandydaci będą mieli tę samą liczbę punktów
z testów. O modelach bez założenia liniowości preferencji zob. p. 3.
5
Skojarzenie to zbiór rozłącznych par nieuporządkowanych, w których pierwszy element
należy do K, a drugi do M.
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół 39
Definicja 2 . Mówimy, że skojarzenie s jest stabilne, jeśli s nie jest
blokowane przez żadną parę KiMj.
Rozważmy jako przykład zbiór K złożony z trzech pań: Agaty, Beaty
i Celiny oraz zbiór M złożony z trzech panów: Tadeusza, Witolda i Zbi-
gniewa. Załóżmy, że preferencje pań i panów są następujące:
A : TWZ T : CAB
B : TWZ W : ABC
C : WTZ Z : ACB
(Zapis A : TWZ oznacza, że Agacie najbardziej odpowiada Tadeusz, na
drugim miejscu stawia ona Witolda, a najmniej jej odpowiada Zbigniew
ciÄ…g TWZ nazywamy listÄ… preferencji Agaty; podobny sens majÄ… pozo-
stałe oznaczenia). Mamy w tym przypadku dokładnie 6 skojarzeń (tyle, ile
jest permutacji w zbiorze 3-elementowym). Aatwo można sprawdzić, że tylko
jedno z nich jest stabilne, a mianowicie s = {AW, BZ, CT } (Agata wycho-
dzi za Witolda, Beata za Zbigniewa, a Celina za Tadeusza). Zauważmy, że
gdyby Agata i Celina zamieniły się mężami, a więc gdybyśmy utworzyli
skojarzenie t = {AT, BZ, CW }, to obie panie skorzystałyby na tym (pano-
wie T i W oczywiście by stracili). Skojarzenie t nie daje jednak stabilnego
układu małżeństw (Beata woli Witolda od Zbigniewa, a Witold woli Beatę
od Celiny, a więc Beata i Witold blokują skojarzenie t).
Jeśli więc chcemy poszukiwać możliwie najkorzystniejszych rozwiązań
(przynajmniej dla którejś ze stron), to powinniśmy poruszać się tylko w zbio-
rze skojarzeń stabilnych. Zbiór ten często zawiera więcej niż jeden element
(na przykład gdyby w poprzednim przykładzie Beata zmieniła swoje prefe-
rencje na ZT W, to oba poprzednie skojarzenia, zarówno s, jak i t, byłyby
stabilne). Ma więc sens następująca definicja:
Definicja 3. Mówimy, że skojarzenie stabilne s jest optymalne dla
kobiet jeśli dla każdej kobiety Ki i dla dowolnego skojarzenia stabilnego
t zachodzi
(") s(Ki) >i t(Ki) lub s(Ki) =t(Ki)
(symbol >i oznacza tutaj relacjÄ™ preferencji dla kobiety Ki).
Inaczej mówiąc, skojarzenie optymalne jest, dla dowolnej kobiety, nie
gorsze od dowolnego skojarzenia stabilnego. Podobnie można zdefiniować
skojarzenie optymalne dla mężczyzn.
Aatwo zauważyć, że w każdym problemie kojarzenia może istnieć co naj-
wyżej jedno skojarzenie optymalne dla kobiet i co najwyżej jedno opty-
malne dla mężczyzn (na przykład w poprzednim przykładzie, przy preferen-
cjach Beaty zmienionych na ZT W skojarzenie t jest optymalne dla kobiet,
a s optymalne dla mężczyzn). Gale i Shapley udowodnili, że skojarzenia
40 Z. Åš w i t a l s k i
optymalne zawsze istnieją i że można je wyznaczyć za pomocą następują-
cego algorytmu (w podanym algorytmie, podobnie jak u Gale a-Shapleya
[GS62], stroną aktywną są mężczyzni otrzymamy w tej sytuacji rozwiąza-
nie optymalne dla mężczyzn; gdyby natomiast stroną inicjującą były kobiety,
to otrzymane rozwiązanie byłoby optymalne dla kobiet):
1. Każdy mężczyzna oświadcza się najlepszej kobiecie na swojej liście pre-
ferencji.
2. Jeśli którejś z kobiet oświadczył się więcej niż jeden mężczyzna, to ko-
bieta ta wybiera najlepszego z nich, a pozostałym odmawia.
3. Mężczyzni, których oświadczyny nie zostały przyjęte przez którąś z ko-
biet, skreślają tę kobietę ze swojej listy preferencji. Przechodzimy do
kroku 1.
Algorytm kończy się, gdy w którymś z etapów w kroku 1. wszyscy męż-
czyzni oświadczą się różnym kobietom. Musi to nastąpić po skończonej licz-
bie etapów, gdyż żaden mężczyzna nie może być odrzucony więcej niż n - 1
razy (gdyby mężczyzna był odrzucony n - 1 razy, to w ostatnim etapie
musiałby być przyjęty przez jedyną wolną kobietę, bo pozostałe byłyby za-
jęte ). Aatwo też zauważyć, że otrzymane skojarzenie s jest stabilne (gdyby
para KiMj była blokująca, to w którymś z kroków algorytmu Mj byłby od-
rzucony przez Ki bo Ki poprzedza s(Mj) na liście preferencji Mj a więc
mąż Ki musi być lepszy od Mj, a stąd para KiMj nie może być blokująca).
Dowód optymalności otrzymanego skojarzenia jest nieco dłuższy, ale rów-
nież elementarny [GS62].
Wróćmy teraz do modelu rekrutacji. Przyjmijmy dla uproszczenia, że
liczba kandydatów jest równa sumie wszystkich limitów (n = qj) oraz,
że w każdym przydziale wszystkie limity szkół są wyczerpane (tzn. każdy
kandydat znajdzie się w jakiejś szkole). Stabilność definiujemy tutaj ana-
logicznie jak dla małżeństw. Para KiSj blokuje przydział s jeśli kandydat
Ki woli szkołę Sj od tej, do której został przydzielony, a szkoła Sj woli
Ki od któregoś z przyjętych do niej kandydatów. Jeśli kandydaci są oce-
niani za pomocą punktacji z testów, to istnienie par blokujących oznacza,
że niektórzy kandydaci nie są przyjęci do szkół, w których mają punktację
wyższą od punktacji najgorszego przyjętego kandydata, mimo że woleliby
być w takiej szkole niż w tej, do której zostali przyjęci. System rekrutacji,
który dopuszczałby do takich sytuacji mógłby być uważany za ewidentnie
niesprawiedliwy.
Wśród przydziałów stabilnych zawsze istnieje dokładnie jeden optymalny
dla kandydatów (K-optymalny) i dokładnie jeden optymalny dla szkół
(S-optymalny). Przydział K-optymalny jest to taki przydział stabilny, który
jest dla wszystkich kandydatów lepszy (lub przynajmniej tak samo dobry)
niż wszystkie inne przydziały stabilne. Przydział optymalny można otrzy-
mać za pomocą algorytmu analogicznego do algorytmu kojarzenia mał-
żeństw. Zaczynamy od przydzielenia wszystkich kandydatów do najbardziej
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół 41
odpowiadających im szkół. W kolejnym kroku każda szkoła Sj tworzy ran-
king wszystkich kandydatów, którzy się do niej zgłosili i zostawia qj najlep-
szych, a pozostałych odrzuca. Kandydaci odrzuceni ze szkoły Sj wykreślają
jÄ… ze swojej listy preferencji i wszystko zaczyna siÄ™ od nowa. Otrzymujemy
w ten sposób przydział optymalny dla kandydatów.
Algorytm dający przydział optymalny dla szkół wyglądałby natomiast
następująco. Najpierw każda szkoła Sj przyjmuje qj najlepszych kandyda-
tów. Kandydaci, którzy dostali się do więcej niż jednej szkoły wycofują swoje
zgłoszenia ze wszystkich szkół oprócz najlepszej. Na wolne miejsca przyj-
mowani są kolejni kandydaci zgodnie z kolejnością na listach rankingowych
poszczególnych szkół. Procedura ta trwa tak długo, aż wszyscy kandydaci
zostaną przyjęci. Mniej więcej tak właśnie działa obecny system rekruta-
cji do szkół wyższych w Polsce, z zastrzeżeniem, że na początku kandydaci
składają podania nie do wszystkich, a tylko do wybranych szkół (a raczej
na kilka wybranych kierunków).
3. Rozwój teorii stabilnych skojarzeń. Artykuł Gale a i Shapleya
zapoczątkował burzliwy rozwój teorii i zastosowań modelu dwustronnych
skojarzeń. Prace poświęcone tej tematyce ukazują się głównie na łamach
czasopism matematycznych, informatycznych i ekonomicznych, ale intere-
sują się nią również specjaliści z wielu innych dziedzin (psychologii, socjolo-
gii, biologii, fizyki i innych). Opublikowano też 3 monografie poświęcone tej
problematyce ([GI89], [RS92], [Knu97]).
Badania teoretyczne można podzielić, z grubsza, na dwa nurty6. Nurt
pierwszy obejmuje analizę własności podstawowego modelu Gale a-Shap-
leya, szukanie jego powiązań z różnymi działami matematyki i analizę róż-
nych modyfikacji algorytmu GS (ewentualnie alternatywnych algorytmów
prowadzących do skojarzeń stabilnych). Nurt drugi (często inspirowany
przez potrzeby praktyki) zajmuje się analizą różnych uogólnień podstawo-
wego modelu GS (np. modyfikowane są założenia o preferencjach, limitach
itd.).
Do nurtu pierwszego zaliczyć można na przykład badanie struktury zbio-
ru skojarzeń stabilnych w modelu GS. W zbiorze tym, w oczywisty sposób,
można wprowadzić dwa naturalne porządki (skojarzenie s jest lepsze od sko-
jarzenia t dla kobiet, jeśli zachodzi ("), drugi porządek jest definiowany tak
samo, ale uwzględniamy mężczyzn). Okazuje się, że każdy z tych porząd-
ków wyznacza w zbiorze skojarzeń stabilnych strukturę kraty rozdzielnej
[Gal01]. Co więcej, dowolna skończona krata rozdzielna jest kratą skojarzeń
stabilnych w pewnym modelu GS [Bla84].
6
Oczywiście podział taki jest trochę nieprecyzyjny, gdyż w wielu publikacjach oba
nurty zazębiają się .
42 Z. Åš w i t a l s k i
Można się zastanawiać nad liczbą skojarzeń stabilnych w modelu GS.
Załóżmy, że mamy n kobiet i n mężczyzn i chcemy określić minimalną
i maksymalną liczbę skojarzeń stabilnych przy różnych układach preferen-
cji. Minimalna liczba jest równa 1 (jeśli np. wszystkie kobiety lub wszyscy
mężczyzni mają te same preferencje, to algorytm GS zarówno dla kobiet,
jak i dla mężczyzn, daje to samo rozwiązanie i łatwo udowodnić, że jest to
w tym przypadku jedyne rozwiÄ…zanie stabilne). Nie wiadomo natomiast w
jaki sposób zależy od n maksymalna liczba skojarzeń stabilnych problem
ten nie został do tej pory rozwiązany (zob. [Gal01]). Znane są jedynie wyniki
cząstkowe np. Irving i Leather [IL87] pokazali, że jeśli n jest potęgą 2, to
istnieje układ preferencji dający co najmniej 2n-1 skojarzeń stabilnych.
Ważną własnością rozwiązania Gale a-Shapleya jest tzw. niemanipulo-
walność (strategy-proofness). Załóżmy, że mamy zbiór kandydatów K i zbiór
szkół S oraz układ preferencji kandydatów i szkół P =(P (K1), ..., P (Kn),
P (S1), ..., P (Sm)). Załóżmy też, że określona jest jakaś metoda przyporząd-
kowująca każdemu układowi preferencji P skojarzenie s(P ). Metoda ta jest
manipulowalna, jeśli dla pewnego kandydata Ki istnieją preferencje P (Ki)
różne od P (Ki) i takie, że
("")[s(P )(Ki)] >i [s(P )(Ki)],
gdzie P jest układem powstałym z P przez zastąpienie P (Ki) przez P (Ki)
(symbol >i we wzorze ("") oznacza relację P (Ki)). Wzór ("") oznacza, że
szkoła, w której znalazł się kandydat Ki przy preferencjach P jest lepsza
(w sensie preferencji P (Ki)) od szkoły, w której znalazłby się on przy pre-
ferencjach P .
Interpretacja manipulowalności jest następująca. Zakładamy, że kandy-
dat Ki ma jakieÅ› prawdziwe preferencje P (Ki). PodajÄ…c preferencje P (Ki)
kandydat (przy założeniu, że wszyscy inni kandydaci podają preferencje
z układu P ) zostaje umieszczony w szkole s(P )(Ki). Kandydat Ki może
jednak próbować podać fałszywe preferencje P (Ki) licząc na to, że sko-
rzysta dzięki temu i znajdzie się w szkole lepszej niż s(P )(Ki), a mianowicie
w szkole s(P )(Ki) (lepszej z punktu widzenia oczywiście prawdziwych
preferencji P (Ki)). Jeśli jakiś system rekrutacji dopuszczałby taką sytuację,
to oznaczałoby to możliwość manipulowania preferencjami przez kandyda-
tów (niektórzy z nich mogliby podawać nieprawdziwe preferencje po to, aby
znalezć się w lepszej szkole od tej, w której mogliby się znalezć podając
swoje rzeczywiste preferencje). Chcielibyśmy, aby dobry system rekrutacji
był właśnie w tym sensie niemanipulowalny.
Okazuje się, że metoda Gale a-Shapleya jest niemanipulowalna, co wy-
kazali Dubins i Freedman w 1981 roku [DF81]7. Jest to jednak niemanipu-
lowalność tylko z punktu widzenia kandydatów. Roth [RS92] wykazał, że
7
Dubins i Freedman wykazali więcej, a mianowicie, że żadna koalicja kandydatów nie
może zmienić preferencji swoich uczestników tak, aby wszyscy oni mogli na tym skorzystać.
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół 43
nie istnieje metoda, która dawałaby rozwiązania stabilne, i która byłaby
niemożliwa do manipulacji przez wszystkich uczestników danego systemu
(a więc jeśli kandydaci nie mogą manipulować, to szkoły mogą i na odwrót).
Ciekawe powiązania metody GS z twierdzeniami o punkcie stałym (np.
twierdzeniem Tarskiego dla zbiorów częściowo uporządkowanych) podał Fle-
iner w pracy [Fle03].
W nurcie drugim mieści się wiele prac poświęconych różnym uogólnie-
niom metody GS. Zamiast preferencji w postaci liniowych porządków mo-
żemy dopuszczać w modelu preferencje uwzględniające równoważności mię-
dzy kandydatami (lub szkołami) (zob. [MIM02]). Bardzo ogólny model
otrzymujemy, przedstawiajÄ…c preferencje w postaci tzw. funkcji wyboru
(zob. [AG03], [Świ05]). Funkcja wyboru dla szkoły Sj jest to funkcja Cj :
(K) (K) ( (K) oznacza rodzinę podzbiorów zbioru K), która każ-
demu zbiorowi kandydatów L ‚" K przyporzÄ…dkowuje zbiór Cj(L) ‚" L.
Zbiór L możemy interpretować jako zbiór kandydatów, którzy zgłosili się
do szkoły Sj, a zbór Cj(L) jako zbiór kandydatów, których szkoła Sj wy-
brała ze zbioru L. Jeśli szkoła Sj ma preferencje P (Sj) oraz limit qj, to
zbiorem Cj(L) będzie po prostu zbiór qj najlepszych kandydatów ze zbioru
L lub cały zbiór L (jeśli w zbiorze L jest mniej niż qj kandydatów). Jeśli
szkoły stosują różne bardziej skomplikowane (i nie oparte o jednoznacznie
określony liniowy porządek) kryteria przyjęć, to zbiory Cj(L) mogą mieć
bardziej złożoną strukturę. Algorytm GS można w tym przypadku łatwo
uogólnić. Można też wprowadzić odpowiednie pojęcia rozwiązania stabil-
nego i optymalnego. Powstaje więc problem badania warunków, jakie należy
nałożyć na rodzinę funkcji wyboru {Cj} tak, aby uogólniony algorytm GS
dawał rozwiązania optymalne. Warunki takie zostały podane np. w pracach
[AG03], [Świ05] (przy różnych uogólnieniach pojęcia stabilności).
Inne uogólnienia otrzymamy jeśli uwzględnimy konieczność wspólnego
przyjmowania par małżeńskich (nie dotyczy to typowego systemu rekrutacji
kandydatów do szkół, ale ma bardzo ważne znaczenie w amerykańskim sys-
temie rekrutacji kandydatów na staże medyczne w szpitalach znanym pod
nazwÄ… NRMP8 zob. [RS92]) lub dolne limity liczby przyjmowanych kan-
dydatów (tzn. jeśli np. przyjmujemy założenie, że określona jest minimalna
liczba kandydatów, przy której dana szkoła zostanie uruchomiona (dany
kierunek na uczelni zostanie otwarty). Algorytmy dla zadania z dolnymi li-
mitami były przedstawione w pracy [ADG03] (inspiracją dla autorów tej
8
System ten działa od lat 50. ubiegłego wieku pod nazwą NIMP (National Intern
Matching Program), a obecnie NRMP (National Resident Matching Program). Jest to
najbardziej znany scentralizowany system rekrutacji. W jego udoskonalaniu istotny udział
mieli matematycy i ekonomiści zajmujący się teorią dwustronnych skojarzeń (m.in. Alvin
Roth z Uniwersytetu Harvarda). Informacje na jego temat można znalezć w książce [RS92],
a także na stronie www.nrmp.org.
44 Z. Åš w i t a l s k i
pracy była konieczność opracowania komputerowego systemu przyjęć stu-
dentów na specjalności na Wydziale Zarządzania AE w Poznaniu).
4. Zastosowania. Teoria Gale a-Shapleya jest stosowana do modelowa-
nia różnego rodzaju zjawisk ekonomicznych ([KC82], [CK81]), społecznych
([Had99], [FQ05]) czy biologicznych ([BR00]). Ma również wiele zastosowań
bardziej praktycznych związanych głównie z analizą i doskonaleniem istnie-
jących oraz konstruowaniem nowych systemów rekrutacji ([CS06], [ES06]).
Alvin Roth poświęcił wiele swoich prac analizie różnych funkcjonujących
w USA i Wielkiej Brytanii systemów rekrutacji, badając m.in. stabilność
i niemanipulowalność tych systemów ([Rot84], [Rot91], [MR91]). Badania te
byłyby oczywiście niemożliwe bez narzędzi teoretycznych wypracowanych
przez teorię dwustronnych skojarzeń. Uczestniczył on również jako ekspert
w doskonaleniu systemu NRMP. Z drugiej strony, potrzeby praktyki istotnie
wpływają na rozwój badań teoretycznych. Na przykład konieczność uwzględ-
nienia potrzeb par małżeńskich chcących uczestniczyć w systemie NRMP
zainspirowała wiele badań teoretycznych dotyczących kojarzenia z uwzględ-
nieniem wspólnych preferencji dla par (zob. [AC96], [KK02]).
5. Podsumowanie. W artykule starałem się wykazać, że problematyka
dwustronnych skojarzeń jest, z jednej strony, bardzo ciekawa teoretycznie,
a z drugiej bardzo silnie zwiÄ…zana z konkretnymi potrzebami praktyki.
Można się spodziewać jej dalszego rozwoju w miarę rozpowszechniania się
różnego rodzaju komputerowych systemów kojarzenia (w szczególności opar-
tych o komunikacjÄ™ internetowÄ… zob. np. [GN01]).
Główną zasługą Gale a i Shapleya jest precyzyjne, matematyczne ujęcie
problemu rekrutacji. Podstawowym, wykorzystywanym przez nich pojęciem
jest pojęcie przydziału (skojarzenia) stabilnego. Gale i Shapley pokazali jak
wśród przydziałów stabilnych poszukiwać przydziałów, które są korzystne
dla kandydatów i takich, które są korzystne dla szkół. Z ich teorii wynika
też, jakie cechy powinien posiadać dobry system rekrutacji powinien on
mianowicie nie tylko gwarantować stabilność (optymalność) otrzymanego
przydziału, ale również uniemożliwiać manipulowanie preferencjami (przy-
najmniej przez jednÄ… ze stron).
Teoria dwustronnych skojarzeń stała się silną inspiracją do badania i do-
skonalenia istniejących, a także tworzenia nowych systemów rekrutacji
(główne zasługi położył tu Alvin Roth z Uniwersytetu Harvarda).
Myślę, że również w Polsce warto byłoby pokusić się o próbę stworzenia
centralnego systemu rekrutacji do szkół wyższych. System taki byłby znacz-
nym ułatwieniem zarówno dla kandydatów, jak i dla szkół. Istniejąca teoria,
jak i doświadczenia funkcjonujących już systemów (np. NRMP) mogłyby
znacznie ułatwić wdrażanie takiego systemu.
O kojarzeniu małżeństw i rekrutacji kandydatów do szkół 45
Warto na zakończenie zwrócić uwagę na walory dydaktyczne teorii Ga-
le a-Shapleya. Podstawowy model tej teorii jest bardzo elementarny i bez
problemów mógłby być prezentowany uczniom szkół średnich, a nawet pod-
stawowych. Ciekawe są w tym kontekście dwa ostatnie akapity z pracy
[GS62], w których autorzy przedstawiają swoje twierdzenie o istnieniu sko-
jarzenia stabilnego i jego konstruktywny dowód (polegający na konstrukcji
właśnie algorytmu GS) jako przykład matematyki bez liczb i wzorów .
Tego rodzaju przykłady mogą być, według Gale a i Shapleya, argumentami
na rzecz tezy, że matematyka jest bardziej sztuką rozumowania niż sztuką
obliczeń, czy też listą wzorów do zapamiętania. Aatwiej więc mogą zachęcić
do matematyki wszystkich tych (w szczególności uczniów), których zniechęca
tradycyjny sposób nauczania tego przedmiotu.
Literatura
[AC96] B. Al de r s ho f, O.M. Ca r duc c i, Stable matchings with couples, Discrete
Applied Mathematics, 68 (1996), 203 207.
[ADG03] M. A n h o l c e r, W. D y m o w s k i, M. G o d l e w s k i, Optymalny przy-
dział studentów do specjalności jako wariant zagadnienia doboru małżeństw, w:
Metody i zastosowania badań operacyjnych 2002 (red. A. C a ł c z y ń s k i ),
Wyd. Politechniki Radomskiej, Radom, 2003, 31 42.
[AG03] A. A l k a n, D. G a l e, Stable schedule matching under revealed preference,
Journal of Economic Theory, 112 (2003), 289 306.
[Bla84] C. B l a i r, Every Finite Distributive Lattice is a Set of Stable Matchings, Jo-
urnal of Combinatorial Theory (A), 37 (1984), 353 356.
[BR00] C.T. B e r g s t r o m, L.A. R e a l, Toward a theory of mutual mate choice:
Lessons from two-sided matching, Evolutionary Ecology Research, 2 (2000), 493
508.
[CK81] V.P . Cr a wf or d, E.M. Knoe r, Job matching with heterogeneous firms and
workers, Econometrica, 49 (1981), 437 450.
[CS06] Y. C h e n, T. S önme z, School choice: an experimental study, Journal of
Economic Theory, 127 (2006), 202 231.
[DF81] L.E. Dubi ns, D.A. Fr e e dma n, Machiavelli and the Gale-Shapley algo-
rithm, American Mathematical Monthly, 88 (1981), 485 494.
[ES06] H. E r g i n, T. S önme z, Games of school choice under the Boston mecha-
nism, Journal of Public Economics, 90 (2006), 215 237.
[Fle03] T. F l e i n e r, A fixed-point approach to stable matchings and some applica-
tions, Mathematics of Operations Research, 28 (2003), 103 126.
[FQ05] M. Fa f c ha mps, A. Qui s umbi ng, Assets at marriage in rural Ethio-
pia, Journal of Development Economics, 77 (2005), 1 25.
[Gal01] D. G a l e, The two-sided matching problem. Origin, development and current
issues, International Game Theory Review, 3 (2001), 237 252.
[GI89] D. G u s f i e l d, R.W. I r v i n g, The Stable Marriage Problem: Structure and
Algorithms, MIT Press, Cambridge, MA, 1989.
[GN01] W.R. G a t e s, M.E. N i s s e n, Designing Agent-Based Electronic Employ-
ment Market, Electronic Commerce Research, 1 (2001), 239 263.
46 Z. Åš w i t a l s k i
[GS62] D. Ga l e, L.S. Sha pl e y, College Admissions and the Stability of Marriage,
American Mathematical Monthly, 69 (1962), 9 15.
[GI89] D. G u s f i e l d, R.W. I r v i n g, The Stable Marriage Problem: Structure and
Algorithms, MIT Press, Cambridge, MA, 1989.
[Had99] G.K. H a d f i e l d, A coordination model of the sexual division of labor, Journal
of Economic Behavior and Organization 40 (1999), 125 153.
[IL87] R.W. I r v i n g, P . L e a t h e r, The Complexity of Counting Stable Marriages,
SIAM Journal of Computing, 15 (1987), 532 543.
[Kas07] A. K a s z k o w i a k, Sprawiedliwa rekrutacja, Delta, 2 (2007), 5 6.
[KC82] A.S. K e l s o, V.P. C r a w f o r d, Job matching, coalition formation and gross
substitutes, Econometrica, 50 (1982), 1483 1504.
[KK02] B. Kl a us, F. Kl i j n, Stable matchings and preferences of couples, Journal
of Economic Theory, 121 (2005), 75 106.
[Knu97] D.E. K n u t h, Stable Marriage and Its Relation to other Combinatorial Pro-
blems. An Introduction to the Mathematical Analysis of Algorithms, American
Mathematical Society, Providence, Rhode Island, 1997.
[MIM02] D.F. Ma nl ove, R.W. I r vi ng, K. I wa ma, S. Mi yaz a ki, Y. Mo -
r i t a, Hard variants of stable marriage, Theoretical Computer Science, 276
(2002), 261 279.
[MR91] S. M o n g e l l, A.E. R o t h, Sorority Rush as a Two-Sided Matching Mecha-
nism, The American Economic Review, 81 (1991), 441 464.
[Paw00] J. P a w ł o w s k i, Żeby w wyniku naboru nikt nie poczuł się nabrany . Ro-
dzicielskie refleksje po egzaminach do szkół średnich, Biuletyn Informacyjny. In-
formatyka dla szkoły, 31 (2000) ().
[Rot84] A.E. R o t h, The Evolution of the Labor Market for Medical Interns and Resi-
dents: A Case Study in Game Theory, Journal of Political Economy, 92 (1984),
991 1016.
[Rot91] A.E. R o t h, A Natural Experiment in the Organization of Entry-Level La-
bor Markets: Regional Markets for New Physicians and Surgeons in the United
Kingdom, The American Economic Review, 81 (1991), 415 440.
[RS92] A.E. R o t h, M.A. S o t o m a y o r, Two-sided matching. A study in game-
theoretic modeling and analysis, Cambridge University Press, 1992.
[Świ05] Z. Ś w i t a l s k i, Optymalny system rekrutacji kandydatów do szkół, Badania
Operacyjne i Decyzje, 3 4 (2005), 85 98.
Summary
In the paper we describe the model of Gale and Shapley concerning marriage mat-
chings and college admissions (American Mathematical Monthly, 69 (1962), 9 15). We
review some results and applications of the Gale-Shapley theory. We also analyze pro-
blems of recruitment of candidates to schools in Poland from the point of view of this
theory.
Zbigniew Åšwitalski
Wydział Matematyki, Informatyki i Ekonometrii
Uniwersytet Zielonogórski
ul. Szafrana 4a, 65-516 Zielona Góra
e-mail: Z.Switalski@wmie.uz.zgora.pl
Wyszukiwarka
Podobne podstrony:
function cpdf set viewer preferencesśruba dwustronnaModele preferencji optymalizacja wielokryterialnaPreferences08 Fontsfunction cpdf set viewer preferencesPreferowane hipermarkety przez studentów Uniwersytetu JagiellońskiegoPreferences07 FileTypesfunction mb preferred mime namepreferenceswd2 7 preferencjePreferences03 BootPreferences16 ScrollBarPreferences02?ckgroundsPreferences12 Mouse(Irak UE) Nie będzie preferencji dla irackich chrześcijanwięcej podobnych podstron