Теория игр

Основные концепции

Теория игр — наука молодая, хотя, конечно, и не такая молодая, как теория экономических механизмов. Первые шаги на пути к теории игр были сделаны в XVIII веке, первая опубликованная работа относится к первой половине XIX века — это знаменитая книга Антуана Огюстена Курно [14]. Примечательно, что много важных замечаний, относящихся к теории игр, были сделаны биологами, рассматривавшими теорию естественного отбора и поведения животных; поведение было, разумеется, эгоистическим. Классический труд Рональда Фишера [19] содержит многие методы теории игр, а уже после математического оформления этой теории эстафету принял Джон Майнард Смит [46]. Математически же теорию игр оформил Джон фон Нейман: сначала в статьях 1920-х годов [61], а затем в книге с Оскаром Моргенштерном [62], с которой, наверное, и нужно вести историю теории игр как развитого математического аппарата. Учебники по теории игр мы здесь пересказывать не будем, цель этой книги совершенно другая; мы просто изложим вкратце некоторые вещи из теории игр, без которых нам совсем уж не обойтись. А если читатель заинтересуется теорией игр всерьез, рекомендуем ему учебники [20,23,64,65,79].

Дадим формальное определение игр, которые мы будем рассматривать. Кстати, шахматы или даже го не будут подпадать под это определение. Что и логично: мы тут математикой занимаемся, а не эффективными алгоритмами; а с математической точки зрения (да и с точки зрения теории сложности алгоритмов, асимптотической по своей природе) шахматы или го совершенно неинтересны: на конечной доске с конечной продолжительностью партии и с полной информацией выигрышную (или беспроигрышную, если выигрышной нет) стратегию можно "легко" подсчитать простым перебором вариантов.

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

Определение 1.1.Стратегическая игра — это тройка

$$\langle \mathcal I, \{ S_i \}_{i\in\cal I}, \{u_i\}_{i\in\mathcal I}\rangle,$$

где обозначения расшифровываются следующим образом:

$$\mathcal I=\{1,...,N\}$$ — конечное множество игроков.

$$\{S_i\}_{i\in\mathcal I}$$ — множество доступных игрокам действий, где $$S_i$$ — множество действий, доступных игроку $$i$$. Будем обозначать через $$s_i\in S_i$$ действие игрока $$i$$, а через $$\mathbf s_{-i}=[s_j]_{j\neq i}$$ — вектор действий всех игроков, кроме iВообще, обозначения вида $$(\cdot)_{-i}$$ в этой книге встречаться будут повсеместно — привыкайте!. Через $$\mathbf S = \prod_{i=1}^NS_i$$ будем обозначать множество всех векторов действий игроков, через $$\mathbf S_{-i}= \prod_{j\neq i}^NS_i$$ — множество векторов действий всех игроков, кроме $$i$$. Вектор $$(s_1,...,s_N) = (s_i,\mathbf s_{-i}) \in \mathbf S$$ будем называть профилем действий, или исходом.

$$\{u_i\}_{i\in\\mathcal I}$$ — множество функций выплат $$u_i:\mathbf S\to\mathbb R$$.

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

Есть и еще одно важное замечание: в течение этой лекции мы предполагаем, что у участников есть предпочтения по поводу исходов игры и эти предпочтения можно выразить при помощи функций $$u_i:S\to\mathbb R$$. Это далеко не всегда так, и в лекции 6 мы еще поговорим об интересных эффектах, возникающих, когда предпочтения так выразить нельзя. Но для базовой теории игр придется это предположение все-таки сделать.

Если множество стратегий $$S$$ конечно, то множество исходов игры можно выразить $$N$$ -мерной матрицей, в ячейке которой с координатами $$\mathbf s = (s_1,..., s_N)$$ стоят исходы $$(u_1(\mathbf s),..., u_N(\mathbf s))$$. В случае игры с двумя игроками эта конструкция превращается в самую обычную матрицу.

