Основная теорема матричных игр фон Неймана. Методы решения матричных игр

Основная теорема  матричных игр фон Неймана. Методы решения матричных игр.

Конечной антагонистической (или матричной) игрой называется тройка , где множества стратегий U₁и U ₂ состоят из конечного числа точек, а g(u₁ , u₂ )– функция дискретного аргумента.

 

Равенство имеет место тогда и только тогда,  когда матрицаА содержит седловую точку В этом случае общее значение нижней и верхней цены игры называется ценой игры, а i₀  и

j₀ - оптимальными стратегиями игроков.

Теорема (основная теорема матричных игр фон Неймана). Любая матричная игра имеет цену (в смешанных стратегиях), а игроки имеют оптимальные смешанные стратегии, т.е.

v = max min h( p, q) = min max h( p, q) =

pÎS_n 

qÎS_m 

qÎS_m 

pÎS_n

= min h( p ⁰ , q) = max h( p, q ⁰ ) = h( p ⁰ , q ⁰ ) . 

qÎS _m 

pÎS _n

Доказательство. Согласно теореме о необходимых и достаточных условиях существования седловой точки утверждение данной теоремы эк- вивалентно утверждению о существовании седловой точки у функции

h( p, q) на 

S_n ´ S_m . Последнее вытекает из теоремы о существовании седло-

вой точки у вогнуто-выпуклой функции. Действительно, множества

S_n  и S_m 

являются, очевидно, выпуклыми замкнутыми ограниченными

подмножествами пространств 

R ⁿ   и 

R ^m , функция 

h( p, q) 

непрерывна по

p, q 

и линейна по 

p, q , следовательно, является вогнуто-выпуклой. Таким

образом, выполнены все условия теоремы о существовании седловой точки

у вогнуто-выпуклой функции и существует такая точка 

( p⁰ , q⁰ ) , что

h( p, q⁰ ) £ h( p⁰ , q⁰ ) £ h( p⁰ , q) 

"p, q. 

Из теоремы о необходимых и доста-

точных условиях существования седловой точки вытекает, что 

p⁰ реализу-

ет max min h( p, q) , 

q⁰  реализует 

min max h( p, q) 

и нижняя и верхняя цены

pÎS_n 

qÎS 

qÎS_m 

pÎS_n

 

игры в смешанных стратегиях равны между собой, что и требовалось дока- зать.

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

Задача решения матричной игры заключается либо в нахождении цены игры и хотя бы одной оптимальной стратегии каждого игрока, либо в нахождении цены игры и множеств всех оптимальных стратегий обоих игроков. В последнем случае решение называется полным. Так как множества оптимальных стратегий игроков представляют собой подмножества точек S_n  и S_m, удовлетворяющих системам линейных ограничений h( p⁰ , j) ³ v j =1, m.(3) и h(i, q⁰ ) £ v j = 1, n (4), то они являются выпуклыми замкнутыми ограниченными многогранниками.

В простейшем случае, когда у игрока имеются две чистые стратегии и его смешанная стратегия может быть полностью описана вероятностью выбора первой чистой стратегии p или q (вторая стратегия выбирается с

вероятностью 1- p или 1- q ), это означает, что множество оптимальных стратегий представляет собой либо одну точку, либо целый отрезок на от- резке [0,1] (возможно и весь этот отрезок). Для решения такой игры удобен

графический метод.

 

Графический метод

 

Рассмотрим матричную игру с двумя чистыми стратегиями у игрока

1 и произвольным числом стратегий m у игрока 2, т.е. игру с матрицей

размера 2´m (аналогично рассматривается игра с матрицей размера 

n ´ 2 ).

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

запишем

v = max min[a  p + a 

(1 - p)] = max min[(a 

• a  ) p + a

 

] = min[(a 

- a  ) p⁰ + a  ] .

0£ p£1 1£ j£m    ^{1 j 2 j} 

0£ p£1 1£ j£m ^{1 j 2 j} 

