Query complexity of approximate Nash equilibria

DOI10.1145/2908734MaRDI QIDQ3177813zbMATHOpenAlexFDO

Authors Yakov Babichenko

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2908734

zbMATH Keywords

rate of convergenceadaptive dynamicsquery complexityapproximate Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Recommendations

• Query complexity of approximate nash equilibria
• scientific article; zbMATH DE number 6866347
• Query complexity of approximate equilibria in anonymous games
• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Logarithmic query complexity for approximate Nash computation in large games

Cited in

(15)

• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• 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
• An abstraction-refinement methodology for reasoning about network games
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Query complexity of approximate nash equilibria
• Optimally Deceiving a Learning Leader in Stackelberg Games
• Query complexity of approximate equilibria in anonymous games
• Learning convex partitions and computing game-theoretic equilibria from best response queries
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

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 Q3177813)