Согласно (2.3), седловой элемент    матрицы  А  одновременно минимален в строке 
i*  и максимален в столбце 
j*. Этот вывод можно использовать как рабочее правило для нахождения седловых точек.

         Вывод. Если матрица выигрышей имеет седловую точку  (
i*,
j*), то 
i*  и 
j* -  оптимальные стратегии первого и второго игрока, 
v =  - значение игры.

         Пример 2.1. Матрица

имеет две седловые точки (2, 1) и (3, 1) с седловым элементом 1. Решение игры  i* Î {2, 3}, j* = 1, v = 1.

         Пример 2.2. Матрица

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

2.2. Понятие смешанных стратегий. Чтобы понять суть смешанных стратегий, обратимся к примеру 1.2 игры в орлянку с матрицей выигрышей
.
Легко видеть, что матрица выигрышей не имеет седловых точек, поэтому оптимальные чистые стратегии игроков не существуют.

Изменим понятие решения игры так, чтобы оно оставалось приемлемым для игроков и обеспечивало разрешимость игры. Допустим, игроки выбирают свои чистые стратегии  i = 1, 2  и  j = 1, 2  случайно с вероятностями  x₁, x₂  и  y₁, y₂  соответственно. Тогда
,                                       (2.4)
.                                      (2.5)
Можно сказать, что игроки используют смешанные стратегии  x = (x₁, x₂),  y = (y₁, y₂), задавая их так, чтобы выполнялись условия (2.4), (2.5). Множества смешанных стратегий игроков обозначим соответственно  X  и  Y.

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

Таблица 2.1

Вероятности выигрышей первого игрока в игре орлянка

Ситуации	(1,1)	(1,2)	(2,1)	(2,1)
Выигрыши	+1	-1	-1	+1
Вероятности	x1y1	x1y2	x2y1	x2y2

Отсюда по известной из теории вероятностей формуле находим математическое ожидание  M(x, y)  выигрыша первого игрока
M(x, y) = (+1)x₁y₁ + (-1)x₁y₂ + (-1)x₂y₁ + (+1)x₂y₂.
Таким образом, за счет случайного выбора стратегий игроки переходят от первоначальной матричной игры  Г(А)  к новой антагонистической игре
Г.
Покажем, что новая игра имеет решение. Искомые оптимальные стратегии  x*, y*  должны составлять седловую точку функции  М  на  X × Y, т.е. удовлетворять неравенствам
M(x, y
*) ≤ M(x
*, y
*) ≤ M(x
*, y)
для всех смешанных стратегий  x, y. Преобразовав функцию выигрыша
M(x, y) = x₁(y₁ - y₂) - x₂ (y₁ - y₂) = (x₁ - х₂) (y₁ - y₂),
перепишем условия для седловой точки в виде
(x₁ - х₂) (y₁* - y₂*) ≤ (x₁* - х₂*) (y₁* - y₂*) ≤ (x₁* - х₂*) (y₁ - y₂).             (2.6)
Множители  x₁ - х₂  и  у₁ - у₂  на множествах  Х  и  Y  могут независимо принимать значения разных знаков, поэтому неравенства (2.6) удовлетворяются лишь при
x₁* - х₂* = 0,   y₁* - y₂* = 0.
Отсюда с учетом (2.4), (2.5) находим  x₁* = х₂* = y₁* = y₂* = . Следовательно, решение игры в смешанных стратегиях имеет вид
x* = (,),   y* = (,),   M(x
*, y
*) = 0.
2.3. Смешанное расширение матричной игры. После разобранного примера становится понятным формальный переход от матричной игры  Г(А)  с матрицей выигрыша  А  вида (2.1) к новой антагонистической игре  Г с множествами стратегий  , заданными условиями
,                        (2.7)
,                        (2.8)
и функцией выигрышей
.
         Цель перехода прежняя – добиться разрешимости игр, в которых матрицы выигрышей не имеют седловых точек. Прежней остается и содержательная интерпретация элементов новой игры: х
_i  и  y_j – вероятности выбора первым и вторым игроком чистых стратегий  i  и  j  соответственно,  - математическое ожидание выигрыша первого игрока в ситуации  .

         В дальнейшем удобно пользоваться векторно-матричной формой записи функции выигрышей. Условимся здесь и далее считать все векторы в формулах столбцами и использовать знак штрих (´) для обозначения транспонирования. Тогда
.                                                 (2.9)
Действительно, в принятых соглашениях по правилам перемножения матриц имеем



         Смешанное расширение  Г  включает в себя исходную матричную игру  Г(А). В самом деле, если ввести специальные смешанные стратегии
