Гладиаторы, пираты и игры на доверии. Как нами правят теория игр, стратегия и вероятности - [19]

Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна

Теперь одинок легендарный де Вито. Он обращается к Скарлетт, но та предпочитает Брэда. Еще один раунд – и ничего не меняется. Дэнни делает ставку на Адриану – но она счастлива с Расселом. В глубокой депрессии и на грани кризиса Дэнни испытывает удачу с Кирой – и та раскрывает ему объятия. Она так долго была одинока, что ее устраивает даже такой вариант.

Алгоритм завершается, когда все мужчины нашли себе спутниц (и, поскольку обе группы численно равны, все женщины на этой стадии тоже помолвлены). А значит, нашими финалистами становятся:

Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна, Дэнни – Кира

И жили они счастливо (по крайней мере в чудесной стабильности) с тех самых пор.

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

Рад видеть, что вы решили остаться. Итак:

1. Ясно, что алгоритм не может продолжаться до бесконечности. В самом неблагоприятном варианте все мужчины сделают предложение всем женщинам.

2. Ясно, что число помолвленных мужчин всегда будет равняться числу помолвленных женщин. Также ясно и то, что, как только женщина помолвлена, она остается помолвленной (даже если меняется спутник). Кроме того, никто из группы по завершении процесса не может остаться вне помолвки. Достаточно сказать вот что: если Рон напишет «Нина» в своем списке предпочтений (пускай и на последнем месте), а никто другой с ней быть не захочет, она в конце концов Рону и достанется. И потому алгоритм гарантирует, что никто не останется без пары.

3. Но гарантирует ли он стабильность пар? Да – и мы это докажем. Представьте, что Йоко замужем за Джорджем, а Нина – за Полом. Возможно ли, что Йоко предпочтет Пола своему нынешнему супругу – и при этом понравится ему больше его жены, что поставит пары на грань предательства?

Ниже мы предположим, что это возможно, а потом коса найдет на камень – и логическое противоречие докажет, что это на самом деле невозможно.

Итак, предположим, у нас есть нестабильность – иными словами, две пары, Пол – Нина и Джон – Йоко, где Пола влечет к Йоко, а ее – к нему и оба желают быть друг с другом сильнее, чем со своими нынешними супругами. Согласно алгоритму, Полу следовало сделать Йоко предложение еще до того, как он отправился повидаться с Ниной (поскольку Йоко, по нашей предпосылке, получила более высокую оценку в его списке предпочтений). Теперь могут произойти два события:

А. Йоко соглашается на предложение Пола.

Б. Йоко отвечает отказом.

Если произошло событие А, то почему Йоко не живет с Полом? А потому, что выбрала того, кому поставила более высокую оценку, – Джона или кого-либо еще. В любом случае, если она сейчас с Джоном, значит, она оценила его выше, нежели Пола. Вот и обещанное логическое противоречие. Если случилось событие Б, тогда, выходит, Йоко отвергает Пола, поскольку у нее есть лучший спутник (Джон или кто другой), – и при этом тот факт, что сейчас она с Джоном, доказывает, что Джон получил более высокую оценку, нежели Пол, и наша исходная предпосылка вновь оказывается противоречивой.

В двух словах: алгоритм завершается, у каждого есть супруг, и пары стабильны.

А что, если женщины будут выбирать себе фаворитов? Наш пример с актерами даст те же самые пары: здесь у нас только одно стабильное сочетание.

Впрочем, так будет не всегда. Когда стабильных сочетаний несколько, а выбор совершают женщины, формирование пар проходит иначе.

Неверно говорить о неверном выборе в любви: как только выбор есть, верным он быть уже не может.

Марсель Пруст

Война полов: следующий раунд

Время вернуться к примеру, с которого началась эта глава, и напомнить себе о предпочтениях мужчин и женщин.

Предпочтения мужчин:

Рон: Нина, Джина, Йоко

Джон: Джина, Йоко, Нина

Пол: Йоко, Нина, Джина

Предпочтения женщин:

Нина: Джон, Пол, Рон

Джина: Пол, Рон, Джон

Йоко: Рон, Джон, Пол

С первого же взгляда понятно, что на этот раз потребуется только один раунд. Мужчины делают предложение фавориткам, и пары выглядят так: Рон – Нина, Джон – Джина и Пол – Йоко. Вот и все. Они определенно стабильны, ведь все мужчины нашли женщин своей мечты. Для мужчин это оптимальное решение. Впрочем, каждой женщине выпал спутник, которого она в своем списке определила в «аутсайдеры», и вряд ли можно сказать, что женщины счастливы.

Если предложение будут делать женщины, единственный раунд даст следующие пары: Йоко – Рон, Джина – Пол и Нина – Джон. Здесь каждая получает своего фаворита, а мужчинам предстоит провести всю жизнь с теми, кого они в своих списках оценили ниже всех.

Итак, можно увидеть, что игра дает преимущество тем, кто делает предложение в первом раунде.

(Кстати, здесь у нас есть еще один стабильный вариант формирования пар: Нина – Пол, Джина – Рон и Йоко – Джон. Прошу, проверьте эту стабильность – иными словами, убедитесь, что в этом случае не будет измен.)