Teoria gráfica do jogo - Graphical game theory

Na teoria dos jogos , as formas comuns de descrever um jogo são a forma normal e a forma extensiva . A forma gráfica é uma representação compacta alternativa de um jogo usando a interação entre os participantes.

Considere um jogo com jogadores com estratégias cada um. Vamos representar os jogadores como nós em um gráfico em que cada jogador tem uma função utilidade que depende apenas dele e de seus vizinhos. Como a função de utilidade depende de menos outros jogadores, a representação gráfica seria menor. ${\ displaystyle n}$${\ displaystyle m}$

Definição formal

Um jogo gráfico é representado por um gráfico , em que cada jogador é representado por um nó, e há uma borda entre dois nós e se suas funções de utilidade dependem da estratégia que o outro jogador escolherá. Cada nó em tem uma função , onde é o grau do vértice . especifica a utilidade do jogador em função de sua estratégia e também de seus vizinhos. ${\ 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}$

O tamanho da representação do jogo

Para um jogo de jogadores geral , em que cada jogador tem estratégias possíveis, o tamanho de uma representação de forma normal seria . O tamanho da representação gráfica para este jogo é onde está o grau de nó máximo no gráfico. Se , então a representação gráfica do jogo é muito menor. ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle O (m ^ {n})}$${\ displaystyle O (m ^ {d})}$${\ displaystyle d}$${\ displaystyle d \ ll n}$

Um exemplo

No caso em que a função de utilidade de cada jogador depende apenas de um outro jogador:

• 

  A forma gráfica do jogo descrito

O grau máximo do gráfico é 1, e o jogo pode ser descrito como funções (tabelas) de tamanho . Portanto, o tamanho total da entrada será . ${\ displaystyle n}$${\ displaystyle m ^ {2}}$${\ displaystyle nm ^ {2}}$

equilíbrio de Nash

Encontrar o equilíbrio de Nash em um jogo leva um tempo exponencial no tamanho da representação. Se a representação gráfica do jogo for uma árvore, podemos encontrar o equilíbrio em tempo polinomial. No caso geral, onde o grau máximo de um nó é 3 ou mais, o problema é NP-completo .

Leitura adicional

• Michael Kearns (2007) " Jogos Gráficos ". Em Vazirani, Vijay V .; Nisan, Noam ; Roughgarden, Tim ; Tardos, Éva (2007). Teoria Algorítmica dos Jogos (PDF) . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-87282-0.
• Michael Kearns, Michael L. Littman e Satinder Singh (2001) " Modelos Gráficos para Teoria dos Jogos ".