Что означает ситуация равновесия по нэшу. Научная электронная библиотека

Определение 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 решения предыдущего примера.

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

И Оскар Моргенштерн стали основателями нового интересного направления математики, которое получило название "теория игр". В 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 лет вынуждает выбрать вариант с признанием. Размышлять о том, что участники будут придерживаться варианта с молчанием, действуя согласованно, просто нерационально. Такой вывод можно сделать, если изучать равновесие Нэша. Примеры только доказывают правоту.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Равновесие Нэша – это часть теории игр, её автором выступил американский математик Джон Нэш. Эта теория демонстрирует оптимальную игру «в вакууме»: когда ставить олл-ин или коллировать пуш оппонентов. Важно понимать, что пуша/колла по Нэшу в современных покерных реалиях уже не является единственно верной. Она является оптимальной только при условии, если ваши оппоненты знают об этой стратегии и придерживаются её без отклонений.

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

Где использовать равновесие Нэша?

Диапазоны равновесие Нэша подходят для игры в , Sit&Go и турнирах . Применять эту стратегию следуют, когда ваш стек опускается до 15 больших блайндов или ниже, и ваша игра сводится к одним пуш/фолд решениям. Чтобы отточить свое мастерство игры, вам следует использовать специальное программное обеспечение, которое моделирует такие ситуации: и ICMIZER.

Предположим, что ваш оппонент идет олл-ин, а у вас осталось 14 больших блайндов. По равновесию Нэша, вы можете коллировать с широким диапазоном рук, имея 20 BB, включая карманные тройки, QJ, QT и даже K2s.

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

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

Диапазон пуша Нэшу

Диапазон колла по Нэшу

Зеленый цвет – эффективный стек от 15 до 20 больших блайндов.

Желтый и темно-желтый цвет – эффективный стек от 6 до 14 больших блайндов.

Красный цвет – эффективный стек от 1 до 5 больших блайндов.

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

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться отверсии , проверенной 9 мая 2012; проверки требуют2 правки .

Перейти к: навигация ,поиск

Джон Форбс Нэш, ноябрь 2006

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

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

Формальное определение

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

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

Литература

Васин А. А., Морозов В. В. Теория игр и модели математической экономики - М.: МГУ, 2005, 272 с.

Воробьев Н. Н. Теория игр для экономистов-кибернетиков - М.: Наука, 1985

Мазалов В. В. Математическая теория игр и приложения - Изд-во Лань, 2010, 446 с.

Петросян Л. А. , Зенкевич Н. А., Шевкопляс Е. В. Теория игр - СПб: БХВ-Петербург, 2012, 432 с.

Эффективность по Парето

Материал из Википедии - свободной энциклопедии

Перейти к: навигация ,поиск

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

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

Множество состояний системы, оптимальных по Парето, называют «множеством Парето», «множеством альтернатив, оптимальных в смысле Парето», либо «множеством парето-оптимальных альтернатив».

Ситуация, когда достигнута эффективность по Парето - это ситуация, когда все выгоды от обмена исчерпаны.

Эффективность по Парето является одним из центральных понятий для современной экономической науки. На основе этого понятия строятся Первая и Вторая фундаментальные теоремы благосостояния . Одним из приложений Парето-оптимальности является т. н. Парето-распределение ресурсов (трудовых ресурсов и капитала) при международной экономической интеграции, то есть экономическом объединении двух и более государств. Интересно, что Парето-распределение до и после международной экономической интеграции было адекватно математически описано (Далимов Р. Т., 2008). Анализ показал, что добавленная стоимость секторов и доходы трудовых ресурсов движутся противонаправленно в соответствии с хорошо известным уравнением теплопроводности аналогично газу или жидкости в пространстве, что дает возможность применить методику анализа, используемую в физике, в отношении экономических задач по миграции экономических параметров.

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

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

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

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

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

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

Определение. В антогонистической игре пара стратегий (А i , В j) называется равновесной или устойчивой, если ни одному из игроков не выгодно отходить от своей стратегии.

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

33. Функция Неймана- Моргенштерна в теории игр. Равновесие Байеса-Нэша

Систематическая же математическая теория игр была детально разработана американскими учёными Дж. Нейманом и О. Моргенштерном (1944) как средство математического подхода к явлениям конкурентной экономики. В ходе своего развития И. т. переросла эти рамки и превратилась в общую математическую теорию конфликтов.

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

Определить оптимальную стратегию можно:

• Равновесие Байеса-Нэша: если определено статистическое распределение встречаемого поведения (например, 33 % «око за око», 33 % всегда обманывают и 33 % всегда сотрудничают), то стратегию можно вычислить математически . Этим детально занимается теория эволюционной динамики.