Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
20
MarcinAnholcer
3.ZbiórkobietWmożnapodzielićnadwapodzbioryWMiWC,przy
czymkobietyW∈WMsązainteresowaneprzedewszystkimwyborem
mężczyzny,zaśW∈WC–kota,czyliW∈WMmająrelacjepreferencji≻w
M
zdefiniowanenazbiorzeMtakie,że
ml≻w
Mm2⇒(ml,c)≻w(m2,c),
dlaml,m2∈M,c∈C
zaśW∈WCrelacjepreferencji≻w
CzdefiniowanenazbiorzeCtakie,że
cl≻w
Cc2⇒(cl,m)≻w(c2,m),
dlacl,c2∈C,m∈M
Wówczasistniejeprzydziałstabilny.
Dowód
Dowódzaczniemyodkonstrukcjiprzydziału,anastępniewykażemy,
żejestonstabilny.Wykorzystamyprzytymkilkakrotnietwierdzenieoistnieniu
przydziałustabilnegowdwustronnymzagadnieniuprzydziału.
Niech|WM|=nl,i|WC|=n2(oczywiścienl+n2=n).Bazującna
relacjach≻m
⋆
i≻w
Mtworzymy#l–częściowyprzydziałstabilnyelementów
zbioruWMin1spośródelementówzbioruM(oznaczmyichzbiórprzezM1,
azbiórpozostałychn2elementówzbioruMprzezM2).Podobnie,bazującna
relacjach≻c
⋆i≻w
Ctworzymyczęściowyprzydziałstabilny#2wszystkichele-
mentówzbioruWCin2elementówzbioruC(oznaczmyichzbiórprzezC2,
azbiórpozostałychn1elementówzbioruCprzezC1).Powstałewtensposób
paryuzupełniamydokompletnychtrójekwsposóbopisanyponiżej.
Rozpocznijmyodpar(w,c),gdzieW∈WC,c∈C2.Dlakażdejkobiety
W∈WC,poustaleniuc∈C2,obcięcierelacji≻wjestrelacjąokreślonąna
zbiorzeM(oznaczmyjąprzez≻w
2).Przypisujemytakzdefiniowanerelacje
parom(w,c).Jednocześniezauważmy,żezewzględunauprzedniepołączenie
W∈WCic∈C2wpary,obcięciekażdejzrelacji≻mdlam∈M2definiujeten
samporządek,corelacja≻m
⋆.Dołączamydokażdejzparelementym∈M2
wtakisposób,abypowstałyczęściowyprzydział#2
⋆par(traktowanychjakpo-
jedynczeelementy)ielementówm∈M2byłstabilnyzewzględunarelacje
≻w
2i≻m
⋆.
Analogiczniepostępujemywprzypadkupar(w,m),gdzieW∈WM,
m∈Ml.DlakażdejkobietyW∈WM,poustalenium∈Ml,definiujemyrelacje
≻w
lanalogicznie,jakwpoprzednimprzypadku≻w
2,iprzypisujemyjeparom
(w,m).Podobniejakwyżej,dołączamydokażdejzparelementyc∈Clwtaki
sposób,abypowstałyczęściowyprzydział#l
⋆par(traktowanychjakpojedyncze
elementy)ielementówc∈Clbyłstabilnyzewzględunarelacje≻w
li≻c
⋆.
Pokażemy,żewtakzdefiniowanymprzydziale#niemożeistniećtrójka
blokująca,awięcmusibyćstabilny.
