Query complexity of approximate nash equilibria

DOI10.1145/2591796.2591829zbMATH Open1315.91003arXiv1306.6686OpenAlexW1981247840MaRDI QIDQ5259589FDOQ5259589

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)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (10)

• Title not available (Why is that?)
• The query complexity of correlated equilibria
• Logarithmic query complexity for approximate Nash computation in large games
• Communication complexity of approximate Nash equilibria
• Query Complexity of Approximate Equilibria in Anonymous Games
• Query complexity of approximate equilibria in anonymous games
• Inapproximability of Nash Equilibrium
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria

Uses Software

• SuLQ

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the Complexity of Approximating a Nash Equilibrium 👍 👎
• The Computational Complexity of Nash Equilibria in Concisely Represented Games 👍 👎
• Query Complexity of Approximate Nash Equilibria 👍 👎
• Logarithmic query complexity for approximate Nash computation in large games 👍 👎
• Query Complexity of Approximate Equilibria in Anonymous Games 👍 👎
• Query complexity of approximate equilibria in anonymous games 👍 👎
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games 👍 👎
• Lower bounds for the query complexity of equilibria in Lipschitz games 👍 👎

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)