Query complexity of approximate equilibria in anonymous games
From MaRDI portal
Publication:2403236
DOI10.1016/j.jcss.2017.07.002zbMath1376.91018arXiv1412.6455OpenAlexW2740520762MaRDI QIDQ2403236
Stefano Turchetta, Paul W. Goldberg
Publication date: 15 September 2017
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.6455
Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (7)
The Lipschitz constant of perturbed anonymous games ⋮ Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ Learning convex partitions and computing game-theoretic equilibria from best response queries ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ Optimally Deceiving a Learning Leader in Stackelberg Games
Cites Work
- Unnamed Item
- On computing the distribution function for the Poisson binomial distribution
- Sparse covers for sums of indicators
- Symmetries and the complexity of pure Nash equilibrium
- Anonymous games with binary actions
- Characterization of pure strategy equilibria infinite anonymous games
- On the deterministic complexity of searching local maxima
- Approximate Nash equilibria in anonymous games
- Best-reply dynamics in large binary-choice anonymous games
- Logarithmic Query Complexity for Approximate Nash Computation in Large Games
- On the Complexity of Nash Equilibria in Anonymous Games
- Multiagent Learning in Large Anonymous Games
- On the Complexity of Nash Equilibria and Other Fixed Points
- Settling the complexity of computing two-player Nash equilibria
- Tight Bounds for Randomized and Quantum Local Search
- Playing Anonymous Games using Simple Strategies
- Lipschitz Games
- On oblivious PTAS's for nash equilibrium
- The Complexity of Computing a Nash Equilibrium
- Query complexity of approximate nash equilibria
- The fourier transform of poisson multinomial distributions and its algorithmic applications
- A size-free CLT for poisson multinomials and its applications
- Large Robust Games
- An Efficient PTAS for Two-Strategy Anonymous Games
This page was built for publication: Query complexity of approximate equilibria in anonymous games
