## Learning Equilibria of Games via Payoff Queries

*John Fearnley, Martin Gairing, Paul W. Goldberg, Rahul Savani*; 16(Aug):1305−1344, 2015.

### Abstract

A recent body of experimental literature has studied {\em
empirical game-theoretical analysis}, in which we have partial
knowledge of a game, consisting of observations of a subset of
the pure-strategy profiles and their associated payoffs to
players. The aim is to find an exact or approximate Nash
equilibrium of the game, based on these observations. It is
usually assumed that the strategy profiles may be chosen in an
on-line manner by the algorithm. We study a corresponding
computational learning model, and the query complexity of
learning equilibria for various classes of games. We give basic
results for exact equilibria of bimatrix and graphical games. We
then study the query complexity of approximate equilibria in
bimatrix games. Finally, we study the query complexity of exact
equilibria in symmetric network congestion games. For directed
acyclic networks, we can learn the cost functions (and hence
compute an equilibrium) while querying just a small fraction of
pure-strategy profiles. For the special case of parallel links,
we have the stronger result that an equilibrium can be
identified while only learning a small fraction of the cost
values.

[abs][pdf][bib]