В играх с ненулевой суммой в выигрыше или проигрыше могут оказаться все участники игры. Биматричная игра – это конечная игра двух игроков с ненулевой суммой. В этом случае для каждой игровой ситуации A i B j каждый из игроков имеет свой выигрыш a ij для первого игрока и b ij – для второго игрока. К биматричной игре сводится, например, поведение производителей на рынках несовершенной конкуренции. С помощью онлайн-калькулятора можно найти решение биматричной игры , а также ситуации оптимальные по Парето и ситуации устойчивые по Нэшу .

Рассмотрим конфликтную ситуацию, в которой каждый из двух участников имеет следующие возможности для выбора своей линии поведения:

• игрок А – может выбрать любую из стратегий А 1 ,…,А m ,
• игрок В – любую из стратегий В 1 ,…,В n .

При этом их совместный выбор оценивается вполне определённо: если игрок А выбрал i-ю стратегию А i , а игрок В – k -ю стратегию В k , то в итоге выигрыш игрока А будет равен некоторому числу a ik , а выигрыш игрока В некоторому, вообще говоря, другому числу b ik .
Последовательно перебирая все стратегии игрока А и все стратегии игрока В, мы сможем заполнить их выигрышами две таблицы.

Первая из таблиц описывает выигрыш игрока А, а вторая – выигрыш игрока В. Обычно эти таблицы записывают в виде матрицы.
Здесь А – платёжная матрица игрока А, В – платёжная матрица игрока В.

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

Равновесие Нэша – равновесие, когда каждый участник игры выбирает стратегию, которая является для него оптимальной при условии, что остальные участники игры придерживаются определенной стратегии.
Равновесие Нэша не всегда является наиболее оптимальным для участников. В этом случае говорят, что равновесие не является Парето-оптимальным .
Чистая стратегия – определенная реакция игрока на возможные варианты поведения других игроков.
Смешанная стратегия – вероятностная (не определенная точно) реакция игрока на поведение других игроков.

Пример №1 . Борьба за рынки сбыта.
Фирма а намерена сбыть партию товара на одном из двух рынков, контролируемых более крупной фирмой b . С этой целью она проводит подготовительную работу, связанную с определенными затратами. Если фирма b разгадает, на каком из рынков фирма а будет продавать свой товар, она примет контрмеры и воспрепятствует "захвату" рынка (этот вариант означает поражение фирмы а); если нет, то фирма а одерживает победу. Предположим, что для фирмы а проникновение на первый рынок более выгодно, чем проникновение на второй, но и борьба на первом рынке требует от нее больших средств. Например, победа фирмы а на первом рынке приносит ей вдвое большую прибыль, чем победа на втором, но зато поражение на первом рынке полностью ее разоряет.
Составим математическую модель этого конфликта, считая фирму а игроком 1 и фирму b игроком 2. Стратегии игрока 1: А 1 – проникновение на рынок 1, А 2 – проникновение на рынок 2; стратегии игрока 2: В 1 – контрмеры на рынке 1, В 2 – контрмеры на рынке 2. Пусть для фирмы а ее победа на 1-м рынке оценивается в 2 единицы, а победа на 2-м рынке – в 1 единицу; поражение фирмы а на 1-м рынке оценивается в -10, а на 2-м в -1. Для фирмы b ее победа составляет соответственно 5 и 1 единицу, а поражение -2 и -1. Получаем в итоге биматричную игру Г с матрицами выигрышей
.
По теореме эта игра может иметь либо чистые, либо вполне смешанные ситуации равновесия. Ситуаций равновесия в чистых стратегиях здесь нет. Убедимся теперь, что данная игра имеет вполне смешанную ситуацию равновесия. Находим , .
Итак, рассматриваемая игра имеет единственную ситуацию равновесия , где , . Она может быть реализована при многократном повторении игры (то есть при многократном воспроизведении описанной ситуации) следующим образом: фирма а должна использовать чистые стратегии 1 и 2 с частотами 2/9 и 7/9, а фирма b – чистые стратегии 1 и 2 с частотами 3/14 и 11/14. Любая из фирм, отклонившись от указанной смешанной стратегии, уменьшает свой ожидаемый выигрыш.

Пример №2 . Найти ситуации оптимальные по Парето и ситуации устойчивые по Нэшу для биматричной игры.

Пример №3 . Имеются 2 фирмы: первая может произвести одно из двух изделий А 1 и А 2 , вторая – одно из двух изделий B 1 , B 2 . Если первая фирма произведет продукцию A i (i = 1, 2), а вторая - B j (j = 1, 2), то прибыль этих фирм (зависящая от того, являются ли эти изделия взаимодополняющими или конкурирующими), определяется таблицей №1:

	В 1	В 2
А 1	(5, 6)	(3, 2)
А 2	(2, 1)	(5, 3)

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

