Меню Главная Случайная статья Настройки Равновесие Нэша Материал из https://ru.wikipedia.org Равновесие Нэша — концепция решения, одно из ключевых понятий теории игр. Так называется набор стратегий в игре для двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют[1]. Джон Нэш доказал существование такого равновесия в смешанных стратегиях в любой конечной игре. Содержание 1 История 2 Математическая формулировка 3 Чисто-стратегическое равновесие Нэша 4 Смешанно-стратегическое равновесие Нэша 5 Существование равновесия 6 Примеры использования понятия 6.1 Социология 6.2 Политология 6.3 Экономика 6.4 Военное дело 7 См. также 8 Примечания 9 Литература История Эта концепция впервые использована Антуаном Огюстом Курно. Он показал, как найти то, что мы называем равновесием Нэша, в игре Курно. Нэш первым доказал, что подобные равновесия должны существовать для всех конечных игр с любым числом игроков. Это было сделано в его диссертации по некооперативным играм в 1950 году. До Нэша это было доказано только для игр с 2 участниками с нулевой суммой Джоном фон Нейманом и Оскаром Моргенштерном (1947). Математическая формулировка Допустим, ${\displaystyle (S,H)}$ — некооперативная игра n лиц в нормальной форме, где ${\displaystyle H_{i}(x^{*})\geqslant H_{i}(x_{i},x_{-i}^{*}).}$ Игра может иметь равновесие Нэша в чистых стратегиях или в смешанных (то есть при выборе чистой стратегии стохастически с фиксированной частотой). Чисто-стратегическое равновесие Нэша Чистая стратегия (англ. Pure strategy) — это выбор конкретного, детерминированного действия игроком. В игре с конечным числом чистых стратегий, чисто-стратегическое равновесие Нэша — это профиль стратегий ${\displaystyle \mathbf {s} ^{*}=(s_{1}^{*},s_{2}^{*},\dots ,s_{n}^{*})}$, где ${\displaystyle s_{i}^{*}}$ — чистая стратегия игрока ${\displaystyle i}$, такой что для каждого игрока ${\displaystyle i}$ и любой другой его чистой стратегии ${\displaystyle s_{i}\in S_{i}}$ выполняется: ${\displaystyle u_{i}(s_{i}^{*},\mathbf {s} _{-i}^{*})\geq u_{i}(s_{i},\mathbf {s} _{-i}^{*}),}$ где ${\displaystyle \mathbf {s} _{-i}^{*}}$ — набор чистых стратегий всех игроков, кроме ${\displaystyle i}$, а ${\displaystyle u_{i}}$ — функция выигрыша игрока ${\displaystyle i}$. В ряде игр, например, в «Дилемме заключённого», такое равновесие существует. Однако в других играх, таких как «Камень, ножницы, бумага», чисто-стратегическое равновесие отсутствует. Смешанно-стратегическое равновесие Нэша Смешанная стратегия (англ. Mixed strategy) игрока — это вероятностное распределение на множестве его чистых стратегий. Игрок выбирает каждую чистую стратегию с определённой вероятностью. Смешанная стратегия ${\displaystyle \sigma _{i}}$ представляет собой вектор вероятностей ${\displaystyle \mathbf {p} _{i}}$, где ${\displaystyle \sum _{s\in S_{i}}p_{i}(s)=1}$. Смешанно-стратегическое равновесие Нэша — это набор смешанных стратегий ${\displaystyle {\boldsymbol {\sigma }}^{*}=(\sigma _{1}^{*},\sigma _{2}^{*},\dots ,\sigma _{n}^{*})}$, такой что для каждого игрока ${\displaystyle i}$ и любой его смешанной стратегии ${\displaystyle \sigma _{i}}$ выполняется: ${\displaystyle \mathbb {E} [u_{i}(\sigma _{i}^{*},{\boldsymbol {\sigma }}_{-i}^{*})]\geq \mathbb {E} [u_{i}(\sigma _{i},{\boldsymbol {\sigma }}_{-i}^{*})],}$ где ${\displaystyle \mathbb {E} [u_{i}(\dots )]}$ — ожидаемый выигрыш игрока ${\displaystyle i}$ при использовании смешанных стратегий. Если игрок использует собственную смешанную стратегию (т.е. присваивает ненулевую вероятность нескольким чистым стратегиям), он должен быть безразличен в отношении выигрыша от каждой из этих чистых стратегий. Существование равновесия Отсутствие равновесия Нэша в чистых стратегиях характерно для многих матричных игр. Включение смешанных стратегий позволяет гарантировать существование равновесия. Теорема Нэша о существовании (англ. Nash's existence theorem) — фундаментальный результат, доказанный Джоном Нэшем в 1950 году[2]: В любой конечной игре (игре с конечным числом игроков и конечным числом чистых стратегий у каждого игрока) в нормальной форме существует, по меньшей мере, одно равновесие Нэша в смешанных стратегиях. Доказательство теоремы опирается на теорему о неподвижной точке Какутани. Теорема гарантирует, что даже если в игре нет стабильного чистого выбора, всегда существует стабильный вероятностный (смешанный) выбор, от которого ни один рациональный игрок не захочет отклониться в одностороннем порядке. Тем не менее, существуют большие семейства игр, в которых равновесие Нэша существует и в чистых стратегиях [3][4]. Примерами являются конечные позиционные (графовые) игры с ${\displaystyle n}$ игроками и с совершенной информацией. В случае двух игроков, существование равновесия Нэша в чистых стратегиях эквивалентно двойственности гиперграфов. Для игр с нулевой суммой это было показано Дж. Эдмондсом и Д. Р. Фулкерсоном[5]. Позднее этот результат был обобщен для игр с ненулевой суммой[6][7] [8]. Примечательно, что в таких равновесиях стратегия одного игрока не зависит от предпочтений другого. Примеры использования понятия Социология В социологической теории рационального выбора отдельно подчёркивается, что устойчивое состояние общества (социальное равновесие) может отличаться от оптимального (социальный оптимум). Такие неоптимальные, но устойчивые состояния и называют в социологии равновесием Нэша. Актор B 1 2 Актор A 1 A: +1, B: +1 A: 1, B: +2 2 A: +2, B: 1 A: 0, B: 0 В таблице слева приведена структура действия в терминах теории игр, составленная для двух действующих субъектов (акторов). Каждый актор имеет два варианта действия, обозначенных цифрами 1 и 2. Коэффициенты вознаграждения, получаемые ими при выборе определённых вариантов действия, указаны в соответствующих ячейках таблицы. Предположим, что в данный момент оба актора используют действие 2, а их вознаграждения соответственно равны нулю. Выбрав действие 1, актор A ухудшит собственную ситуацию на одну позицию (A: 1, B: +2). Аналогично актор B самостоятельно выбрав вариант 1, в то время когда актор A продолжает использовать действие 2, только ухудшит свою ситуацию (A: +2, B: 1). Таким образом, несмотря на то, что оба актора понимают, что оптимальным для них была бы ситуация, когда оба они используют действие 1 (вознаграждение — A: +1, B: +1), ни у одного из них нет мотива к изменению ситуации, а равновесие становится результатом отсутствия таких мотивов. Если система уже находится в оптимальном состоянии (когда оба актора выбрали действие 1), то у обоих из них всегда будет искушение начать использовать действие 2, которое принесёт им вознаграждение за счёт другого игрока. Этот пример иллюстрирует возможность существования двух социальных состояний: устойчивого, но неоптимального (оба актора используют вариант 2); а также второго оптимального, но неустойчивого (оба актора используют вариант 1).[9] Политология Для объяснения различных явлений в политической теории часто используется понятие ядра, являющееся более слабым вариантом равновесия Нэша. Ядром называют набор состояний, в каждом из которых ни одна группа акторов, способных выстроить новое (отсутствующее в данном ядре) состояние, не улучшит своей ситуации по сравнению с их состоянием в данном ядре.[9] Экономика В отрасли имеются две фирмы № 1 и № 2. Каждая из фирм может установить два уровня цен: «высокие» и «низкие». Если обе фирмы выберут высокие цены, то каждая будет иметь прибыль по 3 млн. Если обе выберут низкие, то каждая получит по 2 млн. Однако, если одна выберет высокие, а другая низкие, то вторая получит 4 млн, а первая только 1 млн. Наиболее выигрышный в сумме вариант — одновременный выбор высоких цен (сумма = 6 млн). Однако это состояние (при отсутствии картельного сговора) нестабильно из-за возможности относительного выигрыша, которая открывается перед фирмой, отступившей от этой стратегии. Поэтому обе компании с наибольшей вероятностью выберут низкие цены. Хотя этот вариант и не даёт максимального суммарного выигрыша (сумма = 4 млн), он исключает относительный выигрыш конкурента, который тот мог бы получить за счёт отступления от взаимно-оптимальной стратегии. Такая ситуация и называется «равновесием по Нэшу»[10]. В модели олигополии Штакельберга для двух фирм-участников бескоалиционной игры можно принять, что существует две стратегии: 1. дуополист Курно (K) и дуополист Штакельберга (S), то есть S-стратег. Таким образом для двух игроков возможны следующие стратегии: (K1;K2) (K1;S2);(K2;S1);(S1;S2). Как следует из построения модели прибыль при выборе стратегии S: ${\displaystyle \pi ^{1}={\frac {(a-c)^{2}}{8b}}}$, а при выборе стратегии K: ${\displaystyle \pi ^{2}={\frac {(a-c)^{2}}{16b}}}$, видно, что максимальный выигрыш первого игрока реализуется в ситуации (S1;K2), а второго (K1;S2). Так как эти ситуации несовместимы, то есть не могут реализоваться одновременно, то получить максимальный выигрыш оба игрока одновременно не могут. В данном случае оптимальным поведением обоих игроков будет выбор стратегии S, так как в этом случае стратегия S лучше стратегии K с точки зрения минимального возможного выигрыша. В данном случае выбор (S1;S2) является равновесием по Нэшу. Односторонее отклонение от данной стратегии автоматически уменьшает выигрыш любого из игроков, при этом суммарный выигрыш в данном типе равновесия меньше суммарного выигрыша при выборе стратегии (K1;K2) обоими игроками. Однако в условиях данной модели при отсутствии обмена информацией между игроками отклонение от равновесия по Нэшу не будет реализовано в виду повышенного риска того, что второй игрок может воспользоваться ситуацией и не выбрать стратегию K. Военное дело Концепция взаимного гарантированного уничтожения. Ни одна из сторон, владеющих ядерным оружием, не может ни безнаказанно начать конфликт, ни разоружиться в одностороннем порядке. См. также Эффективность по Парето Парадокс Бертрана Эволюционно стабильная стратегия Примечания Univertv — Равновесие Нэша: шоппинг, репутация, голосование Архивная копия от 13 декабря 2009 на Wayback Machine. Nash, John F. (1950). Equilibrium points in n-person games. PNAS (англ.). 36 (1): 48–49. 1 2 Джеймс С. Коулман. Экономическая социология с точки зрения теории рационального выбора (рус.) // Экономическая социология : электронный журнал. — 2004. — Т. 5, № 3. — С. 35—44. Архивировано 9 августа 2017 года. «Nash’s Nobel prize» Архивная копия от 26 мая 2015 на Wayback Machine, The Economist, 24 May 2015. Литература Васин А. А., Морозов В. В. Теория игр и модели математической экономики. — М.: МГУ, 2005, 272 с. ISBN 5-317-01388-7. Воробьёв Н. Н. Теория игр для экономистов-кибернетиков. — М.: Наука, 1985 Мазалов В. В. Математическая теория игр и приложения. — Изд-во Лань, 2010, 446 с. Петросян Л. А., Зенкевич Н. А., Шевкопляс Е. В. Теория игр. — СПб: БХВ-Петербург, 2012, 432 с.