Пример 1.1. Первый пример возьмем совсем уж из детства — рассмотрим классическую игру "камень-ножницы-бумага"Хотя насчет детства еще можно поспорить: в США вот недавно появилась аж целая ассоциация, посвященная игре в "Rock, Paper, Scissors" под логичным названием USARPS. Призы неплохие — можете попробовать свои силы на сайте http://www.usarps.com/.. Камень побеждает ножницы, ножницы побеждают бумагу, бумага — камень. У игры получается вот какая матрица (где $$1$$ означает победу того игрока, чьи стратегии выписаны слева, а $$-1$$ — победу игрока, стратегии которого стоят в первой строке):

$$\begin{array}{r|rrr} \sdt{Камень} \sdt{Ножницы} \sdt{Бумага} \\ \hline \text{Камень} 0 1 -1 \\ \text{Ножницы} -1 0 1 \\ \text{Бумага} 1 -1 0 \\ \end{array}$$

Конец примера 1.1.

Пример 1.2. В качестве второго примера рассмотрим классическую игру полковника Блотто [70,79]. Полковник Блотто должен распределить свои силы ( $$M$$ солдат) между несколькими участками поля боя ( $$S$$ участков). Его противник должен сделать то же самое (количество его солдат может отличаться). Выигрывает тот, кто победит на большем количестве участков боя.

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

(3,0,0),  (2,1,0),  (2,0,1),  (1,2,0),  (1,1,1),
(1,0,2),  (0,3,0),  (0,2,1),  (0,1,2),  (0,0,3).

В результате у этой игры получается вот какая матрица. Здесь стратегии Блотто изображены слева, противника — сверху; $$1$$ означает, что победил Блотто, $$-1$$ — что противник, $$0$$ — случилась ничья.

$$\begin{array}{l|rrrrrrrrrr} \sd{(3,0,0)} \sd{(2,1,0)} \sd{(2,0,1)} \sd{(1,2,0)} \sd{(1,1,1)} \sd{(1,0,2)} \sd{(0,3,0)} \sd{(0,2,1)} \sd{(0,1,2)} \sd{(0,0,3)} \\ \hline (3,0,0) 0 0 0 0 -1 0 0 -1 -1 0 \\ (2,1,0) 0 0 0 0 0 1 0 -1 0 1 \\ (2,0,1) 0 0 0 1 0 0 1 0 -1 0 \\ (1,2,0) 0 0 -1 0 0 0 0 0 1 1 \\ (1,1,1) 1 0 0 0 0 0 1 0 0 1 \\ (1,0,2) 0 -1 0 0 0 0 1 1 0 0 \\ (0,3,0) 0 0 -1 0 -1 -1 0 0 0 0 \\ (0,2,1) 1 1 0 0 0 -1 0 0 0 0 \\ (0,1,2) 1 0 1 -1 0 0 0 0 0 0 \\ (0,0,3) 0 -1 0 -1 -1 0 0 0 0 0 \end{array}$$

Конец примера 1.2.

Отметим, что в играх из примеров 1.1 и 1.2 прибыль одного участника строго равнялась убытку второго. Такие игры называются играми с нулевой суммой ; формально говоря, в таких играх для любого профиля действий участников $$\mathbf s\in S$$ верно, что $$\sum_{i=1}^Nu_i(\mathbf s) = 0$$ .

В дальнейшем нас будут интересовать не только игры с конечными множествами стратегий, но и игры с непрерывными такими множествами. Возьмем классический пример — конкуренцию по Курно (Cournot competition)Этот пример действительно восходит к классику экономической теории Антуану Огюстену Курно [14].

(рис 1.1) Конкуренция по Курно: функции оптимального ответа

Пример 1.3. Рассмотрим рынок некоего продукта, на котором находятся ровно две фирмы: $$\mathcal I = \{1,2\}$$. Стратегия каждого из участников — количество продукта, которое он производит: $$s_i \in [0,\infty)$$.

Прибыль каждого участника в результате игры — это его общий доход за вычетом себестоимости:

$$u_i(s_1, s_2) = s_ip(s_1 + s_2) - c_i s_i,$$

где $$p(q)$$ — функция, по которой определяется цена, а $$c_i$$ — цена за единицу для компании $$i$$. Мы будем предполагать, что $$c_1 = c_2 = 1$$. В качестве функции $$p$$ мы рассмотрим

