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

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

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

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

Если два игрока, Алиса и Боб, выбирают стратегии A и B, (A, B) является равновесием Нэша, если у Алисы нет другой доступной стратегии, которая лучше, чем A, максимизирует свой выигрыш в ответ на выбор Бобом B, и у Боба нет другой стратегии. В игре, в которой Кэрол и Дэн также являются игроками, (A, B, C, D) является равновесием Нэша, если A является лучшим ответом Алисы на ( B, C, D), B — лучший ответ Боба на (A, C, D) и так далее.

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

Приложения

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

Эта концепция использовалась для анализа враждебных ситуаций, таких как войны и гонка вооружений. (см. «Дилемма заключенного» ), а также то, как конфликт можно смягчить путем повторного взаимодействия (см. « око за око» ). Его также использовали для изучения того, в какой степени люди с разными предпочтениями могут сотрудничать (см. «Битва полов» ) и будут ли они идти на риск для достижения совместного результата (см. « Охота на оленя» ). Он использовался для изучения принятия технических стандартов , а также возникновение массового изъятия банковских вкладов и валютных кризисов (см. координационную игру ). Другие приложения включают поток трафика (см. Принцип Уордропа ), способы организации аукционов (см. Теорию аукционов ), результаты усилий нескольких сторон в образовательном процессе, регулирующее законодательство, такое как экологические нормы (см. « Трагедия общего достояния »), управление природными ресурсами, анализ стратегий в маркетинге, пенальти в футболе (см. соответствующие пенни ), навигация робота в толпе, энергетические системы, транспортные системы, проблемы эвакуации и беспроводная связь.

История

Равновесие Нэша названо в честь американского математика Джона Форбса Нэша-младшего . Эту же идею использовал в особом применении в 1838 году Антуан Огюстен Курно в своей теории олигополии . Согласно теории Курно, каждая из нескольких фирм выбирает, какой объем выпускать, чтобы максимизировать свою прибыль. Наилучший выпуск одной фирмы зависит от выпуска других. Равновесие Курно возникает, когда объем выпуска каждой фирмы максимизирует ее прибыль с учетом объема выпуска других фирм, что представляет собой чисто стратегическое равновесие Нэша. Курно также ввел концепцию динамики наилучшего ответа в своем анализе устойчивости равновесия. Однако Курно не использовал эту идею ни в каких других приложениях и не давал ей общего определения.

Современная концепция равновесия Нэша вместо этого определяется в терминах смешанных стратегий , где игроки выбирают распределение вероятностей среди возможных чистых стратегий (которые могут отнести 100% вероятности к одной чистой стратегии; такие чистые стратегии являются подмножеством смешанных стратегий). Концепция равновесия смешанных стратегий была введена Джоном фон Нейманом и Оскаром Моргенштерном в их книге 1944 года «Теория игр и экономического поведения» , но их анализ ограничивался частным случаем игр с нулевой суммой . Они показали, что равновесие Нэша в смешанной стратегии будет существовать для любой игры с нулевой суммой и конечным набором действий. Вклад Нэша в его статье 1951 года «Некооперативные игры» состоял в том, чтобы определить равновесие Нэша со смешанной стратегией для любой игры с конечным набором действий и доказать, что в такой игре должно существовать хотя бы одно равновесие Нэша (со смешанной стратегией). игра. Ключ к способности Нэша доказать существование в гораздо более широком смысле, чем фон Нейман, заключался в его определении равновесия. По словам Нэша, «точка равновесия — это n-кортеж, в котором смешанная стратегия каждого игрока максимизирует [их] выигрыш, если стратегии других остаются фиксированными. Таким образом, стратегия каждого игрока оптимальна по сравнению со стратегиями других». Постановка проблемы в этой форме позволила Нэшу использовать теорему Какутани о неподвижной точке в его статье 1950 года для доказательства существования равновесий. В его статье 1951 года с той же целью использовалась более простая теорема Брауэра о неподвижной точке .

Теоретики игр обнаружили, что в некоторых обстоятельствах равновесие Нэша делает неверные прогнозы или не дает уникальных прогнозов. Они предложили множество концепций решений («уточнений» равновесий Нэша), призванных исключить неправдоподобные равновесия Нэша. Один особенно важный вопрос заключается в том, что некоторые равновесия Нэша могут быть основаны на угрозах, которые не являются « правдоподобными ». В 1965 году Рейнхард Зельтен предложил идеальное равновесие подигры как уточнение, устраняющее равновесия, зависящие от недостоверных угроз . Другие расширения концепции равновесия Нэша касаются того, что происходит, если игра повторяется , или что происходит, если игра ведется в отсутствие полной информации . Однако последующие уточнения и расширения равновесия Нэша разделяют основную идею, на которой основана концепция Нэша: равновесие — это набор стратегий, при котором стратегия каждого игрока является оптимальной с учетом выбора других.

Определения

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

