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

Концепция решения некооперативной игры

В теории игр равновесие Нэша , названное в честь математика Джона Нэша , является наиболее распространенным способом определения решения некооперативной игры с участием двух или более игроков. В равновесии Нэша предполагается, что каждый игрок знает равновесные стратегии других игроков, и никто не получит никакой выгоды, изменив только свою собственную стратегию. ^[1] Принцип равновесия Нэша восходит к временам Курно , который в 1838 году применил его к конкурирующим фирмам, выбирающим объемы выпуска. ^[2]

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

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

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

Приложения

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

Эта концепция использовалась для анализа враждебных ситуаций, таких как войны и гонка вооружений ^[4] (см. «Дилемма заключенного »), а также того, как конфликт можно смягчить путем повторяющегося взаимодействия (см. «око за око» ). Его также использовали для изучения того, в какой степени люди с разными предпочтениями могут сотрудничать (см. « Битва полов ») и будут ли они рисковать ради достижения совместного результата (см. « Охота на оленя »). Он использовался для изучения принятия технических стандартов , ^{[ нужна ссылка ]} , а также случаев массового изъятия банковских вкладов и валютных кризисов (см. координационную игру ). Другие приложения включают транспортный поток (см. принцип Уордропа ), способы организации аукционов (см. теорию аукционов ), результаты усилий, приложенных множеством сторон в образовательном процессе, ^[5] нормативное законодательство, такое как экологические нормы (см. Трагедию общего достояния ). , ^[6] управление природными ресурсами, ^[7] анализ стратегий в маркетинге, ^[8] даже пенальти в футболе (см. сопоставление пенни ), ^[9] энергетические системы, транспортные системы, проблемы эвакуации ^[10] и беспроводная связь. ^[11]

История

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

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

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

Определения

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

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

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

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

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

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

${\displaystyle 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}^{*}}$

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

Варианты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мы можем применить это правило к матрице 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. Во многих случаях третье условие не выполняется, поскольку, хотя равновесие и должно существовать, оно неизвестно из-за сложности игры, например, в китайских шахматах . ^[22] Или, если оно известно, оно может быть известно не всем игрокам, как при игре в крестики-нолики с маленьким ребенком, который отчаянно хочет выиграть (соответствует другим критериям).
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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следовательно, существует фиксированная точка и равновесие по Нэшу. ^[24] ${\displaystyle r}$

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

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

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

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

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

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

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

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

${\displaystyle \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.}$

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

${\displaystyle {\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}}}$

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

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

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

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

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

Так что давайте

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

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

${\displaystyle {\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}}}$

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

${\displaystyle \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)}$

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

Примеры

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

