Gradient Methods for Stackelberg Games

Kareem Amin, Michael Wellman, Satinder Singh
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:465-474, 2016.

Abstract

Stackelberg games are two-stage games in which the first player (called the leader) commits to a strategy, after which the other player (the follower) selects a best-response. These types of games have seen numerous practical application in security settings, where the leader (in this case, a defender) must allocate resources to protect various targets. Real world applications include the scheduling of US federal air marshals to international flights, and resource allocation at LAX airport. However, the best known algorithm for solving general Stackelberg games requires solving Integer Programs, and fails to scale beyond a few (significantly smaller than 100) number of leader actions, or follower types. In this paper, we present a new approach for solving large Stackelberg games in the security settings, using techniques from AI. Large-scale control problems are often times solved by restricting the controller to a rich, but parameterized, class of policies; the optimal control can then be computed using Monte Carlo gradient methods. We demonstrate that the same approach can be taken in a strategic setting. We evaluate our strategies empirically, demonsrating they have negligible regret against the leader’s true equilibrium strategy, while scaling to large games.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-amin16a, title = {Gradient Methods for Stackelberg Games}, author = {Amin, Kareem and Wellman, Michael and Singh, Satinder}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {465--474}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/amin16a/amin16a.pdf}, url = {https://proceedings.mlr.press/r14/amin16a.html}, abstract = {Stackelberg games are two-stage games in which the first player (called the leader) commits to a strategy, after which the other player (the follower) selects a best-response. These types of games have seen numerous practical application in security settings, where the leader (in this case, a defender) must allocate resources to protect various targets. Real world applications include the scheduling of US federal air marshals to international flights, and resource allocation at LAX airport. However, the best known algorithm for solving general Stackelberg games requires solving Integer Programs, and fails to scale beyond a few (significantly smaller than 100) number of leader actions, or follower types. In this paper, we present a new approach for solving large Stackelberg games in the security settings, using techniques from AI. Large-scale control problems are often times solved by restricting the controller to a rich, but parameterized, class of policies; the optimal control can then be computed using Monte Carlo gradient methods. We demonstrate that the same approach can be taken in a strategic setting. We evaluate our strategies empirically, demonsrating they have negligible regret against the leader’s true equilibrium strategy, while scaling to large games.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Gradient Methods for Stackelberg Games %A Kareem Amin %A Michael Wellman %A Satinder Singh %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-amin16a %I PMLR %P 465--474 %U https://proceedings.mlr.press/r14/amin16a.html %V R14 %X Stackelberg games are two-stage games in which the first player (called the leader) commits to a strategy, after which the other player (the follower) selects a best-response. These types of games have seen numerous practical application in security settings, where the leader (in this case, a defender) must allocate resources to protect various targets. Real world applications include the scheduling of US federal air marshals to international flights, and resource allocation at LAX airport. However, the best known algorithm for solving general Stackelberg games requires solving Integer Programs, and fails to scale beyond a few (significantly smaller than 100) number of leader actions, or follower types. In this paper, we present a new approach for solving large Stackelberg games in the security settings, using techniques from AI. Large-scale control problems are often times solved by restricting the controller to a rich, but parameterized, class of policies; the optimal control can then be computed using Monte Carlo gradient methods. We demonstrate that the same approach can be taken in a strategic setting. We evaluate our strategies empirically, demonsrating they have negligible regret against the leader’s true equilibrium strategy, while scaling to large games. %Z Reissued by PMLR on 04 October 2026.
APA
Amin, K., Wellman, M. & Singh, S.. (2016). Gradient Methods for Stackelberg Games. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:465-474 Available from https://proceedings.mlr.press/r14/amin16a.html. Reissued by PMLR on 04 October 2026.

Related Material