# On Dynamic Programming Theory for Leader-Follower Stochastic Games

arXiv: https://arxiv.org/abs/2512.05667 · HTML: https://mlsanity.com/paper/2512.05667/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 30 references that are in the map.
- First posted on arXiv 5 Dec 2025.

## Builds on (most cited first, 4 of 4)

- [Solving Zero-Sum One-Sided Partially Observable Stochastic Games](https://mlsanity.com/paper/2010.11243/) (2020)
- [Solving Hierarchical Information-Sharing Dec-POMDPs: An Extensive-Form Game Approach](https://mlsanity.com/paper/2402.02954/) (2024)
- [Optimally Solving Simultaneous-Move Dec-POMDPs: The Sequential Central Planning Approach](https://mlsanity.com/paper/2408.13139/) (2024)
- [Worst-Case Analysis for a Leader-follower Partially Observable Stochastic Game](https://mlsanity.com/paper/1901.01483/) (2019)

## Abstract (arXiv)

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.