$$p(q) = \begin{cases}2-q, q \le 2, \\ 0, q > 2.\end{cases}$$

Давайте попробуем проанализировать, как фирмам лучше всего играть в свою игру. Попробуем построить оптимальную стратегию для игрока $$1$$, если игрок $$2$$ произвел товара $$s_{-i}$$ (best response function, $$B_i(s_{-i})$$ ). Если $$s_{-i}>2$$, то производить ничего не надо, потому что равновесная цена все равно будет равна нулю. Если же $$s_i\in [0,2]$$, то оптимальную стратегию придется искать так:

$$B_i(s_{-i}) = \arg\max\limits_{s_i\ge 0}(s_i(2-s_i-s_{-i})-s_i) = \\ = \arg\max\limits_{s_i\ge 0}(-s_i^2 + s_i(1-s_{-i})) = \frac{1-s_{-i}}2.$$

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

Конец примера 1.3.

Доминантные и доминируемые стратегии

Что же делать участвующим в игре агентам? Как им определить, какая стратегия лучше других?

Давайте для начала поставим перед собой более скромную цель: определить, какие стратегии точно не подойдут.

Определение 1.2. Стратегия $$s\in S_i$$ агента $$i$$ называется доминируемой, если существует такая стратегия $$s^\prime \in S_i$$, что

$$\forall \mathbf s_{-i} \in \mathbf S_{-i}\quad u_i(s^\prime, \mathbf s_{-i})\ge u_i(s, \mathbf s_{-i}).$$

В таком случае говорят, что $$s^\prime$$ доминирует над $$s$$.

Иначе говоря, стратегия $$s$$ доминируема, если существует другая стратегия, которая не хуже $$s^\prime$$ в каждой точке, при любых возможных комбинациях стратегий других агентов. Значит, нет вообще никакой причины предпочитать $$s$$, и ее можно просто отбросить при анализе.

Пример 1.4. Вспомним пример 1.2, в котором полковник Блотто собирался расставить войска на поле. Если проанализировать матрицу из примера 1.2, станет очевидным, что стратегии $$(3,0,0)$$, $$(0,3,0)$$ и $$(0,0,3)$$ доминируются другими: например, стратегия $$(1,1,1)$$ окажется лучше любой из них. Разумеется, то же самое верно и для противника Блотто. Таким образом, матрица существенно сократится.

$$\begin{array}{l|rrrrrrr} \sd{(2,1,0)} \sd{(2,0,1)} \sd{(1,2,0)} \sd{(1,1,1)} \sd{(1,0,2)} \sd{(0,2,1)} \sd{(0,1,2)}\\ \hline (2,1,0) 0 0 0 0 1 -1 0 \\ (2,0,1) 0 0 1 0 0 0 -1 \\ (1,2,0) 0 -1 0 0 0 0 1 \\ (1,1,1) 0 0 0 0 0 0 0 \\ (1,0,2) -1 0 0 0 0 1 0 \\ (0,2,1) 1 0 0 0 -1 0 0 \\ (0,1,2) 0 1 -1 0 0 0 0 \end{array}$$

Конец примера 1.4.

Пример 1.5. В примере 1.3, в котором мы обсуждали конкуренцию по Курно, было очень много доминируемых стратегий. Таковыми были все стратегии $$s_i \ge 2$$: они гарантированно приносили неположительную прибыль, в то время как нулевая стратегия ( $$s_i=0$$, ничего не производить) гарантирует нулевую прибыль. Поэтому сразу можно было ограничиться анализом квадрата $$[0,2]\times [0,2]$$ в качестве множества стратегий.

Конец примера 1.5.

Правда, стоит заметить, что легко построить пример, в котором любая стратегия доминируема. Это будет значить, что некоторые стратегии эквивалентны, то есть доминируют друг над другом. В таких случаях хотя бы одну из них стоит оставить, а то совсем не из чего будет выбирать.

Продолжаем разговор. После доминируемых стратегий логично будет ввести доминантные стратегии.

Определение 1.3. Стратегия $$s\in S_i$$ агента $$i$$ называется доминантной, если всякая другая стратегия $$s^\prime \in S_i$$ ею доминируется, то есть

