Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
MarcinAnholcer
UniwersytetEkonomicznywPoznaniu
ROZWIĄZANIASTABILNEWTRÓJSTRONNYM
ZAGADNIENIUPRZYDZIAŁU
Wprowadzenie
W1962rokuGaleiShapleywpracy[5],analizującproblemprzydziału
kandydatówdoszkół,sformułowalidwustronnezagadnienieprzydziału.
Wzagadnieniutymwystępujądwan-elementowezbiory:kobietWimężczyzn
M.KażdakobietaW∈Wmaokreślonąrelacjęsilnejpreferencji≻wnazbiorze
M(przytymzapisml≻wm2oznacza,żekobietawwolimężczyznęm1
odmężczyznym2),zaśkażdymężczyznam∈Manalogicznieokreślonąrelację
silnejpreferencji≻mnazbiorzeM.Przydziałemnazywamyfunkcję
#:W∪M→W∪M
taką,że
#(W)∈M,
#(m)∈W,
dlaW∈W
(1)
dlam∈M
(2)
#(m)=W⟺#(W)=m,
dlaW∈W,m∈M
(3)
Parablokującaprzydział#topara(w,m),dlaktórejzachodząwarunki
m≻w#(W)
W≻m#(m)
(4)
(5)
GaleiShapleywykazali,żedlakażdegoukładupreferencjiistnieje
przydziałstabilny,tzn.taki,wktórymniewystępujeżadnaparablokująca.
Problembyłanalizowanyiuogólnianynaróżnesposoby.Dośćdokładny
przeglądwynikówzwiązanychztymzagadnieniemmożnaznaleźćwprze-
glądowejpracyIwamyiMiyazakiego[7].
