Operations Research 2025
Abstract Submission

2366. Are System Optimal Dynamic Flows Implementable by Tolls?

Invited abstract in session FA-8: Game Theory and Strategic Behavior in Real-World Systems, stream Game Theory and Behavioral Management Science.

Friday, 8:45-10:15
Room: H8

Authors (first author is the speaker)

1. Lukas Graf
University of Passau
2. Tobias Harks
University of Passau
3. Julian Schwarz
University of Passau

Abstract

In two seminal papers by Fleischer, Jain and Mahdian and Karakostas and Kolliopulos presented at FOCS 2004, it was shown that system optimal static flows can always be implemented by tolls. That is, there exist tolls on the edges such that the given flow becomes a Wardrop equilibrium. This result holds even for the case of multiple commodities with heterogeneous value-of-time sensitivities.
For the much more complex setting of dynamic flows, we recently identified necessary and sufficient conditions for such flows over time to be implementable by time dependent edge tolls. However, whether system optimal dynamic flows are among those implementable flows is far from obvious.

We now consider this question of implementability of system optimal flows for a general dynamic flow model involving multiple commodities with individual source-sink pairs, fixed inflow rates and heterogeneous valuations of travel time and money spent. We present both a positive and a, perhaps surprising, negative result:
For the negative result, we provide a network with multiple source and sink pairs in which under the Vickrey queuing model no system optimal flow is implementable - even if all users value travel times and spent money the same. Our counter-example even shows that the ratio of the achievable equilibrium travel times by using tolls and the system optimal travel times can be unbounded.
For the single-source, single-sink case, we show that if the traversal time functions are suitably well-behaved (as is the case, for example, in the Vickrey queuing model), any system optimal flow is implementable.

Keywords

Status: accepted

Back to the list of papers