$$\forall s^\prime\in S_i \text{ }\forall \mathbf s_{-i} \in \mathbf S_{-i}\quad u_i(s,\mathbf s_{-i})\ge u_i(s^\prime,\mathbf s_{-i}).$$

Доминантная стратегия для агента — настоящее счастье. Ему вообще думать не надо: достаточно выбрать доминантную стратегию, все равно никакая другая ни при каком исходе ничего лучшего не даст.

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

Определение 1.4. Равновесие в доминантных стратегиях для стратегической игры $$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle$$ — это такой профиль стратегий $$s^*\in S$$, что для всякого агента $$i\in\mathcal I$$ стратегия $$s^*_i$$ является доминантной.

Такое равновесие является самым устойчивым из всех. В следующей лекции мы приведем пример из теории экономических механизмов, в котором возникает такое равновесие — так называемый аукцион Викри (см. теорему 2.1.

Но, к сожалению, счастье достижимо далеко не всегда. Ни в примере 1.1, ни в примере 1.2, ни в примере 1.3 никакого равновесия в доминантных стратегиях не получалось. Для каждой стратегии $$s_i$$ игрока $$i$$ там существовал профиль стратегий других игроков $$s_{-i}$$, в котором игроку $$i$$ было бы выгодно сменить $$s_i$$ на ту или иную $$s^\prime_i\neq s_i$$.

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

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

Тогда приходится учитывать не только свои собственные стратегии, но и стратегии других агентов. Учет этот приведет к понятию равновесия, сформулированному в 1950 году Джоном Нэшем [60].

Определение 1.5. Равновесие Нэша в чистых стратегиях для стратегической игры $$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle$$ — это такой профиль стратегий $$\s^*\in S$$, что для всякого агента $$i\in\cal I$$ выполняется следующее условие:

$$\forall s_i\in S_i\quad u_i(s_i^*,\mathbf s_{-i}^*)\ge u_i(s_i,\mathbf s_{-i}^*).$$

Иначе говоря, как и прежде, агенту невыгодно отклоняться от избранной стратегии $$s_i^*$$. Но теперь ему это невыгодно делать не абстрактно, при любом выборе стратегий у других агентов, а только в конкретном профиле стратегий $$\s^*$$.

Пример 1.6. Продолжаем рассматривать беднягу Блотто. Матрица игры полковника без доминируемых стратегий была приведена в примере 1.4. Из матрицы легко видеть, что если один игрок выбирает стратегию $$(1,1,1)$$, то от выбора другого уже ничего не зависит, то есть можно сказать, что другому тоже нет резона отклоняться от стратегии $$(1,1,1)$$. Все это значит, что для данной игры профиль стратегий $$((1,1,1), (1,1,1))$$ находится в равновесии Нэша.

Конец примера 1.6.

Приведем и непрерывный пример — поверьте, нас еще ждут подобные рассуждения, и пора привыкать к чуть более серьезному анализу.

Пример 1.7. Вернемся к анализу конкуренции по Курно из примера 1.3. На этот раз мы не будем ничего упрощать: пусть цена задается неизвестной функцией $$P(s_1+s_2)$$, а себестоимость производства для каждой фирмы — неизвестной функцией $$C_i(s_i)$$. Чтобы найти равновесие Нэша, найдем функцию лучшего ответа. Прибыль компании определяется как

$$\Pi_i(s_1, s_2) = s_iP(s_1 + s_2) - C_i(s_i).$$

Чтобы определить максимум функции $$\Pi_i$$ для фиксированного $$s_{i}$$, нужно просто найти производную

$$\frac{\partial\Pi_i}{\partial s_i} = \frac{\partial P(s_1 + s_2)}{\partial s_i} - P(s_1 + s_2) - \frac{\partial C_i(s_i)}{\partial s_i}$$

и приравнять ее к нулю. Соответственно, равновесие Нэша достигается там, где обе фирмы выдают оптимальный ответ на стратегию противника, то есть на решениях следующей системы дифференциальных уравнений:

$$\frac{\partial \Pi_1}{\partial s_1} = \frac{\partial P(s_1 + s_2)}{\partial s_1} - P(s_1 + s_2) - \frac{\partial C_1(s_1)}{\partial s_1} = 0, \\ \frac{\partial \Pi_2}{\partial s_2} = \frac{\partial P(s_1 + s_2)}{\partial s_i} - P(s_1 + s_2) - \frac{\partial C_2(s_2)}{\partial s_2} = 0.$$

Оставим читателю удовольствие проверить, что в рассмотренном в примере 1.3 частном случае равновесием Нэша действительно будет точка пересечения прямых на рис. 1.1.

Конец примера 1.7.

В определении 1.5 упоминался странный термин "чистые стратегии": а какими еще они бывают? Оказывается, что стратегии бывают не только чистыми, но и смешанными. Смешанные стратегии — логичное расширение понятия стратегии: давайте разрешим игроку не только выбирать одну из $$s_i$$, но и делать из них более или менее случайный выбор.

Определение 1.6. Смешанная стратегия для игрока $$i$$ в стратегической игре $$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle$$ — это распределение вероятностей $$\sigma_i\in\Sigma_i$$, где $$\Sigma_i$$ — множество всех распределений вероятностей над $$S_i$$ .

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

Бывают игры, где нет равновесий Нэша для чистых стратегий. Но оно всегда (в конечном случае) есть в смешанных стратегиях.

Пример 1.8. Вспомним игру "камень-ножницы-бумага", матрицу которой мы уже выписывали в примере 1.1.

$$\begin{array}{r|rrr} \sdt{Камень} \sdt{Ножницы} \sdt{Бумага} \\ \hline \text{Камень} 0 1 -1 \\ \text{Ножницы} -1 0 1 \\ \text{Бумага} 1 -1 0 \\ \end{array}$$

Очевидно, что никакого равновесия Нэша в чистых стратегиях здесь нет: для любой стратегии найдется кому ее опровергнуть. Но равновесие Нэша в смешанных стратегиях здесь имеется. Предположим, что второй игрок выбирает камень, ножницы или бумагу с вероятностью $$\frac{1}{3}$$, а первый выбирает их с вероятностями $$p$$, $$q$$ и $$1-p-q$$. Тогда первый игрок выигрывает с вероятностью

$$\frac{1}{3}p + \frac{1}{3}q + \frac{1}{3}(1-p-q)=\frac{1}{3},$$

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

$$\left[\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right),\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)\right]$$