Определение 2.10. Пусть задана игра G в нормальной форме (N,Sj , Исход s = (s, s 2 > > %)е5 называется равновесием

Нэша (NE - Nash Equilibrium) игры G, если Vi е 1.....N, Уу, е 5,

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

на множестве своих стратегий.

В точке равновесия Нэша стратегия х,- - одна из лучших для игрока i стратегий в ответ на х_ ; =(х 1 ,х 2 ,--.,^_ 1 ,х 1+1 ,...,х лг) - стратегии остальных игроков. Игрок i рассматривает стратегии из х_ ; как заданную вполне определенную совокупность стратегий «внешнего мира», на которую он не может активно воздействовать. Он может активно выбирать лишь свою стратегию в, которая будет наилучшим выбором, если остальные игроки выберут s_j. При этом игрок i полагает, что аналогично выбирают свои стратегии и все остальные игроки.

В точке равновесия Нэша игроку i невыгодно в одиночку отклоняться от стратегии s it если остальные игроки придерживаются стратегий 5 1 ,s 2 ,...s,-_ 1 ,s i+1 ...s N . Действия «в одиночку» могут только уменьшить выигрыш игрока i. Поиск точки равновесия Нэша, таким образом, сводится к решению системы из N задач максимизации функций полезности по соответствующим переменным

Пусть G - (N, 5,-, Uj , i - 1,..N) - конечная игра в нормальной форме.

Назовем X,- множеством смешанных стратегий игрока i, а множество X = X,-Х 2 -...-X jV - множеством профилей всех смешанных стратегий. Обозначим аеХ - элементы этого множества.

Назовем игру G = (N; X; и) смешанным расширением игры G. Тогда равновесие в смешанных стратегиях в игре G - это равновесие Нэша в ее смешанном расширении.

Пример 2.17. Задана биматричная игра

Какие выигрыши будут у игроков при выборе ими стратегий т = 0,а + 0,6Ь и п = 0,25с + 0,75d ?

Решение

Запишем рядом с чистыми стратегиями вероятности их выбора:

Поскольку выбор стратегий осуществляется игроками независимо, вероятность профиля (а; с) равна 0,4-0,25 = 0,1. Аналогично рассчитываются вероятности выигрышей игроков при остальных наборах чистых стратегий. Для удобства выигрыши игроков представим в виде вектор-столбца:

Ответ: щ - 2; и 2 = 0,25.

Наряду с равновесием Нэша введем еще одно важное понятие - доминирования по Парето.

Пусть задана игра в нормальной форме G = (N,Si, u it i = l,...,N). Рассмотрим два профиля стратегий x = (x,x 2 ,...,x jY)e5 и i/ = (i/ v i/ 2 ,...,yy)&S.

Определение 2.11. Профиль стратегий х доминирует по Парето профиль стратегий у, если

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

Определение 2.12. Профиль стратегий х называется оптимальным по Парето (Парето-оптимальным), если он недоминируем но Парето.

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

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

Решение

Очевидно, ни одна из стратегий не является строго доминируемой. Поэтому равновесия в строго доминирующих стратегиях нет.

Для определения равновесий Нэша подчеркнем наибольшие выигрыши каждого из игроков при фиксированных ходах противника:

Исходы с двойными подчеркиваниями будут равновесиями Нэша: (a; d) (b; с); (b;d ).

Для определения Парето-оптимальных исходов удобно изобразить все точки биматричной игры в критериальной плоскости (рис. 2.21 - по осям откладываем выигрыши игроков).

Рис. 2.21

Парето-оптимальными являются точки, в направлении штриховки от которых (к «северо-востоку») нет других точек. Таковыми являются исходы (а ; d) (а; с); (Ь; с). Введем для краткости обозначения для Парето- оптимальных точек - Р и для равновесных по Нэшу - N. Получим

Выясним, существуют ли в этой игре равновесные по Нэшу профили смешанных стратегий.

Пусть стратегии а и b играются с вероятностями р и 1 - р соответственно, а стратегии с и d - с вероятностями q и 1 - q.

Максимизируем функцию щ(р, q) = 3q - 2pq по переменной р е при постоянном значении q

К аналогичному результату приводит рассмотрение рационального поведения второго игрока, оптимизирующего u 2 (p,q ) по переменной q при постоянном значении р

Изобразим полученный результат (рис. 2.22) в координатах (q, р ):

Рис. 2.22

Как видим, оба графика совпали.

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

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

Решение

Очевидно, доминирующих стратегий в игре нет. Точек равновесия Нэша в чистых стратегиях также нет. Парето-оптимальные профили: (а ; d) и {b d).

Рассмотрим смешанные стратегии игроков.

Пусть стратегии а и b играются с вероятностями р и 1 - р соответственно, а стратегии cud - с вероятностями q и 1 - q. Запишем матрицу ожидаемых выигрышей первого и второго игроков:

Очевидно, первый игрок решает задачу

Решением задачи является

Эти три случая представлены на рис. 2.23.

Рис. 2.23

Аналогично второй игрок решает задачу Решением задачи является

Эти три случая представлены на рис. 2.24.

Рис. 2.24

Совмещая рисунки, получим рис. 2.25.

Рис. 2.25

Точка N (р = 0,75; q = 0,6), очевидно, является точкой равновесия Нэша в смешанных стратегиях, поскольку она получена в результате решения задач максимизации функции u x (p,q ) пори u 2 (p,q) по q.

Ответ: равновесие Нэша:

Как соотносятся между собой решения игр в чистых стратегиях, полученные методом итерационного исключения строго доминируемых стратегий (если они существуют) и равновесий Нэша? Ответ на этот вопрос дают следующие две теоремы.

Теорема 2.3. Если существует процедура итерационного исключения строго доминируемых стратегий в игре G - (S ;, щ;i - 1,...,N), которая приводит к единственному исходу s = (s i ,s 2 ,...,s N), то этот исход является единственным равновесием Нэша.

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

Замечание. Если в теореме 2.3 исключить слово «строго», то она перестает быть справедливой. Например, в игре

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

Теорема 2.4. Если исход явля

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

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

Пример 2.20. Рассмотрим матричную игру:

Точка равновесия Нэша - (а,х). Однако стратегия а первого игрока доминируема (не строго) стратегией с, а стратегия х второго игрока доминируема стратегией у. Тем самым мы показали, что условие строгой доминируемое™ в теореме существенно.

Пример 2.21. Рассмотрим игру двух игроков, называемую «битва полов» (или «семейный спор»). Саша и Маша пытаются решить, как им проводить выходной день, - пойти на футбол или на балет. Конечно, Саше больше хочется пойти на футбол, Маша же получает большее удовольствие от балета. Но совсем никакого удовольствия они не получат, если будут развлекаться порознь (бывает же такое!). Саша и Маша выбирают место развлечения одновременно и независимо друг от друга, не сговариваясь. Матрица выигрышей имеет следующий вид :

В данной игре исход (Футбол; футбол) является точкой равновесия Нэша. Это значит, что если игроки договорились о выборе каждым из них первой стратегии, то ни одному из них невыгодно будет отклоняться от нее, если другой ее придерживается. Аналогично и исход (Балет; балет) будет точкой равновесия Нэша. Рассмотрим теперь возможность выбора игроками смешанных стратегий. Пусть первый игрок (Саша) выбирает первую и вторую чистые стратегии с вероятностями соответственно р и 1 - р. Второй игрок (Маша) выбирает первую и вторую чистые стратегии с вероятностями соответственно q и 1 -q. Получаем матрицу

Выигрыш Саши равен

Стратегия Саши определяется выбором вероятности р. Функция выигрыша Саши и с (р, q) р ,

если , и, следовательно, приСаша выберет максимальное значение вероятности, т.е.р = 1.

Аналогично если, то функция u c (p,q) - убывающая по переменной/;, и, следовательно, при Саша, максимизируя свой выигрыш, выберет минимальное значение вероятности, т.е. р = 0.

При функция и с (р> q) не зависит от р и Сашу удовлетворяет любое значение р е . Таким образом, имеем

Все сказанное наглядно представляется диаграммой (рис. 2.26).

Рис. 2.26

Выигрыш Маши равен

Стратегия Маши определяется выбором вероятности q. Функция выигрыша Маши u M (p,q) является монотонно возрастающей по переменной q,

если , и, следовательно, приМаша выберет максимальное значение вероятности, т.е.q = 1.

Аналогично если , то функция u M (p,q) - убывающая по переменной q, и, следовательно, приМаша выберет минимальное значение

вероятности, т.е.

При функция и и (р, q) не зависит от q и Машу удовлетворяет

любое значение

Все сказанное наглядно представляется диаграммой (рис. 2.27). Совмещение диаграмм на рис. 2.26 и 2.27 дает три точки пересечения наилучших выборов игроков на всевозможные действия другого игрока (рис. 2.28).

Имеем три точки равновесия Нэша. Первые

две из них соответствуют выбору чистых стратегий (Балет; балет) и (Футбол; футбол). Третья точка представляет собой точку равновесия Нэша в смешанных стратегиях.

Заметим, что значения платежных функций обоих игроков в точке В соседней точке, например , значения платежных функций игроков равны Однако

эта точка не будет точкой равновесия, поскольку если Маша будет придерживаться стратегии , то Саше будет более выгодна стратегия р = 1,

поскольку

Рис. 2.27

Пример 2.22. Рассмотрим пример биматричной игры, в которой существует бесконечно много равновесий 11эша:

Выигрыш первого игрока равен

р получим

Графически этот выбор изображается следующим образом (рис. 2.29).

Рис. 2.29

q вторым игроком. Но первый игрок не знает, каков выбор второго игрока. Он лишь знает, что второй игрок будет также максимизировать свою функцию выигрыша по переменной q.

Выигрыш второго игрока равен

Из условия максимизации функции выигрыша по переменной q получим

Графически этот выбор изображается следующим образом (рис. 2.30).

Рис. 230

Совместим графики на рис. 2.29 и 2.30 (рис. 2.31).

Рис. 2.31

Графики совпадают на отрезке АВ и в начале координат. Все эти точки и будут равновесиями Нэша в смешанных стратегиях. Точка p = q = 0 означает выбор профиля чистых стратегий (b;d ). Поэтому получим: NE:{(b;d), (pa + (l-p)b ; с), ре }.

Следующая теорема дает ответ на вопрос о существовании равновесия Нэша в довольно широком классе игр.

Теорема 2.5 (Нэш, 1950). Для любой конечной игры (т.е. множество игроков и множества их чистых стратегий конечны) в нормальной форме G = (N,S jt Uj,i = 1,..., N) всегда существует по крайней мере одна точка равновесия Нэша, возможно, в смешанных стратегиях.

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

Пример 2.23. Дана биматричная игра:

Найти все равновесия Нэша в смешанных стратегиях.

Решение

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

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

Очевидно, никакая смешанная стратегия ра + (1- р)Ь не сможет доминировать чистую стратегию с, поскольку неравенство /?-0 + (1-/?)-2>14 невыполнимо ни при каких значениях р е . Значит, стратегия с не может быть строго доминируема даже с применением смешанных стратегий.

Как было доказано выше, величина f(p) = p-A + (l-p) B при /?е, {А и В - действительные числа) может принимать все значения между числами А и В. Действительно, поскольку /(/?) - линейная функция, то множеством ее значений является отрезок E(f) = .

Аналогично стратегия а не может быть доминируема смешанной стратегией pb + (l-р)с, поскольку (при выборе вторым игроком стратегии е) потребуется выполнение неравенства 4/?+ 4(1-/?) >6.

Предполагая, что смешанная стратегия pa + (1 - р)с может строго доминировать чистую стратегию Ь, также получим невыполнимое неравенство 2/?+ 4(1-/?) >8.

Следовательно, в данной игре не существует строго доминируемых стратегий первого игрока.

Рассмотрим стратегии второго игрока. Выпишем матрицу его выигрышей:

Очевидно, стратегии ей/ недоминируемы. Поскольку 2 е , 1 е , то можем предположить, что существует смешанная стратегия qe + (l-q)f, строго доминирующая чистую стратегию d. Проверим наше предположение. Для этого требуется выполнение системы неравенств:

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

видно, что смешанная стратегия строго доминирует стратегию d.

Важно понимать, что не только второй игрок исключает стратегию d, но и первый игрок, поставив себя на место второго и выполнив за него все указанные операции, может прийти к вывод}" об исключении стратегии d.

