Стратегические игры. Доступный учебник по теории игр

Диксит Авинаш

В двух средних исходах присутствует некоторая неоднозначность. Предположим, каждый игрок ценит привлекательный сад более высоко, чем собственный вклад в его создание. В таком случае исход, указанный в списке вторым, обеспечит выигрыш 3, а исход под номером три – выигрыш 2.

Допустим, участницы игры ходят поочередно. Эмили получает право первого хода и решает, инвестировать ли ей в сад. В свою очередь Нина, глядя на выбор Эмили, решает, стоит ли и ей так поступить. И наконец, Талия, оценив выбор Эмили и Нины, делает аналогичный выбор [22] .

22

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

На рис. 3.6 изображено дерево этой игры. Чтобы облегчить ее описание, мы обозначили узлы действия специальными символами. Эмили делает ход в начальном узле a,

а ветви, соответствующие двум имеющимся у нее вариантам выбора («внести вклад» и «не вносить вклад»), ведут к узлам b и c. В каждом из них должна сделать ход Нина и выбрать один из представленных вариантов. Ее выбор приводит к узлам d, e, f и g, в каждом из которых наступает очередь Талии ходить. Имеющиеся у Талии варианты выбора приводят к восьми концевым узлам, где мы показываем выигрыш в таком порядке: (Эмили, Нина, Талия) [23] . Например, если Эмили решает инвестировать в создание сада, Нина нет, а Талия да, то красивый декоративный сад будет разбит и две участницы, внесшие вклад в его создание, получат выигрыш 3 каждая, а участница, которая решила сэкономить, – свой максимальный выигрыш 4. В данном случае список выигрышей выглядит так: (3, 4, 3).

23

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

.

Рис. 3.6. Игра «уличный сад»

Для того чтобы применить к этой игре метод обратных рассуждений, начнем с узлов действия, расположенных непосредственно перед концевыми узлами, а именно с узлов d, e, f и g. Талия делает ход в каждом из этих узлов. В узле d она сталкивается с ситуацией, когда и Эмили, и Нина вносят вклад в создание сада, то есть сад уже наверняка будет красивым, поэтому, выбрав вариант «не вносить вклад», Талия получает свой максимальный выигрыш 4, тогда как в противном случае – следующий по размеру выигрыш 3. Стало быть, предпочтительный для Талии вариант выбора в данном узле – «не вносить вклад». Мы отображаем это путем выделения соответствующей ветви жирной линией и добавления к ней стрелки; любого из этих способов было бы достаточно для иллюстрации выбора Талии. В узле e Эмили выбрала вариант «внести вклад», а Нина – «не вносить», поэтому вклад Талии крайне важен для создания красивого сада. Талия получит выигрыш 3, если выберет «внести вклад», и 2 в результате отказа. Ее предпочтительный вариант выбора в узле e – «внести вклад». Аналогичным образом можно проверить выбор Талии в двух оставшихся узлах.

Теперь давайте вернемся немного назад и проанализируем предыдущий этап – а именно узлы b и c, в которых наступает очередь Нины выбирать. В узле b Эмили решила инвестировать в создание сада, поэтому Нина рассуждает так: «Если я выберу вариант “внести вклад”, это приведет игру в узел d, а там, насколько мне известно, Талия выберет “не вносить вклад”, и мой выигрыш составит 3. (Сад будет красивым, но я понесу убытки.) Если я выберу “не вносить вклад”, игра переместится в узел e, где, как мне известно, Талия выберет “внести вклад”, а мой выигрыш будет 4. (Сад будет красивым, а я сэкономлю на расходах.) Следовательно, я выбираю “не вносить вклад”». Аналогичные рассуждения показывают, что в узле c Нина предпочтет вариант «внести вклад».

И наконец, рассмотрим выбор Эмили в начальном узле a. Она может предвидеть последующий выбор как Нины, так и Талии и знает, что если выберет вариант «внести вклад», то Нина выберет «не вносить вклад», а Талия – «внести вклад». Если две участницы игры инвестируют в создание сада, он будет красивым, но Эмили понесет издержки, а значит, ее выигрыш составит 3. Если Эмили предпочтет «не вносить вклад», то в двух следующих друг за другом узлах будет выбран вариант «внести вклад», и при наличии красивого сада и отсутствии издержек ее выигрыш составит 4. Таким образом, оптимальный выбор Эмили в узле a – «не вносить вклад».

Теперь подвести итоги анализа игры «уличный сад» методом обратных рассуждений не составит труда. Эмили выберет вариант «не вносить вклад», затем Нина – «внести вклад» и наконец Талия – тоже «внести вклад». Такая последовательность выбора образует конкретный путь игры на данном дереве, который проходит по нижней ветви, исходящей из начального узла, а затем по верхним ветвям в каждом из двух идущих друг за другом следующих узлов, с и f. На рис. 3.6 этот путь игры легко отследить как непрерывную последовательность стрелок, пролегающую

