Articles

Dynamic Atomic Congestion Games with Seasonal Flows

M. SCARSINI, M. SCHÖDER, T. TOMALA

Operations Research

mars-avril 2018, vol. 66, n°2, pp.327-339

Départements : Economie et Sciences de la décision, GREGHEC (CNRS)

Mots clés : network games, dynamic flows, price of anarchy, price of stability, Braess ratio, max-flow min-cut

https://pubsonline.informs.org/doi/pdf/10.1287/opre.2017.1683


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 by 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 coincides, but the selfish behavior of the first players has consequences that cannot be undone and are paid by all future generations. In more general topologies, our main contributions are three-fold. First, we show that equilibria are usually not unique. In particular, we prove that there exists a sequence of networks such that the price of anarchy is equal to n-1, where n is the number of vertices, and the price of stability is equal to 1.Second, we illustrate a new dynamic version of Braess's paradox: the presence of initial queues in a network may decrease the long-run costs in equilibrium. This paradox may arise even in networks for which no Braess's paradox was previously known.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. This measure is the increase in costs compared to uniform departures for optimal and equilibrium flows in parallel networks


JavaScriptSettings