Равновесие Нэша в теории игр: концепция решения некооперативных игр.

Введение

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

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

Приложения

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

История

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

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

Профиль стратегии – это набор стратегий, по одной для каждого игрока. Неформально, профиль стратегии является равновесием Нэша, если ни один игрок не может улучшить свой результат, односторонне изменив свою стратегию. Чтобы понять, что это значит, представьте, что каждому игроку сообщают о стратегиях других игроков. Предположим, что каждый игрок задает себе вопрос: "Зная стратегии других игроков и считая их фиксированными, могу ли я получить выгоду, изменив свою стратегию?" Например, если игрок отвечает "Да", то этот набор стратегий не является равновесием Нэша. Но если каждый игрок предпочитает не менять свою стратегию (или безразличен между изменением и неизменением), то профиль стратегии является равновесием Нэша. Таким образом, каждая стратегия в равновесии Нэша является оптимальным ответом на стратегии других игроков в этом равновесии. Формально, пусть – множество всех возможных стратегий для игрока , где – множество стратегий всех игроков, кроме игрока i. Пусть – профиль стратегии, набор, состоящий из одной стратегии для каждого игрока. Пусть – выигрыш игрока i как функция от стратегий. Профиль стратегии является равновесием Нэша, если

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

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

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

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

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

Равновесие Нэша определяет стабильность только с точки зрения индивидуальных отклонений игроков. В кооперативных играх такая концепция представляется недостаточно убедительной. Сильное равновесие Нэша допускает отклонения любых мыслимых коалиций. Формально, сильное равновесие Нэша – это равновесие Нэша, в котором ни одна коалиция, учитывая действия игроков, не входящих в неё, не может совместно отклониться таким образом, чтобы все её участники выиграли. Однако, концепция сильного равновесия Нэша иногда кажется излишне "строгой", поскольку допускается неограниченное частное общение между игроками. Фактически, сильное равновесие Нэша должно быть парето-оптимальным. В силу этих требований, сильное равновесие Нэша встречается редко и поэтому малоприменимо во многих областях теории игр. Тем не менее, в играх, таких как выборы с числом игроков, значительно превышающим число возможных исходов, оно может быть более распространенным, чем стабильное равновесие. Существует уточнённое равновесие Нэша, известное как коалиционно устойчивое равновесие Нэша (CPNE). Кроме того, игра может иметь равновесие Нэша, устойчивое к коалициям размером меньше заданного значения k. CPNE связано с теорией ядра.

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

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

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

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

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

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

Применение равновесия Нэша заключается в определении ожидаемого потока трафика в сети. Рассмотрим граф справа. Если предположить, что есть "автомобили", движущиеся из А в D, каково ожидаемое распределение трафика в сети? Эту ситуацию можно смоделировать как "игру", где каждый путешественник имеет выбор из 3 стратегий, и каждая стратегия представляет собой маршрут из А в D (один из ABD, ABCD или ACD). "Выигрыш" каждой стратегии – это время в пути по каждому маршруту. На графе справа автомобиль, движущийся по маршруту ABD, испытывает время в пути , где – количество автомобилей, движущихся по ребру AB. Таким образом, выигрыш от любой стратегии зависит от выбора других игроков, как это обычно бывает. Однако в данном случае целью является минимизация времени в пути, а не его максимизация. Равновесие наступит, когда время на всех путях будет одинаковым. Когда это происходит, ни у одного водителя нет стимула менять маршрут, поскольку это может только увеличить время его поездки. Для графа справа, если, например, 100 автомобилей едут из А в D, то равновесие наступит, когда 25 водителей поедут по ABD, 50 – по ABCD и 25 – по ACD. Теперь у каждого водителя общее время в пути составляет 3,75 (это можно увидеть, поскольку в общей сложности 75 автомобилей проезжают по ребру AB, и аналогично, 75 автомобилей проезжают по ребру CD). Обратите внимание, что это распределение не является социально оптимальным. Если бы 100 автомобилей договорились, что 50 поедут по ABD, а остальные 50 – по ACD, то время в пути для каждого автомобиля составило бы всего 3,5, что меньше, чем 3,75. Это также равновесие Нэша, если удалить путь между B и C, что означает, что добавление еще одного возможного маршрута может снизить эффективность системы, явление, известное как парадокс Бресса.

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

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

