IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v48y2023i3p1364-1392.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • Zijun Wu & Rolf H. Möhring, 2023. "A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games," Mathematics of Operations Research, INFORMS, vol. 48(3), pages 1364-1392, August.
    • Handle: RePEc:inm:ormoor:v:48:y:2023:i:3:p:1364-1392
    DOI: 10.1287/moor.2022.1292
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2022.1292
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2022.1292?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:ormoor:v:48:y:2023:i:3:p:1364-1392. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.