Juego sucinto

Ver también: Teoría de juegos § Representaciones de juegos alternativas

Considere un juego de tres jugadores, I, II y III, enfrentando, respectivamente, las estrategias {T, B}, {L, R} y {l, r}. Sin más restricciones, se requerirían 3 * 2 3 = 24 valores de utilidad para describir tal juego.
	L , l	L , r	R , l	R , r
T	4 , 6 , 2	5 , 5 , 5	8 , 1 , 7	1 , 4 , 9
B	8 , 6 , 6	7 , 4 , 7	9 , 6 , 5	0 , 3 , 0
Para cada perfil de estrategia, la utilidad del primer jugador aparece en primer lugar ( rojo ), y le siguen las utilidades del segundo jugador ( verde ) y del tercer jugador ( azul ).

En la teoría algorítmica de juegos , un juego sucinto o un juego sucintamente representable es un juego que puede representarse en un tamaño mucho más pequeño que su representación de forma normal . Sin imponer restricciones a las utilidades de los jugadores, describir un juego de jugadores, cada uno enfrentando estrategias , requiere enumerar los valores de las utilidades. Incluso los algoritmos triviales son capaces de encontrar un equilibrio de Nash en un polinomio de tiempo en la longitud de una entrada tan grande. Un juego sucinto es de tipo polinomial si en un juego representado por una cadena de longitud n${\displaystyle n}$${\displaystyle s}$ ${\displaystyle ns^{n}}$el número de jugadores, así como el número de estrategias de cada jugador, está delimitado por un polinomio en n ^[1] ( Papadimitriou y Roughgarden 2008 ^[2] dan una definición formal que describe los juegos sucintos como un problema computacional ) .

Tipos de juegos sucintos

Juegos graficos

Digamos que la utilidad de cada jugador depende solo de su propia acción y la acción de otro jugador; por ejemplo, I depende de II, II de III y III de I. Representar un juego de este tipo requeriría solo tres tablas de utilidad 2x2, que contengan en total solo 12 valores de utilidad. L R T 9 8 B 3 4 l r L 6 8 R 1 3 T B l 4 4 r 5 7

Los juegos gráficos son juegos en los que las utilidades de cada jugador dependen de las acciones de muy pocos jugadores. Si es el mayor número de jugadores por cuyas acciones se ve afectado un solo jugador (es decir, es el grado de la gráfica del juego), el número de valores de utilidad necesarios para describir el juego es , que, para un pequeño, es una mejora considerable. .${\displaystyle d}$${\displaystyle ns^{d+1}}$${\displaystyle d}$

Se ha demostrado que cualquier juego de forma normal se puede reducir a un juego gráfico con todos los grados delimitados por tres y con dos estrategias para cada jugador. ^[3] A diferencia de los juegos de forma normal, el problema de encontrar un equilibrio de Nash puro en juegos gráficos (si existe) es NP-completo . ^[4] El problema de encontrar un equilibrio de Nash (posiblemente mixto) en un juego gráfico es PPAD -completo. ^[5] Encontrar un equilibrio correlacionado de un juego gráfico se puede hacer en tiempo polinomial, y para una gráfica con un ancho de árbol acotado , esto también es cierto para encontrar un equilibrio correlacionado óptimo . ^[2]

Juegos dispersos

Cuando la mayoría de las utilidades son 0, como se muestra a continuación, es fácil obtener una representación sucinta.
	L , l	L , r	R , l	R , r
T	0 , 0 , 0	2 , 0 , 1	0 , 0 , 0	0 , 7 , 0
B	0 , 0 , 0	0 , 0 , 0	2 , 0 , 3	0 , 0 , 0

Los juegos dispersos son aquellos en los que la mayoría de las utilidades son cero. Los juegos gráficos pueden verse como un caso especial de juegos dispersos.

Para un juego de dos jugadores, un juego disperso puede definirse como un juego en el que cada fila y columna de las dos matrices de pago (utilidad) tiene como máximo un número constante de entradas distintas de cero. Se ha demostrado que la búsqueda de un equilibrio de Nash en un juego tan escasa es PPAD-dura, y que no existe un completo esquema de aproximación de tiempo polinomial a menos PPAD está en P . ^[6]

Juegos simétricos

Supongamos que los tres jugadores son idénticos (los colorearemos todos de morado ) y se enfrentan al conjunto de estrategias {T, B}. Sea #TP y #BP el número de compañeros de un jugador que han elegido T y B, respectivamente. Describir este juego requiere solo 6 valores de utilidad. # TP = 2 # BP = 0 # TP = 1 # BP = 1 # TP = 0 # BP = 2 T 5 2 2 B 1 7 2

