EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1060. Bicriteria Nash Flows over Time

Invited abstract in session TA-36: Game Theory, Solutions and Structures V, stream Game Theory, Solutions and Structures.

Tuesday, 8:30-10:00
Room: 32 (building: 306)

Authors (first author is the speaker)

1. Tim Oosterwijk
Operations Analytics, Vrije Universiteit Amsterdam
2. Daniel Schmand
University of Bremen
3. Marc Schröder
Quantitative Economics, Maastricht University

Abstract

Traffic congestion imposes a huge economic loss. As such, there has been a huge effort to understand congestion using theoretical models. The dynamic model that gained most attention is the deterministic fluid queuing model.
A common drawback of most models is that users only aim for minimizing their arrival time. However, users are not always that single-minded. We extend the state-of-the-art game theoretic traffic models with a multi-criteria objective function. We assume that users try to minimize costs subject to arriving at the sink before a given deadline. Here, costs could be thought of as an intrinsic preference regarding different route choices and queuing dynamics only play a role for the arrival time.
We determine the existence and structure of Nash flows over time and fully characterize the price of anarchy for this model, which measures the ratio of the quality of the Nash flow and the optimal flow. We evaluate the quality both with respect to the throughput for a given deadline and the makespan for a given amount of flow. We prove the following results. (1) In series-parallel graphs, both prices of anarchy are unbounded. (2) In parallel path graphs the throughput-PoA is at most 2, or at most e/(e-1) if all transit times are 0. Both bounds are tight. (3) In parallel path graphs the makespan-PoA is at most e/(e-1), independent of transit times, and this is tight. All our upper bounds are also valid for dynamic equilibria in the deterministic fluid queuing model.

Keywords

Status: accepted

Back to the list of papers