находится в равновесии.

Конец примера 1.8.

Доказательство того, что равновесие в смешанных стратегиях всегда существует, следует из теоремы Какутани о неподвижной точке [12,31].

Теорема 1.1 (Какутани) Пусть $$S$$ — непустое выпуклое компактное подмножество евклидова пространства $$\mathbb R^n$$, а $$\phi:S\to 2^S$$ — многозначная функция на $$S$$ с замкнутым графиком, такая, что множество $$\phi(\mathbf x)$$ непусто, замкнуто и выпукло для всех $$\mathbf x\in S$$. Тогда у $$\phi$$ есть неподвижная точка: $$\exists \mathbf x: \mathbf x\in\phi(\mathbf x)$$.

(рис 1.2) Контрпример к теореме Какутани для невыпуклого графика

Замечание. Чтобы понять условие теоремы, обычно лучше всего привести пример, в котором без одного из условий теорема оказывается неверной. Вот и здесь: давайте рассмотрим многозначную функцию на единичном отрезке $$f:[0,1]\to 2^{[0,1]}$$, заданную как

$$f(x) = \begin{cases}x+\frac12, x < \frac12, \\ \{0,1\}, x = \frac12, \\ x - \frac12, x > \frac12.\end{cases}$$

Получилась функция с замкнутым графиком (график ее изображен на рис. рис. 1.2), но прямую $$x=f(x)$$ он не пересекает, а все потому, что в точке $$x=\frac12$$ график не является выпуклым (если замкнуть его по выпуклости в этой точке, то она и будет неподвижной для $$f$$ ). Ну а для любой функции, удовлетворяющей всем условиям теоремы, все в порядке: вот, например, на рис. рис. 1.3 функция $$f(x)=\left[\frac12-\frac12x,1-x\right]$$, заданная на все том же отрезке $$S=[0,1]$$. Как видно, она пересекает прямую $$x=f(x)$$ (причем далеко не в одной точке); $$x$$ -координаты всего этого пересечения представляют собой неподвижные точки функции $$f$$.