Профиль стратегии — это набор стратегий, по одной для каждого игрока. Неформально, профиль стратегии представляет собой равновесие Нэша, если ни один игрок не может добиться большего, в одностороннем порядке изменив свою стратегию. Чтобы понять, что это значит, представьте, что каждому игроку рассказывают стратегии других. Предположим тогда, что каждый игрок спрашивает себя: «Зная стратегии других игроков и рассматривая стратегии других игроков как высеченные в камне, могу ли я получить выгоду от изменения своей стратегии?»

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

Формально пусть $S_{i}$ быть набором всех возможных стратегий игрока $i$, где $i=1,\ldots ,N$. Позволять $s^{*}=(s_{i}^{*},s_{-i}^{*})$ — профиль стратегии, набор, состоящий из одной стратегии для каждого игрока, где $s_{-i}^{*}$ обозначает $N-1$ стратегии всех игроков, кроме $i$. Позволять $u_{i}(s_{i},s_{-i}^{*})$ Будьте игроком I. Выигрыш как функция стратегии. Профиль стратегии $s^{*}$ является равновесием Нэша, если

$u_{i}(s_{i}^{*},s_{-i}^{*})\geq u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;s_{i}\in S_{i}$

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

$u_{i}(s_{i}^{*},s_{-i}^{*})>u_{i}(s_{i},s_{-i}^{*})\;\;{\rm {for\;all}}\;\;s_{i}\in S_{i},s_{i}\neq s_{i}^{*}$

Набор стратегий $S_{i}$ может быть разным для разных игроков, а его элементами могут быть разнообразные математические объекты. Проще всего, игрок может выбрать одну из двух стратегий, например $S_{i}=\{{\text{Yes}},{\text{No}}\}.$ Или набор стратегий может представлять собой конечный набор условных стратегий, реагирующих на действия других игроков, например $S_{i}=\{{\text{Yes}}|p={\text{Low}},{\text{No}}|p={\text{High}}\}.$ Или это может быть бесконечное множество, континуум или неограниченное множество, например $S_{i}=\{{\text{Price}}\}$ такой, что ${\text{Price}}$ является неотрицательным действительным числом. Существующие доказательства Нэша предполагают конечное множество стратегий, но концепция равновесия Нэша этого не требует.

Варианты

Чистое/смешанное равновесие

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

Строгое/Нестрогое равновесие

Предположим, что в равновесии Нэша каждый игрок задает себе вопрос: «Зная стратегии других игроков и рассматривая стратегии других игроков как высеченные в камне, понесу ли я убытки, изменив свою стратегию?»

Если ответ каждого игрока «Да», то равновесие классифицируется как строгое равновесие Нэша .

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

Равновесие для коалиций

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

Уточненное равновесие Нэша, известное как коалиционно-устойчивое равновесие Нэша (CPNE). происходит, когда игроки не могут добиться большего, даже если им разрешено общаться и заключать «самообеспечивающееся» соглашение об отклонении. Каждая коррелирующая стратегия, поддерживаемая повторяющимся строгим доминированием и находящаяся на границе Парето, представляет собой CPNE. Кроме того, игра может иметь равновесие Нэша, устойчивое к коалициям меньше заданного размера k. CPNE связан с теорией ядра .

Существование

Теорема существования Нэша

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

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

• Игра, в которой два игрока одновременно называют число и побеждает игрок, назвавший большее число, не имеет NE, поскольку множество вариантов выбора не является компактным, поскольку оно неограничено.
• Каждый из двух игроков выбирает вещественное число строго меньше 5, и побеждает тот, у кого число больше; не существует самого большого числа, строго меньшего 5 (если бы это число могло равняться 5, равновесие Нэша привело бы к тому, что оба игрока выбрали бы 5 и сыграли бы вничью). Здесь множество вариантов выбора не является компактным, поскольку оно не замкнуто.

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

Теорема существования Розена

Розен расширил теорему существования Нэша несколькими способами. Он рассматривает игру для n игроков, в которой стратегия каждого игрока i представляет собой вектор s _i в евклидовом пространстве R. ^мне _. Обозначим m := m ₁ +...+ m _n ; поэтому кортеж стратегий — это вектор в R ^м . Частью определения игры является подмножество S из R. ^м такой, что кортеж стратегий должен находиться в S . Это означает, что действия игроков потенциально могут быть ограничены на основе действий других игроков. Обычным частным случаем модели является ситуация, когда является декартовым произведением выпуклых множеств , _S1 ..., Sn _{, такое} что стратегия игрока i должна находиться в Si _. S Это представляет собой случай, когда действия каждого игрока i ограничены независимо от действий других игроков. Если выполняются следующие условия:

• T выпукло , замкнуто и ограничено;
• Каждая функция выигрыша u _i непрерывна в стратегиях всех игроков и вогнута по s _i для каждого фиксированного значения s _{- i} .

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

Результат Нэша относится к частному случаю, в котором каждый Si _{билинейными} является симплексом (представляющим все возможные комбинации чистых стратегий), а функции выигрыша всех игроков являются функциями стратегий.

Рациональность

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

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

Примеры

