Algoritmos para el cálculo del equilibrio de Nash.

10

Busqué en el foro para ver si esto se ha preguntado antes, y aunque se discute la teoría algorítmica de juegos, no pude encontrar este problema en particular. Estoy tratando de descubrir cuál es el algoritmo más conocido para calcular equilibrios de Nash aproximados (de estrategia mixta) en un juego finito de n personas. Por supuesto, este algoritmo sería PPAD. Estoy más interesado en la velocidad / eficiencia que en la precisión perfecta del algoritmo.

Gracias Philip

ds.algorithms gt.game-theory Philip White
fuente
Podemos ayudarlo mejor si brinda más detalles. Por ejemplo, ¿qué valor de tienes en mente? ¿Tiene alguna estructura especial de la función de pago en mente? ¿Realmente necesita un equilibrio de Nash o sería suficiente un equilibrio correlacionado? ¿Está buscando algo con buenos límites demostrables o algo con buen rendimiento práctico? n
Warren Schudy

Respuestas:

7

La respuesta corta es que, aunque existen algunos algoritmos de tiempo polinomiales para encontrar de forma demostrable equilibrios de Nash aproximados, todos ellos encuentran aproximaciones relativamente pobres, probablemente no lo suficientemente buenas si realmente está tratando de encontrar un algoritmo para jugar un juego. Se sabe más para juegos de 2 jugadores que para juegos de n jugadores.

Si lo que intenta hacer es encontrar un equilibrio de Nash (aproximado), una cosa fácil de codificar que podría intentar es simular el juego, con cada jugador usando el algoritmo de mayoría ponderada aleatoria (http://en.wikipedia.org/ wiki / Randomized_weighted_majority_algorithm). No se garantiza que esto funcione, pero en muchos casos lo hará (y se garantiza en ciertas clases de juegos, como los juegos de suma cero). En particular, si este proceso converge, se garantiza que converja a un equilibrio de Nash. El peligro es que no convergerá y circulará para siempre, pero incluso en este caso, la historia empírica del juego convergerá en el conjunto de equilibrios groseros correlacionados.

Aaron Roth
fuente
Comencé a echar un vistazo al documento mencionado en la respuesta anterior. No entendí todo (o gran parte a primera vista) ... ¿puede explicar por qué la aproximación es "relativamente pobre"? Además, ¿podría explicar brevemente qué es un "equilibrio correlacionado grueso"? Sé lo que es un equilibrio correlacionado, pero lo que significa para tal ecuación. ser grosero Finalmente, ¿qué quiere decir con "la historia empírica del juego convergerá ... [etc.]"? ¿Cómo puede algo que nunca converge converger a un conjunto de CCE? Gracias por su respuesta, estoy buscando el artículo de Wikipedia ahora.
Philip White
Para algunos antecedentes sobre algoritmos que producen distribuciones que convergen en equilibrios correlacionados gruesos o equilibrados correlacionados, comenzaría aquí: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
Aaron Roth
Si desea un equilibrio correlacionado en lugar de un equilibrio correlacionado grueso, puede usar un alumno sin arrepentimiento interno. Por ejemplo (enchufe descarado) cs.brown.edu/~ws/papers/regret.pdf . También hay algoritmos para calcular equilibrios correlacionados directamente en el tiempo polinómico.
Warren Schudy
10

n

Joseph O'Rourke
fuente
4

Si está interesado en algoritmos que realmente se implementan en el software, hay varios que conozco:

  1. el paquete GAMBIT (http://www.gambit-project.org/doc/index.html) implementa varios algoritmos de equilibrio de Nash para la forma normal de 2 jugadores y n jugadores, y en algunos casos juegos de forma extensa.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) implementa los algoritmos GNM e IPA de Govindan & Wilson para juegos de forma normal para n jugadores.

  3. Para juegos grandes, la representación de forma normal es problemática ya que el tamaño crece exponencialmente en el número de jugadores. En cambio, si la función de utilidad de su juego tiene ciertos tipos de estructura, puede usar una "representación concisa" (por ejemplo, juegos gráficos, juegos simétricos, juegos de gráficos de acción) para expresarla usando mucho menos espacio; Además, la estructura a menudo se puede explotar para acelerar la computación. En términos de software, AGG Solver (http://agg.cs.ubc.ca) adapta el algoritmo GNM de GameTracer y el algoritmo simpdiv de GAMBIT a la representación del juego de gráficos de acción (AGG). (Descargo de responsabilidad: estoy involucrado en el desarrollo de este paquete de software).

Albert
fuente