Logarithmic query complexity for approximate Nash computation in large games

DOI10.1007/s00224-018-9851-8zbMath1411.91052OpenAlexW2511655436MaRDI QIDQ1733380

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

Publication date: 21 March 2019

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-018-9851-8

zbMATH Keywords

game theoryequilibrium computationmulti-player gamesuncoupled dynamicsLipschitz games

Mathematics Subject Classification ID

Games with infinitely many players (91A07) Signaling and communication in game theory (91A28) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Spaces of games (91A70)

Related Items (5)

Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ PPAD-complete approximate pure Nash equilibria in Lipschitz games ⋮ PPAD-complete pure approximate Nash equilibria in Lipschitz games ⋮ Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ Optimally Deceiving a Learning Leader in Stackelberg Games

Cites Work

• Unnamed Item
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Learning by trial and error
• The query complexity of correlated equilibria
• 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