Logarithmic Query Complexity for Approximate Nash Computation in Large Games

DOI10.1007/978-3-662-53354-3_1MaRDI QIDQ2819443zbMATH OpenOpenAlexFDO

Authors 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, https://ora.ox.ac.uk/objects/uuid:2f9dc1ef-0d83-42b1-8034-c0d54de02835

zbMATH Keywords

large gameslogarithmic query complexityNash equilibrium computation

Mathematics Subject Classification ID

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

Abstract: We investigate the problem of equilibrium computation for "large" $n$-player games. Large games have a Lipschitz-type property that no single player's utility is greatly affected by any other individual player's actions. In this paper, we mostly focus on the case where any change of strategy by a player causes other players' payoffs to change by at most $frac1n$. We study algorithms having query access to the game's payoff function, aiming to find $epsilon$-Nash equilibria. We seek algorithms that obtain $epsilon$ as small as possible, in time polynomial in $n$. Our main result is a randomised algorithm that achieves $epsilon$ approaching $frac18$ for 2-strategy games in a {em completely uncoupled} setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players' payoffs/actions. $O(logn)$ rounds/queries are required. We also show how to obtain a slight improvement over $frac18$, by introducing a small amount of communication between the players. Finally, we give extension of our results to large games with more than two strategies per player, and alternative largeness parameters.

Recommendations

• Logarithmic query complexity for approximate Nash computation in large games
• Query complexity of approximate Nash equilibria
• Query complexity of approximate nash equilibria
• scientific article; zbMATH DE number 6866347
• Query complexity of approximate equilibria in anonymous games
• Query complexity of approximate equilibria in anonymous games
• On the complexity of approximating a Nash equilibrium
• scientific article; zbMATH DE number 6783488
• The Computational Complexity of Nash Equilibria in Concisely Represented Games
• Lower bounds for the query complexity of equilibria in Lipschitz 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

Cited in

(8)

• Logarithmic query complexity for approximate Nash computation in large games
• Query complexity of approximate equilibria in anonymous games
• Lower bounds for the query complexity of equilibria in Lipschitz games
• Query complexity of approximate Nash equilibria
• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• Query complexity of 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: 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 Q2819443)