Query complexity of approximate equilibria in anonymous games

DOI10.1016/J.JCSS.2017.07.002MaRDI QIDQ2403236zbMATH OpenOpenAlexFDO

Authors Paul W. Goldberg, Stefano Turchetta

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

zbMATH Keywords

algorithmscomputational complexitygame theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Approximation algorithms (68W25) Noncooperative games (91A10)

Abstract: We study the computation of equilibria of anonymous games, via algorithms that may proceed via a sequence of adaptive queries to the game's payoff function, assumed to be unknown initially. The general topic we consider is emph{query complexity}, that is, how many queries are necessary or sufficient to compute an exact or approximate Nash equilibrium. We show that exact equilibria cannot be found via query-efficient algorithms. We also give an example of a 2-strategy, 3-player anonymous game that does not have any exact Nash equilibrium in rational numbers. However, more positive query-complexity bounds are attainable if either further symmetries of the utility functions are assumed or we focus on approximate equilibria. We investigate four sub-classes of anonymous games previously considered by cite{bfh09, dp14}. Our main result is a new randomized query-efficient algorithm that finds a $O(n^{-1/4})$-approximate Nash equilibrium querying $ildeO(n^{3/2})$ payoffs and runs in time $ildeO(n^{3/2})$. This improves on the running time of pre-existing algorithms for approximate equilibria of anonymous games, and is the first one to obtain an inverse polynomial approximation in poly-time. We also show how this can be utilized as an efficient polynomial-time approximation scheme (PTAS). Furthermore, we prove that $Omega(nlogn)$ payoffs must be queried in order to find any $epsilon$-well-supported Nash equilibrium, even by randomized algorithms.

Recommendations

• Query complexity of approximate equilibria in anonymous games
• Approximate Nash equilibria in anonymous games
• Playing anonymous games using simple strategies
• On the complexity of Nash equilibria in anonymous games
• An Efficient PTAS for Two-Strategy Anonymous Games

Cites work

• A size-free CLT for Poisson multinomials and its applications
• An Efficient PTAS for Two-Strategy Anonymous Games
• Anonymous games with binary actions
• Approximate Nash equilibria in anonymous games
• Best-reply dynamics in large binary-choice anonymous games
• Characterization of pure strategy equilibria infinite anonymous games
• Large Robust Games
• Learning equilibria of games via payoff queries
• Lipschitz games
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Multiagent Learning in Large Anonymous Games
• On computing the distribution function for the Poisson binomial distribution
• On oblivious PTAS's for nash equilibrium
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of Nash equilibria in anonymous games
• On the deterministic complexity of searching local maxima
• Playing anonymous games using simple strategies
• Query complexity of approximate nash equilibria
• Settling the complexity of computing two-player Nash equilibria
• Sparse covers for sums of indicators
• Symmetries and the complexity of pure Nash equilibrium
• The complexity of computing a Nash equilibrium
• The Fourier transform of Poisson multinomial distributions and its algorithmic applications
• Tight bounds for randomized and quantum local search

Cited in

(17)

• The Lipschitz constant of perturbed anonymous games
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Approximate Nash equilibria in anonymous games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• On the complexity of Nash equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• Computing Equilibria in Large Games We Play
• Playing anonymous games using simple strategies
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• Optimally Deceiving a Learning Leader in Stackelberg Games
• Query complexity of approximate nash equilibria
• An Efficient PTAS for Two-Strategy Anonymous Games
• Learning equilibria of games via payoff queries
• PPAD-complete approximate pure Nash equilibria in Lipschitz games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• PPAD-complete pure approximate Nash equilibria in Lipschitz games

This page was built for publication: Query complexity of approximate equilibria in anonymous games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403236)