Literature
Display
← All papers

Congestion Games with Heterogeneous Valuations: An Optimal Transport Approach

Pan-Yang Su · Negar Mehr · Shankar Sastry

Preprint posted · arXiv (preprint) ↗

Robotics14 min text · CondensedOriginal paper ↗
Contents

At a glance

The model combines a continuum of agents with multidimensional outcome valuations, finite strategies that share congested resources, and optional hard capacities. Equilibria admit aggregate-flow and outcome-threshold descriptions; welfare-optimal assignments use semi-discrete optimal transport and strategy-level dual potentials. With utility valuation minus latency and convex total resource costs xℓ(x), welfare maximization is convex and a social optimum can be supported by marginal-cost tolls plus capacity multipliers. The results characterize structure and existence under stated assumptions; no convergent numerical solver or empirical mobility deployment is demonstrated.

I Introduction

The paper connects heterogeneous allocation preferences with endogenous congestion, then separates equilibrium and welfare characterizations.

I-A A New Congestion Game Model

Agents can value destinations, charging stations or service outcomes differently while their strategies consume shared resources. A valuation vector records these preferences, and congestion depends on the resulting allocation. This joins multidimensional assignment with network congestion, rather than representing heterogeneity only by one participation cutoff.

I-B Theoretical Contributions

Three results drive the paper. First, used strategies for a given outcome have minimum equal latency at equilibrium, producing one outcome-threshold vector per group. Second, fixing aggregate flows turns optimal type-to-strategy assignment into semi-discrete transport, with finite strategy-indexed dual potentials. Third, separable utility produces a convex planner problem and marginal-cost/capacity pricing under additional regularity. The equilibrium and optimal-transport arguments have different origins; the dual vector is not automatically an implementable congestion price.

I-C An Emerging Application

Advanced air mobility motivates joint destination/route choice with both delays and infrastructure limits. The paper supplies a static model for this setting, not an operational air-traffic mechanism. Its notation uses componentwise vector order, measurable pushforwards and almost-everywhere statements over the continuum population.

II Related Work

The main connections are nonatomic congestion games, continuum matching and semi-discrete transport. The new combination concerns multidimensional outcome values with endogenous congestion.

II-A Nonatomic Congestion Games

Compared with player-specific single-resource games, strategies may use several shared resources and utility need not separate valuation from latency. Elastic-demand routing is recovered through an outside option, while multiple outcomes require a multidimensional partition. Destination-choice preferences need not follow a prescribed parametric random-utility distribution.

II-B Matching Markets

Threshold geometry resembles continuum college matching, but the model is one-sided, with cardinal utilities and congestion externalities. It studies Nash equilibria and welfare optima, rather than stable two-sided matchings. Prior finite matching-with-congestion models do not give the same continuum/network characterization.

II-C Optimal Transport for Nonatomic Games

Other transport approaches analyze Cournot–Nash equilibria or physical movement through congested space. Here optimal transport assigns types to a finite strategy set conditional on its target masses; the outer optimization chooses those masses. It does not transport travelers geometrically between prescribed origin/destination distributions.

III Model

The primitives specify resources, groups, outcomes, strategies, valuation distributions and utilities; the solution objects initially assign a strategy to every type.

III-A Nonatomic Congestion Games with Heterogeneous Valuations

Each group has a finite strategy set partitioned by outcome. Its finite measure describes the total mass of agents at each valuation vector.

III-A 1 Elements

Resources have positive capacities and nonnegative, nondecreasing continuous latency functions. Strategy latency sums the latencies of its resources. The main model uses individual resource capacities; later extensions permit coupled constraints.

III-A 2 Agents, Outcomes, and Strategies

Group i has mass rᵢ, outcomes Dᵢ and strategies 𝒫ᵢ, with each strategy a subset of resources and assigned to exactly one outcome. Strategies are group-indexed/disjoint as labels, even when they share resources. In routing, an outcome is a destination and a strategy is a path to it.

Equation
𝒫i=⋃j∈Di𝒫i,j,𝒫i,j∩𝒫i,j′=∅for ​j≠j′,\mathcal{P}_{i}=\bigcup_{j\in D_{i}}\mathcal{P}_{i,j},\qquad\mathcal{P}_{i,j}\cap\mathcal{P}_{i,j^{\prime}}=\emptyset\quad\text{for }j\neq j^{\prime},

III-A 3 Flows

Strategy flows are nonnegative masses. Admissibility requires each group’s flows to sum to rᵢ; resource loads sum all strategy flows using that resource. Capacity feasibility adds load≤capacity. Latencies depend on these aggregate loads, not on the identity of individual agents.

Equation
ℓP​(f):=∑e∈Pℓe​(fe).\ell_{P}(f):=\sum_{e\in P}\ell_{e}(f_{e}).

III-A 4 Always-Feasible Strategies

Each group must have a strategy consisting entirely of nonbinding-capacity resources. This guarantees an always-feasible alternative, interpretable as not participating. It is essential to arguments excluding overloaded equilibria in the basic capacity model.

Equation
ce≥∑i∈Ieri,Ie:={i∈[k]∣∃P∈𝒫i​ such that ​e∈P}.c_{e}\geq\sum_{i\in I_{e}}r_{i},\qquad I_{e}:=\{i\in[k]\mid\exists P\in\mathcal{P}_{i}\text{ such that }e\in P\}.

III-A 5 Valuations

Valuations lie in a compact nonnegative box, with total population measure rᵢ. The measure is a deterministic distribution of types, not uncertainty about an individual’s private draw. Main results assume absolute continuity with respect to Lebesgue measure, so outcome indifference sets are null; arbitrary measures are handled later with splittable type masses.

Equations
V:=⨆i∈[k]Vi,ℬV:={⨆i∈[k]Ai|Ai∈ℬVi,∀i∈[k]},V:=\bigsqcup_{i\in[k]}V_{i},\qquad\mathcal{B}_{V}:=\left\{\bigsqcup_{i\in[k]}A_{i}\;\middle|\;A_{i}\in\mathcal{B}_{V_{i}},\ \forall i\in[k]\right\},
μ⁡(⨆i∈[k]Ai):=∑i∈[k]μi​(Ai).\mu\left(\bigsqcup_{i\in[k]}A_{i}\right):=\sum_{i\in[k]}\mu_{i}(A_{i}).

III-A 6 Action Profiles

A measurable pure action profile pushes the population measure onto strategy flows. Lemma 1 shows that every admissible flow can be realized: nonatomicity permits partitioning each group’s type space into measurable pieces with the requested masses. Profiles differing only on null sets are equivalent. This realizability statement alone does not establish equilibrium existence.

Equations
a⁡((i,v))∈𝒫i,∀i∈[k],v∈Vi.a((i,v))\in\mathcal{P}_{i},\qquad\forall i\in[k],\ v\in V_{i}.
a:=(ai,v)i∈[k],v∈Vi,ai,v:=a⁡((i,v)).a:=(a_{i,v})_{i\in[k],\,v\in V_{i}},\qquad a_{i,v}:=a((i,v)).
fP=μ⁡(a−1​(P)),∀P∈𝒫.f_{P}=\mu\bigl(a^{-1}(P)\bigr),\qquad\forall P\in\mathcal{P}.

III-A 7 Utility Functions

Utility Uᵢ(value,latency) is continuous, strictly increasing in value and strictly decreasing in latency. Soft congestion changes latency continuously; a strategy using an overloaded resource instead receives −∞, or a sufficiently low finite substitute. The always-feasible option makes such a strategy unattractive in the basic model. Separable utility value−latency is a later specialization.

