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

Рассмотрим такой пример (для ясности и наглядности я сократил список; в нем осталось лишь трое мужчин и три женщины).

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

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

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

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

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

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

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

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

В моем примере каждый мужчина предпочел «свою» женщину, а каждая женщина – «своего» мужчину, и ничьи интересы не пересекаются – но здесь не только нет «брака на небесах», здесь еще и есть повод для беспокойства.

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

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

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

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

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

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

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

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

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

А что, если трое мужчин поставят на первое место одну и ту же женщину?

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

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

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

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

Что в таком случае делать Зое?

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

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

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

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

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

Да, видимо, Зою ждет немало проблем…

Теперь предположим, что у нас 10 мужчин и 10 женщин. Что лучше: свести как можно больше людей с их фаворитами или по крайней мере с теми, кто занял в их списках «второе место»? Или свести как можно меньше людей с теми, кому они отвели «последние места»?

На этот вопрос нет однозначных ответов.

Впрочем, Зоя – женщина практичная. Она знает: блаженства всем никто не обещал – и ставит себе гораздо более скромную цель. Ее задача – создать стабильные пары, в которых супруги не будут изменять друг другу.

Что это значит в практическом смысле? Итак, для того чтобы предотвратить измены, Зоя должна убедиться в том, что в ее парах никого не влечет сверх меры к кому-либо помимо супруга или супруги. Рассмотрим такие пары: Пол и Нина, Рон и Джина. Итак, Пол женат на Нине, но, предположим, Джина нравится ему больше; и при этом Пол нравится Джине больше, чем ее старый добрый Рон. При таком сочетании измены неизбежны. Заметьте, проблемы не будет, если Джина нравится Полу больше жены, но сама при этом любит мужа: она просто отвергнет любые поползновения Пола.

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

Алгоритм Гейла – Шепли для стабильного брака

В 1962 г. Ллойд Шепли – признанный американский математик и обладатель Нобелевской премии 2012 г. по экономике – и покойный американский математик и экономист Дэвид Гейл (мы с ним встречались в главе про игру «Хрум!») продемонстрировали, как можно сочетать парами любые равные группы мужчин и женщин и избежать измен. Очень важно понять: этот алгоритм не гарантирует счастья, только стабильность. Очень возможно, что Нина, выйдя замуж за Пола, будет мечтать о Джоне, но алгоритм гарантирует, что Джон любит свою жену больше, чем Нину. Это не значит, что Джон счастлив в браке, и, может быть, он даже грезит о другой женщине – но, если так, алгоритм убеждает в том, что эта женщина предпочитает Джону своего мужа. И так далее…

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

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

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

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