Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
18
MarcinAnholcer
1.Trójstronnezagadnienieprzydziału
Jednymzuogólnieńomawianegoproblemujestwielostronnezagadnienie
przydziału,wktórymwmiejscedwóchzbiorówWiMrozpatrujemywiększą
ichliczbę(powiedzmykzbiorów),apreferencjesązdefiniowanenienazbiorze
pojedynczychelementów,aleichuporządkowanych(k–1)-tek.Wszczegól-
nościrozpatrywanejesttrójstronnezagadnienieprzydziału(k=3),wktórym
trzecizbióroznaczanyjestwliteraturzenp.jakozbiórdzieciC,psówD
albokotówC.Wdalszejczęścipracyposługiwaćsiębędziemyostatnimzwy-
mienionychoznaczeń,używanymnp.wpracy[2].Trójstronnezagadnienie
przydziałumożemywówczaszdefiniowaćwnastępującysposób.
Danesątrzyn-elementowezbiory:kobietW,mężczyznMikotówC.
KażdakobietaW∈Wmaokreślonąrelacjęsilnejpreferencji≻wnazbiorze
M×C,każdymężczyznam∈Manalogicznieokreślonąrelacjęsilnejpre-
ferencji≻mnazbiorzeW×C,akażdykotc∈C–relacjęsilnejpreferencji≻c
nazbiorzeW×M.Przydziałemnazywamyfunkcję
#:W∪M∪C→(W×M)∪(W×C)∪(M×C)
taką,że
#(W)∈M×C,
dlaW∈W
(6)
#(m)∈W×C,
dlam∈M
(7)
#(c)∈W×M,
dlac∈C
(8)
#(m)=(m,c)⇔#(m)=(W,c)⇔#(c)=(W,m)
(9)
dlaW∈W,m∈M,c∈C
Trójkablokującaprzydział#totrójka(w,m,c),dlaktórejzachodzą
warunki
(m,c)≻w#(W)
(10)
(W,c)≻m#(m)
(11)
(W,m)≻c#(c)
(12)
Wprzeciwieństwiedodwustronnegozagadnieniaprzydziału,zagadnienie
trójstronne(aniogólniejwielostronne)niemusiposiadaćprzydziałustabilnego.
Przykładtakiegozagadnieniapodanyzostałwpracy[2].Niechn=2,
W={w1,w2},M={m1,m2},C={c1,c2},zaśpreferencjesąpostaci
(m2,c2)≻w
1
(m2,cl)≻w
1
(ml,cl)≻w
1
(ml,c2)
(m2,c2)≻w
2
(ml,cl)≻w
2
(m2,cl)≻w
2
(ml,c2)
(W2,cl)≻m
1
(Wl,c2)≻m
1
(W2,c2)≻m
1
(Wl,cl)
(W2,cl)≻m
2
(Wl,cl)≻m
2
(W2,c2)≻m
2
(Wl,c2)
(W2,ml)≻c
1
(Wl,m2)≻c
1
(Wl,ml)≻c
1
(W2,m2)
(Wl,ml)≻c
2
(W2,ml)≻c
2
(W2,m2)≻c
2
(Wl,m2)