En los juegos simétricos, todos los jugadores son idénticos, por lo que al evaluar la utilidad de una combinación de estrategias, lo único que importa es cuántos de los jugadores juegan cada una de las estrategias. Por lo tanto, describir un juego de este tipo requiere dar solo valores de utilidad.${\displaystyle n}$${\displaystyle s}$${\displaystyle s{\tbinom {n+s-2}{s-1}}}$

En un juego simétrico con 2 estrategias, siempre existe un equilibrio de Nash puro, aunque puede que no exista un equilibrio de Nash puro simétrico . ^[7] El problema de encontrar un equilibrio de Nash puro en un juego simétrico (posiblemente con más de dos jugadores) con un número constante de acciones está en AC ⁰ ; sin embargo, cuando el número de acciones crece con el número de jugadores (incluso linealmente), el problema es NP-completo. ^[8] En cualquier juego simétrico existe un equilibrio simétrico . Dado un juego simétrico de n jugadores que enfrentan k estrategias, se puede encontrar un equilibrio simétrico en el tiempo polinómico si k = . ^[9]${\displaystyle O(\log n/\log \log n)}$Encontrar un equilibrio correlacionado en juegos simétricos se puede hacer en tiempo polinomial. ^[2]

Juegos anónimos

Si los jugadores fueran diferentes pero no distinguieran entre otros jugadores, necesitaríamos enumerar 18 valores de utilidad para representar el juego, una tabla como la que se da para los "juegos simétricos" para cada jugador. # TP = 2 # BP = 0 # TP = 1 # BP = 1 # TP = 0 # BP = 2 T 8 , 8 , 2 2 , 9 , 5 4 , 1 , 4 B 6 , 1 , 3 2 , 2 , 1 7 , 0 , 6

En los juegos anónimos , los jugadores tienen diferentes utilidades, pero no distinguen entre otros jugadores (por ejemplo, tener que elegir entre "ir al cine" e "ir al bar" sin preocuparse solo por la cantidad de gente que habrá en cada lugar, no por con quién se encontrarán allí). En un juego así, la utilidad de un jugador depende nuevamente de cuántos de sus compañeros elijan qué estrategia y la suya propia, por lo que se requieren valores de utilidad.${\displaystyle sn{\tbinom {n+s-2}{s-1}}}$

Si el número de acciones crece con el número de jugadores, encontrar un equilibrio de Nash puro en un juego anónimo es NP-difícil . ^[8] Se puede encontrar un equilibrio correlacionado óptimo de un juego anónimo en el tiempo polinomial. ^[2] Cuando el número de estrategias es 2, existe un PTAS conocido para encontrar un equilibrio de Nash ε-aproximado . ^[10]

Juegos de Polymatrix

Si el juego en cuestión fuera un juego de polímatrix, describirlo requeriría 24 valores de utilidad. Para simplificar, examinemos solo las utilidades del jugador I (necesitaríamos dos tablas más para cada uno de los otros jugadores). L R T 4 , 6 8 , 7 B 3 , 7 9 , 1 l r T 7 , 7 1 , 6 B 8 , 6 6 , 4 l r L 2 , 9 3 , 3 R 2 , 4 1 , 5 Si se eligiera el perfil de estrategia (B, R, l), la utilidad del jugador I sería 9 + 8 = 17, la utilidad del jugador II sería 1 + 2 = 3 y la utilidad del jugador III sería 6 + 4 = 10.

En un juego de Polymatrix (también conocido como un juego multimatrix ), hay una matriz de utilidad para cada par de jugadores (i, j) , que denota un componente del jugador de utilidad i de. La utilidad final del jugador i es la suma de todos esos componentes. El número de valores de utilidades necesarios para representar un juego de este tipo es .${\displaystyle O(n^{2}*s^{2})}$

Los juegos de Polymatrix siempre tienen al menos un equilibrio de Nash mixto. ^[11] El problema de encontrar un equilibrio de Nash en un juego polimatriz es PPAD-completo. ^[5] Además, el problema de encontrar un equilibrio de Nash aproximado constante en un juego de polimatriz también es PPAD-completo. ^[12] Encontrar un equilibrio correlacionado de un juego polimatriz se puede hacer en tiempo polinomial. ^[2] Tenga en cuenta que incluso si los juegos por parejas que se juegan entre jugadores tienen equilibrios de Nash puros, la interacción global no admite necesariamente un equilibrio de Nash puro (aunque debe existir un equilibrio de Nash mixto).