2 j _{1£ j£m} 1 j 2 j 2 j

Для графического решения игры на отрезке [0,1] построим m линейных

функций 

(a_{1 j} - a_{2 j} ) p + a_{2 j} , 

j = 1,2,..., m , найдем их нижнюю огибающую, соот-

ветствующую операции 

min , и у этой огибающей — точку (точки) макси-

1£ j £ m

мума. Абсцисса этой точки является оптимальной вероятностью выбора

первой чистой стратегии 

p ⁰ , а ордината — значением цены игры. Так как

при этом нижняя огибающая является, очевидно, графиком вогнутой ку- сочно-линейной функции (ломаной линией), то в точке максимума воз- можны два случая: либо через эту точку проходят две прямые, соответ

ствующие некоторым 

j₁    и 

j₂    и имеющие одна положительный, а другая

 

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

В первом случае можно построить оптимальную стратегию игрока 2,использующую только чистые стратегии j_{1 и} j₂    (q ₁=0 для всех j ¹ j ₁ j ₂).

Для этого q_j1 ⁰     q_j2  ⁰  

надо выбирать как решение системы

q _j1⁰   + q _j2⁰= 1, k₁ q_j1 ⁰ +k₂ q_j2 ⁰= 0,

где k₁  и k₂- коэффициенты наклонов соответствующих прямых.

Тогда, очевидно, выполняется h( p, q ⁰ ) ) = v "p, , т.е. по первой из теорем о необходимых и достаточных условиях  оптимальности стратегии q⁰— оптимальная стратегия.

Во втором случае оптимальной является j -я чистая стратегия, так как   h( p, j) = v "p.

На рис. 7.1 и 7.2 изображены характерные для первого и второго

случая графические построения.

 

h ^h

 

 

 

 

 

 

 

v ^j1 v ^j

 

 

j₂

 

0 p⁰ 1 p

Рис. 7.1 

 

 

 

0 p⁰ 1 p

Рис. 7.2

 

Метод Шепли-Сноу

 

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

Теорема (Шепли-Сноу). Все крайние оптимальные стратегии

p⁰  и q⁰  обоих игроков в игре с платежной матрицей ‖a_ij‖ и цена игры v

должны удовлетворять какой-либо из систем уравнений:

_å a_{i j} p_i2- v = 0, t = 1,..., r, _å p_i   = 1,   (1)

_å a_{i j} q_i2- v = 0, s = 1,..., r, _å q_i   = 1,   (2)

где a - квадратная матрица, полученная из матрицы a_ij   вычеркиванием некоторого количества строк и столбцов. Все остальные p⁰ и q⁰ с индексами, соответствующими вычеркнутым строкам и столбцам, равны нулю. При этом, если v ¹ 0 , то матрица a    невырождена.

s

По теореме Шепли-Сноу полное решение матричной игры сводится

к перебору всех квадратных подматриц матрицы игры и решению соответствующих систем линейных уравнений (1), (2). Если v ¹ 0 , то эти системы, очевидно, либо имеют единственное решение, либо не имеют решения. Полученное решение надо проверить на неотрицательность и на выполнение условий оптимальности (4), (3) для вычеркнутых строк и столбцов. Если условия выполнены, то решения системы, дополненные нулями на местах, соответствующих вычеркнутым строкам и столбцам, являются оптимальными стратегиями (но необязательно крайними, так как условия теоремы необходимые, но не достаточные). Полный перебор при- ведет к нахождению всех крайних оптимальных стратегий. Так как трудоемкость решения по методу Шепли-Сноу растет с увеличением размерности матрицы игры, то имеет смысл предварительно вычеркнуть в соответствии с принципом доминирования лишние строки и столбцы (если ищется полное решение, то при строгом доминировании), которые входят в оптимальные стратегии с нулевой вероятностью; цена игры при этом, очевидно, не меняется. Так как при решении системы линейных уравнений (1), (2) удобнее оперировать с невырожденной подматрицей a

s t

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

Метод Брауна

