Лекция 6 методы решения Матричных игр в смешанных стратегиях (продолжение)

6.1. Применение линейного программирования

В общем случае решение игры m×n сводится к задаче линейного программирования (присистема линейных уравнений не имеет решения или имеет бесконечное множество решений).

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

Средний выигрыш игрока 1 при его оптимальной смешанной стратегиии любой чистой стратегии игрока 2остается неизменным и равным цене игрыγ

(6.1.1)

Поскольку при m ≠ nрешение системы неоднородных линейных уравнений (6.1.1) найти невозможно, перейдем к эквивалентной (вспомогательной) задаче линейного программирования, учитывая, что средний выигрыш, равный цене игры, мы хотим сделать максимально возможным, а также то, что,.

(6.1.2)

Обозначив , получим

(6.1.3)

Здесь можно при необходимости заменить ограничения в виде равенств парами ограничений в виде неравенств.

Аналогично, средний проигрыш игрока 2 при его оптимальной смешанной стратегиии любой чистой стратегииигрока 1остается неизменным и равным цене игрыγ

(6.1.4)

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

(6.1.5)

Обозначив , получим

(6.1.6)

Здесь также можно заменить ограничения в виде равенств парами ограничений в виде неравенств.

С другой стороны, средний выигрыш игрока 1 при его оптимальной смешанной стратегиии любой чистой стратегии игрока 2в силу (3.2.2) будет не меньше, чем цена игрыγ

(6.1.7)

Соответственно, вспомогательная задача линейного программирования может быть записана в виде

(6.1.8)

Аналогично, средний проигрыш игрока 2 при его оптимальной смешанной стратегиии любой чистой стратегииигрока 1в силу (3.2.2) будет не больше, чем цена игрыγ

(6.1.9)

Соответственно, вспомогательная задача линейного программирования

(6.1.10)

Задачи (4.2.8) и (4.2.10) это прямаяидвойственнаязадачи линейного программирования.

Пример 6.1 Решение игры с помощью линейного программирования

	y1	y2
x1	4	0
x2	2	3

Здесь α₁=0, α₂=2, α=2, β₁=4, β₂=3, β=3, x₂―максиминная стратегия, y₂―минимаксная стратегия, седловая точка и ситуация равновесия отсутствуют.

Вначале найдем точное решение игры для игрока 1и игрока2 с помощью решения систем линейных уравнений вида (6.1.1) и (6.1.4).

Система

имеет решение, состоящее из положительных величин

Система

тоже имеет решение, состоящее из положительных величин

Соответствующие задачи линейного программирования имеют вид

и

Решение игры можно найти графически.

Лекция 7 итерационный метод решения Матричной игры

7.1. Метод Брауна-Робинсона

Рассмотрим теперь приближенный метод решения игры―итерационный метод Брауна-Робинсона.

В соответствии с заданной матрицей игры она многократно разыгрывается. Начинается с того, что игрок1 выбирает произвольно одну из своих чистых стратегий, например, x_i. Игрок2 отвечает на это той своей стратегией y_j, которая делает минимальным выигрыш при стратегии x_i. На это игрок 1 отвечает той своей стратегией x_k, которая дает максимальный выигрыш при стратегииy_j. Далее игрок2 отвечает на стратегии x_iи x_kтакой стратегией y_l, которая дает наименьший средний выигрыш игроку 1при этих двух стратегиях x_iи x_k, и так далее. На каждом шаге итерационного процесса каждый игрок отвечает на любой ход противника той своей стратегией, которая является оптимальной относительно всех его предыдущих ходов, рассматриваемых как некоторая смешанная стратегия, в которой чистые стратегии имеют вероятности, соответствующие относительным частотам их применения.

Пусть осуществлено k повторений игры, в которых чистые стратегии x_iи y_jприменялись с относительными частотами, и,.

Тогда накопленные средние результаты игры для чистых стратегий x_iи y_jбудут

(7.1.1)

(7.1.2)

где ―результат игры при стратегии x_iи стратегии, применяемой игроком 2наs-м повторении игры,―результат игры при стратегии y_jи стратегии, применяемой игроком 1наs-м повторении игры.

Игроки на (k+1)-м повторении игры выбирают те из своих стратегий, для которых средние результаты будут (средний выигрыш игрока 1максимален, а средний проигрыш игрока 2минимален)

(7.1.3)

(7.1.4)

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

Можно доказать, что средний выигрыш игрока 1и средний проигрыш игрока 2стремятся к цене игры

(7.1.5)

а соответствующие смешанные стратегии ,

приближаются к оптимальным смешанным стратегиям ,.

Об окончании итеративного процесса можно судить по величине

(7.1.6)

Когда при некотором k=N величина Δ(N) становится меньше заданного значения, процесс прекращают и считают, что цена игры

(7.1.7)

Преимущество итерационного метода решения игр, который сходится довольно медленно, в том, что объем и сложность вычислений медленно возрастают при увеличении числа стратегий mиn.