Элементы теории игр в задачах моделирования экономических процессов

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

Если в игре игроки объединяются в две группы, преследующие противоположные  цели, то такая игра называется игрой двух лиц (парная игра).

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

ГЛАВА 2. РАЗЛИЧНЫЕ ВИДЫ ИГР И СПОСОБЫ ИХ РЕШЕНИЯ

2.1. Решение матричной игры в чистых стратегиях

 

В  простейшей математической модели конечной конфликтной ситуации имеется два участника и выигрыш одного равен проигрышу другого. Такая модель называется антагонистической игрой двух лиц с нулевой суммой. Игра состоит из двух ходов: игрок А выбирает одну из возможных стратегий А_i, , а игрок В выбирает одну из возможных стратегий В_j, . Каждый выбор производится при полном незнании выбора соперника. В результате выигрыш игроков составит соответственно a_ij и (- a_ij ). Цель игрока А - максимизировать величину a_ij, а игрока В - минимизировать эту величину.

 Матрица, составленная из величин a_ij, , ,

                                      

 

является платежной матрицей, или матрицей игры. Каждый элемент платежной матрицы a_ij, , равен выигрышу А (проигрышу В), если он выбрал стратегию А_i, , а игрок В выбирал стратегию В_j, .

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

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

                             .

 Величина a - гарантированный выигрыш игрока А называется нижней ценой игры. Стратегия A_iопт, обеспечивающая получение выигрыша a, называется максиминной.

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

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

                                    .

 Величина b - гарантированный проигрыш игрока В называется верхней ценой игры. Стратегия B_jопт, обеспечивающая получение проигрыша b, называется минимаксной.

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

Фактический выигрыш игрока А (проигрыш игрока В) при разумных действиях партнеров ограничен верхней и нижней ценой игры. Для матричной игры справедливо неравенство a £ b.

 Если a = b =v, т.е.

                                   = ,

то выигрыш  игрока А (проигрыш игрока В) определяется числом v. Оно называется ценой игры.

Если a = b =v, то такая игра называется игрой с седловой точкой, элемент матрицы а_{iопт jопт} = v, соответствующий паре оптимальных стратегий (A_iопт, B_jопт), называется седловой точкой матрицы. Этот элемент является ценой игры.

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

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

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

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

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

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

2.2. Решение матричной игры в смешанных стратегиях

 

Если платежная матрица не имеет седловой точки, т.е. a <b и , то поиск решения игры приводит к применению сложной стратегии, состоящей в случайном применении двух и более стратегий с определенными частотами.

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

В игре, матрица которой имеет размерность m ´ n, стратегии первого игрока задаются наборами вероятностей (x₁, x₂,..., x_m), с которыми игрок применяет свои чистые стратегии. Эти наборы можно рассмотреть как m-мерные векторы, для координат которых выполняются условия

                               , x_i ³ 0, .

Аналогично для второго игрока наборы вероятностей определяют n-мерные векторы (y₁, y₂,..., y_n), для координат которых выполняются условия                            = 1, y_j ³ 0, .

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

                                .

Согласно  теории Неймана, каждая конечная игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий. Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры: a £ v £ b. Применение первым игроком оптимальной стратегии _опт должно обеспечить ему при любых действиях второго игрока выигрыш не меньше цены игры. Поэтому выполняется соотношение

                                 , .

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

                 , .

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

 Если все элементы i-й строки платежной матрицы больше соответствующих элементов k-й строки, то i-я стратегия игрока А будет доминирующей над k-й стратегией. Если все элементы j-го столбца платежной матрицы меньше соответствующих элементов k-го столбца, то j-я стратегия игрока В является доминирующей над k-й стратегией.

2.3. Решение игр графическим методом

 

    Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

Первый случай. Игра (2 ´ 2) с матрицей без седловой точки.

                                                    

Решением игры являются смешанные стратегии игроков (x₁, x₂) и (y₁, y₂), где x₁ - вероятность применения первым игроком первой стратегии, x₂ - вероятность применения первым игроком второй стратегии, y₁ - вероятность применения вторым игроком первой стратегии, y₂ - вероятность применения вторым игроком второй стратегии. Очевидно, что

                               x₁ + x₂ = 1, y₁ + y₂ = 1.

Найдем решение игры графическим методом. На оси ОX отложим отрезок, длина которого равна единице. Левый конец (x = 0) соответствует стратегии первого игрока А₁, правый (x = 1) - стратегии А₂. Внутренние точки отрезка будут соответствовать смешанным стратегиям (x₁, x₂) первого игрока, где x₁ =1 - x₂. Через концы отрезка проведем прямые, перпендикулярные оси ОX, на которых будем откладывать выигрыш при соответствующих чистых стратегиях. Если игрок В применяет стратегию В₁, то выигрыш при использовании первым игроком стратегий А₁ и А₂ составит соответственно а₁₁ и а₂₁. Отложим эти точки на прямых и соединим их отрезком В₁В₁. Если игрок А применяет смешанную стратегию, то выигрышу соответствует некоторая точка М, лежащая на этом отрезке. (см. рис.1)

 

Рис.1. Стратегии игрока А

Аналогично строится отрезок В₂В₂, соответствующий стратегии В₂ игрока В.

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

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

В игре (2 ´ 2) обе стратегии являются активными.

 

Рис.2. Стратегии игроков А и В

Ломаная В₁NВ₂ является нижней границей выигрыша, получаемого игроком А. (см. рис.2) Точка N, в которой он максимален, определяет цену игры и ее решение. Найдем оптимальную стратегию первого игрока. Запишем систему уравнений

                                                         

Приравнивая выражения для v из уравнений системы и учитывая, что

 

x₁ + x₂ = 1, получим , , (1)

                            . (2)

Составляя аналогичную систему

                                           

и учитывая условие

                             y₁ + y₂ = 1,

можно найти оптимальную стратегию  игрока В:

                                                 . (3)

 

 Второй случай. Игра (2 ´ n) с матрицей

 

         .

Для каждой из n стратегий игрока В строится соответствующий ей отрезок на плоскости. Находится нижняя граница выигрыша, получаемого игроком А, и определяется точка на нижней границе, соответствующая наибольшему выигрышу. Выделяются две активные стратегии игрока В, отрезки которых проходят через данную точку. Далее рассматриваются только эти две стратегии игрока В. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).

Третий случай. Рассмотрим игру (m ´ 2) с матрицей

                            .

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

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

Далее рассматриваются только эти  две стратегии игрока А. Игра сводится к игре с матрицей (2 ´ 2). Оптимальные стратегии и цену игры находят по формулам (1) - (3).

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

 

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