Logarithmic query complexity for approximate Nash computation in large games

Conference item

We investigate the problem of equilibrium computation for “large” n-player games where each player has two pure strategies. 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 assume that a player can change another player’s payoff by at most 1 n by changing her strategy. We study algorithms having query access to the game’s payoff function, aiming to find ε-Nash equilibria. We seek algorithms that obtain ε as small as possible, in time polynomial in n. Our main result is a randomised algorithm that achieves ε approaching 1 8 in a completely uncoupled setting, where each player observes her own payoff to a query, and adjusts her behaviour independently of other players’ payoffs/actions. O(log n) rounds/queries are required. We also show how to obtain a slight improvement over 1 8 , by introducing a small amount of communication between the players.

Authors: Goldberg, P; Marmolejo Cossio, F; Wu, Z

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer, Berlin, Heidelberg
• Host title: International Symposium on Algorithmic Game Theory: SAGT 2016: Algorithmic Game Theory
• Volume: 9928
• Pages: 3-14
• Series: Lecture Notes in Computer Science
• Publication date: 2016-01-01
• Acceptance date: 2016-07-01
• DOI: 10.1007/978-3-662-53354-3_1
• ISSN: 0302-9743
• ISBN: 9783662533536