在共享约束下证明纳什均衡存在性并设计收敛算法。
Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation
- 基于玩家局部凹性与可行集收缩性，证明均衡存在。
- 提出自适应步长对数障碍梯度上升法，$ ext{O}(ε^{-3})$ 次迭代收敛。
- 适用于非凸可行域，适合博弈学习与分布式优化场景。
我们研究在共享耦合约束下，玩家策略受限的凹博弈中纳什均衡的存在性与计算问题。在玩家局部凹性约束条件下，利用拓扑不动点理论和可行集收缩性的新结构洞察，证明了纳什均衡的存在性，放宽了以往工作的强假设。在确立存在性后，进一步探讨在耦合约束下，玩家独立学习动态是否具有收敛性。针对势博弈类，设计了一种收敛算法：采用对数障碍正则化梯度上升并自适应调整步长。从初始可行策略出发，在精确梯度反馈下，该方法在 $ ext{O}(ε^{-3})$ 次迭代内收敛至 $ε$-近似约束纳什均衡。
原文摘要 · Abstract (English)
We study the existence and computation of Nash equilibria in concave games where the players' admissible strategies are subject to shared coupling constraints. Under playerwise concavity of constraints, we prove existence of Nash equilibria. Our proof leverages topological fixed point theory and novel structural insights into the contractibility of feasible sets, and relaxes strong assumptions for existence in prior work. Having established existence, we address the question of whether in the presence of coupling constraints, playerwise independent learning dynamics have convergence guarantees. We address this positively for the class of potential games by designing a convergent algorithm. To account for the possibly nonconvex feasible region, we employ a log barrier regularized gradient ascent with adaptive stepsizes. Starting from an initial feasible strategy profile and under exact gradient feedback, the proposed method converges to an $ε$-approximate constrained Nash equilibrium within $\mathcal{O}(ε^{-3})$ iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。