Teoría gráfica de juegos - Graphical game theory

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}$

Definicion formal

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 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}$

El tamaño de la representación del juego.

Para un juego de jugadores en 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}$

Un ejemplo

En caso de que la función de utilidad de cada jugador dependa solo de otro jugador:

• 

  La forma gráfica del juego descrito.

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}}$${\ Displaystyle nm ^ {2}}$

equilibrio de Nash

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 .

Otras lecturas

• Michael Kearns (2007) " Juegos gráficos ". En Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoría algorítmica de juegos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
• Michael Kearns, Michael L. Littman y Satinder Singh (2001) " Modelos gráficos para teoría de juegos ".