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

Было предложено разделить эту статью на статьи под названием « Равновесие по Нэшу» и « Доказательства существования равновесия по Нэшу» . ( Обсудить ) ( декабрь 2020 г. )

В теории игр , то равновесие Нэша , названный в честь математик Джон Форбс Нэш - младший , является наиболее распространенным способом для определения решения в виде не-кооперативной игры с участием двух или более игроков. В равновесии по Нэшу предполагается, что каждый игрок знает стратегии равновесия других игроков, и ни один игрок не получит ничего, изменяя только свою собственную стратегию. ^[1] Принцип равновесия по Нэшу восходит к временам Курно , который применил его к конкурирующим фирмам, выбирающим выпуск. ^[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]

История [ править ]

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

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

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

Определения [ править ]

Nash Equilibrium [ править ]

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

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

Формально, пусть будет набор всех возможных стратегий для игрока , где . Пусть будет профиль стратегии, набор, состоящий из одной стратегии для каждого игрока, где обозначает стратегии всех игроков, кроме . Пусть - выигрыш игрока i как функция стратегий. Профиль стратегии является равновесием по Нэшу, если ^[15]${\ displaystyle S_ {i}}$${\ displaystyle i}$${\ Displaystyle я = 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}}$

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

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

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

Строгое / Слабое равновесие [ править ]

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

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

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

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

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

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

Равновесия по Нэшу могут не существовать, если набор вариантов бесконечен и некомпактен. Примером является игра, в которой два игрока одновременно называют число, и игрок, назвавший большее число, выигрывает. Другой пример: каждый из двух игроков выбирает действительное число строго меньше 5, и побеждает тот, у кого наибольшее число; не существует наибольшего числа, строго меньшего, чем 5 (если бы это число могло равняться 5, в равновесии Нэша оба игрока выбрали бы 5 и сыграли вничью). Однако равновесие по Нэшу существует, если набор вариантов компактен , а выигрыш каждого игрока непрерывен в стратегиях всех игроков. ^[17]

Примеры [ править ]

Координационная игра [ править ]

Координации игра является классическим ( симметричным ) два игроком, две стратегии игры, с примером матрицей выигрышей , показанной справа. Таким образом, игроки должны координировать свои действия, принимая стратегию А, чтобы получить наибольшую выгоду; т.е. 4. Если оба игрока выбрали стратегию B, равновесие по Нэшу все равно сохраняется. Хотя каждому игроку присуждается выигрыш меньше оптимального, ни у одного из игроков нет стимула менять стратегию из-за уменьшения немедленного выигрыша (с 2 до 1).

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

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

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

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

Сетевой трафик [ править ]

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

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

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

Соревновательная игра [ править ]

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

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

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

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

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

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

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

Возникновение [ править ]

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

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

Если условия не выполняются [ править ]

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

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

Где выполняются условия [ править ]

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

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

Эта идея была формализована Aumann, R. и A. Brandenburger, 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.

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

NE и ненадежные угрозы [ править ]

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

На изображении справа показана простая последовательная игра, которая иллюстрирует проблему несовершенных равновесий Нэша в подиграх. В этой игре игрок выбирает влево (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})}$

Следовательно, существует фиксированная точка и равновесие по Нэшу. ^[23]${\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 и 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. Это создает систему уравнений, из которых могут быть выведены вероятности выбора каждой стратегии. ^[14]

Примеры [ править ]

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

E [выигрыш за игру A H] = (−1) q + (+1) (1− q ) = 1−2 q

E [выигрыш за игру A T] = (+1) q + (−1) (1− q ) = 2 q −1

E [выигрыш за игру A H] = E [выигрыш за игру A за T] ⇒ 1-2 q = 2 q −1 ⇒ q = 1/2

E [выигрыш для B, играющего H] = (+1) p + (−1) (1− p ) = 2 p −1

E [выигрыш за игру B T] = (−1) p + (+1) (1− p ) = 1−2 p

E [выигрыш для B, играющего H] = E [выигрыш для B, играющего T] ⇒ 2 p −1 = 1−2 p ⇒ p = 1/2

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

Странность точек равновесия [ править ]

В 1971 году Роберт Уилсон предложил теорему о нечетности ^[24] , согласно которой почти все конечные игры имеют конечное число нечетных решений. В 1993 году Харшаньи также опубликовал статью, подтверждающую теорему. ^[25] Например, дилемма заключенного (1), битва полов (3) и охота на оленей (3). Все эти игры имеют нечетное количество равновесий по Нэшу.

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

См. Также [ править ]

Примечания [ править ]

Ссылки [ править ]

Учебники по теории игр [ править ]

Оригинальные статьи Нэша [ править ]

Другие ссылки [ править ]

Внешние ссылки [ править ]

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