Logarithmic query complexity for approximate Nash computation in large games

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings
EditorsMartin Gairing, Rahul Savani
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783662533536
StatePublished - 2016
Externally publishedYes
Event9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom
Duration: Sep 19 2016Sep 21 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9928 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Symposium on Algorithmic Game Theory, SAGT 2016
Country/TerritoryUnited Kingdom

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.


Dive into the research topics of 'Logarithmic query complexity for approximate Nash computation in large games'. Together they form a unique fingerprint.

Cite this