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

Решение матричных игр в смешанных стратегиях может быть найдено либо графиче­ски, либо методами линейного программирования. Графический метод применим для решения игр, в которых хотя бы один игрок имеет две чистые стратегии. Этот метод интере­сен в том плане, что графически объясняет понятие седловой точки. Методами линейно­го программирования может быть решена любая игра двух лиц с нулевой суммой.

5.4.1. Графическое решение игр

Рассмотрим игру , в которой игрок А имеет две стратегии (рис.5.4.1-1).

Вероятности		y1	y2	…	yn
		B1	B2	…	Bn
x1:	A1	a11	a12	…	a1n
x2:	A2	a21	a22	…	a2n
Рис.5.4.1-1.

Игра предполагает, что игрок А смешивает стратегии A₁ и A₂ с соответствующими ве­роятностями x₁ и (1 - x₁), 0 ≤ x₁ ≤1. Игрок В смешивает стратегии В₁, В₂,..., В_n с вероятно­стями y₁, y₂, ..., y_n, где y_j>0, j = 1, 2, ...,n, y₁+ y₂ + ... + y_n= 1. В этом случае ожидаемый выигрыш игрока А, соответствующий j-й чистой стратегии игрока В, вычисляется в виде

.

Следовательно, игрок А ищет величину x₁, которая максимизирует минимум ожидаемых выигрышей

.

Пример 5.4.1-1.

Рассмотрим следующую игру , в которой платежи выплачиваются игроку A. Платежная матрица

.

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

Таблица 5.4.1-1.

Чистые стратегии игрока В	Ожидаемые выигрыши игрока А
1	-2x1+4
2	-x1+3
3	x1+2
4	-7x1+6

На рис. 5.4.1-2 изображены четыре прямые линии, соответствующие чистым стратегиям игрока В. Чтобы определить наилучший результат из наихудших, построена нижняя огибающая четырех указанных прямых (изображенная на рисунке толстыми линейными сегментами), которая представляет минимальный (наихудший) выигрыш для игрока А независимо от того, что делает игрок В. Максимум (наилучшее) нижней огибающей соответствует максиминному решению в точке . Эта точка определяется пересечением прямых 3 и 4. Следовательно, оптимальным решением для игрока А является смешивание стратегий А₁ и А₂ с вероятностями 0,5 и 0,5 соответственно. Соответствующая цена игры определяется подстановкой x₁* в уравнение либо прямой 3, либо 4, что приводит к следующему результату.

Рис.5.4.1-2. Решение игры графическим методом

Оптимальная смешанная стратегия игрока В определяется двумя стратегия которые определяют нижнюю огибающую графика – стратегии 3 и 4 являются активными. Это значит, что игрок В может смешивать стратегии В₃ и В₄, в этом случае . Следовательно, ожидаемые платежи игрока В, соответствующие чистым стратегиям игрока А, имеют следующий вид.

Таблица 5.4.1-2.

Чистые стратегии игрока А	Ожидаемые выигрыши игрока В
1	4y3 - 1
2	-4y3 + 6

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

.

Его решением будет у₃ = 7/8, что определяет цену игры . Таким образом, решением игры для игрока А является смешивание стратегий А₁ и А₂ с равными вероятностями 0,5 и 0,5, а для игрока В – смешивание стратегий В₃ и В₄ с вероятностями 7/8 и 1/8. (В действительности игра имеет альтернативное решение для игрока В, так как максиминная точка на рис. 5.4.1-1 определяется более чем двумя прямыми. Отсюда следует, что стратегия В₂, которой на графике соответствует прямая под номером 2, также является активной. Любая выпуклая линейная комбинация этих альтернативных решений также является решением задачи).

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

В общем случае геометрическим методом могут решаться игры 2 × n и 3 × n. Активных стратегий в игре m × n, где m < n, не может быть более m. Поэтому игры 2 × n или 3 × m сводятся к играм 2 × 2 и 2 × 3.