NashOpt -- A Python Library for Computing Generalized Nash Equilibria

📄 arXiv: 2512.23636v1 📥 PDF

作者: Alberto Bemporad

分类: eess.SY, cs.GT

发布日期: 2025-12-29

备注: 23 pages, 6 figures

🔗 代码/项目: GITHUB

💡 一句话要点

NashOpt：用于计算广义纳什均衡的Python库，解决非合作博弈问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 广义纳什均衡 非合作博弈 KKT条件 自动微分 混合整数线性规划

📋 核心要点

  1. 现有方法在处理具有共享约束的非合作博弈时，计算广义纳什均衡（GNE）效率较低，尤其是在非线性情况下。
  2. NashOpt库通过利用联合KKT条件，并结合JAX自动微分和混合整数线性规划，高效求解非线性及线性二次博弈的GNE。
  3. 通过线性二次调节和模型预测控制等实例，验证了NashOpt在非合作博弈论控制问题中的有效性，并支持逆博弈和Stackelberg博弈设计。

📝 摘要（中文）

NashOpt是一个开源Python库，用于计算和设计具有共享约束和实值决策变量的非合作博弈中的广义纳什均衡（GNE）。该库利用所有参与者的联合Karush-Kuhn-Tucker（KKT）条件来处理一般的非线性GNE和线性二次博弈，包括它们的变分版本。非线性博弈通过非线性最小二乘公式求解，依赖于JAX进行自动微分。线性二次GNE被重新表述为混合整数线性程序，从而能够有效计算多个均衡。该框架还支持逆博弈和Stackelberg博弈设计问题。NashOpt的功能通过几个例子得到证明，包括线性二次调节和模型预测控制的非合作博弈论控制问题。该库可在https://github.com/bemporad/nashopt 获取。

🔬 方法详解

问题定义：论文旨在解决非合作博弈中广义纳什均衡（GNE）的计算问题，特别是在存在共享约束和实值决策变量的情况下。现有方法在处理非线性博弈时，计算复杂度高，效率低，难以找到多个均衡解。

核心思路：论文的核心思路是利用所有参与者的联合Karush-Kuhn-Tucker（KKT）条件，将GNE问题转化为优化问题进行求解。对于非线性博弈，采用非线性最小二乘法，并借助JAX库进行自动微分，简化梯度计算。对于线性二次博弈，则将其转化为混合整数线性规划（MILP）问题，从而可以高效地计算多个均衡解。

技术框架：NashOpt库的整体框架包括以下几个主要模块：1) 博弈问题定义模块：允许用户定义参与者、决策变量、约束条件和目标函数。2) KKT条件构建模块：自动构建所有参与者的联合KKT条件。3) 求解器模块：针对非线性博弈，使用非线性最小二乘求解器；针对线性二次博弈，使用MILP求解器。4) 结果分析模块：提供均衡解的分析和可视化功能。

关键创新：该库的关键创新在于：1) 统一的框架：能够处理一般的非线性GNE和线性二次博弈。2) 高效的求解方法：利用JAX自动微分加速非线性博弈求解，将线性二次博弈转化为MILP问题，实现多个均衡解的快速计算。3) 支持逆博弈和Stackelberg博弈设计：扩展了GNE计算的应用范围。

关键设计：对于非线性博弈，损失函数采用最小二乘形式，目标是最小化KKT条件的不满足程度。JAX库用于自动计算目标函数的梯度和Hessian矩阵，避免了手动推导的复杂性。对于线性二次博弈，MILP的构建依赖于对偶变量的引入，将互补松弛条件转化为线性约束，从而可以使用现成的MILP求解器进行求解。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

NashOpt通过实例验证了其在求解GNE问题上的有效性。例如，在非合作线性二次调节问题中，NashOpt能够快速找到多个均衡解，并实现系统性能的优化。与传统方法相比，NashOpt在计算效率和求解精度上均有显著提升。此外，该库还展示了在模型预测控制中的应用，证明了其在复杂动态系统中的适用性。

🎯 应用场景

NashOpt库可应用于多个领域，如交通网络优化、电力市场交易、多智能体系统控制、资源分配等。通过计算GNE，可以分析不同参与者在共享资源或约束下的策略选择，从而实现系统整体性能的优化。该库还支持逆博弈和Stackelberg博弈设计，为博弈规则制定者提供决策支持。

📄 摘要（原文）

NashOpt is an open-source Python library for computing and designing generalized Nash equilibria (GNEs) in noncooperative games with shared constraints and real-valued decision variables. The library exploits the joint Karush-Kuhn-Tucker (KKT) conditions of all players to handle both general nonlinear GNEs and linear-quadratic games, including their variational versions. Nonlinear games are solved via nonlinear least-squares formulations, relying on JAX for automatic differentiation. Linear-quadratic GNEs are reformulated as mixed-integer linear programs, enabling efficient computation of multiple equilibria. The framework also supports inverse-game and Stackelberg game-design problems. The capabilities of NashOpt are demonstrated through several examples, including noncooperative game-theoretic control problems of linear quadratic regulation and model predictive control. The library is available at https://github.com/bemporad/nashopt