Bounds for the Query Complexity of Approximate Equilibria

Paul Goldberg, Aaron Roth

[ECCC]

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