3. Максиминная и минимаксная стратегии игроков

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

Максиминная стратегия, принцип максимина

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

Пусть игрок 1 выбрал некоторую чистую стратегию. Посмотрим, какой выигрыш он может себе обеспечить при любом поведении противника.

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

= . (2.1)

Таким образом, α ≥ α_i для всех Стратегия соответствующая выбору строки матрицы А, минимальное значение в которой равно α, называется максиминной чистой стратегией, а величина α, вычисляемая по формуле (2.1), называется нижней ценой игры или максимином.

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

Минимаксная стратегия

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

(2.2)

будет минимальным проигрышем игрока 2, который он обеспечивает себе при любом ходе игрока 1. Ясно, что β ≤ β_j для всех .

Величина β, вычисляемая по формуле (2.2), называется верхней ценой игры или минимаксом. Стратегия , соответствующая выбору столбца матрицы А, максимальное значение в котором равно β, называется минимаксной чистой стратегией. Выбрав минимаксную чистую стратегию, игрок 2 проиграет не больше верхней цены игры.

Замечание. Если рассмотреть матрицу выигрышей В = (b_ij) игрока 2, где b_ij = -a_ij, то легко проверить, что определенная выше минимаксная стратегия будет максиминной для матрицы В. Таким образом, игрок 2 также действует в соответствии с принципом максимина.

Определим максиминную и минимаксную стратегию игроков в примерах.

В первом примере α₁ = -30, α₂ = 10, α₃ = -30; значит, α = 10. Максиминной является стратегия А₂ игрока 1, соответствующая выбору второй строки матрицы А. Выбрав ее, он обеспечивает себе выигрыш, равный 10, независимо от того, какую стратегию выберет игрок 2.

Соответственно, β₁ = 52, β₂ = 10, β₃ = 25, β₄ = 34 и, следовательно, β = 10. Минимаксной является стратегия В₂ игрока 2, соответствующая выбору второго столбца матрицы А (см. таблицу 2.1).

Таблица 2.1

	В1	В2	В3	В4	αi
А1	52	-20	-30	34	-30
А2	38	10	25	15	10
А3	28	-30	15	2 2	-30
βj	52	10	25	34	10 10

В примере 2 α₁ = 15, α₂ = 26, α₃ = 26 и, значит, α = 26. Максиминными являются стратегии А₂ и А₃ игрока 1, соответствующие выбору второй или третьей строки матрицы А. Выбрав любую из этих строк, игрок обеспечивает себе выигрыш, равный 26, независимо от выбора стратегии игроком 2.

Соответственно, β₁ = 35, β₂ = 26, β₃ = 32, β₄ = 27 и, следовательно, β = 26. Минимаксной является стратегия В₂ игрока 2, соответствующая выбору второго столбца матрицы А (см. таблицу 2.2).

Таблица 2.2

	В1	В2	В3	В4	αi
А1	32	25	30	15	15
А2	35	26	32	27	26
А3	28	26	30	26	26
βj	35	26	32	27	26	26

В примере 3 (игра в орлянку) α₁ = α₂ = -1 и, следовательно α = -1. В качестве максиминной стратегии игрока 1 может выступать любая из двух его чистых стратегий А₁ и А₂. Соответственно, β₁ = β₂ = 1 и, значит, β = 1. Минимаксной стратегией игрока 2 также будет любая из двух его чистых стратегий В₁ и В₂.

Таблица 2.3

	В1	В2	αi
А1	1	-1	-1
А2	-1	1	-1
βj	1	1	1	-1