3. Информационные множества
Следующим примером будет игра, в которой доступная игрокам информация не является полной. Игрок
, делая третий ход, не знает, какой выбор сделал
на втором ходу, и даже не помнит, какой выбор делал он сам на первом ходу. Этот пробел памяти со стороны
может осуществиться на практике, если игроком является команда из двух человек, из которых один делает первый ход, а другой — третий.
Пример 5.2. Ход I. Игрок
выбирает число
из множества {1, 2}.
Ход II. Игрок
, зная, какое число
было выбрано в первый ход, в свою очередь выбирает число у из множества {1, 2}.
Ход III. Игрок
не зная о выборе числа у и забыв, какое было выбрано
выбирает число 2 из множества {1, 2}.
После того как были выбраны три числа
и
, игрок
платит игроку
сумму
, где
— функция, определенная в примере 5.1.
Чтобы получить графическое представление этой игры, необходимо каким-то образом указать, что, когда
делает третий ход, он не знает о прошлых ходах, то есть, делая третий ход,
не знает, в каком именно узле рис. 8 он находится. Это дополнительное условие учтено на рис. И; здесь четыре узла, которые
не может различить, делая третий ход, окружены пунктиром.
Однако мы несколько видоизменим это изображение, обозначив пунктирными линиями некоторое разбиение всего множества узлов (за исключением самых верхних узлов, изображающих конечные точки игры, когда никаких выборов делать не нужно). Так мы получаем рис. 12.
Рис. И.
На нем самый нижний узел является в своей области единственным. Это показывает, что
во время первого хода знает точно, в какой точке дерева он находится; то же имеет место для двух узлов, соответствующих второму ходу. Мы будем обозначать множества, на которые разбиты узлы, информационными множествами.
Рис. 12.
Перейдем теперь к описанию стратегий этой игры. Очевидно, у
имеются те же стратегии, что и в примере 5.1, а именно, четыре функции
. Но поскольку
ничего не знает о предыдущем течении игры, его стратегией будет просто одна из упорядоченных пар чисел:
.
Например, когда говорят, что
применяет стратегию
, то это значит, что он выбирает 1 на первом ходу и 2 на втором.
Используя определение функции М, легко написать для новой игры матрицу стратегий.
Матрица 2
Мы замечаем, что эта игра не имеет седловой точки. С помощью теоремы 2.9 учащийся может проверить, что цена игры равна
, оптимальная стратегия для
и оптимальная стратегия для
. Таким образом, в этой игре
должен рассчитывать на меньший выигрыш, чем в игре, описанной в примере 5.1; это и неудивительно, так как он находится теперь в менее выгодном положении.
Замечание 5.3. В примере 5.2 матрица игры в нормальной форме имеет порядок лишь
тогда как в примере 5.1 матрица игры порядка
. Вообще при уменьшении количества доступной информации уменьшается число возможных стратегий и тем самым уменьшается размер матрицы. Это иногда кажется учащимся парадоксальным, так как уменьшение информации должно было бы привести к увеличению трудностей, а не к их уменьшению. Но размер матрицы не является верным показателем трудности игры; кроме того (это почти всеобщая истина), чем меньше мы знаем, тем легче нам решиться на что-нибудь (например, глухому человеку легче выбрать жену, чем человеку с нормальным слухом).
Изменив информационные множества, можно получить другие модификации игры, описанной в примере 5.1.
Пример 5.4. Ход I. Игрок
выбирает
из множества,
Ход II. Игрок
не зная значения
выбирает у из множества {1, 2}.
Ход III. Игрок
зная значение
и
, выбирает
из множества (1, 2}.
Платежная функция игры такая же, как в примере 5.1.
Для этой игры мы получаем диаграмму, изображенную на рис. 13; здесь мы включили два узла, соответствующие второму ходу, в одно и то же информационное множество, потому что во время второго хода игрок
не знает, в какой из этих точек он находится. Мы оставляем в качестве упражнения описание стратегий этой игры и определение матрицы стратегий.
Рис. 13.
Пример 5.5. Ход I. Игрок
выбирает
из множества {1, 2}.
Ход И. Игрок
не зная значения
выбирает у из множества {1, 2}.
Ход III. Игрок
не зная ни значения
ни значения у, выбирает z из множества {1, 2}.
Рис. 14,
Платежная функция игры такая же, как в примере 5.1.
Для этой игры мы получаем диаграмму, изображенную на рис. 14.
В этой игре стратегия игрока
состоит просто из пары чисел
, где i — его выбор на первом ходу, а
— на третьем.
Стратегией игрока
является число
, представляющее его выбор на втором ходу. Итак, у
имеются четыре стратегии, у
— две. Матрицей стратегий является матрица 3.
Матрица 3
Можно легко проверить, что цена игры равна
оптимальная стратегия для
и оптимальная стратегия для
. Таким образом, оказывается, что цена этой игры такая же, как цена игры, описанной в примере 5.2; итак, мы видим, что сведения, которыми обладает
в этой игре, не приносят ему пользы. Но это просто случайность, которая вызвана тем, что для определения платежной функции были взяты именно эти числа. Очевидно, вообще
может быть в лучшем положении в игре такого типа, как описанная в примере 5.2, чем в такой игре, как в примере 5.5.
Может показаться, что пример 5.5 представляет крайнюю степень неведения, в каком могут оказаться игроки, ибо ни один из них ни в один момент не знает, каковы были прошлые выборы. Но это не совсем так, поскольку игрок
делая третий ход, знает хотя бы то, что этому ходу предшествовали два. Нижеследующий пример показывает, что могут быть положения, когда нет даже этих сведений.
Пример 5.6. Дана игра двух лиц, в которой
— один человек, а
— команда из двух человек А и В. Эти три человека изолированы друг от друга в отдельных комнатах и во время игры не могут сообщаться между собой. В начале партии судья входит в комнату, в которой находится
и предлагает ему выбрать число х из множества {1, 2}.
Если
выбирает 1, то судья идет в комнату, в которой находится А, и предлагает ему выбрать число у из множества {1, 2}; если же
выбирает 2, судья идет в комнату, в которой находится В, и предлагает ему выбрать число у из множества {1, 2}. После того как было выбрано у, судья идет в комнату, в которой находится другой член команды
и предлагает ему выбрать число z из множества
После того как выбраны три числа,
платит игроку
сумму (
), где М определено следующим образом:
При рассмотрении этой игры нужно иметь в виду, что когда члену команды
предлагают сделать выбор, он не знает, делает ли он второй или третий ход партии, так как он не знает, какой выбор сделал
. Игра изображена на рис. 15.
Рис. 15.
У
имеются две стратегии: он может выбрать либо 1, либо 2. У
стратегии: А и В могут оба выбрать 1; или А может выбрать 1, а В может выбрать 2; или А может выбрать 2, а В может выбрать 1; или оба они могут выбрать 2. Мы представляем эти четыре стратегии соответственно упорядоченными парами:
Чтобы понять, как вычисляются платежи для различных стратегий, предположим, например, что
применяет стратегию 2, а
— стратегию
. Тогда на первом ходу
выбирает
, следовательно, судья идет сначала в комнату, в которой находится В, который выбирает
наконец, судья идет в комнату, в которой находится А, который выбирает
. Следовательно, платеж будет
Матрица 4 указывает платеж для всех возможных комбинаций стратегий. Цена игры равна
оптимальная стратегия для
, а для
.
Матрица 4