Learning equilibria of games via payoff queries
Learning equilibria of games via payoff queries
复制标题
DOI：
10.1145/2482540.2482558
复制
发表时间：
2013-02
期刊：
影响因子：
--
通讯作者：
John Fearnley;Martin Gairing;P. Goldberg;Rahul Savani
中科院分区：
文献类型：
--
作者：
John Fearnley;Martin Gairing;P. Goldberg;Rahul Savani
最近的一系列实验文献研究了经验游戏理论分析，其中我们对游戏有部分知识，包括观察到纯粹策略概况的一部分及其对玩家的相关收益。目的是根据这些观察结果找到游戏的精确或近似纳什均衡。通常假定可以通过算法以在线方式选择策略概况。我们研究了相应的计算学习模型，以及各类游戏学习平衡的查询复杂性。我们为Bimatrix和图形游戏提供了基本结果。我们的重点是对称网络拥堵游戏。对于定向的无环网络，我们可以学习成本函数（因此计算平衡），同时仅查询一小部分的纯构成概况。对于平行链接的特殊情况，我们的结果更强，即只能学习成本值的一小部分，可以确定平衡。
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.