В 2012 г. Рот и Шепли получили Нобелевскую премию за «теорию стабильных распределений и практические наработки в сфере устройства рынков». Их работа была основана на алгоритме Гейла – Шепли.
Гейл покинул наш мир в 2008 г., так и не получив премии, а Элвин Рот завоевал награду после того, как обнаружил другие важные области применения алгоритма Гейла – Шепли… и учредил в Новой Англии программу по обмену почками.
Интермедия. Игра в гладиаторов
«Гладиаторы» – одна из моих любимых игр. На уроках, посвященных вероятностям или теории игр, я всегда привожу ее в пример. Это трудное упражнение в высшей степени рекомендовано истинным энтузиастам математики.
Игра проходит так. Есть две группы гладиаторов – А (афиняне) и В (варвары). Предположим, что в группе А 20 гладиаторов, а в группе В – 30. У каждого гладиатора есть опознавательный номер, положительное целое число, обозначающее его силу (скажем, число килограммов, которые он может поднять). Гладиаторы сражаются друг с другом на дуэлях. Их шансы на победу соотносятся так: когда гладиатор с силой 100 сражается с гладиатором с силой 150, для расчета его шансов на победу 100 делится на (100+150), ведь чем сильнее гладиатор, тем больше вероятность того, что он победит. Если силы двух гладиаторов, вышедших на дуэль, равны, шансы каждого конечно же составляют 50 %, и чем больше разрыв между ними, тем выше шансы более сильного гладиатора.
У каждой группы есть тренер, который решает, каких гладиаторов выпустить на ринг, но решение он принимает только один раз. Он волен выслать самого сильного бойца первым или последним, но в любом случае победитель дуэли отправляется в конец очереди и ждет своего хода – у вас не получится сделать так, чтобы ваш самый сильный гладиатор сражался непрестанно. Тот, кто проиграл поединок, выбывает из состязания, а выигравший присваивает себе всю его силу – иными словами, если «Гладиатор 130» побеждает «Гладиатора 145», последний выбывает из игры, а первый получает новое имя – «Гладиатор 275». Игра кончается, когда в одной из групп заканчиваются бойцы-гладиаторы, что, естественно, приводит к ее поражению.
Какая стратегия будет здесь лучшей? В каком порядке выпускать бойцов на ринг? (Уделите себе минутку и подумайте об этом, прежде чем читать дальше.)
Ответ довольно удивителен: вам не нужен тренер. Порядок выхода бойцов никак не влияет на вероятность победы. Шансы на нее равны сумме сил всей команды гладиаторов, разделенной на общую сумму сил обеих команд.
