论文标题
潜在游戏中NASH平衡的沟通复杂性
Communication complexity of Nash equilibrium in potential games
论文作者
论文摘要
我们证明了在潜在游戏中（可能混合）NASH平衡的通信复杂性。特别是，我们表明，找到纳什平衡需要$ poly（n）$ communication in Twip-player $ n \ times n $潜在的游戏，而$ 2^{poly（n）} $ communication in $ n $ n $ - 玩家两次攻击游戏。据我们所知，这些是在潜在游戏中（可能混合）NASH平衡模型中证明硬度的第一个结果。
We prove communication complexity lower bounds for (possibly mixed) Nash equilibrium in potential games. In particular, we show that finding a Nash equilibrium requires $poly(N)$ communication in two-player $N \times N$ potential games, and $2^{poly(n)}$ communication in $n$-player two-action games. To the best of our knowledge, these are the first results to demonstrate hardness in any model of (possibly mixed) Nash equilibrium in potential games.
