# Solving Structured Hierarchical Games Using Differential Backward Induction

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2021.

## Built on by (most cited first, 3 of 3)

- [Oracles & Followers: Stackelberg Equilibria in Deep Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2210.11942/) (2022)
- [SoK: Machine Learning Governance](https://mlsanity.com/paper/2109.10870/) (2021)
- [ReLExS: Reinforcement Learning Explanations for Stackelberg No-Regret Learners](https://mlsanity.com/paper/2408.14086/) (2024)

## Abstract (arXiv)

From large-scale organizations to decentralized political systems, hierarchical strategic decision making is commonplace. We introduce a novel class of structured hierarchical games (SHGs) that formally capture such hierarchical strategic interactions. In an SHG, each player is a node in a tree, and strategic choices of players are sequenced from root to leaves, with root moving first, followed by its children, then followed by their children, and so on until the leaves. A player's utility in an SHG depends on its own decision, and on the choices of its parent and all the tree leaves. SHGs thus generalize simultaneous-move games, as well as Stackelberg games with many followers. We leverage the structure of both the sequence of player moves as well as payoff dependence to develop a gradient-based back propagation-style algorithm, which we call Differential Backward Induction (DBI), for approximating equilibria of SHGs. We provide a sufficient condition for convergence of DBI and demonstrate its efficacy in finding approximate equilibrium solutions to several SHG models of hierarchical policy-making problems.