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) ; 顶点标签可以用恒定的本地算法进行核查。 这个连接让我们在图形游戏中获得最佳反应反应的趋同性时间的新的较低界限。 由于我们确定分布的趋同性有时会缓慢, 我们还提出并给一个不理解的直观概念, 的“ ” 的趋同性战略的趋同性反应也是我们所使用的最精确的趋同性反应。

0
下载
关闭预览

相关内容

DC:Distributed Computing。 Explanation:分布式计算。 Publisher:Springer。 SIT:http://dblp.uni-trier.de/db/journals/dc/
【经典书】算法博弈论,775页pdf,Algorithmic Game Theory
专知会员服务
149+阅读 · 2021年5月9日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
124+阅读 · 2020年6月25日
【ICLR2020】图神经网络与图像处理,微分方程,27页ppt
专知会员服务
47+阅读 · 2020年6月6日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
已删除
将门创投
5+阅读 · 2017年8月15日
VIP会员
相关VIP内容
【经典书】算法博弈论,775页pdf,Algorithmic Game Theory
专知会员服务
149+阅读 · 2021年5月9日
【图与几何深度学习】Graph and geometric deep learning,49页ppt
一份简单《图神经网络》教程,28页ppt
专知会员服务
123+阅读 · 2020年8月2日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【硬核书】群论,Group Theory,135页pdf
专知会员服务
124+阅读 · 2020年6月25日
【ICLR2020】图神经网络与图像处理,微分方程,27页ppt
专知会员服务
47+阅读 · 2020年6月6日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
107+阅读 · 2020年5月3日
相关资讯
已删除
将门创投
5+阅读 · 2017年8月15日
Top
微信扫码咨询专知VIP会员