No article text was recorded for this version.
PPAD-completeness (computational intractability of exact equilibria)
Version 2 of 2153 papers192 conceptsfrozen 2026-10-04
Papers in this version
- Blog: Some Recent Results in Algorithmic Game Theory
- Blog: On Equilibrium Computation in Biased Games with Quadratic Penalties
- Blog: Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
- Blog: Approximate Well-Supported Nash Equilibria Below Two-Thirds
- Blog: On tightness of Tsaknakis-Spirakis descent methods for approximate Nash equilibria
- Blog: On oblivious PTAS's for nash equilibrium
- Blog: An Improved Quasi-Polynomial Algorithm for Approximate Well-Supported Nash Equilibria
- Blog: Lipschitz Continuity and Approximate Equilibria
- Blog: Well-Supported versus Approximate Nash Equilibria: Query Complexity of Large Games
- Blog: Graphical Models for Game Theory
- Blog: Computing Nash Equilibria: Approximation and Smoothed Complexity
- Blog: On the Approximation Performance of Fictitious Play in Finite Games
- Blog: Approximate Well-supported Nash Equilibria Below Two-thirds
- Blog: On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies
- Blog: Exchangeable equilibria contradict exactness of the\n Papadimitriou-Roughgarden algorithm
- Blog: Approximate Well-supported Nash Equilibria below Two-thirds
- Blog: Finding equilibria in large sequential games of imperfect information
- Blog: Constant Rank Bimatrix Games are PPAD-hard
- Blog: Inapproximability Results for Approximate Nash Equilibria
- Blog: Algorithms and complexity for computing Nash equilibria in adversarial team games
- Blog: Budget Allocation Problem with Multiple Advertisers: A Game Theoretic View
- Blog: Computational Complexity of Approximate Nash Equilibrium in Large Games
- Blog: On the Complexity of Nash Equilibria in Anonymous Games
- Blog: The Query Complexity of Correlated Equilibria
- Blog: Finding approximate Nash equilibria of bimatrix games via payoff queries
- Blog: Distributed Methods for Computing Approximate Equilibria
- Blog: Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
- Blog: Pure-Circuit: Tight Inapproximability for PPAD
- Blog: Approximate Equilibria in Games with Few Players
- Blog: Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games
- Blog: Computing Nash Equilibrium in Wireless Ad Hoc Networks: A Simulation-Based Approach
- Blog: Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure
- Blog: On the Stability of Learning in Network Games with Many Players
- Blog: On the Existence of Low-Rank Explanations for Mixed Strategy Behavior
- Blog: An Empirical Study of Finding Approximate Equilibria in Bimatrix Games
- Blog: Learning Equilibria of Simulation-Based Games
- Blog: Limit-Computable Grains of Truth for Arbitrary Computable Extensive-Form (Un)Known Games
- Blog: On the Approximation Performance of Fictitious Play in Finite Games
- Blog: Efficient Nash Computation in Large Population Games with Bounded Influence
- Blog: Receding Horizon Games for Modeling Competitive Supply Chains⋆
- Blog: On Oblivious PTAS's for Nash Equilibrium
- Blog: Tight Inapproximability of Nash Equilibria in Public Goods Games
- Blog: Learning to Play No-Press Diplomacy with Best Response Policy Iteration
- Blog: Methods for finding leader-follower equilibria with multiple followers
- Blog: Near-optimal network design with selfish agents
- Blog: Approximate Pure Nash Equilibria in Weighted Congestion Games: Existence, Efficient Computation, and Structure
- Blog: Digraph k-Coloring Games: New Algorithms and Experiments
- Blog: Computing Constrained Approximate Equilibria in Polymatrix Games
- Blog: Safe and Robust Subgame Exploitation in Imperfect Information Games
- Blog: Learning to Give Checkable Answers with Prover-Verifier Games
- Blog: Playing Anonymous Games using Simple Strategies
- Blog: Computing Stackelberg Equilibria of Large General-Sum Games
- Blog: Geometric Structure and Polynomial-time Algorithm of Game Equilibria
- Blog: Optimal Rhode Island Hold'em Poker
- Blog: Learning equilibria of games via payoff queries
- Blog: Ranking games that have competitiveness-based strategies
- Blog: Learning Sparse Polymatrix Games in Polynomial Time and Sample Complexity
- Blog: Networked Anti-coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence
- Blog: Robust Stackelberg Equilibria
- Blog: The Complexity of Infinite-Horizon General-Sum Stochastic Games
Showing 60 of 153 papers.
History & citation
Current · Permanent link
Cite this direction
Latest version (a living page):
@misc{lacuna_ppad_completeness_computational_intracta_29bd1c76,
title = {PPAD-completeness (computational intractability of exact equilibria)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/ppad-completeness-computational-intractability-of-exact-equilibria/rdr_29bd1c762bb048328192fc72a477d325},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}This exact version (version 2, frozen text):
@misc{lacuna_ppad_completeness_computational_intracta_29bd1c76_v2,
title = {PPAD-completeness (computational intractability of exact equilibria)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/ppad-completeness-computational-intractability-of-exact-equilibria/rdr_29bd1c762bb048328192fc72a477d325/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}