Вычеркнув первый столбец, получим матрицу

Нетрудно увидеть, что в этой матрице смешанная стратегия первого

игрока строго доминирует стратегию с (это стало очевидным только

после исключения стратегии d). Игра сократилась до биматричной игры размерности 2x2:

Теперь е>/. Получим

И наконец, а >- Ь.

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

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

5) Пусть первый игрок играет смешанную стратегию рА + ( 1 - р)С, а второй - qE + (-q)F.

Выигрыш первого игрока равен

Из условия максимизации функции выигрыша по переменной р получим

Графически этот выбор изображается следующим образом (рис. 2.32).

Рис. 2.32

Это наилучшее для первого игрока действие, зависящее от выбора вероятности q вторым игроком.

Выигрыш второго игрока равен

Из условия максимизации функции выигрыша по переменной q получим Графически этот выбор изображается следующим образом (рис. 2.33).

Рис. 2.33

Совместим графики на рис. 2.32 и 2.33 (рис. 2.34).

Рис. 2.34

Графики совпадают в трех точках. Эти точки и будут определять равновесия Нэша:

Пример 2.25. Найти все равновесия Нэша в смешанных стратегиях в биматричной игре

Решение

Способ 1. Нетрудно видеть, что в данной игре не существует строго доминируемых стратегий. Введем смешанные стратегии игроков:

Выигрыш первого игрока максимизируем по переменной р:

Выигрыш второго игрока максимизируем по переменным q и г.

Рассмотрим различные значения р (рис. 2.35).

Рис. 235

Случай 1. Пусть р 0,5. Тогда из (2) и (3) получим р - 0. Итак, (р = ();q = 0;г = 1) - равновесие Нэша. Это исход (b, d).

Случай 2. Пусть р = 0,5. Тогда из (2) получим q = 0, а из (1) 5г= 3, или г = 0,6. Следовательно, (р = 0,5; q = 0; г = 0,6) - равновесие Нэша. Это исход (0,5а + 0,56, 0,6d + 0,4е).

Случай 3. Пусть р е (0,5; 1). Тогда из (2) и (3) получим q = 0; г= 0. Но тогда из (1) имеем р = 1, что противоречит исходному условию.

Случай 4. Пусть р = 1. Тогда из (3) получим г = 0, а из (1) q 3, что выполняется при всех допустимых q. Итак, (р = 1; е;г = 0) - равновесия Нэша. Это исходы (a, qc + (-q)e), qe[ 0; 1].

Ответ: (6, d) (0,5а + 0,56, 0,6с/ + 0,4с); (a,qc + (-q)e), ^е.

Покажем еще один способ нахождения равновесий Нэша в таких играх.

Способ 2 (решения примера 2.25). Рассмотрим выигрыши второго игрока при условии выбора первым игроком смешанной стратегии ра + (-р)Ь. Выигрыш второго игрока при выборе им чистой стратегии с равен U - 3 р при выборе чистой стратегии d - = р + 3(- р)] при выборе чистой стратегии е - U? 2 =Зр + (-р).

Построим графики функций выигрыша второго игрока (рис. 2.36).

Рис. 2.36

Случай 1. Пусть р d. Но наилучшим ответом первого игрока на стратегию второго d является чистая стратегия b (2 > 0), т.е. р- 0, что удовлетворяет исходному условию р 0,5. Следовательно, (b , d) - равновесие Нэша.

Случай 2. Пусть р е (0,5; 1). Тогда второй игрок выбирает чистую стратегию е. Но наилучшим ответом первого игрока на стратегию второго е является чистая стратегия а (4 > 1), т.е. р = 1, что не удовлетворяет исходному условию. В данном промежутке нет равновесий Нэша.

Случай 3. Пусть р = 0.5. Тогда вторым игроком не будет играться стратегия с, г.е. q - 0. Рассмотрим игру

Математическое ожидание выигрыша первого игрока равно

Значение р = 0,5 может быть наилучшим ответом на смешанную стратегию второго игрока только при г = 0,6. Тогда исход (0,5а + 0,56, 0,6d + + 0,4с) - равновесие Нэша.

К тому же результату мы придем и из других рассуждений. А именно, для первого игрока значение р = 0,5 возможно только в случае его безразличия к выбору стратегии а или Ь. Э го значит:

Случай 4. Пусть р= 1. Тогда вторым игроком не будет играться стратегия d, т.е. г = 0. Матрица принимает вид

Тогда (a, qc + (1 - q)e) - равновесие Нэша при любых

Пример 2.26. Найти все равновесия Нэша в смешанных стратегиях в биматричной игре

Решение

Рассмотрим выигрыши второго игрока при использовании им чистых стратегий в ответ на смешанную стратегию первого игрока:

Построим графики этих функций (рис. 2.37).

Рис. 2.37

В точке А пересекаются прямые d не. Найдем точку пересечения:

В точке В пересекаются прямые сие. Найдем точку пересечения:

Ломаная линия MABN - наилучший ответ второго игрока при различных значениях р. Рассмотрим несколько случаев.

Случай 1:

чистая стратегия d. d й, что соответствует значению b, d).

Случай 2: . Тогда наилучшим ответом второго игрока является

чистая стратегия е. Но наилучшим ответом первого игрока на чистую стратегию е второго игрока является чистая стратегия а , что соответствует значению . В этом промежутке нет равновесий Нэша.

Случай 3: . Тогда наилучшим ответом второго игрока является

чистая стратегия с. Но наилучшим ответом первого игрока на чистую стратегию с второго игрока является чистая стратегия а , что соответствует значению . В этом промежутке получили единственное равновесие Нэша (а } с).

Случай 4: (точка Л). В этой точке заведомо не играется стратегия с. Матрица игры принимает вид

Рассмотрим математическое ожидание выигрыша первого игрока:

При равновесном по Нэшу исходе первый игрок максимизирует по р свою функцию полезности:

Очевидно, если является оптимальным для первого игрока, то

. Это значение можно получить из условия равенства значений функции выигрыша первого игрока при выборе им а и /;. Иными словами, первому игроку безразлично, выберет он а или b :

Следовательно, профиль стратегий является равно

весием Нэша.

Случай 5: (точка В). В этой точке заведомо не играется стратегия d. Матрица игры принимает вид

Поскольку а >- b , то р = 1 , что противоречит исходному условию Следовательно, не существует равновесия Нэша, при котором второй игрок выбирает

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

• Здесь и далее в аналогичных примерах стратегии Саши (Футбол, Балет) обозначенысловом, начинающимся с заглавной буквы, стратегии Маши - со строчной.

February 10th, 2015

Давайте быстро поделим 100$. Вы и я решаем, сколько из сотни мы требуем и одновременно озвучиваем суммы. Если наша общая сумма меньше ста, каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги?

Существует единственный выигрышный ход.

Для начала по научному:

Равновесие Нэша (англ. Nash equilibrium ) названо в честь Джона Форбса Нэша - так в теории игр называется тип решений игры двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив своё решение в одностороннем порядке, когда другие участники не меняют решения. Такая совокупность стратегий выбранных участниками и их выигрыши называются равновесием Нэша.

Концепция равновесия Нэша (РН) впервые использована не Нэшем; Антуан Огюст Курно показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Соответственно, некоторые авторы называют его равновесием Нэша-Курно . Однако Нэш первым показал в своей диссертации по некооперативным играм в 1950-м году, что подобные равновесия должны существовать для всех конечных игр с любым числом игроков. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947).

А теперь решение задачки, которая была представлена в начале поста:

Требование 51 $ даст вам максимальную сумму независимо от того, что выберет ваш противник. Если он попросит больше, вы получите 51 $. Если он попросит 50 $ или 51 $, вы получите 50 $. И если он попросит меньше 50 $, вы получите 51 $. В любом случае нет никакого другого варианта, который принесет вам больше денег, чем этот. Равновесие Нэша - ситуация, в которой мы оба выбираем 51 $.

