We address the generalized Nash equilibrium seeking problem in a partial-decision information scenario, where each agent can only exchange information with some neighbors, although its cost function possibly depends on the strategies of all agents. The few existing methods build on projected pseudo-gradient dynamics, and require either double-layer iterations or conservative conditions on the step sizes. To overcome both these flaws and improve efficiency, we design the first fully-distributed single-layer algorithms based on proximal best-response. Our schemes are fixed-step and allow for inexact updates, which is crucial for reducing the computational complexity. Under standard assumptions on the game primitives, we establish convergence to a variational equilibrium (with linear rate for games without coupling constraints) by recasting our algorithms as proximal-point methods, opportunely preconditioned to distribute the computation among the agents. Besides, our operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Since our analysis hinge on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. The potential of our algorithms is validated numerically, revealing much faster convergence with respect to the known projected pseudo-gradient algorithms.


翻译:我们处理普遍纳什均衡在局部决定信息情景中寻求问题,即每个代理商只能与某些邻居交流信息,尽管其成本功能可能取决于所有代理商的战略。少数现有方法建立在预测的假梯度动态基础上,要求双层迭代或按步尺大小保守条件。为了克服这些缺陷并提高效率,我们设计了第一个完全分布的单层算法,其基础是最佳反应。我们的计划是固定的,允许不精确更新,这对降低计算复杂性至关重要。在游戏原始体的标准假设下,我们通过将我们的算法重新表述为准点方法,从而实现变异平衡(无组合限制的游戏线性率),这是在跨步尺尺寸上分配计算的适当先决条件。此外,我们使用操作者理论理论方法支持实施可精确纠正的加速计划,从而进一步提高趋同速度。由于我们的分析取决于有限的单调属性,我们还提供了新的一般结果,大大扩展了准点趋同点方法的适用性(无组合率率率率率率率),我们预测的趋近的趋同法是快速的模拟的变正法。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
MIT新书《强化学习与最优控制》
专知会员服务
275+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Adversarial Mutual Information for Text Generation
Arxiv
13+阅读 · 2020年6月30日
Arxiv
10+阅读 · 2018年3月23日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
人工智能 | NIPS 2019等国际会议信息8条
Call4Papers
7+阅读 · 2019年3月21日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员