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

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

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

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

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

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

Приложения

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

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

История

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

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

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

Определения

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

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

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

Формально, пусть будет набором всех возможных стратегий для игрока , где . Пусть будет профилем стратегий, набором, состоящим из одной стратегии для каждого игрока, где обозначает стратегии всех игроков, кроме . Пусть будет выигрышем игрока 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}}}$

Варианты

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

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

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

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

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

Если же вместо этого для какого-либо игрока наблюдается точное равенство между стратегией в равновесии Нэша и какой-либо другой стратегией, которая дает точно такую ​​же выплату (т. е. игроку безразлично, переключаться или нет), то равновесие классифицируется как слабое ^{[примечание 1]} или нестрогое равновесие Нэша ^{[ требуется ссылка ] [ требуется разъяснение ]} .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

Игра на координацию

Координационная игра — это классическая игра с двумя игроками и двумя стратегиями , как показано в примере матрицы выигрышей справа. Существует два равновесия чистых стратегий: (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}$

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

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

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

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

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

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

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

Для получения формального результата в этом направлении см. Kuhn, H. и др., 1996, «Работа Джона Нэша в теории игр», Журнал экономической теории , 69, 153–185.

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

NE и нереальные угрозы

Иллюстрации в развернутой и нормальной форме, демонстрирующие разницу между 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})}$

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

