论文标题
lipschitz游戏中的ppad-complete纯近似nash均衡
PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz Games
论文作者
论文摘要
Lipschitz游戏，其中有一个限制$λ$（游戏的Lipschitz值），即当玩家的回报可能会发生多大变化时，大约在10年前，Azrieli和Shmaya引入了。他们通过概率方法表明，$ n $ - 玩家Lipschitz游戏每位玩家具有$ M $策略的游戏具有纯$ε$ -Approximate Nash Equilibria，以$ε\geqλ\ sqrt {8n \ log（2mn）} $。在这里，我们为相应的计算问题提供了第一个硬度结果，即使对于简单的Lipschitz游戏（Lipschitz polymatrix游戏），也可以找到纯$ε$ -Approximate平衡是PPAD-COMPLETE，对于合适的成对的值$（ε（n），λ（N），λ（N））$。该结果的新颖特征包括PPAD硬度的证明（在其中应用了无限制的Polymatrix游戏中的人口游戏）和PPAD遏制证明（通过使选择混合游戏的纯平衡选择）。实际上，我们的方法意味着对于任何类别的Lipschitz游戏，PPAD都可以遏制，在这些游戏中，可以确定地计算出混合策略概况的收益。
Lipschitz games, in which there is a limit $λ$ (the Lipschitz value of the game) on how much a player's payoffs may change when some other player deviates, were introduced about 10 years ago by Azrieli and Shmaya. They showed via the probabilistic method that $n$-player Lipschitz games with $m$ strategies per player have pure $ε$-approximate Nash equilibria, for $ε\geqλ\sqrt{8n\log(2mn)}$. Here we provide the first hardness result for the corresponding computational problem, showing that even for a simple class of Lipschitz games (Lipschitz polymatrix games), finding pure $ε$-approximate equilibria is PPAD-complete, for suitable pairs of values $(ε(n), λ(n))$. Novel features of this result include both the proof of PPAD hardness (in which we apply a population game reduction from unrestricted polymatrix games) and the proof of containment in PPAD (by derandomizing the selection of a pure equilibrium from a mixed one). In fact, our approach implies containment in PPAD for any class of Lipschitz games where payoffs from mixed-strategy profiles can be deterministically computed.
