Приложение по теории игр

Предварительное замечание

Теория игр, описывающая и объясняющая закономерности стратегического поведения, широко используется в экономике, политических науках, эволюционной биологии. Данное приложение к учебнику помогает читателю познакомиться с элементарными основами игровых моделей, которые используются в данном учебнике. Безусловно, этот материал не является исчерпывающим и не заменяет специализированных текстов. По теории игр написано множество замечательных учебников, из которых заинтересованному читателю мы можем порекомендовать Gibbons R. Game Theory for Applied Economists, 1992 и более продвинутый Osborne, M.J and Rubinstein, A. A Course in Game Theory, 1994, а из русскоязычных ресурсов – Захаров А.В. Теория игр в общественных науках, 2015 и Челноков А.Ю. Теория игр: учебник и практикум для бакалавриата и магистратуры, 2016. Любителям научно-популярной литературы можно посоветовать Диксит, А., Нейлбафф, Б. Теория игр. Искусство стратегического мышления в бизнесе и жизни, 2015 и Бинмор, К. Теория игр: очень краткое введение, 2017.

Базовые концепции. Статические игры

Игра

Игра – это набор из трех элементов \((P, S, U)\), где

• \(P\) – множество игроков (или агентов)

• \(\mathbf{S} = \{S_1, ... , S_p\}\) – множество наборов стратегий для каждого игрока. Элемент множества \(S_1 \times ... \times S_p\) называется профилем стратегий

• \(\mathbf{U} = \{U_1, ..., U_p\}\) – функции выигрышей (или полезностей) для игроков. Функция выигрыша ставит в соответствие каждому профилю стратегий исход, к которому приходит игрок: \(U_i: S_1 \times ... \times S_p \rightarrow \mathbb{R}\).

Пример: Пусть \(P = \{1,2\}\), \(S_1 = S_2 = \{c, nc\}\) \[U_1(s_1, s_2) = \begin{cases} -5, s_1 = c, s_2 = c\\ 0, s_1 = nc, s_2 = c\\ -25, s_1 = c, s_2 = nc\\ -10, s_1 = nc, s_2 = nc \end{cases}\]

\(U_2(s_1, s_2) = U_1(s_2, s_1)\)

Проще игру представить в виде таблички со стратегиями игрока 1 по строкам, стратегиями игрока 2 по столбцам и выигрышами первого и второго игрока в ячейках (это называется представлением в нормальной форме)

Дилемма Заключенного

	Молчать	Выдать
Молчать	\(-5,-5\)	\(-25,0\)
Выдать	\(0,-25\)	\(-10,-10\)

Упражнение: Сформулируйте игру «Камень-Ножницы-Бумага» по определению.

Равновесие по Нэшу

Фундаментальной концепцией теории игр является равновесие.

Профиль стратегий \(s^*\) называется равновесием по Нэшу, если для каждого игрока i \[\forall s_i \in S_i; U_i(s^*_i, s^*_{-1}) \geq U_i(s_i, s^*_{-1})\]

Иными словами, если каждому игроку невыгодно отклоняться от этого профиля стратегий в одиночку.

О равновесии стоит думать именно как об устойчивом исходе, а не как о предсказании. Равновесий может быть несколько или не быть вовсе. Несмотря на то, что сам термин «равновесие» в русском языке имеет скорее положительную коннотацию, в теории игр и в жизни часто встречаются «плохие», неэффективные равновесия.

Пример: Рассмотрим игру «Дилемма заключенного». Двое соучастников ограбления посажены в разные камеры. Они могут давать или не давать показания. Заключенный, сотрудничающий со следствием, получает освобождение, если его напарник молчал (тогда напарник, в свою очередь, наказывается сильнее). Если оба дали показания, эти сведения используются для увеличения срока заключения. Найдем наибольший выигрыш первого игрока в каждом столбце и наибольший выигрыш второго игрока в каждой строке (это называется наилучшим ответом). Там, где эти наибольшие выигрыши совпадают – это равновесие по Нэшу (Выдать, Выдать). В этой игре одно равновесие в чистых стратегиях.

Обратите внимание, что в данном случае мы имеем дело с равновесием в доминирующих стратегиях, то есть игроку не просто выгодно выдавать, ему выгодно выдавать вне зависимости от действий другого игрока (а не только в равновесном профиле)

\[\forall s_i, s_{-i} \in S_i; U_i(s^*_i, s_{-1}) \geq U_i(s_i, s_{-1})\]

