Skip to Main content Skip to Navigation
Conference papers

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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Monday, November 3, 2014 - 2:01:51 AM
Last modification on : Thursday, July 8, 2021 - 3:52:48 AM
Long-term archiving on: : Wednesday, February 4, 2015 - 10:06:54 AM


Files produced by the author(s)


  • HAL Id : hal-01077627, version 1


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. pp.16. ⟨hal-01077627⟩



Record views


Files downloads