Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
ROZWIĄZANIASTABILNE…
19
Jakłatwosprawdzić,przydział{(Wl,ml,cl),(W2,m2,c2)}blokowany
jestprzeztrójkę(Wl,m2,cl),przydział{(Wl,m2,cl),(W2,ml,cl)}przeztrójkę
(W2,m2,c2),adwapozostałeprzydziałyprzeztrójkę(W2,ml,cl).
Jednymzgłównychproblemówstojącychprzedbadaczamijestpodanie
warunkówkoniecznychiwystarczającychistnieniaprzydziałustabilnego.
Dotejporyukazałosiękilkaprac,wktórychbadanowarunkiwystarczające.
Wszczególnościanalizowanozagadnieniaprzydziałuzcyklicznymipreferen-
cjami.ProblemzostałpostawionyprzezKnuthaw[8],anastępniebadany,
międzyinnymiprzezBorosaiinnych([2],dowódistnieniastabilnychprzy-
działówdlaściślecyklicznych,niekonieczniesilnych,relacjipreferencji,gdy
n≤k),Erikssonaiinnych([4],ściślecyklicznepreferencje,n=4,k=3),
Huanga([6],aspektyalgorytmiczneizwiązanezezłożonościąproblemu)oraz
BiróiMcDermida([1],złożoność).
PewienspecyficznytyppreferencjirozpatrywanyjestprzezDanilova
w[3].Autordefiniujepreferencjeleksykograficzne,czylitakie,żekażdymęż-
czyznajestzainteresowanyprzedewszystkimwyboremkobietyiviceversa
(oczywiściekażdyzezbiorówWiMmożebyćzastąpionyprzezzbiórC).Niżej
przeanalizujemyukładypreferencji,wktórympreferencjejednejzegrupmuszą
coprawdapozostaćleksykograficzne,jednakniemusządotyczyćtylkojednego
zpozostałychpodzbiorów.
2.Nowywynik
Głównymrezultatemprezentowanymwniniejszymartykulejestnastępu-
jącetwierdzenie,nawiązującedowynikuzpracy[3].
Twierdzenie1
Niechdanebędzietrójstronnezagadnienieprzydziału.Załóżmy,żespeł-
nionesąwarunki
1.Każdymężczyznam∈Mmarelacjępreferencji≻m
⋆określonąnazbi-
orzeW,ajegorelacjapreferencji≻mspełniawarunek
Wl≻m
⋆W2⇒(Wl,c)≻m(W2,c),
dlaWl,W2∈W,c∈C
czylijestzainteresowanyprzedewszystkimwyboremkobiety,awybórkotajest
drugorzędny.
2.Każdykotc∈Cmarelacjępreferencji≻c
⋆określonąnazbiorzeW,
ajegorelacjapreferencji≻cspełniawarunek
Wl≻c
⋆W2⇒(Wl,m)≻c(W2,m),
dlaWl,W2∈W,m∈M
czylijestzainteresowanyprzedewszystkimwyboremkobiety,awybór
mężczyznyjestdrugorzędny.
