Решение игр в смешанных стратегиях

Если парная игра не имеет седловой точки, то она не имеет и решения, то есть, делая личные ходы (или, говоря иначе, в чистых стратегиях), игрок A гарантирует себе выигрыш, равный нижней цене игры, которая, вообще говоря, меньше верхней цены игры.

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

Определение. Пусть игрок A имеет m стратегий, а игрок B – n стратегий. Смешанной стратегией игрока A называется набор вероятностей S_A = (p₁, p₂, …, p_m), где p₁ + p₂ +… + p_m = 1, с которыми он чередует свои стратегии.

Аналогично определяется смешанная стратегия игрока B как набор S_B = (q₁, q₂, …, q_m), где q₁ + q₂ +… + q_n = 1.

Имеет место следующая теорема.

Теорема (основная теорема теории игр). Любая m ´ n игра имеет решение в смешанных стратегиях и её решение может получено методами линейного программирования.

Доказательство. Пусть m ´ n игра имеет матрицу

требуется найти решение игры, то есть две оптимальные смешанные стратегии игроков S_A = (p₁, p₂, …, p_m) и S_B = (q₁, q₂, …, q_m), где p₁ + p₂ +… + p_m = 1 и q₁ + q₂ +… + q_n = 1.

Во-первых, можно считать, что цена игры n (пока неизвестная) больше нуля. Действительно, если n £ 0, то это означает, что некоторые элементы матрицы игры не положительные. Тогда найдём число M > 0, которое прибавим ко всем элементам матрицы игры и получим новую матрицу с положительными элементами. Это сложение сделает новую цену игры n + M положительной, но не изменит решения игры.

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

Стратегия является оптимальной, то есть при любой стратегии игрока B средний выигрыш игрока A будет больше или равен цены игры n, таким образом, получаем систему ограничений

Разделим обе части всех неравенств на положительное число n и обозначим

тогда система ограничений примет вид

Далее, так как p₁ + p₂ +… + p_m = 1, то

Игрок A стремится максимизировать свой средний выигрыш n, то есть минимизировать отношение

Таким образом, получаем задачу линейного программирования:

Заметим, что эта задача имеет решение, найдя которое найдём новую цену игры , вычтя из которой число M, получим искомую цену игры.

Аналогичные рассуждения дают оптимальную стратегию игрока B:

обозначим

тогда оптимальная стратегия игрока B есть решение следующей задачи линейного программирования:

причём

Применим основную теорему теории игр для отыскания оптимальных стратегий игроков в игре "поиск".

1. Матрица игры "поиск" содержит отрицательные элементы, поэтому, прибавляя к её элементам число M= 1, получим

2. Для нахождения оптимальной стратегии игрока A решаем следующую задачу линейного программирования:

Так как последняя система ограничений эквивалентна системе

то минимум функции равен 1 и достигается при

Так как то n = 1. Вычитая из n число M = 1, получим, что цена игры равна 0 = 1 – 1, а оптимальная стратегия

Итак, чередуя свои обе стратегии с вероятностями , игрок A гарантирует себе средний выигрыш, равный 0, что больше нижней цены игры -1 при чистых стратегиях.

Аналогичные рассуждения приводят к тому, что игрок B, чередуя свои стратегии с вероятностями , получает средний выигрыш, равный 0.