Учебное пособие: Матричные игры

Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:

; ;

; ;

.

Ответ: ; ; .

Другой вариант игры 2x2 получается, если использовать стратегии А₂ и А₆. В этом случае платежная матрица имеет вид

Тогда

; ;

; ;

.

Ответ: ; ; .

Естественно, что цена игры для обоих вариантов одинакова.

В заключение наметим общую схему решения матричных игр 2xn и mx2:

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

2. Производится упрощение матричной игры путем исключения дублирующих и доминируемых стратегий. Если упрощенная игра имеет размерность не 2x2, то переходим к этапу 3.

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

4. Решается матричная игра 2x2.

ТЕСТЫ

(В - Верно, Н - Неверно)

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

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

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

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

5. Прибавление одного и того же числа ко всем элементам платежной матрицы не влияет на цену игры.

6. Умножение всех элементов платежной матрицы на одно и тоже положительное число не изменяет оптимальных стратегий игроков.

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

8. Любая матричная игра 2xn или mx2 может быть сведена к игре 2х2.

Ответы: (1 - В; 2 - В; 3 - В; 4 - В; 5 - Н; 6 - В; 7 - Н; 8 - В).

ЗАДАЧИ

Решить следующие матричные игры:

2.8 Решение игр mхn. Эквивалентные задачи линейного программирования

Пусть имеется матричная игра mxn без седловой точки с матрицей выигрышей ||a_ij||. Допустим, что все выигрыши a_ij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на C, а оптимальные решения S_A и S_B не изменятся).

Если все aij положительны, то и цена игры при оптимальной стратегии тоже положительна, т.к. .

В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий S_A=||p₁, p₂, ..., p_m|| и S_B=||q₁, q₂, ..., q_n||, применение которой обеспечивает игрокам получение цены игры .

Найдем вначале S_A. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии S_B и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем :

(2.25)

Разделив левую и правую часть каждого из неравенств (2.25) на положительную величину v и введя обозначения:

(2.26)

запишем неравенства (2.25) в следующем виде:

, (2.27)

где x₁, x₂, ... x_m - неотрицательные переменные.

В силу того, что

p₁+p₂+...+p_m=1,

переменные x₁, x₂, ... x_m удовлетворяют условию

. (2.28)

Учитывая, что игрок А стремится максимизировать , получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x₁, x₂, ... x_m такие, чтобы они удовлетворяли линейным ограничениям - неравенствам (2.27) и обращали в минимум линейную функцию этих переменных:

min L(x)=x₁+x₂+ ... +x_m. (2.29)

Из решения задачи линейного программирования находим цену игры и оптимальную стратегию Sa по формулам:

, (2.30)

, . (2.31)

Аналогично находим оптимальную стратегию S_В игрока В. Предположим, что игрок А отказался от своей оптимальной стратегии S_A и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем :

. (2.32)

Разделив левую и правую части каждого их неравенств (2.32) на положительную величину и введя обозначения:

, (2.33)

запишем неравенство (2.32) в следующем виде:

, (2.34)

где y₁, y₂, ..., y_n - неотрицательные переменные.

В силу того, что q₁+q₂+...+q_n=1, переменные y₁, y₂, ..., y_n удовлетворяют условию

. (2.35)

Учитывая, что игрок В стремится минимизировать положительную цену v (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y₁, y₂, ..., y_n такие, чтобы они удовлетворяли линейным ограничениям (2.34) и обращали в максимум линейную функцию этих переменных:

max L(y)=y₁+y₂+ ... +y_m. (2.36)

Эта задача является двойственной по отношению к задаче, представленной условиями (2.27) и (2.29).

Оптимальная стратегия S_B=||q₁, q₂, ..., q_n|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:

, . (2.37)

Таким образом, оптимальные стратегии S_A=||p₁, p₂, ..., p_m|| и S_B=||q₁, q₂, ..., q_n|| матричной игры mxn с платежной матрицей ||a_ij|| могут быть найдены путем решения пары двойственных задач линейного программирования:

При этом

, (2.38)

.

Пример. Найти решение и цену матричной игры, платежная матрица которой имеет вид

Решение

1. Так как =1 не равно =3, то игра не имеет седловой точки.

2. В данной игре нет дублирующих и доминируемых стратегий.

3. Решаем игру путем решения пары двойственных задач линейного программирования.

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

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

Начальная симплекс - таблица двойственной задачи имеет вид

ведущий столбец

ведущий столбец

ведущий столбец

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

Оптимальное решение двойственной задачи линейного программирования следующее:

у₁=; у₂=; у₃=; max L (y)= .

Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (2.37) и (2.38):

;

.

Следовательно, .

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

Получаем x₁=; x₂=; x₃=; max L (x)= .

Отсюда определим вероятности применения своих активных стратегий игроком А:

.

Следовательно: .

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

ТЕСТЫ

(В - Верно, Н - Неверно)

Если все элементы платежной матрицы в матричной игре положительны, то и цена игры положительна.

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

В прямой задаче линейного программирования, к которой сводится матричная игра, целевая функция подлежит максимизации.

В обратной задаче линейного программирования, к которой сводится матричная игра, ограничения получаются со знаком «».

Цена матричной игры, получаемая из решения прямой и обратной задач может быть различна.

Ответы: (1 - В; 2 - В; 3 - Н; 4 - В; 5 - Н).

ЗАДАЧИ

Решить следующие матричные игры: