提出在线可行点法,解决多智能体博弈中动态约束下的均衡收敛问题。
An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems
- 设计新算法确保每轮迭代都满足联合约束
- 在有限通信下实现对良性均衡的收敛
- 适用于需实时满足约束的多智能体系统
我们研究重复进行的广义纳什均衡博弈,这转化为带有联合约束的多智能体在线学习问题。主要挑战在于每个智能体的可行集依赖于其他智能体的同时行动,因此随时间动态变化。由于约束是系统内生而非对抗性,现有方法虽能通过惩罚项将约束融入目标函数,但无法保证所有迭代中约束均被满足且同时收敛到广义纳什均衡。本文提出一种新的在线可行点法,在允许有限通信的前提下,确保可行性。我们定义了‘良性’广义纳什均衡问题类别,并证明该方法在此类问题上可收敛至均衡。通过对比现有定义并举例说明,展示了方法的有效性。
原文摘要 · Abstract (English)
We consider a repeatedly played generalized Nash equilibrium game. This induces a multi-agent online learning problem with joint constraints. An important challenge in this setting is that the feasible set for each agent depends on the simultaneous moves of the other agents and, therefore, varies over time. As a consequence, the agents face time-varying constraints, which are not adversarial but rather endogenous to the system. Prior work in this setting focused on convergence to a feasible solution in the limit via integrating the constraints in the objective as a penalty function. However, no existing work can guarantee that the constraints are satisfied for all iterations while simultaneously guaranteeing convergence to a generalized Nash equilibrium. This is a problem of fundamental theoretical interest and practical relevance. In this work, we introduce a new online feasible point method. Under the assumption that limited communication between the agents is allowed, this method guarantees feasibility. We identify the class of benign generalized Nash equilibrium problems, for which the convergence of our method to the equilibrium is guaranteed. We set this class of benign generalized Nash equilibrium games in context with existing definitions and illustrate our method with examples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。