Методы решения матричных игр

Аналитический метод

Рассмотрим наиболее простой случай конечных игр размера без седловой точки с платежной матрицей:

Требуется найти оптимальные смешанные стратегии игроков A и B и цену игры .

Каковы бы ни были действия противника, выигрыш будет равен цене игры . Это означает, что если первый игрок A придерживается своей оптимальной стратегии , то второму игроку B не имеет смысла отступать от своей оптимальной стратегии В игре , не имеющей седловой точки, обе стратегии являются активными.

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

Для второго игрока аналогично:

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

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

Пример. Дана платежная матрица

Найти решение.

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

для первого игрока –

где вероятность выбора первым игроком первой стратегии, вероятность выбора первым игроком второй стратегии;

для второго игрока –

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

Решая составленные системы уравнений, получаем:

Следовательно, оптимальные смешанные стратегии игроков имеют вид:

а цена игры

Это означает, что при выборе игроком А оптимальной смешанной стратегии против оптимальной смешанной стратегии игрока В, игрок А получит средний выигрыш 18/5 ден. ед., а игрок В – средний проигрыш 18/5 ден. ед.

Графический метод

Графический метод применим к играм, в которых хотя бы один игрок имеет только две стратегии.

1. Рассмотрим игру размера .

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

Ожидаемый выигрыш первого игрока A при применении вторым игроком B первой стратегии составит

Аналогично найдём ожидаемые выигрыши первого игрока при применении вторым игроком 2, 3, …, стратегий. Полученные данные поместим в следующую таблицу:

Таблица № 1.

Чистые стратегии второго игрока	Ожидаемые выигрыши первого игрока
…	………………….
N

Следовательно, ожидаемый выигрыш первого игрока А, соответствующий чистой стратегии игрока В, вычисляется в виде:

(3)

Игрок А должен выбирать такие стратегии, чтобы максимизировать свой минимальный ожидаемый выигрыш, т. е.

На плоскости уравнение (3) описывает прямую. Тем самым, каждой чистой стратегии игрока В на этой плоскости соответствует своя прямая. Для начала на плоскости (x₁, ) необходимо последовательно построить все прямые. Затем для каждого значения , путем визуального сравнения соответствующих ему значений на каждой из соответствующих прямых определяется и отмечается наименьшее из них.

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

Верхняя точка C построенной нижней огибающей определяет и цену игры, и оптимальную стратегию игрока А.

C

0 1 x₁

Рис. 1

2. Рассмотрим игру размера .

Тогда платежная матрица имеет вид:

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

Графиком функции

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

0 1 y₁

Рис. 2

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

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

Пусть – вероятность выбора первым игроком стратегии А₁, тогда – вероятность выбора первым игроком стратегии А₂.

Таблица № 2.

Чистые стратегии второго игрока	Ожидаемые выигрыши первого игрока

Строим на координатной плоскости все четыре прямые, уравнения которых получены в таблице № 2. Каждую из этих прямых строим по двум точкам – точке пересечения вертикальной оси при и точке пересечения с вертикальной прямой Затем находим нижнюю огибающую для построенных прямых.

6 (4)

4 (2)

(1) 3

2 (3) 2

0 1 x₁

Рис. 3

На пересечении прямых (3) и (4) нижней огибающей лежит её наивысшая точка. Решая систему уравнений

получаем

Значит, оптимальная стратегия первого игрока А и его цена игры соответственно равны:

Теперь найдем оптимальное решение второго игрока. Пусть – вероятности выбора вторым игроком стратегий В₁, В₂, В₃, В₄ соответственно. Выделяем из четырех чистых стратегий игрока В стратегии В₃ и В₄, которые соответствуют прямым (3) и (4), определяющим наивысшую точку нижней огибающей, тогда стратегии В₁, В₂ вторым игроком не выбираются, поэтому Найдем ожидаемые проигрыши второго игрока при применении игроком А первой и второй чистых стратегий.

Таблица № 3.

Чистые стратегии первого игрока	Ожидаемые проигрыши второго игрока

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

0 1 y₃

Рис. 4

Решая систему уравнений:

получаем

Следовательно, оптимальное решение второго игрока:

Полное решение игры будет иметь следующий вид:

Пример 2. Найти решение игры заданной платежной матрицей:

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

Пусть – вероятность выбора вторым игроком стратегии В₁, тогда – вероятность выбора вторым игроком стратегии В₂.

Таблица № 4.

Чистые стратегии первого игрока	Ожидаемые проигрыши второго игрока

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

6 (4)

4 (1)

3 (2) 3

2 (3) 2

0 1 y₁

Рис. 5

На верхней огибающей в точке пересечения прямых (1) и (3) расположено минимальное значение цены игры.

Решая систему уравнений этих прямых

получаем

Значит, оптимальная стратегия второго игрока В и его цена игры соответственно равны:

Пусть – вероятности выбора первым игроком стратегий А₁, А₂, А₃, А₄ соответственно. Прямые, пересекающиеся в минимаксной точке, соответствуют первой и третьей чистым стратегиям первого игрока, тогда стратегии А₂ и А₄ первый игрок не выбирает, это означает, что Следовательно, Найдем ожидаемые выигрыши первого игрока.

Таблица № 5.

Чистые стратегии второго игрока	Ожидаемые выигрыши первого игрока

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

2 2

0 1 x₁

Рис. 6

Решая систему уравнений:

получаем

Следовательно, оптимальное решение первого игрока:

Полное решение игры будет иметь следующий вид:

Правило доминирования

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

Рассмотрим игру размера с платежной матрицей:

.

Определение: Будем считать, что j-я стратегия матрицы А доминирует i-ю стратегию этой матрицы , если одновременно выполняются следующие n неравенств:

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

Определение: Будем считать, что l-й столбец матрицы А

доминирует k-й столбец этой матрицы

если одновременно выполняются следующие неравенства:

Если в матрице А один из столбцов (l-й) доминирует другой столбец (k-й), то число столбцов в матрице А можно уменьшать путем отбрасывания доминируемого столбца (k).

Замечание 1: Игрок А (игрок В) поступит разумно, если будет избегать стратегий, которым в матрице игры отвечают доминируемые строки (столбцы).

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

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

Пример. Рассмотрим игру с матрицей

.

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

Применим правило доминирования. Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой, или что то же, стратегия А₄ дублирует стратегию А₁. Значит одну из этих строк можно вычеркнуть, не нанося ущерба решению:

Сравнивая поэлементно 1-ю и 2-ю строки, замечаем, что все элементы 1-й строки больше либо равны соответствующим элементам 2-й строки, значит 1-я строка доминирует 2-ю строку, или, что то же, стратегия А₁ доминирует стратегию А₂. Это позволяет уменьшить число строк матрицы, т. е. можно вычеркнуть доминируемую сроку А₂:

Перейдем к рассмотрению столбцов. Замечая, что элементы 4-го столбца полученной матрицы меньше соответствующих элементов 3-го столбца, т. е. 4-й столбец доминирует 3-й столбец, приходим к игре размера с помощью вычеркивания 3-го столбца:

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: