Сущность теории игр

* игра без седловой точки;

* игроки используют случайную смесь чистых стратегий с заданными вероятностями;

* игра многократно повторяется в сходных условиях;

* при каждом из ходов ни один игрок не информирован о выборе стратегии другим игроком;

* допускается осреднение результатов игр.

Применяются следующие обозначения смешанных стратегий.

Для игрока 1 смешанная стратегия, заключающаяся в применении чистых стратегий А₁, А₂, ..., А_т с соответствующими вероятностями р₁, р_2, ..., р_т.

 

 

 

 

где .

Для игрока 2

 

 

где .

q_j -- вероятность применения чистой стратегии B_j.

В случае когда р_i = 1, для игрока 1 имеем чистую стратегию

 

 (1.7)

 

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

 

 (1.8)

 

где и - векторы;

p_i и q_i - компоненты векторов.

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

 

 (1.9)

 

Игрок 2 добивается того, чтобы выполнялось условие

 

 (1.10)

 

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

 

 (1.11)

 

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

0. - оптимальная смешанная стратегия игрока 1;
1. - оптимальная смешанная стратегия игрока 2;
2. g - цена игры.

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

 

 (1.12)

 

Существует основная теорема математических игр.

Для матричной игры с любой матрицей А величины

 

 и (1.13)

 

существуют и равны между собой: a = b = g.

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

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

 

 (1.14)

 

Значит, имеется платежная матрица

 

 (1.15)

 

При этом

 

a₁₁p₁ + a₂₁p₂ = g; (1.16)

a₁₂p₁ + a₂₂p₂ = g; (1.17)

p₁ + p₂ = 1. (1.18)

a₁₁p₁ + a₂₁(1 - p₁) = a₁₂p₁ + a₂₂(1 - p₁); (1.19)

a₁₁p₁ + a₂₁ - a₂₁p₁ = a₁₂p₁ + a₂₂ - a₂₂p₁, (1.20)

 

откуда получаем оптимальные значения и :

 

 (1.21)

 (1.22)

 

Зная и , находим g:

 

 (1.23)

 

Вычислив g, находим и :

 

a₁₁q₁ + a₁₂q₂ = g; q₁ + q₂ = 1; (1.24)

a₁₁q₁ + a₁₂ (1 - q₁) = g. (1.25)

при a₁₁ № a₁₂. (1.26)

 

Задача решена, так как найдены векторы и цена игры g. Имея матрицу платежей А, можно решить задачу графически. При этом методе алгоритм решения весьма прост (рис. 2.1).

1. По оси абсцисс откладывается отрезок единичной длины.

2. По оси ординат откладываются выигрыши при стратегии А₁.

3. На линии, параллельной оси ординат, в точке 1 откладываются выигрыши при стратегии a₂.

4. Концы отрезков обозначаются для a₁₁-b₁₁, a₁₂-b₂₁, a₂₂-b₂₂ , a₂₁-b₁₂ и проводятся две прямые линии b₁₁b₁₂ и b₂₁b₂₂.

5. Определяется ордината точки пересечения с. Она равна g. Абсцисса точки с равна р₂ (р₁ = 1 - р₂).

 

Рис. 1.1. Оптимальная смешанная стратегия

 

Данный метод имеет достаточно широкую область приложения. Это основано на общем свойстве игр тґп, состоящем в том, что в любой игре тґп каждый игрок имеет оптимальную смешанную стратегию, в которой число чистых стратегий не больше, чем min(m, n). Из этого свойства можно получить известное следствие: в любой игре 2ґп и тґ2 каждая оптимальная стратегия и содержит не более двух активных стратегий. Значит, любая игра 2ґп и тґ2 может быть сведена к игре 2ґ2. Следовательно, игры 2ґп и тґ2 можно решить графически. Если матрица конечной игры имеет размерность тґп, где т > 2 и п > 2, то для определения оптимальных смешанных стратегий используется линейное программирование.

 

2. Мажорирование (доминирование) стратегий

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

 

 (1.27)

 

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

 

 (1.28)

 

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

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

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

В качестве иллюстрации к сказанному рассмотрим матрицу игры:

 

 (1.29)

 

Для первых двух чистых стратегий игрока 1 возьмем частоты их применения (вероятности) равными 0,25 и 0,75.

Третья стратегия игрока 1 мажорируется линейной выпуклой комбинацией первой и второй чистых стратегий, взятых с частотами 0,25 и 0,75 соответственно, т.е. смешанной стратегией:

 

24 Ч 0,25 + 0 Ч 0,75 = 6 > 4; (1.30)

0 Ч 0,25 + 8 Ч 0,75 = 6 > 5. (1.31)

 

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

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

 

 (1.32)

 

третья стратегия игрока 2 мажорируется смешанной стратегией из первой и второй его чистых стратегий, взятых с частотами 0,5 и 0,5:

 

10 Ч 0,5 + 0Ч0,5 = 5 < 6; (1.33)

0 Ч 0,5 + 10 Ч 0,5 = 5 < 7. (1.34)

 

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

 

 (1.35)

 

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

 

 

1.3 Игры с природой

 

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

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

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

 

2. ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ СМЕШАННЫХ СТРАТЕГИЙ

 

2.1 Постановка задачи

 

Выбрать оптимальный режим работы новой системы ЭВМ, состоящей из двух ЭВМ типов А₁ и А₂. Известны выигрыши от внедрения каждого типа ЭВМ в зависимости от внешних условий, если сравнить со старой системой.

При использовании ЭВМ типов А₁ и А₂ в зависимости от характера решаемых задач В₁ и В₂ (долговременные и краткосрочные) будет разный эффект. Предполагается, что максимальный выигрыш соответствует наибольшему значению критерия эффекта от замены вычислительной техники старого поколения на ЭВМ A₁ и А₂.

Итак, дана матрица игры (табл. 1), где A₁, А₂ - стратегии руководителя; В_1, В₂ - стратегии, отражающие характер решаемых на ЭВМ задач.

 

Таблица 2.1.

Игрок 2 Игрок 1	В1	В2	ai
А1	0,3	0,8	0,3
А2	0,7	0,4	0,4
bj	0,7	0,8

 

Требуется найти оптимальную смешанную стратегию руководителя и гарантированный средний результат g, т.е. определить, какую долю времени должны использоваться ЭВМ типов A₁ и А₂.

 

2.2 Описание алгоритма решения

 

Запишем условия в принятых обозначениях:

а₁₁ = 0,3; а₁₂ = 0,8; а₂₁ = 0,7; а₂₂ = 0,4.

 

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

 

a₁ = 0,3; a₂ = 0,4; a = 0,4; b₁=0,7; b₂ = 0,8; b = 0,7.