Брэд – Скарлетт, Рассел – Адриана, Дэнни – Рианна
Единственным одиноким мужчиной теперь остается Джордж (Sic transit gloria mundi). И он делает предложение Рианне, которая с радостью соглашается, ведь в ее списке Джордж стоял выше Дэнни (и ростом он повыше). Итак, наши пары:
Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна
Теперь одинок легендарный де Вито. Он обращается к Скарлетт, но та предпочитает Брэда. Еще один раунд – и ничего не меняется. Дэнни делает ставку на Адриану – но она счастлива с Расселом. В глубокой депрессии и на грани кризиса Дэнни испытывает удачу с Кирой – и та раскрывает ему объятия. Она так долго была одинока, что ее устраивает даже такой вариант.
Алгоритм завершается, когда все мужчины нашли себе спутниц (и, поскольку обе группы численно равны, все женщины на этой стадии тоже помолвлены). А значит, нашими финалистами становятся:
Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна, Дэнни – Кира
И жили они счастливо (по крайней мере в чудесной стабильности) с тех самых пор.
Довольно легко принять то, что пары, сформированные по алгоритму Гейла – Шепли, останутся стабильными; но, чтобы устранить все сомнения, давайте это докажем. Если вам, мои читатели, не слишком по душе логический анализ и доказательства и если вы верите в то, что алгоритм Гейла – Шепли работает безупречно, приглашаю вас перейти сразу к следующей части.
Рад видеть, что вы решили остаться. Итак:
1. Ясно, что алгоритм не может продолжаться до бесконечности. В самом неблагоприятном варианте все мужчины сделают предложение всем женщинам.
2. Ясно, что число помолвленных мужчин всегда будет равняться числу помолвленных женщин. Также ясно и то, что, как только женщина помолвлена, она остается помолвленной (даже если меняется спутник). Кроме того, никто из группы по завершении процесса не может остаться вне помолвки. Достаточно сказать вот что: если Рон напишет «Нина» в своем списке предпочтений (пускай и на последнем месте), а никто другой с ней быть не захочет, она в конце концов Рону и достанется. И потому алгоритм гарантирует, что никто не останется без пары.
3. Но гарантирует ли он стабильность пар? Да – и мы это докажем. Представьте, что Йоко замужем за Джорджем, а Нина – за Полом. Возможно ли, что Йоко предпочтет Пола своему нынешнему супругу – и при этом понравится ему больше его жены, что поставит пары на грань предательства?
Ниже мы предположим, что это возможно, а потом коса найдет на камень – и логическое противоречие докажет, что это на самом деле невозможно.
Итак, предположим, у нас есть нестабильность – иными словами, две пары, Пол – Нина и Джон – Йоко, где Пола влечет к Йоко, а ее – к нему и оба желают быть друг с другом сильнее, чем со своими нынешними супругами. Согласно алгоритму, Полу следовало сделать Йоко предложение еще до того, как он отправился повидаться с Ниной (поскольку Йоко, по нашей предпосылке, получила более высокую оценку в его списке предпочтений). Теперь могут произойти два события:
А. Йоко соглашается на предложение Пола.
Б. Йоко отвечает отказом.
Если произошло событие А, то почему Йоко не живет с Полом? А потому, что выбрала того, кому поставила более высокую оценку, – Джона или кого-либо еще. В любом случае, если она сейчас с Джоном, значит, она оценила его выше, нежели Пола. Вот и обещанное логическое противоречие. Если случилось событие Б, тогда, выходит, Йоко отвергает Пола, поскольку у нее есть лучший спутник (Джон или кто другой), – и при этом тот факт, что сейчас она с Джоном, доказывает, что Джон получил более высокую оценку, нежели Пол, и наша исходная предпосылка вновь оказывается противоречивой.
В двух словах: алгоритм завершается, у каждого есть супруг, и пары стабильны.
А что, если женщины будут выбирать себе фаворитов? Наш пример с актерами даст те же самые пары: здесь у нас только одно стабильное сочетание.
Впрочем, так будет не всегда. Когда стабильных сочетаний несколько, а выбор совершают женщины, формирование пар проходит иначе.
Неверно говорить о неверном выборе в любви: как только выбор есть, верным он быть уже не может.
