Convex Duality in Perturbed Utility Route Choice
Mogens Fosgerau, Jesper R.-V. Sørensen · 2026
Read Convex Duality in Perturbed Utility Route Choice by Mogens Fosgerau, Jesper R.-V. Sørensen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20220.txt.
Introduction
Fosgerau and Sørensen build a broad convex duality frame for perturbed utility route choice, where travelers pick routes under utility maximization. They show the traveler's constrained, possibly jagged utility problem has a dual form: a free concave maximization with a smooth goal. The one best flow comes back link by link from any dual answer through convex conjugates of link perturbation functions. That frame backs fast gradient-based optimization on big networks, quick sensitivity checks, and a neat parallel with current flow in electric circuits.
Catalog record
| CREATOR | Mogens Fosgerau, Jesper R.-V. Sørensen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111309 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.20220
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Convex Duality in Perturbed Utility Route Choice Mogens Fosgerau, Jesper R.-V. Sørensen Abstract This paper develops a highly general convex duality framework for the perturbed utility route choice (PURC) model. We show that the traveler’s constrained, potentially non-smooth utility maximization problem admits a dual formulation: an unconstrained concave maximization problem with a differentiable objective. The unique optimal flow can be recovered link-by-link from any dual solution via the convex conjugates of link perturbation functions. These properties enable efficient gradient-based optimization for large-scale networks and fast computation for sensitivity analysis. Finally, the framework reveals a structural analogy between PURC and current flow in electrical circuits. 1 Introduction Figure 1 illustrates a large dataset of GPS traces of bicycle trips in Copenhagen. Such data have become widely available, tracking millions of trips—by cars, trucks, bicycles, and using public transport—at high spatial and temporal resolution across large networks. Modeling such data is essential for informing policy on the design and regulation of transport networks, including infrastructure investment and road pricing. This requires disaggregate models that predict individual route choices through large-scale networks. Figure 1: Bicycle data and bicycle-relevant network for Copenhagen illustrated with figures from Fosgerau et al. 2023 . The sheer size and complexity of transportation networks makes this a challenging problem. For perspective, the number of distinct cycle-free paths between two points in an urban network is astronomically large—on the order of the square of the number of atoms in the universe ( Roberts and Kroese 2007 ) . Because of this combinatorial explosion, it has proven difficult to adapt the classical discrete choice model ( McFadden 1981 ) to the route choice problem ( Prato 2009 ) . This paper develops a convex-analytic foundation for the perturbed utility route choice (PURC) model ( Fosgerau et al. 2022 ) —a recent alternative to classical discrete choice approaches. Unlike traditional models that describe route choice as a discrete choice among a set of routes, PURC operates directly on the network structure, enabling tractable analysis and computation for large-scale systems. PURC is an instance of the general perturbed utility model proposed by Fosgerau and McFadden 2012 , which unifies several models widely used in economics ( Fudenberg et al. 2015 ; Allen and Rehbeck 2019 ; Allen and Rehbeck 2020 ; Fosgerau et al. 2024a ) . Building on this foundation, we derive a dual formulation and computational properties that make the model practical for large-scale applications ( Fosgerau et al. 2023 ; Yao et al. 2024 ) . We show that the PURC model generalizes a model of electrical current flow ( Rockafellar 1984 ) , placing it among physics-inspired transportation models such as the gravity model and the Lighthill-Whitham-Richards traffic flow model. In the general perturbed utility model , an agent maximizes utility of the form U(\bm{x})=\langle\bm{v},\bm{x}\rangle-H(\bm{x}),\quad\bm{x}\in B, where \bm{x} is a demand vector, B\subseteq\mathbb{R}^{n} is a budget set, \bm{v} is a vector of utility indexes, and H is a convex function on \mathbb{R}^{n} called the perturbation function . Any additive random utility discrete choice model can be expressed in this form when the budget B is the probability simplex ( Hofbauer and Sandholm 2002 ) , in which case the demand \bm{x} is a probability vector. The perturbed utility route choice model describes route choice in a network from a given origin to a given destination. Unlike discrete choice models, demand is not a probability vector but a non-negative flow assigned to each link. The flow on a link can be interpreted as the probability of observing a random trip on that link, and the budget constraint enforces flow conservation as traffic moves through the network. The perturbation function is separable across links, H(\bm{x})=\sum_{e\in\mathcal{E}}h_{e}(x_{e}), where each h_{e} is a univariate convex function. The perturbation function can be interpreted as an information cost, a Bregman divergence ( Bregman 1967 ) measuring the distance of the flow vector to some (here unspecified) base flow. In this paper, we establish conditions for a general PURC model and derive properties essential for applications. Our main contributions are: • Existence and uniqueness of a solution to the traveler’s PURC problem (the primal), ensuring a well-defined demand. • A dual problem that is unconstrained, concave, and differentiable, even when the primal is non-smooth. These properties enable modern gradient-based optimization ( Nesterov 2018 , see, e.g.,) for large-scale networks. • A closed-form dual objective with closed-form gradient and Hessian, enabling optimization and sensitivity analysis. • A simple link-by-link recovery of demand from a dual solution via convex conjugates of link perturbation functions. • A computationally simple expression of the Jacobian of the optimal flow useful for sensitivity analysis ( Fosgerau et al. 2025 ) . • A clearer understanding of the model’s duality structure through convex analysis. • Understanding the PURC model as an analog of an electrical circuit. On the latter point, we find that a version of the perturbed utility structure is mathematically identical to the basic model of a resistive electric circuit ( Rockafellar 1984 ) . Thus, flow corresponds to electric current, travelers to electrons, link perturbation functions h_{e} to resistance, and flow conservation to Kirchhoff’s current law. The Lagrange multipliers for flow conservation constraints act as potentials, reinforcing the analogy. The PURC framework applies to abstract networks. In addition to physical transport networks this includes, e.g., public transport networks ( de Cea and Fernández 1993 ) , dynamic networks with time dimensions ( Ran and Boyce 1996 ) , and hypernetworks incorporating mode, origin, destination, and timing choices ( Sheffi and Daganzo 1980 ) . It applies to activity-based models ( Ben-Akiva and Bowman 1998 ) , social and computer networks, and even educational or occupational pathways. 1.1 Related Literature The literature on route choice is extensive; see Prato 2009 for a review. Most studies treat route choice as a discrete choice among routes, which creates the challenge that the number of feasible routes is enormous. Research has therefore focused on constructing choice sets with good coverage to avoid bias and on developing models with realistic substitution patterns. A newer line of research considers recursive models, where travelers choose paths link by link in a Markovian fashion. Early work addressed the assignment problem ( Dial 1971 ; Bell 1995 ; Shen et al. 1996 ; Baillon and Cominetti 2008 ) . Subsequent studies introduced the recursive logit model and its generalizations based on the multivariate extreme value distribution ( Fosgerau et al. 2013 ; Mai et al. 2015a ; Mai et al. 2015b ; Mai 2016 ) . The duality properties of these models have been exploited by Oyama et al. 2022 . However, applying recursive logit to large networks remains challenging due to the need to invert large matrices. Zimmermann and Frejinger 2020 provides a comprehensive tutorial. The PURC model ( Fosgerau et al. 2022 ; Fosgerau et al. 2023 ) departs from the discrete choice paradigm by modeling travelers as maximizing a perturbed utility function ( Fosgerau and McFadden 2012 ) . It requires no choice set and uses the entire network directly. Substitution patterns arise from the network structure via a perturbation function defined as a sum of convex link-flow functions. With aggregate route data, PURC can be estimated