Vкаждый игрок выбирает одну из своих стратегий независимо от другого: первый одну из т стратегий, второй одну из п\
Vесли первый игрок выбирает стратегию /, а второй стратегию у, то первый игрок получает выигрьпи , который интерпретируется как
платеж от второго игрока.
Такая игра называется игрой двух лиц с нулевой суммой и представляется в виде матрицы игры (табл. 5.1), которая содержит выигрыши первого игрока (или, как отмечалось, проигрыши второго игрока).
Таблица 5.1
| Стратегия 1 Игрока 2 | Стратегия 2 Игрока 2 | | Стратегия п Игрока 2 |
Стратегия 1 Игрока 1 | | | | |
Стратегия 2 Игрока 1 | | | | 2« |
| | | | |
Стратегия т Игрока 1 | «1 | ««2 | | |
В табл. 5.2 приведена некоторая конкретная матрица игры, согласно которой вьшгрьш! первого игрока составит 2 единицы, если первый игрок выберет свою вторую стратегию, а второй игрок свою первую стратегию.
Таблица 5.2
| Стратегия 1 | Стратегия 2 | Стратегия 3 | Стратегия 4 |
Стратегия 1 | | | | |
Стратегия 2 | | | | |
В игре с нулевой суммой сумма выигрышей игроков всегда равна нулю. Как уже отмечалось, плательщиком выигрыша первого игрока является второй игрок. Таким образом, какая-либо кооперация между ними не возможна.
5.2.2. Верхнее и нижнее значение игры, условие седловой точки.
Предполагается, что каждый из игроков знает стратегию своего противника и платежную матрицу игры. Рассмотрим с этой точки зрения некоторую конкретную игру (табл. 5.3).
Таблица 53
| Стратегия 1 | Стратегия 2 | Стратегия 3 | Минимум по строкам |
Стратегия 1 | | | | |
Стратегия 2 | | | | |
Стратегия 3 | | | | |
Максимум по столбцам | | | | |
Как должен играть первый игрок? Если первый игрок выберет свою первую стратегию, то второй игрок, очевидно, выберет первую или вторую, поскольку в этом случае его потери будут минимальными - 4 единицы. Значение «4» является минимальным в первой строке. Рассуждая аналогично, легко видеть, что если первый игрок выбирает свою третью стратегию, то второй выбирает 3-ю, проигрывая при этом 1. Если первый игрок выбирает стратегию 2, то второй стра- И
Матрица удовлетворяет условию седловой точки в том случае, если: max (минимумы по строкам) = min (максимум по столбцам) или
V = max mm а.. • Ki<.m\<.j<j4
Величина
mm max a, \<.j\<j<m
max mm a..
называет-
\<d<.m\<,j<Jt J
СЯ нижней ценой игры, или максимальным гарантированным выигрышем первого игрока (максимином).
Величина min max а называстся
верхней ценой игры, или минимальным гарантированным проигрышем второго игрока (миннмаксом).
тегию 2 с проигрьппем 5. В крайнем правом столбце таблицы записаны минимумы по строкам. Логично предположить, что первый игрок будет выбирать стратегию, обеспечивающую ему выигрыш максимального из этих значений.
Мы показали, что первый игрок может гарантированно выиграть по крайней мере 5 единиц. Он понимает, что на большее он рассчитывать не может, так как, выбирая стратегию 2, второй игрок обеспечивает выигрыш первого не более 5.
Матрица, которую мы рассматриваем, удовлетворяет условию седловой точки:
max (минимумы по строкам) = min (максимум по столбцам). (5.1)
Говорят, что если выполнено условие (5.1), то игра имеет седловую точку, В строго математическом виде это можно переписать как
V = max min а„ = min max а.,.(5.2)
Справедлива следующая теорема:
Теорема 1. Для любой конечной игры выполнено соотношение max min а..< min max а.,.
\ui<,m\uj<.n IJ lujunlium
Доказательство: Очевидно, что
min a, < a,,
отсюда получаем
max mm <maxa...
\iumluj<nl<i<m
Так как в этом неравенстве слева стоит конкретное число, а справа - выражение, зависящее отj\ то справедливо следующее неравенство
max min а,, < min max а..,
что и требовалось доказать.
Назовем величину max min а., нижней ценой игры, или максимальным
гарантированным вьшгрьш1ем первого игрока (максимином). Стратегия, соответствующая максимину, называется максиминной стратегией.
Назовем величину min max л... верхней ценой игры, или минималь-
\<.j<n\ui<m
ным гарантированным проигрьппем второго игрока (минимаксом). Стратегия, соответствующая минимаксу называется минимаксной стратегией.
Как было доказано, нижнее значение любой матричной игры не превосходит верхнего значения.
Если игра имеет седловую точку, то первый игрок может выбирать любую стратегию, для которой реализуется максимум в левой части соотношения (5.2) (максиминная стратегия), а второй игрок может выбрать любую стратегию, на которой реализуется минимум в правой части соотношения (5.2) (минимаксная стратегия). Если игра имеет седловую точку, то общее значение v, которое достигается слева и справа в соотношении (5.2), называется ценой игры.
Седловая точка может рассматриваться как точка равновесия в том смысле, что отклонение от нее для каждого из игроков невыгодно. Действительно, в нашем примере если первый игрок сменит свою оптимальную стратегию 2 на 1 или 3, то выигрыш первого (соответственно проигрыш второго) увеличится. 114