А. Йоко соглашается на предложение Пола.
Б. Йоко отвечает отказом.
Если произошло событие А, то почему Йоко не живет с Полом? А потому, что выбрала того, кому поставила более высокую оценку, – Джона или кого-либо еще. В любом случае, если она сейчас с Джоном, значит, она оценила его выше, нежели Пола. Вот и обещанное логическое противоречие. Если случилось событие Б, тогда, выходит, Йоко отвергает Пола, поскольку у нее есть лучший спутник (Джон или кто другой), – и при этом тот факт, что сейчас она с Джоном, доказывает, что Джон получил более высокую оценку, нежели Пол, и наша исходная предпосылка вновь оказывается противоречивой.
В двух словах: алгоритм завершается, у каждого есть супруг, и пары стабильны.
А что, если женщины будут выбирать себе фаворитов? Наш пример с актерами даст те же самые пары: здесь у нас только одно стабильное сочетание.
Впрочем, так будет не всегда. Когда стабильных сочетаний несколько, а выбор совершают женщины, формирование пар проходит иначе.
Неверно говорить о неверном выборе в любви: как только выбор есть, верным он быть уже не может.
Война полов: следующий раунд
Время вернуться к примеру, с которого началась эта глава, и напомнить себе о предпочтениях мужчин и женщин.
Предпочтения мужчин:
Рон: Нина, Джина, Йоко
Джон: Джина, Йоко, Нина
Пол: Йоко, Нина, Джина
Предпочтения женщин:
Нина: Джон, Пол, Рон
Джина: Пол, Рон, Джон
Йоко: Рон, Джон, Пол
С первого же взгляда понятно, что на этот раз потребуется только один раунд. Мужчины делают предложение фавориткам, и пары выглядят так: Рон – Нина, Джон – Джина и Пол – Йоко. Вот и все. Они определенно стабильны, ведь все мужчины нашли женщин своей мечты. Для мужчин это оптимальное решение. Впрочем, каждой женщине выпал спутник, которого она в своем списке определила в «аутсайдеры», и вряд ли можно сказать, что женщины счастливы.
Если предложение будут делать женщины, единственный раунд даст следующие пары: Йоко – Рон, Джина – Пол и Нина – Джон. Здесь каждая получает своего фаворита, а мужчинам предстоит провести всю жизнь с теми, кого они в своих списках оценили ниже всех.
Итак, можно увидеть, что игра дает преимущество тем, кто делает предложение в первом раунде.
(Кстати, здесь у нас есть еще один стабильный вариант формирования пар: Нина – Пол, Джина – Рон и Йоко – Джон. Прошу, проверьте эту стабильность – иными словами, убедитесь, что в этом случае не будет измен.)
Футболисты без моделей
Алгоритм Гейла – Шепли не сложен, но и не тривиален. Если мы оставим в стороне предпосылку о двух полах и предположим, что четверо футболистов должны провести ночь перед важным матчем в номерах для двоих, возможно, у нас не получится найти стабильное решение в выборе подходящего соседа по комнате.
Проверьте – и увидите: здесь не получится никаких стабильных пар.
И Нобелевскую премию получает…
Есть много сфер, где можно применить алгоритм Гейла – Шепли. Самая знаменитая – это назначение выпускников медицинских школ в больницы для прохождения интернатуры. Готов биться об заклад: вы уже догадались, что больницы получили право предлагать первыми (и по этому вопросу еще и сейчас ведутся судебные тяжбы). Другое важное применение «стабильного брака» – приписывание пользователей к серверам в интернете.
В 2012 г. Рот и Шепли получили Нобелевскую премию за «теорию стабильных распределений и практические наработки в сфере устройства рынков». Их работа была основана на алгоритме Гейла – Шепли.
Гейл покинул наш мир в 2008 г., так и не получив премии, а Элвин Рот завоевал награду после того, как обнаружил другие важные области применения алгоритма Гейла – Шепли… и учредил в Новой Англии программу по обмену почками.
Интермедия. Игра в гладиаторов
«Гладиаторы» – одна из моих любимых игр. На уроках, посвященных вероятностям или теории игр, я всегда привожу ее в пример. Это трудное упражнение в высшей степени рекомендовано истинным энтузиастам математики.
Игра проходит так. Есть две группы гладиаторов – А (афиняне) и В (варвары). Предположим, что в группе А 20 гладиаторов, а в группе В – 30. У каждого гладиатора есть опознавательный номер, положительное целое число, обозначающее его силу (скажем, число килограммов, которые он может поднять). Гладиаторы сражаются друг с другом на дуэлях. Их шансы на победу соотносятся так: когда гладиатор с силой 100 сражается с гладиатором с силой 150, для расчета его шансов на победу 100 делится на (100+150), ведь чем сильнее гладиатор, тем больше вероятность того, что он победит. Если силы двух гладиаторов, вышедших на дуэль, равны, шансы каждого конечно же составляют 50 %, и чем больше разрыв между ними, тем выше шансы более сильного гладиатора.
У каждой группы есть тренер, который решает, каких гладиаторов выпустить на ринг, но решение он принимает только один раз. Он волен выслать самого сильного бойца первым или последним, но в любом случае победитель дуэли отправляется в конец очереди и ждет своего хода – у вас не получится сделать так, чтобы ваш самый сильный гладиатор сражался непрестанно. Тот, кто проиграл поединок, выбывает из состязания, а выигравший присваивает себе всю его силу – иными словами, если «Гладиатор 130» побеждает «Гладиатора 145», последний выбывает из игры, а первый получает новое имя – «Гладиатор 275». Игра кончается, когда в одной из групп заканчиваются бойцы-гладиаторы, что, естественно, приводит к ее поражению.
Какая стратегия будет здесь лучшей? В каком порядке выпускать бойцов на ринг? (Уделите себе минутку и подумайте об этом, прежде чем читать дальше.)
Ответ довольно удивителен: вам не нужен тренер. Порядок выхода бойцов никак не влияет на вероятность победы. Шансы на нее равны сумме сил всей команды гладиаторов, разделенной на общую сумму сил обеих команд.
Докажите это! (Подсказка: не начинайте с общих случаев! Это будет сложно. Начните с одного афинского гладиатора и двоих варваров; потом проверьте, что случится с двумя афинянами и двумя варварами… Надеюсь, вы сумеете найти паттерн. А еще можете попытаться прийти к решению методом индукции.)
Не стану утверждать, будто это упражнение способно принести какие-то особые прозрения спортивным тренерам. Несомненно, тренеры важны, хотя иногда их важность слегка переоценивают.
6. Крестный отец и «Дилемма заключенного»
Эту главу я посвящаю самой популярной игре во всем репертуаре теории игр – «Дилемме заключенного». Мы рассмотрим каждый аспект игры, включая и итеративную версию дилеммы, и узнаем кое-что действительно важное: эгоистическое поведение не только влечет проблемы с моралью, но и во многих случаях стратегически неразумно.
Самая знаменитая и популярная игра в теории игр – это «Дилемма заключенного». Она развилась из эксперимента, который Мелвин Дрешер и Меррил Флад проводили в 1950-х гг. для корпорации RAND. А название ей дала одна история, которую в 1950 г., на лекции, посвященной данному эксперименту на факультете психологии в Стэнфорде, рассказал Альберт Такер. На эту тему написаны бесчисленные статьи, книги и докторские диссертации, и, верю, даже вне университетских стен о ней много кто хоть краем уха да слышал.
Рассмотрим популярную версию игры. В ней участвуют двое с выразительными именами А и Б. Они под арестом, в тюрьме, полиция подозревает их в совершении ужасного преступления, но материальных доказательств нет. Итак, полицейским необходимо их разговорить, и предпочтительнее всего, чтобы говорили они друг о друге. И вот задержанных ставят в известность: если оба решат молчать, обоих на год упекут за решетку по более легкой статье – припишут квартирную кражу со взломом или иной проступок. Прокуроры предлагают им сделку: если один предаст другого, предателя тут же отпустят на свободу; а вот другой за доказанное преступление будет приговорен к двадцати годам тюрьмы. Если каждый обвинит в преступлении другого, оба получат по 18 лет тюрьмы (скидка 10 % за помощь следствию). Заключенных сажают в разные камеры, и каждый должен принять решение, не видя другого, – иными словами, узнать, какое решение принял другой, ни один из них не может, пока окончательно не примет свое.
В таблице, приведенной ниже, кратко представлены правила игры (числа обозначают годы тюремного заключения):
Математики называют такой вид диаграмм «платежной матрицей»: они не любят терминов вроде «таблица» или «схема» – а то еще, не дай бог, обычные люди поймут.
Если честно, пока что история довольно скучна и трудно понять, почему столь многие о ней писали. Она становится интересной, когда мы начинаем раздумывать над тем, как нам играть. На первый взгляд ответ ясен: обоим нужно молчать, провести год в тюрьме за счет налогоплательщиков и выйти на свободу даже раньше, чем в том случае, если бы оба стали примерными заключенными. Конец истории. И все же, будь все так просто, никто бы и не тревожился ни о какой «дилемме заключенного». А правда такова: произойти здесь может что угодно.
Чтобы на самом деле понять дилемму, встанем на минутку на место А:
«Не знаю, что может сказать Б или что он уже сказал, но знаю, что у него только два варианта: молчать или предать. Если он будет молчать, а я тоже откажусь говорить – есть же, в конце концов, Пятая поправка! – я проведу год в тюрьме. Но если я его предам, то могу выйти! В смысле если он будет держать рот на замке, я выйду! Что тут думать? Толкнуть его под поезд, и дело с концом!
С другой стороны, если он меня выдаст, а я буду молчать, я сгнию в тюрьме. Двадцать лет в аду – это долго. И если он начнет болтать, так надо бы и мне заговорить. Тогда я буду сидеть только 18 лет. Лучше, чем 20, правда?
Есть! Я понял! Лучше всего предать! Ведь тогда я либо не пойду в тюрьму, либо просижу на два года меньше, а два года – это 730 дней на свободе! Какой я умный!»