Координационная игра

Основная статья: Координационная игра

Координационная игра, показывающая выигрыши игрока 1 (строка) \ игрока 2 (столбец)

Стратегия игрока 1	Стратегия игрока 2
	Игрок 2 принимает стратегию А	Игрок 2 принимает стратегию Б
Игрок 1 принимает стратегию А	4 4	3 1
Игрок 1 принимает стратегию Б	1 3	2 2

Координационная игра — это классическая игра для двух игроков с двумя стратегиями , как показано в примере матрицы выигрышей справа. Существует два равновесия в чистой стратегии: (A,A) с выигрышем 4 для каждого игрока и (B,B) с выигрышем 2 для каждого. Комбинация (B,B) представляет собой равновесие Нэша, поскольку если любой из игроков в одностороннем порядке изменит свою стратегию с B на A, его выигрыш упадет с 2 до 1.

Охота на оленя

Стратегия игрока 1	Стратегия игрока 2
	Охота на оленя	Охота на кролика
Охота на оленя	2 2	1 0
Охота на кролика	0 1	1 1

Известный пример координационной игры — охота на оленя . Два игрока могут выбрать охоту на оленя или кролика, причем олень дает больше мяса (4 единицы полезности, по 2 на каждого игрока), чем кролик (1 единица полезности). Предостережение заключается в том, что на оленя необходимо охотиться сообща, поэтому, если один игрок попытается охотиться на оленя, а другой охотится на кролика, охотник на оленей потерпит полную неудачу при выигрыше 0, тогда как охотник на кроликов добьется успеха при выигрыш равен 1. В игре есть два равновесия: (олень, олень) и (кролик, кролик), поскольку оптимальная стратегия игрока зависит от его ожиданий относительно того, что сделает другой игрок. Если один охотник уверен, что другой будет охотиться на оленя, он должен охотиться на оленя; однако, если они думают, что другой будет охотиться на кролика, они тоже будут охотиться на кролика. Эта игра используется как аналогия социального сотрудничества, поскольку большая часть выгод, которые люди получают в обществе, зависит от того, будут ли люди сотрудничать и безоговорочно доверять друг другу в действиях, соответствующих сотрудничеству.

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

Игра вождения

Стратегия игрока 1	Стратегия игрока 2
	Двигайтесь слева	Двигайтесь справа
Двигайтесь слева	10 10	0 0
Двигайтесь справа	0 0	10 10

В этом случае существуют два чисто стратегических равновесия Нэша, когда оба решают двигаться либо влево, либо вправо. Если мы допускаем смешанные стратегии (когда чистая стратегия выбирается случайным образом с некоторой фиксированной вероятностью), то для одного и того же случая существует три равновесия Нэша: два мы видели в форме чистой стратегии, где вероятности равны (0 %, 100%) для первого игрока, (0%, 100%) для второго игрока; и (100%, 0%) для первого игрока и (100%, 0%) для второго игрока соответственно. Добавляем еще один, где вероятности для каждого игрока (50%, 50%).

Сетевой трафик

Смотрите также: парадокс Брасса

Пример сетевого графика. Значения на краях — это время в пути, которое испытывает «автомобиль», едущий по этому краю. $x$ — количество автомобилей, проезжающих через это ребро.

Равновесия Нэша применяются для определения ожидаемого потока трафика в сети. Рассмотрим график справа. Если предположить, что существуют $x$ «автомобили», едущие из A в D , каково ожидаемое распределение трафика в сети?

Эту ситуацию можно смоделировать как « игру », где каждый путешественник имеет выбор из трех стратегий и где каждая стратегия представляет собой маршрут от A до D (одна из ABD , ABCD или ACD ). «Выигрыш» каждой стратегии — это время в пути по каждому маршруту. На графике справа поездки автомобиля через ABD составляет время $1+{\frac {x}{100}}+2$, где $x$ — количество автомобилей, едущих по ребру AB . Таким образом, выигрыши для любой данной стратегии, как обычно, зависят от выбора других игроков. Однако в данном случае цель состоит в том, чтобы минимизировать время в пути, а не максимизировать его. Равновесие наступит, когда время на всех путях будет совершенно одинаковым. Когда это происходит, ни у одного водителя нет стимула менять маршрут, поскольку это может только увеличить время в пути. Для графика справа, если, например, 100 автомобилей едут из A в D , то равновесие наступит, когда 25 водителей едут через ABD , 50 через ABCD и 25 через ACD . Общее время поездки каждого водителя теперь равно 3,75 (чтобы увидеть это, в общей сложности 75 автомобилей занимают ребро AB , а также 75 машин занимают ребро CD ).

Обратите внимание, что это распределение на самом деле не является социально оптимальным. Если 100 автомобилей договорились, что 50 будут путешествовать через ABD , а остальные 50 — через ACD , то время в пути для любого отдельного автомобиля фактически составит 3,5, что меньше 3,75. Это также равновесие Нэша, если путь между B и C удален, а это означает, что добавление еще одного возможного маршрута может снизить эффективность системы - явление, известное как парадокс Брасса .

