Efficient Decomposition of Bimatrix Games (Extended Abstract)

Xiang Jiang
(University of Cambridge)
Arno Pauly
(University of Cambridge)

Exploiting the algebraic structure of the set of bimatrix games, a divide-and-conquer algorithm for finding Nash equilibria is proposed. The algorithm is fixed-parameter tractable with the size of the largest irreducible component of a game as parameter. An implementation of the algorithm is shown to yield a significant performance increase on inputs with small parameters.

In Fabio Mogavero, Aniello Murano and Moshe Y. Vardi: Proceedings 2nd International Workshop on Strategic Reasoning (SR 2014), Grenoble, France, April 5-6, 2014, Electronic Proceedings in Theoretical Computer Science 146, pp. 75–81.
Published: 1st April 2014.

ArXived at: http://dx.doi.org/10.4204/EPTCS.146.10 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org