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

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

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

	В₁	В₂	…	В_j	…	В_n
А₁	а₁₁	а₁₂	…	а₁_j	…	а_1n
…	…	…	…	…	…	…	(7.1)
А_i	а_i₁	а_i2…	…	а_ij	…	а_in
…	…	…	…	…	…	…
А_m	а_m₁	а_m₂	…	а_mj	…	а_m_n

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

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

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

	В₁	В₂	В₃
А₁		-3		-3
А₂	-3		-5	-5
А₃		-5		-5

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

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, т.е. нижняя цена игры никогда не превосходит верхнюю.

Игра с седловой точкой

Если в матричной игре нижняя и верхняя цены игры совпадают, то такая игра имеет «седловую точку» в чистых стратегиях, а число u = a = b называют ценой игры. В этом случае решением игры, т.е. оптимальным поведением для обоих игроков являются их максиминная для игрока А и минимаксная для игрока В стратегии игры. Любое отклонение игроков от своих оптимальных стратегий не может оказаться им выгодным. Элемент платежной матрицы, отвечающий оптимальным стратегиям, называется седловой точкой.

Пример. Пусть игра задана следующей платежной матрицей: