Когда делать

9

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

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

Итак, мне интересно, когда второе подразумевает первое; то есть для каких игр мы можем ожидатьϵ- равновесия Нэша будут "близки" к равновесиям Нэша?


Более формально, предположим, у меня есть игра на n игроки и последовательность профилей стратегии (s1(1),,sn(1)),(s1(2),,sn(2)),(s1(3),,sn(3)),,

каждый (s1(i),,sn(i)) это ϵiРавновесие по Нэшу и последовательность ϵ1,ϵ2,ϵ3, сходится к нулю.

Мои вопросы:

  1. Когда (при каких условиях / предположениях) все стратегии сходятся? То есть для каждого игрокаj, sj(1),sj(2),sj(3), обязательно сходится.

  2. При каких дополнительных условиях предел этой последовательности фактически является равновесием по Нэшу в игре? (Мне кажется, что никаких дополнительных предположений не требуется; т. Е. Если все стратегии сходятся, предел должен быть NE.)

  3. Когда работает алгоритм для вычислений ϵ- равновесия Нэша обязательно подразумевают алгоритм приближенных вычислений стратегий равновесия Нэша? Достаточно ли вышеуказанных условий?

Огромное спасибо!


Редактировать 2014-03-19

После прочтения ссылки в ответе Рахула, кажется более разумным думать с точки зрения 1расстояния между распределениями, а не сходящиеся последовательности. Поэтому я постараюсь перефразировать вопросы, а также изложить некоторые недавние мысли.

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

  2. предполагать pэто профиль стратегии, то есть распределение продукта по стратегиям игроков. Для каких игр можно сказать, чтоp является ϵ-Наше равновесие подразумевает pq1δдля некоторого равновесия по Нэшу , где как ? (Обратите внимание, что обратное имеет место, если выплаты ограничены )qδ0ϵ01

    Это на самом деле сложно, потому что в настройке сложности, которую мы называем «игрой», мы на самом деле являемся последовательностью игр, параметризованных , количеством чистых стратегий («действий»). Так что как , и относительные показатели имеют значение. Вот простой контрпример, чтобы показать ответ не «все игры». Предположим, мы исправили последовательность убывания . Затем для каждого игру для двух игроков по действиям, где, если игрок играет первое действие, он получает выигрыш независимо от того, что играет другой игрок; если игрок играет второе действие, он получает выплатуnnϵ0ϵ1,ϵ2,ϵnn11ϵnнезависимо от того, что играет другой игрок; и если игрок выполняет какое-либо другое действие, он получает выплату независимо от того, что играет другой игрок.0

    Таким образом, каждая игра имеет -равновесие (оба играют второе действие), которое максимально далеко на расстоянии от своего единственного равновесия Нэша (оба играют первое действие).nϵn1

    Итак, два интересных подвопроса:

    1. Для фиксированной игры и фиксированного , будь то для «достаточно малого» вышеупомянутое условие выполнено (все -equilibria близки к равновесиям Нэша).nϵϵ
    2. Возможно, по сути тот же вопрос, но выполняется ли условие, если различия в выплатах ограничены константой от .n
  3. Тот же вопрос, что и (2), но относящийся к фактическим равновесиям, вычисляемым алгоритмами. Я предполагаю, что, вероятно, мы либо получим алгоритмические / конструктивные ответы, либо не получим вообще, так что различие не имеет большого значения.

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

Ответы:

5

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

Пранджал Авастхи, Мария-Флорина Балкан, Аврим Блум или Ор Шеффет и Сантош Вемпала (2010). О равновесиях по Нэшу приближенно-устойчивых игр. В материалах Третьей международной конференции по алгоритмической теории игр (SAGT'10), 78-89.

В частности, в статье приведен пример класса игр для вопроса 3.

Рахул Савани
источник
Спасибо! Я думаю, что это состояние искусства. Я также добавлю некоторые мысли в мой вопрос.
Усул