Алгоритмы вычисления равновесия по Нэшу.

10

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

Спасибо Филип

ds.algorithms gt.game-theory Филип Уайт
источник
Мы можем помочь вам лучше, если вы дадите больше деталей. Например, какое значение вы имеете в виду? У вас есть какая-то особая структура функции выплаты? Вы действительно нуждаетесь в равновесии Нэша или достаточно коррелированного равновесия? Вы ищете что-то с хорошими доказуемыми границами или что-то с хорошим практическим исполнением? N
Уоррен Шуди

Ответы:

7

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

Если то, что вы пытаетесь сделать, - это найти (приблизительное) равновесие Нэша, то одна из простых вещей, которую вы можете попробовать кодировать, - это симуляция игры, при которой каждый игрок использует алгоритм рандомизированного взвешенного большинства (http://en.wikipedia.org/ вики / Randomized_weighted_majority_algorithm). Это не гарантированно сработает, но во многих случаях сработает (и гарантируется в определенных классах игр, таких как игры с нулевой суммой). В частности, если этот процесс сходится вообще, он гарантированно сходится к равновесию по Нэшу. Опасность заключается в том, что он не будет сходиться, а вращаться вечно - но даже в этом случае эмпирическая история игрового процесса будет сходиться к набору грубых коррелированных равновесий.

Аарон Рот
источник
Я начал смотреть на бумагу, упомянутую в ответе выше. Я не все понял (или многое на первый взгляд) ... вы можете объяснить, почему приближение "относительно плохое"? Кроме того, не могли бы вы вкратце объяснить, что такое «грубое коррелированное равновесие»? Я знаю, что такое коррелированное равновесие, но что это значит для такого уравнения. быть грубым. Наконец, что вы подразумеваете под «эмпирической историей игрового процесса будет сходиться ... [и т. Д.]»? Как что-то, что никогда не сходится, сходится к набору CCE? Спасибо за ваш ответ, сейчас я смотрю статью в Википедии.
Филипп Уайт
Для некоторой предыстории об алгоритмах, которые производят распределения, которые сходятся к грубым коррелированным равновесиям или коррелированным равновесиям, я бы начал здесь: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
Аарон Рот
Если вы хотите коррелированные равновесия, а не грубые коррелированные равновесия, вы можете использовать ученика без внутреннего сожаления. Например (бесстыдный плагин) cs.brown.edu/~ws/papers/regret.pdf . Существуют также алгоритмы для вычисления коррелированных равновесий непосредственно за полиномиальное время.
Уоррен Шуди
4

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

  1. Пакет GAMBIT (http://www.gambit-project.org/doc/index.html) реализует несколько алгоритмов равновесия по Нэшу для нормальных форм для 2 игроков и для n игроков, а в некоторых случаях - для игр с расширенной формой.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) реализует алгоритмы Govindan & Wilson GNM и IPA для игр в нормальной форме для n-игроков.

  3. В больших играх нормальное представление формы проблематично, так как размер растет в геометрической прогрессии по количеству игроков. Вместо этого, если функция полезности вашей игры имеет определенную структуру, вы можете использовать «краткое представление» (например, графические игры, симметричные игры, игры с графами действий), чтобы выразить ее, используя гораздо меньше места; и, кроме того, структура часто может использоваться для ускорения вычислений. С точки зрения программного обеспечения, AGG Solver (http://agg.cs.ubc.ca) адаптирует алгоритм GameTracer GNM и алгоритм GAMBIT simpdiv к представлению игры-графика действий (AGG). (Отказ от ответственности: я участвую в разработке этого программного пакета.)

альберт
источник