Конкурсная игра

Игра-соревнование

Стратегия игрока 1	Стратегия игрока 2
	Выберите «0»	Выберите «1»	Выберите «2»	Выберите «3»
Выберите «0»	0 , 0	2 , −2	2 , −2	2 , −2
Выберите «1»	−2 , 2	1 , 1	3 , −1	3 , −1
Выберите «2»	−2 , 2	−1 , 3	2 , 2	4 , 0
Выберите «3»	−2 , 2	−1 , 3	0 , 4	3 , 3

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

В этой игре существует уникальное равновесие Нэша, основанное на чистой стратегии: оба игрока выбирают 0 (выделено светло-красным). Любую другую стратегию можно улучшить, если игрок изменит свое число на одно меньшее, чем у другого игрока. В соседней таблице, если игра начинается с зеленого квадрата, в интересах игрока 1 перейти на фиолетовый квадрат, а в интересах игрока 2 — перейти на синий квадрат. Хотя это не соответствует определению соревновательной игры, если игра модифицирована так, что два игрока выигрывают указанную сумму, если они оба выбирают одно и то же число, а в противном случае ничего не выигрывают, то существует 4 равновесия Нэша: (0,0 ), (1,1), (2,2) и (3,3).

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

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

Матрица выигрышей – равновесия Нэша выделены жирным шрифтом.

Стратегия игрока 1	Стратегия игрока 2
	Вариант А	Вариант Б	Вариант С
Вариант А	0, 0	25, 40	5, 10
Вариант Б	40, 25	0, 0	5, 15
Вариант С	10, 5	15, 5	10, 10

Мы можем применить это правило к матрице 3×3:

Используя это правило, мы можем очень быстро (намного быстрее, чем при формальном анализе) увидеть, что ячейками равновесия Нэша являются (B,A), (A,B) и (C,C). Действительно, для ячейки (B,A) 40 — это максимум первого столбца, а 25 — максимум второй строки. Для (A,B) 25 — максимум второго столбца, а 40 — максимум первой строки; то же самое относится и к ячейке (C,C). Для других ячеек один или оба элемента дуплета не являются максимальными из соответствующих строк и столбцов.

При этом сама механика поиска равновесных ячеек очевидна: найдите максимум столбца и проверьте, является ли второй член пары максимумом строки. Если эти условия соблюдены, ячейка представляет собой равновесие Нэша. Таким образом проверьте все столбцы, чтобы найти все ячейки NE. Матрица N×N может иметь от 0 до N×N равновесий Нэша чистой стратегии .

Стабильность

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

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

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

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

В приведенном выше примере «вождения» существуют как стабильные, так и нестабильные состояния равновесия. Равновесия, включающие смешанные стратегии со 100%-ной вероятностью, устойчивы. Если любой из игроков немного изменит свои вероятности, они оба окажутся в невыгодном положении, и у их противника не будет причин, в свою очередь, менять свою стратегию. Равновесие (50%,50%) неустойчиво. Если любой из игроков меняет свои вероятности (что не принесет ни пользы, ни ущерба ожиданиям игрока, внесшего это изменение, если смешанная стратегия другого игрока все еще (50%,50%)), то у другого игрока сразу же появляется лучшая стратегия при либо (0%, 100%), либо (100%, 0%).

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

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

возникновение

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

1. Все игроки сделают все возможное, чтобы максимизировать ожидаемый выигрыш, как описано в игре.
2. Игроки безупречны в исполнении.
3. У игроков достаточно интеллекта, чтобы найти решение.
4. Игроки знают запланированную равновесную стратегию всех остальных игроков.
5. Игроки считают, что отклонение в их собственной стратегии не вызовет отклонений со стороны других игроков.
6. Общеизвестно , что этим условиям соответствуют все игроки, в том числе и этот. Таким образом, каждый игрок не только должен знать, что другие игроки соответствуют условиям, но также он должен знать, что все они знают, что они соответствуют им, и знать, что они знают, что они знают, что они им соответствуют, и так далее.

Если условия не соблюдены

Примеры задач теории игр , в которых эти условия не выполняются:

1. Первое условие не выполняется, если игра неправильно описывает количества, которые игрок хочет максимизировать. В этом случае у этого игрока нет особой причины принимать равновесную стратегию. Например, дилемма заключенного не является дилеммой, если любой из игроков рад оказаться в тюрьме на неопределенный срок.
2. Намеренное или случайное несовершенство исполнения. Например, компьютер, способный безупречно вести логическую игру, лицом к лицу со вторым безупречным компьютером, приведет к равновесию. Введение несовершенства приведет к его нарушению либо через проигрыш игрока, допустившего ошибку, либо через отрицание критерия общеизвестности, ведущего к возможной победе игрока. (Примером может служить игрок, внезапно включивший задний ход в игре с курицей , гарантируя сценарий без потерь и без выигрыша).
3. Во многих случаях третье условие не выполняется, поскольку, хотя равновесие и должно существовать, оно неизвестно из-за сложности игры, например, в китайских шахматах . Или, если оно известно, оно может быть известно не всем игрокам, как при игре в крестики-нолики с маленьким ребенком, который отчаянно хочет выиграть (соответствует другим критериям).
4. Критерий общеизвестности может не соблюдаться, даже если все игроки действительно соответствуют всем остальным критериям. Игроки, ошибочно не доверяющие рациональности друг друга, могут принять контрстратегии против ожидаемой иррациональной игры от имени своих оппонентов. Это важный фактор в « цыплятах » или гонке вооружений . , например,

Где условия соблюдены

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

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

Эта идея была формализована Р. Ауманном и А. Бранденбургером, 1995, Epistemic Conditions for Nash Equilibrium , Econometrica, 63, 1161-1180, которые интерпретировали смешанную стратегию каждого игрока как гипотезу о поведении других игроков и показали, что если игра и рациональность игроков взаимно известна и эти гипотезы общеизвестны, то гипотезы должны представлять собой равновесие Нэша (для этого результата необходимо общее априорное предположение в целом, но не в случае двух игроков. В этом случае предположения должны быть только взаимно известны).

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

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

Формальный результат в этом направлении см. в Kuhn, H. and et al., 1996, «The Work of John Nash in Game Theory», Journal of Economic Theory , 69, 153–185.

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

НЭ и недостоверные угрозы

Иллюстрации расширенной и нормальной формы, показывающие разницу между SPNE и другими NE. Синее равновесие не является идеальным в подигре, потому что второй игрок делает неправдоподобную угрозу в 2(2) недоброй (U).

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

На изображении справа показана простая последовательная игра, которая иллюстрирует проблему с несовершенными равновесиями Нэша в подыграх. В этой игре первый игрок выбирает левую (L) или правую (R), после чего второго игрока призывают быть добрым (K) или недобрым (U) к первому игроку. Однако второй игрок только выиграет от того, что будет неприятно, если первый игрок пойдет налево. Если первый игрок сделает правильный выбор, второй рациональный игрок будет фактически добр к нему/ней в этой подигре. Однако неправдоподобная угроза недобрости при 2(2) по-прежнему является частью синего (L, (U,U)) равновесия Нэша. Следовательно, если обе стороны могут ожидать рационального поведения, идеальное равновесие Нэша в подыгре может быть более значимой концепцией решения, когда возникают такие динамические несоответствия .

Доказательство существования

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

Первоначальное доказательство Нэша (в его диссертации) использовало теорему Брауэра о неподвижной точке (вариант см., например, ниже). В этом разделе представлено более простое доказательство с помощью теоремы Какутани о неподвижной точке , следуя статье Нэша 1950 года (он благодарит Дэвида Гейла за наблюдение о том, что такое упрощение возможно).

Чтобы доказать существование равновесия по Нэшу, пусть $r_{i}(\sigma _{-i})$ быть лучшим ответом игрока i на стратегии всех остальных игроков.

$r_{i}(\sigma _{-i})=\mathop {\underset {\sigma _{i}}{\operatorname {arg\,max} }} u_{i}(\sigma _{i},\sigma _{-i})$

Здесь, $\sigma \in \Sigma$, где $\Sigma =\Sigma _{i}\times \Sigma _{-i}$, представляет собой профиль смешанной стратегии в множестве всех смешанных стратегий и $u_{i}$ – функция выигрыша для игрока i. Определите функцию с множеством значений $r\colon \Sigma \rightarrow 2^{\Sigma }$ такой, что $r=r_{i}(\sigma _{-i})\times r_{-i}(\sigma _{i})$. Существование равновесия по Нэшу эквивалентно тому, что $r$ наличие фиксированной точки.

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

1. $\Sigma$ компактно, выпукло и непусто.
2. $r(\sigma )$ непусто.
3. $r(\sigma )$ является верхнеполунепрерывным
4. $r(\sigma )$ является выпуклым.

Условие 1. выполняется в силу того, что $\Sigma$ является симплексом и, следовательно, компактным. Выпуклость возникает из способности игроков смешивать стратегии. $\Sigma$ непусто, пока у игроков есть стратегии.

Условия 2 и 3 удовлетворяются посредством теоремы Бержа о максимуме . Потому что $u_{i}$ является непрерывным и компактным, $r(\sigma _{i})$ непусто и полунепрерывно сверху .

Условие 4. выполняется в результате смешанных стратегий. Предполагать $\sigma _{i},\sigma '_{i}\in r(\sigma _{-i})$, затем $\lambda \sigma _{i}+(1-\lambda )\sigma '_{i}\in r(\sigma _{-i})$. т. е. если две стратегии максимизируют выигрыш, то сочетание двух стратегий даст один и тот же выигрыш.

Следовательно, существует неподвижная точка в $r$ и равновесие Нэша.

