Solving structured hierarchical games using differential backward induction
Zun Li, Feiran Jia, Aditya Mate, Shahin Jabbari, Mithun Chakraborty, Milind Tambe, Yevgeniy Vorobeychik
Abstract
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.
BibTeX
@InProceedings{pmlr-v180-li22a,
title = {Solving structured hierarchical games using differential backward induction},
author = {Li, Zun and Jia, Feiran and Mate, Aditya and Jabbari, Shahin and Chakraborty, Mithun and Tambe, Milind and Vorobeychik, Yevgeniy},
booktitle = {Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence},
pages = {1107--1117},
year = {2022},
editor = {Cussens, James and Zhang, Kun},
volume = {180},
series = {Proceedings of Machine Learning Research},
month = {01--05 Aug},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v180/li22a/li22a.pdf},
url = {https://proceedings.mlr.press/v180/li22a.html},
abstract = {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.}
}