Graphical games are a useful framework for modeling the interactions of (selfish) agents who are connected via an underlying topology and whose behaviors influence each other. They have wide applications ranging from computer science to economics and biology. Yet, even though a player's payoff only depends on the actions of their direct neighbors in graphical games, computing the Nash equilibria and making statements about the convergence time of "natural" local dynamics in particular can be highly challenging. In this work, we present a novel approach for classifying complexity of Nash equilibria in graphical games by establishing a connection to local graph algorithms, a subfield of distributed computing. In particular, we make the observation that the equilibria of graphical games are equivalent to locally verifiable labelings (LVL) in graphs; vertex labelings which are verifiable with a constant-round local algorithm. This connection allows us to derive novel lower bounds on the convergence time to equilibrium of best-response dynamics in graphical games. Since we establish that distributed convergence can sometimes be provably slow, we also introduce and give bounds on an intuitive notion of "time-constrained" inefficiency of best responses. We exemplify how our results can be used in the implementation of mechanisms that ensure convergence of best responses to a Nash equilibrium. Our results thus also give insight into the convergence of strategy-proof algorithms for graphical games, which is still not well understood.
翻译:图形化游戏是一个有用的框架, 用来模拟( 自私) 代理人的互动( 自私) 。 这些代理人通过基本的地形学连接, 其行为相互影响。 它们有着广泛的应用, 从计算机科学到经济学和生物学。 然而, 尽管玩家的回报仅仅取决于图形游戏中直接邻居的行动, 计算纳什平衡, 并声明“ 自然” 本地动态的趋同时间, 特别是具有高度挑战性。 在这项工作中, 我们提出了一个新颖的方法, 通过建立与本地图表算法( 分布式计算的一个子领域)的连接, 来区分图形游戏中Nash equiquilibria 的复杂性。 特别是, 我们观察到图形游戏的平衡性相当于在图形化游戏中可在当地核实的标签( LVL) ; 顶点标签可以用恒定的本地算法进行核查。 这个连接让我们在图形游戏中获得最佳反应反应的趋同性时间的新的较低界限。 由于我们确定分布的趋同性有时会缓慢, 我们还提出并给一个不理解的直观概念, 的“ ” 的趋同性战略的趋同性反应也是我们所使用的最精确的趋同性反应。