Los juegos competitivos de polimatriz con solo interacciones de suma cero entre jugadores son una generalización de los juegos de suma cero para dos jugadores . El teorema de Minimax, originalmente formulado para juegos de dos jugadores por von Neumann, se generaliza a juegos de polímatriz de suma cero. ^{[13] Al} igual que los juegos de suma cero de dos jugadores, los juegos de suma cero polimatriz tienen equilibrios de Nash mixtos que se pueden calcular en tiempo polinómico y esos equilibrios coinciden con equilibrios correlacionados . Pero algunas otras propiedades de los juegos de suma cero para dos jugadores no se generalizan. En particular, los jugadores no necesitan tener un valor único.del juego y las estrategias de equilibrio no son estrategias de máximo-mínimo en el sentido de que las ganancias de los jugadores en el peor de los casos no se maximizan cuando se usa una estrategia de equilibrio. Existe una biblioteca Python de código abierto ^[14] para simular juegos polimatrix competitivos.

Los juegos de Polymatrix que tienen juegos de coordinación en sus bordes son juegos potenciales ^[15] y pueden resolverse usando un método de función potencial.

Juegos de circuito

Comparemos ahora las diversas estrategias de los jugadores con los valores booleanos "0" y "1", y dejemos que X represente la elección del jugador I, Y la elección del jugador II y Z para la elección del jugador III. Asignemos a cada jugador un circuito: Jugador I: X ∧ (Y ∨ Z) Jugador II: X ⨁ Y ⨁ Z Jugador III: X ∨ Y Estos describen la tabla de utilidades a continuación.
	0 , 0	0 , 1	1 , 0	1 , 1
0	0 , 0 , 0	0 , 1 , 0	0 , 1 , 1	0 , 0 , 1
1	0 , 1 , 1	1 , 0 , 1	1 , 0 , 1	1 , 1 , 1

La forma más flexible de representar un juego sucinto es representar a cada jugador mediante una máquina de Turing delimitada por tiempo polinomial , que toma como entrada las acciones de todos los jugadores y genera la utilidad del jugador. Tal máquina de Turing es equivalente a un circuito booleano , y es esta representación, conocida como juegos de circuitos , la que consideraremos.

Calcular el valor de un juego de circuito de suma cero de 2 jugadores es un problema completo de EXP , ^[16] y se sabe que la aproximación del valor de dicho juego hasta un factor multiplicativo está en PSPACE . ^[17] Determinar si existe un equilibrio de Nash puro es un problema completo (consulte Jerarquía de polinomios ). ^[18]${\displaystyle \Sigma _{2}^{\rm {P}}}$

Otras representaciones

Existen muchos otros tipos de juegos sucintos (muchos tienen que ver con la asignación de recursos). Los ejemplos incluyen juegos de congestión , juegos de congestión de la red , juegos de programación , juegos de efectos locales , juegos de localización de servicios , juegos de acción y de gráficos , juegos hypergraphical y más.

Resumen de las complejidades de encontrar equilibrios

A continuación se muestra una tabla de algunos resultados de complejidad conocidos para encontrar ciertas clases de equilibrios en varias representaciones de juegos. "NE" significa "equilibrio de Nash" y "CE" para "equilibrio correlacionado". n es el número de jugadores y s es el número de estrategias que enfrenta cada jugador (asumimos que todos los jugadores enfrentan el mismo número de estrategias). En los juegos gráficos, d es el grado máximo de la gráfica del juego. Para obtener referencias, consulte el texto del artículo principal.

Representación	Tamaño ( O (...))	NE puro	NE mixto	CE	CE óptima
Juego en forma normal	${\displaystyle ns^{n}}$	NP-completo	PPAD-completo	PAG	PAG
Juego grafico	${\displaystyle ns^{d+1}}$	NP-completo	PPAD-completo	PAG	NP-duro
Juego simétrico	${\displaystyle s{\tbinom {n+s-1}{s-1}}}$	NP-completo	El cálculo del equilibrio de Nash simétrico es PPAD-difícil para dos jugadores. El cálculo del equilibrio de Nash no simétrico para dos jugadores es NP-completo.	PAG	PAG
Juego anónimo	${\displaystyle sn{\tbinom {n+s-1}{s-1}}}$	NP-duro		PAG	PAG
Juego de Polymatrix	${\displaystyle n^{2}s^{2}}$		PPAD-completo (polinomio para polimatriz de suma cero)	PAG	NP-duro
Juego de circuito		${\displaystyle \Sigma _{2}^{\rm {P}}}$-completo
Juego de congestión		PLS-completo		PAG	NP-duro

Notas

