Some Tractable Win-Lose Games

DOI10.1007/978-3-642-20877-5_36zbMath1332.91011arXiv1010.5951OpenAlexW1571611914MaRDI QIDQ3010417

Nagarajan Krishnamurthy, Samir Datta

Publication date: 1 July 2011

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

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

Mathematics Subject Classification ID

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

Related Items (1)

The complexity of computational problems about Nash equilibria in symmetric win-lose games

Cites Work

• Unnamed Item
• An approach to the subgraph homeomorphism problem
• NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems
• On the complexity of the parity argument and other inefficient proofs of existence
• Non-cooperative games
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space.
• Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
• Settling the complexity of computing two-player Nash equilibria
• Dividing a Graph into Triconnected Components
• The Complexity of Computing a Nash Equilibrium
• 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

This page was built for publication: Some Tractable Win-Lose Games