Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZWIĄZANIASTABILNE…
21
Załóżmy,żetrójkablokującaistniejeijestnią(w,m,c).Załóżmyponad-
to,że#(W)=(ml,cl),#(m)=(W2,c2),#(c)=(W3,m3).Przyjmijmy,
żeW∈WM(zewzględunasymetrięrozpatrywanegoproblemudowóddla
W∈WCmożezostaćpominięty).Możezajśćjedenzdwóchprzypadków.
1)ml≠m,awięcrównieżW2≠W.Oznaczałobytojednak,że
W2≻m
⋆Wiml≻w
Mm,cobyłobysprzecznezestabilnościączęściowego
przydziału#l,
2).ml=m,awięcrównieżW2=W.Oznaczałobytojednak,żec≻w
lcl
oraz(m,W)≻c
⋆(m3,W3),cobyłobysprzecznezestabilnościączęściowego
przydziału#l
⋆.
Ponieważwobuprzypadkachotrzymaliśmysprzeczność,parablokująca
niemożeistnieć.Tokończydowód,gdyżzewzględunasymetriędefiniowa-
negozagadnieniaanalizaprzypadkuW∈WCprzebiegaanalogicznie.
Podsumowanie
Wpracyzdefiniowanazostałanowarodzinatrójstronnychzagadnień
przydziału,dlaktórychistniejąprzydziałystabilne.Rodzinatajestróżnaod
zdefiniowanychwcześniej,choćprzedstawionyrezultatnawiązujewyników
zawartychwpracyDanilova[3].
Wdalszychbadaniachwartosięskoncentrowaćnapróbieuogólnienia
otrzymanegowynikunaproblemywielostronne(k>3).
Literatura
1.BiróP.,McDermidE.(2010).Three-SidedStableMatchingswithCyclicPre-
ferences.Algorithmica,58,s.5-18.
2.BorosE.,GurvichV.,JaslarS.,KrasnerD.(2004).StableMatchingsinThree-sided
SystemswithCyclicPreferences.DiscreteMathematics,289,s.1-10.
3.DanilovV.I.(2003).ExistenceofStableMatchingsinSomeThree-SidedSystems.
MathematicalSocialSciences,46,s.145-148.
4.ErikssonK.,SjöstrandJ.,StrimlingP.(2006).Three-dimensionalStableMatching
withCyclicPreferences.MathematicalSocialSciences,52,s.77-87.
5.GaleD.,ShapleyL.S.CollegeAdmissionsandtheStabilityofMarriage.Am.Math.
Mon.,69,s.9-15.
6.HuangC.-C.(2010).CircularStableMatchingand3-wayKidneyTransplant.Algo-
rithmica,58,s.137-150.
