Query complexity of approximate nash equilibria

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n.

• Publication year

  2013

• Venue

  Symposium on the Theory of Computing

• Publication date

  2013-06-27

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2591796.2591829arXiv 1306.6686
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Communication Complexity

  2016cited by this paper
• Query Complexity of Approximate Nash Equilibria

  2016influential reference
• Inapproximability of Nash Equilibrium

  2014influential reference
• Simple approximate equilibria in large games

  2014influential reference
• Bounds for the query complexity of approximate equilibria

  2014influential reference
• Learning equilibria of games via payoff queries

  2013cited by this paper
• Approximate Nash Equilibria via Sampling

  2013influential reference
• Query Complexity of Correlated Equilibrium

  2013cited by this paper
• Polynomial-time computation of exact correlated equilibrium in compact games

  2010cited by this paper
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures

  2010influential reference
• Population Games And Evolutionary Dynamics

  2010cited by this paper
• Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games

  2008influential reference
• Settling the Complexity of Two-Player Nash Equilibrium

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

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

  2006influential reference
• Adaptive Heuristics

  2005cited by this paper
• Computing correlated equilibria in multi-player games

  2005cited by this paper
• Communication complexity as a lower bound for learning in games

  2004influential reference
• Playing large games using simple strategies

  2003cited by this paper
• Uncoupled Dynamics Do Not Lead to Nash Equilibrium

  2003cited by this paper
• A simple adaptive procedure leading to correlated equilibrium

  2000cited by this paper
• Communication Complexity

  1997cited by this paper
• Probability Inequalities for Sums of Bounded Random Variables

  1994cited by this paper
• The Statistical Mechanics of Strategic Interaction

  1993cited by this paper
• Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions

  1990cited by this paper
• The weighted majority algorithm

  1989cited by this paper
• Exponential lower bounds for finding Brouwer fixed points

  1987influential reference
• Centre De Referència En Economia Analítica Barcelona Economics Working Paper Series Working Paper Nº 174 Stochastic Uncoupled Dynamics and Nash Equilibrium

  year unknowncited by this paper

• The Complexity of Min-Max Optimization with Product Constraints

  2026cites this paper
• Expected Variational Inequalities

  2025cites this paper
• Logarithmic Comparison-Based Query Complexity for Fair Division of Indivisible Goods

  2024cites this paper
• Query-Efficient Algorithms to Find the Unique Nash Equilibrium in a Two-Player Zero-Sum Matrix Game

  2023cites this paper
• Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization

  2023cites this paper
• Social Optimum Equilibrium Selection for Distributed Multi-Agent Optimization

  2023cites this paper
• Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games

  2023cites this paper
• The Computational Complexity of Equilibria with Strategic Constraints

  2023cites this paper
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games

  2023cites this paper
• On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games

  2023influential citation
• An Active Learning Method for Solving Competitive Multiagent Decision-Making and Control Problems

  2022cites this paper
• A learning-based approach to multi-agent decision-making

  2022cites this paper
• On Last-Iterate Convergence Beyond Zero-Sum Games

  2022cites this paper
• Lower Bounds for the Query Complexity of Equilibria in Lipschitz Games

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

  2021cites this paper
• Sample-based Approximation of Nash in Large Many-Player Games via Gradient Descent

  2021cites this paper
• Sample Complexity of Solving Non-Cooperative Games

  2020cites this paper
• Communication complexity of Nash equilibrium in potential games (extended abstract)

  2020cites this paper
• Optimally Deceiving a Learning Leader in Stackelberg Games

  2020cites this paper
• Complexity Theory, Game Theory, and Economics: The Barbados Lectures

  2020cites this paper
• Smooth markets: A basic mechanism for organizing gradient-based learners

  2020cites this paper
• Learning Equilibria of Simulation-Based Games

  2019cites this paper
• Lecture 2 : Symmetry Gap Theorem & Hardness of Finding Fixed Point

  2019cites this paper
• On Communication Complexity of Fixed Point Computation

  2019cites this paper
• Optimizing the strategy of activities using numerical methods for determining equilibrium

  2019cites this paper
• Complexity Theory, Game Theory, and Economics

  2018cites this paper
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

  2018cites this paper
• 2 5 D ec 2 01 7 The Query Complexity of Correlated Equilibria ∗ †

  2018cites this paper
• Smoothed Efficient Algorithms and Reductions for Network Coordination Games

  2018cites this paper
• ∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria

  2018cites this paper
• Learning Game-Theoretic Equilibria Via Query Protocols

  2017cites this paper
• Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria

  2017cites this paper
• Identify the Nash Equilibrium in Static Games with Random Payoffs

  2017cites this paper
• Algorithmic information structure design: a survey

  2017cites this paper
• Ham Sandwich is Equivalent to Borsuk-Ulam

  2017cites this paper
• Communication complexity of approximate Nash equilibria

  2016cites this paper
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games

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

  2016cites this paper
• On the Communication Complexity of Approximate Fixed Points

  2016cites this paper
• Bounds for the Query Complexity of Approximate Equilibria

  2016influential citation
• Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

  2016influential citation
• Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games

  2015influential citation
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria

  2015cites this paper
• STOCHASTIC LEARNING DYNAMICS AND SPEED OF CONVERGENCE IN POPULATION GAMES BY ITAI ARIELI

  2015cites this paper
• Simple approximate equilibria in large games

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

  2014influential citation
• Query complexity of approximate equilibria in anonymous games

  2014cites this paper
• Inapproximability of Nash Equilibrium

  2014influential citation
• Bounds for the query complexity of approximate equilibria

  2014cites this paper
• The Query Complexity of Correlated Equilibria

  2013cites this paper
• Finding approximate nash equilibria of bimatrix games via payoff queries

  2013cites this paper
• Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

  2013cites this paper
• Learning equilibria of games via payoff queries

  2013cites this paper
• Approximate Nash Equilibria via Sampling

  2013cites this paper
• Query Complexity of Correlated Equilibrium

  2013influential citation