(рис 1.3) Пример к теореме Какутани

Следствие 1.1.1. В любой конечной игре существует равновесие Нэша в смешанных стратегиях.

Каждая смешанная стратегия есть распределение вероятностей на множестве возможных действий агента, а значит, сумма этих вероятностей равна единице. Но в $$n$$ -мерном евклидовом пространстве симплекс

$$\Delta^n = \left\{\bm a = (a_1, a_2, \ldots, a_n)\mid a_i\ge0, \sum_{i=1}^n a_i = 1\right\}$$

является выпуклым компактным множеством. Выигрыш игрока в игре со смешанными стратегиями есть математическое ожидание вида

$$G_i(a_1, a_2,..., a_n) = \sum\limits_{i_1 = 1}^{m_1} \sum\limits_{i_2 = 1}^{m_2} .. \sum\limits_{i_n = 1}^{m_n} g_i(i_1, i_2,..., i_n)a_1^{i_1} a_2^{i_2} .. a_n^{i_n}.$$

Эта функция является линейной и непрерывной по $$\mathbf a$$ при фиксированных остальных аргументах. Следовательно, по теореме Какутани, у этой функции будет неподвижная точка. Это и означает существование равновесия по Нэшу в играх со смешанными стратегиями.

Говорят, в 1949 году Нэш рассказал фон Нейману о своей новой идее насчет равновесия для смешанных стратегий. Фон Нейман в своем стиле ответил: "Это, знаете ли, тривиально; это же всего лишь теорема о неподвижной точке". Позже Нэшу за это "тривиальное наблюдение" дали Нобелевскую премию (хотя, конечно, не только за него).

Совместные смешанные стратегии

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

Пример 1.9. Этот классический пример называется "Семейный спор" (по-английски звучит более внушительно: "Battle of the sexes"). Рассмотрим семью (пока что из двух человек), которая пытается решить, куда пойти вечером. Муж, разумеется, хочет идти на футбол, в то время как жена пытается вытащить мужа в театр. Но, несмотря на этот конфликт интересов, за семью можно быть спокойным: и муж, и жена хотят провести вечер вместе, и ни футбол, ни театр будут не в радость, если пойти туда одному. Осталось только сделать предположение (пожалуй, самое противоестественное), что муж и жена не обсуждают друг с другом свои решения, а просто сами по себе идут или на футбол, или в театр. У игры получается следующая матрица (строки выбирает муж, столбцы — жена; в векторе результатов первый компонент принадлежит мужу, второй — жене).

$$\begin{array}{r|rr} \sdt{Футбол} \sdt{Театр} \\ \hline \text{Футбол} (5, 2) (0, 0) \\ \text{Театр} (0, 0) (2, 5) \\ \end{array}$$

Как нетрудно заметить, у этой игры два равновесия Нэша:

$$(\text{Футбол}, \text{Футбол})\text{ и } (\text{Театр}, \text{Театр}).$$

Ни мужу, ни жене невыгодно отклоняться от одного из этих равновесий. Но вот первая беда: любое из них нечестное — если постоянно выбирать одну и ту же стратегию (а стимулов отклоняться-то нет), один супруг будет получать значительно большую выгоду, чем другой.

Можно попробовать решить эту игру в смешанных стратегиях. Сыграем за мужа: найдем для данной вероятности $$q$$ того, что жена пойдет на футбол, оптимальную вероятность $$p$$ пойти на футбол самому:

$$\text{E [выгода мужа]} = 5pq + 2(1-p)(1-q) = p(7q-2) + 2-2q.$$

