Header menu link for other important links
Some Tractable Win-Lose Games
Published in Springer Berlin Heidelberg
Pages: 365 - 376

Finding a Nash equilibrium in a bimatrix game is PPAD-hard (Chen and Deng, 2006 [3], Chen, Deng and Teng, 2009 [6]). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane and Valiant, 2005 [1]). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta, 2006 [8]) and planar games (Addario-Berry, Olver and Vetta, 2007 [2]).

We extend the results in the latter work to K 3,3 minor-free games and a subclass of K 5 minor-free games. Both these classes strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace UL, a small complexity class contained well within polynomial time P. Apart from these classes of games, our results also extend to a class of games that contain both K 3,3 and K 5 as minors, thereby covering a large and non-trivial class of win-lose bimatrix games. For this class, we prove an upper bound of nondeterministic logspace NL, again a small complexity class in P. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.

About the journal
JournalData powered by TypesetInternational Conference on Theory and Applications of Models of Computation
PublisherData powered by TypesetSpringer Berlin Heidelberg
Open AccessNo