Стратегические игры. Доступный учебник по теории игр Диксит Авинаш
Невероятное количество компьютерных и человеко-часов ушло на поиск решения игры в шахматы. С не меньшим упорством исследователи работали и над решением несколько более простой игры — в шашки, и в 2007 году объявили, что оно найдено[28].
Шашки — еще одна игра с двумя участниками, в которую играют на доске восемь на восемь клеток. Каждый игрок имеет по 12 круглых фигур, или шашек, разного цвета (рис. 3.9), и игроки по очереди передвигают их по диагонали, перепрыгивая (и захватывая) шашки противника, когда это возможно. Как и в шахматах, игра заканчивается и игрок А выигрывает, если у игрока Б не остается шашек или ему некуда ходить. Кроме того, партия может завершиться вничью, если оба игрока согласятся, что ни один из них не может победить.
Рис. 3.9. Шашки
Хотя сложность шашек меркнет на фоне шахмат (количество вероятных позиций в шашках приблизительно равно квадратному корню из количества позиций в шахматах), существует 5 1020 возможных позиций, так что о построении дерева игры не может быть и речи. Если исходить из здравого смысла и результатов чемпионатов мира по шашкам за многие годы, то хорошая игра должна приводить к ничьей, но это не было доказано. Однако спустя какое-то время программисту из Канады все же удалось получить такое доказательство — компьютерную программу Chinook, которая способна обеспечить гарантированную ничью.
Chinook появилась в 1989 году, а в 1992-м впервые сразилась с чемпионом мира по шашкам Марионом Тинсли (проиграв со счетом 4:2 при 33 ничьих), а затем еще раз в 1994 году (когда во время серии ничьих у Тинсли пошатнулось здоровье). В период с 1997 по 2001 год работа над программой была приостановлена, поскольку ее создатели ждали усовершенствования компьютерных технологий. И наконец весной 2007 года Chinook продемонстрировала беспроигрышный алгоритм игры в шашки, использующий комбинацию анализа методом обратных рассуждений с конца игры и прямого анализа игры с исходной позиции наряду с эквивалентом функции промежуточной оценки для отслеживания лучших ходов в базе данных, включающей все возможные позиции на доске.
Создатели Chinook называют полную игру в шашки «слабо решенной»; они знают, что могут обеспечить ничью, и у них есть стратегия ее достижения с исходной позиции. Для всех 39 1012 возможных позиций с наличием 10 или менее шашек на доске они описывают игру как «строго решенную». В этом случае они знают, что могут не только сыграть вничью, но и достичь ее из любой позиции, сформировавшейся после того, как на доске останется не более 10 шашек. Этот алгоритм сначала решил эндшпиль с 10 шашками, а затем вернулся к началу игры, чтобы найти те ее пути, на которых оба игрока делают оптимальный выбор. Механизм поиска, включающий комплексную систему оценки каждой промежуточной позиции, неизбежно приводил к тем позициям с 10 шашками, которые гарантировали ничью.
Следовательно, наша надежда на будущее анализа методом обратных рассуждений небеспочвенна. Мы знаем, что в действительно простых играх можем найти равновесие посредством вербальных рассуждений без необходимости рисовать дерево игры в явной форме. В играх среднего уровня сложности процесс вербальных размышлений затрудняется, но можно нарисовать дерево игры и использовать его в ходе анализа методом обратных рассуждений. Иногда при анализе дерева игры умеренной сложности имеет смысл прибегнуть к помощи компьютера. В более сложных играх, таких как шашки и шахматы, мы можем нарисовать только часть дерева игры, поэтому должны применять сочетание двух методов: 1) просчет ходов, строящийся на логике обратных рассуждений; 2) эмпирическая оценка промежуточных позиций на основе опыта. Вычислительные возможности существующих алгоритмов подтверждают тот факт, что даже некоторые игры этой категории поддаются решению при наличии соответствующего времени и ресурсов.
К счастью, большинство стратегических игр, с которыми мы сталкиваемся в области экономики, политики, спорта, бизнеса и в повседневной жизни, гораздо проще по сравнению с шахматами или даже шашками. В них может быть несколько игроков, которые ходят по несколько раз, и даже большое количество игроков и большое количество ходов. Однако у нас есть шанс нарисовать приемлемое дерево для игр, последовательных по своей сути. Логика обратных рассуждений остается в силе; и часто так бывает, что стоит вам освоить этот метод, и вы легко выполняете необходимый логический анализ и решаете игру даже без построения дерева игры в явной форме. Кроме того, именно на этом промежуточном уровне сложности (между простыми примерами, которые мы решили в данной главе, и нерешенными играми вроде шахмат) могут пригодиться такие компьютерные программы, как Gambit; это открывает перспективу применения теории к решению многих игр на практике.
6. Фактические данные, касающиеся метода обратных рассуждений
Насколько хорошо фактические участники игр с последовательными ходами выполняют вычисления в рамках анализа методом обратных рассуждений? Таких систематизированных данных крайне мало, но аудиторные и научно-исследовательские эксперименты с некоторыми играми привели к результатам, на первый взгляд противоречащим погнозам теории. Ряд экспериментов имеют весьма интересные последствия для стратегического анализа игр с последовательными ходами.
Например, в ходе многих экспериментов разыгрывалась состоящая из одного раунда переговорная игра, где двух игроков, А и Б, выбирали из группы студентов или добровольцев. Затем экспериментатор давал им один доллар или другую оговоренную сумму, которую следовало разделить между двумя игроками по следующей схеме: игрок А предлагает, скажем, вариант «75 центов мне и 25 центов игроку Б». Если Б принимает это предложение, то доллар делится именно так, если отклоняет, то никто ничего не получает.
В данном случае анализ методом обратных рассуждений говорит о том, что игроку Б следует принять любую сумму, какой бы маленькой она ни была, поскольку альтернатива еще хуже (то есть 0), и исходя из этого игрок А вообще должен предложить «99 центов мне и 1 цент Б». Однако подобного исхода почти никогда не бывает. Большинство игроков, выступающих в роли игрока А, предлагают более справедливое, близкое к равному разделение суммы. На самом деле 50:50 — самый распространенный вариант. Мало того, большинство участников, будучи в роли игрока Б, отклоняют предложения, оставляющие им менее 25 % от общей суммы, и уходят ни с чем, а некоторые отвергают даже 40 %[29].
Многие специалисты по теории игр не согласны, что эти выводы подрывают теорию, аргументируя свою точку зрения примерно так: «Эти суммы настолько малы, что разум игроков воспринимает происходящее как нечто тривиальное. Игрок Б теряет 25 или 40 центов, что практически равно нулю, но при этом, возможно, испытывает определенное удовлетворение от того, что отказался от столь унизительного предложения. Если бы на кону стояла тысяча долларов и 25 % составляли бы приличную сумму, то любой игрок Б принял бы такое предложение». Но этот аргумент нельзя считать бесспорным. Эксперименты с гораздо более высокими ставками демонстрируют аналогичные результаты. В Индонезии, например, оперировали суммами, не очень большими в долларах, но составлявшими трехмесячный заработок участников экспериментов. И тем не менее их результаты не показали явной склонности игроков А делать предложения о менее равноценном дележе общей суммы, хотя по мере ее увеличения игроки Б были готовы принимать несколько меньшую долю. Аналогичные эксперименты, проведенные в Словацкой Республике, доказали, что серьезное изменение выигрышей не влияет на поведение неопытных игроков[30].
Как правило, у участников подобных экспериментов нет ни базовых знаний в области теории игр, ни специальных вычислительных навыков. Но это чрезвычайно простая игра, и наверняка даже самый неопытный игрок может ее проанализировать посредством обратных рассуждений, а ответы на прямые вопросы, поставленные после эксперимента, обычно говорят о том, что большинство его участников действительно делают это. Такие результаты свидетельствуют не столько о несостоятельности метода обратных рассуждений, сколько об ошибке теоретиков, полагающих, что каждого игрока интересует исключительно собственная прибыль, и не учитывающих моральный аспект вопроса. В большинстве стран общество прививает своим членам обостренное чувство справедливости, которое заставляет игроков Б отклонять любое явно несправедливое предложение. Учитывая это, игроки А предлагают практически равное разделение общей суммы.
Эти выводы подтверждают данные, полученные в рамках изучения новой науки под названием нейроэкономика. Алан Сэнфи и его коллеги сделали томограмму головного мозга игроков в момент принятия решений в ультимативной игре и обнаружили возбуждение активности в области головного мозга, отвечающей за негативные эмоции, в тот момент, когда игроки Б отклоняли «несправедливые» (менее чем 50:50) предложения о дележе общей суммы. Создается впечатление, что глубинные инстинкты и чувство гнева и отвращения причастны к таким отказам. Кроме того, исследователи обнаружили, что «несправедливые» предложения (менее чем 50:50) отклонялись реже, когда игроки Б знали, что их делает компьютер, по сравнению со случаями, когда они исходили от человека[31].
Примечательно, что игроки А демонстрируют склонность к щедрости даже при отсутствии угрозы возмездия. В радикальном варианте игры под названием диктаторская игра, где игрок А решает, как делить общую сумму, а Б вообще лишен выбора, многие игроки А все же отдают вполне приличную долю игрокам Б. Это позволяет предположить, что у игроков есть некое врожденное предпочтение к относительно равноценному распределению общей суммы[32]. Однако в игре в диктатора предложения игроков А заметно менее щедрые, чем в ультимативной игре; это доказывает, что реальный страх возмездия также весьма сильный мотиватор. Кроме того, по всей видимости, немалую роль играет и мнение о нас окружающих. Примечательно, что когда схема эксперимента меняется таким образом, чтобы даже экспериментатор не мог определить, кто предложил (или принял) разделение, готовность делиться заметно снижается.
Еще одна экспериментальная игра со столь же парадоксальными результатами проходит по следующей схеме: выбираются два игрока, А и Б. Экспериментатор кладет на стол монету в 10 центов. Игрок А может ее взять или пропустить ход. Если игрок А берет монету, игра закончена; при этом А получает 10 центов, а Б — ничего. Если игрок А пропускает ход, экспериментатор кладет на стол еще одну монету в 10 центов, и теперь игроку Б предстоит выбирать, взять ли ему обе монеты или пропустить ход. Игроки действуют по очереди, а стопка монет растет до тех пор, пока не достигнет определенной предельной суммы (например, одного доллара), заранее известной обоим игрокам.
Дерево этой игры показано на рис. 3.10. Из-за его внешнего вида игры такого типа часто называют игра «стоножка»[33]. Возможно, вам даже не понадобится строить дерево игры, чтобы проанализировать ее методом обратных рассуждений. Очевидно, что игрок Б возьмет один доллар на последнем этапе, поэтому игроку А следует взять 90 центов на предпоследнем этапе и т. д. Следовательно, игрок А должен взять монету в 10 центов в самом начале и закончить игру.
Рис. 3.10. Игра «стоножка»
Однако во время экспериментов такие игры длятся, как правило, несколько раундов. Примечательно, что благодаря иррациональному поведению игроки как группа получают больше денег, чем в случае, если бы они придерживались логики обратных рассуждений. Иногда более весомых успехов добивается игрок А, а иногда — игрок Б, а порой им даже удается разрешить конфликт или задачу с переговорами. В ходе аудиторного эксперимента, который проводил один из нас (Диксит), одна такая игра дошла до самого конца. Игрок Б забрал свой доллар и совершенно добровольно отдал 50 центов игроку А. Диксит спросил: «Вы сговорились? Вы с Б друзья?» На что игрок А ответил: «Нет, мы даже не были знакомы раньше. Но теперь он мой друг». Мы столкнемся с аналогичными примерами сотрудничества, на первый взгляд противоречащими логике обратных рассуждений, при анализе повторяющихся игр с дилеммой заключенных в главе 10.
Игра «стоножка» указывает на возможную проблему с логикой обратных рассуждений в играх с ненулевой суммой, даже если игроки принимают решения исходя исключительно из денежных соображений. Обратите внимание, что, пропуская ход в первом раунде, игрок А уже показывает, что не опирается на метод обратных рассуждений. Так чего следует ожидать от него игроку Б в третьем раунде? Пропустив ход однажды, игрок А может снова это сделать, а значит, игроку Б было бы целесообразно пропустить ход во втором раунде. В конечном счете кто-то заберет всю стопку монет, но исходное отклонение от логики обратных рассуждений не позволяет предсказать, когда именно это произойдет. А поскольку стопка монет продолжает расти, если я увижу, что вы отклоняетесь от логики обратных рассуждений, у меня также может возникнуть желание отклониться от нее как минимум на какое-то время. Игрок может сознательно пропустить ход в одном из начальных раундов игры, чтобы сигнализировать о готовности пропускать ходы в будущих раундах. Такая проблема не возникает в играх с нулевой суммой, в которых отсутствует стимул к сотрудничеству посредством ожидания.
В поддержку этого наблюдения Стивен Левитт, Джон Лист и Салли Сэдофф провели эксперименты с участием шахматистов мирового класса и обнаружили, что поведение игроков в большей степени соответствует логике обратных рассуждений в играх с последовательными ходами с нулевой суммой, чем в игре «стоножка» с ненулевой суммой. Их игра «стоножка» состоит из шести узлов, а общая сумма выигрыша растет довольно резко от раунда к раунду[34]. Несмотря на значительные выгоды для игроков, способных пропускать ходы, передавая их друг другу, согласно равновесию обратных рассуждений в каждом узле необходимо выбирать вариант «взять». Вопреки теории всего 4 процента игроков сыграли «взять» в первом узле, практически не поддержав равновесие обратных рассуждений даже в этой простой игре на шесть ходов. (Доля игроков, выбравших вариант «взять», увеличивалась в ходе игры[35].)
Напротив, в игре с последовательными ходами с нулевой суммой, в которой равновесие обратных рассуждений достигается за 20 ходов (вам предстоит решить эту игру в упражнении S7), шахматисты играли в точном соответствии с ним в 10 раз чаще, чем в игре «стоножка», состоящей из шести ходов[36].
Левитт и его соавторы также экспериментировали с похожей, но более сложной игрой с нулевой суммой (одну из версий которой вам предлагается решить в упражнении U5), где шахматисты достигали полного равновесия обратных рассуждений только в 10 процентах случаев (в 20 процентах, когда в игре участвовали гроссмейстеры с самым высоким рейтингом), хотя на последних нескольких ходах согласование ходов с методом обратных рассуждений составляло почти 100 процентов. Поскольку шахматисты мирового класса проводят десятки тысяч часов в попытках выиграть шахматные партии посредством обратных рассуждений, эти результаты указывают на то, что даже в высшей степени опытные игроки зачастую не могут мгновенно включиться в новую игру: им необходимо накопить в ней немного опыта, прежде чем они смогут определить оптимальную стратегию. Изучение теории игр поможет вам без труда находить глубинное сходство между разными на первый взгляд ситуациями, а значит, и быстрее вырабатывать эффективные стратегии в любых новых играх, с которыми вы можете столкнуться.
Исходя из приведенных примеров можно сделать вывод, что кажущееся нарушение стратегической логики во многих случаях объясняется заботой людей не только о денежном выигрыше, но и о моральной стороне вопроса, в данном случае о справедливости. Однако подобное объяснение подходит не для всех наблюдаемых методов ведения игры, противоречащих принципу обратных рассуждений. Люди действительно не умеют заглядывать достаточно далеко вперед и делать надлежащие выводы из таких попыток. Скажем, когда эмитенты кредитных карт предлагают выгодные исходные процентные ставки или полное отсутствие комиссионных за первый год, многие попадаются на эту удочку, не осознавая, что впоследствии им, возможно, придется выложить гораздо больше. Следовательно, теоретико-игровой анализ метода обратных рассуждений и равновесий, полученных посредством этого метода, выполняет рекомендательную функцию в той же степени, что и описательную. Люди, овладевшие теорией обратных рассуждений, склонны принимать более эффективные решения и обычно получают более высокие выигрыши, что бы они ни включали в их расчеты. А специалисты по теории игр могут использовать свои знания, чтобы давать ценные советы тем, кто попал в сложные стратегические ситуации и не имеет навыков определения лучшей стратегии.
7. Стратегии в реалити-шоу Survivor
Примеры, приведенные в предыдущих разделах, намеренно подобраны так, чтобы проиллюстрировать и объяснить базовые концепции, такие как узлы, ветви, ходы и стратегии, а также метод обратных рассуждений. Теперь мы покажем, как их все применить, рассмотрев ситуацию из реальной жизни (или по крайней мере из жизни в реалити-шоу).
Летом 2000 года телеканал CBS показал первое реалити-шоу Survivor[37], которое моментально обрело популярность и способствовало созданию нового телевизионного жанра — «реалити-ТВ». Если опустить множество сложных деталей и некоторые более ранние этапы шоу, не имеющие отношения к нашей цели, то его концепция состояла в следующем. Группу участников под названием «племя» отправляли на необитаемый остров, где они должны были сами добывать себе пищу и искать крышу над головой. Каждые три дня члены племени путем голосования исключали из своих рядов одного из товарищей. Человек, набравший наибольшее количество голосов против, становился жертвой дня. Однако перед каждым собранием совета племени продержавшиеся до этого момента состязались в игре, требовавшей наличия физических или психических навыков, придуманной продюсерами специально для данного случая. Ее победитель получал иммунитет от предстоящего голосования. Кроме того, никто не имел права голосовать против себя. И наконец, когда оставалось всего два участника шоу, семь выбывших ранее членов племени возвращались в игру в качестве жюри, чтобы выбрать одного из них как ее победителя и обладателя приза в миллион долларов.
Перед каждым участником состязания стояли следующие стратегические задачи: 1) добиться того, чтобы остальные члены племени воспринимали его как человека, вносящего ценный вклад в поиски пищи и выполнение других задач по выживанию, но при этом не показаться сильным конкурентом, а значит, кандидатом на вылет; 2) сформировать союзы с другими соплеменниками, чтобы обеспечить блоки голосов и защитить себя от исключения из племени; 3) предать союзников, когда в игре останется слишком мало участников и каждому придется против кого-то голосовать; 4) сделать это без серьезной потери популярности среди других игроков, которые в конечном счете получат право голоса в жюри.
Мы рассмотрим ситуацию, когда в реалити-шоу осталось всего три участника: Руди, Келли и Рик. Самый старший, Руди, был честным, прямолинейным человеком, который пользовался большим авторитетом среди ранее выбывших участников шоу. По всеобщему мнению, если бы Руди был одним из двух последних игроков, то именно он стал бы победителем в реалити-шоу. Следовательно, и Келли, и Рик были заинтересованы в том, чтобы на последнем голосовании противостоять друг другу, а не Руди. Однако ни один из них не хотел играть решающую роль в голосовании против Руди, потому что, когда в игре остается три участника, голос обладателя иммунитета фактически становится решающим, поскольку два других игрока голосуют друг против друга. Таким образом, члены жюри точно бы знали, кто ответственен за изгнание Руди, и, учитывая его популярность, неодобрительно отнеслись бы к голосованию против него. Человек, сделавший это, снизил бы свои шансы на последнем голосовании. Это было особенно актуально для Рика, так как всем было известно, что он заключил с Руди союз.
Испытание на получение иммунитета было проверкой на выносливость: каждый участник игры должен был стоять на неудобной опоре, наклонившись так, чтобы прикасаться одной рукой к установленному на центральном столбе тотему под названием «идол иммунитета». Игрок, который отрывал от него руку хотя бы на мгновение, проигрывал испытание; победителем становился тот, кто смог продержаться дольше всех.
Через полтора часа после начала испытания Рик понял, что его лучшая стратегия — намеренно его проиграть. Тогда, если Руди получит иммунитет, он сохранит союз и поддержит Рика — Руди был известен как хозяин своего слова. В таком случае Рик проиграл бы в итоге Руди, но для него это было бы ничуть не хуже, чем если бы он выиграл состязание и поддержал Руди. Если иммунитет получит Келли (а это куда более вероятно), то она будет заинтересована голосовать против Руди: у нее есть хотя бы какие-то шансы в борьбе против Рика, но никаких — в противостоянии с Руди. При таком сценарии шансы Рика на победу становились весьма неплохими. С другой стороны, если бы сам Рик получил иммунитет, а затем проголосовал против Руди, его шансы в борьбе против Келли снизились бы в связи с голосованием за изгнание Руди.
В итоге Рик умышленно сошел с опоры и впоследствии совершенно четко объяснил причины своего решения перед камерой. Его расчет оказался верным. Келли выиграла испытание и проголосовала против Руди. А в решающем голосовании жюри с перевесом в один голос отдало звание победителя Рику.
Фактически размышления Рика представляли собой анализ дерева игры методом обратных рассуждений. Он выполнил его интуитивно, без построения дерева, стоя в неудобной позе, ухватившись за идола иммунитета. Но ему понадобилось полтора часа, чтобы прийти к такому выводу.
Это дерево игры изображено на рис. 3.11. Очевидно, что оно гораздо более сложное по сравнению с деревьями, представленными в предыдущих разделах. В нем больше ветвей и ходов, кроме того, есть неопределенные исходы, а вероятность победы или поражения в различных альтернативных ситуациях необходимо оценивать, поскольку точное значение неизвестно. Однако вы увидите, как в процессе анализа дерева игры мы будем делать обоснованные предположения относительно шансов на победу или поражение.
Рис. 3.11. Дерево игры в иммунитет в реалити-шоу Survivor
В начальном узле Рик решает, стоит ли продолжать участвовать в испытании на получение иммунитета. В любом случае возможного победителя с уверенностью предсказать нельзя, что отображено на дереве игры и позволяет сделать выбор «природе», как в ситуации с подбрасыванием монеты на рис. 3.1. Если Рик продолжит игру, «природа» выберет победителя из трех участников состязания. Поскольку фактические значения вероятности нам неизвестны, мы возьмем конкретные значения для наглядности и укажем важные исходные предположения. Первое состоит в том, что Келли обладает высокой выносливостью, а Руди, будучи самым старшим, вряд ли победит. Поэтому мы присваиваем следующие значения вероятности победы в случае, если Рик решит продолжить игру: Келли — 0,5 (50 %), Рик — 0,45 и Руди — всего 0,05. Если Рик сойдет с дистанции, «природа» случайным образом выберет победителя из двух оставшихся игроков. Здесь мы основываемся на предположении, что Келли выиграет с вероятностью 0,9, а Руди — 0,1.
Остальные ветви дерева исходят из узлов, соответствующих трем возможным победителям испытания. Если выиграет Руди, он, как и обещал, поддержит Рика, и жюри проголосует за Рика[38]. Если иммунитет получит Рик, ему придется решать, кого поддержать — Келли или Руди. Если Руди, то жюри за него и проголосует. Если Келли, то неизвестно, кого предпочтет жюри. Мы предполагаем, что Рик, выступив против Руди, утратит расположение некоторых членов жюри и, несмотря на большую благосклонность со стороны жюри по сравнению с Келли, получит голоса его членов с вероятностью всего 0,4. Точно так же, если иммунитет достанется Келли, она может поддержать либо Руди и потерять голоса членов жюри, либо Рика. Если Келли выберет Рика, его вероятность получить голоса членов жюри повысится — 0,6, поскольку в этом случае жюри ему больше симпатизирует и он не голосовал против Руди.
Как насчет фактических выигрышей игроков? Мы можем с уверенностью предположить, что и Рик, и Келли стремятся максимизировать вероятность того, что в конечном счете кто-то из них выиграет 1 миллион долларов. Руди тоже хочет получить этот приз, но для него крайне важно сдержать данное Рику слово. С учетом этих предпочтений игроков Рик может выполнить анализ дерева игры методом обратных рассуждений, чтобы определить свой первоначальный выбор.
Рик знает, что, выиграв испытание на получение иммунитета (самый верхний путь после его первого хода и хода «природы»), он должен поддержать Келли, чтобы обеспечить себе победу с вероятностью 40 процентов; поддержка Руди на данном этапе означала бы для него нулевую вероятность победы. Рик может также вычислить, что, если Келли получит иммунитет (что происходит по одному разу в верхней и нижней половине дерева), она решит его поддержать по тем же причинам, и тогда вероятность его победы составит 0,6.
Каковы шансы Рика, рассчитанные в начальном узле? Если Рик выбирает в нем вариант «прекратить», у него остается только один путь к победе: Келли получает иммунитет (вероятность 0,9), после этого поддерживает Рика (вероятность 1), и жюри голосует за него (вероятность 0,6). Поскольку победа Рика зависит от совокупности этих трех событий, общая вероятность его победы представляет собой произведение трех вероятностей: 0,9 1 0,6 = 0,54[39]. Если Рик в начальном узле выбирает вариант «продолжить», это открывает ему два пути к победе. Во-первых, он победит, если выиграет испытание на получение иммунитета (вероятность 0,45), после чего устранит Руди (вероятность 1) и все же получит голоса жюри в противостоянии с Келли (вероятность 0,4); общая вероятность победы при таком развитии событий составляет 0,45 0,4 = 0,18. Во-вторых, он станет победителем, если Келли выиграет испытание на получение иммунитета (вероятность 0,5), затем избавится от Руди (вероятность 1), а Рику достанутся голоса жюри (вероятность 0,6); в этом случае общая вероятность составляет 0,5 0,6 = 0,3. Общая вероятность победы Рика при выборе варианта «продолжить» представляет собой сумму вероятностей двух путей к победе, а именно 0,18 + 0,3 = 0,48.
Теперь Рик может сравнить вероятность выигрыша миллиона долларов при выборе варианта «прекратить» (0,54) с вероятностью победы в случае выбора варианта «продолжить» (0,48). С учетом предполагаемых значений различных вероятностей на дереве игры у Рика больше шансов на победу, если он откажется от участия в испытании на получение иммунитета. Следовательно, «прекратить» — его оптимальная стратегия. Хотя этот результат основан на присвоении определенных предполагаемых значений вероятностям тех или иных событий, он остается для Рика лучшим при выполнении следующих условий: 1) Келли с большой вероятностью выиграет испытание на получение иммунитета, если Рик откажется от дальнейшего участия в нем; 2) победа Рика в последнем голосовании жюри более вероятна в случае, если Келли, а не Рик, проголосует против Руди[40].
Этот пример служит нескольким целям. Главное — он показывает, как использование анализа методом обратных рассуждений позволяет решить даже сложное дерево игры со значительной внешней неопределенностью и отсутствием информации о точных значениях вероятностей. Мы надеемся, что это придаст вам уверенности касательно применения данного метода, а также научит превращать несколько расплывчатое вербальное описание в более точную логическую аргументацию. Вы можете возразить, что Рик выполнил такой анализ без построения дерева игры. Но знание системы или общей модели существенно упрощает эту задачу даже в новых незнакомых обстоятельствах. Следовательно, приобретение системных навыков, несомненно, заслуживает потраченных усилий.
Вторая цель данного примера — проиллюстрировать на первый взгляд парадоксальную стратегию «проиграть, чтобы выиграть», еще одно применение которой можно найти в спортивных соревнованиях, проходящих в два этапа, таких как чемпионат мира по футболу. Первый этап проводится в рамках лиги в нескольких группах по четыре команды в каждой. Две лучшие команды в каждой группе участвуют во втором туре чемпионата, где каждая команда встречается с другими командами согласно заранее оговоренной схеме. Скажем, команда, занявшая первое место в группе А, играет с командой, занявшей второе место в группе B, и т. д. В такой ситуации выигрышной стратегиейдля команды может стать поражение в одном из матчей первого этапа, если оно позволит ей занять второе место в группе, что обеспечит возможность сыграть следующий матч против команды, вероятность победить которую гораздо выше, чем в случае, если бы команда заняла первое место на первом этапе.
Резюме
Участникам игр с последовательными ходами необходимо проанализировать последствия своих текущих ходов, прежде чем выбирать действия. Как правило, анализ чистых игр с последовательными ходами требует построения дерева игры. Такое дерево состоит из узлов и ветвей, отображающих все вероятные действия каждого игрока при каждой возможности сделать ход, а также выигрыши для всех предполагаемых исходов игры. Стратегия каждого игрока представляет собой исчерпывающий план, описывающий его действия в каждом узле принятия решений в зависимости от всех возможных комбинаций действий, предпринятых другими игроками в предыдущих узлах. В играх с последовательными ходами используется концепция равновесия обратных рассуждений, в соответствии с которой игроки определяют свои равновесные стратегии посредством прогнозного анализа последующих узлов и выполненных в них возможных действий, а также путем применения этих прогнозов для вычисления лучшего текущего действия. Этот процесс известен как «обратные рассуждения» или «обратная индукция».
Ряд типов игр предоставляет игрокам различные преимущества, такие, например, как преимущество первого хода. Наличие в игре большого количества участников или ходов приводит к росту дерева игры с последовательными ходами, но не меняет процесса ее решения. Иногда построение полного дерева игры может потребовать больше места или времени, чем это возможно на практике. Во многих случаях такие игры решаются путем простых логических размышлений или посредством определения стратегических сходных элементов различных действий, что позволяет уменьшить размер дерева игры.
При решении более крупных игр вербальные размышления могут привести к равновесию обратных рассуждений, если игра достаточно простая или ее полное дерево поддается построению и анализу. Если игра сложная, вербальные размышления слишком трудны, а полное дерево игры огромно, можно прибегнуть к помощи компьютерной программы. Игру в шашки удалось решить посредством такой программы, хотя полное решение игры в шахматы еще предположительно долго будет оставаться за пределами возможностей компьютеров. В реальных шахматных баталиях в определении ходов игроков присутствуют как элементы искусства (выявление закономерностей и возможностей в зависимости от рисков), так и науки (упреждающее вычисление вероятных исходов игры, вытекающее из результатов определенных ходов).
Проверка теории игр с последовательными ходами на первый взгляд подтверждает тот факт, что реальные игры демонстрируют иррациональность игроков или неспособность теории адекватно предсказывать их поведение. Встречный аргумент подчеркивает сложность фактических предпочтений в отношении различных возможных исходов игры, а также пользу стратегической теории для определения оптимальных действий в случаях, когда фактические предпочтения известны.
Ключевые термины
Ветвь
Дерево игры
Дерево решений
Концевой узел
Корень (дерева)
Метод обратных рассуждений
Начальный узел
Обратная индукция
Отсечение (ветвей)
Преимущество второго хода
Преимущество первого хода
Путь игры
Равновесие обратных рассуждений
Равновесный путь игры
Узел
Узел действия
Узел принятия решений
Функция промежуточной оценки
Ход
Экстенсивная форма
Упражнения с решениями
S1. Предположим, два игрока, Гензель и Гретель, участвуют в игре с последовательными ходами. Гензель ходит первым, Гретель — второй, причем каждый ходит только раз.
a) Нарисуйте дерево игры, в которой у Гензеля есть два возможных действия («вверх» или «вниз») в каждом узле, а у Гретель — три («вверх», «посредине» или «вниз»). Сколько узлов каждого типа (узлов принятия решений и концевых узлов) присутствует в дереве этой игры?
b) Нарисуйте дерево для игры, в которой у Гензеля и Гретель по три возможных действия («сидеть», стоять» и «прыгать») в каждом узле. Сколько узлов двух типов присутствует в дереве такой игры?
c) Нарисуйте дерево для игры, в которой у Гензеля четыре возможных действия («север», «юг», «восток», «запад») в каждом узле, а у Гретель — два («стоять» или «идти»). Сколько узлов двух типов присутствует в дереве такой игры?
S2. Определите, сколько чистых стратегий (исчерпывающих планов действий) находится в распоряжении каждого игрока в следующих играх. Перечислите все чистые стратегии каждого игрока.
S3. Для каждой из игр, представленных в упражнении S2, вычислите исход, полученный посредством равновесия обратных рассуждений, а также полную равновесную стратегию каждого игрока.
S4. Рассмотрим соперничество между Airbus и Boeing в сфере разработки нового коммерческого реактивного самолета. Предположим, что Boeing лидирует в этом процессе, а в Airbus размышляют, стоит ли вступать в конкурентную борьбу. В случае отказа Airbus получит нулевую прибыль, тогда как Boeing станет монополистом и заработает 1 миллиард долларов. Если Airbus решит вступить в борьбу и создать конкурентоспособный самолет, то Boeing придется решать, уладить ли разногласия с Airbus мирным путем или развязать ценовую войну. Мирная конкуренция обеспечит каждой компании прибыль в 300 миллионов долларов, а ценовая война приведет к потере каждой из них 100 миллионов долларов, поскольку цены на самолеты настолько сильно упадут, что ни одна из них не сможет возместить затрат на разработку самолета.
Нарисуйте дерево этой игры. Найдите равновесия обратных рассуждений и опишите равновесные стратегии компаний.
S5. Рассмотрим игру, в которой два игрока, Фред и Барни, по очереди извлекают спички из кучки. Изначально там находится 21 спичка, и Фред ходит первым. На каждом ходе каждый игрок может убрать одну, две, три или четыре спички. Побеждает тот, кто забрал последнюю спичку.
a) Предположим, осталось шесть спичек и пришла очередь Барни ходить. Какой ход он должен сделать, чтобы обеспечить себе победу? Объясните логику своих рассуждений.
b) Допустим, осталось 12 спичек и настала очередь Барни ходить. Какой ход он должен сделать, чтобы обеспечить себе победу? (Совет: используйте свой ответ в пункте a и примените метод обратных рассуждений.)
c) Теперь начните с исходной точки игры. Если оба игрока выберут оптимальный способ ее ведения, то кто из них победит?
d) Какие оптимальные стратегии (исчерпывающие планы действий) есть в распоряжении каждого игрока?
S6. Проанализируем игру из предыдущего упражнения. Предположим, игроки достигли того момента, когда следующим ходить должен Фред, а спичек осталось всего пять.
a) Нарисуйте дерево этой игры, начиная с пяти спичек.
b) Найдите для нее равновесие обратных рассуждений, начиная с пяти спичек.
c) Можно ли сказать, что в этой игре с пятью спичками существует преимущество первого или второго хода?
d) Объясните, почему вы нашли более одного равновесия обратных рассуждений. Как ваш ответ связан с оптимальными стратегиями, которые вы определили в пункте с предыдущего упражнения?
S7. Элрой и Джуди играют в игру, которую Элрой называет «гонка до 100». Элрой ходит первым, и игроки по очереди выбирают числа от одного до девяти, на каждом ходе прибавляя новое число к промежуточной сумме. Победителем становится тот, кто увеличит промежуточную сумму ровно до 100.
a) Если оба игрока ведут игру оптимальным способом, то кто из них выиграет? Есть ли преимущество первого хода в этой игре? Объясните логику своих рассуждений.
b) Каковы оптимальные стратегии (исчерпывающие планы действий) для каждого игрока?
S8. В римском Колизее только что бросили раба на съедение львам. Три льва посажены на цепь в ряд, причем льву 1 до раба ближе всего. Длина цепи каждого льва такова, что он может дотянуться лишь до двух находящихся рядом с ним игроков.
Игра проходит следующим образом. Сначала лев 1 решает, съесть ли ему раба. Если он съедает, тогда лев 2 решает, съесть ли ему льва 1 (который стал слишком тяжелым, чтобы защищаться). Если лев 1 не съедает раба, тогда у льва 2 не остается выбора: бесполезно пытаться съесть льва 1, поскольку в драке погибнут они оба. Точно так же, если лев 2 съедает льва 1, то лев 3 решает, съесть ли ему льва 2.
Предпочтения каждого льва вполне естественны: лучший исход игры (4) — кого-то съесть и остаться в живых; следующий приемлемый исход (3) — выжить, но остаться голодным; следующий исход (2) — съесть кого-то и быть съеденным; худший исход (1) — остаться голодным и быть съеденным.
a) Нарисуйте дерево этой игры с выигрышами для трех участников.
b) Какое равновесие обратных рассуждений имеет место в этой игре? Обязательно опишите стратегии, а не только выигрыши.
c) Есть ли в этой игре преимущество первого хода? Объясните, почему есть или почему нет.
d) Сколько полных стратегий у каждого льва? Перечислите их.
S9. Три крупных универмага (Big Giant, Titan и Frieda’s) планируют открыть филиал в одном из двух новых торговых центров в районе Бостона. Торговый центр Urban Mall не очень большой и может вместить максимум два универмага в качестве «якорей», но зато он расположен рядом с крупным богатым населенным пунктом. Торговый центр Rural Mall находится дальше, в сельской сравнительно бедной местности и может вместить три якорных магазина. Ни один из трех универмагов не хочет открывать филиалы в обоих торговых центрах, потому что их сегменты покупателей частично пересекаются, а значит, размещение филиалов в обоих торговых центрах будет означать конкуренцию с самим собой. Каждый универмаг склонен работать в торговом центре вместе с одним или несколькими универмагами, а не в одиночку, поскольку такой торговый центр привлекает намного больше покупателей, что увеличивает прибыль каждого магазина. Кроме того, каждый универмаг предпочитает Urban Mall из-за более богатого контингента покупателей. Каждый универмаг должен выбрать между попыткой получить торговую площадь в Urban Mall (зная, что в случае неудачи можно попробовать побороться за место в Rural Mall) и ее получением в Rural Mall сразу же (даже не пробуя попасть в Urban Mall).
В данном случае универмаги так ранжируют пять возможных исходов этой игры: 5 (лучший исход) — в торговом центре Urban Mall вместе с другим универмагом; 4 — в торговом центре Rural Mall вместе с еще одним или двумя универмагами; 3 — один в Urban Mall; 2 — один в Rural Mall; 1 (худший исход) — один в Rural Mall после неудачной борьбы за место в Urban Mall, тогда как другие магазины уже получили лучшие якорные места в Urban Mall.
Поскольку в этих трех магазинах различные системы управления, они с разной скоростью готовят необходимые документы для получения торговой площади в новом торговом центре. В Frieda’s с этим справляются быстрее всех, затем следует Big Giant и наконец Titan, в котором процесс подготовки плана размещения филиала наименее эффективен. После подачи ими заявок на предоставление торговой площади торговый центр решает, какие универмаги выбрать. Учитывая узнаваемость названий Big Giant и Titan среди потенциальных покупателей, торговый центр выберет либо одного из них, либо обоих, прежде чем рассматривать запрос Frieda’s. Следовательно, Frieda’s не получит одну из торговых площадей в Urban Mall, если все три универмага подадут на них заявки; так будет даже в случае, если Frieda’s первым сделает свой ход.
a) Нарисуйте дерево этой игры с размещением универмагов в торговом центре.
b) Проиллюстрируйте процесс отсечения ветвей на дереве в ходе обратных рассуждений и используйте усеченное дерево для поиска равновесия обратных рассуждений. Опишите это равновесие с помощью (полных) стратегий, применяемых всеми универмагами. Какими окажутся выигрыши каждого универмага в случае исхода, полученного в результате равновесия обратных рассуждений?
S10 (дополнительное упражнение). Рассмотрим следующую ультимативную игру с переговорами, которая изучалась в ходе лабораторных экспериментов. Игрок, делающий предложение, ходит первым и предлагает разделить сумму в 10 долларов между собой и вторым игроком. Принцип дележа может быть любым. Например, игрок может оставить себе все 10 долларов, или взять себе 9 долларов и отдать 1 доллар оппоненту, или 8 долларов себе и 2 доллара другому игроку и т. д. (Обратите внимание, что в этом случае у предлагающего игрока одиннадцать возможных вариантов выбора.) Второй игрок, получив предложение о разделении общей суммы, может либо принять, либо отвергнуть его. Если он его примет, оба игрока получат предложенную сумму. Если отвергнет, оба не получат ничего.
a) Постройте дерево этой игры.
b) Сколько полных стратегий находится в распоряжении каждого игрока?
c) В чем состоит равновесие обратных рассуждений в этой игре при условии, что игроков интересует исключительно денежный выигрыш?
d) Предположим, второй игрок, Рейчел, примет любое предложение в 3 (или больше) доллара и отклонит любое предложение в 2 (или меньше) доллара. Допустим, предлагающий игрок, Пит, знает о стратегии Рейчел и хочет получить максимальный денежный выигрыш. Какую стратегию он применит?
e) Истинный выигрыш Рейчел (ее «полезность») может не совпадать с денежным выигрышем. Какие еще аспекты игры могут представлять для нее интерес? С учетом вашего ответа составьте набор выигрышей Рейчел, который бы сделал ее стратегию оптимальной.
f) В ходе лабораторных экспериментов игроки, как правило, не придерживаются равновесия обратных рассуждений. Игроки, делающие предложение, обычно предлагают соперникам сумму от 2 до 5 долларов. А те часто отклоняют предложения 3, 2 и особенно 1 доллар. Объясните, почему, по вашему мнению, происходит именно так.
Упражнения без решений
U1. «В игре с последовательными ходами игрок, делающий ход первым, непременно выиграет». Это утверждение истинно или ложно? Обоснуйте свой ответ посредством нескольких кратких предложений и приведите пример, иллюстрирующий его.
U2. Сколько стратегий (исчерпывающих планов действий) в каждой из представленных ниже игр имеется в распоряжении каждого игрока? Перечислите все чистые стратегии каждого игрока.
U3. Определите для каждой из игр, представленных в упражнении U2, исход, полученный посредством равновесия обратных рассуждений, и полную равновесную стратегию каждого игрока.
U4. В Вашингтоне проходят дебаты по предложениям А и Б. Конгресс предпочитает предложение А, тогда как президент — предложение Б. Эти предложения не взаимоисключающие: оба могут стать законами или быть отклонены. Таким образом, существует четыре возможных исхода, имеющих следующий рейтинг (более высокий показатель означает более предпочтительный исход).
a) Ходы в этой игре выполняются по следующей схеме. Сначала Конгресс решает, принимать ли законопроект и должен ли он включать в себя предложение А, или Б, или оба. Затем президент решает, подписать ли законопроект или наложить на него вето. У Конгресса нет достаточного количества голосов для преодоления вето. Нарисуйте дерево этой игры и найдите равновесие обратных рассуждений.
b) Предположим, правила игры изменились: президент получает право постатейного вето. Таким образом, если Конгресс примет законопроект, содержащий оба предложения, президент может не только выбирать, подписать его или наложить вето, но и накладывать вето лишь на одно из предложений. Постройте новое дерево игры и найдите равновесие обратных рассуждений.
c) Объясните на интуитивном уровне, в чем разница между этими двумя равновесиями.
U5. Два игрока, Эми и Бет, играют в игру, в которой разыгрывается банка с сотней монет номиналом 1 цент. Игроки делают ходы по очереди; Эми ходит первой. Каждый раз, когда наступает очередь одной из участниц ходить, она берет из банки от 1 до 10 центов. Побеждает тот, после чьего хода банка опустеет.
a) Если игроки ведут игру оптимальным способом, то кто из них выиграет? Есть ли в этой игре преимущество первого хода? Объясните логику своих рассуждений.
b) Какие оптимальные стратегии (исчерпывающие планы действий) имеются в распоряжении каждого игрока?
U6. Рассмотрим несколько измененный вариант игры, представленной в упражнении U5. Теперь игрок, опустошивший банку, проигрывает.
a) Присутствует ли преимущество первого хода в этой игре?
b) Какие оптимальные стратегии есть в распоряжении каждого игрока?
U7. Кермит и Фоззи играют в игру с двумя банками, в каждой из которых находится по 100 одноцентовых монет. Игроки делают ходы по очереди; Кермит ходит первым. Всякий раз, когда наступает очередь игрока ходить, он берет из одной из банок от 1 до 10 центов. Побеждает тот, после чьего хода обе банки опустеют. (Обратите внимание, что, когда игрок достает оставшиеся монеты из второй банки, первая банка уже должна быть пустой в результате предыдущего хода кого-то из игроков.)
a) В этой игре имеет место преимущество первого или второго хода? Объясните, кто из игроков может обеспечить себе победу и каким образом. (Совет: упростите игру, начав с меньшего количества монет в каждой банке, и попытайтесь понять, применимы ли сделанные выводы в реальной игре.)
b) Какие оптимальные стратегии есть в распоряжении каждого игрока? (Совет: сначала проанализируйте исходную ситуацию, в которой в обеих банках одинаковое количество монет, затем когда их количество от 1 до 10 центов и наконец когда число монет свыше 10 центов.)
U8. Измените упражнение S8 таким образом, чтобы в нем было четыре льва.
a) Постройте дерево игры с выигрышами для этих четырех участников.
b) Какое равновесие обратных рассуждений имеет в ней место? Обязательно опишите стратегии, а не только выигрыши.
c) Дополнительный лев — это хорошо или плохо для раба? Обоснуйте свой ответ.
U9. Для того чтобы предоставить маме один день отдыха, отец планирует устроить своим детям, Барту и Кэсси, воскресную экскурсию. Барт предпочитает поход в парк развлечений (Р), а Кэсси — в музей науки (Н). Каждый ребенок получит 3 единицы полезности за более предпочтительное занятие и только 2 единицы — за менее предпочтительное. Отец — 2 единицы полезности за любое из занятий.
Чтобы определиться с планами на воскресенье, отец намерен сначала спросить Барта о его предпочтениях, а затем Кэсси, после того как она узнает, что выбрал Барт. Каждый ребенок может выбрать либо парк развлечений (Р), либо музей науки (Н). Если оба остановятся на одном и том же, то именно туда все и пойдут. Если возникнут разногласия, тогда отец примет окончательное решение. У него как у отца есть дополнительный вариант действий: он может предложить парк развлечений, музей науки или поход в горы, причем за поход получит 3 единицы полезности, а Барт и Кэсси по 1.
Поскольку отец хочет, чтобы его дети не конфликтовали, он получит 2 дополнительные единицы полезности, если дети выберут одно и то же занятие (не имеет значения, какое именно).
a) Постройте дерево с выигрышами для этой игры с тремя участниками.
b) Какое равновесие обратных рассуждений имеет в ней место? Обязательно опишите стратегии, а не только выигрыши.
c) Сколько разных полных стратегий находится в распоряжении Барта? Обоснуйте свой ответ.
d) Сколько разных полных стратегий у Кэсси? Обоснуйте ответ.
U10 (дополнительное, более трудное упражнение). Рассмотрим дерево игры Survivor, представленное на рис. 3.11. Мы могли не угадать точные значения, которые Рик присвоил вероятностям различных исходов, поэтому давайте обобщим это дерево, проанализировав другие возможные значения. В частности, предположим, что вероятность победы в испытании на получение иммунитета в случае, если Рик выберет вариант «продолжить», составляет x для Рика, y для Келли и 1 — x — y для Руди; точно так же вероятность победы в случае отказа Рика от дальнейшей борьбы равна z для Келли и 1 — z для Руди. Далее допустим, что шанс Рика на то, что его выберет жюри, составляет p, если он выиграет испытание на получение иммунитета и проголосует за изгнание Руди с острова, и q, если Келли выиграет испытание и проголосует за изгнание Руди с острова. Предположим также, что, если Руди выиграет испытание на получение иммунитета, он поддержит Рика с вероятностью 1 и станет победителем в игре с вероятностью 1, если войдет в число двух финалистов. Обратите внимание, что в примере, отображенном на рис. 3.11, были такие значения: x = 0,45, y = 0,5, z = 0,9, р = 0,4 и q = 0,6. (В общем случае переменные p и q необязательно должны в сумме составлять 1, хотя именно так получилось на рис. 3.11.)
a) Найдите алгебраическую формулу, выраженную через x, y, z, p, q, для определения вероятности того, что Рик выиграет миллион долларов, если выберет вариант «продолжить». (Обратите внимание: формула может включать в себя не все переменные.)
b) Найдите аналогичную алгебраическую формулу для определения вероятности того, что Рик выиграет миллион долларов, если выберет вариант «прекратить». (Опять же, формула может не включать в себя все переменные.)
c) Используйте эти результаты для поиска алгебраического неравенства, указывающего, при каких обстоятельствах Рику следует выбрать вариант «прекратить».
d) Предположим, значения всех переменных те же, что и на рис. 3.11, кроме z. Насколько высоким или низким может быть значение z, чтобы Рик по-прежнему предпочел вариант «прекратить»? Объясните на интуитивном уровне, почему при некоторых значениях z Рику лучше выбрать вариант «продолжить».
e) Допустим, значения всех переменных те же, что и на рис. 3.11, за исключением p и q. Предположим также, что, поскольку жюри с большей вероятностью выберет того, кто не станет голосовать против Руди, значения p и q должны удовлетворять условию p > 0,5 > q. При каких значениях коэффициента p/q Рику следует выбрать вариант «прекратить»? Объясните на интуитивном уровне, почему при некоторых значениях p и q для Рика предпочтительнее вариант «продолжить».
Глава 4. Игры с одновременными ходами: дискретные стратегии
* * *
Игрой с одновременными ходами, как пояснялось в главе 2, считается игра, в которой игроки делают ходы, не зная о выборе соперников. Очевидно, что такая ситуация складывается в случае, когда игроки действуют одновременно, а также когда они выбирают действия обособленно, не располагая информацией о действиях других игроков, даже если этот выбор делается в разное время. (Именно поэтому в играх с одновременными ходами имеет место несовершенная информация в том смысле, о котором мы говорили в разделе 2.Г главы 2.) Эта глава посвящена играм, в которых присутствует только одновременное взаимодействие между игроками. Мы рассмотрим различные типы игр с одновременными ходами, опишем концепцию их решения под названием «равновесие Нэша» и проанализируем игры без, с одним и несколькими равновесиями.
К категории игр с одновременными ходами можно отнести многие из знакомых вам стратегических ситуаций. Различные производители телевизоров, стереосистем или автомобилей принимают решения о дизайне и свойствах продукта, не зная о контраргументах конкурентов. Избиратели на выборах одновременно отдают свои голоса, не зная о предпочтениях других избирателей. В футболе взаимодействие между вратарем и нападающим противника во время пенальти требует одновременного решения обоих: вратарь не может себе позволить ждать удара по мячу, чтобы определить его траекторию, поскольку тогда уже будет слишком поздно.
Очевидно, что при выборе действия участник игры с одновременными ходами не располагает информацией о решениях других игроков. Кроме того, он не может предвидеть их реакцию на его выбор, так как они тоже действуют вслепую по отношению к нему. Поэтому каждый игрок должен анализировать предполагаемые шаги соперников, а те, в свою очередь, проводить аналогичный встречный анализ. Такая цикличность несколько усложняет анализ игр с одновременными ходами по сравнению с анализом игр с последовательными ходами, но выполнить его не так уж трудно. В этой главе мы сформулируем для этих игр простую концепцию равновесия, обладающую значительной пояснительной и прогностической способностью.
1. Описание игр с одновременными ходами и дискретными стратегиями
В главе 2 и главе 3 мы неоднократно подчеркивали, что стратегия — это исчерпывающий план действий. Однако в чистых играх с одновременными ходами у каждого участника есть максимум одна возможность действовать (хотя такое действие может состоять из множества компонентов), поскольку если бы их было несколько, это был бы уже элемент игры с последовательными ходами. Стало быть, в играх с одновременными ходами нет никаких реальных различий между стратегией и действием, поэтому в данном контексте эти термины часто используются как синонимы. Существует только одна сложность. Стратегия может представлять собой вероятностный выбор из первоначально оговоренных базовых действий. Например, в спорте игрок или команда могут умышленно выбирать действия в случайном порядке, чтобы соперник был вынужден угадывать. Такие вероятностные стратегии называются смешанными и рассматриваются в главе 7. Сейчас же мы ограничимся анализом базовых, первоначально оговоренных действий, обозначаемых термином чистые стратегии.
Во многих играх у каждого игрока есть конечное количество дискретных чистых стратегий, например дриблинг, пас и бросок в баскетболе, тогда как в ряде других игр чистая стратегия игрока может представлять собой любое число из непрерывного диапазона значений, скажем цену, назначаемую компанией на свой продукт[41]. Это различие никак не влияет на общую концепцию равновесия в играх с одновременными ходами, но связанные с такими играми идеи легче формулировать с помощью дискретных стратегий; решение игр с непрерывными стратегиями требует несколько более продвинутых инструментов. Поэтому в данной главе мы ограничимся анализом более простых чистых дискретных стратегий, а стратегии с непрерывными переменными рассмотрим в главе 5.
Игры с одновременными ходами и дискретными стратегиями чаще всего описывают с помощью таблицы игры (синонимы: матрица игры или таблица выигрышей), которая называется нормальной или стратегической формой игры. Таблица игры позволяет проиллюстрировать игру с любым количеством участников, однако ее размерность должна соответствовать их числу. В случае игры с двумя участниками таблица имеет два измерения, а заголовки строк и столбцов в ней — это стратегии, находящиеся в распоряжении первого и второго игроков. Следовательно, размер таблицы зависит от количества доступных игрокам стратегий[42]. В ячейках указываются выигрыши, которые получат игроки при подобающей конфигурации стратегий. Игры с тремя участниками требуют трехмерной таблицы; ее мы рассмотрим далее в этой главе.
Концепция таблицы выигрышей для простой игры приведена на рис. 4.1. Представленная на нем игра не имеет специальной интерпретации, поэтому мы можем сформулировать концепции, не отвлекаясь на ее «историю». Имена участников игры — Строка и Столбец. В распоряжении Строки находится четыре варианта выбора (стратегий или действий), обозначенных как «вверху», «высоко», «низко», «внизу», а Столбца — три варианта: «слева», «посредине» и «справа». Каждый выбор Строки и Столбца определяет возможный исход игры. Выигрыши, связанные с каждым исходом игры, показаны в ячейке, соответствующей данной строке и данному столбцу. Принято считать, что из двух чисел, отображающих выигрыши, первое число отвечает выигрышу Строки, а второе — выигрышу Столбца. Например, если Строка выберет вариант «высоко», а Столбец — «справа», выигрыши составят 6 в случае Строки и 4 в случае Столбца. Для дополнительного удобства мы выделяем все, что касается Строки (имя игрока, его стратегии и выигрыши), черным цветом, а Столбца — серым.
Рис. 4.1. Представление игры с одновременными ходами в виде таблицы
Далее рассмотрим второй пример игры с более содержательной историей. На рис. 4.2 представлена упрощенная версия одного розыгрыша в американском футболе. Нападающие пытаются продвинуть мяч вперед, чтобы повысить шансы забить филд-гол. У них есть четыре возможные стратегии: пробежка и три паса разной длины (короткий, средний и длинный). Чтобы сдерживать атаку, защитники могут использовать одну из трех стратегий: защита в случае пробежки и в случае паса и блиц против квотербека. Нападающие пытаются набрать как можно больше ярдов, тогда как защитники — помешать им это сделать. Предположим, у нас достаточно информации об основных сильных сторонах тех и других, для того чтобы оценить вероятность завершения различных розыгрышей и определить среднее количество набранных ярдов, которого можно было бы ожидать при каждой комбинации стратегий. Например, когда команда нападения выбирает стратегию «средний пас», а команда защиты отвечает стратегией «защита в случае паса», по нашим оценкам, выигрыш нападения составляет 4,5 набранных ярда, или +4,5[43]. «Выигрыш» защиты — 4,5 потерянных ярда, или 4,5. В других ячейках также показаны наши оценки количества ярдов, набранных или потерянных каждой командой.
Рис. 4.2. Один розыгрыш в американском футболе
Обратите внимание, что сумма выигрышей в каждой ячейке таблицы равна 0: когда нападающие набирают 5 ярдов, защитники теряют 5 ярдов, и наоборот: когда нападающие теряют 2 ярда, защитники набирают 2 ярда. Такая схема достаточно широко распространена в спорте, где интересы двух сторон прямо противоположны друг другу. Как отмечалось в главе 2, мы называем это игрой с нулевой (или иногда с постоянной) суммой. Вы должны помнить, что, согласно определению, игра с нулевой суммой представляет собой игру, в которой сумма выигрышей во всех ячейках постоянная величина, будь то 0, 6 или 1000. (В разделе 7 описывается игра, в которой сумма выигрышей двух игроков составляет 100.) Основная особенность игры с нулевой сумой состоит в том, что проигрыш одного игрока равен выигрышу другого.
2. Равновесие Нэша
Для анализа игр с одновременными ходами необходимо рассмотреть, как игроки выбирают действия. Вернемся к игре, представленной на рис. 4.1. Обратите внимание на тот ее исход, при котором Строка выбирает вариант «низко», а Столбец — «посредине», с выигрышами 5 для Строки и 4 для Столбца. Каждый игрок отдает предпочтение действию, которое обеспечит ему более высокий выигрыш, и при данном исходе делает такой выбор с учетом выбора соперника. Если Строка выбирает вариант «низко», может ли Столбец получить более высокий выигрыш, выбрав что-то другое, а не «посредине»? Нет, поскольку вариант «слева» обеспечивает ему выигрыш 2, а вариант «справа» — выигрыш 3 и оба не превышают выигрыш 4 в случае варианта «посредине». Стало быть, стратегия «посредине» — наилучший ответ Столбца на стратегию «низко», реализуемую Строкой. С другой стороны, если Столбец остановится на варианте «посредине», получит ли Строка более высокий выигрыш, предпочтя варианту «низко» какой-нибудь иной? И снова нет, потому что выигрыши от выбора варианта «вверху» (2), «высоко» (3) или «внизу» (4) не будут больше выигрыша Строки в случае выбора варианта «низко» (5). Следовательно, «низко» — наилучший ответ Строки на стратегию «посредине», применяемую Столбцом.
Эти два варианта выбора, «низко» для Строки и «посредине» для Столбца, представляют собой наилучший ответ игрока, сделавшего соответствующий выбор, на действие другого игрока. После такого выбора оба игрока не захотели бы по собственной инициативе переключаться на что-либо другое. Согласно определению некооперативной игры, игроки делают выбор независимо друг от друга; следовательно, такие односторонние изменения — все, что может предпринять каждый игрок. Но поскольку ни один из них к ним не склонен, было бы естественно называть данное положение вещей равновесием. В этом и состоит суть концепции равновесия Нэша.
Согласно несколько более формальной формулировке, равновесие Нэша[44] в игре представляет собой перечень стратегий (по одной на каждого участника), при котором ни один игрок не может увеличить выигрыш, выбрав другую стратегию из имеющихся в его распоряжении, если другие игроки придерживаются стратегий, оговоренных в этом перечне.
Для того чтобы лучше понять концепцию равновесия Нэша, давайте еще раз проанализируем игру на рис. 4.1. Возьмем какую-либо другую ячейку вместо ячеек «низко», «посредине», например ячейку, в которой Строка выбирает вариант «высоко», а Столбец — «слева». Может ли это сочетание стратегий быть равновесием Нэша? Нет, потому что, если Столбец применит стратегию «слева», Строка при выборе стратегии «внизу» вместо «высоко», которая обеспечивает выигрыш 4, получит более высокий выигрыш 5. Точно так же сочетание стратегий «внизу», «слева» не будет равновесием Нэша, поскольку Столбец может извлечь больше выгоды, перейдя на стратегию «справа» и тем самым увеличив свой выигрыш с 6 до 7.
Определение равновесия Нэша не требует, чтобы равновесные варианты выбора обязательно были лучше всех имеющихся вариантов. На рис. 4.3 отображена та же ситуация, что и на рис. 4.1, за одним исключением: выигрыш Строки от стратегий «внизу», «посредине» изменился на 5, то есть стал таким же, как и для стратегий «низко», «посредине». По-прежнему верно то, что при выборе Столбцом варианта «посредине» Строка не может добиться большего, чем в случае выбора варианта «низко». Следовательно, ни у одного игрока нет оснований для изменения действия в результате исхода «низко», «посредине», что позволяет квалифицировать данный исход как равновесие Нэша[45].
Рис. 4.3. Вариант игры, представленной на рис. 4.1, с равными выигрышами
Однако важно учесть, что равновесие Нэша не всегда оптимально для обоих игроков. На рис. 4.1 пара стратегий «внизу», «справа» обеспечивает выигрыши 9, 7, которые лучше для обоих игроков, чем выигрыши 5, 4 при равновесии Нэша. Тем не менее, играя независимо друг от друга, игроки не смогут придерживаться именно этих стратегий. Если Столбец предпочтет вариант «справа», Строка может захотеть заменить вариант «внизу» на «низко» и выиграть 12 вместо 9. Получение выигрышей 9, 7 потребует кооперативного действия, которое сделало бы такой «обман» невозможным. Мы рассмотрим данный тип поведения чуть ниже (и более подробно в главе 10), а пока просто хотим указать на тот факт, что равновесие Нэша может не соответствовать общим интересам игроков.
Чтобы закрепить понимание концепции равновесия Нэша, давайте еще раз посмотрим на рис. 4.2, отображающий игру в американский футбол. Если защита выберет стратегию «защита в случае паса», то лучший вариант для нападающих — «короткий пас» (выигрыш 5,6 против 5, 4,5 или 3). И наоборот, если команда нападения предпочтет вариант «короткий пас», то лучший вариант для защиты — «защита в случае паса», которая позволит команде нападения набрать всего 5,6 ярда, тогда как при выборе вариантов «защита в случае пробежки» и «блиц» команда защиты уступила бы 6 и 10,5 ярда соответственно. (Не забывайте, что записи в каждой ячейке таблицы игры с нулевой суммой — это выигрыши игрока под именем Строка, поэтому самый лучший вариант выбора для Столбца — тот, который обеспечивает самый низкий, а не самый высокий показатель.) В данной игре сочетание стратегий «короткий пас», «защита в случае паса» — это равновесие Нэша, а полученный выигрыш команды нападения составляет 5,6 ярда.
Как вычислить равновесие Нэша в играх? Для этого можно проверить каждую ячейку на наличие стратегий, удовлетворяющих равновесию Нэша. Такой систематический анализ надежен, но утомителен, за исключением случаев, когда он выполняется в контексте простых игр или с помощью хорошей компьютерной программы. К счастью, существуют и другие методы, применимые к особым типам игр, которые позволяют не только быстро отыскать равновесие Нэша, но и лучше понять процесс размышлений, посредством которого формируются убеждения, а затем и выбор. Мы проанализируем эти методы в следующих разделах.
Прежде чем приступать к дальнейшему изучению и применению концепции равновесия Нэша, попробуем прояснить то, что, возможно, тревожит некоторых из вас. Мы сказали, что в равновесии Нэша каждый игрок выбирает свой лучший ответ на выбор другого игрока. Но выбор делается одновременно. Тогда как игрок может реагировать на то, что еще не произошло, или по крайней мере не зная, что именно произошло?
Люди постоянно играют в игры с одновременными ходами и делают свой выбор. Для этого им необходимо найти замену фактическим знаниям или наблюдениям за действиями других игроков. Игроки могут делать слепые догадки и рассчитывать на то, что они окажутся ниспосланными свыше, но, к счастью, существуют более эффективные способы выяснить, что предпринимают другие. Один из них — опыт и наблюдение: если игроки постоянно играют в данную игру или аналогичные игры с подобными игроками, у них может сформироваться неплохое представление об их предпочтениях. В этом случае не самые лучшие варианты выбора вряд ли продержатся долго. Еще один способ — логический процесс мышления через размышления других игроков. Вы ставите себя на их место и размышляете о том, о чем они думают; разумеется, они тоже ставят себя на ваше место и размышляют о том, что думаете вы. На первый взгляд такая логика кажется циклической, однако есть несколько способов вмешаться в этот цикл, и мы покажем их на конкретных примерах в следующих разделах. Равновесие Нэша можно считать кульминацией такого процесса размышлений, в ходе которого каждый игрок правильно определил выбор других игроков.
Посредством наблюдения, или логической дедукции, или какого-либо иного подхода вы как участник игры формируете некоторое представление о выборе участников игр с одновременными ходами. Найти слова для описания этого процесса или его результатов не так уж легко. Речь идет не о предвидении и не о прогнозировании, поскольку действия других игроков выполняются одновременно с вашими и не относятся к будущему. Специалисты по теории игр чаще всего используют термин убеждение. Он не идеален для обозначения происходящего, поскольку вызывает смысловые ассоциации с уверенностью или определенностью в большей степени, чем следовало бы (в главе 7 мы допустим возможность того, что убеждения могут быть сопряжены с некоторой неопределенностью), однако ввиду отсутствия более подходящего обозначения нам придется им довольствоваться.
Концепция убеждения соотносится также с описанием неопределенности, представленным в разделе 2.Г главы 2, где мы ввели понятие стратегической неопределенности. Даже в случаях, когда все правила игры (стратегии, имеющиеся в распоряжении игроков, и выигрыши каждого игрока как функция стратегий всех игроков) известны и не подвержены влиянию внешних факторов неопределенности, таких как погода, каждый игрок может испытывать неопределенность относительно действий, предпринимаемых одновременно с ним другими игроками. Точно так же, если прошлые действия не поддаются наблюдению, каждый игрок может испытывать неопределенность по поводу действий других игроков в прошлом. Как же игрокам делать выбор в условиях такой стратегической неопределенности? Они должны составить субъективное мнение или оценку действий других игроков, что, собственно, и позволяет осуществить концепция убеждения.
А теперь представьте себе равновесие Нэша в таком контексте. Мы определили его как конфигурацию стратегий, при которой стратегия каждого игрока представляет собой лучший ответ на стратегии других игроков. Если игрок не располагает информацией о фактическом выборе остальных участников игры, но имеет о нем определенные убеждения, в равновесии Нэша они должны быть правильными: фактические действия других игроков должны соответствовать вашим убеждениям. Следовательно, мы можем дать альтернативное и эквивалентное определение: равновесие Нэша — это такая совокупность стратегий (по одной на каждого игрока), при которой 1) у каждого игрока есть правильные убеждения о стратегиях других игроков; 2) стратегия каждого игрока — лучшая для него самого с учетом его убеждений относительно стратегий других игроков[46].
Данный подход к оценке равновесия Нэша имеет два преимущества. Во-первых, концепция лучшего ответа больше не содержит логического противоречия. Каждый игрок выбирает свой лучший ответ не на не поддающиеся наблюдению действия других игроков, а на собственные уже сформировавшиеся убеждения в отношении их действий. Во-вторых, как сказано в главе 7, где мы допускаем смешанные стратегии, случайность в стратегии одного игрока можно интерпретировать как неопределенность убеждений других игроков в отношении его действий. В этой главе мы будем параллельно использовать обе интерпретации равновесия Нэша.
На первый взгляд может показаться, что формирование правильных убеждений и вычисление лучших ответов — слишком сложная задача для обычного человека. Мы обсудим некоторые критические замечания такого рода, а также эмпирические и экспериментальные данные о равновесии Нэша в главе 5 в контексте чистых стратегий и в главе 7 в контексте смешанных стратегий. А пока просто напомним, что практика — критерий истины. Мы сформулируем и проиллюстрируем концепцию Нэша на примере ее применения и надеемся, что так вы лучше поймете ее достоинства и недостатки, чем в ходе абстрактного обсуждения этой темы.
3. Доминирование
Существует категория игр, в которых одна стратегия неизменно оказывается лучше или хуже другой. В таких случаях применяется один способ, позволяющий упростить поиск равновесия Нэша и его интерпретацию.
Эту концепцию отлично иллюстрирует известная игра под названием «дилемма заключенных». Рассмотрим сюжет, регулярно используемый в телесериале Law and Order («Закон и порядок»). Предположим, мужа и жену арестовали по подозрению в преступном сговоре в целях убийства молодой женщины. Детективы Грин и Лупо размещают их в разных камерах предварительного заключения и допрашивают по отдельности. Реальных улик, связывающих эту пару с убийством, очень мало, хотя есть доказательства того, что они причастны к похищению жертвы. Детективы объясняют каждому подозреваемому, что им обоим грозит тюремное заключение за похищение сроком до 3 лет, даже если ни один из них не признается. Кроме того, мужу и жене по отдельности внушают, что детективам «известны» подробности произошедшего и что один из них участвовал в совершении преступления по принуждению второго. При этом подразумевается, что тюремный срок одного признавшегося будет существенно сокращен, если все подробно изложить на бумаге. (Во многих фильмах такого рода в этот момент на стол обычно кладут стандартный блокнот с отрывными страницами из желтой линованной бумаги и карандаш.) И наконец, супругов убеждают, что, если они оба признают свою вину, можно будет говорить о снижении их тюремных сроков, но не настолько, как в случае, если бы один из них сознался, а другой отрицал свою вину.
В такой ситуации муж и жена — два участника игры с одновременными ходами, в которой каждый игрок должен сделать выбор: сознаваться в убийстве или нет. Оба знают, что в случае отказа признать свою вину каждому из них светит 3 года тюрьмы за причастность к похищению. Подозреваемые также знают, что если один из них сознается, то получит всего 1 год благодаря сотрудничеству с полицией, тогда как другой отправится в тюрьму минимум на 25 лет. Если сознаются оба, у них будет возможность договориться о сокращении тюремного срока до 10 лет для каждого.
Варианты выбора и исходы этой игры представлены в таблице игры на рис. 4.4. Стратегии «признать вину» и «отрицать вину» можно также обозначить как «отказ от сотрудничества» и «сотрудничество», поскольку это отображает роли двух игроков в отношениях между ними. Таким образом, стратегия «отказ от сотрудничества» означает нарушение любой молчаливой договоренности с супругом (супругой), а стратегия «сотрудничество» — совершение действия, которое поможет супругу (супруге), а не сотрудничество с полицейскими.
Рис. 4.4. Дилемма заключенных
Здесь выигрыши — это длительность тюремного заключения в случае каждого исхода игры, поэтому более низкие значения лучше для каждого игрока. Этим данный пример отличается от большинства анализируемых нами игр, в которых более высокий выигрыш — это хорошо, а не плохо. Так что хотим вас предупредить, что больше — не всегда лучше. Когда значения выигрышей отражают рейтинг исходов игры, лучшая альтернатива часто обозначается 1, а последовательно увеличивающиеся числа соответствуют следующим худшим альтернативам. Кроме того, в таблице игры с нулевой суммой, в которой показаны только выигрыши одного игрока, построенные по принципу «чем больше, тем лучше», меньшие числа для другого игрока будут лучше. В представленной здесь дилемме заключенных меньшие числа лучше для обоих игроков. Следовательно, если вам когда-либо придется составлять таблицу выигрышей, где большие числа — это плохо, вы должны четко предупредить об этом читателя, но и сами, если будете читать составленные кем-то примеры, не забывайте о данном нюансе.
Теперь рассмотрим игру с дилеммой заключенных на рис. 4.4 с точки зрения мужа. Он должен подумать, что предпочтет жена. Предположим, он убежден, что она сознается. Тогда его лучший выбор — тоже сознаться, поскольку так он получит 10 лет тюрьмы вместо 25 лет в случае отрицания вины. А если муж полагает, что жена не признается? Опять же, его лучший выбор — сознаться, так как это гарантирует ему всего год заключения вместо трех, которые бы ему обеспечило отрицание вины. Таким образом, в данной игре стратегия «признать вину» для мужа лучше стратегии «отрицать вину» независимо от его убеждений в отношении выбора жены. Будем говорить, что с точки зрения мужа «признать вину» — это доминирующая стратегия, а «отрицать вину» — доминируемая стратегия. Точно так же мы могли бы сказать, что стратегия «признать вину» доминирует над стратегией «отрицать вину» или что стратегия «отрицать вину» доминируется стратегией «признать вину».
Если то или иное действие явно лучшее для игрока независимо от действий других игроков, есть веские основания полагать, что рациональный игрок выберет именно его. Если то или иное действие явно худшее для игрока независимо от действий других игроков, есть не менее серьезные основания считать, что рациональный игрок будет его избегать. Следовательно, доминирование (когда оно существует) образует убедительную основу для теории решений игр с одновременными ходами.
