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

adaptive dynamicsapproximate Nash equilibriumquery complexityrate of convergence

Mathematics Subject Classification ID

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

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

(18)

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