Paper Info
Title
Learning equilibria of games via payoff queries
Abstract
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 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.
Year
DOI
Venue
2013
10.1145/2482540.2482558
Journal of Machine Learning Research
Keywords
DocType
Volume
payoff query,acyclic network,approximate nash equilibrium,small fraction,symmetric network congestion game,associated payoff,graphical game,cost function,basic result,cost value,pure-strategy profile
Conference
abs/1302.3116
ISBN
Citations 
PageRank 
978-1-4503-1962-1
11
0.61
References 
Authors
32
4
Name
Order
Citations
PageRank
John Fearnley113417.49
Martin Gairing263347.14
Paul W. Goldberg375998.26
Rahul Savani424330.09