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

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

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

Рис. 21.

Легко видеть, что в этой игре нет равновесия по Нэшу в чистых стратегиях, так как в любой ситуации одному из игроков выгодно отклониться от выбранной стратегии. Однако, как мы увидим, пара смешанных стратегий 1 = (1/2, ½), 2 = (1/2, ½), в которых каждый из игроков играет свои чистые стратегии с равными вероятностями, образует равновесие по Нэшу в смешанных стратегиях.

Определение 1.7.1 Ситуация (набор смешанных стратегий)  = (₁, .., _n) является равновесием по Нэшу в игре = {I, {_i}, {u_i}}, если для любого i = 1, …, n

Предложение 1.7.1 Пусть S⁺_i S_i — множество чистых стратегий, которые игрок i играет с положительной вероятностью в ситуации )  = (₁, .., _n). Ситуация  является р.Н. в смешанном расширении игры Г тогда и только тогда, когда для всех i = 1,. . . , п

Доказательство. Необходимость. Если бы одно из этих условий не выполнялось для некоторого i, то нашлись бы две стратегии s_i S⁺_i и s'_iSi : , а значит, это не р.Н.

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

Но если это так, то существует чистая стратегия s’_i , которая играется с положительной вероятностью при ’_i и для которой . Так как для любой s_i S⁺_i, это противоречит (1) и (2).

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

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

Пример. Рассмотрим следующую игру (рис.22).

Рис. 22.

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

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

1000р + (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 + (l  q)l , а значит 3q = 1 и q = 1/3 . Таким образом, в смешанном равновесии Он играет "Ф" с вероятностью 2/3 , а Она играет "Ф" с вероятностью 1/3 .

Замечание 1.7.1. В определении смешанного расширения или равновесия в смешанных стратегиях мы предполагаем, что игроки осуществляют рандомизацию своих чистых стратегий независимо. Иными словами, мы можем считать, например, что Природа передает игрокам индивидуальные, независимо распределенные сигналы (1, 2, …, n)  [0,1]x [0,1]x ...x[0,1] , а каждый игрок i принимает решение в зависимости от различных возможных реализаций его сигнала i.

Предположим, однако, что есть некий общий сигнал [0,1] , который могут наблюдать все игроки. В этом случае появляются новые возможности. Так, к примеру, в упомянутой только что игре "Семейный спор" оба игрока могут, например, решить идти на футбол, если, скажем, < 1/2 , и идти на балет, если  1/2 . Выбор стратегии каждым игроком остается случайным, тем не менее здесь мы имеем дело со вполне скоординированными действиями (Он и Она оказываются вместе), явно имеющими равновесный характер, причем если один игрок решает следовать этому правилу, то и для второго оптимально придерживаться этого же правила. Это дает нам пример коррелированного равновесия (совместного равновесия)¹³, введенного Р.Ауманом (Auman (1974)).

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

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

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

Это предложение непосредственно следует из следующего более общего результата, так как в игре множества стратегий игроков — это симплексы в соответствующем пространстве R^M .

Теорема 1.7.1 Debreu (1952), Glicksberg (1952), Fan Ky (1952)¹⁴. Если для каждого i = 1,. . . , п

(1) S_i — непусто, выпукло и компактно (в некотором R^M);

(2) u_i(s₁,. . ., s_n) — непрерывна по (s;,. . ., s_n) и квазивогнута по s;,

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

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

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

Лемма 1.7.1 Если выполнены условия Теоремы 1.7.1, то отображение лучших ответов b_i непусто, выпуклозначно (т. е. множества b_i(s_-i) — непусты и выпуклы) и полунепрерывно сверху¹⁵.

Доказательство леммы 1.7.1. Во-первых заметим, что b_i(s_-i) — это множество тех стратегий i-го игрока, которые максимизируют ui(,s_-i) на компакте Si . Его непустота следует из непрерывности Ui . Выпуклость мно­жества bi(s-i) следует из квазивогнутости функции ui(-,s_;). Чтобы проверить полунепрерывность сверху, мы должны показать, что для любой последовательно­сти: (sf,s^) — > (s;,s_;), такой что sf G bi(s^_i)\/k мы имеем Si G 6(s_;) . За­метим, что VA; Ui(s^s^) > Ui(s',s^) V s' G Si . В силу непрерывности u;(-) , u₄(s₄,s_₄) > u₄(s',s_₄).

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

6(si, . . . , s_n) = 6i(s_i) x 62(5-2) x • • • x b(s__n)

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

Si G bi(s-i) V г = 1, . . . , п. Справедлива также следующая теорема.

Теорема 1.7.2 (Glicksberg (1952)). Если в игре Г множества Si стратегий игроков являются непустыми компактными подмножествами метрического пространства, а функции выигрышей Ui непрерывны, то существует равновесие по Нэшу в смешанных стратегиях.

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

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

u₁(А) = и₂(В) = и₃(с) = 2,

u₁(B) = и₂(С) = и₃(А) = 1,

u₁(С) = и₂(А) = и₃(В) = 0.

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