,   ,           (2.10)
у которых  i-я и  j-я координаты векторов соответственно равны 1,то
,
т.е. вектора (2.10) в игре  Г  аналогичны чистым стратегиям в игре Г(А).

         Разрешимость игры  Г  в смешанных стратегиях сразу же вытекает из теоремы 1.4. Действительно, в данной игре множества    стратегий, заданные условиями (2.7), (2.8), выпуклые и замкнутые и функция выигрышей (2.9) непрерывная и вогнуто-выпуклая на  X × Y. Поэтому по теореме 1.4 наилучшие гарантированные выигрыши игроков существуют и равны. Сформулируем полученный вывод в такой форме.

         Теорема 2.1 (Дж. фон Нейман). Каждая матричная игра разрешима в смешанных стратегиях.

         Этот факт установлен в 1929 году. Теорему 2.1 часто называют основной теоремой матричных игр.

         Остановимся в заключение на практическом значении смешанных стратегий. Допустим, матричная игра  Г(А)  не имеет решения в чистых стратегиях, и игрокам известно ее решение  x*, y*, v  в смешанных стратегиях. Как они должны ими руководствоваться при выборе чистых стратегий? Очевидно, если игра разыгрывается один раз, то практическая польза от смешанных оптимальных стратегий, вообще говоря, не велика. Однако, положение меняется при многократном розыгрыше игры. Пусть она играется  N  раз и  каждый раз игроки выбирают свои чистые стратегии  i, j, ориентируясь на соответствующие координаты  x_i*, y_j*  оптимальных смешанных стратегий. Это значит, что за  N  розыгрышей чистые стратегии  i  и  j  должны применяться соответственно    и    раз так, чтобы частота выбора чистых стратегий была близка расчетным вероятностям
;   .
Если при    все приближенные равенства становятся точными, то среднее арифметическое    выигрышей первого игрока за  N  розыгрышей стремится к значению  v  игры. Это непосредственно следует из определения математического ожидания. Итак, если при достаточно большом количестве розыгрышей матричной игры игроки выбирают чистые стратегии с предписанными оптимальными вероятностями, то среднее арифметическое их выигрышей будет близко значению игры. В этом и состоит практическая польза смешанных стратегий.

2.4. Признаки оптимальности стратегий. Установим вначале один вспомогательный факт.

         Лемма 2.1 (о переходе к смешанным стратегиям). Если смешанная стратегия 
y  и число 
b  таковы, что справедливы неравенства
,                                      (2.11)

то

                                                    (2.12)
для любой смешанной стратегии  х.

         Доказательство. Пусть выполнены неравенства (2.11). Тогда для любой смешанной стратегии  х  со свойствами (2.7) имеем
.
Суммируя данные неравенства, получим

что с учетом равенства (2.7) равносильно (2.12). Лемма доказана.

         Аналогично проверяются импликации, которые тоже будем относить к лемме 2.1:
;
;
.
         Игровой смысл леммы 2.1 достаточно очевиден. Если при некоторой фиксированной стратегии второго игрока любая чистая стратегия первого игрока приносит ему выигрыш не больше  b, то он не может добиться большего выигрыша, переходя к смешанным стратегиям. Таким же образом трактуются и остальные импликации.

         Теорема 2.2. Для того, чтобы стратегии  х*, у*  и число 
v  были решением игры 
Г  необходимо и  достаточно выполнения неравенств
.               (2.13)
         Доказательство. Необходимость. Пусть тройка  х*, у*,
v – решение игры, т.е.
                                  (2.14)
для любых стратегий  х, у  и  . Отсюда и из (2.14) при    вытекает (2.13).

         Достаточность. Пусть некоторые стратегии  х*, у*  и число 
v  удовлетворяют неравенствам (2.13). Покажем, что они образуют решение игры  Г. Переходя в неравенствах (2.13) к смешанным стратегиям (лемма 2.1), получим
                                             (2.15)
для любых стратегий  х, у. В частности, полагая здесь  х = х*,  у = у*, находим  . Следовательно, неравенство (2.15) можно представить в виде (2.14), что свидетельствует об оптимальности стратегий  х*, у*. Тогда число    есть значение игры  Г. Теорема доказана.

         Покажем, как пользоваться критерием оптимальности (2.13).

         Пример 2.1. Убедимся, что тройка
                             (2.16)
составляет решение игры с матрицей
.
         Предварительно заметим, что множители  в критерии оптимальности (2.13) есть  i-я строка и  j-й столбец матрицы  А. Следовательно, выражения   - это скалярные произведения  i-й строки и  j-го столбца матрицы  А  на стратегии  x*  и  y*  соответственно. Пользуясь этими замечаниями, находим


Составим из найденных чисел и числа  v  «символическое» неравенство типа (2.13):
.
Видно, что обычные неравенства справедливы при любом выборе чисел в левой и правой колонке. Следовательно, критерий оптимальности (2.13) выполняется и тройка (2.16) есть решение игры.

         Теорема 2.3. Пусть 
v – значение игры  . Тогда справедливы два утверждения:

1)   
стратегия  х*  оптимальна тогда и только тогда, когда


;                                  (2.17)



2)   
стратегия  у*  оптимальна тогда и только тогда, когда


.


         Доказательство проведем для первого утверждения. Необходимость условия (2.17) вытекает из теоремы 2.2, поэтому осталось установить его достаточность. Пусть неравенства (2.17) верны для некоторой стратегии  х*. Переходя в (2.17) на основании леммы 2.1 к смешанным стратегиям, получим


                                                (2.18)