Поскольку для жены ситуация абсолютно симметрична, понятно, что в точке $$p=\frac57$$, $$q=\frac27$$ (каждый выбирает свой любимый способ провести вечер с вероятностью $$\frac57$$ ) достигается равновесие в смешанных стратегиях, ведь ожидаемая выгода каждого участника не зависит от его стратегии. В итоге ожидаемая выгода и мужа, и жены оказывается равной $$p(7q-2)+2-2q = 2-\frac47 = \frac{10}7$$. Вот и вторая беда: использовать смешанные стратегии хуже, чем просто согласиться на "неподходящий" вариант: там выгода будет равна $$2$$, а тут всего $$\frac{10}7$$.

Конец примера 1.9.

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

Определение 1.7. Совместная смешанная стратегия игроков — это распределение вероятностей на всем множестве возможных чистых стратегий всех игроков $$\mathbf S$$ .

То есть, грубо говоря, муж и жена заранее договариваются: кто-то (возможно, кто-то третий — важно, что ни один участник не контролирует этот результат, но оба имеют к нему доступ) вечером подбросит монетку, и если выпадет орел, то они вместе пойдут в театр, а если решка — на футбол. В такой ситуации исход получается оптимальным: и точку $$(0,0)$$ выбирать никогда не придется, и равновесие честное, ведь у каждого участника ожидаемая выгода равна $$\frac72$$.

Определение 1.8. Равновесие в совместных смешанных стратегиях — это такое распределение вероятностей $$p$$ на множестве чистых стратегий $$\mathbf S$$, что для всех $$i\in\mathcal I$$ и любой пары векторов $$s_i, s^\prime_i\in \mathbf S$$

$$\sum\limits_{\mathbf s_{-i}}p(s_i,\mathbf s_{-i})u_i(s_i,\mathbf s_{-i}) \ge \sum\limits_{\mathbf s_{-i}}p(s_i,\mathbf s_{-i})u_i(s^\prime_i,\mathbf s_{-i}),$$

или, что то же самое,

$$\sum\limits_{\mathbf s_{-i}}p(s_i,\mathbf s_{-i})\left(\vphantom{1^2}u_i(s_i, \mathbf s_{-i}) - u_i(s^\prime_i, \mathbf s_{-i})\right)\ge 0.$$

То есть некое внешнее устройство выбирает стратегию $$\mathbf s\in\mathbf S$$ случайным образом по распределению $$p$$, и оказывается так, что для каждого из игроков в получившемся векторе невыгодно отклоняться от своей стратегии. В примере с семейным спором все выходит именно так: монетка определяет стратегию и мужа, и жены, но при этом выбор делается между двумя равновесиями Нэша, то есть любой случайно выбранный вектор получится равновесным. Совместные смешанные стратегии — это способ перейти от одного равновесия Нэша к линейной комбинации нескольких равновесий, если эта комбинация оказывается более выгодна агентам.

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

До сих пор мы рассматривали исключительно игры, в которых все агенты знали все на свете. Каждый агент знал функции выплаты $$u_i$$ других агентов, знал множества стратегий других игроков $$S_i$$. Более того, каждый агент знал, что каждый другой агент это знает, и что каждый другой агент знает, что он знает, что... в общем, понятно.

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

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

$$\begin{array}{r|rr} \sdt{Футбол} \sdt{Театр} \\ \hline \text{Футбол} (5, 2) (0, 0) \\ \text{Театр} (0, 0) (2, 5) \\ \end{array}$$

А если встречаться не хочет, то матрица становится другой:

$$\begin{array}{r|rr} \sdt{Футбол} \sdt{Театр} \\ \hline \text{Футбол} (5, 0) (0, 5) \\ \text{Театр} (0, 2) (2, 0) \\ \end{array}$$

Пусть муж ничего не знает о желаниях жены, и для него вероятности этих исходов равны 50%. Таким образом, с точки зрения мужа, у жены есть два возможных типа; или, что то же самое, есть два возможных равновероятных состояния мира, и только жена знает истинное состояние (этакая, простите за выражение, "жена Шредингера").

Если в такой ситуации муж решит пойти на футбол, то (в предположении о 50%) ему невыгодно будет менять свое предпочтение, ведь в случае футбола выгода получается $$\frac12\cdot 0 + \frac12\cdot 5 = \frac52$$, а в случае театра лишь $$\frac12\cdot 2 + \frac12\cdot 0 = \frac12$$. А для жены, очевидно, в такой ситуации выгодным будет идти на футбол, если она хочет встретить мужа, и идти в театр, если не хочет. Таким образом, профиль стратегий $$(\text{Футбол}, [\text{Футбол}, \text{Театр}])$$ будет находиться в равновесии Нэша.

