Routing games over time with FIFO policy

DOI10.1007/978-3-319-71924-5_19MaRDI QIDQ4614077zbMATH OpenOpenAlexFDO

Authors Anisse Ismaili

Publication date 30 January 2019

Published in Web and Internet Economics (Search for Journal in Brave)

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

zbMATH Keywords

complexityprice of anarchyrouting games over time

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Noncooperative games (91A10) Games involving graphs (91A43)

Abstract: We study atomic routing games where every agent travels both along its decided edges and through time. The agents arriving on an edge are first lined up in a emph{first-in-first-out} queue and may wait: an edge is associated with a capacity, which defines how many agents-per-time-step can pop from the queue's head and enter the edge, to transit for a fixed delay. We show that the best-response optimization problem is not approximable, and that deciding the existence of a Nash equilibrium is complete for the second level of the polynomial hierarchy. Then, we drop the rationality assumption, introduce a behavioral concept based on GPS navigation, and study its worst-case efficiency ratio to coordination.

Recommendations

• Competitive routing over time
• Nash equilibria and the price of anarchy for flows over time
• Atomic dynamic flow games: adaptive vs. nonadaptive agents
• Nash equilibria and the price of anarchy for flows over time
• A Stackelberg strategy for routing flow over time

Cited in

(9)

• FIFO and randomized competitive packet routing games
• Approximation algorithms for the generalized incremental knapsack problem
• Atomic dynamic flow games: adaptive vs. nonadaptive agents
• On the price of anarchy for flows over time
• Bounding Residence Times for Atomic Dynamic Routings
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• Dynamic flows with adaptive route choice
• A finite time combinatorial algorithm for instantaneous dynamic equilibrium flows
• Atomic dynamic routing games with multiple destinations

This page was built for publication: Routing games over time with FIFO policy

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