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

Risk-Averse Selfish Routing

Author

Listed:
  • Thanasis Lianeas

    (University of Texas at Austin, Austin, Texas 78705)

  • Evdokia Nikolova

    (University of Texas at Austin, Austin, Texas 78705)

  • Nicolas E. Stier-Moses

    (Facebook Core Data Science, Menlo Park, California 94303)

Abstract

We consider a nonatomic selfish routing model with independent stochastic travel times for each edge, represented by mean and variance latency functions that depend on edge flows. This model can apply to traffic in the Internet or in a road network. Variability negatively impacts packets or drivers by introducing jitter in transmission delays, which lowers quality of streaming audio or video, or by making it more difficult to predict the arrival time at destination. At equilibrium, agents may select paths that do not minimize the expected latency so as to obtain lower variability. A social planner, who is likely to be more risk neutral than agents because it operates at a longer time scale, quantifies social cost with the total expected delay along routes. From that perspective, agents may make suboptimal decisions that degrade long-term quality. We define the price of risk aversion (PRA) as the worst-case ratio of the social cost at a risk-averse Wardrop equilibrium to that where agents are risk neutral. This inefficiency metric captures the degradation of system performance caused by variability and risk aversion. For networks with general delay functions and a single source–sink pair, we first show upper bounds for the PRA that depend linearly on the agents’ risk tolerance and on the degree of variability present in the network. We call these bounds structural , as they depend on the structure of the network. To get this result, we rely on a combinatorial proof that employs alternating paths that are reminiscent of those used in max-flow algorithms. For series-parallel graphs, the PRA becomes independent of the network topology and its size. Next, we provide tight and asymptotically tight lower bounds on the PRA by showing a family of structural lower bounds, which grow linearly with the number of nodes in the graph and players’ risk aversion. These are tight for graph sizes that are powers of 2. After that, by focusing on restricting the set of allowable mean latency and variance functions, we derive functional bounds on the PRA that are asymptotically tight and depend on the allowed latency functions but not on the topology. The functional bounds match the price-of-anarchy bounds for congestion games multiplied by an extra factor that accounts for risk aversion. Finally, we turn to the mean-standard deviation user objective—a much more complex model of risk aversion because the cost of a path is nonadditive over edge costs—and provide tight bounds for instances that admit alternating paths with one or two forward subpaths.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:ormoor:v:44:y:2019:i:1:p:38-57
    DOI: 10.1287/moor.2017.0913
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/moor.2017.0913
    Download Restriction: no

    File URL: https://libkey.io/10.1287/moor.2017.0913?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
    ---><---

    References listed on IDEAS

    as
    1. Khani, Alireza & Boyles, Stephen D., 2015. "An exact algorithm for the mean–standard deviation shortest path problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 252-266.
    2. 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.
    3. 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.
    4. Epstein, Amir & Feldman, Michal & Mansour, Yishay, 2009. "Efficient graph topologies in network routing games," Games and Economic Behavior, Elsevier, vol. 66(1), pages 115-125, May.
    5. Nie, Yu (Marco), 2011. "Multi-class percentile user equilibrium with flow-dependent stochasticity," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1641-1659.
    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. Roughgarden, Tim & Schoppmann, Florian, 2015. "Local smoothness and the price of anarchy in splittable congestion games," Journal of Economic Theory, Elsevier, vol. 156(C), pages 317-342.
    8. 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.
    9. 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.
    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. Jerry Anunrojwong & Krishnamurthy Iyer & David Lingenbrink, 2024. "Persuading Risk-Conscious Agents: A Geometric Approach," Operations Research, INFORMS, vol. 72(1), pages 151-166, January.
    2. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Satoru Fujishige & Michel X. Goemans & Tobias Harks & Britta Peis & Rico Zenklusen, 2017. "Matroids Are Immune to Braess’ Paradox," Mathematics of Operations Research, INFORMS, vol. 42(3), pages 745-761, August.
    8. Ahipaşaoğlu, Selin Damla & Meskarian, Rudabeh & Magnanti, Thomas L. & Natarajan, Karthik, 2015. "Beyond normality: A cross moment-stochastic user equilibrium model," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 333-354.
    9. Raimondo, Roberto, 2020. "Pathwise smooth splittable congestion games and inefficiency," Journal of Mathematical Economics, Elsevier, vol. 86(C), pages 15-23.
    10. Parilina, Elena & Sedakov, Artem & Zaccour, Georges, 2017. "Price of anarchy in a linear-state stochastic dynamic game," European Journal of Operational Research, Elsevier, vol. 258(2), pages 790-800.
    11. 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.
    12. 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.
    13. 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.
    14. Michael W. Levin & Melissa Duell & S. Travis Waller, 2020. "Arrival Time Reliability in Strategic User Equilibrium," Networks and Spatial Economics, Springer, vol. 20(3), pages 803-831, September.
    15. 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.
    16. Zhu, Zheng & Mardan, Atabak & Zhu, Shanjiang & Yang, Hai, 2021. "Capturing the interaction between travel time reliability and route choice behavior based on the generalized Bayesian traffic model," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 48-64.
    17. T. Werth & H. Sperber & S. Krumke, 2014. "Computation of equilibria and the price of anarchy in bottleneck congestion games," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 22(4), pages 687-712, December.
    18. Cominetti, Roberto & Dose, Valerio & Scarsini, Marco, 2024. "Phase transitions of the price-of-anarchy function in multi-commodity routing games," Transportation Research Part B: Methodological, Elsevier, vol. 182(C).
    19. Knight, Vincent A. & Harper, Paul R., 2013. "Selfish routing in public services," European Journal of Operational Research, Elsevier, vol. 230(1), pages 122-132.
    20. 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.

    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:44:y:2019:i:1:p:38-57. 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: 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.