от начального до пятого концевого узла, если вести отсчет от верхней части дерева. Выигрыши, которые получат участницы игры, показаны в концевом узле.

Анализ методом обратных рассуждений прост и привлекателен. Мы бы хотели подчеркнуть его некоторые особенности. Во-первых, обратите внимание, что на равновесном пути игры с последовательными ходами отсутствует большинство ветвей и узлов. Однако вычисление лучших действий, которые следовало бы предпринять, если бы игра все же их достигла, – важная часть процесса поиска окончательного равновесия. Выбор на ранних этапах игры ее участницы делают под влиянием своих ожиданий в отношении того, что произойдет, если они выберут действие, отличающееся от оптимального, а также что бы произошло, если бы любая из оставшихся участниц игры предпочла нечто иное, чем то, что является для нее лучшим. Эти ожидания, основанные на прогнозируемых вариантах выбора в узлах, расположенных вне равновесного пути игры (то есть в узлах, которые соответствуют ветвям, отсеченным в процессе анализа методом обратных рассуждений), позволяют участницам игры совершать оптимальные действия в каждом узле. Например, предпочтительный выбор Эмили «не вносить вклад», сделанный в первом узле, обусловлен пониманием того, что если она выберет вариант «внести вклад», то Нина выберет «не вносить вклад», после чего Талия решит «внести вклад»; эта последовательность обеспечит Эмили выигрыш 3 вместо выигрыша 4, который она могла бы получить, указав вариант «не вносить вклад» на первом ходе.

Равновесие обратных рассуждений обеспечивает полное описание всего процесса анализа посредством формулировки оптимальной стратегии для каждого игрока. Мы уже отмечали, что стратегия – это исчерпывающий план действий. Эмили делает первый ход, имея два варианта выбора, а значит, ее стратегия достаточно проста и фактически сводится к одному ходу. Но Нина, которая ходит второй, действует уже в каком-то из двух узлов: в одном – если Эмили выбрала вариант «внести вклад», и в другом – если Эмили предпочла «не вносить вклад». В исчерпывающем плане Нины должны быть указаны действия в каждом из этих случаев. Один такой план, или стратегия, может быть следующим: «Выбрать “внести вклад”, если Эмили выбрала “внести вклад”, и “не вносить вклад”, если Эмили его не вносит». Благодаря анализу методом обратных рассуждений мы знаем, что Нина не выберет эту стратегию, но на данном этапе нам необходимо описать все доступные стратегии, из которых Нина сможет выбирать согласно правилам игры. Мы можем сократить их описание, используя обозначение «В» вместо «внести вклад» и «Н» вместо «не вносить вклад». В результате вышеупомянутую стратегию можно представить так: «В, если Эмили выберет В, а значит, игра перейдет в узел b; Н, если Эмили выберет Н и игра перейдет в узел с», или еще проще: «В в b, Н в c», или даже «ВН», если обстоятельства, при которых выбирается каждое из указанных действий, очевидны или разъяснены ранее. Теперь легко увидеть, что поскольку у Нины по два варианта выбора в каждом из двух узлов, в которых она может действовать, в ее распоряжении находятся четыре плана действий, или стратегии: «В в b, В в c»; «В в b, Н в c»; «Н в b, В в c» и «Н в b, Н в c», или «ВВ», «ВН», «НВ» и «НН». Анализ методом обратных рассуждений, а также стрелки в узлах b и c на рис. 3.6 показывают, что оптимальная стратегия Нины – «НВ».

В случае Талии ситуация усложняется. Когда наступит ее черед, история игры может представлять собой любой из четырех возможных вариантов. Очередь действовать переходит к Талии в одном из четырех узлов дерева: один после выбора Эмили В и Нины В (узел d); второй после В Эмили и Н Нины (узел e); третий после Н Эмили и В Нины (узел f) и четвертый после Н и Эмили, и Нины (узел g). Каждая из стратегий (или исчерпывающих планов действий) Талии должна определять одно из двух действий по каждому из этих четырех сценариев или одно из двух действий в каждом из возможных узлов действия. При наличии четырех узлов, в которых необходимо указать действие, и двух действий, из которых следует выбрать одно в каждом узле, существует 2 x 2 x 2 x 2, или 16, вероятных комбинаций действий. Следовательно, в распоряжении Талии 16 доступных стратегий. Одну из них можно было бы записать так:

«В в d, Н в e, Н в f, В в g», или для краткости «ВННВ»

Здесь мы зафиксировали последовательность четырех сценариев (историй ходов Эмили и Нины) в порядке расположения узлов d, e, f и g. Далее с помощью такой же сокращенной формы записи можно составить полный список всех 16 находящихся в распоряжении Талии стратегий:

ВВВВ, ВВВН, ВВНВ, ВВНН, ВНВВ, ВНВН, ВННВ, ВННН, НВВВ, НВВН, НВНВ, НВНН, ННВВ, ННВН, НННВ, НННН.