Все выполнения приводят к одному паросочетанию

Существует много разных способов доказательства подобных утверждений, не- редко требующих довольно сложной аргументации. Как выясняется, самый простой и наиболее содержательный метод заключается в том, чтобы уникальным образом охарактеризовать полученное паросочетание, а потом показать, что все выполнения приводят к паросочетанию, обладающему такой характеристикой.

Что же это за характеристика? Мы покажем, что каждый мужчина в конечном итоге оказывается «лучшим из возможных партнеров» в конкретном смысле. (Вспомните, что это утверждение истинно, если все мужчины предпочитают разных женщин.)

Пусть S* обозначает множество пар {(m, best(m)):m Ѯ M}. Докажем следующий факт:

(1.7) Каждое выполнение алгоритма Гейла–Шепли приводит к множеству S*.

Это утверждение выглядит удивительно сразу на нескольких уровнях. Прежде всего, в его текущей формулировке не существует причины полагать, что S* во- обще является паросочетанием, не говоря уже об устойчивости. В конце концов, почему у двух мужчин не может быть единого лучшего действительного партнера?

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

Но, несмотря на все, доказать его не так уж сложно.

Доказательство. Пойдем от обратного: предположим, что некоторое выпол- нение  алгоритма Гейла–Шепли порождает паросочетание S, в котором некий мужчина находится в одной паре с женщиной, не являющейся его лучшим действи- тельным партнером. Так как мужчины делают предложение в порядке убывания предпочтений, это означает, что он был отвергнут действительным партнером в ходе выполнения  алгоритма. Возьмем первый момент в ходе выполнения , когда некоторый мужчина (скажем, m) отвергается действительным партнером w.

Поскольку мужчины делают предложение по убыванию предпочтений, а предло- жение отклоняется впервые, неизбежно следует, что женщина w является лучшим действительным партнером m, то есть best(m).

Отказ w мог произойти либо из-за того, что предложение m было отклонено в пользу существующей помолвки w, либо потому, что женщина w разорвала помолвку с m в пользу улучшенного предложения. Но в любом случае в этот момент w образует или продолжает помолвку с мужчиной m’, которого она пред- почитает m.

Поскольку w является действительным партнером m, должно существо- вать устойчивое паросочетание S’, содержащее пару (m, w). Теперь зададимся вопросом: кто является партнером m’ в этом паросочетании? Допустим, это женщина w’ ≠ w.

Так как отказ w от предложения m был первым отказом, полученным мужчиной от действительного партнера при выполнении , из этого следует, что m’ не был от- вергнут никаким действительным партнером на момент выполнения , в котором он был помолвлен с w.

Поскольку предложения делаются в порядке убывания предпочтений, а w’ очевидно является действительным партнером m’, из этого следует, что m’ предпочитает w женщине w’. Но нам уже известно, что w предпо- читает m’ мужчине m, поскольку в ходе выполнения E она отвергла m в пользу m’. Так как (m’, w) ѯ S’, можно сделать вывод, что пара (m’, w) является неустойчивой по отношению к S’.

Но это противоречит требованию об устойчивости S’, а следовательно, исходное предположение было неверным. ■

Итак, для мужчин алгоритм Гейла–Шепли идеален. К сожалению, о женщинах того же сказать нельзя. Для женщины w мужчина m является действительным партнером, если существует устойчивое паросочетание, содержащее пару (m, w). Мужчина m будет называться худшим действительным партнером для w, если m является действительным партнером w и ни один мужчина с оценкой ниже, чем m, в списке предпочтений w не является ее действительным партнером.

(1.8) В устойчивом паросочетании S* каждая женщина оказывается в паре со своим худшим действительным партнером.

Доказательство. Предположим, в S* существует пара (m, w), в которой m не является худшим действительным партнером w. Тогда должно существо- вать устойчивое паросочетание S’, в котором w находится в паре с мужчиной m’, имеющим более низкую оценку, чем m. В  S’ мужчина m находится в  паре  с женщиной w’ ≠ w; поскольку w является лучшим действительным партнером m и w’ является действительным партнером m, мы видим, что m предпочитает w женщине w’.

Но из сказанного следует, что пара (m, w) является неустойчивой по отношению к S’, а это противоречит требованию об устойчивости S’, а следовательно, исходное предположение было неверным. ■

Итак, рассмотренный пример, в котором предпочтения мужчин вступали в противоречие с предпочтениями женщин, дает представление о чрезвычайно общем явлении: для любых входных данных сторона, которая делает предложение в алгоритме Гейла–Шепли, оказывается в паре с лучшим из возможных устойчивых партнеров (с ее точки зрения), тогда как сторона, которая не делает предложение, соответственно оказывается с худшим из возможных устойчивых партнеров.