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

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

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

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

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

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

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

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

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

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

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

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

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

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