1.2 Стратегии теории игр

игра экономический цена запас

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

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

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

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

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

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

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

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

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

Для игрока 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 при использовании обоими игроками смешанных стратегий. Следовательно, решением матричной игры является:

- оптимальная смешанная стратегия игрока 1;

- оптимальная смешанная стратегия игрока 2;

- цена игры.

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

(1.12)

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

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

и (1.13)

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

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

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

(1.14)

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

(1.15)

При этом

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

a₁₂p₁ + a₂₂p₂ = ; (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)

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

(1.23)

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

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

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

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

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

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

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

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

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

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

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

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