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

Алгоритм Гейла – Шепли довольно прост и состоит из конечного числа итераций (раундов). Посмотрим, как он работает, на примере четверки мужчин (Брэд Питт, Джордж Клуни, Рассел Кроу и Дэнни де Вито) и четырех женщин (Скарлетт Йоханссон, Рианна, Кира Найтли и Адриана Лима). Алгоритм будет работать точно так же при любом равном количестве мужчин и женщин.

В таблице, приведенной ниже, представлены предпочтения мужчин:

А предпочтения женщин таковы:

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

После этого каждая женщина выбирает мужчину, занявшего более высокое место в ее списке, – в том случае, если кавалеров больше одного. Если к ней обращается только один кавалер, он и становится ее спутником, даже если стоит на низком месте в ее «перечне желаний». А если к ней никто не подходит, она в этом раунде остается одна. Именно поэтому Скарлетт выбирает Брэда, которого поставила выше Рассела.

Посмотрим на пары, которые у нас уже сформировались. Помните, это временно – они только помолвлены, но еще не женаты.

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

В следующем раунде мужчины, у которых еще нет спутницы, делают предложение той женщине, которая еще их не отвергла и занимает самое высокое место в их списках. Единственным, кто не нашел себе спутницу, сейчас остается Рассел (кстати, именно он играл Джона Форбса Нэша, нобелевского лауреата, в фильме Рона Ховарда), и он предлагает Адриане принять его в спутники.

Желание Адрианы быть с Расселом сильнее, нежели ее влечение к Джорджу, и потому она отзывает помолвку с Джорджем и объявляет о помолвке с Расселом. Теперь наши пары выглядят так:

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

Единственным одиноким мужчиной теперь остается Джордж ( Sic transit gloria mundi ). И он делает предложение Рианне, которая с радостью соглашается, ведь в ее списке Джордж стоял выше Дэнни (и ростом он повыше). Итак, наши пары:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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