ГЛАВА V. ИГРЫ В РАЗВЕРНУТОЙ ФОРМЕ

1. Нормальная и развернутая формы

Выше мы успешно рассмотрели решение прямоугольной игры двух лиц, то есть дали интуитивно приемлемое определение цены и оптимальных стратегий для такой игры, доказали, что решения всегда существуют, и даже показали, как их можно вычислить. Но рассуждения, к которым мы прибегали, хотя большей частью и элементарны, не всегда вполне тривиальны; и читателя, возможно, пугает задача распространения этих выводов на игры более общего вида, то есть с числом игроков >2 и такие, в которых некоторые ходы, возможно, связаны с применением случайных механизмов, игроки могут иметь по нескольку ходов каждый, и знание о ранее происшедшем может меняться от хода к ходу.

Однако положение не так уж плохо, как может показаться с первого взгляда, ибо оказывается, что задача решения игры, в которой игроки делают выборы из конечных множеств (мы будем называть такие игры конечными), всегда тождественна с задачей решения некоторой прямоугольной игры. Поэтому наши выводы о прямоугольных играх можно применить в более общем виде к любой игре двух лиц с нулевой суммой. Этот процесс отыскания прямоугольной игры, эквивалентной некоторой произвольной игре, называется нормализацией, а получающаяся прямоугольная игра называется игрой в нормальной форме;

когда нужно провести различие между этими видами игр, мы будем называть произвольные игры играми в развернутой форме. Начнем с примера игры в развернутой форме.

Пример 5.1. Ход I. Игрок выбирает число х из множества {1, 2}.

Ход II. Игрок , будучи информирован о том, какое число было выбрано на первом ходу, в свою очередь выбирает число у из множества

Ход III. Игрок будучи информирован о том, что второй игрок выбрал и помня, что сам он выбрал на первом ходу выбирает число 2 из множества {1, 2}.

После того как были выбраны три числа , и , игрок платит игроку сумму , где М есть функция, определенная следующим образом:

Чтобы объяснить, как привести игру к прямоугольной форме, введем общее понятие стратегии, которое мы рассматривали до сих пор лишь для прямоугольных игр. Стратегией данного игрока в данной игре мы назовем полный набор указаний, которые говорят ему, как нужно поступить во всех мыслимых ситуациях или, вернее говоря, при любом мыслимом состоянии информации, которую он может иметь а любой момент партии. Так, например, одна из стратегий, которую может применять в рассматриваемой игре, состоит в том, чтобы выбирать 1 во время обоих ходов (независимо от того, что делает на втором ходу). Другая возможная стратегия для выбирать 1 на первом ходу и затем на третьем выбирать то же число, которое выбрал на втором ходу. Возможная стратегия для — выбрать 1 на втором ходу, независимо от того, какой выбор сделал на первом ходу; другая возможная стратегия для — выбрать 1 на втором ходу, если на первом ходу было выбрано 2, и выбрать 2, если на первом ходу была выбрана единица.

Легко видеть, что у игрока в этой игре четыре стратегии, то есть как раз столько, сколько имеется способов отображения множества {1, 2} в себя.

Если мы обозначим через такую функцию, что

то четыре стратегии игрока суть . Говоря, что применяет, например, стратегию мы подразумеваем, что он репшл выбрать 2 на втором ходу, если выбрал 1 на первом, и выбрать 1 на втором ходу, если выбрал 2 на первом.

С другой стороны, стратегия игрока должна указывать ему, что нужно сделать на первом и на третьем ходу. Поскольку первому ходу ничто не предшествовало, у него нет сведений, которые позволили бы ему отличать разные случаи; поэтому стратегия должна просто указывать ему, нужно ли выбрать 1 или 2. Перед третьим ходом стратегия должна сказать ему, какое z нужно выбрать для каждого возможного выбора величин . Итак, стратегию игрока можно представить как систему

где — число, которое ему нужно выбрать на первом ходу, — число, которое ему нужно выбрать на третьем ходу в том случае, если было выбрано на первом ходу и на втором (поскольку каждое i может иметь два значения, у имеется всего 32 возможные стратегии). Если говорится, что применяет, например, стратегию

то это значит, что выбирает 1 на первом ходу; затем, если на первом ходу была выбрана 1 и на втором ходу также выбрал 1, то игроку на третьем ходу нужно выбрать 2, и аналогично для трех других возможностей для третьего хода.

В этой игре описанные нами стратегии игрока обладают некоторой избыточностью; так, второе «2» в данном примере бесполезно, так как оно означает, что если на втором ходу была выбрана 1, а на первом 2 (чего не могло быть, так как данная стратегия указывает игроку что на первом ходу нужно выбрать 1), то на третьем ходу нужно выбрать 2.

(Следовательно, это «2» говорит игроку что делать в таком случае, какого не может быть, если он применяет данную стратегию!). Эту избыточность можно устранить, считая стратегией игрока систему , где i — число, которое нужно выбрать игроку на первом ходу, — числа, которые ему нужно выбрать на третьем ходу, соответственно тому, выбрал ли на втором ходу 1 или 2. Итак, в этом случае мы могли бы упростить описание стратегий игрока , если учесть, что он помнит свой первый ход.

Но наличие этих избыточных сведений не приносит существенного вреда, а описание стратегий для общего случая весьма усложнится, если мы будем пытаться всегда избегать их. Полный разбор этого вопроса смотрите в работе Крентеля, Мак-Кинси и Куайна [61] и в работе Дэлки [22].

Выбрать возможную стратегию для игры и затем играть согласно этой стратегии — это. равносильно тому, чтобы составить все возможные решения перед началом игры. Как только каждый игрок выбрал стратегию, никаких других выборов ему не нужно делать, ибо стратегия предопределяет поведение игрока во все такие моменты игры, когда он должен был бы принимать решения, если бы он не выбрал стратегию. Выбор стратегии определяет исход игры, так что саму игру могла бы провести вычислительная машина.

Предположим, что в рассматриваемой игре игрок решает применять стратегию

а игрок решает применять стратегию . Из описания стратегии игрока мы видим, что на первом ходу он выбирает 1; из описания стратегии игрока следует, что на втором ходу он выбирает 2. Возвращаясь к стратегии игрока , мы заключаем, что на третьем ходу выбирает 1. Тогда, поскольку , мы видим, что если игроки применяют эту пару стратегий, то игрок должен будет заплатить 3 игроку Рассуждая аналогичным образом для других возможных пар стратегий, мы можем записать матрицу стратегий (матрица 1) для прямоугольной игры, к которой приводится данная игра.

Матрица 1 (см. скан)

Эта матрица имеет седловые точки, которые отмечены звездочками. Цена игры для равна 5. Любая из четырех стратегий

является оптимальной для а любая из стратегий или является оптимальной для По отношению к игре в ее первоначальной форме это значит, что один из оптимальных способов игры для следующий: на первом ходу выбрать 2; на третьем ходу выбрать то же число, которое выбрал на втором. Один из оптимальных способов игры для на втором ходу выбрать 1 независимо от того, что выбрал на первом ходу. Другой оптимальный способ игры для выбрать число, отличное от того, которое выбрал на первом ходу.