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

Рассмотрим матричную игру с игроками P1 и P2 и платежной матрицей

1) Перед игроком P1 стоит задача выбора чистой стратегии, в результате применения которой он получит максимально возможный гарантированный

выигрыш. Если игрок P1 выбрал стратегию , то его выигрышем может быть один из выигрышей , расположенный в i-ой строке платежной

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

Обозначим минимальный среди выигрышей через αi:

, (αi –показатель эффективности стратегии Xi).

Продолжая действовать разумно, игрок P1 должен выбрать ту стратегию,

которая максимизирует показатель эффективности, т.е. для которой число αi максимально.

Обозначим:

Число α называется нижней ценой игры в чистых стратегиях, а стратегия

Xi0, которая максимизирует показатель эффективности αi называется максиминной стратегией игрока P1.

Таким образом, если игрок P1 в игре будет следовать максиминной стратегии, то ему при любой игре противника P2 гарантирован выигрыш в чистых стратегиях, не меньший α.

2) Рассмотрим игру с точки зрения игрока P2, который стремиться минимизировать выигрыш игрока P1. Если P2 выберет стратегию , то выигрышем игрока P1 может быть один из выигрышей . Но так как игрок P2 предполагает, что игрок P1 играет наилучшим для себя образом, то выигрышем игрока P1 будет максимальное из этих чисел, обозначим βj:

(βj –показатель неэффективности стратегии Yj).

Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β:

Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.

Теорема 3. Для элементов платежной матрицы имеют место неравенства:

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях: .

Пример. Найти решение игры, заданной платежной матрицей.

Решение:

Решим игру. Пусть – оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.

Рассмотрим матрицу

min

max(-1,-2,4)=4=

max 6 7 4 10

min (6,7,5,10)=5=

- нижняя цена игры.

- верхняя цена игры.

- максиминная стратегия, - минимаксная стратегия

Если то элемент называется седловым элементом матрицы

A=

Теорема 4. (о разрешимости матричной игры в чистых стратегиях) Если платежная матрица A имеет седловой элемент , то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является Xi0 чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v = .

Пример. Найти решение игры, заданной платежной матрицей A=

Решение:

Решим игру. Пусть -оптимальная стратегия первого игрока, - оптимальная стратегия второго игрока, v – цена игры.

Рассмотрим матрицу

min

max 2 3

v = =2 цена игры v = 2, существует седловой элемент = , тогда решение в чистых стратегиях имеет вид:

оптимальная стратегия первого игрока:

оптимальная стратегия второго игрока:

Ответ: оптимальные стратегии игроков ; , цена игры v =2.