Differentiable Bilevel Programming for Stackelberg Congestion Games

References

• Abadi M, Agarwal A, Barham P, Brevdo E, Chen Z, Citro C, Corrado GS, et al. (2015) TensorFlow: Large-scale machine learning on heterogeneous systems. Accessed April 1, 2026, https://www.tensorflow.org/.Google Scholar
• Abdulaal M, LeBlanc LJ (1979) Continuous equilibrium network design models. Transportation Res. Part B Methodological 13(1):19–32.Crossref, Google Scholar
• Agrawal A, Amos B, Barratt S, Boyd S, Diamond S, Kolter JZ (2019) Differentiable convex optimization layers. Adv. Neural Inform. Processing Systems 32:9558–9570. Google Scholar
• Bard JF, Falk JE (1982) An explicit solution to the multi-level programming problem. Comput. Oper. Res. 9(1):77–100.Crossref, Google Scholar
• Baydin AG, Pearlmutter BA, Radul AA, Siskind JM (2018) Automatic differentiation in machine learning: A survey. J. Machine Learn. Res. 18(153):1–43.Google Scholar
• Beck A, Teboulle M (2003) Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3):167–175.Crossref, Google Scholar
• Bertsekas DP, Gafni EM (1982) Projection methods for variational inequalities with application to the traffic assignment problem. Sorensen DC, Wets RJB, eds. Nondifferential and Variational Techniques in Optimization, Mathematical Programming Studies, vol. 17 (Springer, Berlin), 139–159.Crossref, Google Scholar
• Bhaskar U, Ligettm K, Schulman LJ (2013) The network improvement problem for equilibrium routing. Preprint, submitted July 14, https://arxiv.org/abs/1307.3794.Google Scholar
• Björnerstedt J, Weibull JW (1994) Nash equilibrium and evolution by imitation. Technical report, Stockholm University, Stockholm.Google Scholar
• Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258–268.Google Scholar
• Brotcorne L, Labbé M, Marcotte P, Savard G (2001) A bilevel model for toll optimization on a multicommodity transportation network. Transportation Sci. 35(4):345–358.Link, Google Scholar
• Cantarella GE, Sforza A (1987) Methods for equilibrium network traffic signal setting. Odoni AR, Bianco L, Szegö G, eds. Flow Control of Congested Networks, NATO ASI Series, vol. 38 (Springer, Berlin), 69–89.Crossref, Google Scholar
• Chen Z, He F, Zhang L, Yin Y (2016) Optimal deployment of autonomous vehicle lanes with endogenous market penetration. Transportation Res. Part C Emerging Tech. 72:143–156.Crossref, Google Scholar
• Chiou SW (2005) Bilevel programming for the continuous transport network design problem. Transportation Res. Part B Methodological 39(4):361–383.Crossref, Google Scholar
• Dafermos SC (1973) Toll patterns for multiclass-user transportation networks. Transportation Sci. 7(3):211–223.Link, Google Scholar
• Dafermos S (1980) Traffic equilibrium and variational inequalities. Transportation Sci. 14(1):42–54.Link, Google Scholar
• Dafermos S (1988) Sensitivity analysis in variational inequalities. Math. Oper. Res. 13(3):421–434.Link, Google Scholar
• Dantzig GB, Harvey RP, Lansdowne ZF, Robinson DW, Maier SF (1979) Formulating and solving the network design problem by decomposition. Transportation Res. Part B Methodological 13(1):5–17.Crossref, Google Scholar
• Delle Site P (2021) Pricing of connected and autonomous vehicles in mixed-traffic networks. Transportation Res. Record 2675(5):178–192.Crossref, Google Scholar
• Farahani RZ, Miandoabchi E, Szeto WY, Rashidi H (2013) A review of urban transportation network design problems. Eur. J. Oper. Res. 229(2):281–302.Crossref, Google Scholar
• Feng L, Li J, Xu Z, Xie J (2026) Bilevel transit timetabling with synchronization at origin and transfer stops. Transportation Res. Part C: Emerging Tech. 188:105700.Google Scholar
• Finn C, Abbeel P, Levine S (2017) Model-agnostic meta-learning for fast adaptation of deep networks. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (PMLR, Cambridge, MA), 1126–1135.Google Scholar
• Fisk C (1984) Game theory and transportation systems modelling. Transportation Res. Part B Methodological 18(4–5):301–313.Crossref, Google Scholar
• Franceschi L, Donini M, Frasconi P, Pontil M (2017) Forward and reverse gradient-based hyperparameter optimization. Precup D, Teh YW, eds. Proc. 34th Internat. Conf. Machine Learn., vol. 70 (PMLR, Cambridge, MA), 1165–1173.Google Scholar
• Franceschi L, Frasconi P, Salzo S, Grazzi R, Pontil M (2018) Bilevel programming for hyperparameter optimization and meta-learning. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., vol. 80 (PMLR, Cambridge, MA), 1568–1577.Google Scholar
• Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• Friesz TL, Harker PT (1985) Properties of the iterative optimization-equilibrium algorithm. Civil Engrg. Systems 2(3):142–154.Crossref, Google Scholar
• Friesz TL, Bernstein D, Kydes N (2004) Dynamic congestion pricing in disequilibrium. Networks Spatial Econom. 4(2):181–202.Crossref, Google Scholar
• Friesz TL, Tobin RL, Cho HJ, Mehta NJ (1990) Sensitivity analysis based heuristic algorithms for mathematical programs with variational inequality constraints. Math. Programming 48(1–3):265–284.Crossref, Google Scholar
• Friesz TL, Cho HJ, Mehta NJ, Tobin RL, Anandalingam G (1992) A simulated annealing approach to the network design problem with variational inequality constraints. Transportation Sci. 26(1):18–26.Link, Google Scholar
• Fukushima M (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Math. Programming 53(1–3):99–110.Crossref, Google Scholar
• Gairing M, Harks T, Klimm M (2017) Complexity and approximation of the continuous network design problem. SIAM J. Optim. 27(3):1554–1582.Crossref, Google Scholar
• Gartner NH (1985) Demand-responsive traffic signal control research. Transportation Res. Part A General 19(5–6):369–373.Crossref, Google Scholar
• Goodfellow I, Bengio Y, Courville A, Bengio Y (2016) Deep Learning, vol. 1 (MIT Press, Cambridge, MA).Google Scholar
• Griewank A (1989) On automatic differentiation. Iri M, Tanabe K, eds. Mathematical Programming: Recent Developments and Applications (Springer, Dordrecht, Netherlands), 83–108.Google Scholar
• Guo L, Li J (2025) Cardinality-constrained bilevel capacity expansion. Preprint, submitted September 16, https://arxiv.org/abs/2509.13209.Google Scholar
• Harks T, Kleinert I, Klimm M, Möhring RH (2015) Computing network tolls with support constraints. Networks 65(3):262–285.Crossref, Google Scholar
• Hoefer M, Olbrich L, Skopalik A (2008) Taxing subnetworks. Papadimitriou C, Zhang S, eds. Internet and Network Economics, WINE 2008, Lecture Notes in Computer Science, vol. 5385 (Springer, Berlin), 286–294.Crossref, Google Scholar
• Improta G (1987) Mathematical programming methods for urban network control. Odoni AR, Bianco L, Szegö G, eds. Flow Control of Congested Networks, NATO ASI Series, vol. 38 (Springer, Berlin), 35–68.Crossref, Google Scholar
• Jayakrishnan R, Tsai WK, Prashker JN, Rajadhyaksha S (1994) A faster path-based algorithm for traffic assignment. Transportation Res. Record 1443:75–83.Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kullback S (1997) Information Theory and Statistics (Dover Publications, Mineola, NY).Google Scholar
• Lawphongpanich S, Hearn DW (2004) An MPEC approach to second-best toll pricing. Math. Programming 101(1):33–55.Crossref, Google Scholar
• Lazar DA, Coogan S, Pedarsani R (2019) Optimal tolling for heterogeneous traffic networks with mixed autonomy. Canudas de Wit C, ed. Proc. 58th Conf. Decision Control (IEEE, Piscataway, NJ), 4103–4108.Google Scholar
• LeCun Y, Bottou L, Orr GB, Müller KR (1998) Efficient backprop. Orr GB, Müller KR, eds. Neural Networks: Tricks of the Trade, Lecture Notes in Computer Science, vol. 1524 (Springer, Berlin), 9–50.Crossref, Google Scholar
• Li W, Kockelman KM, Huang Y (2021) Traffic and welfare impacts of credit-based congestion pricing applications: An Austin case study. Transportation Res. Record 2675(1):10–24.Crossref, Google Scholar
• Li J, Wang Z, Nie Y (2024) Wardrop equilibrium can be boundedly rational: A new behavioral theory of route choice. Transportation Sci. 58(5):973–994.Link, Google Scholar
• Li J, Yu J, Nie YM, Wang Z (2020) End-to-end learning and intervention in games. Adv. Neural Inform. Processing Systems 33:16653–16665.Google Scholar
• Li C, Yang H, Zhu D, Meng Q (2012) A global optimization method for continuous network design problems. Transportation Res. Part B Methodological 46(9):1144–1158.Crossref, Google Scholar
• Li J, Wang Q, Feng L, Xie J, Nie YM (2024) A day-to-day dynamical approach to the most likely user equilibrium problem. Transportation Sci. 58(6):1193–1213.Link, Google Scholar
• Liu H, Simonyan K, Yang Y (2019) DARTS: Differentiable architecture search. Sainath T, Rush AM, Levine S, Livescu K, Mohamed S, eds. Proc. 7th Internat. Conf. Learn. Representations (International Conference on Learning Representations, Appleton, WI), 8558–8570.Google Scholar
• Liu Z, Yin Y, Bai F, Grimm DK (2023) End-to-end learning of user equilibrium with implicit neural networks. Transportation Res. Part C Emerging Tech. 150:104085.Crossref, Google Scholar
• Liu R, Gao J, Zhang J, Meng D, Lin Z (2021) Investigating bi-level optimization for learning and vision from a unified perspective: A survey and beyond. IEEE Trans. Pattern Anal. Machine Intelligence 44(12):10045–10067.Crossref, Google Scholar
• Liu B, Li J, Yang Z, Wai HT, Hong M, Nie Y, Wang Z (2022) Inducing equilibria via incentives: Simultaneous design-and-play ensures global convergence. Adv. Neural Inform. Processing Systems 35:29001–29013.Crossref, Google Scholar
• Lo HK, Chen A (2000) Reformulating the traffic equilibrium problem via a smooth gap function. Math. Comput. Model. 31(2–3):179–195.Crossref, Google Scholar
• Lu G, Nie YM, Liu X, Li D (2019) Trajectory-based traffic management inside an autonomous vehicle zone. Transportation Res. Part B Methodological 120:76–98.Crossref, Google Scholar
• Luketina J, Berglund M, Greff K, Raiko T (2016) Scalable gradient-based tuning of continuous regularization hyperparameters. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., vol. 80 (PMLR, Cambridge, MA), 2952–2960.Google Scholar
• Luo ZQ, Pang JS, Ralph D (1996) Mathematical Programs with Equilibrium Constraints (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Marcotte P (1981) Design optimal d’un réseau de transport en présence d’effets de congestion. PhD thesis, Universite de Montreal, Montreal.Google Scholar
• Marcotte P (1983) Network optimization with continuous control parameters. Transportation Sci. 17(2):181–197.Link, Google Scholar
• Marcotte P (1986) Network design problem with congestion effects: A case of bilevel programming. Math. Programming 34(2):142–162.Crossref, Google Scholar
• Marcotte P, Marquis G (1992) Efficient implementation of heuristics for the continuous network design problem. Ann. Oper. Res. 34(1):163–176.Crossref, Google Scholar
• Marcotte P, Wu JH (1995) On the convergence of projection methods: Application to the decomposition of affine variational inequalities. J. Optim. Theory Appl. 85(2):347–362.Crossref, Google Scholar
• McKenzie D, Heaton H, Li Q, Wu Fung S, Osher S, Yin W (2024) Three-operator splitting for learning to predict equilibria in convex games. SIAM J. Math. Data Sci. 6(3):627–648.Crossref, Google Scholar
• Meng Q, Yang H, Bell MG (2001) An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Res. Part B Methodological 35(1):83–105.Crossref, Google Scholar
• Metz L, Poole B, Pfau D, Sohl-Dickstein J (2017) Unrolled generative adversarial networks. Larochelle H, Vinyals O, Sainath T, eds. Proc. 5th Internat. Conf. Learn. Representations (International Conference on Learning Representations, Appleton, WI), 1516–1540.Google Scholar
• Migdalas A (1995) Bilevel programming in traffic planning: Models, methods and challenge. J. Global Optim. 7(4):381–405.Crossref, Google Scholar
• Nemirovskij AS, Yudin DB (1983) Problem Complexity and Method Efficiency in Optimization (Wiley-Interscience, New York).Google Scholar
• Paszke A, Gross S, Massa F, Lerer A, Bradbury J, Chanan G, Killeen T, et al. (2019) PyTorch: An imperative style, high-performance deep learning library. Adv. Neural Inform. Processing Systems 32:8024–8035.Google Scholar
• Patriksson M (2004) Sensitivity analysis of traffic equilibria. Transportation Sci. 38(3):258–281.Link, Google Scholar
• Patriksson M, Rockafellar RT (2002) A mathematical model and descent algorithm for bilevel traffic management. Transportation Sci. 36(3):271–291.Link, Google Scholar
• Roch S, Savard G, Marcotte P (2005) An approximation algorithm for Stackelberg network pricing. Networks 46(1):57–67.Crossref, Google Scholar
• Rumelhart DE, Hinton GE, Williams RJ (1986) Learning representations by back-propagating errors. Nature 323(6088):533–536.Crossref, Google Scholar
• Sandholm WH (2015) Population games and deterministic evolutionary dynamics. Young HP, Zamir S, eds. Handbook of Game Theory with Economic Applications, vol. 4 (Elsevier, Amsterdam), 703–778.Google Scholar
• Shaban A, Cheng CA, Hatch N, Boots B (2019) Truncated back-propagation for bilevel optimization. Chaudhuri K, Sugiyama M, eds. Proc. 22nd Internat. Conf. Artificial Intelligence Statist., vol. 89 (PMLR, Cambridge, MA), 1723–1732.Google Scholar
• Sheffi Y (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Method (Prentice-Hall, Hoboken, NJ).Google Scholar
• Sherali HD, Soyster AL, Murphy FH (1983) Stackelberg–Nash–Cournot equilibria: Characterizations and computations. Oper. Res. 31(2):253–276.Link, Google Scholar
• Simoni MD, Kockelman KM, Gurumurthy KM, Bischoff J (2019) Congestion pricing in a world of self-driving vehicles: An analysis of different strategies in alternative future scenarios. Transportation Res. Part C Emerging Tech. 98:167–185.Crossref, Google Scholar
• Smith M (1979) Traffic control and route-choice: A simple example. Transportation Res. Part B Methodological 13(4):289–294.Crossref, Google Scholar
• Smith M, Van Vuren T (1993) Traffic equilibrium with responsive traffic control. Transportation Sci. 27(2):118–132.Link, Google Scholar
• Suwansirikul C, Friesz TL, Tobin RL (1987) Equilibrium decomposed optimization: A heuristic for the continuous equilibrium network design problem. Transportation Sci. 21(4):254–263.Link, Google Scholar
• Tan HN, Gershwin SB, Athans M (1979) Hybrid optimization in urban traffic networks. Technical report, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Tobin RL (1986) Sensitivity analysis for variational inequalities. J. Optim. Theory Appl. 48(1):191–204.Crossref, Google Scholar
• Tobin RL, Friesz TL (1988) Sensitivity analysis for equilibrium network flow. Transportation Sci. 22(4):242–250.Link, Google Scholar
• Transportation Networks for Research Core Team (2023) Transportation networks for research. Accessed April 1, 2026, https://github.com/bstabler/TransportationNetworks.Google Scholar
• Verhoef ET (2002) Second-best congestion pricing in general networks. Heuristic algorithms for finding second-best optimal toll levels and toll points. Transportation Res. Part B Methodological 36(8):707–729.Crossref, Google Scholar
• Vicente L, Savard G, Júdice J (1994) Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2):379–399.Crossref, Google Scholar
• von Stackelberg H (1952) The Theory of the Market Economy (Oxford University Press, Oxford, UK).Google Scholar
• Wang Q, Li H, Xie J, Nie YM, Li J (2026) A general algorithm for traffic assignment problems with continuously distributed user attributes. Transportation Res. Part B Methodological 209:103465.Crossref, Google Scholar
• Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers 1(3):325–378.Crossref, Google Scholar
• Weibull JW (1997) Evolutionary Game Theory (MIT Press, Cambridge, MA).Google Scholar
• Xiang Y, Sun D, Fan W, Gong X (1997) Generalized simulated annealing algorithm and its application to the Thomson model. Phys. Lett. A 233(3):216–220.Crossref, Google Scholar
• Xie J, Nie YM (2019) A new algorithm for achieving proportionality in user equilibrium traffic assignment. Transportation Sci. 53(2):566–584.Link, Google Scholar
• Xie J, Nie YM, Liu X (2018) A greedy path-based algorithm for traffic assignment. Transportation Res. Record 2672(48):36–44.Crossref, Google Scholar
• Yang H, Bell MGH (1998) Models and algorithms for road network design: A review and some new developments. Transport Rev. 18(3):257–278.Crossref, Google Scholar
• Yang H, Bell MGH (2007) Sensitivity analysis of network traffic equilibrium revisited: The corrected approach. Heydecker BG, ed. Proc. 4th IMA Internat. Conf. Math. Transport. (Elsevier, Oxford, UK), 373–395.Google Scholar
• Yang H, Huang H-J (2005) Mathematical and Economic Theory of Road Pricing (Emerald Group Publishing Limited, Bingley, UK).Crossref, Google Scholar
• Yang H, Yagar S (1994) Traffic assignment and traffic control in general freeway-arterial corridor systems. Transportation Res. Part B Methodological 28(6):463–486.Crossref, Google Scholar
• Yang H, Zhang X, Meng Q (2007) Stackelberg games and multiple equilibrium behaviors on networks. Transportation Res. Part B Methodological 41(8):841–861.Crossref, Google Scholar
• Yu J, Wang Q, Nie M, Li J (2026) A scalable descent algorithm for network design problems. Transportation Res. Part E Logist. Transportation Rev. 211:104838.Crossref, Google Scholar
• Zhang K, Nie YM (2018) Mitigating the impact of selfish routing: An optimal-ratio control scheme (ORCS) inspired by autonomous driving. Transportation Res. Part C Emerging Tech. 87:75–90.Crossref, Google Scholar
• Zhang K, Nie YM (2021) To pool or not to pool: Equilibrium, pricing and regulation. Transportation Res. Part B Methodological 151:59–90.Crossref, Google Scholar
• Zhang L, Lawphongpanich S, Yin Y (2009) An active-set algorithm for discrete network design problems. Lam WHK, Wong SC, Lo HK, eds. Transportation and Traffic Theory 2009: Golden Jubilee (Springer, New York), 283–300.Crossref, Google Scholar