MPaR'08 - artykuł nr 7
O pewnym algorytmie poszukiwania stabilnych skojarzeń
Zbigniew Świtalski
Streszczenie:
Poszukiwanie stabilnych skojarzeń jest ważnym problemem praktycznym związanym z optymalizacją systemów rekrutacji (kandydatów do szkół, pracowników do firm itp.). Najbardziej znaną metodą rozwiązującą to zagadnienie jest algorytm Gale'a-Shapleya. W artykule A Non-constructive Elementary Proof of the Existence of Stable Marriages ("Games and Economic Behavior" 13(1996), 135-137) Marilda Sotomayor przedstawiła "niekonstruktywny" dowód istnienia stabilnych skojarzeń w modelu Gale'a-Shapleya. W pracy O pewnym algorytmie poszukiwania stabilnych skojarzeń (Z. Świtalski) pokazano, że dowód Sotomayor zawiera w niejawnej postaci pewien algorytm podobny do algorytmu G-S. Porównano oba algorytmy i rozważono możliwość uogólnienia algorytmu Sotomayor na przypadek skojarzeń dwustronnych typu "many-to-many" oraz skojarzeń wielostronnych.
Nota bibliograficzna:
Zbigniew Świtalski. (2008). O pewnym algorytmie poszukiwania stabilnych skojarzeń. W: Tadeusz Trzaskalik (red.), Modelowanie Preferencji a Ryzyko '08. Wydawnictwo Akademii Ekonomicznej im. Karola Adamieckiego w Katowicach, s. 101-112