А теперь немного об этом человеке:

Джон Нэш родился 13 июня 1928 г. в Блюфилде, штат Вирджиния, в строгой протестантской семье. Отец работал инженером в компании Appalachian Electric Power, мама до замужества успела 10 лет проработать школьной учительницей. В школе учился средне, а математику вообще не любил - в школе ее преподавали скучно. Когда Нэшу было 14, к нему в руки попала книга Эрика Т. Белла «Великие математики». «Прочитав эту книгу, я сумел сам, без посторонней помощи, доказать малую теорему Ферма» - пишет Нэш в своей автобиографии. Так его математический гений заявил о себе.

Учёба

Затем последовала учёба в Политехническом институте Карнеги (ныне частный Университет Карнеги-Меллона), где Нэш пробовал изучать химию, прослушал курс международной экономики и потом окончательно утвердился в решении заняться математикой. В 1948 году, окончив институт с двумя дипломами - бакалавра и магистра, - он поступил в Принстонский университет. Институтский преподаватель Нэша Ричард Даффин снабдил его одним из самых лаконичных рекомендательных писем. В нем была единственная строчка: «Этот человек - гений!»

Работы

В Принстоне Джон Нэш услышал о теории игр, в ту пору только представленной Джоном фон Нейманом и Оскаром Моргенштейном. Теория игр поразила его воображение, да так, что в 20 лет Джон Нэш сумел создать основы научного метода, сыгравшего огромную роль в развитии мировой экономики. В 1949 году 21-летний ученый написал диссертацию о теории игр. Сорок пять лет спустя он получил за эту работу Нобелевскую премию по экономике. Вклад Нэша описали так: зафундаментальный анализ равновесия в теории некооперативных игр.

Нейман и Моргенштейн занимались так называемыми играми с нулевой суммой, в которых победа одной стороны неизбежно означает поражение другой. В 1950 - 1953 гг. Нэш опубликовал четыре без преувеличения революционные работы, в которых представил глубокий анализ «игр с ненулевой суммой» - особого класса игр, в которых все участники или выигрывают, или терпят поражение. Примером такой игры могут стать переговоры об увеличении зарплаты между профсоюзом и руководством компании. Эта ситуация может завершиться либо длительной забастовкой, в которой пострадают обе стороны, либо достижением взаимовыгодного соглашения. Нэш сумел разглядеть новое лицо конкуренции, смоделировав ситуацию, впоследствии получившую название «равновесие по Нэшу» или «некооперативное равновесие», при которой обе стороны используют идеальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение только ухудшит их положение.

В 1951 году Джон Нэш стал работать в Массачусетском Технологическом институте (MIT) в Кэмбридже. Коллеги его особенно не любили, т. к. он был очень эгоистичен, однако относились к нему терпеливо, ведь его математические способности были блестящими. Там у Джона завязались близкие отношения с Элеанор Стиэр, которая вскоре уже ждала от него ребёнка. Так Нэш стал отцом, однако он отказался дать свое имя ребенку для записи в свидетельство о рождении, а также отказался оказывать какую-либо финансовую поддержку. В 1950-х гг. Нэш был знаменит. Он сотрудничал с корпорацией RAND, занимающейся аналитическими и стратегическими разработками, в которой работали ведущие американские ученые. Там, опять-таки благодаря своим исследованиям в области теории игр, Нэш стал одним из ведущих специалистов в области ведения «холодной войны». Кроме этого, работая в MIT Нэш написал ряд статей по вещественной алгебраической геометрии и теории римановых многообразий, высоко оценённые современниками.

Болезнь

Вскоре Джон Нэш встретил Алисию Лард и в 1957 г. они поженились. В июле 1958 г. журнал Fortune назвал Нэшавосходящей звездой Америки в «новой математике». Вскоре жена Нэша забеременела, но это совпало с болезнью Нэша - онзаболел шизофренией. В это время Джону было 30 лет, а Алисии - всего 26. В начале Алисия пыталась скрыть все происходящее от друзей и коллег, желая спасти карьеру Нэша. Однако спустя несколько месяцев безумного поведения, Алисия насильно поместила мужа в частную психиатрическую клинику в пригороде Бостона, McLean Hospital, где ему поставили диагноз «параноидальная шизофрения». После выписки он внезапно решил уехать в Европу. Алисия оставила новорожденного сына своей матери и последовала за мужем. Она вернула своего мужа в Америку. По возвращении они обосновались в Принстоне, где Алисия нашла работу. Но болезнь Нэша прогрессировала: он постоянно чего-то боялся, говорил о себе в третьем лице, писал бессмысленные почтовые карточки, звонил бывшим коллегам. Они терпеливо выслушивали его бесконечные рассуждения о нумерологии и состоянии политических дел в мире.

Ухудшение состояния мужа все сильнее угнетало Алисию. В 1959 г. он лишился работы. В январе 1961 года полностью подавленная Алисия, мать Джона и его сестра Марта приняли трудное решение: поместить Джона в Trenton State Hospital в Нью Джерси, где Джон прошел курс инсулиновой терапии - жесткое и рискованное лечение, 5 дней в неделю в течении полутора месяцев. После выписки коллеги Нэша из Принстона решили ему помочь, предложив ему работу в качестве исследователя, однако Джон опять отправился в Европу, но на этот раз один. Домой он отправлял только загадочные письма. В 1962 году, после 3 лет смятения, Алисия развелась с Джоном. При помощи матери она вырастила сына сама. Позднее оказалось, что у него тоже шизофрения.

Несмотря на развод с Алисией коллеги-математики продолжали помогать Нэшу - они дали ему работу в Университете и устроили встречу с психиатром, которой выписал анти-психотические лекарства. Состояние Нэша улучшилось, и он стал проводить время с Элеонорой и своим первым сыном Джоном Дэвидом. «Это было очень обнадёживающее время, - вспоминает сестра Джона Марта. - Это был достаточно долгий период. Но затем все стало меняться». Джон перестал принимать лекарства, опасаясь, что они могут оказать подавляющие влияние на мыслительную активность и симптомы шизофрении опять проявились.

В 1970 г. Алисия Нэш, будучи уверенной, что она совершила ошибку, предав мужа, приняла его вновь, и теперь уже как пансионера, это возможно и спасло его от состояния бездомности. В последующие годы Нэш продолжал ходить в Принстон, записывая на досках странные формулы. Студенты Принстона прозвали его «Фантом». Затем в 1980 гг. Нэшу стало заметно лучше - симптомы отступили и он стал более вовлеченным в окружающую жизнь. Болезнь, к удивлению врачей, стала отступать. Точнее, Нэш стал учиться не обращать на нее внимания и вновь занялся математикой. «Сейчас я мыслю вполне здраво, как всякий ученый, - пишет Нэш в своей автобиографии. - Не скажу, что это вызывает у меня радость, какую испытывает всякий выздоравливающий от физического недуга. Здравое мышление ограничивает представления человека о его связи с космосом».

Признание

В 1994, в возрасте 66 лет, Джон Нэш получил Нобелевскую Премию за свою работу по теории игр. Однако он был лишен возможности прочитать традиционную Нобелевскую лекцию в Стокгольмском университете, так как организаторы опасались за его состояние. Вместо этого был организован семинар (с его участием), на котором обсуждался его вклад в теорию игр. После этого Нэш был приглашен прочитать лекцию в университете Уппсалы, раз уж ему не предоставилось такой возможности в Стокгольме. По словам приглашавшего его профессора Математического института университета Уппсалы Кристера Кисельмана, лекция была посвящена космологии.

В 2001 году, через 38 лет после развода, Джон и Алисия вновь поженились. Нэш вернулся в свой офис в Принстоне, где продолжает познавать математику и познавать этот мир - мир, в котором вначале он был так успешен; мир, который заставил его пройти через очень сложное заболевание; и всё-таки этот мир принял его вновь.

«Игры разума»

В 1998 году американская журналистка (и профессор экономики Колумбийского университета Сильвия Назар) написала биографию Нэша под названием «A Beautiful Mind: The Life of Mathematical Genius and Nobel Laureate John Nash» (Прекрасный ум: Жизнь гения математики и нобелевского лауреата Джона Нэша). Книга мгновенно стала бестселлером.

