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

Рассмотрим общий случай матричной игры представленной следующей платежной матрицей.

Таблица 2. Матрица игры в смешанных стратегиях.

Ai	Bj	p i
B1	B2	…	Bn
A1	a 11	a 12	…	a 1n	P1
A2	a 21	a 22	…	a 2n	P2
…	…	…	…	…	…
Am	a m1	a m2	…	a mn	Pm
q j	q 1	q 2	…	q n

 

Обозначим через P₁,P₂,...,P_m вероятности которые игрок А применяет

в ходе игры, используя свои чистые стратегии A₁,A₂, …, A_m.

Т.к. в матрице представлен полный набор чистых стратегий игрока А, то для вероятностей P_i выполняются условия:

,

Упорядоченное множество (, , …, ), элементы которого удовлетворяют приведенным условиям полностью определяют характер игры игрока А и называются его смешанной стратегией. Таким образом, смешанной стратегией игрока А является полный набор вероятностей применения его чистых стратегий. Механизм случайного выбора чистых стратегий, которым пользуется игрок А, обеспечивает ему бесконечное множество смешанных стратегий. Любая его чистая стратегия A_i может рассматриваться как частный случай смешанных стратегий, i-я компонента которой равна 1, а остальные равны 0, т.е. (0, …, 1, …, 0).Аналогично упорядоченное множество, элементы которого удовлетворяют

соотношениям называют смешанной стратегией игрока В. Игрок В, как и игрок А, располагают бесконечным множеством смешанных стратегий.

Пусть игроки А и В применяют смешанные стратегии . Это означает, что игрок А использует стратегии A_i с вероятностью p_i, a игрок В- стратегию B_j с вероятностью q_j. Поскольку игроки выбирает свои чистые стратегии случайно и независимо друг от друга, то вероятность выбора комбинации (А_i;В_j) будет равна произведению вероятностей p_i и q_j, т.е. p_i * q_j. При использовании смешанных стратегий игра приобретает случайный характер, случайной становится и величина выигрыша игрока А (проигрыш игрока В). В связи с этим можно вести речь лишь о средней величине (математическое ожидание) выигрыша (проигрыша). Эта величина является функцией от смешанных стратегий , и определяется по формуле:

(; )=

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

Однако, вместо выигрыша a_ij теперь надо иметь в виду средний выигрыш (; ), а вместо чистых стратегий с номерами i и j, следует подразумевать смешанные стратегии .

Нижней ценой игры будем называть число , определяемое по формуле:

, а верхней ценой игры – число , которое определяется по формуле:

Назовем оптимальными смешанные стратегии ^* и ^* игроков А и В, удовлетворяющие равенству

=

Величину называют ценой игры v = Или, р* и q* называются оптимальными смешанными стратегиями соответственно игроков А и В, если они образуют седловую точку для платежной функции

_, т.е. удовлетворяют неравенству

Из этого неравенства следует, что в седловой точке (p*;q*) платежная функция достигает максимум по смешанной стратегии ^*игрока А и минимума по смешанной стратегии ^*игрока В. Оказывается, если использовать смешанные стратегии, то для любой матричной игры можно найти оптимальные стратегии и цену игры.

Теорема1. В смешанных стратегиях любая конечная матричная игра имеет седловую точку.

Теорема 2. Для того чтобы смешанные стратегии * = ( *, *,.., *) и * = ( *, *,.., *) были оптимальными для игроков А и В в игре с матрицей (A_ij)_mn и ценой v, необходимо и достаточно чтобы выполнялись следующие неравенства:

Т.е. теорема утверждает, что если игрок А примет оптимальную смешанную стратегию , а игрок В - любую чистую стратегию B_j, то выигрыш игрока А будет не меньше цены игры v. Если игрок В использует оптимальную смешанную стратегию , а игрок А - любую чистую стратегию A_i, то проигрыш игрока В не превышает цены игры V.

Чистые стратегии игрока, входящие в его оптимальную смешанную стратегию с вероятностями, отличными от нуля, называются активными стратегиями игрока.

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

