Устойчивость для пар в задаче стабильного соответствия

В проблеме устойчивого сопоставления утверждается, что могут существовать случаи, когда список людей может быть доволен своими решениями, но список не может быть, когда алгоритм запускается с предложениями мужчин. $m$ $f$

Из того, что я прочитал, нестабильное совпадение происходит, когда и предпочитают друг друга своим текущим партнерам. $m$ $f$

Я немного растерялся в определении стабильного соответствия для этого случая. Я собираюсь просмотреть слайды здесь .

Является ли пара стабильной, пока мужчины довольны, даже если предпочтения женщины не совпадают? $(m, f)$

combinatorics phwd
источник

«Мужчины довольны» - это немного искажение. Если мы запустим алгоритм Гейла-Шепли, который предлагают мужчины, мы получим «оптимальное для мужчин» стабильное сопоставление. Это совпадение, которое лучше всего подходит для набора мужчин среди всех стабильных совпадений. Но это не значит, что каждый человек соответствует своему первому выбору. Некоторые из них все еще хотели бы поменяться, если бы могли; просто никто из их фаворитов не захочет с ними переключаться. И некоторые женщины могут быть сопоставлены с их первым выбором, просто это не обязательно является лучшим стабильным соответствием для женщин в целом.

Усул

Ответы:

Да, это стабильно. Не нужно назначать оптимальный выбор для обеих сторон. Чтобы разорвать брак, нужны две добровольные партии, несчастье одной стороны в браке не делает его нестабильным.

Кава
источник

Хорошо, теперь я все перечитал. Столь стабильное сопоставление здесь, когда мужчины предлагают, допускает только оптимальный выбор с мужчинами, в частности, «оптимальность для мужчин», как указано на слайдах, поэтому пары, где женщины получают наилучшие предпочтения, никогда не приходят в этот алгоритм, а только в версии, где женщины те, чтобы предложить. Я думаю, что обернул голову вокруг стабильного соответствия сейчас.

phwd