В 2001 году под руководством Рона Ховарда по мотивам книги был снят фильм «A Beautiful Mind», в русском прокате «Игры разума». Фильм получил четыре «Оскара» (за лучшие адаптированный сценарий, режиссуру, актрису второго плана и, наконец, лучший фильм), награду «Золотой глобус» и был отмечен несколькими призами Bafta (британская премия за кинематографические достижения).

Как видим, фильм практически правда. Конечно, с некоторыми «литературными» искажениями.

• На роль режиссёра фильма был предложен Роберт Редфорд, но его не устроило расписание съёмок.
• На роль Джона Нэша пробовался Том Круз, а на роль Алисии - Сальма Хайек. Любопытно, что она родилась в том же городке Эль Сальвадор, что и её несостоявшаяся героиня.
• Когда Нэш впервые видит Паркера, он обращается к нему как к «большому брату» (намёк на роман Оруэлла «1984»). Ещё одна отсылка к Оруэллу происходит позднее, когда мы видим номер на двери кабинета Нэша - 101.
• В роли рукописи, которую молодой Джон Нэш показывает своему куратору, профессору Хелинджеру, выступает подлинная копия статьи, напечатанной в журнале Econometrica под заголовком «Задача совершения сделки».
• Сценарист фильма Акива Голдсман имел немалый опыт общения с душевнобольными людьми: в свою бытность врачом он лично разрабатывал методики восстановления душевного здоровья детей и взрослых.
• Куратором фильма по математической части стал профессор Барнардского колледжа Дэйв Байер - именно его рукойРасселл Кроу «выводит» на доске мудрёные формулы.
• «Мудрёные формулы» при внимательном рассмотрении представляют собой просто бессмысленный набор греческих букв, стрелок и математических знаков.
• В отличие от своего экранного двойника, отличавшегося редкой преданностью своей «половинке», реальный Джон Нэш в своей жизни несколько раз был женат, а в двадцать с небольшим лет усыновил внебрачного ребенка.
• В части фильма, относящейся к периоду вручения Нобелевской Премии (1994 г.), Нэш говорит о том, что якобы принимает антипсихотики нового типа, однако в действительности Джон Нэш отказался от них еще в 1970 году, и его ремиссия не была связана с приемом нейролептиков.

Где же сегодня применяются открытия Нэша?

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

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

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

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

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

И еще немного научных теорий: вот вам например , а вот . Вспомним еще про , и . А ведь есть еще и Оригинал статьи находится на сайте ИнфоГлаз.рф Ссылка на статью, с которой сделана эта копия -

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

Второй игрок выберет стратегию A, если предполагает, что первый выберет стратегию Z; в то же время стратегия B для него предпочтительнее в случае, если первый выберет Y.

Таблица 16.8.

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

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

Кроме ситуаций, рассмотренных в предыдущем разделе, бывают ситуации14 , которые естественно моделировать, исходя из следующих предположений:

игроки при принятии решений ориентируются на предполагаемые действия партнеров;

ожидания являются равновесными (совпадают с фактически выбранными партнерами действиями).

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

Формально равновесие Нэша определяется следующим образом.

Определение 90:

Набор стратегий x X является равновесием Нэша15 , если

1) стратегия x i каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков xe −i :

ui (xi , xe −i ) = max ui (xi , xe −i ) i = 1, . . . , n;

x iX i

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

15 Американский математик Джон Нэш получил Нобелевскую премию по экономике в 1994 г. вместе с Дж. Харшаньи и Р. Зельтеном «за новаторский анализ равновесий в теории некооперативных игр». Концепция равновесия была предложена в следующих статьях: J. F. Nash: Equilibrium Points in N-Person Games,

Proceedings of the National Academy of Sciences of the United States of America 36 (1950): 48–49; J. F. Nash: NonCooperative Games, Annals of Mathematics 54 (1951): 286–295 (рус. пер. Дж. Нэш: Бескоалиционные игры, в кн. Матричные игры, Н. Н. Воробьев (ред.), М.: Физматгиз, 1961: 205–221).

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

xe −i = x−i i = 1, . . . , n

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

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

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

Набор стратегий x X является равновесием Нэша, если стратегия xi каждого игрока является наилучшим для него откликом на стратегии других игроков x−i :

ui (xi , x−i ) = max ui (xi , x−i ) i = 1, . . . , n

x iX i

Это свойство можно также записать в терминах так называемых функций (отображений) отклика.

Определение 91:

Отображение отклика i-го игрока,

Ri : X−i 7→Xi

сопоставляет каждому набору стратегий других игроков, x−i X−i , множество стратегий i-го игрока, каждая из которых является наилучшим откликом на x−i . Другими словами,

ui (yi , x−i ) = max ui (xi , x−i ) x−i X−i , yi Ri (x−i )x i X i

Введение отображений отклика позволяет записать определение равновесия Нэша более компактно: набор стратегий x X является равновесием Нэша, если

xi Ri (x−i ) i = 1, . . . , n

Если отклик каждого игрока однозначен (является функцией), то множество равновесий Нэша совпадает с множеством решений системы уравнений:

xi = Ri (x−i ) i = 1, . . . , n.

В Таблице 16.8 отображения отклика игроков изображены подчеркиванием выигрышей, соответствующих оптимальным действиям. Равновесие Нэша в данной игре - клетка (B, Y), поскольку выигрыши обоих игроков в ней подчеркнуты.

Проиллюстрируем использование функций отклика на примере игры, в которой игроки имеют континуум стратегий.

Игра 5. «Международная торговля»

Две страны одновременно выбирают уровень таможенных пошлин, τi . Объем торговли между странами16 , x, зависит от установленных пошлин как

x = 1 − τ1 − τ2

Цель каждой страны - максимизировать доходы ui = τi x.

Максимизируем выигрыш 1-й страны,

τ1 (1 − τ1 − τ2 )

по τ1 считая фиксированным уровень пошлины, установленный 2-й страной. Условие первого порядка имеет вид

1 − 2τ1 − τ2 = 0

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

Условие первого порядка для задачи максимизации выигрыша 2-й страны находится аналогично:

1 − τ1 − 2τ2 = 0

Решив систему из двух линейных уравнений, найдем равновесие Нэша:

τ1 = τ2 = 1/3

Оптимальный отклик 1-й страны на уровень таможенной пошлины, установленной 2-й страной описывается функцией

τ1 (τ2 ) =1 − τ 2

Аналогично, функция отклика 2-й страны имеет вид

τ2 (τ1 ) =1 − τ 1 2

Чтобы найти равновесие Нэша, требуется решить систему уравнений

τ1 (τ2 ) = τ1 ,

τ2 (τ) = τ .

Графически поиск равновесия Нэша показан не Рис. 16.3 . Точки, лежащие на кривых оптимального отклика τ1 (τ2 ) и τ2 (τ1 ), характеризуются тем, что в них касательные к кривым безразличия игроков параллельны соответствующей оси координат. Напомним, что кривой безразличия называют множество точек, в которых полезность рассматриваемого индивидуума одна и та же (ui (x) = const). Равновесие находится как точка пересечения кривых отклика.

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

Связь между введенными концепциями решений описывается следующими утверждения-

16 В этой игре мы для упрощения не делаем различия между экспортом и импортом.

		(τ2 )
				равновесия
				τ2 (τ1 )

Рис. 16.3. Равновесие Нэша в игре «Международная торговля»

Теорема 151:

Если x = (x1 , . . . , xm ) - равновесие Нэша в некоторой игре, то ни одна из составляющих его стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий.

Обратная теорема верна в случае единственности.

Теорема 152:

Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1 , . . . , xm ) - равновесие Нэша в этой игре.

Доказательства этих двух утверждений даны в Приложении B (с. 641 ). Нам важно здесь, что концепция Нэша не входит в противоречие с идеями рациональности, заложенной в процедуре отбрасывания строго доминируемых стратегий.

По-видимому, естественно считать, что разумно определенное равновесие, не может быть отброшено при последовательном отбрасывании строго доминируемых стратегий. Первую из теорем можно рассматривать как подтверждение того, что концепция Нэша достаточно разумна. Отметим, что данный результат относится только к строгому доминированию. Можно привести пример равновесия Нэша с одной или несколькими слабо доминируемыми стратегиями (см. напр. Таблицу16.11 на с.652 ).

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

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

Игра 6. «Инспекция»