Можно доказать, что число активных стратегий игроков не превышает наименьшего из чисел m и n (m - число строк, n - число столбцов)

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

Если в платежной матрице элементы к-ой строки не меньше соответствующим элементов s-ой строки, т.е. a_kj ≥ a_sj (j= ), то выигрыш игрока А при стратегии А_к будет больше (не меньше), чем при стратегии A_s, какой бы стратегией B_j не воспользовался игрок В. Поэтому для игрока А стратегия А_к будет более выгодной, чем стратегия A_s.

В связи с этим говорят, что стратегия А_к доминирует над стратегией A_s, и называют стратегию А_к доминирующей, а стратегию A_s - доминируемой.

Аналогично, если элементы p-го столбца не превосходят

соответствующих элементов r-го столбца, т. е. , то

игроку В при любых условиях невыгодно применять стратегию В_r, так как в этом случае он будет проигрывать больше (не меньше), чем при стратегии В_p. Поэтому говорят, что стратегия В_p доминирует над стратегией В_r, и называют их соответственно доминирующей и доминируемой.

Частным случаем доминирования является дублирование стратегий. Упрощение платежных матриц за счет исключения заведомо невыгодных игрокам чистых стратегий оправдано ввиду справедливости следующей теоремы.

Теорема 4. Пусть Y - игра, в матрице которой к-ая стратегия, игрока А доминирует над s-ой, а Y'-игра, матрица которая получена из матрицы игры Y исключением s-й строки.

Тогда:

а) цена игры Y' равна цене игры Y;

б) оптимальная смешанная стратегия

q*= (q₁*,...,q_n*) игрока В в игре Y' является также его оптимальной смешанной стратегией и в игре Y;

в) если р* = (p₁*,...,p_s-1*,p_s+1,---,p_m) -оптимальная смешанная стратегия игрока А в игре Y', то его смешанная стратегия р* = (р₁*,...,р_s-1*,0,р_s+1*,...,р_m) является оптимальной в игре Y.

Из теоремы следует, что если стратегия А_к доминирует над стратегией A_s, то вероятность применения стратегии A_s в оптимальной смешанной стратегии р* игрока А равна нулю, а поэтому s-ую строку из платежной матрицы можно исключить.

Аналогично, если p-аястратегия B_pигрока В доминирует над г-ой стратегией В_г, то r-тый столбец из платежной матрицы можно исключить.

Пример. Выполним возможные упрощения платежной матрицы:

Значения элементов 1-ой и 3-ей строк соответственно равны, поэтому одну из них (например, 3-ью) можно опустить. Элементы второй строки не превышают соответствующим элементам первой, поэтому ее опускаем и приходим к матрице:

Элементы второго и элементы третьего столбцов, превышают элементы четвертого, а элемент пятого превышает элементы второго.

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

Если полученную матрицу вновь проанализировать с позиций игрока А, то дальнейшие упрощения сделать нельзя.

То есть не приступая к решению игры с исходной матрицей (а это громоздкая процедура), мы уже знаем, что в оптимальной смешанной стратегии р* игрока А компонента p₂^*p₃* равны нулю, т.е. р* = (P₁*;0;0;p₄*), а для оптимальной смешанной стратегии q* игрока В имеются три нулевых компонента q₁*,q₃*,q₅*, т.е. q* = (0;q₂*;0;q₃*;0).

Итак, вместо того чтобы искать решения игры с матрицей размерности 4*5, достаточно решить игру размерности 2*2.

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

Теорема 5. Пусть и - оптимальные смешанные стратегии игроков А и В в игре Y с матрицей (A_ij) _m*n и ценой v.

Тогда и будут оптимальными в игре Y' с матрицей (ba_ij+C)_m*n (где b > 0) и ценой v^’ = bv+C.

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

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

Например, разделив элементы матрицы

на 100 (умножить на 0,01), а затем, прибавив к элементам новой матрицы число 3, получим матрицу

Т.е. элементы a_ij' преобразованной матрицы получены из элементов исходной матрицы a_ij по формуле a_ij'= 0,01a_ij+ 3

Полученная матрица называется стратегически эквивалентной.