Dynamic Atomic Congestion Games with Seasonal Flows

• 成果类型: Article
• 署名作者: Scarsini, Marco; Schroder, Marc; Tomala, Tristan
• 署名单位: Luiss Guido Carli University; RWTH Aachen University; Hautes Etudes Commerciales (HEC) Paris
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2017.1683
• 发表日期: 2018
• 页码: 327-339
• 关键词: traffic equilibrium assignment; braesss paradox; networks; CONVERGENCE; algorithm; price; cost; fair

摘要

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.