论文标题
凹面网络零和游戏中梯度方法的指数收敛
Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
论文作者
论文摘要
由生成对抗网络的激励，我们研究了凹面网络零和游戏中NASH平衡的计算，这是两人首先提出的两人零和零和游戏的多人游戏概括。扩展了先前的结果，我们表明，在此概括中保留了凸孔双玩家零和游戏的各种游戏理论属性。然后，我们概括了先前在两人零和游戏中获得的最后一次迭代收敛结果。当玩家使用梯度上升及其变体，乐观的梯度上升来更新策略时，我们会分析收敛速度，在三种环境中显示出最后的迭代收敛 - 当玩家的收益是线性的，强烈的凹入和Lipschitz的，并且强烈凹入和光滑。我们提供了支持这些理论发现的实验结果。
Motivated by Generative Adversarial Networks, we study the computation of Nash equilibrium in concave network zero-sum games (NZSGs), a multiplayer generalization of two-player zero-sum games first proposed with linear payoffs. Extending previous results, we show that various game theoretic properties of convex-concave two-player zero-sum games are preserved in this generalization. We then generalize last iterate convergence results obtained previously in two-player zero-sum games. We analyze convergence rates when players update their strategies using Gradient Ascent, and its variant, Optimistic Gradient Ascent, showing last iterate convergence in three settings -- when the payoffs of players are linear, strongly concave and Lipschitz, and strongly concave and smooth. We provide experimental results that support these theoretical findings.
