Risk-Averse Selfish Routing

References

• Altman E, Boulogne T, El-Azouzi R, Jiménez T, Wynter L (2006) A survey on networking games in telecommunications. Comput. Oper. Res. 33(2):286–311.Crossref, Google Scholar
• Angelidakis H, Fotakis D, Lianeas T (2013) Stochastic congestion games with risk-averse players. Vöcking B, ed. Algorithmic Game Theory—Proc. 6th Internat. Sympos., Lecture Notes in Computer Science, Vol. 8146 (Springer, Berlin), 86–97.Google Scholar
• Balcan MF, Blum A, Mansour Y (2013) The price of uncertainty. ACM Trans. Econ. Comput. 1(3):article 15; http://dx.doi.org/10.1145/2509413.2509415.Crossref, Google Scholar
• Beckmann MJ, McGuire CB, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• Bonifaci V, Salek M, Schafer G (2011) Efficiency of restricted tolls in non-atomic network routing games. Persiano G, ed. Algorithmic Game Theory—Proc. 4th Internat. Sympos., Lecture Notes in Computer Science, Vol. 6982 (Springer, Berlin), 302–313.Crossref, Google Scholar
• Boyles SD, Waller ST (2010) A mean-variance model for the minimum cost flow problem with stochastic arc costs. Networks 56(3):215–227.Crossref, Google Scholar
• Boyles SD, Kockelman KM, Waller ST (2010) Congestion pricing under operational, supply-side uncertainty. Transportation Res. Part C: Emerging Tech. 18(4):519–535.Crossref, Google Scholar
• Chau CK, Sim KM (2003) The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Oper. Res. Lett. 31(5):327–334.Crossref, Google Scholar
• Chen PA, Kempe D (2008) Altruism, selfishness, and spite in traffic routing. Proc. 9th ACM Conf. Electronic Commerce (ACM Press, New York), 140–149, http://dx.doi.org/10.1145/1386790.1386816.Google Scholar
• Cole R, Dodis Y, Roughgarden T (2006) How much can taxes help selfish routing? J. Comput. System Sci. 72(3):444–467.Crossref, Google Scholar
• Cominetti R (2015) Equilibrium routing under uncertainty. Math. Programming 151(1):117–151.Crossref, Google Scholar
• Cominetti R, Torrico A (2016) Additive consistency of risk measures and its application to risk-averse routing in networks. Math. Oper. Res. 41(4):1510–1521.Link, Google Scholar
• Correa JR, Stier-Moses NE (2011) Wardrop equilibria. Cochran JJ, ed. Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math. Oper. Res. 29(4):961–976.Link, Google Scholar
• Correa JR, Schulz AS, Stier-Moses NE (2008) A geometric approach to the price of anarchy in nonatomic congestion games. Games Econom. Behav. 64(2):457–469.Crossref, Google Scholar
• Dughmi S (2014) On the hardness of signaling. Proc. IEEE 55nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 354–363. http://dx.doi.org/10.1109/FOCS.2014.45.Google Scholar
• Dughmi S, Peres Y (2012) Mechanisms for risk averse agents, without loss. Workshop Risk Aversion Algorithmic Game Theory Mechanism Design, Valencia, Spain.Google Scholar
• Epstein A, Feldman M, Mansour Y (2009) Efficient graph topologies in network routing games. Games Econom. Behav. 66(1):115–125.Crossref, Google Scholar
• Federal Highway Administration (2017) Traffic congestion and reliability: Trends and advanced strategies for congestion mitigation. Final report, U.S. Department of Transportation, Washington, DC. https://ops.fhwa.dot.gov/congestion_report/executive_summary.htm.Google Scholar
• Fiat A, Papadimitriou C (2010) When the players are not expectation maximizers. Kontogiannis S, Koutsoupias E, Spirakis PG, eds. Algorithmic Game Theory—Proc. 3rd Internat. Sympos., Lecture Notes in Computer Science, Vol. 6386 (Springer, Berlin), 1–14.Google Scholar
• Fotakis D (2010) Congestion games with linearly independent paths: Convergence time and price of anarchy. Theory Comput. Systems 47(1):113–136.Crossref, Google Scholar
• Fotakis D, Spirakis PG (2008) Cost-balancing tolls for atomic network congestion games. Internet Math. 5(4):343–363.Crossref, Google Scholar
• Fotakis D, Kalimeris D, Lianeas T (2015) Improving selfish routing for risk-averse players. Markakis E, Schäfer G, eds. Web Internet Econom.—Proc. 11th Internat. Conf., Lecture Notes in Computer Science, Vol. 9470 (Springer, Berlin), 328–342.Google Scholar
• Fu H, Hartline J, Hoy D (2013) Prior-independent auctions for risk-averse agents. Proc. 14th ACM Conf. Electronic Commerce (ACM Press, New York), 471–488.Google Scholar
• Harks T (2011) Stackelberg strategies and collusion in network games with splittable flow. Theory Comput. Systems 48(4):781–802.Crossref, Google Scholar
• Karakostas G, Kolliopoulos SG (2005) The efficiency of optimal taxes. López-Ortiz A, Hamel A, eds. Combinatorial Algorithmic Aspects Networking (CAAN’04), Lecture Notes in Computer Science, Vol. 3405 (Springer, Berlin), 3–12.Crossref, Google Scholar
• Khani A, Boyles SD (2015) An exact algorithm for the mean-standard deviation shortest path problem. Transportation Res. Part B 81(1):252–266.Crossref, Google Scholar
• Kleer P, Schäfer G (2016) The impact of worst-case deviations in non-atomic network routing games. Gairing M, Savani R, eds. Algorithmic Game Theory—Proc. 9th Internat. Sympos., Lecture Notes in Computer Science, Vol. 9928 (Springer, Berlin), 129–140.Google Scholar
• Koutsoupias E, Papadimitriou CH (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• Krokhmal P, Zabarankin M, Uryasev S (2011) Modeling and optimization of risk. Surveys Oper. Res. Management Sci. 16(2):49–66.Crossref, Google Scholar
• Li J, Deshpande A (2011) Maximizing expected utility for stochastic combinatorial optimization problems. Proc. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (IEEE Computer Society, Washington, DC), 797–806.Google Scholar
• Lianeas T, Nikolova E, Stier-Moses NE (2016) Asymptotically tight bounds for inefficiency in risk-averse selfish routing. Kambhampati S, ed. Proc. 25th Internat. Joint Conf. Artificial Intelligence (IJCAI 2016) (IJCAI/AAAI Press, Menlo Park, CA), 338–344.Google Scholar
• Markowitz H (1952) Portfolio selection. J. Finance 7(1):77–98.Google Scholar
• Meir R, Parkes D (2015) Congestion games with distance-based strict uncertainty. Proc. 29th AAAI Conf. Artificial Intelligence (AAAI’15) (AAAI Press, Menlo Park, CA), 986–992.Google Scholar
• Meir R, Parkes D (2015) Playing the wrong game: Smoothness bounds for congestion games with behavioral biases. ACM SIGMETRICS Perform. Eval. Rev. 43(3):67–70.Crossref, Google Scholar
• Meir R, Parkes DC (2016) When are marginal congestion tolls optimal? Presentation, 9th International Workshop on Agents in Traffic and Transportation (ATT 2016), July 10, CEUR Workshop, New York.Google Scholar
• Milchtaich I (2016) Internalization of social cost in congestion games. Working paper, Bar-Ilan University, Ramat Gan, Israel. https://faculty.biu.ac.il/˜milchti/papers/continuum.pdf.Google Scholar
• Neumann JV, Morgenstern O (1944) Theory of Games and Economic Behavior (Princeton University Press, Princeton, NJ).Google Scholar
• Nie Y (2011) Multi-class percentile user equilibrium with flow-dependent stochasticity. Transportation Res. Part B 45(10):1641–1659.Crossref, Google Scholar
• Nikolova E (2010) Approximation algorithms for reliable stochastic combinatorial optimization. Serna M, Shaltiel R, Jansen K, Rolim J, eds. Approximation, Randomization, Combinatorial Optimization: Algorithms Techniques—Proc. 13th Internat. Conf. Approximation (APPROX/RANDOM’10), Lecutre Notes in Computer Science, Vol. 6302 (Springer, Berlin), 338–351.Google Scholar
• Nikolova E, Stier-Moses NE (2011) Stochastic selfish routing. Persiano G, ed. Algorithmic Game Theory—Proc. 4th Internat. Sympos., Lecture Notes in Computer Science, Vol. 6982 (Springer, Berlin), 314–325.Google Scholar
• Nikolova E, Stier-Moses NE (2014) A mean-risk model for the traffic assignment problem with stochastic travel times. Oper. Res. 62(2):366–382.Link, Google Scholar
• Nikolova E, Stier-Moses NE (2015) The burden of risk aversion in mean-risk selfish routing. Roughgarden T, Feldman M, Schwarz M, eds. Proc. 16th ACM Conf. Econom. Comput. (ACM Press, New York), 489–506.Google Scholar
• Nikolova E, Brand M, Karger DR (2006) Optimal route planning under uncertainty. Long D, Smith SF, Borrajo D, McCluskey L, eds. Proc. 16th Internat. Conf. Automated Planning Scheduling (ICAPS) (AAAI Press, Menlo Park, CA), 131–141.Google Scholar
• Nikolova E, Kelner JA, Brand M, Mitzenmacher M (2006) Stochastic shortest paths via quasi-convex maximization. Algorithms—ESA 2006, Lecture Notes in Computer Science, Vol. 4168 (Springer-Verlag, Berlin), 552–563.Crossref, Google Scholar
• Nisan N, Roughgarden T, Tardos É, Vazirani VV (2007) Algorithmic Game Theory (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Ordóñez F, Stier-Moses NE (2010) Wardrop equilibria with risk-averse users. Transportation Sci. 44(1):63–86.Link, Google Scholar
• Papadimitriou CH (2001) Algorithms, games, and the Internet. Proc. 33rd Annual ACM Sympos. Theory Comput. (STOC) (ACM Press, New York), 749–753.Google Scholar
• Perakis G (2007) The “price of anarchy” under nonlinear and asymmetric costs. Math. Oper. Res. 32(3):614–628.Link, Google Scholar
• Pigou AC (1920) The Economics of Welfare (Macmillan, London).Google Scholar
• Piliouras G, Nikolova E, Shamma JS (2013) Risk sensitivity of price of anarchy under uncertainty. Proc. 14th ACM Conf. Electronic Commerce (ACM Press, New York), 715–732.Google Scholar
• Rockafellar RT (2007) Coherent approaches to risk in optimization under uncertainty. Klastorin T, ed. OR Tools and Applications: Glimpses of Future Technologies, Tutorials in Operations Research (INFORMS, Hanover, MD), 38–61.Link, Google Scholar
• Roughgarden T (2003) The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2):341–364.Crossref, Google Scholar
• Roughgarden T (2006) On the severity of Braess’s paradox: Designing networks for selfish users is hard. J. Comput. System Sci. 72(5):922–953.Crossref, Google Scholar
• Roughgarden T, Schoppmann F (2015) Local smoothness and the price of anarchy in splittable congestion games. J. Econom. Theory 156(March):317–342.Crossref, Google Scholar
• Roughgarden T, Tardos É (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• Sheffi Y (1985) Urban Transportation Networks (Prentice-Hall, Englewood, NJ).Google Scholar
• Swamy C (2011) Risk-averse stochastic optimization: Probabilistically-constrained models and algorithms for black-box distributions. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1627–1646.Google Scholar
• Tversky A, Kahneman D (1981) The framing of decisions and the psychology of choice. Science 211(4481):453–458.Crossref, Google Scholar
• Valdes J, Tarjan RE, Lawler EL (1979) The recognition of series parallel digraphs. Proc. 11th Annual ACM Sympos. Theory Comput. (STOC) (ACM Press, New York), 1–12.Google Scholar
• Vicroads (2014) Traffic monitor 2012–13. Last accessed October 2017, https://www.vicroads.vic.gov.au/˜/media/files/documents/traffic%20and%20road%20use/trafficmonitorreport20122013.ashx.Google Scholar
• Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Institute of Civil Engrg. 1(3):325–362.Google Scholar