Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Аналогично можно найти смешанную стратегию для игрока Б. Обозначим за р вероятность того, что он запишет 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 евро за партию. Если Б выберет любую другую стратегию, а игрок А будет придерживаться прежней, то выигрыш Б уменьшится. Напротив, если игрок Б будет придерживаться оптимальной стратегии, а игрок А выберет другую, проигрыш А возрастет.

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

Рассмотрим другие примеры, чтобы увидеть возможные применения метода смешанных стратегий.

Некая компания занимается разработкой нового продукта и оценивает возможность его выхода на рынок в следующем году. Можно выпустить продукт ограниченной серией из-за опасений, что экономическая обстановка будет неудовлетворительной, либо выпустить продукт крупной серией в надежде на экономический рост. Ожидаемая прибыль (в тысячах евро) приведена в таблице:

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

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

Обозначим за р вероятность выпуска крупной серии, (1 — р) — малой серии, V — ожидаемый доход. При плохой экономической обстановке доход будет равняться

V = 500 (1 — р) + ЮОр, что равносильно V = 500 - 400р.

При хорошей экономической обстановке доход будет равняться

V = 300 (1 — р) + 900р, то есть V = 300 + 600р.

Решением этой системы уравнений является р = l/5, V = 420. Это означает, что если бы ситуация могла повториться несколько раз, то оптимальным вариантом было бы выпускать продукт крупной серией 1 раз из 5 случайным образом и 4 раза из 5 — малой серией, при этом средний ожидаемый доход составит 420 тысяч евро.