Ordinary and Prophet Planning Under Uncertainty in Bernoulli Congestion Games

References

• Acemoglu D, Makhdoumi A, Malekian A, Ozdaglar A (2018) Informational Braess’ paradox: The effect of information on traffic congestion. Oper. Res. 66(4):893–917.Link, Google Scholar
• Aland S, Dumrauf D, Gairing M, Monien B, Schoppmann F (2011) Exact price of anarchy for polynomial congestion games. SIAM J. Comput. 40(5):1211–1233.Crossref, Google Scholar
• Angelidakis H, Fotakis D, Lianeas T (2013) Stochastic congestion games with risk-averse players. Vöcking B, ed. Algorithmic Game Theory. SAGT 2013, Lecture Notes in Computer Science, vol. 8146 (Springer, Berlin), 86–97.Crossref, Google Scholar
• Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
• Ashlagi I, Monderer D, Tennenholtz M (2006) Resource selection games with unknown number of players. Proc. Fifth Internat. Joint Conf. Autonomous Agents Multiagent Systems AAMAS ‘06 (ACM, New York), 819–825.Google Scholar
• Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Crossref, Google Scholar
• Beckmann MJ, McGuire C, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• Bilò V, Moscardelli L, Vinci C (2024) Uniform mixed equilibria in network congestion games with link failures. Math. Oper. Res. 49(1):509–535.Link, Google Scholar
• Caragiannis I, Kaklamanis C, Kanellopoulos P, Kyropoulou M, Papaioannou E (2010) The impact of altruism on the efficiency of atomic congestion games. Wirsing M, Hofmann M, Rauschmayer A, eds. Trustworthly Global Computing (Springer, Berlin), 172–188.Crossref, Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Chen PA, de Keijzer B, Kempe D, Schäfer G (2014) Altruism and its impact on the price of anarchy. ACM Trans. Econom. Comput. 2(4):17:1–17:45.Google Scholar
• Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. STOC’05 Proc. 37th Annual ACM Sympos. Theory Comput. (ACM, New York), 67–73.Google Scholar
• Colini-Baldeschi R, Cominetti R, Scarsini M (2019) Price of anarchy for highly congested routing games in parallel networks. Theory Comput. Systems 63(1):90–113.Crossref, Google Scholar
• Colini-Baldeschi R, Cominetti R, Mertikopoulos P, Scarsini M (2017) The asymptotic behavior of the price of anarchy. Devanur R, Lu NP, eds. Web Internet Econom. 13th Internat. Conf. WINE 2017 (Springer International Publishing, Cham, Switzerland), 133–145.Google Scholar
• 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
• 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
• Cominetti R, Dose V, Scarsini M (2024) The price of anarchy in routing games as a function of the demand. Math. Programming 203(1–2):531–558.Crossref, Google Scholar
• Cominetti R, Scarsini M, Schröder M, Stier-Moses N (2023) Approximation and convergence of large atomic congestion games. Math. Oper. Res. 48(2):784–811.Link, Google Scholar
• Correa JR, Stier-Moses NE (2011) Wardrop equilibria. Cochran JJ, Cox LA, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Correa J, Hoeksma R, Schröder M (2019) Network congestion games are robust to variable demand. Transportation Res. Part B Methodological 119:69–78.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
• Dumrauf D, Gairing M (2006) Price of anarchy for polynomial Wardrop games. Spirakis P, Mavronicolas M, Kontogiannis S, eds. Internet and Network Economics (Springer, Berlin), 319–330.Crossref, Google Scholar
• Foster DP, Vohra RV (1997) Calibrated learning and correlated equilibrium. Games Econom. Behav. 21(1–2):40–55.Crossref, Google Scholar
• Gairing M (2006) Selfish routing in networks. PhD dissertation, Universität Paderborn, Paderborn, Germany.Google Scholar
• Gairing M, Monien B, Tiemann K (2008) Selfish routing with incomplete information. Theory Comput. Systems 42(1):91–130.Crossref, Google Scholar
• Griesbach SM, Hoefer M, Klimm M, Koglin T (2022) Public signals in network congestion games. Proc. 23rd ACM Conf. Econom. Comput. EC ‘22 (Association for Computing Machinery, New York).Google Scholar
• Hannan J (1958) Approximation to Bayes risk in repeated play. Contributions to the Theory of Games, vol. 3 (Princeton University Press, Princeton, NJ), 97–140.Google Scholar
• Harks T, Végh LA (2007) Nonadaptive selfish routing with online demands. Proc. 4th Conf. Combinatorial Algorithmic Aspects Networking CAAN’07 (Springer-Verlag, Berlin), 27–45.Google Scholar
• Kleer P, Schäfer G (2019) Tight inefficiency bounds for perception-parameterized affine congestion games. Theoret. Comput. Sci. 754:65–87.Crossref, Google Scholar
• Knoblauch A (2008) Closed-form expressions for the moments of the binomial probability distribution. SIAM J. Appl. Math. 69(1):197–204.Crossref, Google Scholar
• Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. STACS 99 (Trier), Lecture Notes in Computer Science, vol. 1563 (Springer, Berlin), 404–413.Crossref, Google Scholar
• Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• Li Y, Jia Y, Tan H, Wang R, Han Z, Lau FCM (2017) Congestion game with agent and resource failures. IEEE J. Selected Areas Comm. 35(3):764–778.Crossref, Google Scholar
• Lianeas T, Nikolova E, Stier-Moses NE (2019) Risk-averse selfish routing. Math. Oper. Res. 44(1):38–57.Abstract, Google Scholar
• Macault E, Scarsini M, Tomala T (2022) Social learning in nonatomic routing games. Games Econom. Behav. 132(2022):221–233.Crossref, Google Scholar
• Macault E, Scarsini M, Tomala T (2023) Corrigendum to “Social learning in nonatomic routing games.” Games Econom. Behav. 138(2023):407–408.Crossref, Google Scholar
• Marcotte P, Nguyen S, Schoeb A (2004) A strategic flow model of traffic assignment in static capacitated networks. Oper. Res. 52(2):191–212.Link, Google Scholar
• Meir R, Tennenholtz M, Bachrach Y, Key P (2012) Congestion games with agent failures. Proc. Conf. AAAI Artificial Intelligence 26(1):1401–1407.Crossref, Google Scholar
• Miller-Hooks E (2001) Adaptive least-expected time paths in stochastic, time-varying transportation and data networks. Networks 37(1):35–52.Crossref, Google Scholar
• Nguyen S, Pallottino S (1988) Equilibrium traffic assignment for large scale transit networks. Eur. J. Oper. Res. 37(2):176–186.Crossref, 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
• Ordóñez F, Stier-Moses NE (2010) Wardrop equilibria with risk-averse users. Transportation Sci. 44(1):63–86.Link, Google Scholar
• Penn M, Polukarov M, Tennenholtz M (2009) Congestion games with load-dependent failures: Identical resources. Games Econom. Behav. 67(1):156–173.Crossref, Google Scholar
• Penn M, Polukarov M, Tennenholtz M (2011) Congestion games with failures. Discrete Appl. Math. 159(15):1508–1525.Crossref, Google Scholar
• Pigou AC (1920) The Economics of Welfare, 1st ed. (Macmillan and Co., London).Google Scholar
• Piliouras G, Nikolova E, Shamma JS (2016) Risk sensitivity of price of anarchy under uncertainty. ACM Trans. Econom. Comput. 5(1):5.Google Scholar
• Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2:65–67.Crossref, 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 (2005) Selfish routing with atomic players. Proc. Sixteenth Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1184–1185.Google Scholar
• Roughgarden T (2007) Routing games. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 461–486.Crossref, Google Scholar
• Roughgarden T (2015a) Intrinsic robustness of the price of anarchy. J. ACM 62(5):32.Crossref, Google Scholar
• Roughgarden T (2015b) The price of anarchy in games of incomplete information. ACM Trans. Econom. Comput. 3(1):6.Google Scholar
• Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2):389–403.Crossref, Google Scholar
• Roughgarden T, Tardos E (2007) Introduction to the inefficiency of equilibria. Nisan N, Roughgarden T, Tardos E, Vazirani VV, eds. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 443–459.Crossref, Google Scholar
• Schulz AS, Stier Moses N (2003) On the performance of user equilibria in traffic networks. Proc. Fourteenth Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 86–87.Google Scholar
• Suri S, Tóth CD, Zhou Y (2007) Selfish load balancing and atomic congestion games. Algorithmica 47(1):79–96.Crossref, Google Scholar
• Syrgkanis V (2015) Price of stability in games of incomplete information. Preprint, submitted March 12, http://arxiv.org/abs/1503.03739.Google Scholar
• Ukkusuri S, Waller S (2010) Approximate analytical expressions for transportation network performance under demand uncertainty. Transportation Lett. 2(2):111–123.Crossref, Google Scholar
• Wang C, Doan XV, Chen B (2014) Price of anarchy for non-atomic congestion games with stochastic demands. Transportation Res. Part B Methodological 70:90–111.Crossref, Google Scholar
• Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers Part II, vol. 1, 325–378.Google Scholar
• Wrede S (2019) On the price of anarchy in atomic congestion games under player-entrance-probabilities. Master’s thesis, RWTH Aachen University, Aachen, Germany.Google Scholar
• Wu Z, Möhring RH (2022) A sensitivity analysis for the price of anarchy in nonatomic congestion games. Math. Oper. Res. 48(3):1364–1392.Link, Google Scholar
• Wu M, Amin S, Ozdaglar AE (2021a) Value of information in Bayesian routing games. Oper. Res. 69(1):148–163.Link, Google Scholar
• Wu Z, Möhring RH, Chen Y, Xu D (2021b) Selfishness need not be bad. Math. Oper. Res. 69(2):410–435.Link, Google Scholar
• Zhu Y, Savla K (2022) Information design in nonatomic routing games with partial participation: Computation and properties. IEEE Trans. Control Network Systems 9(2):613–624.Crossref, Google Scholar