ECCC-Report TR13-136https://eccc.weizmann.ac.il/report/2013/136Comments and Revisions published for TR13-136en-usFri, 27 Sep 2013 22:51:41 +0300
Paper TR13-136
| Bounds for the Query Complexity of Approximate Equilibria |
Paul Goldberg,
Aaron Roth
https://eccc.weizmann.ac.il/report/2013/136We analyze the number of payoff queries needed to compute approximate correlated equilibria. For multi-player, 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 which separates 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 \emph{verifying} an approximate well-supported Nash equilibrium to the problem of computing 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.Fri, 27 Sep 2013 22:51:41 +0300https://eccc.weizmann.ac.il/report/2013/136