Constant rank two-player games are PPAD-hard

DOI10.1137/15M1032338MaRDI QIDQ4554071zbMATH OpenOpenAlexFDO

Authors Ruta Mehta

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

zbMATH Keywords

bimatrix gamesNash equilibriumconstant rankLCPparameterized LPPPAD-hard

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05)

Recommendations

• Constant rank bimatrix games are PPAD-hard
• Settling the complexity of computing two-player Nash equilibria
• The complexity of computing a Nash equilibrium
• On the complexity of approximating a Nash equilibrium
• Settling some open problems on 2-player symmetric Nash equilibria

Cites work

• scientific article; zbMATH DE number 49749 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 3069631 (Why is no real title available?)
• A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose Games
• A procedure for finding Nash equilibria in bi-matrix games
• An optimization approach for approximate Nash equilibria
• Bimatrix Equilibrium Points and Mathematical Programming
• Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games
• Equilibrium Points of Bimatrix Games
• Equilibrium computation for two-player games in strategic and extensive form
• Equilibrium tracing in strategic-form games
• Hard-to-Solve Bimatrix Games
• Nash equilibria in random games
• New algorithms for approximate Nash equilibria in bimatrix games
• Non-cooperative games
• On competitiveness in uniform utility allocation markets
• On oblivious PTAS's for nash equilibrium
• On the Complexity of 2D Discrete Fixed Point Problem
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
• Reducibility among Fractional Stability Problems
• Settling some open problems on 2-player symmetric Nash equilibria
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• Settling the complexity of computing two-player Nash equilibria
• Simple complexity from imitation games
• The approximate rank of a matrix and its algorithmic applications
• The complexity of computing a Nash equilibrium
• The complexity of finding Nash equilibria
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games
• The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions
• The equivalence of linear programs and zero-sum games

Cited in

(9)

• On the Complexity of Equilibrium Computation in First-Price Auctions
• The complexity of gradient descent: CLS = PPAD \(\cap\) pls
• Fast Algorithms for Rank-1 Bimatrix Games
• The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
• Settling some open problems on 2-player symmetric Nash equilibria
• A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
• Consensus-Halving: Does It Ever Get Easier?
• Constant rank bimatrix games are PPAD-hard
• A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games

This page was built for publication: Constant rank two-player games are PPAD-hard

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