Teoría gráfica de juegos

En teoría de juegos , las formas comunes de describir un juego son la forma normal y la forma extensiva . La forma gráfica es una representación compacta alternativa de un juego que utiliza la interacción entre los participantes.

Considere un juego con jugadores con estrategias cada uno. Representaremos a los jugadores como nodos en un gráfico en el que cada jugador tiene una función de utilidad que depende solo de él y sus vecinos. Como la función de utilidad depende de menos jugadores, la representación gráfica sería más pequeña. ${\ Displaystyle n}$ ${\ Displaystyle m}$

Un juego gráfico está representado por un gráfico , en el que cada jugador está representado por un nodo, y hay una ventaja entre dos nodos y si sus funciones de utilidad dependen de la estrategia que elija el otro jugador. Cada nodo en tiene una función , donde es el grado de vértice . especifica la utilidad del jugador en función de su estrategia, así como las de sus vecinos. ${\ Displaystyle G}$ ${\ Displaystyle i}$ ${\ Displaystyle j}$ ${\ Displaystyle i}$ ${\ Displaystyle G}$ ${\ Displaystyle u_ {i}: \ {1 \ ldots m \} ^ {d_ {i} +1} \ rightarrow \ mathbb {R}}$ ${\ Displaystyle d_ {i}}$ ${\ Displaystyle i}$ ${\ Displaystyle u_ {i}}$ ${\ Displaystyle i}$

Para un juego de jugadores general , en el que cada jugador tiene posibles estrategias, el tamaño de una representación de forma normal sería . El tamaño de la representación gráfica de este juego es donde está el grado máximo del nodo en el gráfico. Si , entonces la representación gráfica del juego es mucho más pequeña. ${\ Displaystyle n}$ ${\ Displaystyle m}$ ${\ Displaystyle O (m ^ {n})}$ ${\ Displaystyle O (m ^ {d})}$ ${\ Displaystyle d}$ ${\ Displaystyle d \ ll n}$

El grado máximo del gráfico es 1, y el juego se puede describir como funciones (tablas) de tamaño . Entonces, el tamaño total de la entrada será . ${\ Displaystyle n}$ ${\ Displaystyle m ^ {2}}$ $nm^{2}$

Encontrar el equilibrio de Nash en un juego requiere un tiempo exponencial en el tamaño de la representación. Si la representación gráfica del juego es un árbol, podemos encontrar el equilibrio en el tiempo polinomial. En el caso general, donde el grado máximo de un nodo es 3 o más, el problema es NP-completo .