Методы нахождения оптимальных смешанных стратегий.

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

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

- преобразовании платежной матрицы к более простому виду;

- выделении доминируемых стратегий игроков.

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

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

2). Если все элементы платежной матрицы умножить на некоторое число Q, то решение игры останется тем же, но цена игры увеличится в Q раз.

Тогда, например, игра с платежной матрицей

 

	0.5	0.6	0.9	эквивалентна игре
F =	0.7	0.5	0.5	с платежной матрицей F1=
	0.9	0.7	0.8

 

При этом все элементы F были домножены на 10 и из элементов полученной матрицы вычли 5, соответственно изменилась и цена игры. Решение игры осталось прежним - седловая точка (3,2); т.е. оптимальны 3-я стратегия первого игрока и 2-я стратегия второго игрока. Если цену игры, равную 2, подвергнуть обратным преобразованиям (добавить 5 и разделить на 10), то получим исходное значение цены игры 0.7.

 

Решение матричной игры с использованием методов

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

Пусть задана игра с платежной матрицей F = { f_ij }, в которой у первого игрока m чистых стратегий, а у второго игрока n чистых стратегий. Требуется найти решение игры, т.е. определить оптимальные смешанные стратегии игроков.

Приведем игру к виду, когда в платежной матрице содержатся только положительные элементы. Предположим, что известна оптимальная смешанная стратегия 1-го игрока p=(p₁,p₂,.. ...,p_m)^т. Тогда, используя утверждение об активных стратегиях (2.20), можно записать n неравенств вида

p^т F e^j ³ C , j = 1,...,n.

Это эквивалентно p^т F ³ C^т, или F^т p ³ C .

Последние неравенства можно записать в виде

f₁₁p₁ + f₂₁p₂ + ... + f_m1p_m ³ C,

f₁₂p₁ + f₂₂p₂ + ... + f_m2p_m ³ C,

………...........................…...

f_1np₁ + f_2np₂ + ... + f_mnp_m ³ C.

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

Разделим правую и левую часть неравенств на С (т.к. элементы платежной матрицы неотрицательны, то С ³ 0, и характер неравенств сохранится); введем обозначения x_i= p_i / C, i=1,. ..,m. Тогда

f₁₁x₁ + f₂₁x₂ + ... + f_m1x_m ³ 1,

f₁₂x₁ + f₂₂x₂ + ... + f_m2x_m ³ 1,

………............................... (5.15)

f_1nx₁ + f_2nx₂ + ... + f_mnx_m ³ 1,

x_i ³ 0, i = 1,...,m.

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

L(x) = x₁ + x₂ + ... + x_m. (5.16)

Подставим значения x_i (x_i = p_i/C) и получим,

L(x) = 1/C ( p₁ + p₂ + ... + p_m ) = 1/C.

Действительно, сумма p_i, i=1,...,m равна 1 ( из определения смешанной стратегии).

Следовательно, минимизируя L(x) на множестве допустимых x, которое задается (5.15), можно найти оптимальную смешанную стратегию p, доставляющую максимум цене игры. В силу линейности целевой функции и ограничений такая задача может решаться методами линейного программирования. Решение этой задачи всегда существует, т.к. значения F неотрицательны и ищется минимум суммы неизвестных переменных.

Оптимальная смешанная стратегия определяется как p_i = x_i/L, i = 1,...,m; цена игры C = 1/L.

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