Algorithmes pour le calcul de l'équilibre de Nash.

10

J'ai cherché sur le forum pour voir si cela avait déjà été demandé, et bien que la théorie algorithmique des jeux soit discutée, je n'ai pas trouvé ce problème particulier résolu. J'essaie de comprendre quel est l'algorithme le plus connu pour calculer les équilibres de Nash approximatifs (à stratégie mixte) dans un jeu à n personnes. Bien sûr, cet algorithme serait PPAD. Je m'intéresse plus à la vitesse / efficacité qu'à la parfaite précision de l'algorithme.

Merci, Philip

ds.algorithms gt.game-theory Philip White
la source
Nous pouvons mieux vous aider si vous donnez plus de détails. Par exemple, quelle valeur de pensez-vous? Avez-vous une structure particulière de la fonction de paiement à l'esprit? Avez-vous vraiment besoin d'un équilibre de Nash ou un équilibre corrélé suffirait-il? Cherchez-vous quelque chose avec de bonnes limites prouvables ou quelque chose avec de bonnes performances pratiques? n
Warren Schudy

Réponses:

7

La réponse courte est que, bien qu'il existe des algorithmes polynomiaux pour trouver de manière prouvée des équilibres de Nash approximatifs, ils trouvent tous des approximations relativement médiocres - probablement pas assez bonnes si vous essayez réellement de trouver un algorithme pour jouer à un jeu. Plus est connu pour les jeux à 2 joueurs que pour les jeux à n joueurs.

Si ce que vous essayez de faire est de trouver un équilibre Nash (approximatif), une chose facile à coder que vous pourriez essayer est de simuler le jeu, chaque joueur utilisant l'algorithme de la majorité pondérée aléatoire (http://en.wikipedia.org/ wiki / Randomized_weighted_majority_algorithm). Cela n'est pas garanti de fonctionner, mais dans de nombreux cas (et est garanti dans certaines classes de jeux, comme les jeux à somme nulle). En particulier, si ce processus converge, il est certain qu'il convergera vers un équilibre de Nash. Le danger est qu'il ne converge pas et ne tourne pas pour toujours - mais même dans ce cas, l'histoire empirique du jeu va converger vers l'ensemble d'équilibres corrélés grossiers.

Aaron Roth
la source
J'ai commencé à jeter un œil au document mentionné dans la réponse ci-dessus. Je n'ai pas tout compris (ou une grande partie à première vue) ... pouvez-vous expliquer pourquoi l'approximation est "relativement mauvaise?" Pouvez-vous également expliquer brièvement ce qu'est un «équilibre corrélé grossier»? Je sais ce qu'est un équilibre corrélé, mais ce que cela signifie pour un tel éq. être grossier. Enfin, que voulez-vous dire par "l'histoire empirique du jeu convergera ... [etc.]"? Comment quelque chose qui ne converge jamais peut-il converger vers un ensemble de CCE? Merci pour votre réponse, je recherche maintenant l'article Wikipédia.
Philip White
Pour quelques informations sur les algorithmes qui produisent des distributions qui convergent vers des équilibres corrélés grossiers ou des équilibres corrélés, je commencerais ici: cs.cmu.edu/~avrim/Papers/regret-chapter.pdf
Aaron Roth
Si vous voulez des équilibres corrélés plutôt que des équilibres corrélés grossiers, vous pouvez utiliser un apprenant sans regret interne. Par exemple (prise sans vergogne) cs.brown.edu/~ws/papers/regret.pdf . Il existe également des algorithmes pour calculer les équilibres corrélés directement en temps polynomial.
Warren Schudy
10

Peut-être que l'article de 2008 présenté au Symposium sur la théorie des jeux algorithmiques par Hémon, Rougemont et Santha, " Equilibres approximatifs de Nash pour les jeux multi-joueurs " pourrait aider? Ils "présentent des algorithmes polynomiaux pour l'approximation additive" pour les jeux à joueurs.n

Joseph O'Rourke
la source
4

Si vous êtes intéressé par les algorithmes qui sont réellement implémentés dans un logiciel, j'en connais plusieurs:

  1. le package GAMBIT (http://www.gambit-project.org/doc/index.html) implémente plusieurs algorithmes d'équilibre Nash pour la forme normale à 2 joueurs et n joueurs, et dans certains cas des jeux de forme étendus.

  2. GameTracer (http://dags.stanford.edu/Games/gametracer.html) implémente les algorithmes GNM et IPA de Govindan & Wilson pour les jeux de forme normale à n joueurs.

  3. Pour les grands jeux, la représentation de la forme normale est problématique car la taille augmente de façon exponentielle dans le nombre de joueurs. Au lieu de cela, si la fonction d'utilité de votre jeu a certains types de structure, vous pouvez utiliser une "représentation concise" (par exemple des jeux graphiques, des jeux symétriques, des jeux de graphes d'action) pour l'exprimer en utilisant beaucoup moins d'espace; et en outre, la structure peut souvent être exploitée pour des accélérations de calcul. En termes de logiciel, le solveur AGG (http://agg.cs.ubc.ca) adapte l'algorithme GNM de GameTracer et l'algorithme simpdiv de GAMBIT à la représentation du jeu de graphes d'action (AGG). (Avertissement: je suis impliqué dans le développement de ce logiciel pacakge.)

Albert
la source