Определение оптимальной смешанной стратегии

Вспомним третью (последнюю) игру, о которой говорилось в первом разделе этой главы. Каждый из двух игроков может записать одно из двух чисел: игрок А может записать 1 или 8, игрок Б — 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Матрица игры выглядит так:

Игра выглядит справедливой (игрок А может выиграть 1 или 8 евро, игрок Б — 2 или 7), седловой точки не существует: максиминное значение равно -2, минимаксное — 1. Поэтому ни для одного из игроков не существует чистой стратегии. Посмотрим, как в этом случае можно сформировать смешанную стратегию, которая будет оптимальной и позволит определить цену игры.

Смешанная стратегия — это некий «случайный» выбор одной чистой стратегии из набора. Чтобы сформировать смешанную стратегию, каждой чистой стратегии присваивается вероятность, означающая, с какой частотой игрок будет использовать эту чистую стратегию. Например, в нашем случае для игрока А есть две чистые стратегии (записать 1 или записать 8), для Б — две другие. Попробуем найти вероятности p(записать 1), p(записать 8) для игрока А и p(записать 7), p(записать 2) для игрока Б так, чтобы максимально повысить шансы каждого игрока на победу. Если мы определим вероятности и платежи для каждого случая, то сможем определить ожидаемый выигрыш.

Сначала нужно определить вероятности для чистых стратегий игрока А. Обозначим за р вероятность того, что этот игрок запишет 8. Тогда вероятность написания 1 будет равна 1 — р. Следовательно, если игрок Б запишет 7, ожидаемый выигрыш игрока А составит

V = 1 (1 - р) + (-7) р. Получим линейное уравнение V = 1 - 8р.

Если же, напротив, Б запишет 2, то ожидаемый выигрыш для игрока А составит

V = (-2)(1 - р) + 8р, что равносильно V = 10р — 2.

Игрок А хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок Б. Решив систему из двух линейных уравнений, получим значения р и V для игрока А. В данной задаче р = 1/6, V = -1/3.

Аналогично можно найти смешанную стратегию для игрока Б. Обозначим за р вероятность того, что он запишет 2. Тогда вероятность того, что он напишет 7, будет равна (1 — р). Если А запишет 1, то ожидаемый выигрыш Б составит

V = 2р + ( -1) (1 - р), что равносильно V = Зр — 1.

Аналогично если А выберет другую стратегию и запишет 8, то ожидаемый выигрыш игрока Б составит

V = ( -8)р + 7 (1 - р), то есть V = 7 - 15р.

Игрок Б хочет найти, для какого р ожидаемый выигрыш будет наибольшим вне зависимости от того, какую из двух стратегий выберет игрок А. Решив систему из двух линейных уравнений, получим значения р и V для игрока Б. Результаты будут следующими: р = 4/9, V* = 1/3.

Метод, который мы только что применили, можно обобщить для матриц 2 ? 2 и использовать для решения игр, которые не имеют седловой точки, в смешанных стратегиях. Проанализируем полученные результаты более подробно. Во-первых, заметим, что ожидаемые выигрыши совпадают (V = 1/3) и отличаются только знаком. Для А найденный выигрыш отрицательный, для Б — положительный. Это означает, что Б ожидает выиграть столько, сколько проиграет А. Цена игры (средний выигрыш игрока А) определяется с помощью уравнения (ad - bc)/(а + d - b - с), где a,b,c,d — элементы платежной матрицы (слева направо и сверху вниз). Так, в нашем случае цена игры равна (8 - 14)/18 = -6/18 = -1/3, что означает, что игрок А в среднем будет проигрывать 1 евро за каждые три партии, если оба игрока будут придерживаться оптимальных стратегий.

Теперь мы можем напрямую найти смешанные стратегии как для игрока А, так и для игрока Б. Соотношение, с которым игрок А должен применять смешанные стратегии, можно определить, если найти выигрыш и проигрыш для каждой строки матрицы. Так, его выигрыши равны 1 - (-2) = 3 (для первого ряда) и - 7 - 8 = -15 (для второго ряда). Следовательно, в рамках оптимальной стратегии игрок А должен действовать случайным образом, но соблюдать соотношение 15 к 3, или 5 к 1. Он должен записывать 1 в пять раз чаще (например, перед каждым ходом бросать обычный кубик, на пять граней которого нанесена цифра 1, а на одну грань — цифра 8). Заметим, что этот результат совпадает с тем, который мы получили, решив систему уравнений. Вероятность того, что игрок А запишет 8, должна равняться 1/6, следовательно, вероятность того, что он запишет 1, должна равняться 5/6.

Проведем аналогичные вычисления для игрока Б (по столбцам). Для первого столбца 1 — (—7) = 8, для второго столбца -2 -8 = -10. Следовательно, игрок Б должен придерживаться соотношения 10 к 8, либо, что аналогично, 5 к 4, в пользу числа 7. Это совпадает с решением системы уравнений, приведенной выше: мы вычислили, что вероятность написания 2 должна составлять 4/9, следовательно, вероятность написания 7 должна составлять 5/9.

Теперь мы можем сформулировать оптимальную смешанную стратегию для каждого игрока. А делает ходы произвольным образом, но должен записывать 1 с вероятностью 5/6 и записывать 8 с вероятностью 1/6. Аналогично игрок Б должен произвольным образом выбирать между 7 (с вероятностью 5/9) и 2 (с вероятностью 4/9).

ТЕОРЕМА О МИНИМАКСЕ

Для всех конечных игр двух игроков с нулевой суммой существует значение V, равное среднему ожидаемому выигрышу игрока А у игрока Б, если оба будут действовать разумно, то есть совершать ходы с целью увеличения выигрыша.

Эта теорема считается основной в теории игр и используется множеством способов даже в этой главе. Фон Нейман, который ее сформулировал и доказал, полагал, что в ее основе лежат три основные предпосылки.

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

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

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

Наконец, несмотря на то что седловой точки не существует, можно показать, что если каждый игрок будет придерживаться оптимальной смешанной стратегии, то игрок Б в среднем будет выигрывать 1/3 евро за партию. Если Б выберет любую другую стратегию, а игрок А будет придерживаться прежней, то выигрыш Б уменьшится. Напротив, если игрок Б будет придерживаться оптимальной стратегии, а игрок А выберет другую, проигрыш А возрастет.