3. Игры с идеальной памятью и стратегии поведения

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

Это понятие игры с идеальной памятью можно определить точно через информационные множества игры. Игра с идеальной памятью — это игра, удовлетворяющая следующему условию: пусть Р и Q — любые два хода, которые делает один игрок, и такие, что в некоторой партии игры ход Р предшествует ходу Q; U и V — информационные множества, содержащие соответственно Р и Q; каждая точка множества U дает к альтернатив; — множество всех узлов дерева (то есть ходов), которых можно достигнуть, выбрав альтернативу в некоторой точке множества U; тогда для любого i мы имеем .

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

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

Рис. 30.

С другой стороны, стратегия поведения для есть функция, определенная только на , со значением в . Итак, стратегия поведения для в этой игре по существу — такая же, как и смешанная стратегия; это, очевидно, всегда имеет место, когда у игрока лишь одно информационное множество.

Теперь предположим, что применяет стратегию поведения f такую, что

а применяют стратегию поведения g такую, что

Тогда математическое ожидание выигрыша игрока или (как мы будем иногда писать) выражается формулой

Интуитивно очевидно и нетрудно доказать формально, что, применяя смешанные стратегии, игрок поступает по крайней мере не хуже, чем в случае применения стратегий поведения; но легко построить игры, в которых игроку лучше применять смешанные стратегии, чем любую стратегию поведения. С другой стороны, можно показать, что игра с идеальной памятью всегда имеет оптимальные стратегии поведения; если Е есть математическое ожидание выигрыша для игры с идеальной памятью, то имеется стратегия поведения для и стратегия поведения g для такие, что если — любые смешанные стратегии (или любые стратегии поведения) соответственно для то

(В исторических и библиографических замечаниях в конце этой главы указано, где можно найти доказательство этой теоремы.)

Пример 6.4. Рассмотрим игру, диаграмма которой приведена на рис. 30. Поскольку это игра с идеальной памятью, очевидно, имеются оптимальные стратегии поведения для обоих игроков. Как и раньше, мы имеем:

Коэффициент при в этом уравнении равен ; так как он никогда не бывает положительным, то, очевидно, игрок поскольку он хочет увеличить , должен взять

Коэффициент при равен

и никогда не может быть отрицательным, поэтому игроку лучше всего взять

Поскольку, наконец,

мы заключаем, что для лучше всего взять

и подобно этому для игрока лучший выход — взять

Итак, оптимальная система игры для бросить монету, чтобы решить, какую альтернативу выбрать в выбирать всегда левую альтернативу в и выбирать всегда правую альтернативу в

Замечание 6.5. Следует заметить, что вообще число параметров, которые нужно определить при вычислении оптимальных стратегий поведения, гораздо меньше, чем число параметров, связанных с вычислением оптимальных смешанных стратегий. Так, в примере 6.4 при вычислении оптимальной стратегии поведения для нам нужно было иметь дело лишь с тремя параметрами. С другой стороны, поскольку игрок в этой игре имеет восемь чистых стратегий, смешанная стратегия есть элемент множества и, следовательно, вычисление оптимальных смешанных стратегий связано с семью независимыми параметрами.

Однако это преимущество стратегии поведения, по крайней мере частично, компенсируется тем, что математическое ожидание обычно удобнее выражать через смешанные стратегии.

Библиографические замечания

Данное выше формальное определение игр в развернутой форме весьма сходно с определением, которое приведено в работе Куна [63]. Там же приведено доказательство теоремы 6.1. Понятие точки равновесия было введено в работе Нэша [85]. Он же дал доказательство того, что во всякой игре n лиц среди смешанных стратегий имеется точка равновесия.

Доказательство того, что игра с идеальной памятью имеет оптимальные стратегии поведения, можно найти у Куна

[63].