Logarithmic query complexity for approximate Nash computation in large games

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

doi:10.1007/978-3-662-53354-3_1

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 proceeding › Conference contribution

1 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings
Editors	Martin Gairing, Rahul Savani
Publisher	Springer Verlag
Pages	3-14
Number of pages	12
ISBN (Print)	9783662533536
DOIs	https://doi.org/10.1007/978-3-662-53354-3_1
State	Published - 2016
Externally published	Yes
Event	9th International Symposium on Algorithmic Game Theory, SAGT 2016 - Liverpool, United Kingdom Duration: Sep 19 2016 → Sep 21 2016

Publication series

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

Other

Other	9th International Symposium on Algorithmic Game Theory, SAGT 2016
Country/Territory	United Kingdom
City	Liverpool
Period	9/19/16 → 9/21/16

Bibliographical note

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2016.

Publisher link

10.1007/978-3-662-53354-3_1

Find It

Find It at U of M Libraries

Cite this

Goldberg, P. W., Cossío, F. J. M., & Wu, Z. S. (2016). Logarithmic query complexity for approximate Nash computation in large games. In M. Gairing, & R. Savani (Eds.), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings (pp. 3-14). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9928 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-662-53354-3_1

Logarithmic query complexity for approximate Nash computation in large games. / Goldberg, Paul W.; Cossío, Francisco J.Marmolejo; Wu, Zhiwei Steven.
Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. ed. / Martin Gairing; Rahul Savani. Springer Verlag, 2016. p. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9928 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Goldberg, PW, Cossío, FJM & Wu, ZS 2016, Logarithmic query complexity for approximate Nash computation in large games. in M Gairing & R Savani (eds), Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9928 LNCS, Springer Verlag, pp. 3-14, 9th International Symposium on Algorithmic Game Theory, SAGT 2016, Liverpool, United Kingdom, 9/19/16. https://doi.org/10.1007/978-3-662-53354-3_1

Goldberg PW, Cossío FJM, Wu ZS. Logarithmic query complexity for approximate Nash computation in large games. In Gairing M, Savani R, editors, Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. Springer Verlag. 2016. p. 3-14. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-53354-3_1

Goldberg, Paul W. ; Cossío, Francisco J.Marmolejo ; Wu, Zhiwei Steven. / Logarithmic query complexity for approximate Nash computation in large games. Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings. editor / Martin Gairing ; Rahul Savani. Springer Verlag, 2016. pp. 3-14 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5557166c582246168f5c844fa7ec99ae,

title = "Logarithmic query complexity for approximate Nash computation in large games",

abstract = "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{\textquoteright}s utility is greatly affected by any other individual player{\textquoteright}s actions. In this paper, we assume that a player can change another player{\textquoteright}s payoff by at most 1/n by changing her strategy. We study algorithms having query access to the game{\textquoteright}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{\textquoteright} 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.",

author = "Goldberg, \{Paul W.\} and Coss{\'i}o, \{Francisco J.Marmolejo\} and Wu, \{Zhiwei Steven\}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2016.; 9th International Symposium on Algorithmic Game Theory, SAGT 2016 ; Conference date: 19-09-2016 Through 21-09-2016",

year = "2016",

doi = "10.1007/978-3-662-53354-3\_1",

language = "English (US)",

isbn = "9783662533536",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "3--14",

editor = "Martin Gairing and Rahul Savani",

booktitle = "Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings",

}

TY - GEN

T1 - Logarithmic query complexity for approximate Nash computation in large games

AU - Goldberg, Paul W.

AU - Cossío, Francisco J.Marmolejo

AU - Wu, Zhiwei Steven

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84988014310

UR - https://www.scopus.com/pages/publications/84988014310#tab=citedBy

U2 - 10.1007/978-3-662-53354-3_1

DO - 10.1007/978-3-662-53354-3_1

M3 - Conference contribution

AN - SCOPUS:84988014310

SN - 9783662533536

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 14

BT - Algorithmic Game Theory - 9th International Symposium, SAGT 2016, Proceedings

A2 - Gairing, Martin

A2 - Savani, Rahul

PB - Springer Verlag

T2 - 9th International Symposium on Algorithmic Game Theory, SAGT 2016

Y2 - 19 September 2016 through 21 September 2016

ER -

Logarithmic query complexity for approximate Nash computation in large games

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this