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

В двух словах: алгоритм завершается, у каждого есть супруг, и пары стабильны.

А что, если женщины будут выбирать себе фаворитов? Наш пример с актерами даст те же самые пары: здесь у нас только одно стабильное сочетание.

Впрочем, так будет не всегда. Когда стабильных сочетаний несколько, а выбор совершают женщины, формирование пар проходит иначе.

Неверно говорить о неверном выборе в любви: как только выбор есть, верным он быть уже не может.

Война полов: следующий раунд

Время вернуться к примеру, с которого началась эта глава, и напомнить себе о предпочтениях мужчин и женщин.

Предпочтения мужчин:

Рон : Нина, Джина, Йоко

Джон : Джина, Йоко, Нина

Пол : Йоко, Нина, Джина

Предпочтения женщин:

Нина : Джон, Пол, Рон

Джина : Пол, Рон, Джон

Йоко : Рон, Джон, Пол

С первого же взгляда понятно, что на этот раз потребуется только один раунд. Мужчины делают предложение фавориткам, и пары выглядят так: Рон – Нина, Джон – Джина и Пол – Йоко. Вот и все. Они определенно стабильны, ведь все мужчины нашли женщин своей мечты. Для мужчин это оптимальное решение. Впрочем, каждой женщине выпал спутник, которого она в своем списке определила в «аутсайдеры», и вряд ли можно сказать, что женщины счастливы.

Если предложение будут делать женщины, единственный раунд даст следующие пары: Йоко – Рон, Джина – Пол и Нина – Джон. Здесь каждая получает своего фаворита, а мужчинам предстоит провести всю жизнь с теми, кого они в своих списках оценили ниже всех.

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

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

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

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

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

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

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

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

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

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

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

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