Тройная игра

Пусть логики дополнительно договорились выбирать только числа 1 или 2. Как при этом должен действовать каждый из них?

Пусть двое логиков по-прежнему выбирают между 1 и 2, руководствуясь оптимальной стратегией выбора, а третий выбирает между 1, 2 и 3. Как часто он должен выбирать тройку?

Рассмотрите также другой вариант действий: пусть один из логиков остается верен выбору между 1 и 2, а двое других выбирают между 1, 2 и 3. Какой будет оптимальная стратегия для каждого из них?

Начнем с очень простых соображений. Назовем ходом игрока выбор им определенного числа, а партией — игру, в которой каждый игрок сделал свой ход. Результатом партии, по условию, является либо выигрыш 3 долларов одним из игроков, либо выигрыш 1 доллара каждым из них. Иначе говоря, можно считать, что до начала партии каждый игрок делает единичную ставку, а результат партии — либо ничья (каждый сохраняет свою ставку), либо победа одного из игроков (все ставки уходят победителю). Ну и, наконец, мы будем рассматривать не однократную игру (партию), а многократную (матч из огромного числа партий).

Соображение 1. Оптимальная стратегия, какой бы она ни была, должна «в среднем» сохранять игроку его ставку.

(Математики называют такие игры «играми с нулевой суммой».) Это следует из того, что все игроки равноправны, а значит, если они сыграют очень много (3N) результативных партий (то есть партий, которые не закончились вничью), и каждый будет пользоваться оптимальной стратегией (возможно, одной из нескольких, если их больше одной), то каждый выиграет в среднем по N партий и проиграет остальные 2N, а значит, получит дополнительные 2N долларов на выигрышах и столько же потеряет на проигрышах.

Соображение 2. Никакая стратегия, в которой игрок не пользуется случайностью для выбора своего «хода», не может быть оптимальной.

Действительно, оптимальная стратегия должна давать игроку (назовем его первым) гарантированную нулевую сумму независимо от того, какие стратегии используют партнеры. Пусть (по удивительной и необъяснимой случайности, например, в результате умения читать чужие мысли) второй игрок пользуется той же самой стратегией, что и первый (то есть делает те же ходы), а третий постоянно делает другие ходы. Тогда все партии будет выигрывать третий игрок, а оптимальная стратегия приведет к потере первым игроком всех его ставок!

Теперь можно разобраться с наводящими вопросами, заданными в подсказках.

Пусть логики дополнительно договорились выбирать только числа 1 или 2. Как при этом должен действовать каждый из них?

Уточним, что в силу соображения 2 игроки должны выбирать между 1 и 2 случайным образом, то есть выбирать 1 с некоторой вероятностью p, а 2 — с вероятностью (1 − p). Очевидно, что выбор между 1 и 2 полностью симметричен — это приводит к выигрышу, если оба остальных игрока делают другой ход. Следовательно, p = 1 − p и поэтому p = 0,5. Действительно, заполним табличку возможных случаев (при p = 0,5 все эти случаи равновероятны):

Восемь строк таблицы соответствуют восьми равновероятным комбинациям ходов. В двух вариантах партия заканчивается вничью, в остальных — по 2 победы у каждого из игроков.

Кажется, что тот же результат можно было бы получить и без предварительного соображения о том, что p = 0,5. Действительно, пусть мы пока не знаем значения p, но верим, что оно одинаково у всех. Первый игрок получит $1 при обеих ничьих — когда все сделали одинаковые ходы. Это происходит с вероятностью p³ + (1 − p)³. При обоих выигрышах первый игрок получит $3. Таким образом, выигранная им сумма (точнее было бы использовать здесь термин «математическое ожидание выигрыша первого игрока») равна

Этот результат кажется удивительным, но он верен! Действительно, любая случайная стратегия трех игроков приносит каждому в среднем $1 за партию, если стратегия одинакова у всех троих.

Однако почему мы так уверены, что все трое придерживаются одной и той же стратегии? Пусть это верно для двоих, но выбранная ими стратегия соответствует p, не равному 0,5, а третий игрок выбирает между 1 и 2 равновероятно (то есть «его p» равно 0,5). Тогда ожидаемый выигрыш этого игрока равен

Иначе говоря, он всегда выиграет больше чем $1. Таким образом, ни одна стратегия со значением p, отличным от 0,5, здесь не может быть оптимальной!

Пусть двое логиков по-прежнему выбирают между 1 и 2, руководствуясь оптимальной стратегией выбора, а третий выбирает между 1, 2 и 3. Как часто он должен выбирать тройку?

Рассмотрим эту ситуацию с позиции первого игрока. Пусть он с вероятностью p сделает ход 1 или 2, а с вероятностью 1 − p — ход 3. Если в первом случае, выбирая между 1 и 2, он будет использовать ту же оптимальную стратегию, которой пользуются остальные, то его ожидаемый выигрыш будет равен 1 (как и у остальных). А вот при выборе хода 3 он будет выигрывать тогда, когда двое остальных сделали одинаковые ходы, то есть в половине всех случаев.

Таким образом, выигрыш первого игрока при такой стратегии составит

Чем меньше p, тем больше выигрывает такой игрок! Иначе говоря, если он всегда будет выбирать 3, то он будет выигрывать в половине всех игр и проигрывать остальные, а значит, в среднем иметь $1,5. Соответственно, ожидаемый выигрыш у двух остальных уменьшится до $0.75.

Пусть один из логиков остается верен выбору между 1 и 2, а двое других выбирают между 1, 2 и 3. Какой будет оптимальная стратегия для каждого из них?

Это более сложная ситуация, но и с ней можно разобраться с помощью аналогичных соображений.

