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.

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. [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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v39-auger14, title = {Sparse binary zero-sum games}, author = {Auger, David and Liu, Jianlin and Ruette, Sylkvie and Saint-Pierre, David and Teytaud, Oliver}, booktitle = {Proceedings of the Sixth Asian Conference on Machine Learning}, pages = {173--188}, year = {2015}, editor = {Phung, Dinh and Li, Hang}, volume = {39}, series = {Proceedings of Machine Learning Research}, address = {Nha Trang City, Vietnam}, month = {26--28 Nov}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v39/auger14.pdf}, url = {https://proceedings.mlr.press/v39/auger14.html}, 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. [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.} }
Endnote
%0 Conference Paper %T Sparse binary zero-sum games %A David Auger %A Jianlin Liu %A Sylkvie Ruette %A David Saint-Pierre %A Oliver Teytaud %B Proceedings of the Sixth Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Dinh Phung %E Hang Li %F pmlr-v39-auger14 %I PMLR %P 173--188 %U https://proceedings.mlr.press/v39/auger14.html %V 39 %X 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.
RIS
TY - CPAPER TI - Sparse binary zero-sum games AU - David Auger AU - Jianlin Liu AU - Sylkvie Ruette AU - David Saint-Pierre AU - Oliver Teytaud BT - Proceedings of the Sixth Asian Conference on Machine Learning DA - 2015/02/16 ED - Dinh Phung ED - Hang Li ID - pmlr-v39-auger14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 39 SP - 173 EP - 188 L1 - http://proceedings.mlr.press/v39/auger14.pdf UR - https://proceedings.mlr.press/v39/auger14.html AB - 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. ER -
APA
Auger, D., Liu, J., Ruette, S., Saint-Pierre, D. & Teytaud, O.. (2015). Sparse binary zero-sum games. Proceedings of the Sixth Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 39:173-188 Available from https://proceedings.mlr.press/v39/auger14.html.

Related Material