2013/02/13 by John Fearnley, Martin Gairing, Fearnley, John +5 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1302.3116
openalex publication_date 2013/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.