Bounds for the query complexity of approximate equilibria
We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1797108925210820608 |
|---|---|
| author | Goldberg, PW Roth, A |
| author_facet | Goldberg, PW Roth, A |
| author_sort | Goldberg, PW |
| collection | OXFORD |
| description | We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player’s behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium. Finally, we give a query-efficient reduction from the problem of computing an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient. |
| first_indexed | 2024-03-07T07:34:49Z |
| format | Journal article |
| id | oxford-uuid:61b9c3b3-ae74-4e77-96d7-4f0ad91d04a4 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:34:49Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:61b9c3b3-ae74-4e77-96d7-4f0ad91d04a42023-03-03T13:29:19ZBounds for the query complexity of approximate equilibriaJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:61b9c3b3-ae74-4e77-96d7-4f0ad91d04a4EnglishSymplectic Elements at OxfordAssociation for Computing Machinery2016Goldberg, PWRoth, AWe analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player’s behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium. Finally, we give a query-efficient reduction from the problem of computing an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient. |
| spellingShingle | Goldberg, PW Roth, A Bounds for the query complexity of approximate equilibria |
| title | Bounds for the query complexity of approximate equilibria |
| title_full | Bounds for the query complexity of approximate equilibria |
| title_fullStr | Bounds for the query complexity of approximate equilibria |
| title_full_unstemmed | Bounds for the query complexity of approximate equilibria |
| title_short | Bounds for the query complexity of approximate equilibria |
| title_sort | bounds for the query complexity of approximate equilibria |
| work_keys_str_mv | AT goldbergpw boundsforthequerycomplexityofapproximateequilibria AT rotha boundsforthequerycomplexityofapproximateequilibria |