1.7. Равновесие по Нэшу в смешанных стратегиях

Пример.

О р

о ((i,-i) (-i,i)' р u-м) (i,-i)

Рис. 21.

Легко видеть, что в этой игре нет равновесия по Нэшу в чистых стратегиях, так как в любой ситуации одному из игроков выгодно отклониться от выбранной стратегии. Однако, как мы увидим, пара смешанных стратегий а\ = ^ ,

(72 = ^ , в которых каждый из игроков играет свои чистые стратегии с равными вероятностями, образует равновесие по Нэшу в смешанных стратегиях.

Определение 1.7.1. Ситуация (набор смешанных стратегий) а = (<7j,..., сгп) является равновесием по Нэшу в игре

Г = {/, {Sj-}, {и^} , если для любого i = 1,..., п

иг(аг,а_г) > иг(а'г,а_г) V о'% G ?г.

Предложение 1.7.1. Пусть Sf С Si — множество чистых стратегий, которые игрок i играет с положительной вероятностью в ситуации а = (<7i,..., ап) . Ситуация а является р.Н. в смешанном расширении Г игры Г тогда и только тогда, когда для всех i = 1,... ,п (1)

Ui(si,a_i) = ut(s't,Ui(si,a_i) > ut(s't,Доказательство. Необходимость. Если бы одно из этих условий не выполнялось для некоторого i, то нашлись бы две стратегии G Sf и s[ G Si : Ui(s[, (Т_г) > Ui(si, (Т_г) , a значит, это не р.Н.

Достаточность. Предположим теперь, что (1) и (2) выполнены, но а — не р.Н. Тогда существуют игрок i и стратегия а[ такие, что

иг(а[, ст_г) > щ(аг, ст_г).

Но если это так, то существует чистая стратегия s[ , которая играется с положительной вероятностью при а[ и для которой Ui{s[,(j-i) > щ(аг, ст_г) .

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

Это свойство можно использовать для нахождения смешанного равновесия по Нэшу (т.е. равновесия по Нэшу в смешанных стратегиях). Пример. Рассмотрим следующую игру (рис.22):

А В

A f (1000,1000) (0,0) \ В V (0,0) (100,100) )

Рис. 22.

Очевидно, что ситуации (А,А) и (В,В) являются равновесными по Нэшу (в чистых стратегиях). Найдем равновесия по Нэшу в смешанных стратегиях. Предположим, что в таком равновесии игрок 1 играет смешанную стратегию (р, 1 — р), а второй — (q, 1 — q) , причем 0 < p,q < 1.

Тогда, учитывая приведенное предложение, мы получаем, что ожидаемый выигрыш игрока 2 от игры А есть ЮООр + 0(1 — р) , а от игры В есть 100 • (1 — р) + Ор, а значит,

ЮООр + (1 - р) ? 0 = 100 • (1 - р) + 0 • р.

Отсюда 1100р = 100 и, следовательно, р= 1/11. Аналогично q = 1/11. Заметим, что в соответствии с предложением 1.7.1 у игроков в данном примере нет предпочтений относительно вероятностей, которые они приписывают своим стратегиям. Эти вероятности определяют «равновесное рассмотрение»: необходимость сделать другого игрока безразличным относительно его стратегий.

Пример. Вернемся к игре «Семейный спор». Поступая, как и в предыдущем примере, мы получаем, что Она, играя «Ф», получает 1-р+0(1— р) , а играя «Б», получает 0-р+2(1— р) . Следовательно, 2(1 —р) = р . Отсюда Зр = 2 , а следовательно, р = 2/3 . Аналогично получаем 2q + (1 — q) ? 0 = 0 • q + (1 — q)l, а значит, 3q = 1 и q = 1/3. Таким образом, в смешанном равновесии Он играет «Ф» с вероятностью 2/3, а Она играет «Ф» с вероятностью 1/3.

Замечание 1.7.1.

чистых стратегий независимо. Иными словами, мы можем считать, например, что Природа передает игрокам индивидуальные, независимо распределенные сигналы (01, 02, ? ? ?, вп) G [0,1] X [0,1] X ... X [0,1], а каждый игрок i принимает решение в зависимости от различных возможных реализаций его сигнала О; .

Предположим, однако, что есть некий общий сигнал в G [0,1], который могут наблюдать все игроки. В этом случае появляются новые возможности. Так, к примеру, в упомянутой только что игре «Семейный спор» оба игрока могут, например, решить идти на футбол, если, скажем, 0 < ^ , и идти на балет, если 0 > ^ . Выбор стратегии каждым игроком остается случайным, тем не менее здесь мы имеем дело со вполне скоординированными действиями (Он и Она оказываются вместе), явно имеющими равновесный характер, причем если один игрок решает следовать этому правилу, то и для второго оптимально придерживаться этого же правила. Это дает нам пример коррелированного равновесия (совместного равновесия)9, введенного Р. Ауманом (Aumann, 1974).

Формально такое равновесие — это специальный случай равновесия по Байесу-Нэшу, которое мы рассмотрим в главе 3.

Далее мы приведем важные результаты о существовании равновесий по Нэшу.

Предложение 1.7.2. В смешанном расширении Г любой игры Г с конечными множествами стратегий Si,...,Sn существует равновесие по Нэшу в смешанных стратегиях.

Это предложение непосредственно следует из следующего более общего результата, так как в игре Г множества стратегий игроков — это симплексы в соответствующем пространстве Мм . Теорема 1.7.1. Debreu, 1952; Glicksberg, 1952; Fan Ky, 1952)10. Если для каждого i = 1,..., п (1)

Si — непусто, выпукло и компактно (в некотором Мм); (2)

Ui(si,..., sn) — непрерывна по (si,...,sn) и квазиво- гнута по Si,

то в игре Г = {/, {Si}, {иг}} существует равновесие по Нэшу в чистых стратегиях.

Напомним, что функция / : —> IR называется квазивогнутой, если для любого а множество {х : f(x) > а} выпукло.

Доказательство этого предложения опирается на следующую лемму.

Лемма 1.7.1.

Доказательство леммы 1.7.1. Во-первых, заметим, что bi(s_i) —это множество тех стратегий г-го игрока, которые максимизируют на компакте Si. Его непу

стота следует из непрерывности иг-. Выпуклость множества bi(s_i) следует из квазивогнутости функции иг(-, s_8). Чтобы проверить полунепрерывность сверху, мы должны показать, что для любой последовательности (s^, s^J —> такой,

что sG bi^s^^yk, мы имеем G b(s_i) . Заметим, что Ук

ui(si,s-i) > ui(si,s-i) V s'i ? • В силу непрерывности иг(-), Ui(si, 5_г) > Ut(s't, S_i) .

Доказательство Теоремы. Определим отображение b : S —> S формулой

b(s1, ...,sn) = bi(s_i) X b2{s-2) X • • • X b(s_n).

Ясно, что b(-) —многозначное отображение S = S\X - ? -xSn в себя. По лемме &(•) непусто, выпукло-значно, полунепрерывно сверху. Следовательно, по Т.Какутани о неподвижной точке, существует неподвижная точка, т.е. набор стратегий s ? S : s G b(s) . Этот набор стратегий является равновесием по Нэшу, т. к. по построению

Si G bi(s-i) V г = 1,..., п.

Пример. «Голосование». Рассмотрим следующую ситуацию — три игрока 1, 2, 3 и три альтернативы — A, D , С.

Игроки голосуют одновременно за одну из альтернатив, воздержаться невозможно. Таким образом, пространство стратегий Si = {А, В, С}. Альтернатива, получившая большинство, побеждает. Если ни одна из альтернатив не получает большинства, то выбирается альтернатива А. Функции выигрышей таковы:

щ(А) = и2(В) = и3(с) = 2, щ(В) = и2(С) = и3(А) = 1, и1(С) = и2(А) = и3(В) = 0.

В этой игре три равновесных исхода12 (в чистых стратегиях): А , В и С . Теперь посмотрим на равновесия (их больше 3): если игроки 1 и 3 голосуют за А, то игрок 2 не изменит исход, как бы он ни голосовал, и игроку 3 безразлично, как он голосует.

(А, А, А) и (А, В, А) — р.Н., но (А, А, В) — не р.Н., т.к. второму лучше голосовать за В .