Конец примера 1.10.

Более общая формулировка будет изрядно напоминать равновесие в совместных смешанных стратегиях. Но теперь придется немного дополнить модель самой игры. Определение 1.9 отличается от определения 1.1 только множествами типов $$\Theta_i$$.

Определение 1.9. Стратегическая игра с неполной информацией — это четверка

$$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{\Theta_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle,$$

где обозначения расшифровываются следующим образом:

$$\mathcal I=\{1,...,N\}$$ — конечное множество игроков.

$$\{S_i\}_{i\in\mathcal I}$$ — множество доступных игрокам действий.

$$\{\Theta_i\}_{i\in\mathcal I}$$ — множество типов игроков; для типов мы будем применять ту же нотацию, например

$$\theta_{-i} = (\theta_1,...,\theta_{i-1},\theta_{i+1},...,\theta_N).$$

Через $$\mathbf\Theta$$ будем обозначать множество векторов типов: $$\mathbf\Theta=\Theta_1\times\ldots\times\Theta_N$$. Каждому игроку $$i$$ известен его собственный тип $$\theta_i$$ и общее распределение $$p(\mathbf\Theta)$$, из которого берутся типы всех остальных; в частности, игрок $$i$$ знает

$$p(\mathbf\Theta_{-i}\mid \theta_i) = \frac{p(\theta_i,\mathbf\Theta_{-i})}{p(\theta_i)}$$.

$$\{u_i\}_{i\in\mathcal I}$$ — множество функций выплат $$u_i:\mathbf S\times\mathbf\Theta \to\mathbb R$$. Функции выплат теперь зависят не только от стратегий, но и от типов.

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

Определение 1.10. Равновесие по Байесу-Нэшу для стратегической игры с неполной информацией $$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{\Theta_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle$$ — это такой профиль стратегий $$s^*\in S$$, что для всякого агента $$i\in\mathcal I$$ и всякого его типа $$\theta_i\in\Theta_i$$ выполняется следующее условие:

$$s_i^*\in \arg\max\limits_{s^\prime_i\in S_i} \sum\limits_{\mathbf\Theta_{-i}}p(\mathbf\Theta_{-i}\mid\theta_i)u_i(s^\prime_i, \mathbf s_{-i}(\mathbf\Theta_{-i}), \theta_i, \mathbf\Theta_{-i}).$$

Очевидно (проверьте!), что любое равновесие в доминантных стратегиях является равновесием по Байесу-Нэшу.

Кроме уже описанных, нам в теории экономических механизмов потребуется и еще одно понятие равновесия, промежуточное между равновесием по Байесу-Нэшу и равновесием в доминантных стратегиях.

Определение 1.11. Равновесие ex post для стратегической игры с неполной информацией $$\langle \mathcal I, \{S_i\}_{i\in\mathcal I}, \{\Theta_i\}_{i\in\mathcal I}, \{u_i\}_{i\in\mathcal I}\rangle$$ — это равновесие по Байесу-Нэшу $$\mathbf s^*\in S$$, в котором дополнительно выполняется следующее условие: для всех $$i\in\mathcal I$$, всех $$\theta\in\Theta$$ и всех $$s^\prime_i\in S_i$$

$$u_i(\mathbf s^*(\theta), \theta) \ge u_i(\mathbf s^\prime_i, s_{-i}(\theta_{-i}), \theta).$$

Проще говоря, даже если агенту $$i$$ рассказать о том, какие типы были у всех остальных игроков, ему все равно не будет резона менять свое решение. Поэтому агенту $$i$$ гарантированно "не о чем жалеть" в результате игры: даже если он узнает то, чего не знал раньше, все равно для него $$s^*_i$$ останется оптимальной стратегией. Мы еще не раз встретимся с понятием ex post и другими моментами времени в течение игры в контексте аукционов; подробно эти понятия мы объясним в лекции 2.