2.2 Алгоритм решения парной игры с нулевой суммой

Задача 1. Дана платежная матрица 3 х 4, которая определяет выигрыш первого игрока.

10 4 11 7

А = | а_ij | = 7 6 8 20 .

6 2 1 11

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

Последовательность решения задачи.

1 Представим игру в виде таблицы:

Стратегии Игрока I	Стратегии игрока II				Значение, α ј	α
	В1	В2	В3	В4
А1	10	4	11	7	4	-
А2	7	6	8	20	6	6
А3	6	2	1	11	1	-
Значение βі	10	6	11	20	-	-
Β	-	6	-	-	-	-

2 Проанализируем последовательно каждую стратегию игрока 1. Если игрок 1 выбирает стратегию А₁, он может получить выигрыш в размере 10, 4, 11, 7 единиц в зависимости от выбранной стратегии игроком II. При этом выигрыш игрока будут не меньше:

α ₁ = min 10, 4, 11, 7 = 4 ед.

независимо от поведения игрока 2.

Аналогично, при выборе игроком 1 стратегии А₂ гарантированный выигрыш будет равен:

α ₂ = min 7, 6, 8, 20 = 6 ед.

П ри выборе игроком 1 стратегии А₃ гарантированный выигрыш его будет равен

α ₃ = min 6, 2, 1, 11 = 1 ед

З атем из всех α _i = 4, 6, 1 игрок I выделяет наибольшее α = max α _i ,

i

т.е. в данном случае число 6, и выбирает соответствующую ему чистую стратегию А2. Ее называют максиминной, поскольку она отвечает величине

α = max min α _{i j} . ( 1 )

i j

Число α , определяемое по формуле ( 1 ), называется нижней чистой ценой игры (максимином). Оно показывает, какой минимальный выигрыш может получить игрок I, правильно применяя свои чистые стратегии при любых действиях игрока II.

В свою очередь, игрок II, стремясь минимизировать проигрыш, использует принцип: сначала для каждой чистой стратегии В_j ( j = 1,2,3,4) найдет максимально возможный проигрыш β_j = max α _{i j} ( j = 1,2,3,4), т.е.

I

для стратегии В₁: β₁ = max 10, 7, 6 = 10,

В₂: β₂ = max 4, 6, 2 = 6,

В₃: β₃ = max 11, 8, 1 = 11,

В₄: β₄ = max 7, 20, 11 = 20.

Затем среди β_j ( j = 1,2,3,4) выберет минимальное значение β = min β_j:

j

β = min (10, 6, 11, 20 ) = 6,

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

β = min max β _{i j .} (2)

j i

Число β, определяемое по формуле (2), называется верхней чистой ценой игры (минимаксом). Оно показывает, какой максимальный проигрыш может быть у игрока II, при правильном выборе им своих чистых стратегий независимо от действий игрока 1.

Таким образом, решением игры будет: выбор игроком I стратегии А2, выбор игроком II стратегии В2, цена игры равна υ = α = β = 6.

Теорема 1 (без доказательства). В матричной игре нижняя чистая цена игры не превосходит верхней чистой цены игры, т.е. α < β.

Если в матричной игре нижняя и верхняя чистые цены совпадают, т.е. α = β, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры υ = α = β.