Juego conciso

Los juegos gráficos son juegos en los que la utilidad de cada jugador depende de las acciones de muy pocos otros jugadores. Si${\displaystyle d}$es el mayor número de jugadores por cuyas acciones afecta a cualquier jugador individual (es decir, es el grado de entrada del grafo del juego), el número de valores de utilidad necesarios para describir el juego es${\displaystyle ns^{d+1}}$, que, por un pequeño${\displaystyle d}$Es una mejora considerable.

Se ha demostrado que cualquier juego en forma normal es reducible a un juego gráfico con todos los grados acotados por tres y con dos estrategias para cada jugador. ^{[ 3 ]} A diferencia de los juegos en 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 un grafo con un ancho de árbol acotado , esto también es cierto para encontrar un equilibrio correlacionado óptimo . ^{[ 2 ]}

Los juegos dispersos son aquellos en los que la mayoría de las utilidades son nulas. Los juegos gráficos pueden considerarse 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 pagos (utilidad) tiene como máximo un número constante de entradas distintas de cero. Se ha demostrado que encontrar un equilibrio de Nash en un juego disperso de este tipo es PPAD-difícil, y que no existe un esquema de aproximación totalmente ^polinomial a menos que PPAD esté en P. [ ^{6 ]}

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${\displaystyle n}$Los jugadores juegan cada uno de los${\displaystyle s}$estrategias. Por lo tanto, describir dicho juego requiere dar solo${\displaystyle s{\tbinom {n+s-2}{s-1}}}$valores de utilidad.

En un juego simétrico con 2 estrategias siempre existe un equilibrio de Nash puro, aunque un equilibrio de Nash puro simétrico puede no existir. ^{[ 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 se enfrentan a k estrategias, se puede encontrar un equilibrio simétrico en tiempo polinomial si k=${\displaystyle O(\log n/\log \log n)}$. ^{[ 9 ]} Encontrar un equilibrio correlacionado en juegos simétricos puede hacerse en tiempo polinomial. ^{[ 2 ]}

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" preocupándose solo por la cantidad de gente que habrá en cada lugar, no por a quién conocerán allí). En un juego así, la utilidad de un jugador depende de cuántos de sus compañeros elijan qué estrategia, y de la suya propia, por lo que${\displaystyle sn{\tbinom {n+s-2}{s-1}}}$Se requieren valores de utilidad.

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 ]} Un equilibrio correlacionado óptimo de un juego anónimo puede encontrarse en tiempo polinomial. ^{[ 2 ]} Cuando el número de estrategias es 2, existe un PTAS conocido para encontrar un equilibrio de Nash ε-aproximado . ^{[ 10 ]}

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

Los juegos de polimatricias siempre tienen al menos un equilibrio de Nash mixto. ^{[ 11 ]} El problema de encontrar un equilibrio de Nash en un juego de polimatricias es PPAD-completo. ^{[ 5 ]} Además, el problema de encontrar un equilibrio de Nash aproximado constante en un juego de polimatricias también es PPAD-completo. ^{[ 12 ]} Encontrar un equilibrio correlacionado de un juego de polimatricias se puede hacer en tiempo polinomial. ^{[ 2 ]} Nótese que incluso si los juegos por pares jugados entre jugadores tienen equilibrios de Nash puros, la interacción global no necesariamente admite un equilibrio de Nash puro (aunque debe existir un equilibrio de Nash mixto). Verificar si existe un equilibrio de Nash puro es un problema fuertemente NP-completo . ^{[ 13 ]}

Los juegos competitivos de polimatrices con interacciones de suma cero entre jugadores son una generalización de los juegos de suma cero para dos jugadores . El teorema Minimax, formulado originalmente para juegos de dos jugadores por von Neumann, se generaliza a los juegos de polimatrices de suma cero. ^{[ 14 ]} Al igual que los juegos de suma cero para dos jugadores, los juegos de suma cero de polimatrices tienen equilibrios de Nash mixtos que se pueden calcular en tiempo polinomial y estos 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 max-min en el sentido de que las peores ganancias de los jugadores no se maximizan cuando se utiliza una estrategia de equilibrio. Existe una biblioteca de Python de código abierto ^{[ 15 ]} para simular juegos competitivos de polimatrices.

Los juegos de polimatriciales que tienen juegos de coordinación en sus aristas son juegos potenciales ^{[ 16 ]} y pueden resolverse utilizando un método de función potencial.

La forma más flexible de representar un juego conciso es mediante una máquina de Turing con tiempo polinomial limitado , que recibe como entrada las acciones de todos los jugadores y produce como salida la utilidad de cada jugador. Dicha máquina de Turing es equivalente a un circuito booleano , y es esta representación, conocida como juegos de circuito , la que analizaremos.

Calcular el valor de un juego de circuito de suma cero para 2 jugadores es un problema EXP -completo, ^{[ 17 ]} y se sabe que aproximar el valor de dicho juego hasta un factor multiplicativo está en PSPACE . ^{[ 18 ]} Determinar si existe un equilibrio de Nash puro es un problema${\displaystyle \Sigma _{2}^{\rm {P}}}$-problema completo (véase Jerarquía de polinomios ). ^{[ 19 ]}

Existen muchos otros tipos de juegos concisos (muchos de ellos relacionados con la asignación de recursos). Algunos ejemplos son los juegos de congestión , los juegos de congestión de red , los juegos de programación , los juegos de efectos locales , los juegos de localización de instalaciones , los juegos de grafos de acción , los juegos hipergráficos y otros.