Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

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

Published Online:30 Sep 2022https://doi.org/10.1287/moor.2022.1292

References

  • [1] Beckmann MJ, McGuire C, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
  • [2] Bingham NH, Goldie CM, Teugels JL (1987) Regular Variation (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
  • [3] Bureau of Public Roads (1964) Traffic Assignment Manual (U.S. Department of Commerce, Urban Planning Division, Washington, DC).Google Scholar
  • [4] Colini-Baldeschi R, Cominetti R, Scarsini M (2016) On the price of anarchy of highly congested nonatomic network games. Gairing M, Savani R, eds. Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 9928 (Springer, Berlin, Heidelberg), 117–128.Crossref, Google Scholar
  • [5] Colini-Baldeschi R, Cominetti R, Mertikopoulos P, Scarsini M (2017) The asymptotic behavior of the price of anarchy. Devanur NR, Lu P, eds. Web and Internet Economics, Lecture Notes in Computer Science, vol. 10660 (Springer, Cham, Switzerland), 133–145 .Crossref, Google Scholar
  • [6] Colini-Baldeschi R, Cominetti R, Mertikopoulos P, Scarsini M (2020) When is selfish routing bad? The price of anarchy in light and heavy traffic. Oper. Res. 68(2):411–434.Abstract, Google Scholar
  • [7] Cominetti R, Dose V, Scarsini M (2021) The price of anarchy in routing games as a function of the demand. Math. Programming, ePub ahead of print September 8, https://doi.org/10.1007/s10107-021-01701-7.Google Scholar
  • [8] Correa JR, Schulz AS, Stier Moses NE (2004) Selfish routing in capacitated networks. Math. Oper. Res. 29(4):961–976.Link, Google Scholar
  • [9] Correa JR, Schulz AS, Stier-Moses NE (2005) On the inefficiency of equilibria in congestion games. Jünger M, Kaibel V, eds. Integer Programming and Combinatorial Optimization, Internat. IPCO Conf., Lecture Notes in Computer Science, vol. 3509 (Springer, Berlin, Heidelberg), 167–181.Google Scholar
  • [10] Dafermos S (1980) Traffic equilibrium and variational inequalities. Transportation Sci. 14(1):42–54.Link, Google Scholar
  • [11] Dafermos SC, Sparrow FT (1969) The traffic assignment problem for a general network. J. Res. U.S. National Bureau Standards 73(B):91–118.Google Scholar
  • [12] Englert M, Franke T, Olbrich L (2010) Sensitivity of Wardrop equilibria. Theory Comput. Systems 47(1):3–14.Crossref, Google Scholar
  • [13] Hall M (1978) Properties of the equilibrium state in transportation networks. Transportation. Sci. 12(3):208–216.Link, Google Scholar
  • [14] Harks T, Kleinert I, Klimm M, Möhring RH (2015) Computing network tolls with support constraints. Networks 65(3):262–285.Crossref, Google Scholar
  • [15] Jahn O, Möhring RH, Schulz AS, Stier-Moses NE (2005) System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53(4):600–616.Link, Google Scholar
  • [16] Josefsson M, Patriksson M (2007) Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design. Transportation Res. Part B: Methodological 41(1):4–31.Crossref, Google Scholar
  • [17] Kelley J (1975) General Topology (Springer, Berlin).Google Scholar
  • [18] Klimm M, Warode P (2019) Computing all Wardrop equilibria parametrized by the flow demand. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 917–934.Google Scholar
  • [19] Klimm M, Warode P (2022) Parametric computation of minimum-cost flows with piece-wise quadratic costs. Math. Oper. Res. 47(1):812–846.Link, Google Scholar
  • [20] Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. Proc. 16th Annual Sympos. Theoret. Aspects Comput. Sci. (STACS), Lecture Notes in Computer Science, vol. 1563 (Springer, Heidelberg), 404–413.Google Scholar
  • [21] Lu S (2008) Sensitivity of static traffic user equilibria with perturbations in arc cost function and travel demand. Transportation Sci. 42(1):105–123.Link, Google Scholar
  • [22] Monnot B, Benita F, Piliouras G (2017) How bad is selfish routing in practice? Preprint, submitted March 5, https://arxiv.org/abs/1703.01599.Google Scholar
  • [23] Nisan N, Roughgarden T, Tardos E, Vaz VV (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
  • [24] O’Hare SJ, Connors RD, Watling DP (2016) Mechanisms that govern how the price of anarchy varies with travel demand. Transportation Res. Part B: Methodological 84:55–80.Crossref, Google Scholar
  • [25] Papadimitriou C (2001) Algorithms, games, and the internet. Proc. Thirty-third Annual ACM Sympos. Theory Comput. (ACM, New York), 749–753.Google Scholar
  • [26] Patriksson M (2004) Sensitivity analysis of traffic equilibria. Transportation Sci. 38(3):258–281.Link, Google Scholar
  • [27] Perakis G (2007) The price of anarchy under nonlinear and asymmetric costs. Math. Oper. Res. 32(3):614–628.Link, Google Scholar
  • [28] Pigou AC (1920) The Economics of Welfare, 1st ed. (Macmillan and Co., London).Google Scholar
  • [29] Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
  • [30] Roughgarden T (2001) Designing networks for selfish users is hard. Proc. 42nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 472–481.Google Scholar
  • [31] Roughgarden T (2003) The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2):341–364.Crossref, Google Scholar
  • [32] Roughgarden T (2005) Selfish Routing and the Price of Anarchy (The MIT Press, Cambridge, MA).Google Scholar
  • [33] Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J. ACM 62(5):1–42.Crossref, Google Scholar
  • [34] Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
  • [35] Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2):389–403.Crossref, Google Scholar
  • [36] Roughgarden T, Tardos E (2007) Introduction to the inefficiency of equilibria. Nisan N, Roughgarden T, Tardos É, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 443–459.Crossref, Google Scholar
  • [37] Sandholm WH (2001) Potential games with continuous player sets. J. Econom. Theory 97(1):81–108.Crossref, Google Scholar
  • [38] Schmeidler D (1973) Equilibrium points of nonatomic games. J. Statist. Phys. 7(4):295–300.Crossref, Google Scholar
  • [39] Smith MJ (1979) The existence, uniqueness and stability of traffic equilibria. Transportation Res. Part B: Methodological 13(4):295–304.Crossref, Google Scholar
  • [40] Takalloo M, Kwon C (2020) Sensitivity of Wardrop equilibria: Revisited. Optim. Lett. 14(3):781–796.Crossref, Google Scholar
  • [41] Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers 1(3):325–362.Google Scholar
  • [42] Wu Z, Möhring R, Chen Y, Xu D (2021) Selfishness need not be bad. Oper. Res. 69(2):410–435.Link, Google Scholar
  • [43] Youn H, Gastner MT, Jeong H (2008) Price of anarchy in transportation networks: Efficiency and optimality control. Phys. Rev. Lett. 101(12):128701.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree