Г Л А В А  8 МЕТОДЫ ТЕОРИИ ИГР.

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

Типичным примером конфликтных ситуаций в экономической системе является конкурентная борьба, например, борьба за рынок.

Результат или исход игры, даже в том случае, когда он не имеет прямой количественной оценки, обычно характеризуется некоторым числом, например, выигрыш +1, проигрыш -1, ничья - 0.

Игра может быть парной или множественной (многие участники).

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

Процесс (развитие) игры происходит в результате последовательного выполнения тех или иных ходов.

Ход называется личным, если он осуществляется одним из игроков в результате сознательного анализа ситуаций.

Ход называется случайным, когда он осуществляется в результате того или иного случайного процесса (например, раздача карт).

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

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

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

Результаты конечной парной игры с нулевой суммой (КПИНС), можно задать матрицей, строки и столбцы которой соответствуют различным стратегиям, а ее элементы есть соответствующие выигрыши одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры. При этом удобно проигрыш первой стороны рассматривать как ее отрицательный выигрыш, а выигрыш второй - как ее отрицательный проигрыш.

Если первая сторона имеет m стратегий, а вторая - n, то имеем дело с игрой m x n.

Рассмотрим игру  m x n  со следующей матрицей:

где Ai (i = 1, 2, ..., m) - стратегии первого игрока, Bj (j = 1, 2, ..., n) - стратегии второго игрока, аij - плата в сеансе игры со стратегиями Ai и Bj.

Если первый игрок применяет стратегию Аi, то другой будет стремиться к тому, чтобы выбором соответствующей стратегии свести выигрыш первого игрока к минимуму.  Из "арсенала" - набора своих стратегий второй выбирает такую стратегию Вj, чтобы величина аij  была бы минимальной, т.е. если  ai есть величина этого минимума, то:

                                                                               ai = min aij .

                                                                                           j

C точки зрения первого игрока (при любых ответах противника) целесообразно стремиться найти такую стратегию, при которой ai будет обращаться в максимум. Пусть этот максимум равен a. Он называется нижней ценой игры. Так как значение a вычисляется по формуле:

                                                                                  a = max  ai 

                                                                                             i

  или 

                                                                            a = max min aij ,

                                                                                      i       j

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

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

                                                                          b = min max aij.

                                                                                     j       i

Величина b называется верхней ценой игры или минимаксом. Ей соответствует минимаксная стратегия второго игрока.

Имеет место неравенство:

                                                                                     a   b.

При < b первый игрок может существенно увеличить свой средний выигрыш по сравнению с , если он будет пользоваться не чистой (одной единственной стратегией), а так называемой смешанной стратегией.

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

Известно, что для любой КПИНС существует пара оптимальных стратегий (вообще говоря смешанных).

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

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

Цена игры заключена между нижней и верхней ценой игры:

                                                                               a g   b.

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

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

Известно, что у игры  m x n  число полезных стратегий с каждой стороны не превосходит минимального из чисел  m и n.

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

Пусть имеем игру  3 x 3 со следующей матрицей:

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

Следующим шагом в поиске решения является нахождение нижней и верхней цены игры:

                                                                  a = max min aij = max ( 0, 0 ) = 0,

                                                                             i      j

                                                                   b = min max aij = min ( 1, 2 ) = 1.

                                                                             j      i

Поскольку максимин (нулевой элемент) есть и в первой и во второй строке, то обе стратегии первого игрока являются максиминными. Минимаксной же стратегией второго игрока является лишь стратегия В1.

В нашем случае a b и следовательно, решение нужно искать среди смешанных стратегий.

Рассмотрим другой пример. Пусть игра  2 x 3 задана матрицей:

Находим нижнюю и верхнюю цену игры:

                                                                a = max min aij = max ( -1, 1 ) = 1;

                                                                           i       j               i

                                                                b = min max aij = min ( 3,3,1 ) = 1.

                                                                           j      i                j

В  этом случае a = b = 1, т.к. a g    b, и цена игры равна 1. Решение же игры задается парой чистых стратегий (А2, В3) ибо максимин (он же минимакс) расположен во второй строке и в третьем столбце.

