Settling the complexity of computing two-player Nash equilibria
From MaRDI portal
Publication:3452212
DOI10.1145/1516512.1516516zbMath1325.68095arXiv0704.1678OpenAlexW2057913812MaRDI QIDQ3452212
Xi Chen, Xiaotie Deng, Shang-Hua Teng
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0704.1678
Nash equilibriumSperner's lemmatwo-player gameLemke-Howson algorithmsmoothed analysisPPAD-completenessArrow-Debreu marketBrouwer's fixed point
Noncooperative games (91A10) Special types of economic equilibria (91B52) 2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (only showing first 100 items - show all)
On the Complexity of Equilibrium Computation in First-Price Auctions ⋮ TFNP: An Update ⋮ Consensus-Halving: Does It Ever Get Easier? ⋮ A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games ⋮ Evolution of Mixed Strategies in Monotone Games ⋮ Public goods games in directed networks ⋮ Automated equilibrium analysis of \(2\times 2\times 2\) games ⋮ A fast algorithm to solve large-scale matrix games based on dimensionality reduction and its application in multiple unmanned combat air vehicles attack-defense decision-making ⋮ Provably efficient reinforcement learning in decentralized general-sum Markov games ⋮ Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ PPAD is as hard as LWE and iterated squaring ⋮ Tropical Complementarity Problems and Nash Equilibria ⋮ Unnamed Item ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ Structure Versus Hardness Through the Obfuscation Lens ⋮ COMPUTING NASH EQUILIBRIA FOR TWO-PLAYER RESTRICTED NETWORK CONGESTION GAMES IS $\mathcal{PLS}$-COMPLETE ⋮ The classes PPA-\(k\): existence from arguments modulo \(k\) ⋮ From Minicrypt to Obfustopia via Private-Key Functional Encryption ⋮ Can PPAD hardness be based on standard cryptographic assumptions? ⋮ Substitution with Satiation: A New Class of Utility Functions and a Complementary Pivot Algorithm ⋮ The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg ⋮ Unnamed Item ⋮ The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Consensus Halving for Sets of Items ⋮ Inapproximability of Nash Equilibrium ⋮ 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties ⋮ Computing approximate Nash equilibria in general network revenue management games ⋮ ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria ⋮ Settling Some Open Problems on 2-Player Symmetric Nash Equilibria ⋮ Approximating Nash Equilibria in Tree Polymatrix Games ⋮ Smoothed Analysis of Local Search Algorithms ⋮ The Journey from NP to TFNP Hardness ⋮ On the complexity of an expanded Tarski's fixed point problem under the componentwise ordering ⋮ Computing equilibria: a computational complexity perspective ⋮ A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities ⋮ Equilibrium computation in resource allocation games ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ Inverse Game Theory: Learning Utilities in Succinct Games ⋮ Approximate well-supported Nash equilibria below two-thirds ⋮ Constant Rank Two-Player Games are PPAD-hard ⋮ A Glimpse at Paul G. Spirakis ⋮ Weighted Boolean Formula Games ⋮ The Linear Complementarity Problems with a Few Variables per Constraint ⋮ Communication complexity of approximate Nash equilibria ⋮ The Computational Complexity of Finding a Mixed Berge Equilibrium for a k-Person Noncooperative Game in Normal Form ⋮ An algorithm for finding approximate Nash equilibria in bimatrix games ⋮ Computing pure Nash equilibria in network revenue management games ⋮ On the performance of mildly greedy players in cut games ⋮ LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization ⋮ Query complexity of approximate equilibria in anonymous games ⋮ The complexity of computational problems about Nash equilibria in symmetric win-lose games ⋮ Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem ⋮ Mixing time and stationary expected social welfare of logit dynamics ⋮ The Exact Computational Complexity of Evolutionarily Stable Strategies ⋮ From minicrypt to obfustopia via private-key functional encryption ⋮ Parameterized complexity of sparse linear complementarity problems ⋮ Belief-invariant and quantum equilibria in games of incomplete information ⋮ On the approximation performance of fictitious play in finite games ⋮ Complexity of rational and irrational Nash equilibria ⋮ On tightness of the Tsaknakis-Spirakis algorithm for approximate Nash equilibrium ⋮ \(\mathsf{PPAD}\)-completeness of polyhedral versions of Sperner's lemma ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ On Pure Nash Equilibria in Stochastic Games ⋮ Learning convex partitions and computing game-theoretic equilibria from best response queries ⋮ Recursive stochastic games with positive rewards ⋮ Total functions in QMA ⋮ Unique end of potential line ⋮ Computing Equilibria with Partial Commitment ⋮ Distributed Methods for Computing Approximate Equilibria ⋮ Unnamed Item ⋮ Sperner’s Colorings and Optimal Partitioning of the Simplex ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Tatonnement beyond gross substitutes? Gradient descent to the rescue ⋮ Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds ⋮ Colorful linear programming, Nash equilibrium, and pivots ⋮ Understanding PPA-completeness ⋮ Computational aspects of uncertainty profiles and angel-daemon games ⋮ On the communication complexity of approximate Nash equilibria ⋮ The computational complexity of weak saddles ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ Computing exact solutions of consensus halving and the Borsuk-Ulam theorem ⋮ Computing solutions of the multiclass network equilibrium problem with affine cost functions ⋮ Semidefinite programming for min-max problems and games ⋮ The Hairy Ball problem is PPAD-complete ⋮ Distributed methods for computing approximate equilibria ⋮ Equilibrium paths in discounted supergames ⋮ Amortized Analysis of Asynchronous Price Dynamics ⋮ Some Tractable Win-Lose Games ⋮ Towards a unified complexity theory of total functions ⋮ Automatizability and Simple Stochastic Games ⋮ Limited lookahead in imperfect-information games ⋮ Computing approximate Nash equilibria in polymatrix games ⋮ On Stackelberg mixed strategies ⋮ On the complexity of deciding bimatrix games similarity ⋮ Approximation schemes for stochastic mean payoff games with perfect information and few random positions
This page was built for publication: Settling the complexity of computing two-player Nash equilibria
