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

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

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

	В1	В2	…	Вj	…	Вn
А1	а11	а12	…	а 1j	…	а 1n
(39) А2	а21	а 22	…	а 2j	…	а 2n
…	…	…	…	…	…	…
Аi	аi1	а i2…	…	а ij	…	а in
…	…	…	…	…	…	…
Аm	аm1	а m2	…	а mj	…	а mn

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

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

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

	В1	В2	В3	min
А1	2	-3	4	-3
А2	-3	4	-5	-5
А 3	4	-5	6	-5
max	4	4	6

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

_i = а_ij.

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

 = _i = а_ij.

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

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

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

 = _j = а_ij.

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

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