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. Since our analysis hinges on a restricted monotonicity property, we also provide new general results that significantly extend the domain of applicability of proximal-point methods. Besides, the operator-theoretic approach favors the implementation of provably correct acceleration schemes that can further improve the convergence speed. Finally, the potential of our algorithms is demonstrated numerically, revealing much faster convergence with respect to projected pseudo-gradient methods and validating our theoretical findings.


翻译:我们处理在局部决定信息情景中寻求问题的普世纳什均衡问题,即每个代理商只能与某些邻居交流信息,尽管其成本功能可能取决于所有代理商的战略。少数现有方法以预测的假梯度动态为基础,要求使用双层迭代或阶梯尺寸的保守条件。为了克服这些缺陷并提高效率,我们设计了第一个完全分布的单层算法,其依据是准最佳反应。我们的计划是固定的,允许不精确的更新,这对降低计算复杂性至关重要。在游戏原始人的标准假设下,我们通过将我们的算法重新表述为准点方法,或者需要双层迭代,或者需要双层迭代,或者需要一步尺寸的保守条件。为了克服这些缺陷并提高效率,我们设计了第一个完全分散的单层算法。由于我们的分析以有限的单一度属性为基础,我们还提供了新的一般结果,大大扩展了准点方法的适用性领域。此外,操作者理论方法更有利于执行可实现准确的加速计划,从而可以进一步提高我们预测的趋同率,最终展示了我们量化的方法。

0
下载
关闭预览

相关内容

《计算机信息》杂志发表高质量的论文,扩大了运筹学和计算的范围,寻求有关理论、方法、实验、系统和应用方面的原创研究论文、新颖的调查和教程论文,以及描述新的和有用的软件工具的论文。官网链接:https://pubsonline.informs.org/journal/ijoc
ICML 2021论文收录
专知会员服务
122+阅读 · 2021年5月8日
专知会员服务
47+阅读 · 2021年3月5日
应用机器学习书稿,361页pdf
专知会员服务
58+阅读 · 2020年11月24日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习在材料科学中的应用综述,21页pdf
专知会员服务
48+阅读 · 2019年9月24日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【OpenAI】深度强化学习关键论文列表
专知
11+阅读 · 2018年11月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
0+阅读 · 2022年2月13日
Arxiv
0+阅读 · 2022年2月11日
Adversarial Mutual Information for Text Generation
Arxiv
13+阅读 · 2020年6月30日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关VIP内容
ICML 2021论文收录
专知会员服务
122+阅读 · 2021年5月8日
专知会员服务
47+阅读 · 2021年3月5日
应用机器学习书稿,361页pdf
专知会员服务
58+阅读 · 2020年11月24日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习在材料科学中的应用综述,21页pdf
专知会员服务
48+阅读 · 2019年9月24日
相关资讯
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
【OpenAI】深度强化学习关键论文列表
专知
11+阅读 · 2018年11月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员