1. Papadimitriou, Christos H. (2007). "La complejidad de encontrar los equilibrios de Nash". En Nisan, Noam; Roughgarden, Tim; Tardos, Éva; et al. (eds.). Teoría algorítmica de juegos . Prensa de la Universidad de Cambridge. págs.  29 –52. ISBN  978-0-521-87282-9.
2. Papadimitriou, Christos H .; Roughgarden, Tim (2008). "Computación de equilibrios correlacionados en juegos multijugador". J. ACM . 55 (3): 1–29. CiteSeerX 10.1.1.335.2634 . doi : 10.1145 / 1379759.1379762 .  
3. Goldberg, Paul W .; Papadimitriou, Christos H. (2006). "Reducibilidad entre problemas de equilibrio" . Actas del trigésimo octavo simposio anual de ACM sobre teoría de la computación . Seattle, WA, Estados Unidos: ACM. págs. 61–70. doi : 10.1145 / 1132516.1132526 . ISBN  1-59593-134-1. Consultado el 25 de enero de 2010 .
4. Gottlob, G .; Greco, G .; Scarcello, F. (2005). "Equilibrios puros de Nash: juegos difíciles y fáciles". Revista de Investigación en Inteligencia Artificial . 24 (195–220): 26–37. arXiv : 1109.2152 . doi : 10.1613 / jair.1683 .
5. Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H. (2006). "El mundo del juego es plano: la complejidad de los equilibrios de Nash en juegos sucintos". Autómatas, lenguajes y programación . Apuntes de conferencias en Ciencias de la Computación. 4051 . págs. 513–524. CiteSeerX 10.1.1.111.8075 . doi : 10.1007 / 11786986_45 . ISBN   978-3-540-35904-3.
6. Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua (2006). "Los juegos dispersos son difíciles". Economía de Internet y redes . págs.  262-273 . doi : 10.1007 / 11944874_24 . ISBN  978-3-540-68138-0.
7. Cheng, Shih-Fen; Reeves, Daniel M .; Vorobeychik, Yevgeniy; Wellman, Michael P. (2004). Notas sobre equilibrios en juegos simétricos . Taller AAMAS-04 sobre Teoría de Juegos y Teoría de Decisiones.
8. Brandt, Felix; Fischer, Felix; Holzer, Markus (2009). "Simetrías y la complejidad del equilibrio puro de Nash" . J. Comput. Syst. Sci . 75 (3): 163-177. doi : 10.1016 / j.jcss.2008.09.001 . Consultado el 31 de enero de 2010 .
9. Papadimitriou, Christos H .; Roughgarden, Tim (2005). "Calculando equilibrios en juegos multijugador" . Actas del decimosexto simposio anual ACM-SIAM sobre algoritmos discretos . Vancouver, Columbia Británica: Sociedad de Matemáticas Industriales y Aplicadas. págs. 82–91. ISBN  0-89871-585-7. Consultado el 25 de enero de 2010 .
10. Daskalakis, Constantinos; Papadimitriou, Christos H. (2007). "Calculando equilibrios en juegos anónimos". arXiv : 0710.5582v1 [ cs ].
11. Howson, Joseph T. (enero de 1972). "Equilibrios de juegos de Polymatrix". Ciencias de la gestión . 18 (5): 312–318. doi : 10.1287 / mnsc.18.5.312 . ISSN 0025-1909 . JSTOR 2634798 .   
12. Rubinstein, Aviad (1 de enero de 2015). Inaproximación del equilibrio de Nash . Actas del 47º Simposio Anual ACM sobre Teoría de la Computación . STOC '15. Nueva York, NY, EE.UU .: ACM. págs. 409–418. arXiv : 1405.3322 . doi : 10.1145 / 2746539.2746578 . ISBN 9781450335362.
13. Cai, Y., Candogan, O., Daskalakis, C. y Papadimitriou, C. (2016). Juegos Polymatrix de suma cero: una generalización de Minimax. https://people.csail.mit.edu/costis/zerosum_final3.pdf
14. O. Person https://pypi.org/project/polymatrix/
15. Rahn, Mona y Schafer, Guido (2015) Equilibrios eficientes en juegos de coordinación Polymatrix https://arxiv.org/pdf/1504.07518.pdf
16. Feigenbaum, Joan; Koller, Daphne; Shor, Peter (1995). Una clasificación teórica de juegos de clases de complejidad interactiva . Certificador de Matemática Discreta e Informática Teórica . Consultado el 25 de enero de 2010 .
17. Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher (2005). "Sobre la complejidad de los juegos sucintos de suma cero" . Actas de la 20ª Conferencia Anual IEEE sobre Complejidad Computacional . Sociedad de Informática IEEE. págs. 323–332. ISBN  0-7695-2364-1. Consultado el 23 de enero de 2010 .
18. Schoenebeck, subvención; Vadhan, Salil (2006). "La complejidad computacional de los equilibrios nash en juegos representados de forma concisa" . Actas de la 7ª conferencia ACM sobre comercio electrónico . Ann Arbor, Michigan, Estados Unidos: ACM. págs. 270-279. doi : 10.1145 / 1134707.1134737 . ISBN  1-59593-236-4. Consultado el 25 de enero de 2010 .

enlaces externos

• Teoría algorítmica de juegos: la complejidad computacional del Nash puro