A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games

• 成果类型: Article
• 署名作者: Wu, Zijun; Moehring, Rolf H.
• 署名单位: Hefei University; Technical University of Berlin
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1292
• 发表日期: 2023
• 页码: 1364-1392
• 关键词: traffic equilibrium; INEFFICIENCY; networks

摘要

The price of anarchy (PoA) is a standard measure to quantify the inefficiency of equilibria in nonatomic congestion games. Most publications have focused on worst-case bounds for the PoA. Only a few have analyzed the sensitivity of the PoA against changes of the demands or cost functions, although that is crucial for empirical computations of the PoA. We analyze the sensitivity of the PoA with respect to (w.r.t.) simultaneous changes of demands and cost functions. The key to this analysis is a metric for the distance between two games that defines a topological metric space consisting of all games with the same combinatorial structure. The PoA is then a locally pointwise Holder continuous function of the demands and cost functions, and we analyze the Holder exponent for different classes of cost functions. We also apply our approach to the convergence analysis of the PoA when the total demand tends to zero or infinity. Our results further develop the recent seminal work on the sensitivity of the PoA w.r.t. changes of only the demands under special conditions.