On the complexity of approximating a Nash equilibrium

No abstract is available for this paper.

• Publication year

  2011

• Venue

  ACM-SIAM Symposium on Discrete Algorithms

• Publication date

  2011-01-23

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2483699.2483703
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On minmax theorems for multiplayer games

  2011cited by this paper
• On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract)

  2010cited by this paper
• Practical and Efficient Approximations of Nash Equilibria for Win-Lose Games Based on Graph Spectra

  2010cited by this paper
• On a Network Generalization of the Minmax Theorem

  2009cited by this paper
• On oblivious PTAS's for nash equilibrium

  2009cited by this paper
• How hard is it to approximate the best Nash equilibrium?

  2009cited by this paper
• A Graph Spectral Approach for Computing Approximate Nash Equilibria

  2009cited by this paper
• Progress in approximate nash equilibria

  2007cited by this paper
• Integrated Project Member of the FET Proactive Initiative Complex Systems DELIS-TR-537 An Optimization Approach for Approximate Nash Equilibria

  2007cited by this paper
• Approximating nash equilibria using small-support strategies

  2007influential reference
• New algorithms for approximate Nash equilibria in bimatrix games

  2007cited by this paper
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games

  2007cited by this paper
• The complexity of computing a Nash equilibrium

  2006cited by this paper
• Computing Nash Equilibria: Approximation and Smoothed Complexity

  2006cited by this paper
• Reducibility among equilibrium problems

  2006influential reference
• Polynomial algorithms for approximating Nash equilibria of bimatrix games

  2006cited by this paper
• A note on approximate Nash equilibria

  2006cited by this paper
• Settling the Complexity of Two-Player Nash Equilibrium

  2006cited by this paper
• On the complexity of two-player win-lose games

  2005cited by this paper
• 3-NASH is PPAD-Complete

  2005cited by this paper
• Three-Player Games Are Hard

  2005cited by this paper
• Playing large games using simple strategies

  2003cited by this paper
• Non-Cooperative Games

  2003cited by this paper
• Graphical Models for Game Theory

  2001cited by this paper
• On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

  1994cited by this paper
• Nash and correlated equilibria: Some complexity considerations

  1989cited by this paper
• private communication

  1969cited by this paper
• The Approximation of Fixed Points of a Continuous Mapping

  1967cited by this paper
• Exposition of a New Theory on the Measurement of Risk

  1954cited by this paper
• Equilibrium Points in N-Person Games.

  1950influential reference

• Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

  2025cites this paper
• Game-Theoretic Understandings of Multi-Agent Systems with Multiple Objectives

  2025cites this paper
• Convergent Q-Learning for Infinite-Horizon General-Sum Markov Games through Behavioral Economics

  2025cites this paper
• Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games

  2025influential citation
• Statistical Equilibrium of Optimistic Beliefs

  2025cites this paper
• Tractable Multi-Agent Reinforcement Learning through Behavioral Economics

  2025influential citation
• Minimal Regret Walras Equilibria for Combinatorial Markets

  2025cites this paper
• A Formal and Deployable Gaming Operation to Defend IT/OT Networks

  2025cites this paper
• "It's Time!" Toward a Human-AI Quantum Experience Design Paradigm: Reinventing the Theoretical Framework of HCI

  2024cites this paper
• Taming Equilibrium Bias in Risk-Sensitive Multi-Agent Reinforcement Learning

  2024cites this paper
• On the Decomposition of Differential Game

  2024cites this paper
• First-order (coarse) correlated equilibria in non-concave games

  2024cites this paper
• Convergence to Nash Equilibrium and No-regret Guarantee in (Markov) Potential Games

  2024cites this paper
• Nash Equilibria via Stochastic Eigendecomposition

  2024cites this paper
• Transformers as Game Players: Provable In-context Game-playing Capabilities of Pre-trained Models

  2024cites this paper
• A Survey on Self-play Methods in Reinforcement Learning

  2024cites this paper
• A survey on algorithms for Nash equilibria in finite normal-form games

  2024cites this paper
• Tractable Equilibrium Computation in Markov Games through Risk Aversion

  2024cites this paper
• The Attractor of the Replicator Dynamic in Zero-Sum Games

  2023cites this paper
• Provable Particle-based Primal-Dual Algorithm for Mixed Nash Equilibrium

  2023cites this paper
• Decentralized Robust V-learning for Solving Markov Games with Model Uncertainty

  2023cites this paper
• V-Learning - A Simple, Efficient, Decentralized Algorithm for Multiagent Reinforcement Learning

  2023cites this paper
• Smooth Nash Equilibria: Algorithms and Complexity

  2023influential citation
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium

  2023cites this paper
• How Suboptimal is Work-From-Home Security in IT/ICS Enterprises? A Strategic Organizational Theory for Managers

  2023cites this paper
• Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation

  2023cites this paper
• Algorithms and Complexity for Computing Nash Equilibria in Adversarial Team Games

  2023cites this paper
• Optimistic Mirror Descent Either Converges to Nash or to Strong Coarse Correlated Equilibria in Bimatrix Games

  2022cites this paper
• Towards the PAC Learnability of Nash Equilibrium

  2022cites this paper
• Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains via Dual Mirror Descent

  2022influential citation
• Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model

  2022cites this paper
• Pure-Circuit: Strong Inapproximability for PPAD

  2022cites this paper
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model

  2022influential citation
• Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games

  2022cites this paper
• Learning in Congestion Games with Bandit Feedback

  2022cites this paper
• Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus

  2022cites this paper
• Independent Natural Policy Gradient Methods for Potential Games: Finite-time Global Convergence with Entropy Regularization

  2022cites this paper
• Pure-Circuit: Tight Inapproximability for PPAD

  2022cites this paper
• The Complexity of Infinite-Horizon General-Sum Stochastic Games

  2022cites this paper
• Plan Better Amid Conservatism: Offline Multi-Agent Reinforcement Learning with Actor Rectification

  2021cites this paper
• Is Nash Equilibrium Approximator Learnable?

  2021cites this paper
• V-Learning - A Simple, Efficient, Decentralized Algorithm for Multiagent RL

  2021cites this paper
• Finite-Sample Analysis of Decentralized Q-Learning for Stochastic Games

  2021cites this paper
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?

  2021cites this paper
• Provable Self-Play Algorithms for Competitive Reinforcement Learning

  2020influential citation
• Navigating the Landscape of Games

  2020cites this paper
• Complexity Aspects of Fundamental Questions in Polynomial Optimization

  2020cites this paper
• The complexity of constrained min-max optimization

  2020cites this paper
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play

  2020cites this paper
• Navigating the landscape of multiplayer games

  2020cites this paper
• A GENERALIZED TRAINING APPROACH

  2019cites this paper
• Metastability of the Logit Dynamics for Asymptotically Well-Behaved Potential Games

  2019cites this paper
• Hardness of Approximation Between P and NP

  2019cites this paper
• Zero-sum polymatrix games with link uncertainty: A Dempster-Shafer theory solution

  2019cites this paper
• A Generalized Training Approach for Multiagent Learning

  2019cites this paper
• Monotonic and Non-Monotonic Solution Concepts for Generalized Circuits

  2019cites this paper
• Equilibrium Computation in Atomic Splittable Routing Games with Convex Cost Functions

  2018cites this paper
• A Graph Transduction Game for Multi-target Tracking

  2018cites this paper
• The nudge wars: A modern socialist calculation debate

  2018cites this paper
• Solving Zero-Sum Games Using Best-Response Oracles with Applications to Search Games

  2017cites this paper
• Semidefinite Programming and Nash Equilibria in Bimatrix Games

  2017cites this paper
• Multi-player Approximate Nash Equilibria

  2017influential citation
• Finding Clearing Payments in Financial Networks with Credit Default Swaps is PPAD-complete

  2017cites this paper
• Game Theory, Alive

  2017cites this paper
• The Computational Complexity of Clearing Financial Networks with Credit Default Swaps

  2017cites this paper
• Scalable Unsupervised Learning with Game Theory

  2017cites this paper
• Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

  2016cites this paper
• Twenty Lectures on Algorithmic Game Theory

  2016cites this paper
• Kimmo Berg and Mitri Kitti Equilibrium Paths in Discounted Supergames Aboa Centre for Economics

  2016cites this paper
• Computational Analysis of Intelligent Agents: Social and Strategic Settings

  2016cites this paper
• Exclusion Method for Finding Nash Equilibrium in Multiplayer Games

  2016cites this paper
• Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder

  2015cites this paper
• ETH-Hardness for Symmetric Signaling in Zero-Sum Games

  2015cites this paper
• Approximate Nash equilibria in anonymous games

  2015cites this paper
• Approximate Nash Equilibria with Near Optimal Social Welfare

  2015cites this paper
• Approximating Nash Equilibria in Tree Polymatrix Games

  2015cites this paper
• Can Almost Everybody be Almost Happy?

  2015influential citation
• Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

  2015cites this paper
• On Equilibrium Computation in Biased Games with Quadratic Penalties

  2015cites this paper
• The Complexity of Computing Equilibria

  2015cites this paper
• D ec 2 01 5 ETH-Hardness for Symmetric Signaling in Zero-Sum Games

  2015cites this paper
• ETH-Hardness for Signaling in Symmetric Zero-Sum Games

  2015cites this paper
• Automated Generation of Counterterrorism Policies Using Multiexpert Input

  2015cites this paper
• Constraint Games: Modeling and Solving Games with Constraints. (Contrainte Jeux: modélisation et Jeux Résolution avec Contraintes)

  2014cites this paper
• Computing Approximate Nash Equilibria in Polymatrix Games

  2014cites this paper
• Computational Complexity of Approximate Nash Equilibrium in Large Games

  2014cites this paper
• Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem

  2014cites this paper
• Simple approximate equilibria in large games

  2014cites this paper
• Regulating Monopolistic ISPS without Neutrality

  2014cites this paper
• Inapproximability of Nash Equilibrium

  2014cites this paper
• Equilibrium paths in discounted supergames

  2014cites this paper
• Approximating Carathéodory's Theorem and Nash Equilibria

  2014cites this paper
• Towards the Computation of a Nash Equilibrium

  2014cites this paper
• Complexité des dynamiques de jeux

  2013cites this paper
• Congestion and Its Role in Network Equilibrium

  2012cites this paper
• Metastability of Potential Games

  2012cites this paper
• The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games

  2012cites this paper
• Metastability of Asymptotically Well-Behaved Potential Games

  2012cites this paper
• Nash equilibria, gale strings, and perfect matchings

  2011influential citation
• Graph Transduction as a Noncooperative Game

  2011cites this paper