论文标题
图形游戏的严格不适当性
Tight Inapproximability for Graphical Games
论文作者
论文摘要
我们为在两次图形游戏中找到近似平衡的计算复杂性提供了完整的表征。我们考虑了两个最精心研究的近似概念：$ \ varepsilon $ -nash Equilibria（$ \ varepsilon $ -ne）和$ \ varepsilon $ -Well-well supported Nash Equilibria（$ \ \ \ \ \ \ \ varepsilon $ -wsne）我们证明，对于任何常数$ \ varepsilon <1/2 $，计算$ \ varepsilon $ -ne都是ppad complete，而一种非常简单的算法（即，让所有玩家在两个动作之间均匀混合）会产生$ 1/2 $ -ne。另一方面，我们表明，对于任何常数$ \ varepsilon <1 $，计算$ \ varepsilon $ -wsne都是完整的，而$ 1 $ -WSNE的实现都是微不足道的，因为任何策略配置文件都是$ 1 $ -WSNE。我们所有的下限都立即适用于图形游戏，每个玩家都有两个以上的动作。
We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: $\varepsilon$-Nash equilibria ($\varepsilon$-NE) and $\varepsilon$-well-supported Nash equilibria ($\varepsilon$-WSNE), where $\varepsilon \in [0,1]$. We prove that computing an $\varepsilon$-NE is PPAD-complete for any constant $\varepsilon < 1/2$, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a $1/2$-NE. On the other hand, we show that computing an $\varepsilon$-WSNE is PPAD-complete for any constant $\varepsilon < 1$, while a $1$-WSNE is trivial to achieve, because any strategy profile is a $1$-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.
