Logarithmic query complexity for approximate Nash computation in large games
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...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Springer, Berlin, Heidelberg
2016
|
| _version_ | 1826258334231035904 |
|---|---|
| author | Goldberg, P Marmolejo Cossio, F Wu, Z |
| author_facet | Goldberg, P Marmolejo Cossio, F Wu, Z |
| author_sort | Goldberg, P |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T18:32:21Z |
| format | Conference item |
| id | oxford-uuid:0a1744a2-6139-4c87-a408-5452f764dcc8 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:32:21Z |
| publishDate | 2016 |
| publisher | Springer, Berlin, Heidelberg |
| record_format | dspace |
| spelling | oxford-uuid:0a1744a2-6139-4c87-a408-5452f764dcc82022-03-26T09:21:53ZLogarithmic query complexity for approximate Nash computation in large gamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:0a1744a2-6139-4c87-a408-5452f764dcc8Symplectic Elements at OxfordSpringer, Berlin, Heidelberg2016Goldberg, PMarmolejo Cossio, FWu, ZWe 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. |
| spellingShingle | Goldberg, P Marmolejo Cossio, F Wu, Z Logarithmic query complexity for approximate Nash computation in large games |
| title | Logarithmic query complexity for approximate Nash computation in large games |
| title_full | Logarithmic query complexity for approximate Nash computation in large games |
| title_fullStr | Logarithmic query complexity for approximate Nash computation in large games |
| title_full_unstemmed | Logarithmic query complexity for approximate Nash computation in large games |
| title_short | Logarithmic query complexity for approximate Nash computation in large games |
| title_sort | logarithmic query complexity for approximate nash computation in large games |
| work_keys_str_mv | AT goldbergp logarithmicquerycomplexityforapproximatenashcomputationinlargegames AT marmolejocossiof logarithmicquerycomplexityforapproximatenashcomputationinlargegames AT wuz logarithmicquerycomplexityforapproximatenashcomputationinlargegames |