Sparse binary zero-sum games


David Auger, Jianlin Liu, Sylkvie Ruette, David Saint-Pierre, Oliver Teytaud ;
Proceedings of the Sixth Asian Conference on Machine Learning, PMLR 39:173-188, 2015.


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. [1] has proposed a new version, empirically 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.

Related Material