Пусть каждый из первых двух игроков с вероятностью p делает ход 1 или 2, а с вероятностью 1 − p — ход 3. Так как эти два игрока действуют одинаково, нам проще разобраться с теми случаями, в которых выигрывает третий. Если они делают ход 1 или 2, то ожидаемый выигрыш каждого из троих равен 1 (см. выше), а вот если они оба делают ход 3, то всегда (!) выигрывает третий игрок.

Кроме того, третий игрок выигрывает в тех случаях, когда он сам выбирает 1, один из первых двух выбирает 2, а другой — 3. Это происходит с вероятностью \(0{,}5p(1-p)\). Иначе говоря, ожидаемая сумма выигрыша третьего игрока при этом равна

Цель первых двух игроков — минимизировать эту величину, тогда их собственный выигрыш будет максимальным. Минимум достигается при p = 0,9 и равен 39/40, что достаточно мало отличается от 1, но все же дает им некоторое преимущество.

Практически так же можно показать, что каким бы ни был выбор внутри конечного списка вариантов (например, «можно делать только ходы 1, 2, ..., k»), расширение двоими игроками этого списка вариантов еще на одно число всегда приносит им преимущество перед тем игроком, который придерживается исходного списка.

Кажется, теперь можно приступать к решению задачи. Ответ в ней такой: каждый игрок должен делать ход k случайным образом с вероятностью 1/2^k.

Докажем этот ответ по индукции, а именно, будем доказывать, что оптимальная стратегия при ограничении ходов множеством чисел, не превосходящих N, состоит в выборе числа 1 с вероятностью 1/2, числа 2 — с вероятностью 1/4, ..., а последних двух чисел — с равной вероятностью. Базу индукции для N = 2 мы уже рассмотрели.

Пусть мы уже разобрались с оптимальной стратегией при выборе игроками одной из N − 1 возможностей. Теперь рассмотрим игру для N возможностей.

Пусть игрок выбирает ход 1 с вероятностью p. Если он сделал такой выбор, то:
- его выигрыш равен 1 в случае, если оба остальных тоже сделали ход 1;
- его выигрыш равен 3 в случае, если оба не сделали такой ход.
Иначе говоря, ожидаемый выигрыш равен \(S_1=p^2 + 3p(1-p)^2\).

Если он не сделал такой выбор, а оба остальных сделали, то он выиграл. И, наконец, если все трое не выбрали 1, то для них игра свелась к игре с (N − 1) возможностями, в которой ожидаемый выигрыш каждого игрока равен 1. Итого ожидание выигрыша для хода «не 1» равно \(S_2=3(1-p)p^2 + (1-p)^3\). Так как S₁ + S₂ (по формуле бинома Ньютона) равно 1, то наименьшее из двух этих выражений не больше 1/2. Если одно из них будет меньше 1/2, а другое больше 1/2, то оба других игрока смогут изменить стратегию так, чтобы уменьшить ожидаемый выигрыш первого. Поэтому он должен позаботиться о том, чтобы каждое из выражений S₁ и S₂ было равно 1/2. После небольших алгебраических преобразований равенства S₁ = S₂ получаем, что p = 1/2. Иначе говоря, ход 1 каждым из игроков делается с вероятностью 1/2, а с остальной вероятностью они применяют оптимальную стратегию для N − 1 возможностей.

По индукции получаем, что каждый ход k делается с такой же вероятностью, как и суммарно все большие ходы, то есть с вероятностью 1/2^k.

Рассмотренная задача — один из наиболее простых примеров задач теории игр. Здесь «игра» — это любой процесс, в котором каждая из участвующих сторон стремится к реализации своих интересов, и эти интересы у разных сторон могут вступать в конфликт друг с другом.

Методы теории игр сейчас уже считаются классическими, хотя появились они относительно недавно (основополагающая книга Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» вышла в 1944 году). Джон Нэш получил Нобелевскую премию по экономике за свою диссертационную работу 1949 года, посвященную поиску точек равновесия в вероятностных играх.

Вся вторая половина XX века ознаменовалась победным маршем теоретико-игровых методов по прикладным наукам — не только экономическим, но и в технике, кибернетике, биологии. Собственно, где-то от четверти до трети всех Нобелевских премий по экономике в это время присуждались математикам именно за их вклад в экономическую науку.

Одним из важнейших (хотя и далеко не единственным) классов игр являются игры с нулевой суммой (zero-sum game). Лучше всего изучены такие игры для двух игроков, однако и игры многих игроков тоже не были обойдены вниманием специалистов. Исследование таких игр получило даже отдельное название — «эволюционная теория игр» (Evolutionary game theory), потому что именно такими методами моделируется влияние дарвиновского естественного отбора. В рамках эволюционной теории игр изучается не столько поиск оптимальной стратегии в статической игре, сколько изменение оптимальных стратегий с течением времени.

Известнейший пример игры, в которой оптимальная стратегия может зависеть от поведения оппонента, — «Дилемма заключенного». В ней у каждого есть две стратегии — «предательство» и «сотрудничество», но параметры выигрышей подобраны так, что каждому по отдельности выгоднее использовать «предательство», а суммарный выигрыш больше всего оказывается в режиме «сотрудничество». Дилемма заключенного возникает из-за того, что выбор рациональной стратегии каждым участником по отдельности не приводит всех вместе к оптимальному решению. Поэтому при рассмотрении повторяющейся игры (по тем же правилам) участники могут «наказывать» других за отказ от сотрудничества — и именно угроза такого наказания может оказываться фактором, сдерживающим желание игроков использовать более выгодное «предательство». Таким образом, повторяющаяся (многоходовая) игра может использовать стратегии, зависящие от поведения других участников.

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