¿Conjeturas sobresalientes y problemas abiertos en la teoría de juegos (algorítmica)?

14

¿Qué tipo de conjeturas y principales problemas abiertos son los más importantes en la teoría algorítmica de juegos (o la teoría de juegos en general en lo que se refiere a CS)? Por ejemplo, la resolución de NASH como PPAD completo, creo, habría sido la más grande hasta que se resolvió.

(Agregado: resolver la relación de PPAD con P y NP es un buen problema abierto, pero otros que no estén tan arraigados en la complejidad computacional también serían buenos).

big-list gt.game-theory daveagp
fuente
3
Esta pregunta funcionaría mejor si la marcaras como CW (Community Wiki). Ver aquí: meta.cstheory.stackexchange.com/questions/225/…
Daniel Apon
2
Estoy de acuerdo. por favor márquelo CW.
Suresh Venkat

Respuestas:

5

Aquí hay varios problemas abiertos:

1-El principal problema abierto es el problema de calcular los equilibrios aproximados de Nash.

2- ¿Existe un algoritmo eficiente para calcular equilibrios puros de Nash en juegos de congestión?

¿3 equilibrios de búsqueda con mínima ineficiencia?

4-Tim Roughgarden, en Comunicaciones de la ACM, planteó el siguiente problema abierto:

¿en qué medida la computación eficiente "compatible con incentivos" es fundamentalmente menos poderosa que la computación eficiente "clásica"?

Teoría de juego algorítmico, Comunicaciones de la ACM, Volumen 53, Número 7, (julio de 2010)

Además, estas referencias contienen algunos problemas abiertos: Nisan, Roughgarden, Tardos y Vazirani, editores. Teoría de juego algorítmico. Cambridge University Press, 2007.

T. Roughgarden. Teoría de juego algorítmico: algunos grandes éxitos y direcciones futuras. En TCS '08, p. 21-42.

Mohammad Al-Turkistany
fuente
La encuesta reciente es muy útil. En realidad había mirado el libro de Nisan +++ --- ¡una búsqueda de texto para "conjetura" da solo un par de resultados! --- pero de hecho hay muchos problemas abiertos. Cualquier conjetura específica, o problemas abiertos menos técnicos específicos, aún serían bienvenidos en mi búsqueda.
daveagp
Calcular un equilibrio puro de Nash de un juego de congestión general es PLS completo, por lo que es poco probable que exista un algoritmo eficiente.
Rahul Savani
1

En esta referencia, Papadimitriou y Roughgarden plantean 6 problemas abiertos relacionados con el cálculo de equilibrios correlacionados:

Papadimitriou y Tim Roughgarden, calculando equilibrios correlacionados en juegos multijugador

Además, en este artículo, Papadimitriou plantea varios problemas abiertos relacionados con la teoría de juegos e Internet:

Papadimitriou, Algoritmos, Juegos e Internet, Proc. STOC 2001

Mohammad Al-Turkistany
fuente
2
La encuesta de Papadimitriou está un poco desactualizada, ya que se han logrado avances significativos en la mayoría de los problemas abiertos desde 2001.
Ryan Williams