Теория игр

 

 

Составим  из найденных чисел и числа  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. В игре с матрицей