Матричные игры

Пусть игрок А имеет m чистых стратегий А₁, А₂, … А_i,…А_m, а игрок В имеет n чистых стратегий B₁, B₂, … B_j,…B_n. Такая игра называется игрой m х n. Если игрок А пользуется стратегией А_i, а игрок В пользуется стратегией В_j, то обозначим через а_ij выигрыш игрока А, если а_ij > 0, или проигрыш игрока А, если а_ij < 0. Очевидно, что – это одновременно проигрыш игрока В, если а_ij > 0, и выигрыш игрока В, если а_ij < 0.

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

Каждая строка этой матрицы соответствует некоторой стратегии игрока А, а каждый столбец – некоторой стратегии игрока В.

Пример игры. Два игрока выкидывают на пальцах числа, причем четное число пальцев – это выигрыш игрока А, нечетное – проигрыш игрока А. Для простоты введем ограничение – игроки выкидывают от 1 до 3 пальцев.

Составим платежную таблицу:

	В1	В2	В3	Вn
А1		-3		-3
А2	-3		-5	-5
А3		-5		-5
max i

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

a_i = а_ij.

В нашем примере a₁ = -3; a₂ = -5; a₃ = -5. Далее, среди полученных значений l_i-х определим максимальное

a = a_i = а_ij.

В нашем примере a = -3, т.е. игрок А проигрывает 3 очка. Это число a называется нижней ценой игры, а соответствующая ему стратегия называется максиминной. В нашем примере стратегия А₁ максиминная, т.е. из всех наихудших ситуаций выбирают наилучшую. Эта величина (a) – гарантированный «выигрыш» игрока А, какую бы стратегию ни выбрал игрок В.

Меньше нижней цены игры игрок А никогда не «выиграет».

Игрок В старается максимально уменьшить свой проигрыш. Для этого определяется верхняя цена игры

b = b_j = а_ij.

Соответствующая стратегия называется минимаксной. В нашем примере будет две минимаксных стратегии В₁ и В₂. При этом игрок В проигрывает 4 очка.

Теорема 1. В любой матричной игре справедливо неравенство a £ b, т.е. нижняя цена игры никогда не превосходит верхнюю.