Смешанное расширение матричных игр

Исследование в матричных играх начинается с нахождения её цены. Если матричная игра имеет решение, то нахождением цены игры (и соответствующих оптимальных стратегий) ис-следование игры и заканчивается. Но при нахождении оптимальных стратегий в любом случае определяется нижняя и верхняя цена данной игры (см. формулы (2) и (4)). Игрок A не должен надеяться на выигрыш бóльший, чем верхняя цена игры, и может быть уверен в получении вы-игрыша не меньше нижней цены игры (соответсвенно, игрок B не должен надеяться на проиг-рыш мéньший, чем нижняя цена игры, и может быть уверен, что его проигрыш не больше верх-ней цены игры). В этом общем случае новые решения матричных игр следует искать в возмож-ности многократного повторения игр и применения стратегий случайно, с определённой веро-ятностью.

Модификация исходной матричной игры, в которой её стратегии могут выбираться игро-ками уже не однозначно (как в разделах 1 - 3), а вероятностным образом, называется смешан-ным расширением данной матричной игры. Если игрок A выбирает стратегию ic вероятностью x_i (i = 1, ..., m), а игрок B- стратегию jc вероятностью y_j(j = 1, ..., n), то говорят, что игроки A и B используют смешанные стратегииx = (x₁, ..., x_m) и y = (y₁, ..., y_n). Стратегии исходной игры обычно называются чистыми стратегиями, а рассмотренные в разделе 2 решения исходной игры - решениями в чистых стратегиях. Чистая стратегия является частным случаем смешан-ной стратегии, когда все вероятности, кроме вероятности выбора данной чистой стратегии, рав-ны 0, а вероятность выбора данной чистой стратегии равна 1.

Таким образом, в смешанном расширение матричной игры множество стратегий игрока A- это бесконечное множество вероятностных распределений на конечном множестве исходных чистых стратегий {1, ..., m}. Проще говоря, это множество всех векторов x = (x₁ , ..., x_m), у кото-рых все координаты неотрицательны и их сумма равна 1. Координата x_i вектора x является ве-роятностью выбора чистой стратегии i. Аналогично определяется множество стратегий игрока B- множество всех векторов y = (y₁ , ..., y_n), у которых все координаты неотрицательны и их сумма равна 1. В отличие от множеств чистых стратегий, множества смешанных стратегий бес-конечны.

Пусть игроки A и B выбрали стратегии xи y. Тогда средний выигрыш игрока A определяется формулой

g(x,y) = . (9)

Как и ранее, игрок A стремится максимизировать свой средний выигрыш g(x,y), а игрок B- ми-нимизировать его, т.е. минимизировать свой средний проигрыш. Как и ранее, игрок A не знает, какую стратегию yвыбирает игрок B. Повторяя рассуждения из начала раздела 2, приходим к определению оптимальной смешанной стратегии x* игрока А и нижней цены игры в смешан-ных стратегияхV^-:

смешанной оптимальной стратегиейx* игрока А называется любая смешанная страте-гия игрока А, на которой достигается внешний максимум по множеству всех смешанных стратегий в следуюшем выражении (максимине):

max_xmin_yg(x,y), (10a) где g(x,y) определяется формулой (9), x* - любая смешанная стратегия игрока А, на которой до-

стигается внешний максимум в (10a) иV^- = min_yg(x*,y). Обозначим через X* множество всех оптимальных стратегий игрока А. Как и в разделе 2,V^- иX* определяются только по платёж-ной матрице Q.

Аналогично определяется минимакс

min_ymax_xg(x,y), (10b)

смешанная оптимальная стратегияy* игрока В, множество Y* всех оптимальных стратегий игрока B и верхняя цена игры в смешанных стратегиях V⁺ = max_xg(x,y*), определяемые только по платёжной матрице Q.

Как и в случае чистых стратегий, для смешанных стратегий имеет место неравенство

V^- ≤ V⁺; (11)

если V^- = V⁺, то число V, равное их общему значению, называется ценой игры в смешанных стратегиях.

Решением матричной игры в смешанных стратегиях называется пара стратегий áx*, y*ñ, удовлетворяющая условиям

g(x, y*) ≤ g(x*, y*) ≤ g(x*, y), (12)

где g(x,y) определяется формулой (9), x и y-произвольные стратегии игроков А и B.

Для смешанных стратегий имеет место утверждение, аналогичное утверждению 1 для чис-тых стратегий:

Утверждение 5. 1) V^-= V⁺ тогда и только тогда, когда для некоторой пары стратегий áx*, y*ñ выполняются условия (12); 2) стратегии x* и y*, удовлетворяющие (12), являются оптималь-ными; 3) цена игры V = g(x*, y*) ■

