Задача № 8

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

Найдите оптимальные стратегии игроков и цену игры.

Стратегии 1 игрока	Стратегии 2-го игрока
	B1	B2	B3
A1	2	-7	0
A2	-4	-5	-3
A3	-1	-6	1

Решение

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

1. Прежде всего воспользуемся тем фактом, что если к каждому элементу платежной матрицы прибавить одно и то же число C, то это не поменяет набора оптимальных стратегий игроков, а лишь увеличит цену игры на C. Это свойство позволяет любую платежную матрицу преобразовать к матрице с неотрицательными элементами.

Очевидно, в нашем случае удобно взять C=7. Преобразованная платежная матрица примет вид:

Стратегии 1 игрока	Стратегии 2-го игрока
	B1	B2	B3
A1	9	0	7
A2	3	2	4
A3	6	1	8

2. Нижней ценой игры v₁ называется наилучший из наихудших платежей 1-го игрока.

Таким образом, для определения нижней цены игры v₁необходимо определить минимальные платежи в каждой строке платежной матрицы, а затем выбрать из них наибольший.

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

3. Верхней ценой игры v₂ называется наилучший из наихудших платежей 2-го игрока.

Таким образом, для определения верхней цены игры v₂ необходимо определить максимальные платежи в каждом столбце платежной матрицы, а затем выбрать из них наименьший.

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

4. Как доказывается в теории игр и статистических решений, всегда выполняется следующее неравенство .

Если для игры имеет место равенство , то такая игра называется игрой с седловой точкой, а v называется ценой игры. В этом случае максиминная стратегия является оптимальной для 1-го игрока, а минимаксная — для 2-го игрока.

5. Применяя изложенные выше правила к преобразованной платежной матрице, получаем:

Стратегии 1-го игрока		Стратегии 2-го игрока						min по строке
		B1		B2		B3
A1	9		0		7		0
A2	3		2		4		2
A3	6		1		8		1
max по столбцу	9		2		7

Таким образом, . Это и есть цена преобразованной игры. Цена исходной игры

Ответ: оптимальной стратегией для 1-го игрока является стратегия A₂, для 2-го игрока— B₂. Цена игры .