для любой стратегии  у. По теореме Дж. фон Неймана игра  Г  имеет решение  . По определению решение удовлетворяет неравенствам


                                        (2.19)



для любых стратегий  х, у. Полагая, в частности, в (2.18)    и в (2.19)  х = х*, имеем


.


Следовательно, неравенства (2.19) с учетом (2.18) можно записать в виде


.


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

         Теорема 2.4 (о дополняющей нежесткости). Пусть 
v – значение игры 
Г. Если некоторая оптимальная стратегия  х* первого игрока имеет координату  , то любая оптимальная стратегия  у*  второго игрока удовлетворяет равенству


.                                              (2.20)


Аналогично, если имеется оптимальная стратегия  у* второго игрока с координатой  , то любая оптимальная стратегия  х*  первого игрока удовлетворяет равенству


.


         Доказательство. Допустим противное: посылка первого утверждения теоремы верна, а заключение (2.20) не верно. Тогда в силу теоремы 2.3 найдется такая оптимальная стратегия  у*, для которой справедливо строгое неравенство  . Используя это неравенство и теорему 2.3, получим



что невозможно. Следовательно, для любой оптимальной стратегии  у*  второго игрока возможно лишь равенство (2.20). Второе утверждение теоремы устанавливается точно так же. Теорема доказана.

         Обращая утверждение теоремы, получим

         Следствие 2.1. Если  , то  . Если  , то  .

2.5. Свойства значения игры. Нам понадобится вспомогательная

         Лемма 2.2 (о переходе к дискретным экстремумам). В матричной игре  Г  для произвольных стратегий  х, у  верны равенства


,                (2.21)
(вычисление экстремумов ведется по всем соответствующим чистым и смешанным стратегиям).

         Доказательство. Поскольку вектора  eⁱ, i = 1,2,…,m являются стратегиями, то при любом    имеем
.
Отсюда с помощью леммы 2.1 о переходе к смешанным стратегиям получим
,
где  х - произвольная стратегия. Усиливая данное неравенство на основании теоремы Вейерштрасса, можем написать
.
Тем самым первое равенство (2.21) установлено. Второе проверяется аналогично. Теорема доказана.

         Записывая формулы для значения матричной игры с использованием соотношений (2.21), получим

         Следствие 2.2. Значение игры  Г  можно вычислять по упрощенным формулам
.
         Следствие 2.3. Для значения  игры  Г  справедливы оценки
.
         Действительно, в силу свойств экстремумов и следствия 2.1 имеем
.
Осталось заметить, что  .

2.6. Соотношения превосходства. Доминирование (превосходство) строк или столбцов матрицы выигрышей позволяет сделать некоторые заключения об оптимальных стратегиях игроков и, в конечном счете, упростить матричную игру. Введем понятие доминирования. Говорят, что вектор    доминируется вектором   и пишут  , если
.                            (2.22)
Если все неравенства (2.22) строгие, то говорят о строгом доминировании  вектора  а  вектором  b  и записывают  . Далее, вектор

называют выпуклой комбинацией векторов  , если
.
Числа    называют коэффициентами выпуклой комбинации.

         Теорема 2.5 (о доминировании строк). Пусть
i-я строка матрицы  А  строго доминируется выпуклой комбинацией других строк. Тогда в любой оптимальной стратегии  х*  первого игрока  координата  х
_i*= 0.

         Доказательство. Считаем для простоты  i = m  и
,                            (2.23)
где  - коэффициенты выпуклой комбинации. Допустим, что найдется оптимальная стратегия  х*  первого игрока, в которой  х
_m*. Тогда по теореме 2.4любая оптимальная стратегия  у*  второго игрока удовлетворяет равенству
,
где  v – значение игры  Г. Отсюда в координатной записи с учетом (2.23) имеем
.
Усилим последнее неравенство, пользуясь свойством

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

Точно так же проверяется справедливость аналогичного утверждения.

         Теорема 2.6 (о доминировании столбцов). Пусть выпуклая комбинация некоторых столбцов матрицы  А  строго доминируется ее 
j-м столбцом Тогда в любой оптимальной стратегии 
y*  второго игрока  координата 
y_j*= 0.

         Согласно теореме 2.5, первый игрок выбирает доминируемые строки с нулевыми вероятностями. Другими словами, он может не принимать их во внимание и просто вычеркнуть из матрицы выигрышей. Та же ситуация с «превосходящими» столбцами матрицы, которые игнорируются (вычеркиваются) вторым игроком. В результате вычеркивания строк и столбцов размерность матрицы выигрышей понижается и решение игры упрощается.

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

         Пример 2.3. В матрице

последняя строка строго доминируется выпуклой комбинацией первых двух строк с указанными рядом коэффициентами. По теореме 2.5 матрицу выигрышей можно упростить

и искать оптимальные стратегии игроков в виде  .

         Использование нестрогого доминирования может приводить к потери решений матричной игры.

         Пример 2.4. В игре с матрицей