We propose a model of discrete time dynamic congestion games with atomic players and a single source-destination pair. The latencies of edges are composed of free-flow transit times and possible queuing time due to capacity constraints. We give a precise description of the dynamics induced by the individual strategies of players and of the corresponding costs, either when the traffic is controlled by a planner, or when players act selfishly. In parallel networks, optimal and equilibrium behavior eventually coincide, but the selfish behavior of the initial players has consequences that cannot be undone and are paid by all future generations. In more general topologies, our main contributions are threefold. First, we illustrate a new dynamic version of Braess paradox: the presence of initial queues in the network may decrease the long-run costs in equilibrium. This paradox can arise in networks for which no Braess paradox was previously known. Second, we show that equilibria are not unique and can induce very different long-run costs. In particular, we give a sequence of networks such that the price of stability is equal to 1, and the price of anarchy is equal to n − 1, where n is the number of vertices. Third, we propose an extension to model seasonalities by assuming that departure flows fluctuate periodically over time. We introduce a measure that captures the queues induced by periodicity of inflows. For optimal and equilibrium flows in parallel networks this measure is the increase in cost compared to uniform departures.

Dynamic Atomic Congestion Games with Seasonal Flows / Scarsini, Marco; Schröder, Marc; Tomala, Tristan. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - 66:2(2018), pp. 327-339. [10.1287/opre.2017.1683]

Dynamic Atomic Congestion Games with Seasonal Flows

Scarsini, Marco;
2018

Abstract

We propose a model of discrete time dynamic congestion games with atomic players and a single source-destination pair. The latencies of edges are composed of free-flow transit times and possible queuing time due to capacity constraints. We give a precise description of the dynamics induced by the individual strategies of players and of the corresponding costs, either when the traffic is controlled by a planner, or when players act selfishly. In parallel networks, optimal and equilibrium behavior eventually coincide, but the selfish behavior of the initial players has consequences that cannot be undone and are paid by all future generations. In more general topologies, our main contributions are threefold. First, we illustrate a new dynamic version of Braess paradox: the presence of initial queues in the network may decrease the long-run costs in equilibrium. This paradox can arise in networks for which no Braess paradox was previously known. Second, we show that equilibria are not unique and can induce very different long-run costs. In particular, we give a sequence of networks such that the price of stability is equal to 1, and the price of anarchy is equal to n − 1, where n is the number of vertices. Third, we propose an extension to model seasonalities by assuming that departure flows fluctuate periodically over time. We introduce a measure that captures the queues induced by periodicity of inflows. For optimal and equilibrium flows in parallel networks this measure is the increase in cost compared to uniform departures.
network games, dynamic flows, price of anarchy, price of stability, Braess ratio, max-flow min-cut
Dynamic Atomic Congestion Games with Seasonal Flows / Scarsini, Marco; Schröder, Marc; Tomala, Tristan. - In: OPERATIONS RESEARCH. - ISSN 0030-364X. - 66:2(2018), pp. 327-339. [10.1287/opre.2017.1683]
File in questo prodotto:
File Dimensione Formato  
OR2018SST-sm.pdf

Solo gestori archivio

Descrizione: supplementary material
Tipologia: Altro materiale allegato
Licenza: Tutti i diritti riservati
Dimensione 330.39 kB
Formato Adobe PDF
330.39 kB Adobe PDF   Visualizza/Apri
OR2018SST.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: Tutti i diritti riservati
Dimensione 572.75 kB
Formato Adobe PDF
572.75 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/177954
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 10
social impact