Query complexity of approximate nash equilibria

DOI10.1145/2591796.2591829MaRDI QIDQ5259589zbMATH OpenOpenAlexFDO

Authors Yakov Babichenko

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.6686

zbMATH Keywords

rate of convergenceadaptive dynamicsgame theorycomplexityfixed pointquery complexityapproximate Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) (n)-person games, (n>2) (91A06)

Abstract: We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players $n$. Our main result states that for $n$-player binary-action games and for constant $varepsilon$, the query complexity of an $varepsilon$-well-supported Nash equilibrium is exponential in $n$. One of the consequences of this result is an exponential lower bound on the rate of convergence of adaptive dynamics to approxiamte Nash equilibrium.

Recommendations

• Query complexity of approximate Nash equilibria
• Logarithmic query complexity for approximate Nash computation in large games
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• scientific article; zbMATH DE number 6866347
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Lower bounds for the query complexity of equilibria in Lipschitz games

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(14)

• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Inapproximability of Nash equilibrium
• Empirical distribution of equilibrium play and its testing application
• Learning equilibria of games via payoff queries
• Logarithmic query complexity for approximate Nash computation in large games
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate Nash equilibria
• ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Query complexity of approximate equilibria in anonymous games
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• The query complexity of correlated equilibria
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Query complexity of approximate nash equilibria

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