Игры двух лиц с нулевой суммой

Игра двух лиц с нулевой сум­мой задается следующими условия­ми:

- имеются два игрока, стратегии одного из которых расположены по строкам (первый игрок), а другого по столбцам (второй игрок);

- каждый игрок выбирает одну из своих стратегий независимо от друго­го: первый одну из т стратегий, второй одну из п;

- если первый игрок выбирает стратегию i, а второй стратегию j, то первый игрок получает выигрыш a_ij, который интерпретируется как платеж от второго игрока.

Такая игра называется игрой двух лиц с нулевой суммой и пред­ставляется в виде матрицы игры (табл. 7.1), которая содержит выиг­рыши первого игрока (или, как отмечалось, проигрыши второго игро­ка).

Таблица 7.1 – Пример матрицы игры

В табл. 7.2 приведена некоторая конкретная матрица игры, согласно которой выигрыш первого игрока составит 2 единицы, если первый иг­рок выберет свою вторую стратегию, а второй игрок свою первую стра­тегию.

Таблица 7.2

В игре с нулевой суммой сумма выигрышей игроков всегда равна ну­лю. Как уже отмечалось, плательщиком выигрыша первого игрока явля­ется второй игрок. Таким образом, какая-либо кооперация между ними невозможна.

Предполагается, что каждый из игроков знает стратегию своего против­ника и платежную матрицу игры. Рассмотрим с этой точки зрения неко­торую конкретную игру (табл. 7.3).

Таблица 7.3 – Матрица игры

Как должен играть первый иг­рок? Если первый игрок выберет свою первую стратегию, то второй игрок, очевидно, выберет первую или вторую, поскольку в этом слу­чае его потери будут минимальны­ми - 4 единицы. Значение «4» явля­ется минимальным в первой строке. Рассуждая аналогично, легко ви­деть, что если первый игрок выби­рает свою третью стратегию, то второй выбирает 3-ю, проигрывая при этом 1. Если первый игрок вы­бирает стратегию 2, то второй стра­тегию 2 с проигрышем 5. В крайнем правом столбце таблицы записаны минимумы по строкам. Логично предположить, что первый игрок будет выбирать стратегию, обеспечивающую ему выигрыш максимального из этих значений.

Мы доказали, что первый игрок может гарантированно выиграть, по крайней мере, 5 единиц. Он понимает, что на большее он рассчитывать не может, так как, выбирая стратегию 2, второй игрок обеспечивает выиг­рыш первого не более 5.

Матрица удовлетворяет усло­вию седловой точки в том случае, если: max (минимумы по строкам) = min (максимум по столбцам) или

v=max min a_ij = min max a_ij (7.1)

i j j i

Величина v=max min a_ij, называется нижней ценой игры, или максималь-

i j

ным гарантированным выигры­шем первого игрока (максимином).

Величина v=min max a_ij, называется верхней ценой игры, или максималь­-

j i

ным гарантированным проигры­шем второго игрока (минимаксом).

Матрица, которую мы рассматриваем, удовлетворяет условию седловой точки (7.1):

max (минимумы по строкам) = min (максимум по столбцам). (7.2)

Говорят, что если выполнено условие (7.1), то игра имеет седловую точку.

Если игра имеет седловую точку, то первый игрок может выбирать любую стратегию, для которой реализуется максимум в левой части со­отношения (7.1) (максиминная стратегия), а второй игрок может выбрать любую стратегию, на которой реализуется минимум в правой части со­отношения (7.1) (минимаксная стратегия). Если игра имеет седловую точку, то общее значение v, которое достигается слева и справа в соот­ношении (7.1), называется ценой игры.

Седловая точка может рассматриваться как точка равновесия в том смысле, что отклонение от нее для каждого из игроков невыгодно. Дей­ствительно, в нашем примере если первый игрок сменит свою оптималь­ную стратегию 2 на 1 или 3, то выигрыш первого (соответственно проиг­рыш второго) увеличится.

В итоге будет разумно ожидать, что в описанной выше игре противники будут придерживаться избранных стратегий. Матрич­ная антагонистическая игра, для которой max min a_ij = min max a_ij называется вполне определенной, или игрой, имеющей решение в чис­тых стратегиях.