Модели

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

а) заинтересованных сторон;

в) возможных действий каждой из сторон;

в) интересов сторон.

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

Для игр характерна неопределенность результата (исхода). Причины или источники неопределенности относятся к трем группам:

1) Комбинаторные источники (шахматы)

2) Влияние случайных факторов (игра в орлянку, кости, карточные игры, где случаен расклад)

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

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

Классификации стратегических игр

Игры различают

1) По числу игроков (игра 2-х лиц, игра n ( n>2 ) лиц)

2) По числу игроков и их стратегий (конечные, бесконечные)

3) По количеству информации, имеющейся у игроков относительно прошлых ходов (игры с полной, игры с неполной информацией). Шахматы – пример игры с полной информацией.

4) По принципу деления выигрыша (коалиционные, бескоалиционные).

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

Модель и методы решения

В игре двух лиц с нулевой суммой (такую игру называют также антагонистической) принимают участие два игрока: игрок 1 и игрок 2. В распоряжении каждого игрока имеется множество стратегий. Под стратегией понимают совокупность правил (принципов), определяющих выбор варианта действий при каждом личном ходе игрока в зависимости от сложившейся ситуации. Пусть A = {a1, a2, ..., } - множество стратегий игрока 1, B = {b1, b2, ..., } - множество стратегий игрока 2. Элементы множества A - возможные стратегии (действия) игрока 1, элементы множества B - стратегии игрока 2. Условия игры представлены так называемой функцией выигрыша игрока 1: H(ai , bj) , где ai О A  – i – я стратегия игрока 1 , bj ОB – j – я стратегия игрока 2. В игре с нулевой суммой выигрыш игрока 2 равносилен проигрышу игрока 1 и равен поэтому -H(ai, bj). Предполагается, что функция выигрыша обоим игрокам известна. Поскольку игроков всего двое и игра антагонистическая, коалиции невозможны.

Игра, в которой множества A и B стратегий игроков конечны, т.е. | A | < Ґ , | B | < Ґ, называется матричной. В этом случае функция выигрышей игрока 1 имеет вид матрицы, называемой матрицей игры (матрица выигрышей, платежная матрица) H = {aij} m, n , i=1,..., m; j=1,..., n. Строки этой матрицы соответствуют стратегиям a1, a2, ..., am игрока 1, столбцы – стратегиям b1, b2, ..., bn игрока 2. Элемент матрицы aij = H(ai , bj) – выигрыш игрока 1 в случае, когда он применит стратегию ai , а его противник – стратегию bj , i=1,..., m, j=1,..., n . Элементы матрицы могут быть положительными, отрицательными или равными нулю. Случай, когда данный элемент матрицы положителен, означает, что игрок 2 в определенной ситуации должен уплатить игроку 1 сумму, равную значению этого элемента. Если данный элемент отрицателен, игрок 1 уплачивает игроку 2 сумму, равную абсолютному значению этого элемента. И, наконец, если этот элемент равен нулю, никакой выплаты не производится. Таким образом, в игре двух лиц с нулевой суммой один игрок выигрывает столько же, сколько проигрывает другой (все выплаты производятся из "карманов" противников). Это и объясняет название – игра с нулевой суммой. Игрок 1 стремится к максимальному выигрышу, игрок 2 - к минимальному проигрышу. Решить игру - значит найти оптимальные стратегии игроков и их выигрыши.

В игре двух лиц с нулевой суммой, как и в любой другой стратегической игре, исход зависит от поведения обоих игроков, которое основывается на так называемых правилах игры. Допустим, что согласно правилам игры, игрок 1 может выбрать произвольную строку матрицы и, следовательно, может выбрать одно из чисел 1, 2, ..., m. Аналогично, игрок 2 имеет возможность выбора произвольного столбца матрицы выигрышей и, следовательно, одного из чисел 1, 2, ..., n. Исход (результат) игры и, следовательно, сумму, которую игрок 2 должен уплатить игроку 1, определяет элемент матрицы выигрышей, находящийся на пересечении строки, выбранной игроком 1, и столбца, выбранного игроком 2. Существенно, что ни один из партнеров не знает, какую стратегию применит его противник. Таким образом, имеет место ситуация полной неопределенности, при которой теория вероятности не может помочь игрокам в выборе решения. Рассмотрим процесс принятия решений обеими сторонами более детально, предполагая, что игроки действуют рационально. Если игрок 1 не знает, как поступит его противник, то, действуя наиболее целесообразно, не желая рисковать и считая, что противник также будет действовать целесообразно, он выберет такую стратегию, которая гарантирует ему наибольший из наименьших выигрышей при любой стратегии противника. Принято говорить, что при таком образе действий игрок 1 руководствуется принципом максиминного выигрыша. Этот выигрыш определяется формулой     a = maxi   min j aij .

Величина a называется нижней ценой игры, максиминным выигрышем, или сокращенно максимином. В свою очередь игрок 2, действуя рационально, выберет такую стратегию, которая гарантирует ему наименьший из возможных проигрышей при любых действиях противника. Принято говорить, игрок 2 руководствуется принципом минимаксного проигрыша. Этот проигрыш определяется выражением b = minj maxi aij .

Величина b называется верхней ценой игры или минимаксом. Принцип осторожности, который определяет выбор партнерами стратегий, соответствующих максиминному выигрышу или минимаксному проигрышу, часто называют принципом минимакса, а стратегии, вытекающие из этого принципа, - минимаксными стратегиями. Доказывается, что всегда a Ј b, чем и объясняются названия "нижняя цена" и "верхняя цена". В случае, когда нижняя цена игры равняется ее верхней цене, их общее значение называется ценой игры. При этом результат стратегической игры двух лиц с нулевой суммой можно определить, не приступая к фактической игре: вполне реален сценарий, когда партнеры, взглянув на матрицу, рассчитываются, пожимают друг другу руки и расходятся. Очевидно, что исход такой игры не изменится, если она будет повторена многократно, поскольку ни одному из игроков невыгодно отклоняться от своих минимаксных стратегий. Ситуация, в которой нижняя и верхняя цены игры совпадают, называется седловой точкой. Формальное определение: кортеж стратегий или ситуация (ai*, bj*) О A x B называется седловой точкой, если H(ai*, bj*) = maxi { H(ai, bj*); i=1, 2, ..., m} = minj { H(ai*, bj); j=1, 2, ..., n}.

В седловой точке элемент матрицы aij* = H(ai*, bj*) является одновременно наименьшим в строке и наибольшим в столбце и, следовательно, соответствует цене игры. Однако существуют матрицы игры двух лиц с нулевой суммой (и таких игр большинство), для которых a № b, т.е. определенная выше седловая точка отсутствует. Исход такой игры определить труднее, поскольку какой-либо одной, так называемой чистой оптимальной стратегии ни для одного игрока не существует. В таких случаях говорят, что решение игры в чистых стратегиях отсутствует, и рассматривают так называемое смешанное расширение игры, решение которой ищут в смешанных стратегиях. Смешанная стратегия игрока – это случайная величина, значениями которой являются его чистые стратегии. Задание смешанной стратегии игрока состоит в указании вероятностей (частот), с которыми выбираются его первоначальные (чистые) стратегии. При этом предполагается, что игра повторяется многократно.

Для матричной игры mґ n обозначим через P = (p1, p2, ..., pm) - смешанную стратегию игрока 1, где p1 і 0, p2 і 0, ...,pm і 0 и

m
S pi = 1
i=1

Через Q=(q1, q2, ..., qn) обозначим смешанную стратегию игрока 2, где q1 і 0, q2 і 0, ..., qn і 0 и.

n
S q j = 1
j=1

Здесь p1, p2, ..., pm - вероятности использования игроком 1 в смешанной стратегии своих чистых стратегий a1, a2, ..., am. и.q1, q2, ...,qn - вероятности использования игроком 2 в смешанной стратегии своих чистых стратегий b1, b2, ..., bn.

Математическое ожидание выигрыша игрока 1:

m n
M(P, Q) = S S aij pi qj.
i=1 j=1

Смешанная стратегия, которая гарантирует данному игроку наибольший возможный средний выигрыш (или наименьший возможный средний проигрыш), называется его оптимальной смешанной стратегией, а стратегии, из которых складывается оптимальная смешанная стратегия, определяются как выгодные стратегии. Пусть P* - смешанная стратегия игрока 1, Q* - смешанная стратегия игрока 2. Пара смешанных стратегий (P*, Q*), при которой M(P, Q*) Ј M(P*, Q*) Ј M(P*, Q), называют седловой точкой смешанного расширения игры, а математическое ожидание выигрыша v = M(P*, Q*) - ценой игры, причем всегда a Ј v Ј b.

Доминирование стратегий

Если платежная матрица такова, что каждый элемент некоторой строки i не меньше соответствующего элемента строки k и по меньшей мере один ее элемент строго больше соответствующего элемента строки k, то говорят, что стратегия ai игрока 1 доминирует его стратегию ak . Доминируемая стратегия ak не может быть оптимальной чистой стратегией игрока 1, или войти в его оптимальную смешанную стратегию с ненулевой вероятностью, поэтому ее можно исключить из рассмотрения, вычеркнув из матрицы строку k. Аналогично, если каждый элемент некоторого столбца j не больше соответствующего элемента столбца r и по меньшей мере один его элемент строго меньше соответствующего элемента столбца r , то говорят, что стратегия bj игрока 2 доминирует его стратегию br . Поэтому столбец r матрицы можно вычеркнуть.

