Stabilność dla par w problemie ze stabilnym dopasowaniem

W Stable Matching Problem stwierdzono, że mogą istnieć przypadki, w których lista mężczyzn może być zadowolona z ich decyzji, ale lista nie może, gdy algorytm jest uruchamiany z propozycjami mężczyzn. $m$ $f$

Z tego, co przeczytałem, niestabilne dopasowanie występuje, gdy i wolą się od swoich obecnych partnerów. $m$ $f$

Jestem trochę zagubiony w definicji Stabilnego Dopasowywania w tym przypadku. Idę tutaj po slajdach .

Czy para stabilna, dopóki mężczyźni są zadowoleni, mimo że preferencje kobiety nie zostały dopasowane? $(m, f)$

combinatorics

— phwd
źródło

„Mężczyźni są zadowoleni” to trochę zniekształcenie. Jeśli uruchomimy algorytm Gale-Shapleya, w którym proponują to mężczyźni, otrzymamy stabilne dopasowanie „optymalne dla mężczyzn”. Jest to dopasowanie, które jest ogólnie najlepsze dla zestawu mężczyzn spośród wszystkich stabilnych dopasowań. Ale to nie znaczy, że każdy człowiek jest dopasowany do swojego pierwszego wyboru. Niektórzy z nich nadal chcieliby się zmienić, jeśli mogli; po prostu żaden z ich ulubionych nie chciałby się z nimi zamienić. I niektóre kobiety mogą być dopasowane do ich pierwszych wyborów, niekoniecznie jest to najlepsze stabilne dopasowanie dla kobiet ogólnie.

— usul

Tak, jest stabilny. Nie musi przypisywać optymalnych wyborów dla obu stron. Aby zerwać małżeństwo, potrzebujesz dwóch chętnych stron, nieszczęście jednej strony małżeństwa nie powoduje tutaj niestabilności.

— Kaveh
źródło

Ok, przeczytałem wszystko teraz. Tak stabilne dopasowanie tutaj, gdy mężczyźni proponują, pozwala tylko na optymalne wybory z mężczyznami konkretnie „Optymalność mężczyzny”, o których mowa w slajdach, więc pary, w których kobiety mają najlepsze preferencje, nigdy nie pojawiają się w tym algorytmie, ale tylko w wersji, w której kobiety są te do zaproponowania. Chyba owinęłam teraz głowę stabilnym dopasowaniem.

— phwd,