Constant Rank Two-Player Games are PPAD-hard
From MaRDI portal
Publication:4554071
DOI10.1137/15M1032338zbMath1419.91009OpenAlexW2898884066MaRDI QIDQ4554071
Publication date: 7 November 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1032338
Analysis of algorithms (68W40) Noncooperative games (91A10) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Fast Algorithms for Rank-1 Bimatrix Games ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On total functions, existence theorems and computational complexity
- On competitiveness in uniform utility allocation markets
- Games of fixed rank: a hierarchy of bimatrix games
- Equilibrium tracing in strategic-form games
- New algorithms for approximate Nash equilibria in bimatrix games
- The complexity of stochastic games
- On the complexity of the parity argument and other inefficient proofs of existence
- The equivalence of linear programs and zero-sum games
- Simple complexity from imitation games
- Non-cooperative games
- On the Complexity of Nash Equilibria and Other Fixed Points
- A procedure for finding Nash equilibria in bi-matrix games
- Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- On the Complexity of 2D Discrete Fixed Point Problem
- The Complexity of Solving Stochastic Games on Graphs
- Reducibility among Fractional Stability Problems
- Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
- On oblivious PTAS's for nash equilibrium
- The Complexity of Computing a Nash Equilibrium
- A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
- Equilibrium Points of Bimatrix Games
- Rank-1 bimatrix games
- Nash equilibria in random games
- Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
- Hard-to-Solve Bimatrix Games
- The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
- The approximate rank of a matrix and its algorithmic applications
- Bimatrix Equilibrium Points and Mathematical Programming
This page was built for publication: Constant Rank Two-Player Games are PPAD-hard
