When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

• 成果类型: Article
• 署名作者: Colini-Baldeschi, Riccardo; Cominetti, Roberto; Mertikopoulos, Panayotis; Scarsini, Marco
• 署名单位: Facebook Inc; Universidad Adolfo Ibanez; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Luiss Guido Carli University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1894
• 发表日期: 2020
• 页码: 411-434
• 关键词: nonatomic congestion games; Price of anarchy; light traffic; heavy traffic; Regular Variation

摘要

This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin/destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the following question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain a positive distance away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials) and inflow patterns, the price of anarchy does converge to 1 in both heavy and light traffic, irrespective of the network topology and the number of O/D pairs in the network. We also examine the rate of convergence of the price of anarchy, and we show that it follows a power law whose degree can be computed explicitly when the network's cost functions are polynomials.