Стратегические игры. Доступный учебник по теории игр Диксит Авинаш
Давайте возьмем в качестве примера этого процесса игру, представленную на рис. 4.1. Рассмотрим первые стратегии Строки. Если какая-то стратегия неизменно обеспечивает этому игроку худшие выигрыши, то она является доминируемой и ее можно исключить из рассмотрения в поисках равновесного выбора Строки. В данном примере единственная доминируемая стратегия Строки — «высоко», над которой доминирует стратегия «внизу»: если Столбец выберет стратегию «слева», Строка получит выигрыш 5 за счет стратегии «внизу» и 4 — за счет стратегии «высоко»; если Столбец предпочтет стратегию «справа», Строка получит выигрыш 9, применив стратегию «внизу», и только 6 в случае «высоко». Следовательно, мы можем исключить стратегию «высоко» из рассмотрения. Теперь проанализируем варианты выбора Столбца на предмет исключения. Стратегия Столбца «слева» доминируется стратегией «справа» (что подтверждают аналогичные рассуждения: 1 < 2, 2 < 3 и 6 < 7). Обратите внимание, что мы не могли сделать такой вывод раньше, до удаления стратегии Строки «высоко»: в игре против стратегии Строки «высоко» Столбец получил бы выигрыш 5 за счет стратегии «слева» и только 4 за счет стратегии «справа». Стало быть, первый этап исключения стратегии Строки «высоко» позволяет перейти ко второму этапу, сводящемуся к удалению стратегии Столбца «слева». Таким образом, в контексте оставшегося набора стратегий («вверху», «низко» и «внизу» у Строки и «посредине» и «справа» у Столбца) стратегии Строки «вверху» и «внизу» доминируемы стратегией «низко». Когда у Строки остается только стратегия «низко», Столбец выберет свой наилучший ответ — а именно стратегию «посредине».
Следовательно, эта игра разрешима по доминированию, а ее исход — «низко»/«посредине» с выигрышами 5, 4. Мы определили его как равновесие Нэша, когда впервые иллюстрировали данную концепцию с помощью этой игры. Теперь более подробно рассмотрели процесс размышлений игроков, приводящий к формированию правильных убеждений. Рациональный игрок Строка не выберет стратегию «высоко». Рациональный игрок Столбец поймет это и, взвесив эффективность своих стратегий против оставшихся у Строки, не выберет «слева». Строка, в свою очередь, предвидя это, не выберет ни «вверху», ни «внизу». И наконец, Столбец, проанализировав все это, применит «посредине».
Другие игры могут быть не разрешимы по доминированию, а последовательное исключение доминируемых стратегий может не обеспечить уникальный исход игры. Но даже в таких случаях исключение доминируемых стратегий позволяет уменьшить размер игры и облегчить ее решение с помощью одного или более методов, описанных в следующих разделах. Стало быть, исключение доминируемых стратегий может стать полезным шагом на пути к решению большой игры с одновременными ходами, даже если не предоставляет возможности решить ее полностью.
До сих пор в процессе анализа итеративного исключения доминируемых стратегий все сравнения выигрышей носили однозначный характер. Но что если выигрыши окажутся равными? Рассмотрим вариант предыдущей игры, показанной на рис. 4.3. В этой ее версии стратегии «высоко» (у Строки) и «слева» (у Столбца) также исключаются. На следующем этапе «низко» по-прежнему доминирует над «вверху», а вот доминирование «низко» над «внизу» стало менее очевидным. Эти две стратегии обеспечивают Строке равные выигрыши в борьбе против стратегии Столбца «посредине», хотя стратегия «низко» все же гарантирует Строке более высокий выигрыш по сравнению со стратегией «внизу» при их использовании против стратегии Столбца «справа». Будем говорить, что с точки зрения Строки в данный момент стратегия «низко» слабо доминирует над стратегией «внизу». Напротив, стратегия «низко» строго доминирует над стратегией «вверху», поскольку обеспечивает более высокие выигрыши, чем стратегия «вверху», разыгранная против обеих стратегий Столбца («посредине» и «справа»), анализируемых на данном этапе.
А теперь хотим предупредить вас вот о чем: последовательное исключение слабо доминируемых стратегий может привести к потере некоторых равновесий Нэша. Рассмотрим игру, представленную на рис. 4.6, где мы вводим Ровену как игрока вместо Строки и Колина вместо Столбца[48]. В случае Ровены стратегия «вверх» слабо доминируема стратегией «вниз»; если Колин сыграет «налево», то Ровена получит лучший выигрыш, применив стратегию «вниз», а не «вверх», а если Колин сыграет «направо», то Ровена получит один и тот же выигрыш от обеих своих стратегий. Точно так же для Колина стратегия «направо» слабо доминирует над стратегией «налево». В таком случае разрешимость по доминированию говорит нам, что сочетание стратегий «вниз»/«направо» — равновесие Нэша. Это действительно так, но «вниз»/«налево» и «вверх»/«направо» — тоже равновесия Нэша. Рассмотрим сочетание «вниз»/«налево». Когда Ровена выбирает «вниз», Колин не может улучшить свой выигрыш, переключившись на стратегию «направо», а когда Колин выбирает «налево», лучший ответ Ровены — сыграть «вниз». Аналогичные рассуждения позволяют убедиться, что «вверх»/«направо» — также равновесие Нэша.
Рис. 4.6. Исключение слабо доминируемых стратегий
В связи с этим при использовании слабого доминирования для исключения некоторых стратегий целесообразно проверить, не пропустили ли вы какие-либо равновесия, с помощью других методов (таких как метод, представленный в следующем разделе). Решение по итеративному доминированию можно считать вероятным равновесием Нэша в этой игре с одновременными ходами, однако следует учитывать также важность множественности равновесий и другие равновесия сами по себе. Мы рассмотрим эти вопросы в следующих главах, проанализировав множественность равновесий в главе 5 и взаимосвязи между играми с последовательными и одновременными ходами в главе 6.
4. Анализ наилучших ответов
Во многих играх с одновременными ходами нет ни доминирующих, ни доминируемых стратегий. Другие игры могут иметь одну или несколько доминируемых стратегий, но их итеративное исключение не обеспечивает единственного исхода игры. В таких случаях необходимо выполнить следующий шаг в процессе поиска решения игры. Мы по-прежнему ищем равновесие Нэша, в котором каждый игрок предпринимает свое лучшее действие с учетом действий другого игрока (игроков), но теперь должны прибегнуть к более тонкому стратегическому мышлению, чем то, которого требует простое исключение доминируемых стратегий.
Здесь мы сформулируем еще один систематический метод поиска равновесий Нэша, который нам очень пригодится при выполнении последующего анализа. Для начала введем требование о правильности убеждений. Мы будем по очереди принимать точку зрения каждого игрока и задавать такой вопрос: какой лучший ответ данного игрока на каждый вариант выбора, который может сделать другой игрок (игроки)? Таким образом мы найдем лучшие ответы каждого игрока на все стратегии, доступные другим игрокам. В математических терминах это означает, что мы найдем стратегию лучшего ответа каждого игрока в зависимости от (или как функцию от) стратегий, находящихся в распоряжении других игроков.
Вернемся к игре, в которую играли Строка и Столбец, и представим ее на рис. 4.7. Сначала проанализируем ответы Строки. Если Столбец применит стратегию «слева», наилучший ответ Строки — «внизу», обеспечивающий выигрыш 5. Мы показываем его, выделив соответствующий выигрыш кружком в таблице игры. Если Столбец предпочтет стратегию «посредине», лучший ответ Строки — «низко» (тоже выигрыш 5). А если Столбец выберет стратегию «справа», оптимальный выбор Строки — снова «низко» (выигрыш 12). Опять же, мы показываем лучшие варианты выбора Строки, обведя кружками соответствующие выигрыши. Аналогичным образом представлены лучшие ответы Столбца, выигрыши по которым выделены кружками: 3 (стратегия «посредине» как лучший ответ на стратегию Строки «вверху»), 5 («слева» как лучший ответ на «высоко»), 4 («посредине» как лучший ответ на «низко») и 7 («справа» как лучший ответ на «внизу»)[49]. Мы видим, что в одной ячейке — а именно «низко»/«посредине» — оба выигрыша выделены кружками. Следовательно, стратегии «низко» у Строки и «посредине» у Столбца одновременно будут лучшими ответами друг на друга. Мы нашли равновесие Нэша в этой игре еще раз.
Рис. 4.7. Анализ наилучших ответов
Анализ наилучших ответов — это исчерпывающий способ обнаружения в игре всех возможных равновесий Нэша. Вам следует углубить понимание этого метода, применив его ко всем играм, описанным в данной главе. Примеры с доминированием представляют особый интерес. Если у Строки есть доминирующая стратегия, именно она будет наилучшим ответом на все стратегии Столбца; следовательно, все наилучшие ответы Строки расположены по горизонтали в одной и той же строке. Точно так же, если у Столбца есть доминирующая стратегия, то все его наилучшие ответы выстроятся по вертикали в одном и том же столбце. Вы можете сами проверить, как такой анализ позволяет определить равновесия Нэша в дилемме заключенных с участием мужа и жены, показанной на рис. 4.4, и в игре между Конгрессом и Федеральной резервной системой, отображенной на рис. 4.5.
В некоторых играх анализ наилучших ответов не позволяет найти равновесие Нэша, подобно тому как разрешимость по доминированию не всегда обеспечивает требуемый результат. Однако в данном случае мы можем сказать кое-что более конкретное, чем при неудачной попытке использовать доминирование. Когда анализ наилучших ответов в игре с дискретными стратегиями не обнаруживает равновесия Нэша, это означает, что в этой игре нет равновесия в чистых стратегиях. Мы рассмотрим игры такого типа в разделе 7 данной главы, а в главе 5 расширим область применения анализа наилучших ответов на игры, в которых стратегии представляют собой непрерывные переменные, например цены или расходы на рекламу. Кроме того, мы построим кривые наилучших ответов, что позволит нам находить равновесия Нэша, и увидим, что в подобных играх равновесие может отсутствовать с меньшей вероятностью в силу непрерывности выбора стратегий.
5. Три игрока
До сих пор мы анализировали только игры между двумя участниками. Однако все рассмотренные методы анализа применимы и для поиска равновесий Нэша в чистых стратегиях в любой игре с одновременными ходами с участием любого количества игроков. Когда в игре больше двух участников, каждому из которых доступно сравнительно небольшое количество чистых стратегий, анализ можно выполнить с помощью таблицы игры, подобно тому как мы это делали в первых четырех разделах данной главы.
В главе 3 мы рассматривали игру с тремя участницами, каждая из которых имела по две чистые стратегии. Эмили, Нине и Талии предстояло решить, вносить ли вклад в создание декоративного сада на их маленькой улице. Мы предположили, что в случае вклада всех трех участниц игры сад будет не лучше, чем при вкладе двоих девушек, а вот если вклад сделает только одна участница, сад получится настолько скудным, что уж лучше его и не высаживать вовсе. Теперь допустим, что три участницы делают выбор одновременно, а разнообразие возможных исходов и выигрышей несколько богаче. В частности, размер и пышность сада будут зависеть от точного количества инвесторов: вклад трех участниц позволит разбить самый большой и красивый сад, двух — средний сад и одной — маленький.
Предположим, Эмили анализирует вероятные исходы игры «уличный сад». Ей предстоит оценить шесть возможных вариантов. Эмили может выбирать, вносить или не вносить вклад, если и Нина, и Талия внесут свой вклад или если ни одна из них этого не сделает либо сделает только одна. С точки зрения Эмили, лучший возможный исход с рейтингом 6 — воспользоваться добротой соседок и сделать так, чтобы Нина и Талия инвестировали в создание сада, а она сама — нет. Тогда Эмили могла бы наслаждаться средним садом, не вкладывая в него заработанные тяжелым трудом деньги. Если Нина и Талия вложат средства в сад и Эмили тоже, она сможет любоваться большим прекрасным садом, но ценой собственного вклада, поэтому она присваивает этому исходу рейтинг 5.
На другом конце диапазона находятся исходы, возникающие в случае отказа Нины и Талии инвестировать в сад. При таком раскладе Эмили снова предпочтет не вносить вклад, поскольку иначе все расходы на создание общественного сада, которым будут наслаждаться все, лягут на ее плечи; уж лучше она посадит цветы у себя во дворе. Таким образом, если другие участницы игры отказываются вкладывать средства в создание сада, Эмили присваивает рейтинг 1 исходу, при котором она вносит вклад, и рейтинг 2 исходу, при котором она этого не делает.
Между крайними случаями находятся ситуации, в которых кто-то один — либо Нина, либо Талия — вносит вклад, но не сразу обе. Когда одна из них это делает, Эмили знает, что сможет наслаждаться маленьким садом, не принимая участия в его создании. Кроме того, она считает, что цена ее вклада перевешивает то, что он позволит увеличить размер сада. Поэтому Эмили присваивает рейтинг 4 исходу, при котором она не вносит вклад, но получает возможность наслаждаться маленьким садом, и рейтинг 3 исходу, при котором вносит вклад, обеспечивая создание среднего сада. Поскольку Нина и Талия придерживаются аналогичных взглядов на затраты и преимущества, каждая из них составляет такой же рейтинг вероятных исходов игры, в котором самый худший — когда каждая участница инвестирует в создание сада, а две оставшиеся этого не делают, и т. д.
Если все трое решают, вносить ли вклад в создание сада, не зная о действиях соседок, перед нами — игра с одновременными ходами с тремя игроками. Для того чтобы найти в ней равновесие Нэша, необходимо составить таблицу игры. В случае игры с тремя участниками таблица должна быть трехмерной, а стратегии третьего игрока должны соответствовать третьему измерению. Самый простой способ его прибавить к двумерной таблице игры — добавить страницы. Первая страница таблицы отображает выигрыши для первой стратегии третьего игрока, вторая страница — выигрыши для второй стратегии третьего игрока и т. д.
Мы показываем трехмерную таблицу игры «уличный сад» на рис. 4.8. В ней две строки отведены для двух стратегий Эмили, два столбца — для двух стратегий Нины и две страницы — для двух стратегий Талии. Мы разместили эти страницы рядом, чтобы вы могли видеть все одновременно. В каждой ячейке выигрыши перечислены в следующем порядке: сначала выигрыш игрока строки, затем выигрыш игрока столбца, далее выигрыш игрока страницы, то есть в данном примере: Эмили, Нина, Талия.
Рис. 4.8. Игра «уличный сад»
Прежде всего мы должны определить, есть ли доминирующие стратегии у каждой из участниц. В таблицах игр из одной страницы это было достаточно просто: мы просто сравнивали исходы, связанные с одной из стратегий игрока, с исходами другой его стратегии. На практике в случае игрока строки такое сравнение требовало простой проверки данных в столбцах одной страницы таблицы и наоборот в случае игрока столбца. Сейчас же мы должны проверить данные на обеих страницах таблицы, чтобы определить, есть ли доминирующая стратегия у какой-либо из участниц игры.
В случае Эмили мы сравниваем две строки обеих страниц таблицы и видим, что если Талия внесет вклад, то доминирующая стратегия Эмили — не вносить вклад. Следовательно, для Эмили лучше не вносить вклад в создание сада независимо от решений остальных участниц игры. Точно так же мы видим, что доминирующая стратегия Нины (на обеих страницах таблицы) — не вносить вклад. А вот при поиске доминирующей стратегии у Талии нужно быть предельно внимательными. Мы должны сравнить исходы, которые поддерживают постоянство поведения Эмили и Нины, проанализировав выигрыши Талии в случае выбора стратегии «внести вклад» в сравнении с выигрышами от выбора стратегии «не вносить вклад». Иными словами, мы должны сравнить ячейки двух страниц таблицы: верхнюю левую ячейку первой страницы (слева) с верхней левой ячейкой второй страницы (справа) и т. д. Как и для первых двух участниц игры, этот процесс показывает, что доминирующая стратегия Талии — тоже не вносить вклад.
Итак, у каждой участницы игры есть доминирующая стратегия, которая должна быть ее равновесной чистой стратегией. Равновесие Нэша в этой игре состоит в том, что все ее участницы предпочитают не вкладывать средства в создание сада и получить второй по величине выигрыш. При этом сад так и не будет посажен, а участницы игры не понесут лишних расходов.
Обратите внимание, что эта игра — еще один пример дилеммы заключенных. Существует единственное равновесие Нэша, при котором все игроки получают выигрыш 2. Однако у «уличного сада» есть еще один исход (при котором все три соседки инвестируют в сад), обеспечивающий всем трем участницам более высокие выигрыши 5. Хотя каждой из них было бы выгодно поучаствовать в создании сада, ни у кого из них нет индивидуального стимула для этого. В итоге такие сады либо вообще не сажают, либо делают это за счет налоговых поступлений, поскольку городская администрация может взыскать с жителей города такой налог. В главе 11 мы рассмотрим другие дилеммы коллективного действия и изучим некоторые методы их решения.
Равновесие Нэша в игре «уличный сад» можно также найти посредством анализа наилучших ответов, как показано на рис. 4.9. Так как доминирующая стратегия каждой участницы игры — «не вносить вклад», все наилучшие ответы Эмили находятся в ее строке «не вносить вклад», Нины — в ее колонке «не вносить вклад», а Талии — на ее странице «не вносить вклад». Ячейка в правом нижнем углу содержит три наилучших ответа, а значит, это и есть равновесие Нэша.
Рис. 4.9. Анализ наилучших ответов в игре «уличный сад»
6. Множество равновесий в чистых стратегиях
В каждой из игр, рассмотренных в предыдущих разделах, было единственное равновесие Нэша в чистых стратегиях. Однако в целом в играх необязательно должно быть единственное равновесие Нэша. Мы проиллюстрируем этот результат посредством класса игр, имеющих много областей применения, который можно обозначить как координационные игры. У их участников есть общие интересы (хотя и не всегда полностью совпадающие), но поскольку игроки действуют независимо друг от друга (в силу характера некооперативных игр), координация действий, необходимых для достижения общего предпочтительного исхода, проблематична.
А. Встретятся ли Гарри и Салли? Чистая координация
Для того чтобы проиллюстрировать эту идею, давайте представим себе двух студентов-старшекурсников, встретившихся в университетской библиотеке[50]. Они понравились друг другу и хотели бы продолжить общение, но им нужно идти в разные аудитории на лекции. Гарри и Салли договариваются вместе выпить кофе после занятий, которые заканчиваются в 16:30. Во время лекций оба осознают, что из-за волнения забыли договориться о месте встречи. Существует два возможных варианта: Starbucks и Local Latte. К сожалению, эти кафе расположены на противоположных концах большого кампуса, поэтому оказаться в обоих примерно в одно и то же время невозможно. Кроме того, Гарри и Салли не обменялись телефонными номерами, из-за чего не могут отправить друг другу сообщения. Что же нужно сделать каждому из них?
На рис. 4.10 эта ситуация представлена в виде игры с матрицей выигрышей. У каждого игрока два варианта выбора: Starbucks и Local Latte. Выигрыш для каждого равен 1, если они встретятся, и 0, если нет. Анализ наилучших ответов позволяет быстро определить, что в игре два равновесия Нэша: одно — при котором Салли и Гарри выберут Starbucks, и второе — при котором они выберут Local Latte. Для обоих важно достичь одного из этих равновесий, причем какого — не играет роли, поскольку оба равновесия обеспечивают одинаковые выигрыши. Главное, чтобы они скоординированно выбрали одно и то же действие, неважно какое. Именно поэтому такую игру называют игрой с чистой координацией.
Рис. 4.10. Чистая координация
Но смогут ли Гарри и Салли успешно скоординировать свои действия? Или в конечном счете они окажутся в разных кафе и каждый будет думать, что другой его подвел? Увы, такой риск существует. Гарри может решить, что Салли отправится в Starbucks, потому что она что-то говорила о занятиях, которые проходят на той стороне кампуса, где расположен Starbucks. Но у Салли может быть противоположное убеждение относительно того, что сделает Гарри. При наличии множества равновесий Нэша игрокам при выборе одного из них необходим какой-то способ скоординировать свои убеждения или ожидания в отношении действий друг друга.
Эта ситуация аналогична тому, что произошло с героями истории «Какая шина?», рассказанной в главе 1, где мы обозначили метод координации термином «фокальная точка». В данном контексте одно из двух кафе может быть широко известно как место встречи студентов. Однако недостаточно, чтобы Гарри просто об этом знал. Он должен знать, что Салли знает, и что она знает, что он знает, и т. д. Иными словами, их ожидания должны сходиться в фокальной точке. В противном случае Гарри может сомневаться в том, куда пойдет Салли, поскольку он не знает, что она думает о том, куда пойдет он. Подобные сомнения могут возникнуть на третьем, или четвертом, или еще более высоком уровне размышлений о размышлениях[51].
Когда один из нас (Диксит) задал этот вопрос своим студентам, большинство первокурсников выбрали Starbucks, а старшекурсники — местное кафе в студенческом центре университетского городка. Такой расклад закономерен: первокурсники, которые прожили в кампусе совсем немного времени, фокусируют свои ожидания на всем известной национальной сети кафе, тогда как старшекурсники знают местное кафе, ставшее для них самым лучшим местом встречи, и считают, что их друзья придерживаются аналогичного мнения.
Если бы одно кафе было оформлено в оранжевых тонах, а другое — в багровых, то в Принстоне первое кафе служило бы в качестве фокальной точки, поскольку оранжевый — это цвет Принстонского университета, тогда как в Гарварде по той же причине фокальной точкой было бы кафе с багровым декором. Если один человек — студент Принстона, а другой — Гарварда, они могут вообще не встретиться: либо потому, что каждый из них считает свой цвет более приоритетным, либо по той причине, что каждый думает, что другой не проявит гибкость и не пойдет на компромисс. В более общем случае способность участников координационных игр найти фокальную точку зависит от наличия такой общеизвестной точки контакта, будь то историческая, культурная или языковая.
Б. Встретятся ли Гарри и Салли? И где? Игра в доверие
Теперь давайте немного изменим выигрыши в игре. Поведение студентов старших курсов позволяет предположить, что нашей паре может быть не совсем безразлично, какое именно кафе выбирать. В одном заведении может быть лучше кофе, в другом — атмосфера. Или они могут предпочесть менее популярное место встречи студентов, чтобы избежать возможного столкновения с бывшими парнями или девушками. Предположим, Гарри и Салли остановятся на Local Latte; следовательно, выигрыш каждого из них составит 2, если они встретятся в этом кафе, и 1, если они встретятся в Starbucks. Новая матрица выигрышей показана на рис. 4.11.
Рис. 4.11. Игра в доверие
Здесь снова присутствуют два равновесия Нэша. Однако в данной версии игры каждый предпочитает равновесие, при котором оба выбирают Local Latte. К сожалению, тот факт, что обоим участникам нравится такой исход игры, его не гарантирует. Прежде всего (как и всегда в нашем анализе) выигрыши должны быть элементом общего знания, оба игрока должны знать всю матрицу выигрышей, оба должны знать, что оба знают, и т. д. Знание игры во всех подробностях было бы возможным, если бы Гарри и Салли обсудили ситуацию и сошлись во мнениях по поводу преимуществ двух кафе, но просто забыли договориться о том, что встретятся в Local Latte. Но даже в этом случае Гарри мог бы подумать, что у Салли есть какая-то иная причина для выбора Starbucks, или он может подумать, что она подумает, что он подумает, и т. д. Без истинной сходимости ожиданий в отношении действий участники игры могут выбрать худшее равновесие или, что еще печальнее, вообще не скоординировать свои действия, и тогда каждый получит нулевой выигрыш.
Повторим еще раз: участники игры, представленной на рис. 4.11, могут получить предпочтительный равновесный исход, только если каждый из них достаточно убежден в том, что другой выберет надлежащее действие. По этой причине игры такого типа называются играми в доверие[52].
Во многих подобных реальных жизненных ситуациях обрести доверие довольно легко при наличии даже минимальной коммуникации между игроками. Их интересы полностью совпадают: если один скажет «Я пойду в Local Latte», у другого нет оснований сомневаться в истинности этого утверждения, поэтому он пойдет туда же, чтобы получить предпочтительный для обоих исход. Именно поэтому нам пришлось придумать историю с двумя студентами, которые посещают разные занятия и не имеют возможности общаться друг с другом. Если интересы игроков вступают в конфликт, правдивая коммуникация становится более проблематичной. Мы углубимся в эту проблему, когда будем рассматривать стратегическое манипулирование информацией в играх в главе 8.
В более многочисленных группах коммуникацию можно обеспечить посредством планирования встреч или размещения объявлений. Но эти способы эффективны только в случае, когда все знают, что остальные обращают на них внимание, поскольку для успешной координации действий необходимо, чтобы требуемый исход был фокальной точкой. Ожидания игроков должны сходиться в этой точке: все должны знать, что каждый знает, что … каждый делает этот выбор. Именно эту функцию выполняют многие общественные институты и договоренности. Собрания, во время которых присутствующие рассаживаются по кругу и смотрят в его центр, позволяют каждому видеть, что делают остальные. Рекламные объявления во время Суперкубка, особенно когда их показывают накануне матчей в качестве основной приманки, убеждают каждого зрителя, что многие тоже их смотрят. Это делает такие рекламные объявления особенно привлекательными для компаний, выпускающих продукты, которые становятся более желанными для каждого отдельного покупателя, если их покупают многие люди; к данной категории относится продукция компьютерной отрасли, телекоммуникаций и интернет-индустрии[53].
В. Встретятся ли Гарри и Салли? И где? Битва полов
Теперь давайте еще немного усложним игру с выбором кафе. Оба игрока хотят встретиться, но предпочитают разные кафе. Таким образом, Гарри может получить выигрыш 2, а Салли — 1, если они встретятся в Starbucks, и наоборот, если встреча состоится в Local Latte. Матрица выигрышей этой игры показана на рис. 4.12.
Рис. 4.12. Битва полов
Такая игра называется битвой полов. Название происходит от истории, которую специалисты по теории игр придумали для иллюстрации этой структуры выигрышей в сексистских 1950-х годах. В этой истории мужу и жене предстоял выбор между походом на боксерский матч и балет, причем (предположительно, по эволюционно-генетическим причинам) муж должен был выбрать бокс, а жена — балет. Это название прижилось, поэтому мы будем его использовать, хотя наш пример (в котором у любого из игроков вполне могла быть причина предпочесть любое из двух кафе, не имеющая отношения к полу) ясно дает понять, что такая игра необязательно должна иметь сексистский подтекст.
Как будут развиваться события в этой игре? В ней по-прежнему присутствуют два равновесия Нэша. Если Гарри убежден, что Салли выберет Starbucks, ему лучше сделать то же самое, и наоборот. По тем же причинам Local Latte также является равновесием Нэша. Для того чтобы достичь любого из этих равновесий и избежать исходов, при которых игроки отправятся в разные кафе, им необходима фокальная точка, или сходимость ожиданий, точно так же как в игре с чистыми стратегиями и игре в доверие. Однако в битве полов риск неудачи с координацией действий выше. Игроки с самого начала находятся в достаточно симметричных ситуациях, однако каждое из двух равновесий Нэша обеспечивает им асимметричные выигрыши, а их предпочтения в отношении двух возможных исходов вступают в противоречие: Гарри ратует за встречу в Starbucks, а Салли — в Local Latte. Они должны найти способ нарушить эту симметрию.
В стремлении достичь предпочтительного для себя равновесия каждый игрок может прибегнуть к жестким действиям и стратегии, ведущей к лучшему равновесию. В главе 9 мы рассмотрим в деталях такие инструменты ведения игры, как стратегические ходы, которые участники подобных игр могут предпринять для обеспечения предпочтительного исхода. Или каждый игрок попытается угодить другому, что может обусловить досадную ситуацию, когда Гарри отправится в Local Latte, чтобы порадовать Салли, но обнаружит, что она решила доставить удовольствие ему и пошла в Starbucks (очень похоже на то, как герои рассказа О’Генри «Дары волхвов» выбирали подарки друг другу на Рождество). В качестве альтернативы в случае повторяющейся игры успешная координация действий может стать предметом переговоров и поддерживаться как равновесие. Например, Гарри и Салли могут договориться встречаться то в одном, то в другом кафе. В главе 10 мы проанализируем такое неявное сотрудничество в повторяющихся играх в контексте дилеммы заключенных.
Г. Встретятся ли Джеймс и Дин? Игра в труса
Наш последний пример в этом разделе касается координационной игры несколько иного типа. В ней игроки стремятся предотвратить (или не выбирать) одни и те же действия. Кроме того, последствия неудачной попытки координации в подобных играх куда более разрушительны, чем в других играх.
Эта история взята из игры, в которую якобы играли американские подростки в 1950-х годах. Двое подростков садятся в полночь в свои автомобили на противоположных концах улицы какого-нибудь американского городка и мчатся навстречу друг другу. Тот, кто свернет в сторону, чтобы избежать столкновения, становится «трусом», а тот, кто продолжает ехать прямо, считается победителем. Если оба подростка придерживаются прямого курса, происходит столкновение, в котором оба автомобиля получают повреждения, а оба водителя — травмы[54].
Выигрыши «труса» зависят от того, насколько негативным для себя игрок считает «плохой» исход (в данном случае это травмы водителя и повреждения автомобиля) по сравнению с перспективой прослыть трусом. Если слова задевают меньше, чем хруст металла, то таблица разумных выигрышей в варианте игры в труса 1950-х годов выглядит так, как на рис. 4.13. Каждый игрок больше всего хочет стать победителем, а не трусом, и оба одинаково не хотят столкновения автомобилей. Между этими двумя крайностями для вас предпочтительна ситуация, чтобы ваш соперник оказался трусом в игре с вами (сохранить лицо), чем самому стать трусом.
Рис. 4.13. Игра в труса
У этой истории есть четыре важных свойства, которые определяют игру в труса. Во-первых, у каждого игрока есть одна «жесткая» и одна «слабая» стратегия. Во-вторых, в игре присутствуют два равновесия Нэша в чистых стратегиях (иными словами, исходы игры, при которых один из игроков становится трусом или придерживается слабой стратегии). В-третьих, каждый игрок выбирает именно то равновесие, при котором другой игрок предпочитает стать трусом или применяет слабую стратегию. В-четвертых, когда оба придерживаются жесткой стратегии, оба получают очень плохие выигрыши. В играх такого типа реальная игра сводится к проверке ее участниками способов достижения предпочтительного для себя равновесия.
Мы вернулись к ситуации, подобной рассмотренной при обсуждении игры «битва полов». Большинство происходящих в реальной жизни игр в труса предполагают еще более ожесточенные битвы, чем битва полов: преимущества от победы повышаются, так же как и цена поражения, поэтому все проблемы, связанные с конфликтом интересов и асимметрией между игроками, усугубляются. Каждый игрок стремится повлиять на исход такой игры. Может сложиться ситуация, когда один игрок попытается создать впечатление жесткости, которое видели бы все, чтобы запугать соперников[55]. Еще один вариант — найти какой-либо другой способ убедить соперника в том, что вы не сдадитесь, взяв на себя явное и непреложное обязательство ехать прямо. (В главе 9 мы поговорим о том, как делать ходы с обязательствами.) Кроме того, оба игрока могут захотеть предотвратить неблагоприятный исход (столкновение), если это вообще возможно.
Как и в битве полов, если игра повторяется, молчаливая координация — лучший путь к решению игры. Иначе говоря, если бы подростки играли в труса в полночь каждого воскресенья, при выборе равновесных стратегий они знали бы, что у игры есть и прошлое, и будущее. В подобной ситуации они могли бы выбрать такой логически правильный путь, как чередование равновесий, и по очереди бы становились победителями раз в две недели. (Однако если кто-то узнает об этой сделке, пострадает репутация обоих игроков.)
Существует еще один, последний, момент, касающийся координационных игр, о котором следует упомянуть. Концепция равновесия Нэша требует от каждого игрока наличия правильных убеждений в отношении выбора стратегии другим игроком. При поиске равновесий Нэша в чистых стратегиях эта концепция предписывает, чтобы каждый игрок был уверен в выборе другого игрока. Но наш анализ координационных игр показывает, что в размышлениях о выборе других игроков в таких играх присутствует элемент стратегической неопределенности. Как мы можем включить ее в анализ? В главе 7 мы вводим понятие смешанной стратегии, в которой фактический выбор делается случайным образом из доступных действий. Такой подход распространяет концепцию равновесия Нэша на ситуации, когда игроки могут быть не уверены в действиях друг друга.
7. Отсутствие равновесия в чистых стратегиях
В каждой из рассмотренных выше игр было минимум одно равновесие Нэша в чистых стратегиях. В некоторых играх, таких как в разделе 6, было больше одного равновесия, тогда как в предыдущих разделах представлены игры ровно с одним. К сожалению, не все игры, анализируемые нами в процессе изучения стратегии и теории игр, будут иметь легко поддающиеся определению исходы, при которых игроки всегда выбирают одно конкретное действие в качестве равновесной стратегии. В данном разделе мы проанализируем игры, в которых отсутствует равновесие Нэша в чистых стратегиях и ни один из игроков не выбирает неизменно одну и ту же стратегию в качестве своего равновесного действия.
Простой пример такой игры — розыгрыш одного очка в теннисном матче. Представьте себе матч между двумя лучшими теннисистками всех времен — Мартиной Навратиловой и Крис Эверт[56]. Навратилова у сетки только что отправила мяч в сторону Эверт на задней линии, а Эверт вот-вот сделает обводящий удар. Она может попытаться послать мяч либо по линии (ПЛ, сильный прямой удар), либо по диагонали (ПД, более мягкий удар из одного угла корта в другой). Навратилова точно так же должна подготовиться, чтобы прикрыть какую-то одну сторону. Каждая участница игры знает, что не должна давать сопернице никаких подсказок в отношении запланированного действия, понимая, что эта информация будет использована против нее. Навратилова попыталась бы прикрыть ту сторону, в которую Эверт планирует послать мяч, а Эверт сделала бы удар в ту сторону, которую Навратилова не собирается прикрывать. Обе теннисистки должны выполнить соответствующее действие за долю секунды, и обе умеют хорошо скрывать свои намерения до последнего момента. Следовательно, их действия фактически одновременны, поэтому мы можем проанализировать этот розыгрыш очка как игру с одновременными ходами с двумя участниками.
Выигрыши в игре с розыгрышем очков в теннисе соответствуют относительному количеству случаев, когда игрок выигрывает очко в той или иной комбинации обводящего удара и прикрывающей игры. Учитывая, что обводящий удар по линии сильнее удара по диагонали и что Эверт с большей вероятностью выиграет, если Навратилова попытается прикрыть не ту сторону корта, мы можем сформировать приемлемую систему выигрышей. Предположим, Эверт добьется успеха в 80 % обводящих ударов по линии, если Навратилова прикроет корт на случай удара по диагонали, и только в 50 % обводящих ударов по линии, если Навратилова прикроет корт на случай удара по линии. Точно так же Эверт добьется успеха в 90 % ударов по диагонали, если Навратилова прикроет корт на случай удара по линии. Эта доля результативных ударов выше, чем при попытке Навратиловой прикрыть корт на случай удара по диагонали — тогда Эверт выиграет очки только в 20 % случаев.
Очевидно, что доля побед Навратиловой в игре равна разности между 100 % и долей побед Эверт. Следовательно, это игра с нулевой суммой (хотя формально сумма выигрышей двух участниц составляет 100), поэтому мы можем представить всю необходимую информацию в таблице выигрышей, отобразив в каждой ячейке только выигрыш Эверт. На рис. 4.14 показана таблица выигрышей и доля побед Эверт в розыгрышах очков против Навратиловой в каждой из четырех возможных комбинаций их выбора стратегий.
Рис. 4.14. Отсутствие равновесия в чистых стратегиях
Правила решения игр с одновременными ходами говорят нам о том, что сначала следует попытаться найти доминирующие или доминируемые стратегии, а затем использовать анализ наилучшего ответа для поиска равновесия Нэша. Это полезное упражнение позволяет убедиться, что в данной игре нет доминирующих стратегий. Выполнив анализ наилучших ответов, мы приходим к выводу, что лучший ответ Эверт на стратегию ПЛ — стратегия ПД, а на стратегию ПД — стратегия ПЛ. Напротив, наилучший ответ Навратиловой на стратегию ПЛ — стратегия ПЛ, а на стратегию ПД — стратегия ПД. Ни в одной ячейке таблицы выигрышей равновесия Нэша нет, поскольку каждая теннисистка упорно пытается изменить свою стратегию. Например, начав с верхней левой ячейки таблицы, мы обнаружим, что Эверт предпочитает перейти от стратегии ПЛ к стратегии ПД, увеличив свой выигрыш с 50 до 90 процентов. Однако в левой нижней ячейке таблицы мы видим, что Навратилова считает разумным переключиться со стратегии ПЛ на ПД, увеличив свой выигрыш с 10 до 80 процентов. Как вы можете убедиться сами, аналогичным образом Эверт стремится изменить стратегии в нижней левой ячейке, а Навратилова — в верхней правой. В каждой ячейке таблицы одна участница неизменно старается изменить игру, поэтому мы можем бесконечно перемещаться в таблице по кругу в поисках равновесия.
Отсутствие равновесия Нэша в этой и других подобных играх содержит один значимый сигнал: в играх такого типа важно не то, что игроки должны сделать, а то, чего они не должны делать. В частности, каждая участница игры не должна постоянно или систематически выбирать один и тот же удар, оказываясь в такой ситуации. Если любая из теннисисток будет придерживаться определенной линии поведения, другая может воспользоваться этим. (Например, если бы Эверт постоянно делала обводящий удар по диагонали, Навратилова бы знала, что ей каждый раз необходимо прикрывать соответствующую сторону корта, и тем самым снизила бы шансы Эверт на успешное выполнение удара по диагонали.) Самое разумное, что могут сделать участницы игры, — действовать несколько бессистемно, рассчитывая на то, что элемент неожиданности поможет победить соперницу. Асимметричный подход подразумевает выбор каждой стратегии в определенном количестве случаев. (Эверт следует использовать свой более слабый удар достаточно часто, чтобы Навратилова не могла предугадать, какой удар будет направлен в ее сторону. Однако она не должна использовать удары двух типов по установленной схеме, поскольку это также приведет к потере элемента неожиданности.) Подход, при котором игроки выбирают действия случайным образом, известный как смешивание стратегий, подробно рассматривается в главе 7. Игра, представленная на рис. 4.14, может не иметь равновесия в чистых стратегиях, но ее все же можно решить посредством поиска равновесия в смешанных стратегиях, что мы и сделаем в разделе 1 главы 7.
Резюме
Участники игр с одновременными ходами выбирают стратегии, не зная о выборе других игроков. Такие игры можно изобразить в виде таблицы игры, в ячейках которой отображены выигрыши каждого игрока, а ее размерность равна количеству игроков. Игры с нулевой суммой с двумя участниками можно представить в сокращенном виде, отобразив в каждой ячейке таблицы игры только выигрыши одного игрока.
Равновесие Нэша — концепция, используемая для решения игр с одновременными ходами. Такое равновесие состоит из совокупности стратегий (по одной на каждого игрока), где каждый игрок выбрал свой лучший ответ на выбор другого игрока. Кроме того, равновесие Нэша можно трактовать как набор стратегий, при котором у каждого игрока есть правильные убеждения относительно стратегий других игроков, а определенные стратегии являются лучшими для каждого игрока с учетом этих убеждений. Равновесия Нэша можно найти посредством поиска доминирующих стратегий, последовательного исключения доминируемых стратегий или анализа наилучших ответов.
Существует масса классов игр с одновременными ходами. Игра «дилемма заключенных» встречается во многих контекстах. В координационных играх, таких как игра в доверие, игра в труса и битва полов, — множество равновесий, и решение этих игр требует от их участников координации действий. Если в игре отсутствует равновесие в чистых стратегиях, мы должны искать его в смешанных стратегиях, анализ которых представлен в главе 7.
S1. Найдите все равновесия Нэша в чистых стратегиях для представленных ниже игр. Сначала проверьте таблицу игры на наличие доминирующих стратегий. Если таковых нет, решите игру посредством итеративного исключения доминируемых стратегий. Объясните логику своих рассуждений.
a)
b)
c)
d)
S2. Для каждой из четырех игр, представленных в упражнении S1, определите, это игра с нулевой или с ненулевой суммой. Объясните логику своих рассуждений.
S3. Метод минимакса — еще один значимый способ решения игр с нулевой суммой, разработанный задолго до того, как Нэш сформулировал концепцию равновесия в играх с ненулевой суммой. Для того чтобы его применить, необходимо исходить из предположения, что независимо от того, какую стратегию выберет игрок, его соперник сделает такой выбор, который обеспечит этому игроку худший выигрыш от данной стратегии. В случае каждой игры с нулевой суммой, найденной в упражнении S2, используйте метод минимакса для поиска равновесных стратегий игры, выполнив следующие действия:
a) Для каждой стратегии, соответствующей строке таблицы, запишите минимальный выигрыш Ровены (худшее, что может с ней сделать Колин в данном случае). Для каждой стратегии, отображенной в столбце таблицы, запишите минимальный выигрыш Колина (худшее, что может с ним сделать Ровена в данном случае).
b) Для каждого игрока определите стратегию (или стратегии), которая обеспечивает ему лучший из этих худших выигрышей. Это и есть стратегия минимакса каждого игрока.
(Поскольку в данном случае речь идет об игре с нулевой суммой, наилучшие ответы игроков действительно подразумевают сведение выигрышей друг друга к минимуму, а значит, эти стратегии минимакса и есть равновесиями Нэша. Джон фон Нейман доказал существование минимаксного равновесия в играх с нулевой суммой в 1928 году, за двадцать лет до того, как Нэш обобщил эту теорию.)
S4. Найдите все равновесия Нэша в чистых стратегиях в следующих играх с ненулевой суммой. Опишите шаги, которые вы при этом предприняли.
a)
b)
c)
d)
S5. Проанализируйте следующую таблицу игры:
a) Есть ли доминирующая стратегия у Ровены либо у Колина? Объясните, почему есть или нет.
b) Используйте метод итеративного исключения доминируемых стратегий, чтобы как можно больше уменьшить игру. Опишите порядок выполнения такого исключения стратегий и представьте урезанную форму игры.
c) Разрешима ли эта игра по доминированию? Объясните, почему да или нет.
d) Найдите в ней равновесие (или равновесия) Нэша.
S6. «Если у игрока есть доминирующая стратегия в игре с одновременными ходами, значит, он наверняка получит самый лучший исход». Это утверждение истинно или ложно? Обоснуйте свой вывод и приведите пример игры, иллюстрирующий ваш ответ.
S7. Пожилой даме нужна помощь, чтобы перейти улицу. Для этого достаточно одного человека; не имеет смысла привлекать больше людей. Мы с вами находимся поблизости и можем помочь, причем одновременно должны решить, стоит ли это делать. Каждый из нас получит удовольствие с выигрышем 3 единицы, если все разрешится благополучно (независимо от того, кто ее переведет). Однако именно тому, кто непосредственно поможет даме, это обойдется в 1 единицу — такова ценность нашего времени, потраченного на оказание помощи. Если никто из игроков не оказывает помощь, выигрыш каждого будет равен нулю. Сформулируйте эту ситуацию в виде игры. Составьте таблицу выигрышей и найдите равновесия Нэша в чистых стратегиях.
S8. В университете решают, что построить — новую лабораторию или новый театр в кампусе. Факультет естественных наук предпочел бы новую лабораторию, а гуманитарных ратует за театр. Однако финансирование проекта (вне зависимости от того, каким он будет) возможно только в случае единодушной поддержки всего преподавательского состава университета. При возникновении разногласий ни один проект не получит дальнейшего продвижения и оба факультета останутся без нового здания и с наихудшим выигрышем. Собрания двух отдельных групп преподавателей, на которых решается вопрос о поддержке проекта, проходят одновременно, а выигрыши представлены в следующей таблице:
a) Каковы равновесия Нэша в чистых стратегиях в этой игре?
b) Какая из игр, представленных в данной главе, больше всего напоминает эту игру? Объясните логику своих рассуждений.
S9. Предположим, два участника игрового шоу, Алекс и Боб, каждый по отдельности выбирают двери с номерами 1, 2, 3. Оба игрока получают призы, если их выбор совпадает, как показано в следующей таблице:
a) Каковы равновесия Нэша в этой игре? Какое из них (при его наличии) скорее всего приведет к (фокальному) исходу игры? Обоснуйте свой вывод.
b) Рассмотрите несколько измененную игру, в которой варианты выбора — снова просто числа, но две ячейки таблицы с выигрышами 15, 15 теперь содержат выигрыши 25, 25. Какой ожидаемый (средний) выигрыш каждого игрока, если каждый из них подбросит монету, чтобы решить, выбрать вариант 2 или 3? Лучше ли это фокусировки на том, чтобы оба выбрали 1 в качестве фокального равновесия? Как вам следует учитывать риск того, что Алекс может сделать одно, а Боб — другое?
S10. У Марты три сына: Артуро, Бернардо и Карлос. Она находит разбитую лампу посреди гостиной и понимает, что это сделал кто-то из сыновей. На самом деле виновник произошедшего Карлос, но Марта об этом не знает. Она заинтересована скорее в том, чтобы выяснить истину, а не наказать ребенка, поэтому предлагает сыновьям сыграть в следующую игру.
Каждый из них напишет на листе бумаги свое имя, а также слова: «Да, это я разбил лампу» либо «Нет, я не разбивал лампу». Если хотя бы один ребенок признается, что разбил лампу, Марта даст по 2 доллара (обычную сумму карманных денег) каждому, кто скажет, что разбил лампу, и 5 долларов тому, кто будет утверждать, что не делал этого. Если все три сына откажутся сознаваться, ни один из них не получит карманных денег (то есть каждый получит 0 долларов).
a) Составьте таблицу игры. Пусть Артуро соответствует строка таблицы, Бернардо — столбец, а Карлосу — страница.
b) Найдите все равновесия Нэша в этой игре.
c) В этой игре множество равновесий Нэша. Какое из них вы назвали бы фокальной точкой?
S11. Рассмотрите игру, в которой на кону стоит приз в размере 30 долларов. В ней три участника — Ларри, Керли и Мо. Каждый из них может купить (или нет) билет стоимостью 15 или 30 долларов. Игроки делают выбор одновременно и независимо друг от друга. Затем, собрав информацию о решениях игроков по поводу покупки билетов, организатор игры присуждает приз. Если никто не купит билет, приз не присуждается. В противном случае приз вручается тому, кто купил самый дорогой билет, если такой человек всего один, и делится поровну между двумя или тремя игроками, если они купили самые дорогие билеты по одной цене. Представьте эту игру в стратегической форме, включив в нее Ларри в качестве игрока, которому соответствуют строки, Керли — столбцы, а Мо — страницы. Найдите все равновесия Нэша в чистых стратегиях.
S12. Анна и Брюс намерены взять напрокат фильм, но не могут решить, какой именно. Анна хочет комедию, в Брюс — драму. Они решают сделать выбор случайным образом, сыграв в игру «чет или нечет». На счет три каждый из них выбрасывает один или два пальца. Если сумма пальцев представляет собой четное число, побеждает Энн и они берут напрокат комедию, если нечетное, то выигрывает Брюс и они смотрят драму. Каждый игрок получает выигрыш 1 за победу и 0 за проигрыш в игре «чет или нечет».
a) Нарисуйте таблицу игры «чет или нечет».
b) Покажите, что в этой игре нет равновесия Нэша в чистых стратегиях.
S13. В фильме «Игры разума» Джон Нэш и трое его коллег по магистратуре, придя в бар, сталкиваются с дилеммой. В баре находятся четыре брюнетки и одна блондинка. Каждый молодой человек хочет подойти и привлечь внимание одной из девушек. Выигрыш каждого за блондинку составляет 10, за брюнетку — 5, а если кто-то вообще останется без девушки, то 0. Проблема в том, что, если сразу несколько парней подойдут к блондинке, она отвергнет их всех, после чего брюнетки тоже их отвергнут, поскольку не хотят быть вторыми в очереди. Таким образом, каждый игрок получит выигрыш 10 только в случае, если окажется единственным претендентом на внимание блондинки.
a) Сначала упростите ситуацию, заменив четырех парней двумя, и проанализируйте ее. (В баре две брюнетки и одна блондинка, но девушки просто реагируют на действия парней вышеописанным образом и не являются активными участницами игры.) Составьте таблицу выигрышей для этой игры и найдите все равновесия Нэша в чистых стратегиях, присутствующие в ней.
b) Теперь постройте трехмерную таблицу для случая, когда в игре участвуют три молодых человека (а также три брюнетки и одна блондинка, которые не являются активными игроками). Снова найдите в ней равновесия Нэша.
c) Не прибегая к таблице, назовите все равновесия Нэша для изначальной ситуации.
d) (дополнительное упражнение). Используйте результаты, полученные в пунктах а, b и c, чтобы обобщить анализ на ситуацию, когда в игре участвуют n молодых людей. Не пытайтесь строить n-мерную таблицу выигрышей, просто вычислите выигрыш одного игрока в случае, если k других игроков выберут блондинку и (n — k — 1) выберут брюнетку, при k = 0, 1… (n — 1). Может ли исход, указанный в фильме в качестве равновесия Нэша (когда все молодые люди подойдут к брюнеткам), быть действительно равновесием Нэша в данной игре?
Упражнения без решений
U1. Найдите все равновесия Нэша в чистых стратегиях для представленных ниже игр. Сначала проверьте таблицу игры на наличие доминирующих стратегий. Если таковых нет, решите игру посредством итеративного исключения доминируемых стратегий.
a)
b)
c)
b)
U2. Для каждой из четырех игр, представленных в упражнении U1, определите, это игра с нулевой или с ненулевой суммой. Объясните логику своих рассуждений.
U3. Как и в упражнении S3, используйте метод минимакса для поиска равновесий Нэша в играх с нулевой суммой, найденных в упражнении U2.
U4. Найдите все равновесия Нэша в чистых стратегиях в следующих играх. Опишите шаги, которые вы при этом предпринимали.
a)
b)
c)
b)
U5. Используйте метод последовательного исключения доминируемых стратегий для решения следующей игры. Опишите шаги, которые вы для этого предприняли. Покажите, что ваше решение представляет собой равновесие Нэша.
U6. Найдите все равновесия Нэша в чистых стратегиях для следующей игры. Опишите процесс, который вы при этом использовали. Объясните на примере данной игры, почему важно описывать равновесие с применением стратегий, выбранных игроками, а не только выигрышей, полученных в таком равновесии.
U7. Проанализируйте следующую таблицу игры:
a) Проставьте недостающие выигрыши в таблице таким образом, чтобы у Колина была доминирующая стратегия. Укажите, какая стратегия доминирующая, и объясните почему. (Обратите внимание: существует много в равной степени правильных ответов.)
b) Проставьте недостающие выигрыши в таблице таким образом, чтобы ни у одного игрока не было доминирующей стратегии, но при этом у каждого была доминируемая стратегия. Укажите, какие стратегии доминируемые, и объясните почему. (В этом случае тоже существует много в равной степени правильных ответов.)
U8.Битва в море Бисмарка (по названию моря в юго-западной части Тихого океана, отделяющего архипелаг Бисмарка от Папуа — Новой Гвинеи) представляла собой морское сражение между Соединенными Штатами и Японией во время Второй мировой войны. В 1943 году японский адмирал получил приказ провести конвой кораблей в Новую Гвинею. Ему предстояло сделать выбор между дождливым северным маршрутом и более солнечным южным, каждый из которых требовал трех дней плавания. Американцы знали об отплытии конвоя и хотели послать вслед за ним бомбардировщики, но им не было известно, по какому пути отправится конвой. Американцам пришлось послать самолеты-разведчики на поиски конвоя, но их хватало только на изучение одного маршрута за один раз. И американцам, и японцам приходилось принимать решения, не имея никакой информации о планах другой стороны.
Если бы конвой оказался на маршруте, который американцы исследовали первым, они сразу же послали бы туда бомбардировщики, в противном случае они потеряли бы день. Кроме того, плохая погода на северном маршруте тоже затрудняла бомбардировку. Если бы американцы изучили северный маршрут и сразу же обнаружили японцев, они могли бы рассчитывать только на два (из трех) благоприятных дня для бомбардировки; если бы при изучении северного маршрута они обнаружили, что японцы ушли на юг, они тоже могли бы рассчитывать на два дня бомбардировки. Если бы американцы решили сначала исследовать южный маршрут, они могли бы рассчитывать на три полных благоприятных дня для бомбардировки, если бы обнаружили японцев сразу же, и только на один день, если бы увидели, что японцы предпочли северный маршрут.
a) Представьте эту игру в виде таблицы игры.
b) Определите в ней все доминирующие стратегии и вычислите равновесие Нэша.
U9. Двух игроков, Джека и Джилл, поместили в разные комнаты. Затем каждому из них объяснили правила игры. Каждый должен выбрать одну из шести букв: G, K, L, Q, R и W. Если случится так, что оба выберут одну и ту же букву, они получат призы по следующей схеме.
При выборе разных букв каждый игрок получит 0. Всю эту схему доводят до сведения игроков, и обоим говорят, что они оба знают эту схему.
a) Составьте таблицу этой игры. Каковы равновесия Нэша в чистых стратегиях?
b) Может ли одно из равновесий быть фокальной точкой? Какое? Почему?
U10. Три подруги (Джулия, Кристин и Лариса) независимо друг от друга идут покупать платья для выпускного бала. В магазине каждая девушка видит только три платья, которые достойны внимания: черное, бледно-лиловое и желтое. Более того, каждая девушка готова утверждать, что двух ее подруг тоже заинтересовал бы именно этот набор платьев, поскольку у всех троих примерно одинаковые вкусы.
Каждая девушка хотела бы надеть на выпускной бал единственное в своем роде платье, поэтому для нее полезность платья равна 0, если она купит одинаковое платье с кем-то из подруг. Все трое знают, что Джулия однозначно отдаст предпочтение черному перед бледно-лиловым и желтым цветом, поэтому она получила бы полезность 3, если бы была единственной девушкой в черном платье, и полезность 1, если бы только у нее было платье бледно-лилового или желтого цвета. Точно так же все трое знают, что Кристин нравится бледно-лиловый цвет и только во вторую очередь желтый, поэтому ее полезность составила бы 3, если бы только она надела бледно-лиловое платье, 2 — желтое и 1 — черное. И наконец, всем известно, что Лариса обожает желтый, а затем черный, поэтому она получила бы 3, если бы выбрала желтое платье, 2 — черное и 1 — бледно-лиловое.
a) Составьте таблицу для этой игры с участием трех игроков. Пусть Джулии соответствуют строки таблицы, Кристин — столбцы, Ларисе — страницы.
b) Определите все доминируемые стратегии в игре или объясните причину их отсутствия.
c) Каковы равновесия Нэша в чистых стратегиях в этой игре?
U11. Брюс, Колин и Дэвид собираются в доме Дэвида в пятницу вечером, чтобы поиграть в «Монополию». Все трое любят есть суши во время игры. По предыдущему опыту они знают, что двух порций суши вполне достаточно, чтобы утолить голод. Если они закажут меньше двух порций, то останутся голодными и не получат удовольствия от вечера, заказывать больше двух порций тоже не имеет смысла, поскольку они столько не съедят и третья порция испортится. Их любимый ресторан Fishes in the Raw упаковывает суши в такие большие контейнеры, что один человек может купить максимум одну порцию. Ресторан Fishes in the Raw предлагает суши навынос, но, к сожалению, не осуществляет доставку.
Предположим, полезность достаточного количества суши составляет для каждого игрока 20 долларов, а недостаточного — 0 долларов. Каждому игроку, который забирает заказ суши, это обходится в 10 долларов.
К сожалению, друзья забыли договориться о том, кто будет покупать суши в эту пятницу, и у них нет мобильных телефонов, поэтому они должны независимо друг от друга решить, покупать суши (П) или нет (Н).
a) Опишите эту игру в стратегической форме.
b) Найдите все равновесия Нэша в чистых стратегиях.
c) Какое равновесие вы назвали бы фокальной точкой? Объясните логику своих рассуждений.
U12. Роксанна, Сара и Тед очень любят печенье, но в упаковке осталось только одно. Никто не хочет делить его на части, поэтому Сара предлагает сыграть в следующий вариант игры «чет или нечет» (см. упражнение S12), для того чтобы определить, кто съест печенье. На счет три каждый игрок выбрасывает один или два пальца, затем игроки их суммируют и делят сумму на 3. Если остаток 0, печенье достается Роксанне, если 1, то Саре, а если 2, то Теду. Каждый из игроков получает выигрыш 1, если победит (и съест печенье), и 0 в противном случае.
a) Представьте эту игру с тремя участниками в форме таблицы, где Роксанне соответствуют строки, Саре — столбцы, Теду — страницы.
b) Найдите все равновесия Нэша в чистых стратегиях. Можно ли назвать эту игру справедливым способом поделить печенье? Объясните, почему да или нет.
U13 (дополнительное упражнение). Постройте матрицу выигрышей для игры с двумя участниками, удовлетворяющей следующим требованиям. Во-первых, у каждого игрока должно быть три стратегии. Во-вторых, в игре не должны отсутствовать доминирующие стратегии. В-третьих, игра не должна быть разрешима методом минимакса. В-четвертых, в игре должно быть ровно два равновесия Нэша в чистых стратегиях. Составьте матрицу игры, а затем продемонстрируйте, что все перечисленные выше условия соблюдены.
Глава 5. Игры с одновременными ходами: непрерывные стратегии, анализ и обсуждения
* * *
В главе 4 обсуждение фокусировалось на играх с одновременными ходами, в которых каждый игрок мог делать выбор из дискретного множества действий. К дискретным стратегическим играм данного типа относятся спортивные соревнования, позволяющие использовать только небольшое количество вариантов игры в заданной ситуации, скажем пенальти в футболе, когда игрок может выбирать, куда послать мяч: высоко или низко, в угол или в центр ворот. Другие примеры включают в себя координационные игры и игры под общим названием «дилемма заключенных», в которых в распоряжении игроков только две или три стратегии. Такие игры можно проанализировать с помощью таблицы игры, по крайней мере в ситуациях с приемлемым количеством участников и доступных действий.
Однако многие игры с одновременными ходами отличаются от тех, которые мы рассматривали до сих пор, тем, что их участникам приходится выбирать стратегии из широкого диапазона возможных вариантов. Игры, в которых производители выбирают цены на свои продукты, благотворители — суммы пожертвований, а подрядчики — размер заявки на участие в проекте, — все это примеры игр, в которых участники имеют практически бесконечное множество вариантов выбора. Сугубо формально цены и другие суммы в долларах все же можно выразить в минимальных единицах, таких как цент, а значит, на самом деле речь идет о конечном и дискретном множестве стратегий ценообразования. Однако на практике эта единица настолько мала, что, если бы мы допустили подобную дискретность, каждому игроку пришлось бы иметь дело с таким большим количеством дискретных стратегий, что это сделало бы таблицу игры нереально огромной. Поэтому гораздо проще и эффективнее рассматривать эти варианты выбора как непрерывно меняющиеся действительные числа. Когда у игроков столь широкий диапазон доступных действий, таблицы игр становятся фактически бесполезны в качестве инструмента анализа, оказываясь слишком громоздкими для практического применения. Для таких игр нужен иной метод решения. В первой части данной главы мы представим аналитические инструменты для решения игр с непрерывными стратегиями.
В этой главе также рассматриваются некоторые более широкие вопросы, связанные с поведением в играх с одновременными ходами и концепцией равновесия Нэша. В частности, эмпирические данные о ведении игр в соответствии с равновесием Нэша, собранные в ходе как лабораторных экспериментов, так и наблюдений за реальными жизненными ситуациями. Кроме того, представлен ряд теоретических критических замечаний в отношении концепции равновесия Нэша, а также приведены аргументы против подобной критики. Еще вы увидите, что прогнозы, составленные на основе теории игр, во многих случаях целесообразно (с некоторыми оговорками) использовать в качестве отправной точки для понимания фактического поведения.
1. Чистые стратегии, представляющие собой непрерывные переменные
В главе 4 мы сформулировали метод анализа наилучших ответов для поиска всех равновесий Нэша в чистых стратегиях в играх с одновременными ходами. Теперь расширим его на игры, в которых у каждого игрока — непрерывный диапазон вариантов выбора, например при установлении компанией цен на свою продукцию. Чтобы вычислить наилучшие ответы в игре такого типа, мы должны найти для каждого возможного значения цены одной компании значение цены другой компании, которое будет для нее лучшим (максимизирует ее прибыль). Непрерывность множества стратегий позволяет нам использовать алгебраические формулы для того, чтобы продемонстрировать, как стратегии обеспечивают выигрыши, а также показать наилучшие ответы в виде линий на графике, где на осях координат отображена цена (или любая другая непрерывная стратегия) каждого из игроков. При таком способе представления игры равновесие Нэша находится в месте пересечения линий на графике. Мы разовьем эту идею и метод на примере двух историй.
А. Ценовая конкуренция
Наша первая история происходит в маленьком городке под названием Яппи-Хейвен, в котором есть два ресторана: Xavier’s Tapas Bar и Yvonne’s Bistro. Чтобы упростить ситуацию, будем исходить из предположения, что в каждом ресторане используется стандартное меню. Владельцы Xavier’s и Yvonne’s должны установить цены на блюда в своих меню; при этом цель каждого из них, чтобы эти цены обеспечивали максимальную прибыль (выигрыш в этой игре). Мы также полагаем, что рестораны печатают меню порознь, не зная о ценах друг друга, стало быть, это игра с одновременными ходами[57]. Поскольку цены могут принимать любое значение в пределах (почти) бесконечного диапазона, начнем с введения общих или алгебраических обозначений, затем найдем правила наилучших ответов и используем их для решения игры и определения равновесных цен. Обозначим цену ресторана Xavier’s как Px а Yvonne’s как Py.
При определении цены каждый ресторан должен просчитать последствия с точки зрения прибыли. Для того чтобы упростить задачу, мы ставим два ресторана в условия симметричной зависимости, но читатели с развитыми математическими навыками могут выполнить аналогичный анализ, воспользовавшись более общими величинами или даже алгебраическими символами. Допустим, обслуживание одного клиента обходится каждому ресторатору в 8 долларов. Предположим также, что опыт или исследования рынка показывают, что, если цена ресторана Xavier’s Px, а Yvonne’s Py, количество клиентов, Qx и Qy соответственно (в сотнях клиентов в месяц) задается уравнениями[58]
Qx = 44 — 2Px + Py,
Qy = 44 — 2Py + Px.
Основная идея этих уравнений состоит в том, что, если один ресторан повысит цену на 1 доллар (скажем, Yvonne’s повысит Py на один доллар), его объем продаж сократится на 200 в месяц (Qy уменьшится на 2), а объем продаж другого ресторана увеличится на 100 в месяц (Qx увеличится на 1). Можно предположить, что 100 клиентов ресторана Yvonne’s перейдут к Xavier’s, а еще 100 останутся дома.
Обозначим прибыль ресторана Xavier’s за неделю (в сотнях долларов в неделю) символом х (греческая буква [ «пи»] — традиционный экономический символ для обозначения прибыли). Эта прибыль рассчитывается как произведение чистого дохода на одного клиента (цена за вычетом затрат на обслуживание, или Рх — 8) и количества обслуженных клиентов:
x = (Px — 8)Qx = (Px — 8) (44 — 2Px + Py).
Умножив и перегруппировав члены в правой части предыдущего выражения, можем записать прибыль как функцию повышающихся степеней Рх:
Xavier’s устанавливает цену Рх, чтобы максимально увеличить свой выигрыш. Делая это для каждого возможного уровня цены ресторана Yvonne’s Py, мы получим правило наилучших ответов ресторана Xavier’s, которое можно отобразить на графике.
В такой форме можно представить многие простые иллюстративные примеры, в которых одно действительное число (такое как цена) выбирается для максимального увеличения другого, зависимого от него действительного числа (например, прибыль или выигрыш). В приложении к этой главе описан простой общий метод выполнения операции максимизации; вы найдете немало случаев его применения. Здесь же мы просто приводим формулу.
Функция, которую мы хотим максимизировать, задается следующим общим уравнением:
Y = A + BX–CX2.
Мы использовали обозначение Y для величины, которую нужно максимизировать, и X для величины, которую хотим выбрать, чтобы максимизировать Y. В нашем конкретном примере прибыль x будет представлена в виде Y, а цена Pх в виде X. Точно так же, хотя в любой конкретной задаче члены приведенного выше уравнения А, В и С были бы известны, мы обозначили их общими алгебраическими символами, с тем чтобы наша формула была применима ко множеству аналогичных задач. (Формальный термин, которым обозначаются члены А, В и С, — параметры, или алгебраические константы.) Поскольку большинство случаев практического применения подразумевают наличие неотрицательных значений X, таких как цены, а также максимизацию значения Y, необходимо, чтобы выполнялось условие В > 0 и С > 0. Тогда формула, позволяющая выбрать X для максимизации Y с учетом известных значений А, В и С, будет выглядеть так: Х = В/2С. Обратите внимание, что А в ней отсутствует, хотя это, безусловно, влияет на полученное в результате значение Y.
Сравнив общую функцию в уравнении выше и конкретный пример функции прибыли в игре в ценообразование на предыдущей странице, получим[59]