При достаточно большой размерности матрицы игры метод Шепли- Сноу приводит к решению больших систем линейных уравнений, что представляет собой весьма трудоемкий и не просто реализуемый вычисли- тельный процесс. Метод Брауна является более простым и удобным для численной реализации. Идея метода Брауна, с помощью которого можно получить лишь приближенное частное решение игры (т.е. по одной опти- мальной стратегии игроков), состоит в следующем.

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

На первом шаге игроки выбирают произвольные чистые стратегии i₁

и j₁ , ничего не зная о выборе противника.

На втором шаге игроки узнают предыдущий выбор противника и считают, что он и на втором шаге будет придерживаться той же стратегии. Тогда игрок 1 в соответствии со своим критерием выберет такую чистую стратегию i₂ , что       ^ai j= max a_ij   ,

а игрок 2 выберет такую чистую стратегию j₂ , что

^ai j= min ^ai j

На третьем шаге игрок 1 считает, что игрок 2 может использовать

чистые стратегии 1 j и 2 j с равной вероятностью, и выбирает чистую стратегию i 3, которая максимизирует математическое ожидание выигрыша.

Аналогично, игрок 2 считает, что игрок 1 может использовать чистые стратегии i₁ и i₂ с равной вероятностью, и выбирает чистую стратегию  j₃ , которая минимизирует математическое ожидание проигрыша:

На последующих шагах каждый игрок ориентируется на накоплен-

ную противником смешанную стратегию и выбирает свою чистую страте- гию из условия максимума или минимума соответствующего математиче-

ского ожидания. Обозначим через 

p_i (k ) 

и q _j (k) 

частоты появления i -й и

j -й чистых стратегий игроков в k повторениях; 

p_i (k ) = r_i / k, где r_i 

— чис-

ло появлений i -й стратегии игрока 1 

(i = 1,..., n) , 

q _j (k ) = l _j / k , где l _j    —

число появлений j -й стратегии игрока 2 

( j = 1,..., m) . Тогда на 

k + 1шаге

 

игрок 1 считает, что игрок 2 будет использовать смешанную стратегию

q(k) = (q₁ (k),..., q_m (k )) и выбирает чистую стратегию i_{k +1} такую, что

h(ik +1, q(k)) = max h(i, q(k )) . 

Аналогично, игрок 2 считает, что первый будет использовать сме-

шанную стратегию

и выбирает чистую стратегию j_k+1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Далее пересчитывают частоты по формулам

 

и переходят к следующей ( k + 2 )-й итерации.

Обозначим

Из утверждения следует 

v₁ (k ) ³ v ³ v₂ (k)"k ,

где v - цена игры, причем, если v₁ (k ) = v₂ (k) , то это общее значение есть цена игры,а p(k) и q(k) - оптимальные смешанные стратегии игроков.

Основное утверждение, на котором базируется метод Брауна, заклю- чается в сходимости сформулированного итеративного процесса:

практически вычисления по методу Брауна производят следующим образом. Задают точность решения если e > 0 и прекращают процесс после k шагов, если

При этом в качестве приближенного значения цены игры принимают величину

а e -оптимальными стратегиями игроков являются p(s₁ ) , где s₁ определяется из условия

и q(s₂ ) , где s₂ определяется из условия

Скорость сходимости итеративного процесса по методу Брауна уменьшается с увеличением размерности матрицы игры; ее порядок\

_{D(k ) = ck} -1/(n+m-2)

 

Если после конечного числа шагов выполняется равенство D(k ) = 0 ,

то  решение игры найдено точно.

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

Определение. Матричная игра называется симметричной, если ее платежная матрица ‖ a_ij‖ кососимметрическая, т.е.

                                                                    a_ij = -a _ji "i, j

 

Так как кососимметрическая матрица квадратная, то размерности векторов в смешанных стратегиях обоих игроков одинаковы (m = n) , а мно- жества всех смешанных стратегий совпадают. Свойство симметричных игр сформулировано в следующей лемме.