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

Zijun Wu () and Rolf H. Möhring ()
Additional contact information
Zijun Wu: Institute for Applied Optimization, School of Artificial Intelligence and Big Data, Hefei University, Hefei, Anhui 230601, China
Rolf H. Möhring: Institute for Applied Optimization, School of Artificial Intelligence and Big Data, Hefei University, Hefei, Anhui 230601, China; Institute of Mathematics, Technische Universität Berlin, 10623 Berlin, Germany

Mathematics of Operations Research, 2023, vol. 48, issue 3, 1364-1392

Abstract: 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 Hölder continuous function of the demands and cost functions, and we analyze the Hölder 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.

Keywords: Primary: 91A10; 91A14; 91A68; 05C57; 90B06; 90B20; nonatomic congestion games; inefficiency of equilibria; price of anarchy; sensitivity analysis of the price of anarchy; topological spaces of games; convergence analysis of the price of anarchy (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.1292 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:48:y:2023:i:3:p:1364-1392

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().