Когда Нэш высказал эту точку зрения Джону фон Нейману в 1949 году, фон Нейман, как известно, отклонил ее словами: «Знаете, это тривиально. Это всего лишь теорема о неподвижной точке ». (См. Насар, 1998, стр. 94.)

Альтернативное доказательство с использованием теоремы Брауэра о неподвижной точке.

У нас есть игра $G=(N,A,u)$ где $N$ количество игроков и $A=A_{1}\times \cdots \times A_{N}$ это набор действий для игроков. Все наборы действий $A_{i}$ конечны. Позволять $\Delta =\Delta _{1}\times \cdots \times \Delta _{N}$ обозначим множество смешанных стратегий игроков. Конечность $A_{i}$s обеспечивает компактность $\Delta$.

Теперь мы можем определить функции усиления. Для смешанной стратегии $\sigma \in \Delta$, мы даем выигрыш игроку $i$ по действию $a\in A_{i}$ быть

${\text{Gain}}_{i}(\sigma ,a)=\max\{0,u_{i}(a,\sigma _{-i})-u_{i}(\sigma _{i},\sigma _{-i})\}.$

Функция выигрыша представляет собой выгоду, которую получает игрок, изменив свою стратегию в одностороннем порядке. Теперь мы определяем $g=(g_{1},\dotsc ,g_{N})$ где

$g_{i}(\sigma )(a)=\sigma _{i}(a)+{\text{Gain}}_{i}(\sigma ,a)$

для $\sigma \in \Delta ,a\in A_{i}$. Мы видим это

$\sum _{a\in A_{i}}g_{i}(\sigma )(a)=\sum _{a\in A_{i}}\sigma _{i}(a)+{\text{Gain}}_{i}(\sigma ,a)=1+\sum _{a\in A_{i}}{\text{Gain}}_{i}(\sigma ,a)>0.$

Далее мы определяем:

${\begin{cases}f=(f_{1},\cdots ,f_{N}):\Delta \to \Delta \\f_{i}(\sigma )(a)={\frac {g_{i}(\sigma )(a)}{\sum _{b\in A_{i}}g_{i}(\sigma )(b)}}&a\in A_{i}\end{cases}}$

Легко видеть, что каждый $f_{i}$ является допустимой смешанной стратегией в $\Delta _{i}$. Также легко проверить, что каждый $f_{i}$ является непрерывной функцией $\sigma$, и, следовательно, $f$ является непрерывной функцией. Как векторное произведение конечного числа выпуклых компактов, $\Delta$ также компактен и выпукл. Применяя теорему Брауэра о неподвижной точке к $f$ и $\Delta$ мы заключаем, что $f$ имеет фиксированную точку в $\Delta$, позвони $\sigma ^{*}$. Мы утверждаем, что $\sigma ^{*}$ является равновесием Нэша в $G$. Для этого достаточно показать, что

$\forall i\in \{1,\cdots ,N\},\forall a\in A_{i}:\quad {\text{Gain}}_{i}(\sigma ^{*},a)=0.$

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

Теперь предположим, что не все выигрыши равны нулю. Поэтому, $\exists i\in \{1,\cdots ,N\},$ и $a\in A_{i}$ такой, что ${\text{Gain}}_{i}(\sigma ^{*},a)>0$. Затем

$\sum _{a\in A_{i}}g_{i}(\sigma ^{*},a)=1+\sum _{a\in A_{i}}{\text{Gain}}_{i}(\sigma ^{*},a)>1.$

Так что пусть

$C=\sum _{a\in A_{i}}g_{i}(\sigma ^{*},a).$

Также будем обозначать ${\text{Gain}}(i,\cdot )$ как вектор выигрыша, индексированный действиями в $A_{i}$. С $\sigma ^{*}$ это фиксированная точка, которую мы имеем:

${\begin{aligned}\sigma ^{*}=f(\sigma ^{*})&\Rightarrow \sigma _{i}^{*}=f_{i}(\sigma ^{*})\\&\Rightarrow \sigma _{i}^{*}={\frac {g_{i}(\sigma ^{*})}{\sum _{a\in A_{i}}g_{i}(\sigma ^{*})(a)}}\\[6pt]&\Rightarrow \sigma _{i}^{*}={\frac {1}{C}}\left(\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot )\right)\\[6pt]&\Rightarrow C\sigma _{i}^{*}=\sigma _{i}^{*}+{\text{Gain}}_{i}(\sigma ^{*},\cdot )\\&\Rightarrow \left(C-1\right)\sigma _{i}^{*}={\text{Gain}}_{i}(\sigma ^{*},\cdot )\\&\Rightarrow \sigma _{i}^{*}=\left({\frac {1}{C-1}}\right){\text{Gain}}_{i}(\sigma ^{*},\cdot ).\end{aligned}}$

С $C>1$ у нас есть это $\sigma _{i}^{*}$ это некоторое положительное масштабирование вектора ${\text{Gain}}_{i}(\sigma ^{*},\cdot )$. Теперь мы утверждаем, что

