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

Лекция 7

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

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

В соответствии с заданной матрицей игры она многократно разыгрывается. Начинается с того, что игрок 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.