Some tractable win-lose games

DOI10.1007/978-3-642-20877-5_36zbMATH Open1332.91011arXiv1010.5951OpenAlexW1571611914MaRDI QIDQ3010417FDOQ3010417

Authors: Samir Datta, Nagarajan Krishnamurthy 

Publication date: 1 July 2011

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Determining a Nash equilibrium in a $2$-player non-zero sum game is known to be PPAD-hard (Chen and Deng (2006), Chen, Deng and Teng (2009)). The problem, even when restricted to win-lose bimatrix games, remains PPAD-hard (Abbott, Kane and Valiant (2005)). However, there do exist polynomial time tractable classes of win-lose bimatrix games - such as, very sparse games (Codenotti, Leoncini and Resta (2006)) and planar games (Addario-Berry, Olver and Vetta (2007)). 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 of games strictly contain planar games. Further, we sharpen the upper bound to unambiguous logspace, a small complexity class contained well within polynomial time. 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, again a small complexity class within polynomial time. Our techniques are primarily graph theoretic and use structural characterizations of the considered minor-closed families.

Full work available at URL: https://arxiv.org/abs/1010.5951

Recommendations

• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• The complexity of decision problems about Nash equilibria in win-lose games
• Hard-to-Solve Bimatrix Games

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Non-cooperative games
• The complexity of computing a Nash equilibrium
• On the complexity of the parity argument and other inefficient proofs of existence
• Settling the complexity of computing two-player Nash equilibria
• Dividing a Graph into Triconnected Components
• Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
• Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• The approximation complexity of win-lose games
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• An approach to the subgraph homeomorphism problem

Cited In (3)

• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• The complexity of computational problems about Nash equilibria in symmetric win-lose games

This page was built for publication: Some tractable win-lose games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010417)