Pesquisei no fórum para verificar se isso já havia sido perguntado antes e, embora a teoria algorítmica dos jogos seja discutida, não foi possível encontrar esse problema em particular. Estou tentando descobrir qual é o algoritmo mais conhecido para calcular equilíbrios aproximados de Nash (estratégia mista) em um jogo finito de n-pessoa. Obviamente, esse algoritmo seria PPAD. Estou mais interessado em velocidade / eficiência do que precisão perfeita do algoritmo.
Obrigado Philip
ds.algorithms
gt.game-theory
Philip White
fonte
fonte
Respostas:
A resposta curta é que, embora existam algoritmos de tempo polinomial para comprovadamente encontrar equilíbrios aproximados de Nash, todos eles encontram aproximações relativamente ruins - provavelmente não são boas o suficiente se você estiver realmente tentando encontrar um algoritmo para jogar um jogo. Sabe-se mais para jogos de 2 jogadores do que para jogos de n jogadores.
Se o que você está tentando fazer é realmente encontrar um equilíbrio (aproximado) de Nash, uma coisa fácil de codificar que você pode tentar é simular o jogo, com cada jogador usando o algoritmo de maioria ponderada aleatória (http://en.wikipedia.org/ wiki / Randomized_weighted_majority_algorithm). Isso não garante que funcione, mas em muitos casos funcionará (e é garantido em determinadas classes de jogos, como jogos de soma zero). Em particular, se esse processo convergir, é garantido que converge para um equilíbrio de Nash. O perigo é que ele não converja e circule para sempre - mas mesmo nesse caso, a história empírica do jogo converge para o conjunto de equilíbrios grosseiros correlacionados.
fonte
Talvez o artigo de 2008 apresentado no Simpósio sobre Teoria dos Jogos Algorítmicos de Hémon, Rougemont e Santha, " Equilíbrio aproximado de Nash para jogos com vários jogadores " possa ajudar? Eles "exibem algoritmos de tempo polinomial para aproximação aditiva" para jogos com jogadores.n
fonte
Se você está interessado em algoritmos realmente implementados em software, há vários que eu conheço:
o pacote GAMBIT (http://www.gambit-project.org/doc/index.html) implementa vários algoritmos de equilíbrio de Nash para a forma normal de 2 jogadores e n-jogadores e, em alguns casos, jogos extensos.
O GameTracer (http://dags.stanford.edu/Games/gametracer.html) implementa os algoritmos GNM e IPA da Govindan & Wilson para jogos em formato normal para n jogadores.
Para jogos grandes, a representação da forma normal é problemática, pois o tamanho aumenta exponencialmente no número de jogadores. Em vez disso, se a função de utilidade do seu jogo tiver certos tipos de estrutura, você poderá usar uma "representação concisa" (por exemplo, jogos gráficos, jogos simétricos, jogos com gráficos de ação) para expressá-la usando muito menos espaço; além disso, a estrutura pode ser frequentemente explorada para acelerações computacionais. Em termos de software, o AGG Solver (http://agg.cs.ubc.ca) adapta o algoritmo GNM do GameTracer e o algoritmo simpdiv do GAMBIT à representação do jogo de gráficos de ação (AGG). (Isenção de responsabilidade: estou envolvido no desenvolvimento deste software pacakge.)
fonte