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.

本文研究了基于局部知识来学习研究各种类型的博弈及其均衡求解的复杂度，探讨了计算学习模型和对于各种博弈的查询复杂度，着重研究了对称网络拥塞博弈，并通过仅查询少量的纯策略来学习成本函数。