В этой игре первый игрок (проверяемый) поставлен перед выбором - платить или не платить подоходный налог. Второй - налоговой инспектор, решает, проверять или не проверять именно этого налогоплательщика. Если инспектор «ловит» недобросовестного налогоплательщика, то взимает в него штраф и получает поощрение по службе, более чем компенсирующее его издержки; в случае же проверки исправного налогоплательщика, инспектор, не получая поощрения, тем не менее несет издержки, связанные с проверкой. Матрица выигрышей представлена в Таблице 16.9 .

Таблица 16.9.
			Инспектор
		проверять				не проверять
нарушать
Проверяемый
не нарушать

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

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

Те стратегии, которые мы рассматривали раньше, принято называть чистыми стратегиями . Чистые стратегии в статических играх по сути дела совпадают с действиями игроков. Но в некоторых играх естественно ввести в рассмотрение также смешанные стратегии. Подсмешанной стратегией понимают распределение вероятностей на чистых стратегиях. В частном случае, когда множество чистых стратегий каждого игрока конечно,

Xi = {x1 i , . . . , xn i i }

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

µi = (µ1 i , . . . , µn i i )

Обозначим множество смешанных стратегий i-го игрока через Mi :

Mi = µi µk i > 0, k = 1, . . . , ni ; µ1 i + · · · + µn i i = 1

Как мы уже отмечали, стандартное предположение теории игр (как и экономической теории) состоит в том, что если выигрыш - случайная величина, то игроки предпочитают действия, которые приносят им наибольший ожидаемый выигрыш. Ожидаемый выигрыш i-го игрока, соответствующий набору смешанных стратегий всех игроков, (µ1 , . . . , µm ), вычисляется по формуле

Ожидание рассчитывается в предположении, что игроки выбирают стратегии независимо (в статистическом смысле).

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

Эта интерпретация подразумевает, что выбор стратегии зависит от некоторого сигнала, который сам игрок может наблюдать, а его партнеры - нет17 . Например, игрок может выбирать стратегию в зависимости от своего настроения, если ему известно распределение вероятностей его настроений, или от того, с какой ноги он в этот день встал18 .

Определение 92:

Набор смешанных стратегий µ = (µ1 , . . . , µm ) являетсяравновесием Нэша в смешанных стратегиях , если

1) стратегия µ i каждого игрока является наилучшим для него откликом на ожидаемые им стратегии других игроков µe −i :

U(µi , µe −i ) = max U(µi , µe −i ) i = 1, . . . , n;

µ iM i

2) ожидания совпадают с фактически выбираемыми стратегиями:

µe −i = µ−i i = 1, . . . , n.

Заметим, что равновесие Нэша в смешанных стратегиях является обычным равновесием Нэша в так называемом смешанном расширении игры, т. е. игре, чистые стратегии которой являются смешанными стратегиями исходной игры.

Найдем равновесие Нэша в смешанных стратегиях в Игре 16.2.5 .

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

а через ν - вероятность того, что налоговой инспектор проверяет налогоплательщика.

В этих обозначениях ожидаемый выигрыш налогоплательщика равен

U1 (µ, ν) = µ[ν · (−1) + (1 − ν) · 1] + (1 − µ)[ν · 0 + (1 − ν) · 0] =

= µ(1 − 2ν),

а ожидаемый выигрыш инспектора равен

U2 (µ, ν) = ν[µ · 1 + (1 − µ) · (−1)] + (1 − µ)[µ · 0 + (1 − µ) · 0] = = ν(2µ − 1)

Если вероятность проверки мала (ν < 1/2), то налогоплательщику выгодно не платить налог, т. е. выбрать µ = 1. Если вероятность проверки велика, то налогоплательщику выгодно заплатить налог, т. е. выбрать µ = 0. Если же ν = 1/2, то налогоплательщику все равно, платить налог или нет, он может выбрать любую вероятность µ из интервала . Таким образом, отображение отклика налогоплательщика имеет вид:

Рассуждая аналогичным образом, найдем отклик налогового инспектора:

0, если µ < 1/2

ν(µ) = , если µ = 1/2

1, если µ > 1/2.

17 Если сигналы, наблюдаемые игроками, статистически зависимы, то это может помочь игрокам скоординировать свои действия. Это приводит к концепции коррелированного равновесия.

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

Графики отображений отклика обоих игроков представлены на Рис. 16.4 . По осям на этой диаграмме откладываются вероятности (ν и µ соответственно). Они имеют единственную общую точку (1/2, 1/2). Эта точка соответствует равновесию Нэша в смешанных стратегиях. В этом равновесии, как это всегда бывает в равновесиях с невырожденными смешанными стратегиями (то есть в таких равновесиях, в которых ни одна из стратегий не выбирается с вероятностью 1), каждый игрок рандомизирует стратегии, которые обеспечивают ему одинаковую ожидаемую полезность. Вероятности использования соответствующих чистых стратегий, выбранные игроком, определяются не структурой выигрышей данного игрока, а структурой выигрышей его партнера, что может вызвать известные трудности с интерпретацией данного решения.

Рис. 16.4. Отображения отклика в игре «Инспекция»

В отличие от равновесия в чистых стратегиях, равновесие в смешанных стратегиях в конечных играх существует всегда19 , что является следствием следующего общего утверждения.

Теорема 153:

Предположим, что в игре G = hI, {Xi }i I , {ui }i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui (·) вогнута по xi и непрерывна. Тогда в игре G существует равновесие Нэша (в чистых стратегиях).

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

Теорема 154 (Следствие (Теорема Нэша)):

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

Заметим, что существование в игре равновесия в чистых стратегиях не исключает существования равновесия в невырожденных смешанных стратегиях.

Рассмотрим в Игре 16.2.1 «Выбор компьютера» случай, когда выгоды от совместимости значительны, т. е. a < c и b < c. В этом варианте игры два равновесия в чистых стратегиях: (IBM, IBM) и (Mac, Mac). Обозначим µ и ν вероятности выбора компьютера IBM PC первым и вторым игроком соответственно. Ожидаемый выигрыш 1-го игрока равен

U1 (µ, ν) = µ[ν · (a + c) + (1 − ν) · a] + (1 − µ)[ν · 0 + (1 − ν) · c] = = µ[ν · 2c − (c − a)] + (1 − ν)c

а его отклик имеет вид

µ(ν) = ,

Ожидаемый выигрыш 2-го игрока равен

если ν < (c − a)/2c

если ν = (c − a)/2c

если ν > (c − a)/2c.

U2 (µ, ν) = ν[µ · c + (1 − µ) · 0] + (1 − ν)[µ · b + (1 − µ) · (b + c)] =

= ν[µ · 2c − (b + c)] + b + (1 − µ)c

а его отклик имеет вид

ν(µ) = ,

если µ < (b + c)/2c

если µ = (b + c)/2c

если µ > (b + c)/2c.

Графики отображений отклика и точки, соответствующие трем равновесиям изображены на Рис. 16.5 . Как видно, в рассматриваемой игре кроме двух равновесий в чистых стратегиях имеется одно равновесие в невырожденных смешанных стратегиях. Соответствующие вероятности равны

µ = b + cи ν = c − a

Рис. 16.5. Случай, когда в игре «Выбор компьютера» существует три равновесия, одно из которых - равновесие в невырожденных смешанных стратегиях

Приложение A

Теорема повторяется, номер обновляется, ссылки на это приложение нет. Можно поменять местами A и B

Теорема 155:

Предположим, что в игре G = hI, {Xi }i I , {ui0 }i I i у любого игрока множество стратегий Xi непусто, компактно и выпукло, а функция выигрыша ui (·) вогнута по xi и непрерывна. Тогда существует равновесие Нэша.

Доказательство: Докажем, что отображение отклика, Ri (·), каждого игрока полунепрерывно сверху и его значение при каждом x−i X−i непусто и выпукло. Непустота следует из теоремы Вейерштрасса (непрерывная функция на компакте достигает максимума).

16.2. Статические игры с полной информацией