Пример: Координационная игра «Война полов». Предположим, что два игрока выбирают, где провести время, из двух вариантов: на Футболе или в Опере. Для каждого провести время с партнером лучше, чем отдельно от него, при этом первый игрок предпочитает Футбол, а второй Оперу. В этой игре 2 равновесия.

Война полов

	Футбол	Опера
Футбол	\(4, 1\)	\(0, 0\)
Опера	\(0, 0\)	\(1, 4\)

Пример: Координационная игра «Игра с трусом». Предположим, что два игрока встречеются на узкой дороге. Если каждый продолжит движение, они пострадают, но у каждого есть возможность уступить. В этой игре также два равновесия, но в отличии от Войны полов, здесь равновесными оказываются исходы, в которых игроки выбирают отличающиеся стратегии.

Игра с трусом

	Ехать прямо	Свернуть
Ехать прямо	-1, -1	3, 1
Свернуть	1, 3	2, 2

Пример: «Орлянка». Два игрока одновременно выкладывают монетку. Если сторона монетки совпала, побеждает первый игрок. Если не совпала – второй. Эта игра примечательна, во-первых, тем, что равновесия в чистых стратегиях в ней нет вовсе (каждому игроку выгодно вести себя непредсказуемо, как и в игре «Камень-Ножницы-Бумага»). Во-вторых, это пример чистого конфликта, то есть игры, где выигрыш одного автоматически означает проигрыш другого. (Подобные взаимодействия в литературе называются играми с нулевой суммой или антагонистическими играми).

Игра «Орлянка»

	Орел	Решка
Орел	\(1,-1\)	\(-1,1\)
Решка	\(-1,1\)	\(1,-1\)

Динамические игры

В примерах выше мы предполагали, что игроки принимают решения о своей стратегии одновременно и независимо друг от друга – такие игры называются статическими. Однако существует множество ситуаций, в которых решения игроками принимаются последовательно. Рассмотрим игру, в которой первый генерал решает — атаковать город или нет, а второй решает — принять бой или нет. Бой обойдется каждой армии в 5 единиц. Ценность города — 3 единицы. В случае, если бой состоится, выигрывает атакующая армия.

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

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

Равновесие по Нэшу в динамической игре определяется как и в статической: это такой профиль стратегий, от которого каждому игроку в отдельности невыгодно отклоняться.

Упражнение: перепишите эту игру в нормальную форму и найдите ее равновесия.

Равновесный путь и обратная индукция

Равновесный путь в динамической игре – это все посещенные узлы (вершины) дерева при равновесном профиле стратегий.

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

Пример: В игре выше есть два равновесия: (Атаковать, Отступить) и (Не атаковать, Принять бой). Во втором равновесии важно, какой ход сделал бы второй игрок, хоть он и не лежит на равновесном пути. Именно из-за этого потенциального хода первому игроку невыгодно отклоняться.

Второй игрок может выбирать такую стратегию именно потому, что его черед ходить не наступает. А его черед ходить не наступает именно потому, что он выбрал такую стратегию. Такая ситация называется недостоверной угрозой (или недостоверным обязательством). Более сильная концепция равновесия, в которой нет недостоверных угроз, называется равновесием, совершенным по подыграм.

Алгоритм поиска такого равновесия называется обратной индукцией. Сначала ищется оптимальная стратегия в конечных узлах дерева. Зная решение в конечных узлах дерева, ищется оптимальная стратегия в предпоследних узлах. Индукция продолжается, пока не достигнет корня дерева.

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

Игры с неполной информацией

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

Система типов

• \(\mathbf{\Theta} = \{\Theta_1, ... , \Theta_p\}\) – множество типов каждого игрока, а также

• \(\mathcal{F}\) – совместное распределение типов

Предполагается, что игрок знает свой собственный тип, но не знает типов других игроков. Чтобы это формализовать, мы поменяем определение стратегии и дополним определение игры действиями:

• \(\mathbb{M} = {M_1, ..., M_p}\) – множество действий (или сообщений) каждого игрока

• Игрок может пользоваться знанием своего типа, чтобы предпринять действие. Таким образом, стратегия – это функция из типов в действия \(s_i:\Theta_i \to M_i\)

Наконец, типы влияют на полезности, которые игроки получают (и что важно тип игрока, может влиять и на чужую полезность). Таким образом, мы получаем новое определение полезности игрока:

\[U_i: \prod_j A_j \times \prod_j \Theta_j \to \mathbb{R}\]

