  A recent body of experimental literature has studied 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
bimatrix and graphical games. Our focus is on 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.