В области чистых стратегий решение может быть получено непосредственно. Если же решение нужно искать в области смешанных стратегий (a ¹ b), то в общем случае m x n матрицы ||aij|| применяется следующий прием.

Считая все m стратегий первого игрока полезными, определяют вероятность их применения в смешанной оптимальной стратегии (если какая-то стратегия в действительности бесполезна, то соответствующая вероятность обратится в нуль). Пусть искомые вероятности обозначаются р1, р2, ...,   рm, а цена игры (пока неизвестная) - g.

Так как при оптимальной стратегии средний выигрыш первого игрока не меньше g при любой стратегии противника, то ищем n неравенств:

                                                             р1 а11 + р2 а21 + ...... + рm аm1  ³ g

                                                             p1 a12 + p2 a22 +....... + pm am2  ³ g

                                                             ....................................................

                                                             ....................................................

                                                             p1 a1m + p2 a2n +....... + pm amn ³ g

Вводим новые неизвестные:

                                                           x1=p1/g,  x2 = p2/g,  ...,  xm = pm/g.

Чтобы исключить деление на нуль, можно всегда добиться g > 0. Для этой цели достаточно ко всем элементам матрицы ||aij|| прибавить одно и тоже положительное число с и все ее элементы сделать положительными. Эта операция увеличит цену игры на с, но не изменит искомых оптимальных стратегий.

                         m

Так как   å рi = 1,   то   xi = 1/g.

                       i=1

Таким образом,  имеем систему неравенств

                                                              a11x1 + a21x2 +........+ am1xm 1

                                                              a12x1 + a22x2 +........+ am2xm 1

                                                              ...................................................                                          (8.1)

                                                              ...................................................

                                                              a1nx1 + a2nx2 +........+ amnxm 1 ,

где все  xi 0.

Так как цель оптимальной стратегии - максимизация выигрыша, то при ее достижении линейная функция:

                                                                                     m

                                                                            f  =  å xi = 1/

                                                                                    i=1

должна обратиться в минимум.  Итак, оптимальная стратегия первого игрока (т.е. набор вероятностей рi = xi) находятся в результате минимизации функции:

                                                                                         m

                                                                                 f =  å xi,         

                                                                                       i=1

при  xi 0, удовлетворяющих системе неравенств (8.1).

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

Зная цену игры, оптимальную стратегию (а1, а2, ..., аn) второго игрока можно находить уже без решения задачи линейного программирования (хотя оптимальную стратегию второго игрока можно находить и через решение этой задачи, если поменять игроков местами). Для этого выбирается n-1 полезных стратегий первого игрока (имея возможность менять местами игроков  можно  считать, что  m n) и для каждой из них записывается средний выигрыш, который при этом должен быть обязательно равен цене игры g. Например, если для первого игрока полезна стратегия Аi, то ей соответствует уравнение:

                                                                       ai1q1 + ai2q2 +.......+ ainqn = g.

Кроме этого имеется еще одно уравнение:

                                                                                           n

                                                                                          å qi   = 1.

                                                                                          i=1

Всего имеем  n уравнений для n величин q1, q2, ..., qn.

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

При a = b  это очевидно, так как решением являются чистые стратегии. При a ¹ b обе стратегии первого и второго игрока обязательно будут полезными (иначе существовало бы решение в чистых стратегиях). Поэтому неравенства (8.1) превращаются в этом случае в равенства:

                                                                          а11р1 + а21р2 = g 

                                                                                                                                              (8.2)

                                                                          a12p1 + a22p2 = g

так как р1 + р2 = 1, то имеется достаточное число уравнений для определения р1, р2, g. Применим этот прием для решения задачи с матрицей:

                                                                                          1      0    ö

                                                                                                         ÷

                                                                                          0      2    ø.

Уравнение ( 8.2 ) записывается в виде:

                                                                     р1 = g;  2p2 = g;  p1 + p2 = 1,

 отсюда      p2 = 1/3;  p1 = 2/3; g = 2/3.

Следовательно, при случайном чередовании первой и второй стратегии с относительными частотами 2/3 и 1/3 соответственно первому игроку обеспечен средний выигрыш в размере 2/3.

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

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

                                                                                     1q1 + 0q2.

