Проблема свахи
У свахи Зои есть список из 200 клиентов – 100 мужчин и 100 женщин. Каждая женщина дает ей свой перечень: там выписаны имена всех ста мужчин в порядке предпочтений. На самом верху листа – Прекрасный Принц, ниже – не столь привлекательные варианты, и так до самого конца. Сто мужчин в списке Зои сделали то же самое – и предоставили свахе списки женщин, выстроив их имена по предпочтениям.
Теперь, как предполагают, Зоя должна подобрать каждому спутника иного пола и убедиться в том, что все они сочетаются браком, построят дома и будут относительно счастливо жить-поживать да добра наживать. Ясно, что некоторые клиенты не успокоятся на первом же варианте выбора. Если одного мужчину из списка выбрали две женщины – или несколько женщин, – кому-то придется довольствоваться меньшим. Но даже если каждого из мужчин предпочитает всем не более чем одна женщина, а каждая женщина становится фавориткой не более чем для одного мужчины, это еще не гарантия блаженства.
Рассмотрим такой пример (для ясности и наглядности я сократил список; в нем осталось лишь трое мужчин и три женщины).
Предпочтения мужчин:
Рон: Нина, Джина, Йоко
Джон: Джина, Йоко, Нина
Пол: Йоко, Нина, Джина
Предпочтения женщин:
Нина: Джон, Пол, Рон
Джина: Пол, Рон, Джон
Йоко: Рон, Джон, Пол
В моем примере каждый мужчина предпочел «свою» женщину, а каждая женщина – «своего» мужчину, и ничьи интересы не пересекаются – но здесь не только нет «брака на небесах», здесь еще и есть повод для беспокойства.
Будущие супруги будут пребывать в счастье и блаженстве только в том случае, когда фаворит каждой женщины сочтет именно ее своей мечтой – например, если Пол любит Джину, а она в ответ любит его; если Нина с ума сходит по Рону, а он ее боготворит; и если Джон – это Прекрасный Принц для Йоко, за которую он готов умереть. В таком случае мы можем получить вот такую табличку предпочтений.
Предпочтения мужчин:
Рон: Нина, Джина, Йоко
Джон: Йоко, Нина, Джина
Пол: Джина, Йоко, Нина
Предпочтения женщин:
Нина: Рон, Джон, Пол
Джина: Пол, Рон, Джон
Йоко: Джон, Рон, Пол
А что, если трое мужчин поставят на первое место одну и ту же женщину?
Предпочтения мужчин:
Рон: Нина, Джина, Йоко
Джон: Нина, Джина, Йоко
Пол: Нина, Йоко, Джина
Что в таком случае делать Зое?
А если три женщины предоставят идентичные списки?
Предпочтения женщин:
Нина: Рон, Джон, Пол
Джина: Рон, Джон, Пол
Йоко: Рон, Джон, Пол
Да, видимо, Зою ждет немало проблем…
Теперь предположим, что у нас 10 мужчин и 10 женщин. Что лучше: свести как можно больше людей с их фаворитами или по крайней мере с теми, кто занял в их списках «второе место»? Или свести как можно меньше людей с теми, кому они отвели «последние места»?
На этот вопрос нет однозначных ответов.
Впрочем, Зоя – женщина практичная. Она знает: блаженства всем никто не обещал – и ставит себе гораздо более скромную цель. Ее задача – создать стабильные пары, в которых супруги не будут изменять друг другу.
Что это значит в практическом смысле? Итак, для того чтобы предотвратить измены, Зоя должна убедиться в том, что в ее парах никого не влечет сверх меры к кому-либо помимо супруга или супруги. Рассмотрим такие пары: Пол и Нина, Рон и Джина. Итак, Пол женат на Нине, но, предположим, Джина нравится ему больше; и при этом Пол нравится Джине больше, чем ее старый добрый Рон. При таком сочетании измены неизбежны. Заметьте, проблемы не будет, если Джина нравится Полу больше жены, но сама при этом любит мужа: она просто отвергнет любые поползновения Пола.
Кстати, если Пола больше влечет к Джине и это взаимно, а Рон при этом предпочитает Нину, что тоже взаимно, все решается очень легко. Нужно только разорвать старые пары (Пол и Нина, Рон и Джина) и создать две новые и намного более счастливые: Рон и Нина, Пол и Джина.
Алгоритм Гейла – Шепли для стабильного брака
В 1962 г. Ллойд Шепли – признанный американский математик и обладатель Нобелевской премии 2012 г. по экономике – и покойный американский математик и экономист Дэвид Гейл (мы с ним встречались в главе про игру «Хрум!») продемонстрировали, как можно сочетать парами любые равные группы мужчин и женщин и избежать измен. Очень важно понять: этот алгоритм не гарантирует счастья, только стабильность. Очень возможно, что Нина, выйдя замуж за Пола, будет мечтать о Джоне, но алгоритм гарантирует, что Джон любит свою жену больше, чем Нину. Это не значит, что Джон счастлив в браке, и, может быть, он даже грезит о другой женщине – но, если так, алгоритм убеждает в том, что эта женщина предпочитает Джону своего мужа. И так далее…
Алгоритм Гейла – Шепли довольно прост и состоит из конечного числа итераций (раундов). Посмотрим, как он работает, на примере четверки мужчин (Брэд Питт, Джордж Клуни, Рассел Кроу и Дэнни де Вито) и четырех женщин (Скарлетт Йоханссон, Рианна, Кира Найтли и Адриана Лима). Алгоритм будет работать точно так же при любом равном количестве мужчин и женщин.
В таблице, приведенной ниже, представлены предпочтения мужчин:
А предпочтения женщин таковы:
Вместо того чтобы объяснять алгоритм, позвольте показать, как он работает на практике. В первом раунде каждый мужчина делает предложение своей фаворитке. Так, Брэд и Рассел претендуют на внимание Скарлетт, Дэнни выбирает Рианну, а Джордж взывает к Адриане.
После этого каждая женщина выбирает мужчину, занявшего более высокое место в ее списке, – в том случае, если кавалеров больше одного. Если к ней обращается только один кавалер, он и становится ее спутником, даже если стоит на низком месте в ее «перечне желаний». А если к ней никто не подходит, она в этом раунде остается одна. Именно поэтому Скарлетт выбирает Брэда, которого поставила выше Рассела.
Посмотрим на пары, которые у нас уже сформировались. Помните, это временно – они только помолвлены, но еще не женаты.
Брэд – Скарлетт, Джордж – Адриана, Дэнни – Рианна
В следующем раунде мужчины, у которых еще нет спутницы, делают предложение той женщине, которая еще их не отвергла и занимает самое высокое место в их списках. Единственным, кто не нашел себе спутницу, сейчас остается Рассел (кстати, именно он играл Джона Форбса Нэша, нобелевского лауреата, в фильме Рона Ховарда), и он предлагает Адриане принять его в спутники.
Желание Адрианы быть с Расселом сильнее, нежели ее влечение к Джорджу, и потому она отзывает помолвку с Джорджем и объявляет о помолвке с Расселом. Теперь наши пары выглядят так:
Брэд – Скарлетт, Рассел – Адриана, Дэнни – Рианна
Единственным одиноким мужчиной теперь остается Джордж (Sic transit gloria mundi). И он делает предложение Рианне, которая с радостью соглашается, ведь в ее списке Джордж стоял выше Дэнни (и ростом он повыше). Итак, наши пары:
Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна
Теперь одинок легендарный де Вито. Он обращается к Скарлетт, но та предпочитает Брэда. Еще один раунд – и ничего не меняется. Дэнни делает ставку на Адриану – но она счастлива с Расселом. В глубокой депрессии и на грани кризиса Дэнни испытывает удачу с Кирой – и та раскрывает ему объятия. Она так долго была одинока, что ее устраивает даже такой вариант.
Алгоритм завершается, когда все мужчины нашли себе спутниц (и, поскольку обе группы численно равны, все женщины на этой стадии тоже помолвлены). А значит, нашими финалистами становятся:
Брэд – Скарлетт, Рассел – Адриана, Джордж – Рианна, Дэнни – Кира
И жили они счастливо (по крайней мере в чудесной стабильности) с тех самых пор.
Довольно легко принять то, что пары, сформированные по алгоритму Гейла – Шепли, останутся стабильными; но, чтобы устранить все сомнения, давайте это докажем. Если вам, мои читатели, не слишком по душе логический анализ и доказательства и если вы верите в то, что алгоритм Гейла – Шепли работает безупречно, приглашаю вас перейти сразу к следующей части.
Рад видеть, что вы решили остаться. Итак:
1. Ясно, что алгоритм не может продолжаться до бесконечности. В самом неблагоприятном варианте все мужчины сделают предложение всем женщинам.
2. Ясно, что число помолвленных мужчин всегда будет равняться числу помолвленных женщин. Также ясно и то, что, как только женщина помолвлена, она остается помолвленной (даже если меняется спутник). Кроме того, никто из группы по завершении процесса не может остаться вне помолвки. Достаточно сказать вот что: если Рон напишет «Нина» в своем списке предпочтений (пускай и на последнем месте), а никто другой с ней быть не захочет, она в конце концов Рону и достанется. И потому алгоритм гарантирует, что никто не останется без пары.
3. Но гарантирует ли он стабильность пар? Да – и мы это докажем. Представьте, что Йоко замужем за Джорджем, а Нина – за Полом. Возможно ли, что Йоко предпочтет Пола своему нынешнему супругу – и при этом понравится ему больше его жены, что поставит пары на грань предательства?
Ниже мы предположим, что это возможно, а потом коса найдет на камень – и логическое противоречие докажет, что это на самом деле невозможно.
Итак, предположим, у нас есть нестабильность – иными словами, две пары, Пол – Нина и Джон – Йоко, где Пола влечет к Йоко, а ее – к нему и оба желают быть друг с другом сильнее, чем со своими нынешними супругами. Согласно алгоритму, Полу следовало сделать Йоко предложение еще до того, как он отправился повидаться с Ниной (поскольку Йоко, по нашей предпосылке, получила более высокую оценку в его списке предпочтений). Теперь могут произойти два события: