论文标题
朝着纳什平衡发展的动态
A dynamic that evolves toward a Nash equilibrium
论文作者
论文摘要
在本文中，我们研究了基于对冲的繁殖权重动态，这是一种众所周知的理论机器学习和算法游戏理论的算法。已知迭代性篱笆生成的经验平均值（算术平均值）在零和游戏中达到最小值。我们概括了这一结果，以表明经验平均值的加权版本在对称bimatrix游戏类别中收敛到平衡，以降低学习率参数。我们的动态是显示出在不假定收益结构单调或存在潜在函数的情况下向NASH均衡进化的第一个动态系统（无论是连续还是离散）。尽管我们的设置有些限制，但它也是一般的，因为对称bimatrix游戏类别捕获了PPAD类的整个计算复杂性（甚至近似于平衡）。
In this paper, we study an exponentiated multiplicative weights dynamic based on Hedge, a well-known algorithm in theoretical machine learning and algorithmic game theory. The empirical average (arithmetic mean) of the iterates Hedge generates is known to approach a minimax equilibrium in zero-sum games. We generalize that result to show that a weighted version of the empirical average converges to an equilibrium in the class of symmetric bimatrix games for a diminishing learning rate parameter. Our dynamic is the first dynamical system (whether continuous or discrete) shown to evolve toward a Nash equilibrium without assuming monotonicity of the payoff structure or that a potential function exists. Although our setting is somewhat restricted, it is also general as the class of symmetric bimatrix games captures the entire computational complexity of the PPAD class (even to approximate an equilibrium).
