IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v119y2019icp69-78.html
   My bibliography  Save this article

Network congestion games are robust to variable demand

Author

Listed:
  • Correa, José
  • Hoeksma, Ruben
  • Schröder, Marc

Abstract

We consider a non-atomic network congestion game with incomplete information in which nature decides which commodities travel. The users of a commodity do not know which other commodities travel and only have distributional information about their presence. Our main result is that the price of anarchy bounds known for the deterministic demand game also apply to the Bayesian game with random demand, even if the travel probabilities of different commodities are arbitrarily correlated. Moreover, the extension result of price of anarchy bounds for complete information games to incomplete information games in which the set of players is randomly determined can be generalized to the class of smooth games.

Suggested Citation

  • Correa, José & Hoeksma, Ruben & Schröder, Marc, 2019. "Network congestion games are robust to variable demand," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 69-78.
    • Handle: RePEc:eee:transb:v:119:y:2019:i:c:p:69-78
    DOI: 10.1016/j.trb.2018.11.010
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261518304612
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2018.11.010?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Y. Y. Fan & R. E. Kalaba & J. E. Moore, 2005. "Arriving on Time," Journal of Optimization Theory and Applications, Springer, vol. 127(3), pages 497-513, December.
    2. Aumann, Robert J., 1974. "Subjectivity and correlation in randomized strategies," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 67-96, March.
    3. MOULIN, Hervé & VIAL, Jean-Philippe, 1978. "Strategically zero-sum games: the class of games whose completely mixed equilibria connot be improved upon," LIDAM Reprints CORE 359, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Roberto Cominetti & Alfredo Torrico, 2016. "Additive Consistency of Risk Measures and Its Application to Risk-Averse Routing in Networks," Mathematics of Operations Research, INFORMS, vol. 41(4), pages 1510-1521, November.
    5. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    6. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    7. Wang, Chenlan & Doan, Xuan Vinh & Chen, Bo, 2014. "Price of anarchy for non-atomic congestion games with stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 90-111.
    8. Pradeep Dubey, 1986. "Inefficiency of Nash Equilibria," Mathematics of Operations Research, INFORMS, vol. 11(1), pages 1-8, February.
    9. Fernando Ordóñez & Nicolás E. Stier-Moses, 2010. "Wardrop Equilibria with Risk-Averse Users," Transportation Science, INFORMS, vol. 44(1), pages 63-86, February.
    10. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    11. Qi, Jin & Sim, Melvyn & Sun, Defeng & Yuan, Xiaoming, 2016. "Preferences for travel time under risk and ambiguity: Implications in path selection and network equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 264-284.
    12. Correa, José R. & Schulz, Andreas S. & Stier-Moses, Nicolás E., 2008. "A geometric approach to the price of anarchy in nonatomic congestion games," Games and Economic Behavior, Elsevier, vol. 64(2), pages 457-469, November.
    13. Nie, Yu (Marco) & Wu, Xing, 2009. "Shortest path problem considering on-time arrival probability," Transportation Research Part B: Methodological, Elsevier, vol. 43(6), pages 597-613, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 2022. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2123-2142, October.
    2. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 0. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-20.
    3. Macault, Emilien & Scarsini, Marco & Tomala, Tristan, 2022. "Social learning in nonatomic routing games," Games and Economic Behavior, Elsevier, vol. 132(C), pages 221-233.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Qi, Jin & Sim, Melvyn & Sun, Defeng & Yuan, Xiaoming, 2016. "Preferences for travel time under risk and ambiguity: Implications in path selection and network equilibrium," Transportation Research Part B: Methodological, Elsevier, vol. 94(C), pages 264-284.
    2. Thanasis Lianeas & Evdokia Nikolova & Nicolas E. Stier-Moses, 2019. "Risk-Averse Selfish Routing," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 38-57, February.
    3. Leilei Zhang & Tito Homem-de-Mello, 2017. "An Optimal Path Model for the Risk-Averse Traveler," Transportation Science, INFORMS, vol. 51(2), pages 518-535, May.
    4. Zhaoqi Zang & Xiangdong Xu & Kai Qu & Ruiya Chen & Anthony Chen, 2022. "Travel time reliability in transportation networks: A review of methodological developments," Papers 2206.12696, arXiv.org, revised Jul 2022.
    5. Feng, Zengzhe & Gao, Ziyou & Sun, Huijun, 2014. "Bounding the inefficiency of atomic splittable selfish traffic equilibria with elastic demands," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 63(C), pages 31-43.
    6. E. Nikolova & N. E. Stier-Moses, 2014. "A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times," Operations Research, INFORMS, vol. 62(2), pages 366-382, April.
    7. Pieter Kleer, 2023. "Price of anarchy for parallel link networks with generalized mean objective," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 45(1), pages 27-55, March.
    8. Roberto Cominetti & José R. Correa & Nicolás E. Stier-Moses, 2009. "The Impact of Oligopolistic Competition in Networks," Operations Research, INFORMS, vol. 57(6), pages 1421-1437, December.
    9. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 2022. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 44(3), pages 2123-2142, October.
    10. Raimondo, Roberto, 2020. "Pathwise smooth splittable congestion games and inefficiency," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 15-23.
    11. Prakash, A. Arun & Seshadri, Ravi & Srinivasan, Karthik K., 2018. "A consistent reliability-based user-equilibrium problem with risk-averse users and endogenous travel time correlations: Formulation and solution algorithm," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 171-198.
    12. Chenlan Wang & Xuan Vinh Doan & Bo Chen, 0. "Atomic congestion games with random players: network equilibrium and the price of anarchy," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-20.
    13. Wu, Xing & (Marco) Nie, Yu, 2011. "Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 45(9), pages 896-915, November.
    14. Konstantinos Georgalos & Indrajit Ray & Sonali SenGupta, 2020. "Nash versus coarse correlation," Experimental Economics, Springer;Economic Science Association, vol. 23(4), pages 1178-1204, December.
    15. Vincenzo Bonifaci & Tobias Harks & Guido Schäfer, 2010. "Stackelberg Routing in Arbitrary Networks," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 330-346, May.
    16. José R. Correa & Nicolás Figueroa & Nicolás E. Stier-Moses, 2008. "Pricing with markups in industries with increasing marginal costs," Documentos de Trabajo 256, Centro de Economía Aplicada, Universidad de Chile.
    17. Stefanos Leonardos & Costis Melolidakis, 2018. "On the Commitment Value and Commitment Optimal Strategies in Bimatrix Games," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 20(03), pages 1-28, September.
    18. Gaëtan Fournier & Marco Scarsini, 2014. "Hotelling Games on Networks: Efficiency of Equilibria," Documents de travail du Centre d'Economie de la Sorbonne 14033, Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne.
    19. Arthur Flajolet & Sébastien Blandin & Patrick Jaillet, 2018. "Robust Adaptive Routing Under Uncertainty," Operations Research, INFORMS, vol. 66(1), pages 210-229, January.
    20. Manseur, Farida & Farhi, Nadir & Nguyen Van Phu, Cyril & Haj-Salem, Habib & Lebacque, Jean-Patrick, 2020. "Robust routing, its price, and the tradeoff between routing robustness and travel time reliability in road networks," European Journal of Operational Research, Elsevier, vol. 285(1), pages 159-171.

    More about this item

    Statistics

    Access and download statistics

    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:eee:transb:v:119:y:2019:i:c:p:69-78. 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.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    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.