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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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