Р авновесие по Нэшу в смешанных стратегиях.

     

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

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

 

Пример 1.Отсутствие равновесия в чистых стратегиях

             Т а б л и ц а 2.9                                       Т а б л и ц а 2.10

          Матрица А                                    Матрица В

 

    У игроков отсутствуют доминирующие стратегии и в результате графического  анализа доминирования приходим к случаю, когда в соответствующих клетках платежных матриц отсутствуют одновременно выделенные элементы (см. та б л. 2.9 и та б л. 2.10), что иллюстрирует отсутствие равновесия по Нэшу в чистых стратегиях.

Здесь рассматриваются биматричные  одноходовые игры размерности , в которых игроки делают ходы одновременно. Такие игры могут повторяться много раз,  но  в рассматриваемой постановке считается, что какой бы раз не повторялась данная игра, платёжная матрица остаётся неизменной и поэтому не изменяются оптимальные решения, то есть время не влияет на поведение игроков и на выбор оптимальных стратегий (именно поэтому такие игры еще называются статическими).

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

Теорема Нэймана.

Если биматричная игра не имеет решения (оптимума) в чистых стратегиях, то она  имеет  по крайней мере одно равновесие в смешанных стратегиях.

 

Перейдём к поиску решения игры в смешанных стратегиях.

Смешанные стратегии первого игрока

= , где , , .

Смешанные стратегии второго игрока 

= , где , , .

       Если какая либо стратегия выбирается игроком с вероятностью равной единице, то матрицы выбора смешанных стратегий вырождаются в матрицы выбора чистых стратегий.

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

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

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

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

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

где значение   –  выигрыш второго игрока, при условии, что он выбрал первую стратегию, а значение   –  выигрыш второго игрока, при условии, что он выбрал вторую стратегию.

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

или   –  вторую стратегию           .

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

.

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

 

где значение   –  выигрыш первого игрока, при условии, что он выбрал первую стратегию, а значение   –  выигрыш первого игрока, при условии, что он выбрал вторую стратегию.

    Найдём средние выигрыши обоих игроков при использовании ими смешанных стратегий  и , первого

 

и второго

 

    Задача выбора оптимальных смешанных стратегий, обеспечивающих максимизацию выигрышей каждого из игроков представляется в виде совокупности условий и ограничений, которая формулируется как задача линейного программирования:

 

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

 

Определение.           Пара смешанных стратегий     и     игроков  называется равновесием по Нэшу в смешанных стратегиях, если ни одному из игроков невыгодно отклоняться от этих стратегий в одиночку, т.е. когда для любых   и     верно

    и   ,

 при условии, что     и .

  2.5. Аналитический метод решения биматричной игры 2  2

 

При высоких размерностях платежных матриц () оптимальное решение находят численными методами. При минимальной

(2  2) размерности биматричной игры оптимальное решение в смешанных стратегиях можно найти аналитически.

    Воспользуемся полученными в п. 3.1.4. выражениями для средних выигрышей первого и второго игроков, при смешанных стратегиях =  и = , соответственно

,

 

.

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

и второго игроков

.

Откуда находим

и

.

Продифференцируем полученные выражения  и  по переменным и , соответственно,

,

.

Координаты  и , обеспечивающие максимальные значения функциям средних выигрышей  и  найдем, приравняв нулю частные производные

,

.

Замечание 1.   Равенство нулю первой производной даёт условие критической точки, которая отражает необходимое, но вовсе не достаточное условие экстремума, которым может быть как минимум, так и максимум. В данной задаче не требуется дополнительных исследований достаточности и именно максимума, всё это гарантирует теорема Дж. Нэймана.

    Решая полученные уравнения, найдем выражения для оптимальной по Нэшу смеси стратегий в биматричной игре

,              ,

,                   .

Замечание 2. Из полученных формул видно, что хотя бы одна из величин , , или   может оказаться отрицательной. Это означает, что существует решение в чистых стратегиях.

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

 

2.6. Графический метод решения биматричной игры 2  2

 

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

Сформулированные в п. 3.1.4, определяющие ситуацию равновесия,

условия выглядят следующим образом

        или   

Таким образом, равновесная ситуация определяется парой смешанных стратегий , , удовлетворяющих системе неравенств

 

которая приводится к виду

  

 

