提出动态规划框架求解领导者-追随者博弈的最优策略，提升决策效率与可解释性。
On Dynamic Programming Theory for Leader-Follower Stochastic Games
- 基于可信集的状态抽象，用贝尔曼递推构建求解框架
- 证明最优策略合成是NP难问题，设计ε-最优算法并保证领导者可被利用度
- 在安全博弈等场景中显著提升领导者收益与计算速度
领导者-追随者一般和随机博弈（LF-GSSG）建模了不对称承诺下的序贯决策问题：领导者先选定策略，追随者则最优响应，从而产生对领导者有利的强斯塔克尔伯格均衡（SSE）。本文提出一种动态规划（DP）框架，通过贝尔曼递推在可信集——即部分领导者承诺下所有理性的追随者最优响应的正式状态抽象——上进行求解。我们首先证明任意LF-GSSG可无损地转化为一个关于可信集的马尔可夫决策过程（MDP）。进一步，我们建立合成最优无记忆确定性领导者策略是NP难的，由此推动了ε-最优DP算法的发展，并提供了领导者可被利用度的理论保证。在标准混合动机基准测试（包括安全博弈、资源分配和对抗性规划）上的实验表明，该方法在领导者价值和运行时间可扩展性方面均优于当前最优方法。
原文摘要 · Abstract (English)
Leader-follower general-sum stochastic games (LF-GSSGs) model sequential decision-making under asymmetric commitment, where a leader commits to a policy and a follower best responds, yielding a strong Stackelberg equilibrium (SSE) with leader-favourable tie-breaking. This paper introduces a dynamic programming (DP) framework that applies Bellman recursion over credible sets-state abstractions formally representing all rational follower best responses under partial leader commitments-to compute SSEs. We first prove that any LF-GSSG admits a lossless reduction to a Markov decision process (MDP) over credible sets. We further establish that synthesising an optimal memoryless deterministic leader policy is NP-hard, motivating the development of ε-optimal DP algorithms with provable guarantees on leader exploitability. Experiments on standard mixed-motive benchmarks-including security games, resource allocation, and adversarial planning-demonstrate empirical gains in leader value and runtime scalability over state-of-the-art methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。