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

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

То есть, игрокам надо так выбирать свои чистые стратегии в очередной партии, чтобы партнер не догадался о них. Этого можно добиться только тогда, когда сам не знаешь, какую стратегию будешь использовать при очередном ходе. Анализ игры без седловой точки показывает, что игрок А выигрывает больше максимина α, получаемого им при максиминной стратегии, если в ходе игры будет пользоваться не одной, а несколькими чистыми стратегиями, т.е. будет смешивать чистые стратегии. Аналогично – игрок В проигрывает меньше минимакса β, выплачиваемого им игроку А, при минимаксной стратегии, если он будет использовать свою смешанную стратегию.

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

Обычно смешанную стратегию первого игрока обо­значают как вектор

U = ,

где р_i – вероятность выбора игроком А i- ой стратегии.

а второго игрока – как вектор

Z = ,

где q_j, ≥ 0 – вероятность выбора игроком B j- ой стратегии

.

Если р^o – оптимальная стратегия первого игрока, q ° - оптимальная стратегия второго игрока, то число

- называют ценой игры.

Для того чтобы число υ – было ценой игры, а p^o и q ° – оптимальными стратегиями, необходимо и до­статочно выполнение неравенств:

, где (j = 1,..., n),

, где (i = 1,..., m).

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

Пример. Найти решение игры, заданной матрицей .

Решение

Сначала, проверяется наличие седловой точки.

Таблица 3.

	В1	В2
А1 А2			2(Т1) 4(Т2)

Для этого определяются минимальные элементы в каж­дой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5) (Табл. 3).

Значит, нижняя цена игры

,

верхняя цена игры

.

Так как α = 4 ≠ β = 5, то игра седловой точки не имеет и ее решение – смешан­ные оптимальные стратегии, а цена игры лежит в пределах 4≤ ≤5.

Пусть для игрока А стратегия задается вектором U = (p₁, p₂). Тогда при применении игроком В чистой стратегии В₁ или В₂ игрок А получит средний выигрыш, равный цене игры, то есть

Из решения трех уравнений с тремя неизвестными оптимальная стратегия игрока А₁: ; ; v = .

Пусть для игрока В стратегия задается вектором Z = (q₁, q₂). Тогда:

Отсюда оптимальная стратегия игрока В: Следовательно, решением игры будут смешанные стратегии , с оценкой игры v = . Таким образом, если, например, имеется многоходовая игра, то из пяти партий игрок А два раза выбирает первую стратегию и три раза выбирает вторую стратегию, а игрок В один раз использует первую стратегию, и четыре раза – вторую стратегию. В этом случае выигрыш является оптимальным для двух сторон.

 

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

Пусть задана платежная матрица игры:

.

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

, где (j = 1,..., n),

Разделив обе его части на получим:

1.

 

Обозначив, получим:

Так как первый игрок стремится получить макси­мальный выигрыш, то он должен обеспечить минимум величине 1/ . С учетом этого определение оптимальной стратегии первого игрока сводится к нахождению минимума функции:

при условиях:

.

Аналогично определение оптимальной стратегии вто­рого игрока сводится к нахождению максимума функции:

при условиях:

,

где .

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

 

Прямая задача (задача второго игрока)	Двойственная задача (задача первого игрока)
Целевая функция
Z(x) = x1 + x2 + … + xn → max	U(y) = y1 + y2 + … + ym → min
Функциональные ограничения
а11х1 + а12х2 + … + а1nхn ≤ 1 a21х1 + а22х2 + … + а2nхn ≤ 1 … … … am1х1 + аm2х2 + … + аmnхn ≤ 1	а11у1 + а21у2 + … + аm1уm ≥ 1 а12у1 + а221у2 + … + аm2уm ≥ 1 … … … а1nу1 + а2nу2 + … + аmnуm ≥ 1
Прямые ограничения
x1 ≥0, x2 ≥0, …, xn ≥0	y1 ≥0, y2 ≥0, …, ym ≥0

 

Используя решения пары задач, можно выявить оп­тимальные стратегии и цену игры:

; ; .

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

1) составляют пару двойственных задач, эквивалент­ных данной игре;

2) определяют оптимальные планы двойственных задач;

3) находят решение игры по соотношениям между планами задач, оптимальными стратегиями и ценой игры.

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