# Differentiable Bilevel Programming for Stackelberg Congestion Games

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 189 references that are in the map.
- First posted on arXiv 15 Sep 2022.

## Builds on (most cited first, 30 of 36)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks](https://mlsanity.com/paper/1703.03400/) (2017)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems](https://mlsanity.com/paper/1603.04467/) (2016)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Bilevel Programming for Hyperparameter Optimization and Meta-Learning](https://mlsanity.com/paper/1806.04910/) (2018)
- [Gradient-based Hyperparameter Optimization through Reversible Learning](https://mlsanity.com/paper/1502.03492/) (2015)
- [PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search](https://mlsanity.com/paper/1907.05737/) (2019)
- [DiffTaichi: Differentiable Programming for Physical Simulation](https://mlsanity.com/paper/1910.00935/) (2019)
- [Forward and Reverse Gradient-Based Hyperparameter Optimization](https://mlsanity.com/paper/1703.01785/) (2017)
- [Unrolled Generative Adversarial Networks](https://mlsanity.com/paper/1611.02163/) (2016)
- [Truncated Back-propagation for Bilevel Optimization](https://mlsanity.com/paper/1810.10667/) (2018)
- [On the Iteration Complexity of Hypergradient Computation](https://mlsanity.com/paper/2006.16218/) (2020)
- [Investigating Bi-Level Optimization for Learning and Vision from a Unified Perspective: A Survey and Beyond](https://mlsanity.com/paper/2101.11517/) (2021)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Scalable Gradient-Based Tuning of Continuous Regularization Hyperparameters](https://mlsanity.com/paper/1511.06727/) (2015)
- [Theano: A Python framework for fast computation of mathematical expressions](https://mlsanity.com/paper/1605.02688/) (2016)
- [Pontryagin Differentiable Programming: An End-to-End Learning and Control Framework](https://mlsanity.com/paper/1912.12970/) (2019)
- [End-to-End Learning and Intervention in Games](https://mlsanity.com/paper/2010.13834/) (2020)
- [AlphaGAN: Fully Differentiable Architecture Search for Generative Adversarial Networks](https://mlsanity.com/paper/2006.09134/) (2020)
- [Convergence of the Iterates in Mirror Descent Methods](https://mlsanity.com/paper/1805.01526/) (2018)
- [Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence](https://mlsanity.com/paper/2110.01212/) (2021)
- [Altruistic Autonomy: Beating Congestion on Shared Roads](https://mlsanity.com/paper/1810.11978/) (2018)
- [Linear Convergence of Generalized Mirror Descent with Time-Dependent Mirrors](https://mlsanity.com/paper/2009.08574/) (2020)
- [Complexity and Approximation of the Continuous Network Design Problem](https://mlsanity.com/paper/1307.4258/) (2013)
- [Traffic Optimization For a Mixture of Self-interested and Compliant Agents](https://mlsanity.com/paper/1709.09569/) (2017)
- [Information Design in Non-atomic Routing Games with Partial Participation: Computation and Properties](https://mlsanity.com/paper/2005.03000/) (2020)

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

- [An Introduction to Bi-level Optimization: Foundations and Applications in Signal Processing and Machine Learning](https://mlsanity.com/paper/2308.00788/) (2023)
- [Deep Incentive Design with Differentiable Equilibrium Blocks](https://mlsanity.com/paper/2603.07705/) (2026)
- [Learning Optimal Tax Design in Nonatomic Congestion Games](https://mlsanity.com/paper/2402.07437/) (2024)
- [Follower Agnostic Methods for Stackelberg Games](https://mlsanity.com/paper/2302.01421/) (2023)

## Abstract (arXiv)

In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game. Often formulated as bilevel programs, large-scale SCGs are well known for their intractability and complexity. Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning. The core idea centers on replacing the lower-level equilibrium problem with a smooth evolution trajectory defined by the imitative logit dynamic (ILD), which we prove converges to the equilibrium of the congestion game under mild conditions. Building upon this theoretical foundation, we propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming. Thanks to the smoothness of ILD, the algorithm promises both efficiency and scalability. The second algorithm adds a heuristic twist by cutting short the followers' evolution trajectory. Behaviorally, this means that, instead of anticipating the followers' best response at equilibrium, the leader seeks to approximate that response by only looking ahead a limited number of steps. Our numerical experiments are carried out over various instances of classic SCG applications, ranging from toy benchmarks to large-scale real-world examples. The results show the proposed algorithms are reliable and scalable local solvers that deliver high-quality solutions with greater regularity and significantly less computational effort compared to the many incumbents included in our study.