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

Итак, можно увидеть, что игра дает преимущество тем, кто делает предложение в первом раунде.

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

Футболисты без моделей

Алгоритм Гейла – Шепли не сложен, но и не тривиален. Если мы оставим в стороне предпосылку о двух полах и предположим, что четверо футболистов должны провести ночь перед важным матчем в номерах для двоих, возможно, у нас не получится найти стабильное решение в выборе подходящего соседа по комнате.

Проверьте – и увидите: здесь не получится никаких стабильных пар.

И Нобелевскую премию получает…

Есть много сфер, где можно применить алгоритм Гейла – Шепли. Самая знаменитая – это назначение выпускников медицинских школ в больницы для прохождения интернатуры. Готов биться об заклад: вы уже догадались, что больницы получили право предлагать первыми (и по этому вопросу еще и сейчас ведутся судебные тяжбы). Другое важное применение «стабильного брака» – приписывание пользователей к серверам в интернете.

В 2012 г. Рот и Шепли получили Нобелевскую премию за «теорию стабильных распределений и практические наработки в сфере устройства рынков». Их работа была основана на алгоритме Гейла – Шепли.

Гейл покинул наш мир в 2008 г., так и не получив премии, а Элвин Рот завоевал награду после того, как обнаружил другие важные области применения алгоритма Гейла – Шепли… и учредил в Новой Англии программу по обмену почками.

Интермедия. Игра в гладиаторов

«Гладиаторы» – одна из моих любимых игр. На уроках, посвященных вероятностям или теории игр, я всегда привожу ее в пример. Это трудное упражнение в высшей степени рекомендовано истинным энтузиастам математики.

Игра проходит так. Есть две группы гладиаторов – А (афиняне) и В (варвары). Предположим, что в группе А 20 гладиаторов, а в группе В – 30. У каждого гладиатора есть опознавательный номер, положительное целое число, обозначающее его силу (скажем, число килограммов, которые он может поднять). Гладиаторы сражаются друг с другом на дуэлях. Их шансы на победу соотносятся так: когда гладиатор с силой 100 сражается с гладиатором с силой 150, для расчета его шансов на победу 100 делится на (100+150), ведь чем сильнее гладиатор, тем больше вероятность того, что он победит. Если силы двух гладиаторов, вышедших на дуэль, равны, шансы каждого конечно же составляют 50 %, и чем больше разрыв между ними, тем выше шансы более сильного гладиатора.

У каждой группы есть тренер, который решает, каких гладиаторов выпустить на ринг, но решение он принимает только один раз. Он волен выслать самого сильного бойца первым или последним, но в любом случае победитель дуэли отправляется в конец очереди и ждет своего хода – у вас не получится сделать так, чтобы ваш самый сильный гладиатор сражался непрестанно. Тот, кто проиграл поединок, выбывает из состязания, а выигравший присваивает себе всю его силу – иными словами, если «Гладиатор 130» побеждает «Гладиатора 145», последний выбывает из игры, а первый получает новое имя – «Гладиатор 275». Игра кончается, когда в одной из групп заканчиваются бойцы-гладиаторы, что, естественно, приводит к ее поражению.

Какая стратегия будет здесь лучшей? В каком порядке выпускать бойцов на ринг? (Уделите себе минутку и подумайте об этом, прежде чем читать дальше.)

Ответ довольно удивителен: вам не нужен тренер. Порядок выхода бойцов никак не влияет на вероятность победы. Шансы на нее равны сумме сил всей команды гладиаторов, разделенной на общую сумму сил обеих команд.

Докажите это! (Подсказка: не начинайте с общих случаев! Это будет сложно. Начните с одного афинского гладиатора и двоих варваров; потом проверьте, что случится с двумя афинянами и двумя варварами… Надеюсь, вы сумеете найти паттерн. А еще можете попытаться прийти к решению методом индукции.)

Не стану утверждать, будто это упражнение способно принести какие-то особые прозрения спортивным тренерам. Несомненно, тренеры важны, хотя иногда их важность слегка переоценивают.

6. Крестный отец и «Дилемма заключенного»

Эту главу я посвящаю самой популярной игре во всем репертуаре теории игр – «Дилемме заключенного». Мы рассмотрим каждый аспект игры, включая и итеративную версию дилеммы, и узнаем кое-что действительно важное: эгоистическое поведение не только влечет проблемы с моралью, но и во многих случаях стратегически неразумно.