1.1.2. Решение матричных игр в чистых стратегиях (принцип минимакса)

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

Пусть игроки А и В располагают конечным числом возможных действий – чистых стратегий. Обозначим их соответственно А₁, А₂, …, А_m и В₁, В₂, …, В_n. Игрок А может выбрать любую чистую стратегию А_i , а игрок В может выбрать любую чистую стратегию В_j . Пара стратегий (А_i , В_j) однозначно определяет результат игры a_ij (a_ij – выигрыш игрока А или проигрыш игрока В при условии, если игрок A придерживается своей чистой стратегии A_i, а игрок B – чистой стратегии B_j)_. Если известны значения исхода игры a_ij для каждой пары (А_i , В_j) чистых стратегий, то можно составить платежную матрицу выигрышей игрока А (проигрышей игрока В) (рис. 1.1).

	B1	…	Bn	i
A1	a11	…	a1n	1
…	…	…	…	…
Am	am1	…	amn	m
j	1		n

Рис. 1.1. Платежная матрица игры

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

Используя этот принцип, найдем наилучшую стратегию игрока A. Выбирая стратегию A_i, мы должны рассчитывать, что игрок B ответит на нее той из своих стратегий B_j, для которой выигрыш игрока A будет минимальным. Найдем минимальное число a_ij в каждой строке матрицы:

.

Эта величина есть гарантированный (самый малый) выигрыш игрока A при выборе им чистой стратегии A_i. Значения _i обычно записываются в правом столбце платежной матрицы (см. рис. 1.1). Очевидно, что желающий перестраховаться игрок A должен предпочесть другим стратегиям ту, для которой гарантированный выигрыш _i максимален.

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

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

.

Значения _j записываются в дополнительной строке платежной матрицы (см. рис. 1.1).

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

Можно показать, что максимин не превосходит минимакс, т. е.   . Если в игре нижняя цена равна верхней (   ), то говорят, что игра имеет седловую точку и чистую цену игры     . Пару чистых стратегий ( , ), соотвествующих , называют седловой точкой матричной игры, а элемент a_ij^* платежной матрицы, стоящий на пересечении i^*-й строки и j^*-го столбца, – седловым элементом платежной матрицы. Он одновременно является минимальным в своей строке и максимальным в своем столбце. Стратегии и , образующие седловую точку, являются оптимальными. Значения ; ; называют решением игры.

Пример. В игре принимают участие два игрока. Каждый из игроков может записать независимо от другого цифру 4, 5 или 6. Если разность между цифрами, записанными игроками А и В положительна, то игрок А выигрывает количество очков, равное этой разности. Если разность отрицательна, то выигрывает игрок В. Если разность равна нулю, то игра заканчивается вничью. Составить платежную матрицу и найти решение игры.

Решение. Составим платежную матрицу игры. Чистыми стратегиями игрока А будут: А1 – записать число 4; А2 – записать число 5; А3 – записать число 6. У игрока В чистыми будут аналогичные стратегии. Элемент матрицы а₁₁ = 0, так как в ситуации (А1; В1) оба игрока записывают цифру 4 и выигрыш игрока А равен 4 – 4 = 0. В ситуации (А1; В2) выигрыш игрока А составит а₁₂ = 4–5 = –1. Аналогичным образом вычисляются остальные элементы платежной матрицы (рис. 1.2).

	B1 (4)	B2 (5)	B3 (6)	i
A1 (4)	0	–1	–2	–2
A2 (5)	1	0	–1	–1
A3 (6)	2	1	0*	0
j	2	1	0

Рис. 1.2. Платежная матрица примера

Определим минимальные гарантированные выигрыши игрока А, равные при выборе им стратегий А_i. Так, если игрок А записал цифру 4, то его минимальный выигрыш при выборе данной стратегии составит ₁ = min(0; –1; –2) = –2. Аналогично находим ₂ = min(1; 0; –1)= –1, если игрок А записал цифру 5 и ₃ = min(2; 1; 0) = 0, если им записана цифра 6. Найдем нижнюю цену игры игрока А, воспользовавшись “принципом максимина”, т. е. . Нижняя цена игры для игрока А составит  = max(–2; –1; 0) = 0. Таким образом, максиминному выбору игрока А будет отвечать третья стратегия, гарантирующая выигрыш, равный нулю.

Для игрока В значения элементов составят соответственно = 2, = 1, = 0. Верхняя чистая цена игры для игрока В по “принципу минимакса” составит = min (2; 1; 0) = 0. Следовательно, минимаксному выбору игрока В будет отвечать третья стратегия, гарантирующая минимальный проигрыш, равный нулю.

Так как   , то данная игра имеет седловую точку, т. е. третья чистая стратегия игрока А и третья чистая стратегия игрока В образуют седловую точку со значением 0 и данная матричная игра имеет решение (A₃; B₃; 0).