The Price of Anarchy for Instantaneous Dynamic Equilibria

DOI10.1287/MOOR.2022.1336MaRDI QIDQ6122579zbMATH OpenOpenAlexFDO

Authors Lukas Graf, Tobias Harks

Publication date 1 March 2024

Published in Mathematics of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

dynamic traffic assignmentequilibriaflows over timeprice of anarchyVickrey model

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Queues and service in operations research (90B22)

Abstract: We consider flows over time within the deterministic queueing model and study the solution concept of instantaneous dynamic equilibrium (IDE) in which flow particles select at every decision point a currently shortest path. The length of such a path is measured by the physical travel time plus the time spent in queues. Although IDE have been studied since the eighties, the efficiency of the solution concept is not well understood. We study the price of anarchy for this model and show an upper bound of order $mathcalO(Ucdotau)$ for single-sink instances, where $U$ denotes the total inflow volume and $au$ the sum of edge travel times. We complement this upper bound with a family of quite complex instances proving a lower bound of order $Omega(Ucdotlogau)$.

Recommendations

• The price of anarchy for instantaneous dynamic equilibria
• On the price of anarchy for flows over time
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• Dynamic flows with adaptive route choice

Cited in

(2)

• The price of anarchy for instantaneous dynamic equilibria
• Bounding the price of anarchy for mixed traffic equilibrium assignment with stochastic demands and road pricing

This page was built for publication: The Price of Anarchy for Instantaneous Dynamic Equilibria

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