Query complexity of approximate Nash equilibria

DOI10.1145/2908734MaRDI QIDQ3177813zbMATH OpenOpenAlexFDO

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
• Publication:4638112
• 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)

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