Теория игр (стр. 3 из 5)
Аналогично для игрока 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, 
).Игры порядка 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) удовлетворяет системе уравнений