Матричные игры

Свойство 3. Пусть G = (Х,Y,А) – конечная антагонистическая игра, Gў = (Х \ хў,Y,А) – подыгра игры G, а хў – чистая стратегия игрока 1 в игре G, доминируемая некоторой стратегией , спектр которой не содержит хў. Тогда всякое решение (хо, yо, u) игры Gў является решением игры G.

Свойство 4. Пусть G = (Х,Y,А) – конечная антагонистическая игра, Gў = (Х,Y \ yў,А) – подыгра игры G, а yў – чистая стратегия игрока 2 в игре G, доминируемая некоторой стратегией , спектр которой не содержит yў.Тогда всякое решение игры Gў является решением G.

Свойство 5. Если для чистой стратегии хў игрока 1 выполнены условия свойства 3, а для чистой стратегии yў игрока 2 выполнены условия свойства 4, то всякое решение игры Gў = (Х \ хў,Y \ yў,А) является решением игры G = (Х,Y,А).

Свойство 6. Тройка (хо, yо, u) является решением игры G = (Х,Y,А) тогда и только тогда, когда (хо, yо, кu +а) является решением игры G(Х,Y,кА+а), где а – любое вещественное число, к > 0.

Свойство 7. Для того, чтобы хо = ( ) была оптимальной смешанной стратегией матричной игры с матрицей А и ценой игры u, необходимо и достаточно выполнение следующих неравенств

 

 (j = )

 

Аналогично для игрока 2: чтобы yо = ( ,..., ,..., ) была оптимальной смешанной стратегией игрока 2 необходимо и достаточно выполнение следующих неравенств:

 

 (i = )

 

Из последнего свойства вытекает: чтобы установить, является ли предполагаемые (х, y) и u решением матричной игры, достаточно проверить, удовлетворяют ли они неравенствам (*) и (**). С другой стороны, найдя неотрицательные решения неравенств (*) и (**) совместно со следующими уравнениями

 

,

 

получим решение матричной игры.

Таким образом, решение матричной игры сводится к нахождению неотрицательных параметров решений линейных неравенств (*) (**) и линейных уравнений (***). Однако это требует большого объёма вычислений, которое растёт с увеличением числа чистых стратегий игроков. (Например для матрицы 3 3 имеем систему из 6 неравенств и 2 уравнений). Поэтому в первую очередь следует, по возможности используя свойства 2 и 3, уменьшить число чистых стратегий игроков. Затем следует во всех случаях проверить выполнение неравенства

 

= .

 

Если оно выполняется, то игроки имеют чистые оптимальные стратегии (игрок 1 – чистую максиминная, а игрок 2 – чистую минимаксная). В противном случае хотя бы у одного игрока оптимальные стратегии будут смешанные. Для матричных игр небольшого размера эти решения можно найти, применяя свойства 1 – 5.

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

Пример 3. Пусть G = (Х,Y,А), где Х = {1, 2, 3, 4}; Y = {1, 2, 3, 4}, а функция выигрыша А задана следующим образом :

 

 

где С > 0.

Решение. Прежде всего заметим, что по свойству 6 достаточно решить игру G1 = (Х,Y,А), где А1 = А. В матричной форме игра G1 определяется матрицей выигрышей

 

 

Элементы четвёртой строки этой матрицы “Ј” соответствующих элементов третьей строки и поэтому третья стратегия игрока 1 доминирует над четвёртой. Кроме того, элементы первого столбца матрицы А1 “і” соответствующих элементов второго столбца, Следовательно, вторая стратегия игрока 2 доминирует над его первой стратегией.

Далее, из свойства 5 следует, что всякое решение игры G2 = (Х \ {4}, Y \ {1}, А1) является решением игры G1. В матричной форме игру G2 можно представить матрицей

 

.

 

Очевидно, что элементы второй строки “і” полусуммы соответствующих элементов первой и третьей строк. Кроме того, элементы третьего столбца матрицы А2 “і“ соответствующих элементов второго столбца. Применяя свойство 5 получим, что всякое решение игры G3 = (Х \ {4,2}, Y \ {1,4}, А2) является решением игры G2, а следовательно и игры G1. Игра G3 определяется матрицей

 

.

 

Матрица А3 не имеет седловой точки, т.к. не выполнено равенство

 

= ,

 

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

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

,

либо

.

Аналогично, если игрок 2 использует свои чистые стратегии 2 и 3 с равными вероятностями, то математическое ожидание его проигрыша будет равно . Следовательно, указанные стратегии являются оптимальными в игре G3, а величины – значением игры G3. Из предыдущего следует, что эти стратегии оптимальны и в G1.

Таким образом, стратегия Х = ( , 0, , 0) является оптимальной стратегией игрока 1, стратегия Y = (0, , , 0) – оптимальной стратегией игрока 2 в игре G1, а значение игры G1 равно . В силу свойства 4 решением игры G будет тройка (Х,Y, ).

 

 

3. Игры порядка 2 х 2

 

