# Efficient Stackelberg Strategies for Finitely Repeated Games

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2022.

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

- [Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents](https://mlsanity.com/paper/2306.02704/) (2023)
- [Maximizing utility in multi-agent environments by anticipating the behavior of other learners](https://mlsanity.com/paper/2407.04889/) (2024)
- [Algorithmic Collusion Without Threats](https://mlsanity.com/paper/2409.03956/) (2024)
- [Incentivizing High-Quality Content in Online Recommender Systems](https://mlsanity.com/paper/2306.07479/) (2023)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions](https://mlsanity.com/paper/2408.08272/) (2024)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Learning to Play Against Unknown Opponents](https://mlsanity.com/paper/2412.18297/) (2024)
- [Last-iterate Convergence for Symmetric, General-sum, 2 × 2 Games Under The Exponential Weights Dynamic](https://mlsanity.com/paper/2502.08063/) (2025)

## Abstract (arXiv)

We study Stackelberg equilibria in finitely repeated games, where the leader commits to a strategy that picks actions in each round and can be adaptive to the history of play (i.e. they commit to an algorithm). In particular, we study static repeated games with no discounting. We give efficient algorithms for finding approximate Stackelberg equilibria in this setting, along with rates of convergence depending on the time horizon T. In many cases, these algorithms allow the leader to do much better on average than they can in the single-round Stackelberg. We give two algorithms, one computing strategies with an optimal frac1T rate at the expense of an exponential dependence on the number of actions, and another (randomized) approach computing strategies with no dependence on the number of actions but a worse dependence on T of frac1T0.25. Both algorithms build upon a linear program to produce simple automata leader strategies and induce corresponding automata best-responses for the follower. We complement these results by showing that approximating the Stackelberg value in three-player finite-horizon repeated games is a computationally hard problem via a reduction from balanced vertex cover.