В следующем отрывке из книги Джона Кляйнберга и Евы Тардос Разработка алгоритма
(1.8) В стабильном сопоставлении $ S * каждая женщина сопоставляется со своим худшим действительный партнер.
Доказательство. Предположим, что существует пара $ (m, w) $ в $ S * $ такая, что m не является худшим действительным партнером $ w $. Тогда существует стабильное соответствие $ S '$, в котором $ w $ находится в паре с мужчиной $ m' $, который ей нравится меньше $ m. $ В $ S '$ m находится в паре с женщиной $ w / neq w $; поскольку w - лучший допустимый партнер для $ m, $ и $ w $ '- допустимый партнер для m, мы видим, что m предпочитает $ w $, а не $ w'. $
Но из этого следует, что $ (m, w) $ - это нестабильность в $ S '$, что противоречит утверждению, что $ S' $ стабильно и, следовательно, противоречит нашему первоначальному предположению
Я не понимаю, как $ (m, w) $ - нестабильность $ S '$. Если $ m $ предпочитает $ w $ вместо $ w '$, а $ w' $ также предпочитает $ m $, почему это не СТАБИЛЬНО? Тогда я немного смущен тем, как это доказывает утверждение, что каждому w соответствует наихудшее действительное совпадение.