Приравнивая ее цене игры g = 2/3, имеем q1 = 2/3 и отсюда q2 = 1/3. Итак, второй игрок должен смешивать свои стратегии В1 и В2 с частотами 2/3 и 1/3 соответственно.

Описанный метод простого решения задачи может быть обобщен на игры 2 х n.

Игровые методы могут применяться для изучения ситуаций, которые не являются в строгом смысле слова конструктивными. Например, ситуации, где вторым игроком является природа.

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

В этой игре ценой будет денежный доход от реализации урожая (тыс.руб.). Задаем матрицу игры (на практике она определяется из опыта):

Определяем нижнюю и верхнюю цену игры:

                                                                    a = max min aij = max (5, 2) = 5,

                                                                               i       j

                                                                    b = min max aij = min (10, 6) = 6.

                                                                               j       i

Так как a ¹ b, то оптимальной будет смешанная стратегия. Уравнения (8.2 ) будут:

                                                                             5р1 + 10р2 =

                                                                             6р1 +   2р2 =

                                                                               р1 +     р2  = 1

Отсюда:

                                                                  р1 = 8/9,  р2 = 1/9,  = 50/9.   

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

                                                            5q1 + 6q2 = 50/9;   q1 + q2 = 1,

отсюда:

                                                                        q1 = 4/9;  q2 = 5/9.

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

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

Однако, в том-то как раз и состоит отличие рассматриваемой ситуации от подлинно конфликтной, что природа не является сознательным противником и ее стратегия не обязательно оптимальна.

Пусть реальная (смешанная) стратегия задается вероятностями q1 = 0.9  и  q2 = 0.1 (по долголетним наблюдениям), причем в чередовании "плохих" и "хороших" зим нет другой закономерности, кроме этих вероятностей. Задача - выработать оптимальную стратегию нашего поведения (вероятность р1 и р2) для обеспечения максимального выигрыша в этих условиях.

Математическое ожидание выигрыша выразится суммой:

                                                                                    m       n

                                                                            d=  å      å aij pi qj  

                                                                                  i=1     j=1

или

                                                          d = (5q1 + 6q2)p1 + (10q1 + 2q2)p2 = 5.1p1 + 9.2p2.

Нужно найти max этой величины при условии pi 0; p1 + p2 = 1. Отсюда р2 = 1 - р1, d = 9.2 - 41p1 и max этой функции 9.2 может быть получен при р1 = 0,  р2 = 1. Т.е. озимые каждый год.

Более тщательный анализ показывает, что оптимальная стратегия противника (природы) является своего рода перевальной точкой. Если вероятность "плохой" зимы превышает величину выше вычисленной оптимальной вероятности q2 = 5/9, то наиболее благоприятной стратегией будет ежегодное высевание яровых. Если эта вероятность меньше чем 5/9, то рационально ежегодно высевать озимые. Выигрыш в этом случае будет больше, чем цена игры, равная 50/9.

Имеет место следующий итерационный метод. Игрок А выбирает любую из своих стратегий, например, Аi1. Игрок В выбирает в ответ ту  стратегию Вji, которая наиболее выгодна А при стратегии Аi1. Далее А отвечает на это лучшей (против стратегии Вji) стратегией Аi2. В ищет стратегию Вj1, наилучшую против смешанных в равных пропорциях стратегии Аi1 и Аi2. Стратегия Аi3 должна быть наилучшей против равновероятной смеси стратегий Вj1 и Вj2, стратегия Вj3 - наилучшей против равновероятной смеси стратегий Аi1, Ai2, Ai3  и т.д.

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

З А Д А Ч И  П О   Т Е М Е

ЗАДАЧА 8.1.

Пусть парная игра с нулевой суммой 3 х 3 задана следующей платежной матрицей:

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

ЗАДАЧА 8.2.

Пусть парная игра с нулевой суммой задана следующей платежной матрицей:

Определить цену игры.

ЗАДАЧА 8.3.

Коля и Оля условились встретиться у театра зимой. Если Коля прийдет раньше, он будет  мерзнуть, и его потери можно оценить числом -1. Если он опоздает, то его потери составят  -4. Как быть Коле и Оле, считая, что это парная игра с нулевой суммой?

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

