5.2. Верхнее и нижнее значения игры, условие седловой точки

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

Таблица 5.3

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

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

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

v=max min a_ij = min max a_ij (5.1)

i j j i

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

i j

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

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

j i

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

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

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

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

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

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

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