Constant rank bimatrix games are PPAD-hard

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-$0$, 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-$1$ games, leaving rank-2 and beyond unresolved. In this paper we show that NE computation in games with rank $ge3$, 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 $ge6$ 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-$2$ games remains unresolved.

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

Recommendations

• Constant rank two-player games are PPAD-hard
• Games of fixed rank: a hierarchy of bimatrix games
• Games of fixed rank: a hierarchy of bimatrix games
• 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)

zbMATH Keywords

constant rankLCPPPAD-hard2D-Brouwerlinear-FIXP

Mathematics Subject Classification ID

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
• The geometry of differential privacy: the small database and approximate cases
• 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
• 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
• Privately releasing conjunctions and the statistical query barrier
• 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?)
• Understanding PPA-completeness
• On Random Symmetric Bimatrix Games
• Games of fixed rank: a hierarchy of bimatrix games
• Unique End of Potential Line
• Unique end of potential line
• Public goods games in directed networks
• Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
• Settling Some Open Problems on 2-Player Symmetric Nash Equilibria
• Complexity of equilibria in first-price auctions under general tie-breaking rules
• Title not available (Why is that?)

Uses Software

• SuLQ

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)