Докажем выпуклость. Пусть z0 , z00 Ri (x−i ). Очевидно, что u(z0 , x−i ) = u(z00 , x−i вогнутости по xi функции ui (·) следует, что при α

u(αz0 + (1 − α)z00 , x−i ) > αu(z0 , x−i ) + (1 − α)u(z00 , x−i ) =

U(z0 , x−i ) = u(z00 , x−i )

Поскольку функция ui (·) достигает максимума в точках z0 и z00 , то строгое неравенство

невозможно. Таким образом,

αz0 + (1 − α)z00 Ri (x−i )

Докажем теперь полунепрерывность сверху отображения Ri (·). Рассмотрим последовательность xn i сходящуюся к x¯i и последовательность xn −i сходящуюся к x¯−i , причем xn i Ri (xn −i ). Заметим, что в силу компактности множеств Xj x¯i Xi и x¯−i X−i . Нам нужно доказать, что x¯i Ri (x¯−i ). По определению отображения отклика

u(xn i , xn −i ) > u(xi , xn −i ) xi Xi , n

Из непрерывности функции ui (·) следует, что

u(¯xi , x¯−i ) > u(xi , x¯−i ) xi Xi

Тем самым, по введенному выше определению отображения отклика, x¯i Ri (x¯−i ). Опираясь на доказанные только что свойства отображения Ri (·) и на теорему Какутани,

докажем существование равновесия по Нэшу, то есть такого набора стратегий x X , для

которого выполнено

xi Ri (x−i ) i = 1, . . . , n

Определим отображение R(·) из X в X следующим образом:

R(x) = R1 (x−1 ) × · · · × Rn (x−n )

Отметим, что это отображение удовлетворяет тем же свойствам, что и каждое из отображений Ri (·), так как является их декартовым произведением.

Отображение R(·) и множество X удовлетворяют свойствам, которые необходимы для выполнения теоремы Какутани. Таким образом, существует неподвижная точка отображения

Очевидно, что точка x есть равновесие по Нэшу.

Приложение B

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

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

G = hI, {Xi }I , {ui }I i.

Определим последовательность игр {G[t] }t=0,1,2,... , каждая из которых получается из последующей игры отбрасыванием строго доминируемых стратегий. Игры отличаются друг от друга множествами допустимых стратегий:

G[t] = hI, {Xi [t] }I , {ui }I i

Процедура начинается с G= G.

Множество допустимых стратегий i-го игрока на шаге t + 1 рассматриваемой процедуры берется равным множеству не доминируемых строго стратегий i-го игрока в игре t-го шага. Множества не доминируемых строго стратегий будем обозначать через NDi (см. определение строго доминируемых стратегий (Определение89 , с.631 )). Формально

NDi = xi Xi yi Xi : ui (yi , x−i ) > ui (xi , x−i ) x−i X−i

Таким образом, можно записать шаг рассматриваемой процедуры следующим образом:

X i = ND i [t]

где NDi [t] - множество не доминируемых строго стратегий в игре G[t] .

Приведем теперь доказательства Теорем 151 и152 (с.636 ). Теорема151 утверждает следующее:

: Если x = (x1 , . . . , xm ) - равновесие Нэша в некоторой игре, то ни одна из стратегий не может быть отброшена в результате применения процедуры последовательного отбрасывания строго доминируемых стратегий.

Если использовать только что введенные обозначения, то Теорема 151 утверждает, что если x - равновесие Нэша в исходной игре G, то на любом шаге t выполнено

xi Xi [t] , i I, t = 1, 2, . . .

x X[t] , t = 1, 2, . . .

Доказательство (Доказательство Теоремы 151 ): Пусть есть такой шаг τ , что на нем должна быть отброшена стратегия xi некоторого игрока i I . Предполагается, что на предыдущих шагах ни одна из стратегий не была отброшена:

x X[t] , t = 1, . . . , τ.

По определению строгого доминирования существует другая стратегия игрока i, x0 i Xi [τ] , которая дает этому игроку в игре G[τ] более высокий выигрыш при любых выборах других

ui (x0 i , x−i ) > ui (xi , x−i ) x−i X− [τ i ]

В том числе, это соотношение должно быть выполнено для x−i , поскольку мы предположили, что стратегии x−i не были отброшены на предыдущих шагах процедуры (x−i X− [τ i ] ). Значит,

: Если в результате последовательного отбрасывания строго доминируемых стратегий у каждого игрока остается единственная стратегия, xi , то x = (x1 , . . . , xm ) - равновесие Нэша в этой игре.

Данная теорема относится к случаю, когда в процессе отбрасывания строго доминируемых

стратегий начиная с некоторого шага ¯ остается единственный набор стратегий, т. е. t x

Теорема утверждает, что x является единственным равновесием Нэша исходной игры.

Доказательство (Доказательство Теоремы 152 ): Поскольку, согласно доказанной только что теореме, ни одно из равновесий Нэша не может быть отброшено, нам остается только доказать, что указанный набор стратегий x является равновесием Нэша. Предположим, что это не так. Это означает, что существует стратегия x˜i некоторого игрока i, такая что

ui (xi , x−i ) < ui (˜xi , x−i )

По предположению, стратегия x˜i была отброшена на некотором шаге τ , поскольку она не совпадает с xi . Таким образом, существует некоторая строго доминирующая ее стратегия x0 i Xi [τ] , так что

ui (x0 i , x−i ) > ui (˜xi , x−i ) x−i X− [τ i ]

В том числе это неравенство выполнено при x−i = x−i :

ui (x0 i , x−i ) > ui (˜xi , x−i )

Стратегия x0 i не может совпадать со стратегией xi , поскольку в этом случае вышеприведенные неравенства противоречат друг другу. В свою очередь, из этого следует, что должна существовать стратегия x00 i , которая доминирует стратегию x0 i на некотором шаге τ0 > τ , т. е.

	(x00									[τ0 ]
								−i

В том числе

ui (x00 i , x−i ) > ui (x0 i , x−i )

Можно опять утверждать, что стратегия x00 i не может совпадать со стратегией xi , иначе вышеприведенные неравенства противоречили бы друг другу.

Продолжая эти рассуждения, мы получим последовательность шагов τ < τ0 < τ00 < . . .

и соответствующих допустимых стратегий x0 i , x00 i , x000 i , . . ., не совпадающих с xi . Это противо-

/ 667. Два игрока размещают некоторый объект на плоскости, то есть выбирают его координаты (x, y). Игрок 1 находится в точке (x 1 , y1 ), а игрок 2 - в точке (x2 , y2 ). Игрок 1 выбирает координату x, а игрок 2 - координату y. Каждый стремиться, чтобы объект находился как можно ближе к нему. Покажите, что в этой игре у каждого игрока есть строго доминирующая стратегия.

/ 668. Докажите, что если в некоторой игре у каждого из игроков существует строго доминирующая стратегия, то эти стратегии составляют единственное равновесие Нэша.

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

Найдите в следующих играх все равновесия Нэша.

/ 670. Игра 16.2.1 (с.625 ), выигрыши которой представлены в Таблице??////??

/ 671. «Орехи»

Два игрока делят между собой 4 ореха. Каждый делает свою заявку на орехи: xi = 1, 2 или 3. Если x1 + x2 6 4, то каждый получает сколько просил, в противном случае оба не получают ничего.

/ 672. Два преподавателя экономического факультета пишут учебник. Качество учебника (q) зависит от их усилий (e1 и e2 соответственно) в соответствии с функцией

q = 2(e1 + e2 ).

Целевая функция каждого имеет вид

ui = q − ei ,

т. е. качество минус усилия. Можно выбрать усилия на уровне 1, 2 или 3.

/ 673. «Третий лишний» Каждый из трех игроков выбирает одну из сторон монеты: «орёл» или «решка». Если

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

/ 674. Три игрока выбирают одну из трех альтернатив: A, B или C . Альтернатива выбирается голосованием большинством голосов. Каждый из игроков голосует за одну и только за одну альтернативу. Если ни одна из альтернатив не наберет большинство, то будет выбрана альтернатива A. Выигрыши игроков в зависимости от выбранной альтернативы следующие:

u1 (A) = 2, u2 (A) = 0, u3 (A) = 1,

u1 (B) = 1, u2 (B) = 2, u3 (B) = 0,

u1 (C) = 0, u2 (C) = 1, u3 (C) = 2.

/ 675. Формируются два избирательных блока, которые будут претендовать на места в законодательном собрании города N-ска. Каждый из блоков может выбрать одну из трех ориентаций: «левая» (L), «правая» (R) и «экологическая» (E). Каждая из ориентаций может привлечь 50, 30 и 20% избирателей соответственно. Известно, что если интересующая их ориентация не представлена на выборах, то избиратели из соответствующей группы не будут голосовать. Если блоки выберут разные ориентации, то каждый получит соответствующую долю голосов. Если блоки выберут одну и ту же ориентацию, то голоса соответствующей группы избирателей разделятся поровну между ними. Цель каждого блока - получить наибольшее количество голосов.

/ 676. Два игрока размещают точку на плоскости. Один игрок выбирает абсциссу, другой -

ординату. Их выигрыши заданы функциями:

а) ux (x, y) = −x2 + x(y + a) + y2 , uy (x, y) = −y2 + y(x + b) + x2 ,

б) ux (x, y) = −x2 − 2ax(y + 1) + y2 , uy (x, y) = −y2 + 2by(x + 1) + x2 , в) ux (x, y) = −x − y/x + 1/2y2 , uy (x, y) = −y − x/y + 1/2x2 ,

