Матричные игры с нулевой суммой. Платежная матрица игры

   Смешанные  стратегии,  избранные  игроками, называются  оптимальными, если одностороннее отклонение любым игроком от своей оптимальной стратегии может изменить средний выигрыш только в сторону, невыгодную для этого игрока.

   Совокупность, состоящая из оптимальной стратегии  одного игрока и оптимальной стратегии  другого игрока, называется решением игры.

   Средний  выигрыш V при применении обоими игроками оптимальных стратегий называется  ценой  игры. 

   Стратегии, входящие с ненулевыми частотами в оптимальную стратегию игрока, называются  полезными. 

     В  1928  году  фон  Нейманом была доказана  основная  теорема  теории игр, утверждающая, что каждая игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий.

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

Следствие 1.   Любая игра имеет цену. 

Следствие 2.   Цена игры удовлетворяет неравенству ≤ V≤ .

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

§ 6. Аналитический метод решения игры типа  2 x 2

     Рассмотрим  игру без седловой точки типа  2 x 2 с платежной матрицей

C =

и найдем оптимальную стратегию

=

игрока  A. Согласно следствию 3 из основной теоремы теории игр эта стратегия обеспечивает игроку A выигрыш, равный цене игры V, даже если игрок B не выходит за пределы своих полезных стратегий. В данной игре обе чистые стратегии игрока B являются полезными, поскольку в противном случае игра имела бы решение в области чистых стратегий, т.е. была бы игрой с седловой точкой. 

     Отсюда  вытекает, что неизвестные  удовлетворяют следующей системе из трех линейных уравнений

     

решение которой имеет вид

     

     Аналогичным образом  можно  найти оптимальную  стратегию

     

 
 

игрока  B. В этом случае  неизвестные удовлетворяют системе уравнений

решение которой имеет вид

     Применим  теперь полученные формулы к карточной  игре типа "веришь  -  не веришь".

     Пример 6.1.  Имеются две карты: туз и двойка. Игрок А наугад берет одну из них. Если А взял туза, то он заявляет: "У меня туз" и требует у противника рубль. Если же  А взял двойку, то он может либо сказать: "У меня туз" и потребовать рубль, либо признаться, что у него двойка и заплатить рубль. Игрок В, если ему предлагают рубль, берет его. Однако, если у него требуют рубль, то В может либо поверить, что у А туз, и заплатить рубль, либо не верить и потребовать проверки. Если в результате проверки окажется, что у А действительно туз, то В платит 2 рубля. Если же выяснится, что у А была двойка, то А платит 2 рубля.

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

     Решение.  У игрока A есть 2 стратегии: − обманывать, − не обманывать. У игрока В тоже есть 2 стратегии: − верить, −не верить. Это позволяет найти все элементы платежной матрицы игры, вычислив средний выигрыш для каждой комбинации стратегий.

     1.  Комбинация (А обманывает, В верит).

     Если  А берет туза (вероятностью этого 0,5), то он требует рубль. В верит ему и платит. Если А берет двойку (вероятность этого также 0,5), то он обманывает и тоже требует рубль. В верит ему и платит. Средний выигрыш А равен

     2.   Комбинация  (А обманывает, В не верит).

     Если  А берет туза, то он требует рубль, а В не верит и после проверки платит  2 рубля. Если же  А взял двойку, то он обманывает и тоже требует рубль. В не верит ему, и в результате А платит 2 рубля. Средний выигрыш А равен

     3.   Комбинация  (А не обманывает, В верит).

     Если  А берет туза, то он требует рубль, В платит 1 рубль. Если А берет двойку, то он сообщает об этом и платит рубль. Средний выигрыш А равен

     4.   Комбинация (А не обманывает, В не верит).

     Если  А берет туза, то он требует рубль,  В проверяет и платит 2 рубля. Если А берет двойку, то он сообщает об этом и платит рубль. Средний выигрыш А равен  

     Отсюда  вытекает, что платежная матрица  имеет вид

     

