The impact of spillback on the price of anarchy for flows over time

DOI10.1007/978-3-030-57980-7_8zbMATH Open1506.91033arXiv2007.04218OpenAlexW3091166571MaRDI QIDQ2109953FDOQ2109953

Authors: Jonas Israel, Leon Sering 

Publication date: 21 December 2022

Abstract: Flows over time enable a mathematical modeling of traffic that changes as time progresses. In order to evaluate these dynamic flows from a game theoretical perspective we consider the price of anarchy (PoA). In this paper we study the impact of spillback effects on the PoA, which turn out to be substantial. It is known that, in general, the PoA is unbounded in the spillback setting. We extend this by showing that it is still unbounded even when considering networks with unit edge capacities and that the Braess ratio can be arbitrarily large. In contrast to that, we show that on a fixed network the PoA as a function of the flow amount is bounded by a constant and also upper bound the PoA for the set of networks where the outflow capacities satisfy certain constraints depending on the quickest flow. This upper bound only depends on the worst spillback factor of the Nash flows over time of the given network. It therefore provides a way to quantify the impact of spillback to the quality of the dynamic equilibria. In addition, we show the surprising fact that the introduction of spillback behavior can actually speed up dynamic equilibria in some networks.

Full work available at URL: https://arxiv.org/abs/2007.04218

Recommendations

• On the price of anarchy for flows over time
• Nash equilibria and the price of anarchy for flows over time
• Nash equilibria and the price of anarchy for flows over time
• Nash flows over time with spillback
• The toll effect on price of anarchy when costs are nonlinear and asymmetric
• Price of anarchy in congestion games with altruistic/spiteful players
• The price of anarchy for instantaneous dynamic equilibria
• Analysis of Price of Total Anarchy in Congestion Games via Smoothness Arguments
• Price of Anarchy in Networks with Heterogeneous Latency Functions
• The price of anarchy of serial, average and incremental cost sharing

zbMATH Keywords

price of anarchytrafficspillbackdynamic equilibriadeterministic queuingNash flow over time

Mathematics Subject Classification ID

Potential and congestion games (91A14) Algorithmic game theory and complexity (91A68)

This page was built for publication: The impact of spillback on the price of anarchy for flows over time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109953)