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/
【干货书】机器学习速查手册,135页pdf
专知会员服务
127+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
111+阅读 · 2020年5月15日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
108+阅读 · 2020年5月3日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
159+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Arxiv
0+阅读 · 2021年4月20日
Arxiv
0+阅读 · 2021年4月16日
Recent advances in deep learning theory
Arxiv
50+阅读 · 2020年12月20日
VIP会员
相关VIP内容
【干货书】机器学习速查手册,135页pdf
专知会员服务
127+阅读 · 2020年11月20日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
111+阅读 · 2020年5月15日
Python分布式计算,171页pdf,Distributed Computing with Python
专知会员服务
108+阅读 · 2020年5月3日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
159+阅读 · 2019年10月12日
强化学习最新教程,17页pdf
专知会员服务
181+阅读 · 2019年10月11日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
相关资讯
意识是一种数学模式
CreateAMind
3+阅读 · 2019年6月24日
逆强化学习-学习人先验的动机
CreateAMind
16+阅读 · 2019年1月18日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
Top
微信扫码咨询专知VIP会员