Типичным примером конфликтных ситуаций в экономической системе является конкурентная борьба, например, борьба за рынок.

Результат или исход игры, даже в том случае, когда он не имеет прямой количественной оценки, обычно характеризуется некоторым числом, например, выигрыш +1, проигрыш -1, ничья - 0.

Игра может быть парной или множественной (многие участники).

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

Процесс (развитие) игры происходит в результате последовательного выполнения тех или иных ходов.

Ход называется личным, если он осуществляется одним из игроков в результате сознательного анализа ситуаций.

Ход называется случайным, когда он осуществляется в результате того или иного случайного процесса (например, раздача карт).

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

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

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

Результаты конечной парной игры с нулевой суммой (КПИНС), можно задать матрицей, строки и столбцы которой соответствуют различным стратегиям, а ее элементы есть соответствующие выигрыши одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры. При этом удобно проигрыш первой стороны рассматривать как ее отрицательный выигрыш, а выигрыш второй - как ее отрицательный проигрыш.

Если первая сторона имеет m стратегий, а вторая - n, то имеем дело с игрой m x n.

Рассмотрим игру  m x n  со следующей матрицей:

где Ai (i = 1, 2, ..., m) - стратегии первого игрока, Bj (j = 1, 2, ..., n) - стратегии второго игрока, аij - плата в сеансе игры со стратегиями Ai и Bj.

Если первый игрок применяет стратегию Аi, то другой будет стремиться к тому, чтобы выбором соответствующей стратегии свести выигрыш первого игрока к минимуму.  Из "арсенала" - набора своих стратегий второй выбирает такую стратегию Вj, чтобы величина аij  была бы минимальной, т.е. если  ai есть величина этого минимума, то:

                                                                               ai = min aij .

                                                                                           j

C точки зрения первого игрока (при любых ответах противника) целесообразно стремиться найти такую стратегию, при которой ai будет обращаться в максимум. Пусть этот максимум равен a. Он называется нижней ценой игры. Так как значение a вычисляется по формуле:

                                                                                  a = max  ai 

                                                                                             i

  или 

                                                                            a = max min aij ,

                                                                                      i       j

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

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

                                                                          b = min max aij.

                                                                                     j       i

Величина b называется верхней ценой игры или минимаксом. Ей соответствует минимаксная стратегия второго игрока.

Имеет место неравенство:

                                                                                     a   b.

При < b первый игрок может существенно увеличить свой средний выигрыш по сравнению с , если он будет пользоваться не чистой (одной единственной стратегией), а так называемой смешанной стратегией.

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

Известно, что для любой КПИНС существует пара оптимальных стратегий (вообще говоря смешанных).

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

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

Цена игры заключена между нижней и верхней ценой игры:

                                                                               a g   b.

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

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

Известно, что у игры  m x n  число полезных стратегий с каждой стороны не превосходит минимального из чисел  m и n.

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

Пусть имеем игру  3 x 3 со следующей матрицей:

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

Следующим шагом в поиске решения является нахождение нижней и верхней цены игры:

                                                                  a = max min aij = max ( 0, 0 ) = 0,

                                                                             i      j

                                                                   b = min max aij = min ( 1, 2 ) = 1.

                                                                             j      i

Поскольку максимин (нулевой элемент) есть и в первой и во второй строке, то обе стратегии первого игрока являются максиминными. Минимаксной же стратегией второго игрока является лишь стратегия В1.

В нашем случае a b и следовательно, решение нужно искать среди смешанных стратегий.

Рассмотрим другой пример. Пусть игра  2 x 3 задана матрицей:

Находим нижнюю и верхнюю цену игры:

                                                                a = max min aij = max ( -1, 1 ) = 1;

                                                                           i       j               i

                                                                b = min max aij = min ( 3,3,1 ) = 1.

                                                                           j      i                j

В  этом случае a = b = 1, т.к. a g    b, и цена игры равна 1. Решение же игры задается парой чистых стратегий (А2, В3) ибо максимин (он же минимакс) расположен во второй строке и в третьем столбце.

