| Article ID: | iaor20131262 |
| Volume: | 65 |
| Issue: | 4 |
| Start Page Number: | 802 |
| End Page Number: | 816 |
| Publication Date: | Apr 2013 |
| Journal: | Algorithmica |
| Authors: | Huang Chien-Chung, Hermelin Danny, Kratsch Stefan, Wahlstrm Magnus |
| Keywords: | combinatorial optimization |
We study the problem of computing Nash equilibria in a two‐player normal form (bimatrix) game from the perspective of parameterized complexity. Recent results proved hardness for a number of variants, when parameterized by the support size. We complement those results, by identifying three cases in which the problem becomes fixed‐parameter tractable. Our results are based on a graph‐theoretic representation of a bimatrix game, and on applying graph‐theoretic tools on this representation.