Logarithmic query complexity for approximate Nash computation in large games

DOI10.1007/S00224-018-9851-8MaRDI QIDQ1733380zbMATH OpenOpenAlexFDO

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

Publication date 21 March 2019

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

Copyright license Creative Commons Attribution 4.0 International

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

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

Recommendations

• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Query complexity of approximate Nash equilibria
• Query complexity of approximate nash equilibria
• Query complexity of approximate equilibria in anonymous games

Cites work

• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Best-reply dynamics in large binary-choice anonymous games
• Global Nash convergence of Foster and Young's regret testing
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Large Robust Games
• Learning by trial and error
• Learning equilibria of games via payoff queries
• Lipschitz games
• Mechanism design in large games: incentives and privacy (extended abstract)
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate nash equilibria
• The query complexity of correlated equilibria

Cited in

(9)

• Logarithmic Query Complexity for Approximate Nash Computation in Large Games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Query complexity of approximate Nash equilibria
• Lower bounds for the query complexity of equilibria in Lipschitz games
• PPAD-complete pure approximate Nash equilibria in Lipschitz games
• Query complexity of approximate nash equilibria
• Optimally Deceiving a Learning Leader in Stackelberg Games
• PPAD-complete approximate pure Nash equilibria in Lipschitz games
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)

This page was built for publication: Logarithmic query complexity for approximate Nash computation in large games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1733380)