Когда Нэш высказал эту точку зрения Джону фон Нейману в 1949 году, фон Нейман, как известно, отверг ее словами: «Это тривиально, вы знаете. Это всего лишь теорема о неподвижной точке ». (См. Nasar, 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 есть доминирующая стратегия , то существует равновесие Нэша, в котором A играет . В случае двух игроков A и B существует равновесие Нэша, в котором A играет , а B играет наилучший ответ на . Если — строго доминирующая стратегия, A играет во всех равновесиях Нэша. Если и A, и B имеют строго доминирующие стратегии, то существует уникальное равновесие Нэша, в котором каждый играет свою строго доминирующую стратегию. ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$ ${\displaystyle s_{A}}$

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

Примеры

В игре «Соответствующие пенни» игрок A проигрывает очко B, если A и B играют одну и ту же стратегию, и выигрывает очко у B, если они играют разные стратегии. Чтобы вычислить равновесие Нэша со смешанной стратегией, назначьте 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 году Роберт Уилсон сформулировал теорему о нечетности ^[26], которая гласит, что «почти все» конечные игры имеют конечное и нечетное число равновесий Нэша. В 1993 году Харсани опубликовал альтернативное доказательство результата. ^[27] «Почти все» здесь означает, что любая игра с бесконечным или четным числом равновесий является очень особенной в том смысле, что если бы ее выигрыши были хотя бы немного случайным образом возмущены, с вероятностью единица она имела бы нечетное число равновесий.

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

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

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

Примечания

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

Ссылки

1. Осборн, Мартин Дж.; Рубинштейн, Ариэль (12 июля 1994 г.). Курс теории игр . Кембридж, Массачусетс: MIT. стр. 14. ISBN 9780262150415.
2. Крепс Д.М. (1987) «Равновесие Нэша». В: Palgrave Macmillan (ред.) Новый экономический словарь Palgrave . Palgrave Macmillan, Лондон.
3. Нэш, Джон Ф. (1950). «Точки равновесия в играх n лиц». PNAS . 36 (1): 48–49. Bibcode : 1950PNAS...36...48N. doi : 10.1073/pnas.36.1.48 . PMC 1063129. PMID  16588946 . 
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. "Уроки маркетинга от доктора Нэша - Эндрю Фрэнка". 2015-05-25 . Получено 2015-08-30 .
9. Chiappori, P. -A.; Levitt, S.; Groseclose, T. (2002). «Тестирование равновесий смешанных стратегий, когда игроки неоднородны: случай пенальти в футболе» (PDF) . American Economic Review . 92 (4): 1138. CiteSeerX 10.1.1.178.1646 . doi :10.1257/00028280260344678. 
10. Muchen Sun; Франческа Балдини; Кэти Хьюз; Питер Траутман; Тодд Мерфи (2024). «Смешанная стратегия равновесия Нэша для навигации толпы». arXiv : 2403.01537 [cs.RO].
11. Djehiche, B.; Tcheukam, A.; Tembine, H. (2017). «Игра среднего поля эвакуации в многоуровневом здании». IEEE Transactions on Automatic Control . 62 (10): 5154–5169. doi :10.1109/TAC.2017.2679487. ISSN  0018-9286. S2CID  21850096.
12. Djehiche, Boualem; Tcheukam, Alain; Tembine, Hamidou (2017-09-27). «Игры типа среднего поля в инженерии». AIMS Electronics and Electrical Engineering . 1 : 18–73. arXiv : 1605.03281 . doi :10.3934/ElectrEng.2017.1.18. S2CID  16055840.
13. Курно А. (1838) Исследования математических принципов теории богатства
14. Дж. фон Нейман, О. Моргенштерн, Теория игр и экономическое поведение , авторское право 1944, 1953, Princeton University Press
15. Кармона, Гильерме; Подчек, Конрад (2009). «О существовании равновесий Нэша в чистой стратегии в больших играх» (PDF) . Журнал экономической теории . 144 (3): 1300–1319. doi :10.1016/j.jet.2008.11.009. hdl : 10362/11577 . SSRN  882466.^{[ постоянная мертвая ссылка ]}
16. von Ahn, Luis. "Preliminaries of Game Theory" (PDF) . Science of the Web . Архивировано из оригинала (PDF) 2011-10-18 . Получено 2008-11-07 .
17. "Nash Equilibria". hoylab.cornell.edu . Архивировано из оригинала 16 июня 2019 г. Получено 08.12.2019 .
18. BD Bernheim; B. Peleg; MD Whinston (1987), «Coalition-Proof Equilibria I. Concepts», Journal of Economic Theory , 42 (1): 1–12, doi :10.1016/0022-0531(87)90099-8.
19. Ауманн, Р. (1959). «Приемлемые точки в общих кооперативных играх n-человек». Вклад в теорию игр . Том IV. Принстон, Нью-Джерси: Princeton University Press. ISBN 978-1-4008-8216-8.
20. Д. Морено; Дж. Вудерс (1996), «Равновесие, устойчивое к коалициям» (PDF) , Игры и экономическое поведение , 17 (1): 80–112, doi :10.1006/game.1996.0095, hdl : 10016/4408 .
21. MIT OpenCourseWare. 6.254: Теория игр с инженерными приложениями, весна 2010 г. Лекция 6: Непрерывные и прерывные игры.
22. Розен, Дж. Б. (1965). «Существование и уникальность точек равновесия для вогнутых игр N лиц». Econometrica . 33 (3): 520–534. doi : 10.2307/1911749. hdl : 2060/19650010164 . ISSN  0012-9682. JSTOR  1911749.
23. TL Turocy, B. Von Stengel, Game Theory , авторское право 2001, Texas A&M University, London School of Economics, страницы 141-144. Нэш доказал, что для этого типа игры с конечной экстенсивной формой существует идеальное NE ^{[ требуется ссылка ]} — его можно представить как стратегию, соответствующую его исходным условиям для игры с NE. Такие игры могут не иметь уникального NE, но по крайней мере одна из многих равновесных стратегий будет сыграна гипотетическими игроками, имеющими идеальное знание всех 10 ¹⁵⁰ деревьев игры ^{[ требуется ссылка ]} .
24. JC Cox, M. Walker, Learning to Play Cournot Duoploy Strategies Архивировано 11 декабря 2013 г. в Wayback Machine , авторское право 1997 г., Техасский университет A&M, Университет Аризоны, страницы 141–144
25. Фуденбург, Дрю; Тироль, Жан (1991). Теория игр . МТИ Пресс. ISBN 978-0-262-06141-4.
26. Уилсон, Роберт (1 июля 1971 г.). «Вычисление равновесий в играх N лиц». Журнал SIAM по прикладной математике . 21 (1): 80–87. doi :10.1137/0121011. ISSN  0036-1399.
27. Harsanyi, JC (1973-12-01). «Нечетность числа точек равновесия: новое доказательство». International Journal of Game Theory . 2 (1): 235–250. doi :10.1007/BF01737572. ISSN  1432-1270. S2CID  122603890.

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

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

• Бинмор, Кен (2007), Игра по-настоящему: Текст по теории игр , Oxford University Press , ISBN 978-0195300574.
• Диксит, Авинаш, Сьюзан Скит и Дэвид Рейли. Стратегические игры . WW Norton & Company. (Третье издание в 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 участниками» Труды Национальной академии наук 36(1):48-49.
• Нэш, Джон (1951) «Некооперативные игры» Анналы математики 54(2):286-295.

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

• Мельманн, А. (2000) Игра началась! Теория игр в мифах и парадоксах , Американское математическое общество .
• Назар, Сильвия (1998), «Игры разума» , издательство Simon & Schuster .
• Авиад Рубинштейн: «Трудность аппроксимации между 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