Невероятные и неправдоподобные угрозы

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

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

Если у игрока А есть доминирующая стратегия, то существует равновесие Нэша, в котором игрок А играет эту стратегию. В случае двух игроков А и В существует равновесие Нэша, в котором игрок А играет, а игрок В – лучший ответ на эту стратегию. Если стратегия является строго доминирующей, игрок А играет её во всех равновесиях Нэша. Если и у игрока А, и у игрока В есть строго доминирующие стратегии, существует единственное равновесие Нэша, в котором каждый играет свою строго доминирующую стратегию. В играх со смешанными стратегиями равновесия Нэша вероятность выбора игроком любой конкретной (то есть чистой) стратегии можно вычислить, присвоив каждой стратегии переменную, представляющую фиксированную вероятность выбора этой стратегии. Чтобы игрок был готов к рандомизации, его ожидаемый выигрыш для каждой (чистой) стратегии должен быть одинаковым. Кроме того, сумма вероятностей для каждой стратегии конкретного игрока должна равняться 1. Это создает систему уравнений, из которой можно вывести вероятности выбора каждой стратегии. Утверждается, что "почти все" конечные игры имеют конечное и нечетное число равновесий Нэша. В 1993 году Харсаньи опубликовал альтернативное доказательство этого утверждения. "Почти все" здесь означает, что любая игра с бесконечным или четным числом равновесий является очень специфичной в том смысле, что если бы её выигрыши были даже незначительно случайным образом изменены, то с вероятностью один у неё было бы нечетное число равновесий. Например, дилемма заключенного имеет одно равновесие, а игра "битва полов" – три: два чистых и одно смешанное, и это остаётся верным даже при небольших изменениях выигрышей. Игра "бесплатные деньги" является примером "специальной" игры с четным числом равновесий. В ней два игрока должны проголосовать "за", а не "против", чтобы получить награду, при этом голосование происходит одновременно. Существует два равновесия Нэша в чистых стратегиях: ("за", "за") и ("против", "против"), и нет равновесий в смешанных стратегиях, поскольку стратегия "за" слабо доминирует над стратегией "против". Стратегия "за" не хуже стратегии "против" независимо от действий другого игрока, но если есть хоть малейший шанс, что другой игрок выберет "за", то "за" – лучший ответ. Однако при небольшом случайном изменении выигрышей вероятность того, что любые два выигрыша останутся равными (будь то 0 или какое-либо другое число), стремится к нулю, и в игре будет либо одно, либо три равновесия.

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

Диксит, Авинаш, Сьюзан Скит и Дэвид Райли. Стратегические игры. W. W. Norton & Company. (Третье издание в 2009 году). Учебник для студентов бакалавриата. Подходит для студентов и студентов бизнес-направлений. Фуденберг, Дрю и Жан Тироль (1991) Теория игр. MIT Press. Ясное и подробное введение в теорию игр, представленное в экономическом контексте. Моргенштерн, Оскар и Джон фон Нейман (1947) Теория игр и экономическое поведение. Princeton University Press. Современное введение на уровне магистратуры. Всеобъемлющий справочник с вычислительной точки зрения; см. главу 3. Доступно для бесплатного скачивания онлайн.

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

Нэш, Джон (1950) "Точки равновесия в играх с n игроками" ПроCEEDINGS Национальной академии наук 36(1):48–49. Нэш, Джон (1951) "Некооперативные игры" Анналы математики 54(2):286–295.

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

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