Дальнейшее решение ищем, при совокупности ограничений

 

 Приемлемые решения для второго игрока находятся как решение системы неравенств

 

Рассмотрим следующие три ситуации.

1) = 0 и система принимает вид

Разделив на выражение , обе части первого неравенства, с учетом обозначения , полу-чим два случая (в зависимости от знака делителя).

Случай 1.1 (см. рис. 3.1).                               Случай 1.2 (см. рис. 3.2).          

    или      

 

                  

 

             Рис. 2.1                                                                              Рис. 2.2   

 

2) = 1 и система принимает вид

          

Разделив обе части второго неравенства на выражение , с учетом обозначения , получим два случая (в зависимости от знака делителя).

Случай 2.1 (см. рис. 3.3).                                  Случай 2.2 (см. рис. 3.4).         

   или        

 

              

 

          Рис. 2.3                                                                             Рис. 2.4   

     

3) В случае , разделив обе части первого неравенства

 на выражение , и обе части второго неравенства

на , переходим к одной из следующих систем

     или       

Поскольку системе    удовлетворяет единственное значение , то, вне зависимости от знака выражения (),

в последнем случае получаем систему  графическое решение которой представлено на рис. 3.5.

 

Рис.2.5

  Объединяя три случая, а именно = 0, = 1 и , получаем множество решений для второго игрока,

представленное на рис. 3.6            или            представленное на рис. 3.7,

при выполнении условия                                      при выполнении условия

,                               .

             

             Рис. 2.6                                                                     Рис. 2.7                         

 

Переходим к поиску решений для первого игрока, которые находятся как решение следующей системы

Рассмотрим следующие три ситуации.

4)  = 0 и система принимает вид

       

Разделив обе части первого неравенства на выражение , в зависимости от знака делителя, с учетом обозначения , получим два случая.                                     

Случай 4.1 (см. рис. 3.8).                                      Случай 4.2 (см. рис. 3.9).                                                      

        или          

 

               

                Рис. 2.8                                                                   Рис. 2.9   

 

5) = 1 и система принимает вид

              

Разделив обе части второго неравенства на выражение , с учетом обозначения ,  получим два случая (в зависимости от знака делителя).

Случай 5.1 (см. рис. 3.10).                                 Случай 5.2 (см. рис. 3.11).                                                     

         или      

 

                   

 

            Рис. 2.10                                                                     Рис. 2.11   

 

6) В случае , разделив обе части первого неравенства

на выражение ,  и обе части второго неравенства

    на , переходим к одной из следующих систем

или   

Cистеме     удовлетворяет   единственное значение .

В случае   получаем систему графическое решение которой представлено на рис. 3.12.

                                                  Рис. 2.12

Объединяя три случая, а именно  = 0  , = 1 и , получаем множество решений для первого игрока,

представленное на рис. 3.13         или            представленное на рис. 3.14,

при выполнении условия                                      при выполнении условия

                                 .

                              

           Рис. 2.13                                                                           Рис. 2.14   

      

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

В первом случае (см. рис. 3.15),                 Во втором случае (см. рис. 3.16),

при выполнении условий  при выполнении условий                                                                      

налагая графики, изображенные                   налагая графики, изображенные

на рисунках рис. 3.6 и рис. 3.13,                       на рисунках рис. 3.6  и рис. 3.14,

находим точку К с координатами                 находим точку L с координатами

и .                                         и .  

             

           Рис. 2.15                                                                   Рис. 2.16

 В первом случае (рис. 3.15) общими точками являются также точка с координатами (0; 0) и точка с координатами (1; 1).

В третьем случае (см. рис. 3.17),                 В четвертом случае (см. рис. 3.18),

при выполнении условий  при выполнении условий                        

налагая графики, изображенные                   налагая графики, изображенные

на рисунках рис. 3.7 и рис. 3.13,                       на рисунках рис. 3.6 и рис. 3.14,

находим точку М с координатами               находим точку N с координатами

и .                                         и .  

 

             

             

           Рис. 2.17                                                                   Рис. 2.18    

С учетом выражений   и , находим в каждом случае оптимальные смешанные стратегии первого и второго игроков

 

   =                             и                = .

Соответственно, средние выигрыши игроков находятся по формулам

, .

 

ИГРЫ С ПРИРОДОЙ