Равновесия Нэша вообще неисчислимы. Равновесие по Нэшу - это набор стратегий, где, учитывая стратегии противников, каждый игрок получает в течение максимально возможного ожидаемого вознаграждения. Нахождение-Наш равновесия, учитывая и игра, это -полное.
Строго следуя определениям, похоже, нет особых оснований полагать, что стратегии данного Равновесие по Нэшу близко к стратегиям любого равновесия по Нэшу. Тем не менее, мы часто видим в литературе небрежно используемую фразу типа «приблизительно вычислить равновесие Нэша», когда это означает сказать «вычислить приближенное равновесие Нэша».
Итак, мне интересно, когда второе подразумевает первое; то есть для каких игр мы можем ожидать- равновесия Нэша будут "близки" к равновесиям Нэша?
Более формально, предположим, у меня есть игра на игроки и последовательность профилей стратегии ,
каждый это Равновесие по Нэшу и последовательность сходится к нулю.
Мои вопросы:
Когда (при каких условиях / предположениях) все стратегии сходятся? То есть для каждого игрока, обязательно сходится.
При каких дополнительных условиях предел этой последовательности фактически является равновесием по Нэшу в игре? (Мне кажется, что никаких дополнительных предположений не требуется; т. Е. Если все стратегии сходятся, предел должен быть NE.)
Когда работает алгоритм для вычислений - равновесия Нэша обязательно подразумевают алгоритм приближенных вычислений стратегий равновесия Нэша? Достаточно ли вышеуказанных условий?
Огромное спасибо!
Редактировать 2014-03-19
После прочтения ссылки в ответе Рахула, кажется более разумным думать с точки зрения расстояния между распределениями, а не сходящиеся последовательности. Поэтому я постараюсь перефразировать вопросы, а также изложить некоторые недавние мысли.
(Ну, это слишком зависит от алгоритма, чтобы действительно иметь ответ. Без ограничений на алгоритм, вы можете иметь два различных равновесия Нэша и затем, когда вы подключаете все меньше и меньше в алгоритм, расстояние между последовательными выходами может все еще быть большим, потому что выходы колеблются между равновесиями.)
предполагать это профиль стратегии, то есть распределение продукта по стратегиям игроков. Для каких игр можно сказать, что является -Наше равновесие подразумевает для некоторого равновесия по Нэшу , где как ? (Обратите внимание, что обратное имеет место, если выплаты ограничены )
Это на самом деле сложно, потому что в настройке сложности, которую мы называем «игрой», мы на самом деле являемся последовательностью игр, параметризованных , количеством чистых стратегий («действий»). Так что как , и относительные показатели имеют значение. Вот простой контрпример, чтобы показать ответ не «все игры». Предположим, мы исправили последовательность убывания . Затем для каждого игру для двух игроков по действиям, где, если игрок играет первое действие, он получает выигрыш независимо от того, что играет другой игрок; если игрок играет второе действие, он получает выплатунезависимо от того, что играет другой игрок; и если игрок выполняет какое-либо другое действие, он получает выплату независимо от того, что играет другой игрок.
Таким образом, каждая игра имеет -равновесие (оба играют второе действие), которое максимально далеко на расстоянии от своего единственного равновесия Нэша (оба играют первое действие).
Итак, два интересных подвопроса:
- Для фиксированной игры и фиксированного , будь то для «достаточно малого» вышеупомянутое условие выполнено (все -equilibria близки к равновесиям Нэша).
- Возможно, по сути тот же вопрос, но выполняется ли условие, если различия в выплатах ограничены константой от .
Тот же вопрос, что и (2), но относящийся к фактическим равновесиям, вычисляемым алгоритмами. Я предполагаю, что, вероятно, мы либо получим алгоритмические / конструктивные ответы, либо не получим вообще, так что различие не имеет большого значения.
Ответы:
Следующая статья по крайней мере формализует понятие приближенных равновесий, близких к точным равновесиям, и доказывает некоторые связанные структурные результаты.
Пранджал Авастхи, Мария-Флорина Балкан, Аврим Блум или Ор Шеффет и Сантош Вемпала (2010). О равновесиях по Нэшу приближенно-устойчивых игр. В материалах Третьей международной конференции по алгоритмической теории игр (SAGT'10), 78-89.
В частности, в статье приведен пример класса игр для вопроса 3.
источник