Constant rank two-player games are PPAD-hard

DOI10.1137/15M1032338zbMATH Open1419.91009OpenAlexW2898884066MaRDI QIDQ4554071FDOQ4554071

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

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

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)

Cites Work

• The complexity of stochastic games
• Non-cooperative games
• An optimization approach for approximate Nash equilibria
• Title not available (Why is that?)
• The complexity of computing a Nash equilibrium
• Bimatrix Equilibrium Points and Mathematical Programming
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• Title not available (Why is that?)
• Equilibrium Points of Bimatrix Games
• Settling the complexity of computing two-player Nash equilibria
• Equilibrium computation for two-player games in strategic and extensive form
• On total functions, existence theorems and computational complexity
• The complexity of finding Nash equilibria
• Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
• New algorithms for approximate Nash equilibria in bimatrix games
• The complexity of solving stochastic games on graphs
• Title not available (Why is that?)
• Nash equilibria in random games
• On the Complexity of 2D Discrete Fixed Point Problem
• Reducibility among Fractional Stability Problems
• 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
• On oblivious PTAS's for nash equilibrium
• Hard-to-Solve Bimatrix Games
• The approximate rank of a matrix and its algorithmic applications
• The equivalence of linear programs and zero-sum games
• A procedure for finding Nash equilibria in bi-matrix games
• Simple complexity from imitation games
• On competitiveness in uniform utility allocation markets
• Equilibrium tracing in strategic-form games
• Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
• The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions
• Settling some open problems on 2-player symmetric Nash equilibria

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)