В общем случае игра 2 2 определяется матрицей

 

 

Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение в чистых стратегиях, причём оптимальными стратегиями игроков 1 и 2 соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет чистых стратегий, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями. В противном случае один из игроков (например 1) имеет чистую оптимальную стратегию, а другой – только смешанные. Не ограничивая общности, можно считать, что оптимальной стратегией игрока 1 является выбор с вероятностью 1 первой строки. Далее, по свойству 1 следует, что а11 = а12 = u и матрица имеет вид

 

.

 

Легко видеть, что для матриц такого вида одна из стратегий игрока 2 является доминируемой. Следовательно, по свойству 4 этот игрок имеет чистую стратегию, что противоречит предположению.

Пусть Х = (x, 1 - x) – оптимальная стратегия игрока 1. Так как игрок 2 имеет смешанную оптимальную стратегию, из свойства 1 получим, что (см. также свойство 7)

 

 

Отсюда следует, что при u № 0 столбцы матрицы А не могут быть пропорциональны с коэффициентом пропорциональности, отличным от единицы. Если же коэффициент пропорциональности равен единице, то матрица А принимает вид

 

 

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

 

;

.

 

Аналогичные рассуждения приводят нас к тому, что оптимальная стратегия игрока 2 Y = (h, 1 - h) удовлетворяет системе уравнений

 

 

 

откуда

 

.

 

3.1 Графический метод решения игр 2 х n и m х 2

 

Поясним метод на примерах.

Пример 1.

Рассмотрим игру, заданную платёжной матрицей.

 

 

На плоскости хОy введём систему координат и на оси Ох отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (х, 1 - х). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.

В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки Вў1, В2ў, В3ў на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и Вў1, В2 и Вў2, В3 и Вў3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий. Например, расстояние от любой точки отрезка В1Вў1 до оси 0х определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами х и 1–х) и стратегией В1 игрока 2. Это расстояние равно

 

2х1 + 6(1 - х2) = u1

 

(Вспомните планиметрию и рассмотрите трапецию А1 B1 Bў1 A2). Таким образом, ординаты точек, принадлежащих ломанной В1 M N Вў3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (х, 1-х), а её ордината равна цене игры u. Координаты точки N находим как точку пересечения прямых В2 Bў2 и В3 Bў3.

Соответствующие два уравнения имеют вид

 

.

 

Следовательно, Х = ( ; ), при цене игры u = . Таким образом мы можем найти оптимальную стратегию при помощи матрицы .

Оптимальные стратегии для игрока 2 можно найти из системы

 

 

 

И, следовательно, Y = (0; ; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.

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

 

 

Решение. Матрица имеет размерность 2 х 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная А1 K Аў4 соответствует верхней границе выигрыша игрока 1, а отрезок N K –цене игры. Решение игры таково

U = ( ; ); Х = ( ; 0; 0; ); u = .

 

3.2 Сведение матричной игры к задаче линейного программирования

 

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

Итак, пусть дана матричная игра с матрицей А порядка m х n. Согласно свойству 7 оптимальные смешанные стратегии х = (х1,..., хm), y = (y1,..., yn) соответственно игроков 1 и 2 и цена игры u должны удовлетворять соотношениям.

 

 

 

Разделим все уравнения и неравенства в (1) и (2) на u (это можно сделать, т.к. по предположению u > 0) и введём обозначения:

 

  , ,

 

Тогда (1) и (2) перепишется в виде:

 

, , , ,

, , , .

 

Поскольку первый игрок стремится найти такие значения хi и, следовательно, pi, чтобы цена игры u была максимальной, то решение первой задачи сводится к нахождению таких неотрицательных значений pi , при которых

 

, .

 

 

Поскольку второй игрок стремится найти такие значения yj и, следовательно, qj, чтобы цена игры u была наименьшей, то решение второй задачи сводится к нахождению таких неотрицательных значений qj, , при которых

 

, .

 

Формулы (3) и (4) выражают двойственные друг другу задачи линейного программирования (ЛП).

Решив эти задачи, получим значения pi , qj и u.Тогда смешанные стратегии, т.е. xi и yj получаются по формулам:

 

 

 

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

 

 

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

 

 

Составим теперь пару взаимно-двойственных задач:

 

 

 

Решим вторую из них

 

Б.п.	q1	q2	q3	q4	q5	q6	Решение	е	Отношение
	-1	-1	-1	0	0	0	0	-3
q4	1	2	0	1	0	0	1	5	--
q5	1	0	1	0	1	0	1	4
q6	2	1	0	0	0	1	1	5	--

 

Б.п.	q1	q2	q3	q4	q5	q6	Решение	е	Отношение
	0	-1	0	0	1	0	1	1
q4	1	2	0	1	0	0	1	5
q3	1	0	1	0	1	0	1	4	--
q6	2	1	0	0	0	1	1	5

 

Б.п.	q1	q2	q3	q4	q5	q6	Решение	е	Отношение
		0	0		1	0
q2		1	0		0	0
q3	1	0	1	0	1	0	1	4
q6		0	0		0	1

 

Из оптимальной симплекс-таблицы следует, что (q1, q2, q3) = (0; ; 1), а из соотношений двойственности следует, что (p1, p2, p3) = ( ; 1; 0).