Congestion Games with Heterogeneous Valuations: An Optimal Transport Approach
Abstract
In emerging urban mobility and logistics applications, such as advanced air mobility, electric vehicle charging, and shared service systems, agents with heterogeneous valuations choose among multiple outcomes while sharing congested resources. Existing congestion game and resource-allocation models, however, typically restrict either the structure of heterogeneous outcome preferences or the form of congestion externalities. We introduce a nonatomic congestion game framework in which agents have multidimensional heterogeneous valuations over a finite set of outcomes, with the population represented by a measure over the valuation space. We show that, although there is a continuum of heterogeneous agents, both Nash equilibria and social optima admit finite-dimensional characterizations. Nash equilibria are characterized by aggregate flows and outcome-level threshold vectors, while social optima admit a semi-discrete optimal transport formulation characterized by aggregate flows and strategy-level Kantorovich dual potentials. For separable utilities and latency functions ℓe such that x↦ xℓe(x) is convex for every resource e, the social welfare problem becomes a convex optimization problem, and we characterize social optima through marginal congestion costs and capacity-dual prices. Our results provide a geometric characterization of congestion games with multidimensional heterogeneous valuations and connect nonatomic congestion games with semi-discrete optimal transport.
Related
- Monotonicity, Uniqueness and Frank--Wolfe Dynamics in Atomic Splittable Congestion Games
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Non-Potential Congestion Games with a Continuum of Players
- Characterizing Heterogeneous Rates in Finite Mixture Estimation via Partial Optimal Transport
- Bayesian Equilibria of Heterogeneous Non-Atomic Routing Games With Private Information
BibTeX
@misc{su2026congestion,
title = {{Congestion Games with Heterogeneous Valuations: An Optimal Transport Approach}},
author = {Pan-Yang Su and Negar Mehr and Shankar Sastry},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.03625},
eprint = {2607.03625},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.03625},
}
RIS
TY - UNPB
TI - Congestion Games with Heterogeneous Valuations: An Optimal Transport Approach
AU - Pan-Yang Su
AU - Negar Mehr
AU - Shankar Sastry
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2607.03625
UR - https://arxiv.org/abs/2607.03625
AB - In emerging urban mobility and logistics applications, such as advanced air mobility, electric vehicle charging, and shared service systems, agents with heterogeneous valuations choose among multiple outcomes while sharing congested resources. Existing congestion game and resource-allocation models, however, typically restrict either the structure of heterogeneous outcome preferences or the form of congestion externalities. We introduce a nonatomic congestion game framework in which agents have multidimensional heterogeneous valuations over a finite set of outcomes, with the population represented by a measure over the valuation space. We show that, although there is a continuum of heterogeneous agents, both Nash equilibria and social optima admit finite-dimensional characterizations. Nash equilibria are characterized by aggregate flows and outcome-level threshold vectors, while social optima admit a semi-discrete optimal transport formulation characterized by aggregate flows and strategy-level Kantorovich dual potentials. For separable utilities and latency functions ℓ_e such that x↦ xℓ_e(x) is convex for every resource e, the social welfare problem becomes a convex optimization problem, and we characterize social optima through marginal congestion costs and capacity-dual prices. Our results provide a geometric characterization of congestion games with multidimensional heterogeneous valuations and connect nonatomic congestion games with semi-discrete optimal transport.
ER -