Logarithmic Query Complexity for Approximate Nash Computation in Large Games

DOI10.1007/978-3-662-53354-3_1zbMath1403.91032arXiv1610.08906OpenAlexW2906123463MaRDI QIDQ2819443

Paul W. Goldberg, Francisco J. Marmolejo-Cossío, Zhiwei Steven Wu

Publication date: 29 September 2016

Published in: Algorithmic Game Theory (Search for Journal in Brave)

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

zbMATH Keywords

large gamesNash equilibrium computationlogarithmic query complexity

Mathematics Subject Classification ID

Games with infinitely many players (91A07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Query complexity of approximate equilibria in anonymous games

Cites Work

• Unnamed Item
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Learning by trial and error
• Global Nash convergence of Foster and Young's regret testing
• Best-reply dynamics in large binary-choice anonymous games
• Mechanism design in large games
• Query Complexity of Approximate Equilibria in Anonymous Games
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Lipschitz Games
• Query complexity of approximate nash equilibria
• Large Robust Games

This page was built for publication: Logarithmic Query Complexity for Approximate Nash Computation in Large Games