В области чистых стратегий решение может быть получено непосредственно. Если же решение нужно искать в области смешанных стратегий (a ¹ b), то в общем случае m x n матрицы ||aij|| применяется следующий прием.

Считая все m стратегий первого игрока полезными, определяют вероятность их применения в смешанной оптимальной стратегии (если какая-то стратегия в действительности бесполезна, то соответствующая вероятность обратится в нуль). Пусть искомые вероятности обозначаются р1, р2, ...,   рm, а цена игры (пока неизвестная) - g.

Так как при оптимальной стратегии средний выигрыш первого игрока не меньше g при любой стратегии противника, то ищем n неравенств:

                                                             р1 а11 + р2 а21 + ...... + рm аm1  ³ g

                                                             p1 a12 + p2 a22 +....... + pm am2  ³ g

                                                             ....................................................

                                                             ....................................................

                                                             p1 a1m + p2 a2n +....... + pm amn ³ g

Вводим новые неизвестные:

                                                           x1=p1/g,  x2 = p2/g,  ...,  xm = pm/g.

Чтобы исключить деление на нуль, можно всегда добиться g > 0. Для этой цели достаточно ко всем элементам матрицы ||aij|| прибавить одно и тоже положительное число с и все ее элементы сделать положительными. Эта операция увеличит цену игры на с, но не изменит искомых оптимальных стратегий.

                         m

Так как   å рi = 1,   то   xi = 1/g.

                       i=1

Таким образом,  имеем систему неравенств

                                                              a11x1 + a21x2 +........+ am1xm 1

                                                              a12x1 + a22x2 +........+ am2xm 1

                                                              ...................................................                                          (8.1)

                                                              ...................................................

                                                              a1nx1 + a2nx2 +........+ amnxm 1 ,

где все  xi 0.

Так как цель оптимальной стратегии - максимизация выигрыша, то при ее достижении линейная функция:

                                                                                     m

                                                                            f  =  å xi = 1/

                                                                                    i=1

должна обратиться в минимум.  Итак, оптимальная стратегия первого игрока (т.е. набор вероятностей рi = xi) находятся в результате минимизации функции:

                                                                                         m

                                                                                 f =  å xi,         

                                                                                       i=1

при  xi 0, удовлетворяющих системе неравенств (8.1).

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

Зная цену игры, оптимальную стратегию (а1, а2, ..., аn) второго игрока можно находить уже без решения задачи линейного программирования (хотя оптимальную стратегию второго игрока можно находить и через решение этой задачи, если поменять игроков местами). Для этого выбирается n-1 полезных стратегий первого игрока (имея возможность менять местами игроков  можно  считать, что  m n) и для каждой из них записывается средний выигрыш, который при этом должен быть обязательно равен цене игры g. Например, если для первого игрока полезна стратегия Аi, то ей соответствует уравнение:

                                                                       ai1q1 + ai2q2 +.......+ ainqn = g.

Кроме этого имеется еще одно уравнение:

                                                                                           n

                                                                                          å qi   = 1.

                                                                                          i=1

Всего имеем  n уравнений для n величин q1, q2, ..., qn.

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

При a = b  это очевидно, так как решением являются чистые стратегии. При a ¹ b обе стратегии первого и второго игрока обязательно будут полезными (иначе существовало бы решение в чистых стратегиях). Поэтому неравенства (8.1) превращаются в этом случае в равенства:

                                                                          а11р1 + а21р2 = g 

                                                                                                                                              (8.2)

                                                                          a12p1 + a22p2 = g

так как р1 + р2 = 1, то имеется достаточное число уравнений для определения р1, р2, g. Применим этот прием для решения задачи с матрицей:

                                                                                          1      0    ö

                                                                                                         ÷

                                                                                          0      2    ø.

Уравнение ( 8.2 ) записывается в виде:

                                                                     р1 = g;  2p2 = g;  p1 + p2 = 1,

 отсюда      p2 = 1/3;  p1 = 2/3; g = 2/3.

Следовательно, при случайном чередовании первой и второй стратегии с относительными частотами 2/3 и 1/3 соответственно первому игроку обеспечен средний выигрыш в размере 2/3.

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

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

                                                                                     1q1 + 0q2.