$\forall a\in A_{i}:\quad \sigma _{i}^{*}(a)(u_{i}(a_{i},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*}))=\sigma _{i}^{*}(a){\text{Gain}}_{i}(\sigma ^{*},a)$

Чтобы увидеть это, сначала если ${\text{Gain}}_{i}(\sigma ^{*},a)>0$ тогда это верно по определению функции усиления. Теперь предположим, что ${\text{Gain}}_{i}(\sigma ^{*},a)=0$. Из наших предыдущих утверждений мы имеем, что

$\sigma _{i}^{*}(a)=\left({\frac {1}{C-1}}\right){\text{Gain}}_{i}(\sigma ^{*},a)=0$

и поэтому левый член равен нулю, что дает нам понять, что все выражение равно $0$ по мере необходимости.

Итак, мы наконец-то это получили

${\begin{aligned}0&=u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})\\&=\left(\sum _{a\in A_{i}}\sigma _{i}^{*}(a)u_{i}(a_{i},\sigma _{-i}^{*})\right)-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*})\\&=\sum _{a\in A_{i}}\sigma _{i}^{*}(a)(u_{i}(a_{i},\sigma _{-i}^{*})-u_{i}(\sigma _{i}^{*},\sigma _{-i}^{*}))\\&=\sum _{a\in A_{i}}\sigma _{i}^{*}(a){\text{Gain}}_{i}(\sigma ^{*},a)&&{\text{ by the previous statements }}\\&=\sum _{a\in A_{i}}\left(C-1\right)\sigma _{i}^{*}(a)^{2}>0\end{aligned}}$

где последнее неравенство следует, поскольку $\sigma _{i}^{*}$ является ненулевым вектором. Но это явное противоречие, поэтому все выгоды действительно должны быть равны нулю. Поэтому, $\sigma ^{*}$ является равновесием Нэша для $G$ по мере необходимости.

Вычисление равновесия Нэша

Если игрок А имеет доминирующую стратегию $s_{A}$ тогда существует равновесие Нэша, в котором A играет $s_{A}$. В случае двух игроков A и B существует равновесие Нэша, при котором A играет $s_{A}$ и B играет лучший ответ на $s_{A}$. Если $s_{A}$ является строго доминирующей стратегией, игрок А играет $s_{A}$ во всех равновесиях Нэша. Если и A, и B имеют строго доминирующие стратегии, существует уникальное равновесие Нэша, в котором каждый использует свою строго доминирующую стратегию.

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

Примеры

Соответствующие пенни

Стратегия	Игрок Б играет H	Игрок Б играет Т
Игрок А играет H	−1, +1	+1, −1
Игрок А играет Т	+1, −1	−1, +1

В игре «Сопоставление монет» игрок А теряет очко игроку Б, если А и Б используют одну и ту же стратегию, и выигрывает очко у игрока Б, если они используют разные стратегии. Чтобы вычислить равновесие Нэша смешанной стратегии, присвойте A вероятность $p$ играть в H и $(1-p)$ сыграть T и присвоить B вероятность $q$ играть в H и $(1-q)$ играть Т.

$${\begin{aligned}&\mathbb {E} [{\text{payoff for A playing H}}]=(-1)q+(+1)(1-q)=1-2q\\&\mathbb {E} [{\text{payoff for A playing T}}]=(+1)q+(-1)(1-q)=2q-1\\&\mathbb {E} [{\text{payoff for A playing H}}]=\mathbb {E} [{\text{payoff for A playing T}}]\implies 1-2q=2q-1\implies q={\frac {1}{2}}\\&\mathbb {E} [{\text{payoff for B playing H}}]=(+1)p+(-1)(1-p)=2p-1\\&\mathbb {E} [{\text{payoff for B playing T}}]=(-1)p+(+1)(1-p)=1-2p\\&\mathbb {E} [{\text{payoff for B playing H}}]=\mathbb {E} [{\text{payoff for B playing T}}]\implies 2p-1=1-2p\implies p={\frac {1}{2}}\\\end{aligned}}$$

Таким образом, равновесие Нэша в смешанной стратегии в этой игре заключается в том, что каждый игрок случайным образом выбирает H или T с $p={\frac {1}{2}}$ и $q={\frac {1}{2}}$.

Нечетность точек равновесия

Бесплатная игра на деньги

Стратегия	Игрок Б голосует «Да»	Игрок Б голосует «нет»
Игрок А голосует за	1, 1	0, 0
Игрок А голосует «нет»	0, 0	0, 0

В 1971 году Роберт Уилсон сформулировал теорему нечетности. который говорит, что «почти все» конечные игры имеют конечное и нечетное число равновесий Нэша. В 1993 году Харсаньи опубликовал альтернативное доказательство результата. «Почти все» здесь означает, что любая игра с бесконечным или четным числом равновесий является совершенно особенной в том смысле, что если бы ее выигрыши были хотя бы слегка случайно изменены, то с вероятностью единица вместо этого было бы нечетное число равновесий.

