A simple algorithm for computing Nash-equilibria in incomplete information games

Elvis Dohmatob 1
1 PARIETAL - Modelling brain structure, function and variability based on high-field MRI data
Inria Saclay - Ile de France, NEUROSPIN - Service NEUROSPIN
Abstract : We present a simple projection-free primal-dual algorithm for computing approximate Nash-equilibria in two-person zero-sum sequential games with incomplete information and perfect recall (like Texas Hold’em Poker). Our algorithm is numerically stable, performs only basic iterations (i.e matvec multiplications, clipping, etc., and no calls to external first-order oracles, no matrix inversions, etc.), and is applicable to a broad class of two-person zero-sum games including simultaneous games and sequential games with incomplete information and perfect recall. The applicability to the latter kind of games is thanks to the sequence-form representation which allows one to encode such a game as a matrix game with convex polytopial strategy profiles. We prove that the number of iterations needed to produce a Nash-equilibrium with a given precision is inversely proportional to the precision. We present experimental results on matrix games on simplexes and Kuhn Poker.
Type de document :
Communication dans un congrès
OPT2016 -- NIPS workshop on optimization for machine learning, Dec 2016, Barcelona, Spain. 2016, 〈http://opt-ml.org/〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01384460
Contributeur : Elvis Dohmatob <>
Soumis le : jeudi 20 octobre 2016 - 00:57:53
Dernière modification le : vendredi 22 juin 2018 - 01:20:30

Fichier

paper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01384460, version 1

Citation

Elvis Dohmatob. A simple algorithm for computing Nash-equilibria in incomplete information games. OPT2016 -- NIPS workshop on optimization for machine learning, Dec 2016, Barcelona, Spain. 2016, 〈http://opt-ml.org/〉. 〈hal-01384460〉

Partager

Métriques

Consultations de la notice

487

Téléchargements de fichiers

391