Сведение игры двух лиц с нулевой суммой к задаче линейного программирования

При отсутствии седловой точки общим методом нахождения решения игры любой (конечной) размерности является сведение игры двух лиц с нулевой суммой к задаче линейного программирования. Из основного положения теории стратегических игр следует, что при использовании смешанных стратегий существует, по меньшей мере, одно оптимальное решение с ценой игры v , причем a Ј v Ј b, т.е. цена игры находится между верхним и нижним значениями игры. Величина v неизвестна, но всегда можно предположить, что v > 0. Это условие выполняется, поскольку всегда можно путем соответствующего преобразования матрицы сделать все ее элементы положительными. Таким образом, если в исходной платежной матрице имеется хотя бы один неположительный элемент, то первым шагом в процедуре сведения игры к задаче линейного программирования должно быть ее преобразование к матрице, все элементы которой строго положительны. Для этого достаточно увеличить все элементы исходной матрицы на одно и то же число

d > maxi maxj |aij |, где aij Ј 0.

При таком преобразовании матрицы оптимальные стратегии игроков не изменяются.

Допустим, что смешанная стратегия игрока 1 складывается из стратегий a1, a2, ..., am с вероятностями, соответственно, p1, p2, ..., pm (p1+ p2+...+ pm=1). (Некоторые из значений вероятностей могут быть равны нулю). Оптимальная смешанная стратегия игрока 2 складывается из стратегий b1, b2, ..., bn с вероятностями q1, q2, ..., qn , (q1+ q2+...+ qn=1). Условия игры определяются платежной матрицей {aij} m, n , aij > 0, i=1,..., m; j=1,...,n. Если игрок 1 применяет оптимальную смешанную стратегию, а игрок 2 - чистую стратегию bj , то средний выигрыш игрока 1 (математическое ожидание выигрыша) составит

p1 a1j + p2 a2j + ... + pm amj .

Игрок 1 стремится к тому, чтобы при любой стратегии игрока 2 его выигрыш был не менее чем цена игры v, и сама цена игры была максимальной. Такое поведение игрока 1 описывается следующей моделью линейного программирования:

v ® max (игрок 1 стремится максимизировать свой выигрыш)

p1 a11 + p2 a21 + ... + pm am1 і v

p1 a12 + p2 a22 + ... + pm am2 і v

. . .

p1 a1n + p2 a2n + ... + pm amn і v

p1+ p2+...+ pm=1

pi і 0, (i=1,..., m)

Используя обозначения   xi = pi / v , имеем

x1+ x2+...+ xm ® min

a11 x1 + a21 x2 + ... + am1 xm і 1

a12 x1 + a22 x2 + ... + am2 xm і 1                   (1)

. . .

a1n x1 + a2n x2+ ... + amn xm і 1

xi і 0 , (i=1,..., m)

Причем v = 1/ (x1+ x2+...+ xm).

 

Поведению игрока 2 соответствует двойственная задача линейного программирования:

y1+ y2+...+ yn ® max (эквивалентно v ® min: игрок 2 стремится минимизировать свой средний проигрыш)

a11 y1 + a12 y2 + ... + a1n yn Ј 1

a21 y1 + a22 y2 + ... + a2n yn Ј 1              (2)

. . .

am1 y1 + am2 y2+ ... + amn yn Ј 1

yj і 0 , (j=1,..., n),

где yj = q j / v.

Задача (1) всегда имеет решение. Получив ее оптимальное решение x1*, x2*,..., xm* , можно найти цену игры v * = 1/ (x1*+ x2*+...+ xm* ), оптимальные значения p1*, p2*,..., pm* , и, следовательно, оптимальную стратегию игрока 1. Если исходная матрица увеличивалась на d, то для получения цены первоначальной игры, v * нужно уменьшить на d.

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

Матричная игра двух лиц с ненулевой постоянной суммой

Конечная игра, в которой сумма выигрышей обоих игроков не равна нулю и постоянна для всех сочетаний их чистых стратегий, называется матричной игрой двух лиц с ненулевой постоянной суммой. Пусть {aij} m, n - матрица выигрышей игрока 1 и {bij} m, n - матрица выигрышей игрока 2. Причем aij + bij = c для всех i=1,..., m; j=1,..., n.

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

1) Каждому игроку выплачивается сумма c / 2;

2) Решается игра с нулевой суммой с матрицей выигрышей игрока 1 {a' i j} m, n , где  a' i j = a ij - c / 2.

Действительно, в игре с преобразованной таким образом матрицей выигрыша игрок 2 получает сумму c / 2 - aij для всех i=1,..., m; j=1,..., n, т.е. новая игра является игрой с нулевой суммой. При этом каждый игрок ничего не теряет оттого, что каждый из них в игре получает на c / 2 меньше, поскольку по c / 2 они получили перед игрой.