Sparse Binary Zero-Sum Games

David Auger 1 Jialin Liu 1, 2 Sylvie Ruette 3 David L. Saint-Pierre 2 Olivier Teytaud 2, 1
2 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Solving zero-sum matrix games is polynomial, because it boils down to linear programming. The approximate solving is sublinear by randomized algorithms on machines with random access memory. Algorithms working separately and independently on columns and rows have been proposed, with the same performance; these versions are compliant with matrix games with stochastic reward. (Flory and Teytaud, 2011) has proposed a new version, em-pirically performing better on sparse problems, i.e. cases in which the Nash equilibrium has small support. In this paper, we propose a variant, similar to their work, also dedicated to sparse problems, with provably better bounds than existing methods. We then experiment the method on a card game.
Type de document :
Communication dans un congrès
Asian Conference on Machine Learning, 2014, Ho-Chi-Minh-Ville, Vietnam. 29, pp.16, 2014
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01077627
Contributeur : Olivier Teytaud <>
Soumis le : lundi 3 novembre 2014 - 02:01:51
Dernière modification le : jeudi 11 janvier 2018 - 06:22:14
Document(s) archivé(s) le : mercredi 4 février 2015 - 10:06:54

Fichier

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

Identifiants

  • HAL Id : hal-01077627, version 1

Citation

David Auger, Jialin Liu, Sylvie Ruette, David L. Saint-Pierre, Olivier Teytaud. Sparse Binary Zero-Sum Games. Asian Conference on Machine Learning, 2014, Ho-Chi-Minh-Ville, Vietnam. 29, pp.16, 2014. 〈hal-01077627〉

Partager

Métriques

Consultations de la notice

484

Téléchargements de fichiers

169