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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Итак, рассмотренный пример, в котором предпочтения мужчин вступали в противоречие с предпочтениями женщин, дает представление о чрезвы-

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

1.2.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. “Все к одному”
  2. Очерк 1: Гленда «Для себя и для организации я хочу, чтобы все делалось правильно и приводило к нужным результатам»
  3. ЕМУ ЛУЧШЕ ОДНОМУ, В СВОЕЙ ПЕЩЕРЕ
  4. ФОРСИРОВАНИЕ ПЕРЕМЕН НЕ ПРИВОДИТ К УСПЕХУ
  5. Все люди евреи, только не все об этом знают. Бернард Маламуд
  6. Повторяя молитву вслух по одному разу на каждом пальце, одновременно слегка шевелите им, чтобы ваше внимание направилось именно на него.
  7. Очерк 2: Моника «Свести все части воедино и увидеть, что все действительно работает»
  8. Глава 3. К чему приводит чувство беспокойства?
  9. ФОРСИРОВАНИЕ ПЕРЕМЕН ПРИВОДИТ К ОБРАТНОМУ РЕЗУЛЬТАТУ
  10. ВЕЛИЧАЙШИЙ СЕКРЕТ ТОГО, КАК ПРИВОДИТЬ ЗАКОН В ДЕЙСТВИЕ
  11. ПОЧЕМУ ОПРЕДЕЛЕНИЕ ЦЕЛИ ЗА ДРУГОГО НЕ ВСЕГДА ПРИВОДИТ К ОЖИДАЕМЫМ РЕЗУЛЬТАТАМ