Equation 1
ui,v​(ai,v,a−(i,v))\displaystyle u_{i,v}(a_{i,v},a_{-(i,v)}) (1)
={Ui​(vj,ℓP​(f)),ai,v=P∈𝒫i,j,fe≤ce,∀e∈P,−∞,otherwise.\displaystyle=\begin{cases}U_{i}(v_{j},\ell_{P}(f)),&a_{i,v}=P\in\mathcal{P}_{i,j},f_{e}\leq c_{e},\forall e\in P,\\ -\infty,&\text{otherwise}.\end{cases}

III-A 8 Instances

An instance collects the resource and strategy sets, group masses, latency/capacity data, valuation spaces with their measures, utility functions and outcome partition. These primitives determine both population sorting and congestion.

III-B Relation to Classical Nonatomic Congestion Games

Classical nonatomic congestion games are recovered after allowing strategy-specific resource consumption weights and homogeneous valuation masses with infinite capacities. A homogeneous type is an atom in valuation space but still represents many infinitesimal agents, not one strategic player with positive weight. Thus this reduction uses the later general-measure extension, beyond the main absolute-continuity assumption.

Equations
ce=∞,Di={1},Vi={0},μi​({0})=ri,c_{e}=\infty,\qquad D_{i}=\{1\},\qquad V_{i}=\{0\},\qquad\mu_{i}(\{0\})=r_{i},
−ℓP(f)=−∑e∈PαP,eℓe(fe).-\ell_{P}(f)=-\sum_{e\in P}\alpha_{P,e}\ell_{e}(f_{e}).

III-C Nash Equilibria and Social Optima

Nash equilibrium tests individual best responses at unchanged aggregate flow; social optimality maximizes integrated utility over assignments.

III-C 1 Nash Equilibria

Almost every infinitesimal agent must weakly prefer its chosen strategy to every alternative. A unilateral deviation has zero effect on aggregate load, including at a binding capacity. This convention differs materially from equilibrium definitions that permit only positive-mass coalitional deviations.

Equation
ui,v​(ai,v,a−(i,v))≥ui,v​(b,a−(i,v)),∀b∈𝒫i.u_{i,v}(a_{i,v},a_{-(i,v)})\geq u_{i,v}(b,a_{-(i,v)}),\qquad\forall b\in\mathcal{P}_{i}.

III-C 2 Social Optima

Social welfare integrates realized utility over all groups and types. Two assignments with the same flow can have different welfare because they assign different valuations to outcomes. The planner therefore optimizes both the flow and which types realize it.

Equations 2
S​W​(a)\displaystyle SW(a) :=∫Vui,v​(ai,v)​dμ​((i,v))\displaystyle:=\int_{V}u_{i,v}(a_{i,v})\,d\mu((i,v))
=∑i∈[k]∫Viui,v​(ai,v)​d​μi​(v).\displaystyle=\sum_{i\in[k]}\int_{V_{i}}u_{i,v}(a_{i,v})\,d\mu_{i}(v).
a∗∈arg⁡maxa​S​W​(a).a^{*}\in\arg\max_{a}SW(a). (2)

III-D Problem Formulation

The central question is whether infinitely many individual choices can be represented by finite variables. The answer uses aggregate flows plus outcome thresholds for equilibrium and aggregate flows plus strategy dual potentials for general welfare; separability enables explicit supporting prices.

IV Applications

Routing, shared markets and congestible clubs illustrate the framework’s scope. They are mathematical examples, not empirical validations.

IV-A Routing Games with Heterogeneous Valuations

Routing groups share a source but may choose among several destinations. An outside destination can represent not traveling.

IV-A 1 Model

Strategies are simple paths, utility is destination value minus path latency, and the specialized latency assumptions require differentiability and convex xℓ(x). The marginal-cost function is ℓ(x)+xℓ′(x). Multiple destination values generally have no single ordering; zero-valued outside options or homogeneous types fit through the general-measure extension when they violate full-dimensional absolute continuity.

Equations
ℓ^e​(x):=dd​y​(y​ℓe​(y))|y=x.\hat{\ell}_{e}(x):=\left.\frac{d}{dy}\bigl(y\ell_{e}(y)\bigr)\right|_{y=x}.
Ui​(vj,ℓP​(f))=vj−ℓP​(f).U_{i}(v_{j},\ell_{P}(f))=v_{j}-\ell_{P}(f).

IV-A 2 A Two-Destination Example

In the two-destination example, type mass is Lebesgue measure on [0,3]², totaling nine. Equilibrium threshold (2,0) assigns flows (0.5,8.5), with latencies (36,34), so choice is determined by v₁−2 versus v₂. The optimum threshold (1,0) gives flows (2,7) and marginal costs (57,56). Destination heterogeneity permits unequal used-route latencies, so merging both destinations into a single classical endpoint loses the essential sorting structure.

s 1 s_{1} t 1 , 1 t_{1,1} t 1 , 2 t_{1,2} r 1 = 9 r_{1}=9 c 1 = ∞ ℓ 1 ​ ( x ) = 6 ​ x + 33 \begin{aligned} &c_{1}=\infty\\
&\ell_{1}(x)=6x+33\end{aligned} c 2 = ∞ ℓ 2 ​ ( x ) = 4 ​ x \begin{aligned} &c_{2}=\infty\\
&\ell_{2}(x)=4x\end{aligned}
(a) A single-commodity network with one source and two destinations.
00112233440011223344τ1\tau_{1}V1,1​(τ1)V_{1,1}(\tau_{1})V1,2​(τ1)V_{1,2}(\tau_{1})v1v_{1}v2v_{2}
(b) The valuation space V1=[0,3]2V_{1}=[0,3]^{2} and the Nash equilibrium partition induced by τ1=(2,0)\tau_{1}=(2,0).
Fig. 1: A two-destination routing game and the induced partition of the valuation space.
Equations
V1,1​(τ1)\displaystyle V_{1,1}(\tau_{1}) ={v∈V1∣v1−2≥v2},\displaystyle=\{v\in V_{1}\mid v_{1}-2\geq v_{2}\},
V1,2​(τ1)\displaystyle V_{1,2}(\tau_{1}) ={v∈V1∣v1−2<v2}.\displaystyle=\{v\in V_{1}\mid v_{1}-2<v_{2}\}.
f1=0.5,f2=8.5.f_{1}=0.5,\qquad f_{2}=8.5.
ℓ^1​(x)=12​x+33,ℓ^2​(x)=8​x.\hat{\ell}_{1}(x)=12x+33,\qquad\hat{\ell}_{2}(x)=8x.
f1=2,f2=7.f_{1}=2,\qquad f_{2}=7.

IV-B Market-Sharing Games

An agent serving market j obtains value times its share nⱼ/fⱼ, represented by a nonseparable value/latency utility. The literal ratio is singular at zero and does not meet the model’s assumptions. The paper therefore supplies positive numerator/denominator regularization, restoring continuity and strict monotonicity.

EquationsUi​(x,y)=x+ε0y+ε1,ℓj​(f)=fjnj.U_{i}(x,y)=\frac{x+\varepsilon_{0}}{y+\varepsilon_{1}},\qquad\ell_{j}(f)=\frac{f_{j}}{n_{j}}.Ui​(vj,ℓj​(f))=(vj+ε0)​njfj+ε1​nj,U_{i}(v_{j},\ell_{j}(f))=\frac{(v_{j}+\varepsilon_{0})n_{j}}{f_{j}+\varepsilon_{1}n_{j}},

IV-C Congestible Club Goods

Clubs, coworking spaces or fitness facilities are outcomes with membership-dependent congestion and heterogeneous membership values. Capacities represent membership/physical limits; shared resources across facilities motivate coupled constraints.

V Characterizations of Nash Equilibria and Social Optima

The finite description retains both how much traffic each strategy carries and which valuation types receive each outcome. General welfare additionally needs the assignment among same-outcome strategies.

V-A Characterization of Nash Equilibria

Equilibrium existence and its conditional threshold characterization are distinct results.

V-A 1 Existence and Nonexistence

Without binding capacities, continuous aggregate utilities, measurable preferences and finite strategies satisfy Schmeidler’s nonatomic-game existence conditions. Hard capacities break this continuity and can destroy Nash equilibrium under individual zero-mass deviations. The paper does not assert universal existence in the capacitated model.

Equation
{v∈Vi|Ui​(vj1,ℓP1​(f))>Ui​(vj2,ℓP2​(f))}\left\{v\in V_{i}\;\middle|\;U_{i}(v_{j_{1}},\ell_{P_{1}}(f))>U_{i}(v_{j_{2}},\ell_{P_{2}}(f))\right\}

V-A 2 Threshold-Based Characterization

Theorem 1 gives three necessary and sufficient flow conditions: capacity feasibility; each used strategy minimizes latency among strategies to its outcome; and each outcome’s flow equals the measure of types maximizing Uᵢ(vⱼ,τᵢⱼ), where τ is minimum outcome latency. Strict value monotonicity plus absolute continuity makes ties null by fixing all but one valuation coordinate. Conversely, measurable partitions allocate each outcome region among its minimum-latency strategies at the required masses. Thus the thresholds describe sorting while the flow consistency conditions close the congestion feedback.

Equations 3
Vi,j​(τi):={v∈Vi|j∈arg⁡maxj^∈Di​Ui​(vj^,τi,j^)}.V_{i,j}(\tau_{i}):=\left\{v\in V_{i}\;\middle|\;j\in\arg\max_{\hat{j}\in D_{i}}U_{i}(v_{\hat{j}},\tau_{i,\hat{j}})\right\}. (3)
S={v∈Vi|Ui​(vj1,τi,j1)=Ui​(vj2,τi,j2)}.S=\left\{v\in V_{i}\;\middle|\;U_{i}(v_{j_{1}},\tau_{i,j_{1}})=U_{i}(v_{j_{2}},\tau_{i,j_{2}})\right\}.
ℓP​(f)≤ℓQ​(f).\ell_{P}(f)\leq\ell_{Q}(f).
∑P∈𝒫i,jfP=μi​(Vi,j​(τi)),\sum_{P\in\mathcal{P}_{i,j}}f_{P}=\mu_{i}\bigl(V_{i,j}(\tau_{i})\bigr),
τi,j:=minP∈𝒫i,j⁡ℓP​(f).\tau_{i,j}:=\min_{P\in\mathcal{P}_{i,j}}\ell_{P}(f).

V-A 3 Computational Approach

These conditions suggest a finite-dimensional fixed-point computation. No particular algorithm’s convergence or runtime is established; that is explicitly future work.

V-B Characterization of Social Optima

Welfare optimization separates into an outer choice of feasible strategy masses and an inner optimal assignment at those masses.

V-B 1 Upper-Level Problem

For fixed flow f, all strategy latencies are fixed. The value Sᵢ(f) maximizes group i’s integrated utility over measurable assignments whose pushforward is fᵢ. The outer problem maximizes the sum of these values subject to flow conservation, nonnegativity and capacities. Lemma 1 makes every candidate admissible flow realizable.

Equations 4–5d
𝒯i(f):={T:Vi→𝒫i measurable|T#μi=f},\mathcal{T}_{i}(f):=\left\{T:V_{i}\to\mathcal{P}_{i}\text{ measurable}\;\middle|\;T_{\#}\mu_{i}=f\right\},
𝒮i​(f):=supT∈𝒯i​(f)∑j∈Di∑P∈𝒫i,j∫T−1​(P)Ui​(vj,ℓP​(f))​d​μi​(v).\mathcal{S}_{i}(f)\!:=\!\!\!\sup_{T\in\mathcal{T}_{i}(f)}\sum_{j\in D_{i}}\sum_{P\in\mathcal{P}_{i,j}}\int_{T^{-1}(P)}\!\!\!\!\!U_{i}(v_{j},\ell_{P}(f))\,d\mu_{i}(v). (4)
supf\displaystyle\sup_{f}\quad ∑i∈[k]𝒮i​(f)\displaystyle\sum_{i\in[k]}\mathcal{S}_{i}(f) (5a)
s.t. fP≥0,∀P∈𝒫,\displaystyle f_{P}\geq 0,\qquad\forall P\in\mathcal{P}, (5b)
∑P∈𝒫ifP=ri,∀i∈[k],\displaystyle\sum_{P\in\mathcal{P}_{i}}f_{P}=r_{i},\qquad\forall i\in[k], (5c)
fe≤ce,∀e∈E.\displaystyle f_{e}\leq c_{e},\qquad\forall e\in E. (5d)
S​W​(a)=∑i∈[k]∑j∈Di∑P∈𝒫i,j∫ai−1​(P)Ui​(vj,ℓP​(f))​d​μi​(v),SW(a)=\sum_{i\in[k]}\sum_{j\in D_{i}}\sum_{P\in\mathcal{P}_{i,j}}\int_{a_{i}^{-1}(P)}U_{i}(v_{j},\ell_{P}(f))\,d\mu_{i}(v),

V-B 2 Semi-Discrete Optimal Transport

A Kantorovich coupling may split source mass; a Monge map assigns each type deterministically. Lemma 2 uses a nonatomic source, finite targets and bounded continuous reward to equate the transport optimum with a finite dual minimum: integrate the maximum reward minus a target potential, then add potential-weighted target masses. Both extrema are attained, and every optimal dual vector supports some optimal measurable map. The map selection must respect target masses; arbitrary tie-breaking is insufficient.

Equations 6
supπ∈Π⁡(μ,ν)∫X×Yc⁡(x,y)​𝑑π​(x,y).\sup_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c(x,y)\,d\pi(x,y).
supπ∈Π⁡(μ,ν)∫X×Yc⁡(x,j)​dπ​(x,j)\displaystyle\sup_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c(x,j)\,d\pi(x,j) (6)
=minq∈ℝm⁡{∫Xmaxj∈Y⁡(c⁡(x,j)−qj)​dμ​(x)+∑j=1mqj​νj},\displaystyle=\min_{q\in\mathbb{R}^{m}}\left\{\int_{X}\max_{j\in Y}\bigl(c(x,j)-q_{j}\bigr)\,d\mu(x)+\sum_{j=1}^{m}q_{j}\nu_{j}\right\},
T⁡(x)∈arg⁡maxj∈Y⁡(c⁡(x,j)−qj)for μ-a.e. ​x.T(x)\in\arg\max_{j\in Y}\bigl(c(x,j)-q_{j}\bigr)\quad\text{for $\mu$-a.e. }x.

V-B 3 Lower-Level Problem

Theorem 2 applies that lemma to utility at fixed congestion, with one dual potential per strategy. Optimal assignments select utility-minus-potential maximizers and meet prescribed strategy masses. Same-outcome strategies can tie over positive-measure regions, so their supporting regions need not form a disjoint partition. Translation invariance and a uniform utility bound permit an optimal potential vector in [0,2K]. These are conditional assignment prices, not generally resource-level congestion tolls.

Equations 7–8
Vi,P​(q):={v∈Vi|P∈arg⁡maxP^∈𝒫i​[Ui​(vj^,ℓP^​(f))−qP^]},V_{i,P}(q):=\left\{v\in V_{i}\;\middle|\;P\in\arg\max_{\hat{P}\in\mathcal{P}_{i}}\left[U_{i}(v_{\hat{j}},\ell_{\hat{P}}(f))-q_{\hat{P}}\right]\right\},
Ui​(vj,ℓP​(f))−qP=Ui​(vj,ℓQ​(f))−qQU_{i}(v_{j},\ell_{P}(f))-q_{P}=U_{i}(v_{j},\ell_{Q}(f))-q_{Q}
Φi​(w,f):=\displaystyle\Phi_{i}(w,f):={} ∫VimaxP^∈𝒫i⁡[Ui​(vj^,ℓP^​(f))−wP^]​d​μi​(v)\displaystyle\int_{V_{i}}\max_{\hat{P}\in\mathcal{P}_{i}}\left[U_{i}(v_{\hat{j}},\ell_{\hat{P}}(f))-w_{\hat{P}}\right]d\mu_{i}(v) (7)
+∑P∈𝒫iwPfP.\displaystyle+\sum_{P\in\mathcal{P}_{i}}w_{P}f_{P}.
T⁡(v)∈arg⁡maxP^∈𝒫i​[Ui​(vj^,ℓP^​(f))−qP^]T(v)\in\arg\max_{\hat{P}\in\mathcal{P}_{i}}\left[U_{i}(v_{\hat{j}},\ell_{\hat{P}}(f))-q_{\hat{P}}\right]
fi​(𝒫i)=∑P∈𝒫ifP=ri=μi​(Vi).f^{i}(\mathcal{P}_{i})=\sum_{P\in\mathcal{P}_{i}}f_{P}=r_{i}=\mu_{i}(V_{i}).
supπ∈Π⁡(μi,fi)∫Vi×𝒫icf​(v,P)​𝑑π​(v,P).\sup_{\pi\in\Pi(\mu_{i},f^{i})}\int_{V_{i}\times\mathcal{P}_{i}}c_{f}(v,P)\,d\pi(v,P). (8)
supπ∈Π⁡(μi,fi)∫Vi×𝒫icf​(v,P)​𝑑π​(v,P)=minw∈ℝ𝒫i⁡Φi​(w,f).\sup_{\pi\in\Pi(\mu_{i},f^{i})}\int_{V_{i}\times\mathcal{P}_{i}}c_{f}(v,P)\,d\pi(v,P)=\min_{w\in\mathbb{R}^{\mathcal{P}_{i}}}\Phi_{i}(w,f).
T⁡(v)∈arg⁡maxP^∈𝒫i​[Ui​(vj^,ℓP^​(f))−qP^]T(v)\in\arg\max_{\hat{P}\in\mathcal{P}_{i}}\left[U_{i}(v_{\hat{j}},\ell_{\hat{P}}(f))-q_{\hat{P}}\right]
|Ui​(vj,ℓP​(f))|≤K\left|U_{i}(v_{j},\ell_{P}(f))\right|\leq K
Φi​(w+a​𝟏,f)=Φi​(w,f),\Phi_{i}(w+a\mathbf{1},f)=\Phi_{i}(w,f),
Ui​(vj,ℓP​(f))−wP<−KU_{i}(v_{j},\ell_{P}(f))-w_{P}<-K
Ui​(vj^,ℓP^​(f))−wP^≥−K.U_{i}(v_{\hat{j}},\ell_{\hat{P}}(f))-w_{\hat{P}}\geq-K.

V-B 4 Existence and Comparative Statics

Joint continuity and the fixed compact dual box give continuous assignment value and an upper-hemicontinuous nonempty compact optimizer correspondence via Berge’s theorem. Compact feasible flows then yield existence of a social optimum. The max-of-shifted-utilities integrand is submodular in potentials, so the minimizing set is a compact sublattice and hence a complete lattice with extremal selections. This concerns the bounded dual set; it does not prove unique flow or smooth comparative statics.

Equations
Λi​(f):=arg⁡minq∈[0,2​K]|𝒫i|​Φi​(q,f).\Lambda_{i}(f):=\arg\min_{q\in[0,2K]^{|\mathcal{P}_{i}|}}\Phi_{i}(q,f).
P∗∈arg⁡maxP∈𝒫i​{aP−(q1∧q2)P}.P^{*}\in\arg\max_{P\in\mathcal{P}_{i}}\{a_{P}-(q^{1}\wedge q^{2})_{P}\}.
h⁡(q1∧q2)=aP∗−qP∗1≤h⁡(q1).h(q^{1}\wedge q^{2})=a_{P^{*}}-q^{1}_{P^{*}}\leq h(q^{1}).
h⁡(q1∨q2)+h⁡(q1∧q2)≤h⁡(q1)+h⁡(q2).h(q^{1}\vee q^{2})+h(q^{1}\wedge q^{2})\leq h(q^{1})+h(q^{2}).

V-B 5 Computational Approach

Each fixed-flow assignment dual is convex and finite-dimensional, but the general outer welfare problem can remain nonconvex. Finite-dimensional characterization should not be read as an efficient global numerical algorithm.

VI Inducing Social Optima under Separable Utilities

Now specialize to value−latency, differentiable standard latencies with convex xℓ(x), and the constraint qualifications needed for KKT multipliers. Assignment depends only on destination masses once congestion cost is separated.

Equation
Ui​(vj,ℓP​(f))=vj−ℓP​(f).U_{i}(v_{j},\ell_{P}(f))=v_{j}-\ell_{P}(f).

VI-A Social Welfare Optimization Problem

Total congestion cost is ∑ₑfₑℓₑ(fₑ), independent of which types realize a fixed flow. The inner value now maximizes valuations alone and has one dual potential per outcome, not per strategy. Its optimal assignment chooses vⱼ−τᵢⱼ and yields outcome masses equal to threshold-region measures. The symbol Sᵢ is reused here for this valuation-only value; it excludes latency unlike its earlier definition.

Equations 9a–12
νf,i​(j):=νf,i​({j})=∑P∈𝒫i,jfP,j∈Di.\nu_{f,i}(j):=\nu_{f,i}(\{j\})=\sum_{P\in\mathcal{P}_{i,j}}f_{P},\qquad j\in D_{i}.
supf\displaystyle\sup_{f}\quad ∑i∈[k]𝒮i​(f)−∑P∈𝒫fP​ℓP​(f)\displaystyle\sum_{i\in[k]}\mathcal{S}_{i}(f)-\sum_{P\in\mathcal{P}}f_{P}\ell_{P}(f) (9a)
s.t. fP≥0,\displaystyle f_{P}\geq 0, ∀P∈𝒫,\displaystyle\forall P\in\mathcal{P}, (9b)
∑P∈𝒫ifP=ri,\displaystyle\sum_{P\in\mathcal{P}_{i}}f_{P}=r_{i}, ∀i∈[k],\displaystyle\forall i\in[k], (9c)
fe≤ce,\displaystyle f_{e}\leq c_{e}, ∀e∈E,\displaystyle\forall e\in E, (9d)
𝒮i(f):=supT:Vi→Di​ measurableT#​μi=νf,i∑j∈Di∫T−1​(j)vjdμi(v).\mathcal{S}_{i}(f):=\sup_{\begin{subarray}{c}T:V_{i}\to D_{i}\text{ measurable}\\ T_{\#}\mu_{i}=\nu_{f,i}\end{subarray}}\sum_{j\in D_{i}}\int_{T^{-1}(j)}v_{j}\,d\mu_{i}(v). (10)
Ui​(vj,ℓP​(f))=vj−ℓP​(f),U_{i}(v_{j},\ell_{P}(f))=v_{j}-\ell_{P}(f),
S​W​(a)\displaystyle SW(a) =∑i∈[k]∑P∈𝒫i∫a−1​(P)(vj−ℓP​(f))​d​μi​(v)\displaystyle=\sum_{i\in[k]}\sum_{P\in\mathcal{P}_{i}}\int_{a^{-1}(P)}\bigl(v_{j}-\ell_{P}(f)\bigr)\,d\mu_{i}(v)
=∑i∈[k]𝒮i​(f)−∑P∈𝒫fP​ℓP​(f).\displaystyle=\sum_{i\in[k]}\mathcal{S}_{i}(f)-\sum_{P\in\mathcal{P}}f_{P}\ell_{P}(f).
Φi​(p,f):=∫Vimaxj∈Di⁡(vj−pj)​d​μi​(v)+∑j∈Dipj​νf,i​(j).\Phi_{i}(p,f):=\int_{V_{i}}\max_{j\in D_{i}}(v_{j}-p_{j})\,d\mu_{i}(v)+\sum_{j\in D_{i}}p_{j}\nu_{f,i}(j). (11)
T⁡(v)∈arg⁡maxj∈Di​{vj−τi,j}T(v)\in\arg\max_{j\in D_{i}}\{v_{j}-\tau_{i,j}\}
𝒮i​(f)=∑j∈Di∫Vi,j​(τi)vj​d​μi​(v).\mathcal{S}_{i}(f)=\sum_{j\in D_{i}}\int_{V_{i,j}(\tau_{i})}v_{j}\,d\mu_{i}(v). (12)
∑j∈Diνf,i​(j)=ri=μi​(Vi),\sum_{j\in D_{i}}\nu_{f,i}(j)=r_{i}=\mu_{i}(V_{i}),

VI-B Comparative Statics and Convexity

The valuation-only value is a pointwise minimum of affine flow functions, hence concave. Danskin’s theorem describes its supergradients through optimal outcome potentials, repeated across strategies sharing an outcome. A singleton dual solution gives the stated differentiability result for the paper’s ambient concave extension. Subtracting convex total latency preserves a concave welfare objective over linear constraints, yielding a convex optimization problem. This conclusion requires more than merely nondecreasing latency.

Equations 13
Λi​(f):=arg⁡minp∈[0,2​K]|Di|​Φi​(p,f).\Lambda_{i}(f):=\arg\min_{p\in[0,2K]^{|D_{i}|}}\Phi_{i}(p,f).
𝒮~i​(x):=minp∈[0,2​K]|Di|⁡Φi​(p,x),x∈ℝ𝒫i,\widetilde{\mathcal{S}}_{i}(x):=\min_{p\in[0,2K]^{|D_{i}|}}\Phi_{i}(p,x),\qquad x\in\mathbb{R}^{\mathcal{P}_{i}},
∂𝒮i​(f)={g|∃λi∈Λi​(f)​ such thatgP=λi,j,∀j∈Di,∀P∈𝒫i,j}.\partial\mathcal{S}_{i}(f)=\left\{g\;\middle|\;\begin{array}[]{l}\exists\,\lambda_{i}\in\Lambda_{i}(f)\text{ such that}\\[2.84526pt] g_{P}=\lambda_{i,j},\quad\forall j\in D_{i},\ \forall P\in\mathcal{P}_{i,j}\end{array}\right\}.
∂𝒮i​(f)∂fP=λi,j,P∈𝒫i,j.\frac{\partial\mathcal{S}_{i}(f)}{\partial f_{P}}=\lambda_{i,j},\qquad P\in\mathcal{P}_{i,j}.
∂𝒮i​(f)=conv⁡{∇fΦi​(λi,f)|λi∈Λi​(f)}.\partial\mathcal{S}_{i}(f)=\operatorname{conv}\left\{\nabla_{f}\Phi_{i}(\lambda_{i},f)\;\middle|\;\lambda_{i}\in\Lambda_{i}(f)\right\}. (13)
∂Φi​(λi,f)∂fP=λi,j.\frac{\partial\Phi_{i}(\lambda_{i},f)}{\partial f_{P}}=\lambda_{i,j}.
∑P∈𝒫fP​ℓP​(f)=∑e∈Efe​ℓe​(fe).\sum_{P\in\mathcal{P}}f_{P}\ell_{P}(f)=\sum_{e\in E}f_{e}\ell_{e}(f_{e}).

VI-C First-Order Characterization of Social Optima

Theorem 3 combines a compatible optimal assignment potential τ with nonnegative capacity multipliers δ. Nonbinding resources have zero multiplier; every used path maximizes threshold value minus marginal-cost latency minus summed capacity prices. The proof derives these inequalities from KKT stationarity/complementarity and reconstructs the remaining multipliers for sufficiency. Without capacity limits the δ terms vanish, recovering marginal-cost optimality with heterogeneous destination choice.

Equations 14–19
ce>fe⟹δe=0;c_{e}>f_{e}\quad\Longrightarrow\quad\delta_{e}=0; (14)
τi,j−δP−ℓ^P​(f)≥τi,j′−δQ−ℓ^Q​(f),\tau_{i,j}-\delta_{P}-\hat{\ell}_{P}(f)\geq\tau_{i,j^{\prime}}-\delta_{Q}-\hat{\ell}_{Q}(f), (15)
β,δ≥0,\displaystyle\beta,\delta\geq 0, (16a)
βP​fP=0,\displaystyle\beta_{P}f_{P}=0, ∀P∈𝒫,\displaystyle\forall P\in\mathcal{P}, (16b)
δe​(ce−fe)=0,\displaystyle\delta_{e}(c_{e}-f_{e})=0, ∀e∈E,\displaystyle\forall e\in E, (16c)
(ℓ^P​(f)−βP+γi+δP)P∈𝒫i∈∂𝒮i​(f),\displaystyle\bigl(\hat{\ell}_{P}(f)-\beta_{P}+\gamma_{i}+\delta_{P}\bigr)_{P\in\mathcal{P}_{i}}\in\partial\mathcal{S}_{i}(f), ∀i∈[k].\displaystyle\forall i\in[k]. (16d)
τi,j−ℓ^P​(f)+βP−γi−δP=0,P∈𝒫i,j.\tau_{i,j}-\hat{\ell}_{P}(f)+\beta_{P}-\gamma_{i}-\delta_{P}=0,\qquad P\in\mathcal{P}_{i,j}. (17)
τi,j′−δQ−ℓ^Q​(f)=γi−βQ≤γi=τi,j−δP−ℓ^P​(f),\tau_{i,j^{\prime}}-\delta_{Q}-\hat{\ell}_{Q}(f)=\gamma_{i}-\beta_{Q}\leq\gamma_{i}=\tau_{i,j}-\delta_{P}-\hat{\ell}_{P}(f),
Pi∗∈arg⁡maxP∈𝒫i​{τi,j⁡(P)−ℓ^P​(f)−δP},P_{i}^{*}\in\arg\max_{P\in\mathcal{P}_{i}}\left\{\tau_{i,j(P)}-\hat{\ell}_{P}(f)-\delta_{P}\right\},
γi\displaystyle\gamma_{i} =τi,j⁡(Pi∗)−ℓ^Pi∗​(f)−δPi∗,\displaystyle=\tau_{i,j(P_{i}^{*})}-\hat{\ell}_{P_{i}^{*}}(f)-\delta_{P_{i}^{*}}, (18)
βP\displaystyle\beta_{P} =ℓ^P​(f)+δP+γi−τi,j⁡(P).\displaystyle=\hat{\ell}_{P}(f)+\delta_{P}+\gamma_{i}-\tau_{i,j(P)}. (19)
τi,j−ℓ^P​(f)≥τi,j′−ℓ^Q​(f).\tau_{i,j}-\hat{\ell}_{P}(f)\geq\tau_{i,j^{\prime}}-\hat{\ell}_{Q}(f).

VI-D Implementation of Social Optima

Fixed resource prices add to perceived latency. The resulting equilibrium flows maximize valuation-assignment value minus the Beckmann integral potential and the linear price bill. Setting perceived latency to ℓ+xℓ′ and prices to optimal capacity multipliers makes a selected social optimum an equilibrium of the unconstrained priced game. Equivalently, charge the congestion externality xℓ′ plus a capacity fee. This is a supporting-price existence result at an optimum, not a proof that every equilibrium under fixed prices is capacity-feasible or that a practical adaptive pricing process converges. Prices can be interpreted as monetary transfers or delays, but the original welfare objective does not separately add fee revenue or waiting costs.

Equations 20–23
ℓeδ​(fe):=ℓe​(fe)+δe.\ell_{e}^{\delta}(f_{e}):=\ell_{e}(f_{e})+\delta_{e}.
ui,v​(P,f)=vj−ℓP​(f)−δP.u_{i,v}(P,f)=v_{j}-\ell_{P}(f)-\delta_{P}. (20)
ℓP​(f)+δP≤ℓQ​(f)+δQ;\ell_{P}(f)+\delta_{P}\leq\ell_{Q}(f)+\delta_{Q};
∑P∈𝒫i,jfP=μi​(Vi,j​(τi)),\sum_{P\in\mathcal{P}_{i,j}}f_{P}=\mu_{i}(V_{i,j}(\tau_{i})),
supf\displaystyle\sup_{f}\quad ∑i∈[k]𝒮i(f)−∑e∈E\displaystyle\sum_{i\in[k]}\mathcal{S}_{i}(f)-\sum_{e\in E} (∫0feℓe​(x)​𝑑x+δe​fe)\displaystyle\left(\int_{0}^{f_{e}}\ell_{e}(x)\,dx+\delta_{e}f_{e}\right) (21a)
s.t. fP≥0,\displaystyle f_{P}\geq 0, ∀P∈𝒫,\displaystyle\quad\forall P\in\mathcal{P}, (21b)
∑P∈𝒫ifP=ri,\displaystyle\sum_{P\in\mathcal{P}_{i}}f_{P}=r_{i}, ∀i∈[k].\displaystyle\quad\forall i\in[k]. (21c)
C⁡(f):=∑e∈E(∫0feℓe​(x)​𝑑x+δe​fe).C(f):=\sum_{e\in E}\left(\int_{0}^{f_{e}}\ell_{e}(x)\,dx+\delta_{e}f_{e}\right).
λi,j−ℓP​(f)−δP≥λi,j′−ℓQ​(f)−δQ\lambda_{i,j}-\ell_{P}(f)-\delta_{P}\geq\lambda_{i,j^{\prime}}-\ell_{Q}(f)-\delta_{Q} (22)
0\displaystyle 0 =Φi​(λi,f)−𝒮i​(f)\displaystyle=\Phi_{i}(\lambda_{i},f)-\mathcal{S}_{i}(f)
=∫Vi[maxj′∈Di⁡{vj′−λi,j′}−(vTi​(v)−λi,Ti​(v))]​d​μi​(v).\displaystyle=\int_{V_{i}}\Bigl[\max_{j^{\prime}\in D_{i}}\{v_{j^{\prime}}-\lambda_{i,j^{\prime}}\}-\bigl(v_{T_{i}(v)}-\lambda_{i,T_{i}(v)}\bigr)\Bigr]\,d\mu_{i}(v).
vj−λi,j≥vj′−λi,j′,∀j′∈Di.v_{j}-\lambda_{i,j}\geq v_{j^{\prime}}-\lambda_{i,j^{\prime}},\qquad\forall j^{\prime}\in D_{i}. (23)
vj−ℓP​(f)−δP≥vj′−ℓQ​(f)−δQv_{j}-\ell_{P}(f)-\delta_{P}\geq v_{j^{\prime}}-\ell_{Q}(f)-\delta_{Q}
τi,j:=minP∈𝒫i,j⁡{ℓP​(f)+δP}.\tau_{i,j}:=\min_{P\in\mathcal{P}_{i,j}}\{\ell_{P}(f)+\delta_{P}\}.
𝒮i​(h)−𝒮i​(f)\displaystyle\mathcal{S}_{i}(h)-\mathcal{S}_{i}(f)
≤∑j∈Diτi,j​(νh,i​(j)−νf,i​(j))\displaystyle\leq\sum_{j\in D_{i}}\tau_{i,j}\bigl(\nu_{h,i}(j)-\nu_{f,i}(j)\bigr)
≤∑P∈𝒫i(ℓP​(f)+δP)​(hP−fP).\displaystyle\leq\sum_{P\in\mathcal{P}_{i}}\bigl(\ell_{P}(f)+\delta_{P}\bigr)(h_{P}-f_{P}).
C⁡(h)−C⁡(f)≥∑P∈𝒫(ℓP​(f)+δP)​(hP−fP).C(h)-C(f)\geq\sum_{P\in\mathcal{P}}\bigl(\ell_{P}(f)+\delta_{P}\bigr)(h_{P}-f_{P}).
∑i∈[k]𝒮i​(f)−∑e∈E(∫0feℓ^e​(x)​𝑑x+δe∗​fe)\sum_{i\in[k]}\mathcal{S}_{i}(f)-\sum_{e\in E}\left(\int_{0}^{f_{e}}\hat{\ell}_{e}(x)\,dx+\delta_{e}^{*}f_{e}\right)
∫0feℓ^e​(x)​𝑑x=fe​ℓe​(fe).\int_{0}^{f_{e}}\hat{\ell}_{e}(x)\,dx=f_{e}\ell_{e}(f_{e}).
∑i∈[k]𝒮i​(f)−∑e∈Efe​ℓe​(fe)+∑e∈Eδe∗​(ce−fe).\sum_{i\in[k]}\mathcal{S}_{i}(f)-\sum_{e\in E}f_{e}\ell_{e}(f_{e})+\sum_{e\in E}\delta_{e}^{*}(c_{e}-f_{e}).

VII Extensions

Two extensions cover coupled aggregate constraints and type distributions with atoms.

VII-A General Constraints

Continuous coupled constraints replace per-resource capacities, with a nonempty feasible-flow set assumed. The equilibrium characterization is restricted explicitly to constraint-feasible equilibria: a lower-bound violation may otherwise persist at an all-outside Nash profile because one infinitesimal entrant cannot change the deficient load. Inner assignment duality is unchanged. Convex differentiable constraints and standard latencies preserve convex welfare optimization; suitable constraint qualification supplies supporting multipliers.

Equation
ui,v​(ai,v,a−(i,v))\displaystyle u_{i,v}(a_{i,v},a_{-(i,v)})
={Ui​(vj,ℓP​(f)),ai,v=P∈𝒫i,j,P​ is feasible at ​f,−∞,otherwise.\displaystyle=\begin{cases}U_{i}(v_{j},\ell_{P}(f)),&a_{i,v}=P\in\mathcal{P}_{i,j},P\text{ is feasible at }f,\\ -\infty,&\text{otherwise}.\end{cases}

VII-B General Measures

An arbitrary finite type measure may put positive mass on one valuation vector. Represent actions by measurable kernels that split that type’s mass over strategies; constant probabilities fₚ/rᵢ realize any admissible flow. An atom here is a collection of infinitesimal identical agents, not an atomic strategic player. Positive-mass ties require split assignment rather than almost-everywhere unique outcome choice.

Equations
fP=∫Viai​(P∣v)​d​μi​(v),P∈𝒫i.f_{P}=\int_{V_{i}}a_{i}(P\mid v)\,d\mu_{i}(v),\qquad P\in\mathcal{P}_{i}.
∑P∈𝒫ifP=∫Vi∑P∈𝒫iai​(P∣v)​d​μi​(v)=ri.\sum_{P\in\mathcal{P}_{i}}f_{P}=\int_{V_{i}}\sum_{P\in\mathcal{P}_{i}}a_{i}(P\mid v)\,d\mu_{i}(v)=r_{i}.

VIII Conclusion

The paper provides structural and existence results linking multidimensional sorting, congestion and optimal transport. Applications include destination/vertiport allocation and supporting landing fees, under the separable assumptions. Price-of-anarchy bounds, reliable numerical methods and dynamic mechanisms that learn without knowing valuation distributions remain open. There are illustrative examples but no experimental performance claims or deployment evidence.

Acknowledgment

The authors disclose using GPT-6 Astra to help check and revise proofs in Sections V–VII and Appendix A. This is their stated assistance disclosure, not independent proof verification by this edition.

References

The original 51 bibliography entries are retained in the citations view, with linked references from the notes.

Appendix A Proof of Lemma 2

For any optimal dual vector, strong duality forces an optimal coupling onto reward-minus-potential maximizing targets. Disintegration yields measurable target-selection probabilities. Nonatomicity and Lyapunov’s convexity theorem purify this finite-target kernel into a deterministic selection with the same target masses. Integrating the resulting tight dual equality proves that the map is optimal. This mass-preserving purification, rather than arbitrary pointwise argmax selection, is the key exactness step.

Equations
supπ∈Π⁡(μ,ν)∫X×Yc⁡(x,j)​𝑑π​(x,j)\sup_{\pi\in\Pi(\mu,\nu)}\int_{X\times Y}c(x,j)\,d\pi(x,j)
infϕ,q{∫Xϕ⁡(x)​𝑑μ​(x)+∑j=1mqj​νj}\inf_{\phi,q}\left\{\int_{X}\phi(x)\,d\mu(x)+\sum_{j=1}^{m}q_{j}\nu_{j}\right\}
ϕ⁡(x)+qj≥c⁡(x,j),∀x∈X,j∈Y.\phi(x)+q_{j}\geq c(x,j),\qquad\forall x\in X,\ j\in Y.
ϕq​(x)=maxj∈Y⁡(c⁡(x,j)−qj).\phi_{q}(x)=\max_{j\in Y}\bigl(c(x,j)-q_{j}\bigr).
M⁡(x):=arg⁡maxj∈Y⁡(c⁡(x,j)−qj).M(x):=\arg\max_{j\in Y}\bigl(c(x,j)-q_{j}\bigr).
∫X×Yc⁡(x,j)​𝑑π​(x,j)=∫Xϕq​(x)​𝑑μ​(x)+∑j=1mqj​νj.\int_{X\times Y}c(x,j)\,d\pi(x,j)=\int_{X}\phi_{q}(x)\,d\mu(x)+\sum_{j=1}^{m}q_{j}\nu_{j}.
∫X×Y[ϕq​(x)+qj−c⁡(x,j)]​𝑑π​(x,j)=0.\int_{X\times Y}\left[\phi_{q}(x)+q_{j}-c(x,j)\right]d\pi(x,j)=0.
λj:X→[0,1],j∈Y,\lambda_{j}:X\to[0,1],\qquad j\in Y,
∫Xλj​(x)​𝑑μ​(x)=νj,j∈Y.\int_{X}\lambda_{j}(x)\,d\mu(x)=\nu_{j},\qquad j\in Y.
μ⁡(T−1​(j))=∫Xλj​(x)​𝑑μ​(x)=νj,j∈Y.\mu(T^{-1}(j))=\int_{X}\lambda_{j}(x)\,d\mu(x)=\nu_{j},\qquad j\in Y.
∫Xc⁡(x,T⁡(x))​𝑑μ​(x)\displaystyle\int_{X}c(x,T(x))\,d\mu(x) =∫Xϕq​(x)​𝑑μ​(x)+∑j=1mqj​μ​(T−1​(j))\displaystyle=\int_{X}\phi_{q}(x)\,d\mu(x)+\sum_{j=1}^{m}q_{j}\mu(T^{-1}(j))
=∫Xϕq​(x)​𝑑μ​(x)+∑j=1mqj​νj.\displaystyle=\int_{X}\phi_{q}(x)\,d\mu(x)+\sum_{j=1}^{m}q_{j}\nu_{j}.

Appendix B Some Single-Destination Examples

Three one-link examples separate classical routing, excessive participation from congestion externalities, and equilibrium nonexistence caused by a hard cap. Table I summarizes the interventions supporting the optima.

B-A First Example: Classical Routing Games

With unit population, ℓ(x)=x, capacity one and uniform values on [2,3], everyone travels. The unique equilibrium also maximizes welfare, giving 3/2, so no price intervention is needed.

sst1t_{1}r=1r=1c1=1​ or ​1/2ℓ1​(x)=x\begin{aligned} &c_{1}=1\text{ or }1/2\\ &\ell_{1}(x)=x\end{aligned}
Fig. 2: A one-link network with total traffic r=1r=1, latency function ℓ1​(x)=x\ell_{1}(x)=x, and capacity c1c_{1}. This network is used throughout Examples 2, 3 and 4.
TABLE I: Pricing interventions that induce a socially optimal flow in Examples 2, 3 and 4.
Example Valuation distribution Capacity Pricing intervention
Example 2 Unif⁡([2,3])\operatorname{Unif}([2,3]) c1=1c_{1}=1 none
Example 3 Unif⁡([0,1])\operatorname{Unif}([0,1]) c1=1c_{1}=1 marginal-cost toll t1​(x)=xt_{1}(x)=x
Example 4 Unif⁡([2,3])\operatorname{Unif}([2,3]) c1=1/2c_{1}=1/2 marginal-cost toll and capacity fee t1​(x)=xt_{1}(x)=x, δ∗=3/2\delta^{*}=3/2

B-B Second Example: Heterogeneous Valuations and Marginal-Cost Tolling

With values uniform on [0,1], equilibrium routes the upper half of values, so flow is 1/2. Welfare is maximized at cutoff 2/3 and flow 1/3. Replacing perceived latency x by marginal cost 2x, equivalently adding toll x, implements that optimum.

B-C Third Example: Capacity Constraints and Capacity Fees

Keep values uniform on [2,3] but cap flow at 1/2. Below or at capacity, an excluded infinitesimal agent wants to enter without changing aggregate load; above capacity, travelers prefer the outside option. Thus the stated Nash notion has no equilibrium. The welfare optimum serves the upper-valued half, cutoff 5/2. With W(x)=3x−(3/2)x², the capacity multiplier is W′(1/2)=3/2. Add marginal toll x plus that capacity fee: total perceived cost is 2x+3/2, inducing flow 1/2. At the optimum, monetary charges total two, distinct from total perceived cost 5/2 including physical latency.

Equations
W⁡(x)=∫3−x3v​𝑑v−x​ℓ1​(x)=3​x−32​x2.W(x)=\int_{3-x}^{3}v\,dv-x\ell_{1}(x)=3x-\frac{3}{2}x^{2}.
δ∗=W′​(x∗)=3−3​x∗=32.\delta^{*}=W^{\prime}(x^{*})=3-3x^{*}=\frac{3}{2}.
ℓ1​(x)+t1​(x)+δ∗=ℓ^1​(x)+δ∗=2​x+32.\ell_{1}(x)+t_{1}(x)+\delta^{*}=\hat{\ell}_{1}(x)+\delta^{*}=2x+\frac{3}{2}.

B-D Relationship with Existing Single-Destination Traffic Assignment Models

Equilibrium terminology changes the answer to existence questions. The appendix relates the paper’s individual-deviation Nash notion to established elastic-demand and capacitated traffic-assignment notions.

B-D 1 Routing Games with Elastic Demand

Without capacity constraints and with one real destination plus an outside option, the equilibrium agrees with standard elastic-demand routing. The explicit continuum of heterogeneous values provides the individual-choice basis for its aggregate demand formulation.

B-D 2 Routing Games with Edge Capacity Constraints

A capacitated user equilibrium excludes profitable deviations by positive-mass sets, allowing binding capacity to block a move. A BMW equilibrium minimizes the Beckmann potential over capacity-feasible flows. Every Nash equilibrium here is BMW, and every BMW equilibrium is a capacitated user equilibrium; both inclusions are strict. Integrating individual latency inequalities gives the BMW variational inequality. Replacing the outside option in the capped example by a constant-cost-one edge gives a BMW half/half flow that is not Nash, since a zero-mass traveler can still switch to the cheaper capped edge. The finite-feasible-set optimization notion has existence even where individual-deviation Nash fails.

Equations 24a–24e
f~P={fP−δ, if ​P=P1fP+δ, if ​P=P2fP, if ​P∉{P1,P2},\tilde{f}_{P}=\begin{cases}f_{P}-\delta,&\text{ if }P=P_{1}\\ f_{P}+\delta,&\text{ if }P=P_{2}\\ f_{P},&\text{ if }P\notin\{P_{1},P_{2}\},\end{cases}
minf\displaystyle\min_{f}\quad ∑e∈E∫0feℓe​(x)​𝑑x\displaystyle\sum_{e\in E}\int_{0}^{f_{e}}\ell_{e}(x)dx (24a)
  s.t. fP≥0,∀P∈𝒫\displaystyle f_{P}\geq 0,\forall P\in\mathcal{P} (24b)
∑P∈𝒫ifP=ri,∀i∈[k]\displaystyle\sum_{P\in\mathcal{P}_{i}}f_{P}=r_{i},\forall i\in[k] (24c)
fe≤ce,∀e∈E\displaystyle f_{e}\leq c_{e},\forall e\in E (24d)
fe=∑P∈𝒫:e∈PfP,∀e∈E.\displaystyle f_{e}=\sum_{P\in\mathcal{P}:e\in P}f_{P},\forall e\in E. (24e)
u_{i,v}(a_{i,v},a_{-(i,v)}) ≥ u_{i,v}(b_{i,v},a_{-(i,v)}).
Σ_{P∈𝒫} ℓ_P(f) f_P ≤ Σ_{P∈𝒫} ℓ_P(f) g_P.
Σ_{P∈𝒫} ℓ_P(f) (g_P−f_P) ≥ 0.
Capacitated user equilibrium ( Definition 9 ) ∙ \bullet [ 1 , Example 4.3.3] Nash equilibrium ( Definition 5 ) BMW equilibrium ( Definition 10 ) ∙ \bullet (Modified) Example 4
Fig. 3: Relationship among the three equilibrium notions for routing games with edge-capacity constraints. The cited examples show that each inclusion is strict.

Appendix C Basics of Lattice Theory

Under componentwise order, joins and meets are coordinatewise maxima and minima. Submodular minimizers form a sublattice; a nonempty compact sublattice of Euclidean space is complete. These facts justify extremal bounded dual-potential selections, without requiring the optimizer to be unique.

Equations
x1∨x2,x1∧x2∈X′∀x1,x2∈X′,x^{1}\vee x^{2},\;x^{1}\wedge x^{2}\in X^{\prime}\qquad\forall x^{1},x^{2}\in X^{\prime},
f⁡(x1∨x2)+f⁡(x1∧x2)≥f⁡(x1)+f⁡(x2)f(x^{1}\vee x^{2})+f(x^{1}\wedge x^{2})\geq f(x^{1})+f(x^{2})

Appendix D Details of the Extensions

The extensions preserve the inner transport structure while altering either feasible aggregate flows or the representation of individual type mass.

D-A General Constraints

At an optimal flow, multiply each differentiable aggregate-constraint gradient by its KKT multiplier and sum to obtain a fixed resource price. Add this price to marginal-cost latency to support the optimum in an unconstrained priced game. General constraints can produce negative prices, interpreted as subsidies; coordinatewise nondecreasing constraints give nonnegative prices. The argument assumes a constraint qualification such as relative Slater feasibility.

Equations
qe∗:=∑g∈𝒞ηg∗​∂g∂fe​(fE∗),e∈E.q_{e}^{*}:=\sum_{g\in\mathcal{C}}\eta_{g}^{*}\frac{\partial g}{\partial f_{e}}(f_{E}^{*}),\qquad e\in E.
ℓ^e​(x)+qe∗=ℓe​(x)+x​ℓe′​(x)+qe∗.\hat{\ell}_{e}(x)+q_{e}^{*}=\ell_{e}(x)+x\ell_{e}^{\prime}(x)+q_{e}^{*}.

D-B General Measures

For general type measures, a destination kernel must put weight only on best-response outcomes and reproduce their target masses. A strategy kernel similarly disintegrates an optimal transport coupling and is supported on dual maximizers. The finite dual characterization remains, but a deterministic map may no longer exist. The original author portraits and biographies following this appendix are retained.

Equations
Bi​(v,τi):=arg⁡maxj∈Di​Ui​(vj,τi,j).B_{i}(v;\tau_{i}):=\arg\max_{j\in D_{i}}U_{i}(v_{j},\tau_{i,j}).
Vi,j​(τi)={v∈Vi:j∈Bi​(v,τi)}V_{i,j}(\tau_{i})=\{v\in V_{i}:j\in B_{i}(v;\tau_{i})\}
κi​(j∣v)>0⟹j∈Bi​(v,τi)\kappa_{i}(j\mid v)>0\quad\Longrightarrow\quad j\in B_{i}(v;\tau_{i})
∑P∈𝒫i,jfP=∫Viκi​(j∣v)​d​μi​(v),∀j∈Di.\sum_{P\in\mathcal{P}_{i,j}}f_{P}=\int_{V_{i}}\kappa_{i}(j\mid v)\,d\mu_{i}(v),\qquad\forall j\in D_{i}.
∑P∈𝒫i,jfP=μi​(Vi,j​(τi)),∀j∈Di,\sum_{P\in\mathcal{P}_{i,j}}f_{P}=\mu_{i}(V_{i,j}(\tau_{i})),\qquad\forall j\in D_{i},
πi​(d​v,{P})=μi​(d​v)​κi​(P∣v).\pi_{i}(dv,\{P\})=\mu_{i}(dv)\kappa_{i}(P\mid v).
∫Viκi​(P∣v)​d​μi​(v)=fP,P∈𝒫i.\int_{V_{i}}\kappa_{i}(P\mid v)\,d\mu_{i}(v)=f_{P},\qquad P\in\mathcal{P}_{i}.
[Uncaptioned image] Pan-Yang Su (Student Member, IEEE) received the B.S. degree in electrical engineering from National Taiwan University, Taipei, Taiwan, in 2022. He is currently pursuing the Ph.D. degree with the Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, Berkeley, CA, USA. His research focuses on applying game theory and mechanism design techniques to study multi-agent systems, with applications in energy and transportation.
[Uncaptioned image] Negar Mehr (Member, IEEE) received the B.S. degree in mechanical engineering from Sharif University of Technology, Tehran, Iran, in 2013, and the Ph.D. degree in mechanical engineering from the University of California, Berkeley, Berkeley, CA, USA, in 2019. From 2019 to 2020, she was a Postdoctoral Scholar in Aeronautics and Astronautics at Stanford University, Stanford, CA, USA. She then served as an Assistant Professor of Aerospace Engineering at the University of Illinois Urbana-Champaign, Urbana, IL, USA, before joining the University of California, Berkeley, in 2024. She is currently an Assistant Professor of Mechanical Engineering and directs the Berkeley Intelligent Control (ICON) Laboratory. Her research interests include control theory, game theory, and machine learning, with an emphasis on safe and intelligent interactions among robots, humans, and other autonomous agents. Dr. Mehr is a recipient of the AFOSR Young Investigator Award, the ONR Young Investigator Award, the NSF CAREER Award, the ASME Rising Star Award, and the IEEE ITSS Best Ph.D. Dissertation Award.
[Uncaptioned image] Shankar Sastry (Life Fellow, IEEE) is a Professor of EECS, Bioengineering and Mechanical Engineering and the Siebel Professor of Computer Science and Engineering at the University of California Berkeley. He was the Dean of Engineering from 2007-18. He is currently the faculty Director of the Technology Competitiveness and Industrial Policy, a center which conducts studies on policy need to enhance US competitiveness and the FHL Vive Center for Enhanced Reality for exploring the boundaries between augmented reality and real scenes with applications to autonomy, performance arts, and education. He is the honorary chancellor of a new technical university in Chandigarh, India called Plaksha University. He is deeply committed to harnessing the power of technology to lift people out of poverty through his directorship of the Blum Center for Developing Economies 2007-22. He has coauthored about 750 technical papers. He has co-authored or co-edited 10 books, including Adaptive Control: Stability, Convergence and Robustness (with M. Bodson, Prentice Hall, 1989) and A Mathematical Introduction to Robotic Manipulation (with R. Murray and Z. Li, CRC Press, 1994), Nonlinear Systems: Analysis, Stability and Control (Springer-Verlag, 1999), and An Invitation to 3D Vision: From Images to Models (Springer Verlag, 2003) (with Y. Ma. S. Soatto, and J. Kosecka). and Generalized Principal Component Analysis (Springer Verlag, 2016 with R. Vidal and Y. Ma). Dr. Sastry was elected to the National Academy of Engineering in 2001 the American Academy of Arts and Sciences in 2004. He received the President of India Gold Medal in 1977, the NSF Presidential Young Investigator Award in 1985. He got the Eckman Award of the American Automatic Control Council in 1990, the Ragazzini Award for Distinguished Accomplishments in teaching in 2005 and the Rufus Oldenburger Career Award of ASME in 2021. He has received honorary doctorates from KTH, the Royal Institute of Technology, Stockholm, a Ph.D. honoris causa from the University of Waterloo, Canada, and a Laurea Dottorato honoris causa from Politecnico di Torino, and the Berkeley Citation. He has supervised more than 75 doctoral students to completion and over 50 Masters of Science Students and is very proud of the leadership positions that they hold in academia and industry.
Concept demonstration

Open image ↗