Constant rank bimatrix games are PPAD-hard
From MaRDI portal
Publication:5259590
DOI10.1145/2591796.2591835zbMATH Open1315.91002arXiv1402.3350OpenAlexW2067482046MaRDI QIDQ5259590FDOQ5259590
Authors: Ruta Mehta 
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Abstract: The rank of a bimatrix game (A,B) is defined as rank(A+B). Computing a Nash equilibrium (NE) of a rank-, i.e., zero-sum game is equivalent to linear programming (von Neumann'28, Dantzig'51). In 2005, Kannan and Theobald gave an FPTAS for constant rank games, and asked if there exists a polynomial time algorithm to compute an exact NE. Adsul et al. (2011) answered this question affirmatively for rank- games, leaving rank-2 and beyond unresolved. In this paper we show that NE computation in games with rank , is PPAD-hard, settling a decade long open problem. Interestingly, this is the first instance that a problem with an FPTAS turns out to be PPAD-hard. Our reduction bypasses graphical games and game gadgets, and provides a simpler proof of PPAD-hardness for NE computation in bimatrix games. In addition, we get: * An equivalence between 2D-Linear-FIXP and PPAD, improving a result by Etessami and Yannakakis (2007) on equivalence between Linear-FIXP and PPAD. * NE computation in a bimatrix game with convex set of Nash equilibria is as hard as solving a simple stochastic game. * Computing a symmetric NE of a symmetric bimatrix game with rank is PPAD-hard. * Computing a (1/poly(n))-approximate fixed-point of a (Linear-FIXP) piecewise-linear function is PPAD-hard. The status of rank- games remains unresolved.
Full work available at URL: https://arxiv.org/abs/1402.3350
Recommendations
- Constant rank two-player games are PPAD-hard
- Hard-to-Solve Bimatrix Games
- Rank-1 bimatrix games, a homeomorphism and a polynomial time algorithm
- Bimatrix games and bilinear programming
- On the exact polynomial time algorithm for a special class of bimatrix game
- Fast Algorithms for Rank-1 Bimatrix Games
- Random bimatrix games are asymptotically easy to solve (a simple proof)
- Random bimatrix games are asymptotically easy to solve (a simple proof)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) 2-person games (91A05)
Cites Work
- Theory of Cryptography
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower bounds in differential privacy
- Iterative Constructions and Private Data Release
- Differential privacy and the fat-shattering dimension of linear queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release, efficient algorithms and hardness results
- Title not available (Why is that?)
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- Title not available (Why is that?)
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the sample complexity for private learning and private data release
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (12)
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Title not available (Why is that?)
- Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
- Constant rank two-player games are PPAD-hard
- Understanding PPA-completeness
- Settling some open problems on 2-player symmetric Nash equilibria
- Unique End of Potential Line
- Unique end of potential line
- Public goods games in directed networks
- On random symmetric bimatrix games
- Complexity of equilibria in first-price auctions under general tie-breaking rules
- Title not available (Why is that?)
Uses Software
This page was built for publication: Constant rank bimatrix games are PPAD-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259590)