и можно  найти нижнюю и верхнюю цены игры:

     Следовательно, игра не имеет седловой точки, и ее решение нужно искать в области смешанных стратегий. Для этого воспользуемся формулами, полученными выше:         

     

Следовательно, смешанная стратегия игрока A имеет вид

=

Далее получаем

=

     Таким образом, оптимальным для А будет в одной трети случаев обманывать, а в двух третях случаев - не обманывать. Такая тактика обеспечит ему средний выигрыш, равный V = 1/3. Если бы А стал пользоваться своей максиминной стратегией, то его выигрыш был бы равен = 0 . Для В оптимальная стратегия - это в одной трети случаев верить А и платить ему рубль, а в остальных случаях требовать проверки. В этой ситуации его средний проигрыш составит 1/3 , тогда как при применении минимаксной стратегии он будет проигрывать в среднем = 0,5.

     Значение  V = 1/3 показывает, что рассмотренная игра выгодна для А и невыгодна для В, поскольку, пользуясь своей оптимальной стратегией, A всегда может обеспечить себе положительный средний выигрыш. 
 
 
 

§ 7. Графический метод решения игр типа 2 n и m 2

     Рассмотрим  игру типа 2 n с платежной матрицей

     

и проведем через точку (1; 0) координатной плоскости  Oxy прямую l, перпендикулярную оси абсцисс. После этого для каждой из стратегий                  (i =1,2,...,n) проведем прямую

соединяющую точку (0; ) на оси Оу с точкой (0; ) на прямой l. Ось Оу отвечает за стратегию , а прямая l - за стратегию .

Если  игрок А применяет смешанную стратегию

=

то его  выигрыш в случае, если противник  применяет чистую стратегию  , равен

и этому  выигрышу соответствует точка  М на прямой с абсциссой x = .

     Ломаная , отмеченная на чертеже жирной линией, позволяет определить минимальный выигрыш игрока А при любом поведении игрока В. Точка N, в которой эта ломаная достигает максимума, определяет решение и цену игры. Ордината точки N равна цене игры V, а ее абсцисса - частоте применения стратегии в оптимальной смешанной стратегии игрока А.

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

     

     Частоты в оптимальной стратегии

     

игрока В определяются из соотношения

  

     Замечание. Иногда точка N не является пересечением двух стратегий, а попадает на одну из прямых х = 0 или х = 1 . В этом случае решением игры будут соответствующие чистые стратегии.

     Для игры m 2 решение находится совершенно аналогично. Действительно, поскольку выигрыш игрока А одновременно является проигрышем игрока В, то для решения задачи нужно построить ломаную, соответствующую верхней границе выигрыша игрока А, а затем найти на ней точку с минимальной ординатой.

     Пример 7.1.  Пусть игра задана матрицей

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

Решение.

     Проведем  прямые , и построим ломаную линию , соответствующую нижней границе выигрыша. Точка N, в которой эта ломаная достигает максимума, является пересечением прямых

   и   .

Вычислив  координаты точки N: , получаем оптимальную стратегию игрока А

и цену V = 27/7. Так как точка N является пересечением прямых и , то полезными стратегиями игрока В будут стратегии и . Найдем частоты их применения и , зная, что выигрыш равен цене игры, если игрок В применяет оптимальную стратегию, а игрок А - любую из своих полезных стратегий, например, стратегию :

Ответ.    
 

     Пример 7.2. Пусть игра задана матрицей

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

      Решение.

     Воспользовавшись  тем, что игрок B располагает двумя чистыми стратегиями, построим прямые , соответствующие выигрышам игрока А при чистых стратегиях , и ломаную линию , огибающую график сверху. Эта ломаная достигает минимума вточке , которая является пересечением прямых

     

Следовательно, = 0,6; V = 7,2, и оптимальной стратегией игрока В является стратегия

Цена  игры V = 7,2 . Полезными стратегиями игрока А являются стратегии и . Найдем их частоты и :

      Ответ.