(a, b - коэффициенты).

/ 677. «Мороженщики на пляже»

Два мороженщика в жаркий день продают на пляже мороженое. Пляж можно представить как единичный отрезок. Мороженщики выбирают, в каком месте пляжа им находиться, т. е. выбирают координату xi . Покупатели равномерно рассредоточены по пляжу и покупают мороженое у ближайшего к ним продавца. Если x1 < x2 , то первый обслуживают (x1 + x2 )/2 долю пляжа, а второй - 1 − (x1 + x2 )/2. Если мороженщики расположатся в одной и той же точке (x1 = x2 ), покупатели поровну распределятся между ними. Каждый мороженщик стремиться обслуживать как можно большую долю пляжа.

/ 678. «Аукцион» Рассмотрите аукцион, подобный описанному в Игре 16.2.2 , при условии, что выигравший

аукцион игрок платит названную им цену.

/ 679. Проанализируйте Игру 16.2.1 «Выбор компьютера» (с.624 ) и найдите ответы на следующие вопросы:

а) При каких условиях на параметры a, b и c будет существовать равновесие в доминирующих стратегиях? Каким будет это равновесие?

б) При каких условиях на параметры будет равновесием Нэша исход, когда оба выбирают IBM? Когда это равновесие единственно? Может ли оно являться также равновесием в доминирующих стратегиях?

/ 680. Каждый из двух соседей по подъезду выбирает, будет он подметать подъезд раз в неделю или нет. Пусть каждый оценивает выгоду для себя от двойной чистоты в a > 0 денежных единиц, выгоду от одинарной чистоты - в b > 0 единиц, от неубранного подъезда - в 0, а свои затраты на личное участие в уборке - в c > 0. При каких соотношениях между a, b и c в игре сложатся равновесия вида: (0) никто не убирает, (1) один убирает, (2) оба убирают?

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

/ 682. Каждый из двух игроков (i = 1, 2) имеет по 3 стратегии: a, b, c и x, y, z соответственно. Взяв свое имя как бесконечную последовательность символов типа иваниваниван. . . , задайте выигрыши первого игрока так: u1 (a, x) = «и», u1 (a, y) = «в», u1 (a, z) = «а», u1 (b, x) = «н», u1 (b, y) = «и», u1 (b, z) = «в», u1 (c, x) = «а», u1 (c, y) = «н», u1 (c, z) = «и». Подставьте вместо каждой буквы имени ее номер в алфавите, для чего воспользуйтесь Таблицей16.10 . Аналогично используя фамилию, задайте выигрыши второго игрока, u2 (·).

1) Есть ли в Вашей игре доминирующие и строго доминирующие стратегии? Если есть, то образуют ли они равновесие в доминирующих стратегиях?

2) Каким будет результат последовательного отбрасывания строго доминируемых страте-

3) Найдите равновесия Нэша этой игры.

Таблица 16.10.

/ 683. Составьте по имени, фамилии и отчеству матричную игру трех игроков, у каждого из которых по 2 стратегии. Ответьте на вопросы предыдущей задачи.

/ 684. Заполните пропущенные выигрыши в следующей таблице так, чтобы в получившейся игре. . .

(0) не было ни одного равновесия Нэша,

		было одно равновесие Нэша,
		было два равновесия Нэша,
		было три равновесия Нэша,

(4) было четыре равновесия Нэша.

/ 685. 1) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть меньше, чем

min max ui (xi , x−i ).

x −iX −ix iX i

2) Объясните, почему в любом равновесии Нэша выигрыш i-го игрока не может быть

меньше, чем
x iX ix −iX −i

И Оскар Моргенштерн стали основателями нового интересного направления математики, которое получило название "теория игр". В 1950-е годы этим направлением заинтересовался молодой математик Джон Нэш. Теория равновесия стала темой его диссертации, которую он написал, будучи в возрасте 21 год. Так родилась новая стратегия игр под названием «Равновесие по Нэшу», заслужившая Нобелевскую премию спустя много лет - в 1994 году.

Долгий разрыв между написанием диссертации и всеобщим признанием стал испытанием для математика. Гениальность без признания вылилась в серьезные ментальные нарушения, но и эту задачу Джон Нэш смог решить благодаря прекрасному логическуму разуму. Его теория "равновесие по Нэшу" удостоилась премии Нобеля, а его жизнь экранизации в фильме «Beautiful mind» («Игры разума»).

Кратко о теории игр

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

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

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

Дилемма заключенного и научный прорыв

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

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

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

Пример дилеммы заключенного

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

1. Оба одновременно дают показания и получают по 2,5 года в тюрьме.
2. Оба одновременно молчат и получают по 1 году, поскольку в таком случае доказательная база их вины будет мала.
3. Один дает показания и получает свободу, а другой молчит и получает 5 лет тюрьмы.

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

Цепь логических умозаключений

Итак, преступник А рассматривает следующие варианты:

1. Я молчу и молчит мой напарник — мы оба получим по 1 году тюрьмы.
2. Я сдаю напарника и он сдает меня — мы оба получим по 2,5 года тюрьмы.
3. Я молчу, а напарник меня сдает — я получу 5 лет тюрьмы, а он свободу.
4. Я сдаю напарника, а он молчит - я получаю свободу, а он 5 лет тюрьмы.

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

Таблица вероятных исходов дилеммы заключенного.

Вопрос состоит в том, что выберет каждый участник?

«Молчать, нельзя говорить» или «молчать нельзя, говорить»

Чтобы понять выбор участника, нужно пройти по цепочке его размышлений. Следуя рассуждениям преступника А: если я промолчу и промолчит мой напарник, мы получим минимум срока (1 год), но я не могу узнать, как он себя поведет. Если он даст показания против меня, то мне также лучше дать показания, иначе я могу сесть на 5 лет. Лучше мне сесть на 2,5 года, чем на 5 лет. Если он промолчит, то мне тем более нужно дать показания, поскольку так я получу свободу. Точно так же рассуждает и участник B.

Нетрудно понять, что доминирующая стратегия для каждого из преступников - это дача показаний. Оптимальная точка этой игры наступает тогда, когда оба преступника дают показания и получают свой «приз» — 2,5 года тюрьмы. Теория игр Нэша называет это равновесием.

Неоптимальное оптимальное решение по Нэшу

Революционность нэшевского взгляда в том, не является оптимальным, если рассмотреть отдельного участника и его личный интерес. Ведь наилучший вариант - это промолчать и выйти на свободу.

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

Рассматривая вариант, когда оба преступника молчат и получают всего по 1 году, можно назвать него Парето-оптимальным вариантом. Однако он возможен, только если преступники смогли бы сговориться заранее. Но даже это не гарантировало бы этого исхода, поскольку соблазн отступить от уговора и избежать наказания велик. Отсутствие полного доверия друг к другу и опасность получить 5 лет вынуждает выбрать вариант с признанием. Размышлять о том, что участники будут придерживаться варианта с молчанием, действуя согласованно, просто нерационально. Такой вывод можно сделать, если изучать равновесие Нэша. Примеры только доказывают правоту.

Эгоистично или рационально

Теория равновесия Нэша дала потрясающие выводы, опровергнувшие существующие до этого принципы. Например, Адам Смит рассматривал поведение каждого из участников как абсолютно эгоистичное, что и приводило систему в равновесие. Эта теория носила название «невидимая рука рынка».

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

Чисто мужской эксперимент

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

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

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

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

Вся наша жизнь игра

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

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

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

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

Рассмотрим два вида стратегии:

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

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

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

Пенальти и смешанная стратегия

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

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

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