Some Tractable Win-Lose Games

摘要

Finding a Nash equilibrium in a bimatrix game is PPAD-hard (Chen and Deng, 2006 [5], 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 polyno mial 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 axe primarily graph theoretic and use structural characterizations of the considered minor-closed families.