Понятие о нижней и верхней цене игры. Решение игры в чистых стратегиях

Запись матричной игры в виде платежной матрицы

Рассмотрим конечную игру, в которой первый игрок А имеет m стратегий, а второй игрок B-n стратегий. Такая игра называется игрой m×n. Обозначим стратегии A₁, А₂, ..., А_m; и В₁, В₂, ..., В_n. Предположим, что каждая сторона выбрала определенную стратегию: A_i или B_j. Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры — выигрыш одной из сторон a_ij. Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A_i и B является случайной величиной, зависящей от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша, которое также обозначается за a_ij.

Предположим, что нам известны значения a_ij при каждой паре стратегий. Эти значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям A_i, а столбцы — стратегиям B_j.

Тогда, в общем виде матричная игра может быть записана следующей платежной матрицей:

	B1	B2	...	Bn
A1	a11	a12	...	a1n
A2	a21	a22	...	a2n
...	...	...	...	...
Am	am1	am2	...	amn

Таблица — Общий вид платежной матрицы матричной игры

где A_i — названия стратегий игрока 1, B_j — названия стратегий игрока 2, a_ij — значения выигрышей игрока 1 при выборе им i–й стратегии, а игроком 2 — j-й стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока 2 является величиной, противоположенной по знаку значению выигрыша игрока 1.

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

V_н = max_i min_j a_ij

или найти минимальные значения по каждой из строк платежной матрицы, а затем определить максимальное из этих значений. Величина V_н называется максимином матрицы или нижней ценой игры. Та стратегия игрока, которая соответствует максимину V_н называется максиминной стратегией.

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

Величина выигрыша игрока 1 равна, по определению матричной игры, величине проигрыша игрока Поэтому для игрока 2 необходимо определить значение

V_в = min_j max_i a_ij

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

В случае, если значения V_н и V_в не совпадают, при сохранении правил игры (коэффициентов a_ij ) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве V_н = V_в = V. В этом случае говорят, что игра имеет решение в чистых стратегиях, а стратегии, в которых достигается V — оптимальными чистыми стратегиями. Величина V называется чистой ценой игры [8].

Например, в матрице:

	B1	B2	B3	B4	Minj
A1
A2
A3
Maxi

Таблица — Платежная матрица, в которой существует решение в чистых стратегиях

существует решение в чистых стратегиях. При этом для игрока 1 оптимальной чистой стратегией будет стратегия A₁, а для игрока 2 — стратегия B₄.

В матрице решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A₁ и ее значение равно 12, в то время как верхняя цена игры достигается в стратегии B₄ и ее значение равно 13.

	B1	B2	B3	B4	Minj
A1
A2
A3
Maxi

Таблица — Платежная матрица, в которой не существует решения в чистых стратегиях