$${\displaystyle {\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 с помощью и . ${\displaystyle p={\frac {1}{2}}}$ ${\displaystyle q={\frac {1}{2}}}$

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

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

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

Смотрите также

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

Рекомендации

1. Осборн, Мартин Дж.; Рубинштейн, Ариэль (12 июля 1994 г.). Курс теории игр . Кембридж, Массачусетс: Массачусетский технологический институт. п. 14. ISBN 9780262150415.
2. Крепс Д.М. (1987) «Равновесие Нэша». В: Пэлгрейв Макмиллан (ред.) Новый экономический словарь Пэлгрейва . Пэлгрейв Макмиллан, Лондон.
3. Нэш, Джон Ф. (1950). «Точки равновесия в играх n человек». ПНАС . 36 (1): 48–49. дои :10.1073/pnas.36.1.48. ПМЦ 1063129 . 
4. Шеллинг, Томас, Стратегия конфликта , авторские права 1960, 1980, издательство Гарвардского университета, ISBN 0-674-84031-3 . 
5. Де Фраха, Г.; Оливейра, Т.; Занчи, Л. (2010). «Надо стараться больше: оценка роли усилий в достижении образования». Обзор экономики и статистики . 92 (3): 577. doi : 10.1162/REST_a_00013. hdl : 2108/55644 . S2CID  57072280.
6. Уорд, Х. (1996). «Теория игр и политика глобального потепления: состояние дел и за его пределами». Политические исследования . 44 (5): 850–871. doi :10.1111/j.1467-9248.1996.tb00338.x. S2CID  143728467.,
7. Торп, Роберт Б.; Дженнингс, Саймон; Долдер, Пол Дж. (2017). «Риски и преимущества получения довольно хорошего улова при многовидовом смешанном рыболовстве». Журнал морских наук ICES . 74 (8): 2097–2106. doi : 10.1093/icesjms/fsx062 .,
8. «Уроки маркетинга от доктора Нэша - Эндрю Франк». 25 мая 2015 г. Проверено 30 августа 2015 г.
9. Чиаппори, П.-А.; Левитт, С.; Гросеклоуз, Т. (2002). «Тестирование равновесия смешанной стратегии, когда игроки разнородны: случай пенальти в футболе» (PDF) . Американский экономический обзор . 92 (4): 1138. CiteSeerX 10.1.1.178.1646 . дои : 10.1257/00028280260344678. 
10. Джехиче, Б.; Чукам, А.; Тембине, Х. (2017). «Среднеполевая игра эвакуации в многоуровневом здании». Транзакции IEEE при автоматическом управлении . 62 (10): 5154–5169. дои : 10.1109/TAC.2017.2679487. ISSN  0018-9286. S2CID  21850096.
11. Джеиш, Буалем; Чеукам, Ален; Тембине, Хамиду (27 сентября 2017 г.). «Игры типа среднего поля в технике». АИМС Электроника и электротехника . 1 : 18–73. arXiv : 1605.03281 . doi :10.3934/ElectrEng.2017.1.18. S2CID  16055840.
12. Курно А. (1838) Исследования математических принципов теории богатства
13. Дж. Фон Нейман, О. Моргенштерн, Теория игр и экономического поведения , авторские права 1944, 1953, Princeton University Press.
14. Кармона, Гильерме; Подчек, Конрад (2009). «О существовании равновесия Нэша в чистой стратегии в больших играх» (PDF) . Журнал экономической теории . 144 (3): 1300–1319. дои : 10.1016/j.jet.2008.11.009. hdl : 10362/11577 . ССНР  882466.
15. фон Ан, Луис. «Предварительные сведения о теории игр» (PDF) . Архивировано из оригинала (PDF) 18 октября 2011 г. Проверено 7 ноября 2008 г.
16. "Равновесия Нэша". hoylab.cornell.edu . Проверено 8 декабря 2019 г.
17. BD Бернхайм; Б. Пелег; МД Уинстон (1987), «Коалиционное равновесие I. Концепции», Журнал экономической теории , 42 (1): 1–12, doi : 10.1016/0022-0531(87)90099-8.
18. Ауманн, Р. (1959). «Приемлемые баллы в общих кооперативных играх для n человек». Вклад в теорию игр . Том. IV. Принстон, Нью-Джерси: Издательство Принстонского университета. ISBN 978-1-4008-8216-8.
19. Д. Морено; Дж. Вудерс (1996), «Равновесие, защищенное от коалиции» (PDF) , Игры и экономическое поведение , 17 (1): 80–112, doi : 10.1006/game.1996.0095, hdl : 10016/4408 .
20. MIT OpenCourseWare. 6.254: Теория игр с инженерными приложениями, весна 2010 г. Лекция 6: Непрерывные и прерывистые игры.
21. Розен, Дж. Б. (1965). «Существование и уникальность точек равновесия для вогнутых игр N лиц». Эконометрика . 33 (3): 520–534. дои : 10.2307/1911749. hdl : 2060/19650010164 . ISSN  0012-9682.
22. Т. Л. Туроци, Б. Фон Стенгель, Теория игр , авторские права 2001 г., Техасский университет A&M, Лондонская школа экономики, страницы 141–144. Нэш доказал, что для этого типа игры конечной экстенсивной формы существует идеальный НЭ ^{[ нужна ссылка ]} – ее можно представить как стратегию, соответствующую его первоначальным условиям для игры с НЭ. Такие игры могут не иметь уникального NE, но, по крайней мере , в одну из многих равновесных стратегий будут играть гипотетические игроки, прекрасно знающие ^все 10 ^{150 игровых} деревьев ^.
23. Дж. К. Кокс, М. Уокер, Обучение игре в стратегии Cournot Duoploy. Архивировано 11 декабря 2013 г. в Wayback Machine , авторские права 1997 г., Техасский университет A&M, Университет Аризоны, страницы 141–144.
24. Фуденбург, Дрю; Тироль, Жан (1991). Теория игры . МТИ Пресс. ISBN 978-0-262-06141-4.
25. Уилсон, Роберт (1 июля 1971). «Вычисление равновесий в играх N-человека». SIAM Journal по прикладной математике . 21 (1): 80–87. дои : 10.1137/0121011. ISSN  0036-1399.
26. Харсаньи, JC (1 декабря 1973 г.). «Нечетность числа точек равновесия: новое доказательство». Международный журнал теории игр . 2 (1): 235–250. дои : 10.1007/BF01737572. ISSN  1432-1270. S2CID  122603890.

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

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

• Бинмор, Кен (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), Теория игр для бизнеса: учебник по стратегическим играм , Probabilistic Publishing, ISBN 978-0964793873
• Рубинштейн, Ариэль ; Осборн, Мартин Дж. (1994), Курс теории игр , MIT Press , ISBN 978-0-262-65040-3. Современное введение на уровне выпускников.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Мультиагентные системы: алгоритмические, теоретико-игровые и логические основы, Нью-Йорк: Cambridge University Press , 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.