Differentiable Bilevel Programming for Stackelberg Congestion Games
- 7 October 2026
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
Abstract
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 that the proposed algorithms are reliable and scalable local solvers that deliver high-quality solutions with greater regularity and significantly less computational effort compared with the many incumbents included in our study. Funding: This research is funded by the National Natural Science Foundation of China’s Young Scientists Fund (Type C) [Grant 72501242], the U.S. National Science Foundation’s Civil Infrastructure System Program [Grant CMMI 2225087], and the Energy, Power, Control, and Networks Program [Grant ECCS 2048075]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2026.0233 .Keywords
All Related Versions
This publication has 75 references indexed in Scilit:
- Computing network tolls with support constraintsNetworks, 2015
- An Active-set Algorithm for Discrete Network Design Problems2009
- Taxing SubnetworksLecture Notes in Computer Science, 2008
- An approximation algorithm for Stackelberg network pricingNetworks, 2005
- Efficient BackProp1998
- Bilevel programming in traffic planning: Models, methods and challengeJournal of Global Optimization, 1995
- Methods for Equilibrium Network Traffic Signal Setting1987
- Mathematical Programming Methods for Urban Network Control1987
- Sensitivity analysis for variational inequalitiesJournal of Optimization Theory and Applications, 1986
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956