Принципиальное отличие случая смешанных стратегий от случая чистых стратегий фор-мулируется в следующем виде:

Утверждение 6.Для любой матричной игры существует решение в смешанных стратеги-ях ■

В частности, в силу утверждений 6 и 5 в любой матричной игре в смешанных стратегиях

V^- = V⁺. (13)

Напомним, что решение игры в чистых стратегиях существует не всегда, что и продемонс-трировано в примере 2.

Пример 5.Рассмотрим матричную игру двух лиц со следующей платёжной матрицей:

Q =

В этом случае max_imin_jq_ij = max{2, 1} = 2; min_jmax_iq_ij = min{4, 3} = 3, и поскольку

max_i min_j q_ij< min_jmax_i q_ij,

то чистых оптимальных стратегий нет.

Рассмотрим смешанные стратегии x* = (0,75; 0,25) и y* = (0,5; 0,5). Проверим их на опти-мальность. Для этого подсчитаем выражение g(x*, y*). В соответствии с формулой (9) имеем

g(x*, y*) = = 2 + 3 + 4 + 1 = 0,75·0,5·2 + 0,75·0,5·3 + 0,25·0,5·4 + 0,25·0,5·1 = 0,75 + 1,125 + 0,5 + 0,125 = 2,5. (14)

Рассмотрим теперь выражение g(x, y*) для произвольной стратегии x = (x₁,x₂). Из 3-его члена в равенствах (14) после простых выкладок получаем

g(x, y*) = x₁·2,5 + x₂·2,5 = (x₁ + x₂)·2,5 = 2,5 (15a)

(так как сумма вероятностей равна 1).

Рассмотрим теперь выражение g(x*, y) для произвольной стратегии y = (y₁,y₂). Из 3-его члена в равенствах (14) после простых выкладок получаем

g(x*, y) = y₁·2,5 + y₂·2,5 = (y₁ + y₂)·2,5 = 2,5 (15b)

(так как сумма вероятностей равна 1).

Формулы (14), (15a) и (15b) влекут для указанных стратегий x* = (0,75; 0,25) и y* = (0,5; 0,5) и для любых стратегий x = (x₁,x₂) и y = (y₁,y₂) двойное неравенство

g(x, y*) ≤ g(x*, y*) ≤ g(x*, y),

совпадающее с (12). Поэтому по определению пара стратегий áx*, y*ñ является решением в сме-шанных стратегиях данной матричной игры, не обладающей решением в чистых стратегиях ■

Пример 6.Рассмотрим матричную игру двух лиц со следующей платёжной матрицей:

Q =

В этом случае max_imin_jq_ij = max{2, -14} = 2; min_jmax_iq_ij = min{2, 3} = 2, и поскольку макси-мин равен минимаксу, пара чистых стратегий á1, 1ñ является решением данной игры в чистых стратегиях (см. раздел 2).

Напомним, что чистая стратегия является частным случаем смешанной. Положим x* = (1; 0) и y* = (1; 0). Пара смешанных стратегий áx*, y*ñ является той же самой парой чистых стра-тегий á1, 1ñ. При этом, с учётом матрицы Q и вида стратегий x* и y*, имеем

g(x*, y*) = 2. (16)

Рассмотрим теперь выражение g(x, y*) для произвольной стратегии x = (x₁,x₂). В данном случае, с учётом матрицы Q и того, что y* = (1; 0), получаем

g(x, y*) = x₁·2 + x₂·1 = x₁·2 + (1-x₁) = x₁+1 ≤ 2. (17a)

Аналогично, для x* = (1; 0) и произвольной стратегии y = (y₁,y₂), получаем

g(x*, y) = y₁·2 + y₂·3 =y₁·2 + (1-y₁)·3 = 3-y₁³ 2. (17b)

Формулы (16), (17a) и (17b) влекут для указанных стратегий x* = (0,75; 0,25) и y* = (0,5; 0,5), и для любых стратегий x = (x₁,x₂) и y = (y₁,y₂) двойное неравенство

g(x, y*) ≤ g(x*, y*) ≤ g(x*, y),

совпадающее с (12). Поэтому по определению исходная пара чистых стратегий áx*, y*ñ, которая была решением данной игры в чистых стратегиях, является решением этой же игры и в смешанных стратегиях ■

Результат примера 6 не случаен. Имеет место (почти очевидное)

Утверждение 7.В любой матричной игре решение в чистых стратегиях является решени-ем в смешанных стратегиях ■

К сожалению, поиск решений матричных игр в смешанных стратегиях (если у них нет решений в чистых стратегиях) является достаточно сложным с вычислительной точки зрения и здесь не рассматривается. Однако для отдельных классов матричных игр удаётся найти реше-ния в смешанных стратегиях значительно более простыми способами, которые рассматривают-ся в следующем разделе.