Пример: Рассмотрим игру из двух игроков: продавца и покупателя. Продавец имеет тип \(\theta \in \Theta\), который означает качество продаваемого товара. Также предположим, что на рынке есть товары качества от \([0, 1]\), равномерно распределенные на этом интервале, от которых зависят издержки производства и потребительские качества товара. Продавец предлагает цену \(p\), а игрок либо принимает ее, либо нет (обозначим за \(a\)). Полезность продавца: \(U_S = a(p - 0.75 \theta)\). Полезность покупателя: \(U_B = a(\theta - p)\).

Равновесие Байеса-Нэша и убеждения

Теперь определим равновесие в такой игре. Профиль стратегий \(s^\ast\) является Байес-Нэш равновесием, если: \[\begin{gathered} \mathbb{E}(U_i(s_i^\ast(\theta_i), s_{-i}^\ast(\theta_{-i}), \theta_i, \theta_{-i})| \theta_i) \geq \mathbb{E}_{\theta_i}(U_i(s_i(\theta_i), s_{-i}^\ast(\theta_{-i}), \theta_i, \theta_{-i})| \theta_i) \end{gathered}\]

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

Иногда о равновесиях удобно рассуждать в терминах убеждений. Убеждения – это распределение вероятностей над стратегиями других игроков, или вероятностная вера игрока в то, как поведут себя другие. На равновесие  можно смотреть как на пару 1) стратегий, которые являются наилучшим ответом на убеждения, а также 2) убеждения, которые согласованы с этим набором стратегий. Мы используем этот подход, чтобы найти равновесие в нашем примере выше

Пример: Сначала найдем стратегию наилучшего ответа для продавцов. Предположим, покупатель приобретает товар по любой цене ниже цены \(p\) (убеждение). Тогда все продавцы, чей тип \(\theta \leq \frac{p}{0.75}\), будут продавать ровно по этой цене. Теперь найдем наилучший ответ покупателя. Покупатель, которому продавцы с типом \(\theta \leq \frac{p}{0.75}\) предлагают цену \(p\) (убеждение), купит по этой цене только, если \(p \leq \frac{p}{0.75 * 2}\). Из-за того, что лучшие продавцы не могут продать товар по удовлетворительной для покупателя цене, единственной равновесной ценой (которая согласует убеждения с оптимальными стратегиями) будет \(p = 0\), а в продаже будут только товары наихудшего качества. Такой самоотбор возникает потому что покупатели не готовы платить за товар заранее неизвестного качества, а качественные производители не готовы продавать товар по цене низкокачественных товаров.

Упражнение: Какая будет равновесная цена, если производитель не несет никаких издержек?

Дизайн механизмов

Дизайн механизмов – это важный раздел теории игр, который фактически решает обратную задачу. Имея описанные способы решения игры (равновесия), может ли принципал (например, регулятор) сконструировать игру таким образом, чтобы игрокам было выгодно придерживаться профиля стратегий, который приведет к желаемым для регулятора исходам? (На задачу дизайна можно смотреть и как на динамическую игру, в которой регулятор ходит первым, выбирая правила игры, после которого ходят игроки (агенты), играя в ту игру, которую выбрал регулятор). В качестве широко распространенных практических задач можно упомянуть организацию аукционов, систему бонусов и штрафов в стимулирующих трудовых контрактах, дизайн налоговой системы, правила голосования и т.д. Таким образом, базовая задача хорошо сконструированного механизма – заставить агентов своими действиями «выявить» частную информацию. Формальная теория контрактов и ее практические приложения являются частным случаем задачи дизайна механизмов. Заинтересованному читателю мы рекомендуем книгу Савватеев, А., Филатов, А. Занимательная экономика. Теория экономических механизмов от А до Я, 2022.

Эволюционная теория игр

Биологи используют игровые модели для объяснения и описания эволюционного отбора. Для этого можно предположить, что игроки (в контексте биологии – особи) обладают разными типами и случайным образом вступают во взаимодействие друг с другом (базовое взаимодействие может быть любой элементарной игрой – например, Дилеммой заключенного). В таком случае средние выигрыши игроков, которые они получат в этих взаимодействиях, будут зависеть от долей разных типов в популяции. Если предположить, что размер среднего выигрыша определяет репродуктивный успех, то в новом поколении структура популяции изменится в пользу типа, который приносил своему обладателю больший успех. Представители общественных наук все чаще используют подобный инструментарий для анализа динамики социальных норм и культурных характеристик. Заинтересованного читателя мы отсылаем к монографии Боулз, С. Микроэкономика. Поведение, институты и эволюция, 2011.