Элементы теории игр

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

.

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

.

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

= ,

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

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

,

либо

. 

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

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

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

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

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

.

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

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

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

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

;

.

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

откуда

 

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

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

Пример 1.

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

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

      

      y 
 

     11 
 
 
 

                                                    7  

                      М                  N            5

                    

      3

      2                                 u              2

                       

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

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

2х₁ + 6(1 - х₂) = u₁

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

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

.

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

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

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

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

 
 
 
 
 
 
 

         x                                                     8

                                                             7

        6                                К                     6

 

                                                              5

        4 
 

                                        u 

        2 

        1 

                    y 

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

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

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

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

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

                      

                      

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

   ,      ,

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

,   ,   ,   ,

,   ,   ,   .

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

,  .