Приравнивая ее цене игры g = 2/3, имеем q1 = 2/3 и отсюда q2 = 1/3. Итак, второй игрок должен смешивать свои стратегии В1 и В2 с частотами 2/3 и 1/3 соответственно.

Описанный метод простого решения задачи может быть обобщен на игры 2 х n.

Игровые методы могут применяться для изучения ситуаций, которые не являются в строгом смысле слова конструктивными. Например, ситуации, где вторым игроком является природа.

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

В этой игре ценой будет денежный доход от реализации урожая (тыс.руб.). Задаем матрицу игры (на практике она определяется из опыта):

Определяем нижнюю и верхнюю цену игры:

                                                                    a = max min aij = max (5, 2) = 5,

                                                                               i       j

                                                                    b = min max aij = min (10, 6) = 6.

                                                                               j       i

Так как a ¹ b, то оптимальной будет смешанная стратегия. Уравнения (8.2 ) будут:

                                                                             5р1 + 10р2 =

                                                                             6р1 +   2р2 =

                                                                               р1 +     р2  = 1

Отсюда:

                                                                  р1 = 8/9,  р2 = 1/9,  = 50/9.   

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

                                                            5q1 + 6q2 = 50/9;   q1 + q2 = 1,

отсюда:

                                                                        q1 = 4/9;  q2 = 5/9.

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

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

Однако, в том-то как раз и состоит отличие рассматриваемой ситуации от подлинно конфликтной, что природа не является сознательным противником и ее стратегия не обязательно оптимальна.

Пусть реальная (смешанная) стратегия задается вероятностями q1 = 0.9  и  q2 = 0.1 (по долголетним наблюдениям), причем в чередовании "плохих" и "хороших" зим нет другой закономерности, кроме этих вероятностей. Задача - выработать оптимальную стратегию нашего поведения (вероятность р1 и р2) для обеспечения максимального выигрыша в этих условиях.

Математическое ожидание выигрыша выразится суммой:

                                                                                    m       n

                                                                            d=  å      å aij pi qj  

                                                                                  i=1     j=1

или

                                                          d = (5q1 + 6q2)p1 + (10q1 + 2q2)p2 = 5.1p1 + 9.2p2.

Нужно найти max этой величины при условии pi 0; p1 + p2 = 1. Отсюда р2 = 1 - р1, d = 9.2 - 41p1 и max этой функции 9.2 может быть получен при р1 = 0,  р2 = 1. Т.е. озимые каждый год.

Более тщательный анализ показывает, что оптимальная стратегия противника (природы) является своего рода перевальной точкой. Если вероятность "плохой" зимы превышает величину выше вычисленной оптимальной вероятности q2 = 5/9, то наиболее благоприятной стратегией будет ежегодное высевание яровых. Если эта вероятность меньше чем 5/9, то рационально ежегодно высевать озимые. Выигрыш в этом случае будет больше, чем цена игры, равная 50/9.

Имеет место следующий итерационный метод. Игрок А выбирает любую из своих стратегий, например, Аi1. Игрок В выбирает в ответ ту  стратегию Вji, которая наиболее выгодна А при стратегии Аi1. Далее А отвечает на это лучшей (против стратегии Вji) стратегией Аi2. В ищет стратегию Вj1, наилучшую против смешанных в равных пропорциях стратегии Аi1 и Аi2. Стратегия Аi3 должна быть наилучшей против равновероятной смеси стратегий Вj1 и Вj2, стратегия Вj3 - наилучшей против равновероятной смеси стратегий Аi1, Ai2, Ai3  и т.д.

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

З А Д А Ч И  П О   Т Е М Е

ЗАДАЧА 8.1.

Пусть парная игра с нулевой суммой 3 х 3 задана следующей платежной матрицей:

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

ЗАДАЧА 8.2.

Пусть парная игра с нулевой суммой задана следующей платежной матрицей:

Определить цену игры.

ЗАДАЧА 8.3.

Коля и Оля условились встретиться у театра зимой. Если Коля прийдет раньше, он будет  мерзнуть, и его потери можно оценить числом -1. Если он опоздает, то его потери составят  -4. Как быть Коле и Оле, считая, что это парная игра с нулевой суммой?