имеется в дилемме заключенного Например, одно равновесие, а в битве полов — три — два чистых и одно смешанное, и это остается верным, даже если выигрыши немного изменяются. Игра на бесплатные деньги — это пример «особой» игры с четным числом равновесий. В нем два игрока должны проголосовать «за», а не «нет», чтобы получить награду, и голоса происходят одновременно. Существует два равновесия Нэша в чистой стратегии (да, да) и (нет, нет), а равновесий смешанной стратегии нет, поскольку стратегия «да» слабо доминирует над «нет». «Да» так же хорошо, как «нет», независимо от действий другого игрока, но если есть хоть какая-то вероятность, что другой игрок выберет «да», то «да» будет лучшим ответом. Однако при небольшом случайном возмущении выигрышей вероятность того, что любые два выигрыша останутся связанными, будь то 0 или какое-то другое число, исчезающе мала, и вместо этого в игре будет одно или три равновесия.

См. также

• Скорректированная процедура победителя – метод справедливого раздела имущества
• Теория дополнительности - тип задачи математической оптимизации. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Разрешение конфликтов . Методы и процессы, способствующие мирному прекращению конфликта и возмездию.
• Сотрудничество – группы, работающие или действующие вместе.
• Выбор равновесия
• Эволюционно стабильная стратегия - концепция решения в теории игр
• Глоссарий теории игр - Список определений терминов и понятий, используемых в теории игр.
• Закон Хотеллинга - Наблюдение в экономике
• Управляемое равновесие Нэша
• Мексиканское противостояние - Тип противостояния
• Теорема о минимаксе - дает условия, которые гарантируют, что неравенство макс-мин также является равенством.
• Гарантированное взаимное уничтожение – Доктрина военной стратегии
• Расширенное математическое программирование для задач равновесия
• Оптимальный контракт и номинальный контракт – условия подсчета очков в бридж контракта на карточную игру
• Самоподтверждающееся равновесие
• Концепция решения – формальное правило для прогнозирования того, как будет вестись игра.
• Конкуренция Штакельберга – Экономическая модель
• Принцип Уордропа - главный теоретик равновесия транспортных потоков. Страницы с краткими описаниями целей перенаправления.

Библиография

Учебники по теории игр

• Бинмор, Кен (2007), Игра по-настоящему: текст по теории игр , Oxford University Press , ISBN  978-0195300574 .
• Диксит, Авинаш, Сьюзен Скит и Дэвид Рейли. Стратегические игры . WW Нортон и компания. (Третье издание в 2009 г.) Текст для студентов.
• Дутта, Праджит К. (1999), Стратегии и игры: теория и практика , MIT Press , ISBN  978-0-262-04169-0 . Подходит для студентов бакалавриата и бизнеса.
• Фуденберг, Дрю и Жан Тироль (1991) Теория игр MIT Press.
• Гиббонс, Роберт (1992), Теория игр для экономистов-прикладников , Princeton University Press (13 июля 1992 г.), ISBN  978-0-691-00395-5 . Яркое и подробное введение в теорию игр в явно экономическом контексте.
• Моргенштерн, Оскар и Джон фон Нейман (1947) Теория игр и экономическое поведение Издательство Принстонского университета.
• Майерсон, Роджер Б. (1997), Теория игр: анализ конфликта , издательство Гарвардского университета , ISBN  978-0-674-34116-6
• Осборн, Мартин (2004), Введение в теорию игр , Oxford University Press , ISBN  978-0-19-512895-6 .
• Папайоану, Пол (2010), Теория игр для бизнеса: учебник по стратегическим играм , вероятностное издание , ISBN  978-0964793873
• Рубинштейн, Ариэль ; Осборн, Мартин Дж. (1994), Курс теории игр , MIT Press , ISBN  978-0-262-65040-3 . Современное введение на уровне выпускников.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы , Нью-Йорк: Издательство Кембриджского университета , ISBN  978-0-521-89943-7 . Полный справочник с вычислительной точки зрения; см. главу 3. Можно бесплатно загрузить в Интернете .

Оригинальные документы Нэша

• Нэш, Джон (1950) «Точки равновесия в играх n человек» Proceedings of the National Academy of Sciences 36(1):48-49.
• Нэш, Джон (1951) «Некооперативные игры» Анналы математики 54 (2): 286–295.

Другие ссылки

• Мельманн, А. (2000) Игра начинается! Теория игр в мифах и парадоксах , Американское математическое общество .
• Назар, Сильвия (1998), «Игры разума» , Саймон и Шустер .
• Авиад Рубинштейн: «Трудность аппроксимации между P и NP», ACM, ISBN 978-1-947487-23-9 (май 2019 г.), DOI: https://doi.org/10.1145/3241304 . # Объясняет, что равновесие Нэша представляет собой сложную задачу в вычислениях.

Внешние ссылки

• «Теорема Нэша (в теории игр)» , Энциклопедия математики , EMS Press , 2001 [1994]
• Полное доказательство существования равновесий Нэша
• Упрощенная форма и соответствующие результаты, заархивированные 31 июля 2021 г. на Wayback Machine.