通过预编最佳响应映射,简化动态博弈求解过程。
A Data Driven Structural Decomposition of Dynamic Games via Best Response Maps
- 用离线构建的最佳响应映射替代嵌套优化层
- 解的质量接近纳什均衡,误差由映射精度决定
- 适合需高效求解多智能体博弈的场景
动态博弈是建模多智能体决策的强大工具,但计算纳什(广义纳什)均衡仍是核心挑战。复杂性源于紧密耦合的最优性条件、嵌套优化结构及数值条件差。现有博弈求解器直接求解联合博弈,需显式建模所有智能体的目标函数与约束;基于学习的方法则通过预测或策略近似解耦交互,牺牲均衡一致性。本文提出一种概念新颖的动态博弈重构方法:通过将离线编译的最佳响应映射作为可行性约束,移除嵌套优化层与导数耦合。在标准正则条件下,当最佳响应算子精确时,约化问题的任一收敛解均为原博弈的局部开环纳什(GNE)均衡;使用学习代理时,解的均衡一致性误差不超过最佳响应近似误差。该方法经数学证明支持,并在源自自主赛车问题的双人开环动态博弈中进行大规模蒙特卡洛实验验证。与先进联合博弈求解器对比,结果报告了求解质量、计算成本和约束满足度。
原文摘要 · Abstract (English)
Dynamic games are powerful tools to model multi-agent decision-making, yet computing Nash (generalized Nash) equilibria remains a central challenge in such settings. Complexity arises from tightly coupled optimality conditions, nested optimization structures, and poor numerical conditioning. Existing game-theoretic solvers address these challenges by directly solving the joint game, typically requiring explicit modeling of all agents' objective functions and constraints, while learning-based approaches often decouple interaction through prediction or policy approximation, sacrificing equilibrium consistency. This paper introduces a conceptually novel formulation for dynamic games by restructuring the equilibrium computation. Rather than solving a fully coupled game or decoupling agents through prediction or policy approximation, a data-driven structural reduction of the game is proposed that removes nested optimization layers and derivative coupling by embedding an offline-compiled best-response map as a feasibility constraint. Under standard regularity conditions, when the best-response operator is exact, any converged solution of the reduced problem corresponds to a local open-loop Nash (GNE) equilibrium of the original game; with a learned surrogate, the solution is approximately equilibrium-consistent up to the best-response approximation error. The proposed formulation is supported by mathematical proofs, accompanying a large-scale Monte Carlo study in a two-player open-loop dynamic game motivated by the autonomous racing problem. Comparisons are made against state-of-the-art joint game solvers, and results are reported on solution quality, computational cost, and constraint satisfaction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。