Public Signals in Affine Network Congestion Games with Uncertain Free-Flow Times

References

• [1] 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
• [2] 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
• [3] Angelidakis H, Fotakis D, Lianeas T (2013) Stochastic congestion games with risk-averse players. Vöcking B, ed. SAGT’13: Proc. 6th Internat. Sympos. Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 8146 (Springer, Berlin, Heidelberg), 86–97.Google Scholar
• [4] Arieli I, Babichenko Y (2019) Private Bayesian persuasion. J. Econom. Theory 182:185–217.Crossref, Google Scholar
• [5] Arnott R, De Palma A, Lindsey R (1991) Does providing information to drivers reduce traffic congestion? Trans. Res. Part A: General 25(5):309–318.Crossref, Google Scholar
• [6] Ashlagi I, Monderer D, Tennenholtz M (2006) Resource selection games with unknown number of players. AAMAS’06: Proc. Fifth Internat. Joint Conf. Autonomous Agents Multiagent Systems (Association for Computing Machinery, New York), 819–825.Google Scholar
• [7] Aumann R, Maschler M (1966) Game theoretic aspects of gradual disarmament. Rep. US Arms Control Disarmament Agency 80:1–55.Google Scholar
• [8] Aumann RJ, Maschler M, Stearns RE (1995) Repeated Games with Incomplete Information (MIT Press, Cambridge, MA).Google Scholar
• [9] Avis D, Fukuda K (1996) Reverse search for enumeration. Discrete Appl. Math. 65(1–3):21–46.Crossref, Google Scholar
• [10] Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Crossref, Google Scholar
• [11] Badanidiyuru A, Bhawalkar K, Xu H (2018) Targeting and signaling in ad auctions. SODA’18: Proc. 29th Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2545–2563.Google Scholar
• [12] Beckmann M, McGuire CB, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• [13] Bettini M (2022) Static traffic assignment using user equilibrium and system optimum - Python code and network data. Accessed September 28, 2026, https://github.com/MatteoBettini/Traffic-Assignment-Frank-Wolfe-2021.Google Scholar
• [14] Bhaskar U, Cheng Y, Ko YK, Swamy C (2016) Hardness results for signaling in Bayesian zero-sum and network routing games. EC’16: Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 479–496.Google Scholar
• [15] Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12:258–268.Google Scholar
• [16] Buck RC (1943) Partition of space. Amer. Math. Monthly 50(9):541–544.Crossref, Google Scholar
• [17] Bureau of Public Roads (1964) Traffic Assignment Manual (U.S. Dept. of Commerce, Urban Planning Division, Washington, DC).Google Scholar
• [18] Castiglioni M, Celli A, Marchesi A, Gatti N (2020) Online Bayesian persuasion. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. NeurIPS’20: Proc. 34th Internat. Conf. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 16188–16198.Google Scholar
• [19] Castiglioni M, Celli A, Marchesi A, Gatti N (2021a) Signaling in Bayesian network congestion games: The subtle power of symmetry. AAAI 21: Proc. 35th Conf. Artificial Intelligence (AAAI Press, Washington, DC), 5252–5259.Google Scholar
• [20] Castiglioni M, Marchesi A, Celli A, Gatti N (2021b) Multi-receiver online Bayesian persuasion. Meila M, Zhang T, eds. ICML’21: Proc. 38th Internat. Conf. Machine Learn., vol. 139 (PMLR, New York), 1314–1323.Google Scholar
• [21] Christodoulou G, Koutsoupias E (2005) The price of anarchy in finite congestion games. STOC’05: Proc. 37th Symp. Theory Comput. (Association for Computing Machinery, New York), 67–73.Google Scholar
• [22] Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis P (2019) The price of stability of weighted congestion games. SIAM J. Comput. 48(5):1544–1582.Crossref, Google Scholar
• [23] 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
• [24] 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
• [25] Colini-Baldeschi R, Klimm M, Scarsini M (2018) Demand-independent optimal tolls. ICALP’18: Proc.45th Internat. Colloquium Automata Languages Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 107 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 151:1–151:14.Google Scholar
• [26] 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
• [27] 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
• [28] Cominetti R, Dose V, Scarsini M (2024a) Monotonicity of equilibria in nonatomic congestion games. Eur. J. Oper. Res. 316(2):754–766.Crossref, Google Scholar
• [29] Cominetti R, Dose V, Scarsini M (2024b) The price of anarchy in routing games as a function of the demand. Math. Programming 203:531–558.Crossref, Google Scholar
• [30] Cominetti R, Scarsini M, Schröder M, Stier-Moses N (2019) Price of anarchy in stochastic atomic congestion games with affine costs. EC’19: Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 579–580.Google Scholar
• [31] Cominetti R, Scarsini M, Schröder M, Stier-Moses NE (2023) Approximation and convergence of large atomic congestion games. Math. Oper. Res. 48(2):784–811.Link, Google Scholar
• [32] Correa JR, Schulz A, Stier-Moses N (2008) A geometric approach to the price of anarchy in nonatomic congestion games. Games Econom. Behav. 64(2):457–469.Crossref, Google Scholar
• [33] Daneva M, Lindberg PO (2003) A conjugate direction Frank–Wolfe method with applications to the traffic assignment problem. Leopold-Wildburger U, Rendl F, Wäscher G, eds. Oper. Res. Proc. 2002, vol. 2002 (Springer, Berlin, Heidelberg), 133–138.Crossref, Google Scholar
• [34] Das S, Kamenica E, Mirka R (2017) Reducing congestion through information design. 2017 55th Annual Allerton Conf. Comm. Control Comput. (IEEE, Piscataway, NJ), 1279–1284.Google Scholar
• [35] Dial RB (1971) A probabilistic multipath traffic assignment model which obviates path enumeration. Transportation Res. 5(2):83–111.Crossref, Google Scholar
• [36] Duffin RJ (1965) Topology of series-parallel networks. J. Math. Anal. Appl. 10(2):303–318.Crossref, Google Scholar
• [37] Dughmi S (2019) On the hardness of designing public signals. Games Econom. Behav. 118:609–625.Crossref, Google Scholar
• [38] Dughmi S, Xu H (2021) Algorithmic Bayesian persuasion. SIAM J. Comput. 50(3):STOC16-68–STOC16-97. Crossref, Google Scholar
• [39] Dughmi S, Kempe D, Qiang R (2016) Persuasion with limited communication. EC’16: Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 663–680.Google Scholar
• [40] Emek Y, Feldman M, Gamzu I, Leme RP, Tennenholtz M (2014) Signaling schemes for revenue maximization. ACM Trans. Econom. Comput. 2(2):5:1–5:19.Google Scholar
• [41] Englert M, Franke T, Olbrich L (2010) Sensitivity of Wardrop equilibria. Theory Comput. Systems 47(1):3–14.Crossref, Google Scholar
• [42] Fleischer L, Jain K, Mahdian M (2004) Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. FOCS’04: Proc. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 277–285.Google Scholar
• [43] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [44] Fujishige S, Goemans M, Harks T, Peis B, Zenklusen R (2017) Matroids are immune to Braess’ paradox. Math. Oper. Res. 42(3):745–761.Link, Google Scholar
• [45] Gairing M, Harks T, Klimm M (2017) Complexity and approximation of the continuous network design problem. SIAM J. Optim. 27(3):1554–1582.Crossref, Google Scholar
• [46] Gairing M, Monien B, Tiemann K (2008) Selfish routing with incomplete information. Theory Comput. Systems 42(1):91–130.Crossref, Google Scholar
• [47] Gradwohl R, Hahn N, Hoefer M, Smorodinsky R (2022) Algorithms for persuasion with limited communication. Math. Oper. Res. 47(3):2520–2545.Link, Google Scholar
• [48] Griesbach SM, Hoefer M, Klimm M, Koglin T (2024a) Information design for congestion games with unknown demand. AAAI 24: Proc. 38th Conf. Artificial Intelligence (AAAI Press, Washington, DC), 9722–9730.Google Scholar
• [49] Griesbach SM, Klimm M, Warode P, Ziemke T (2024b) Optimizing throughput and makespan of queuing systems by information design. ESA’24: Proc. 32nd Annual Eur. Sympos. Algorithms, Leibniz International Proceedings in Informatics (LIPIcs), vol. 308 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 62:1–62:18.Google Scholar
• [50] Hahn N, Hoefer M, Smorodinsky R (2020a) Prophet inequalities for Bayesian persuasion. Bessiere C, ed. IJCAI’20: Proc. 29th Internat. Joint Conf. Artificial Intelligence, 175–181.Google Scholar
• [51] Hahn N, Hoefer M, Smorodinsky R (2020b) The secretary recommendation problem. EC’20: Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 189.Google Scholar
• [52] Harks T, Kleinert I, Klimm M, Möhring RH (2015) Computing network tolls with support constraints. Networks 65(3):262–285.Crossref, Google Scholar
• [53] Harville DA (1997) Matrix Algebra from a Statistician’s Perspective (Springer, New York).Crossref, Google Scholar
• [54] Hoefer M, Souza A (2010) Tradeoffs and average-case equilibria in selfish routing. ACM Trans. Comput. Theory 2(1):2:1–2:25.Crossref, Google Scholar
• [55] Hoefer M, Olbrich L, Skopalik A (2008) Taxing subnetworks. Papadimitriou C, Zhang S, eds. WINE’08: Proc. 4th Internat. Workshop Internet Network Econom., Lecture Notes in Computer Science, vol. 5385 (Springer, Berlin, Heidelberg), 286–294.Google Scholar
• [56] 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
• [57] Jelinek T, Klaas M, Schäfer G (2014) Computing optimal tolls with arc restrictions and heterogeneous players. STACS’14: Proc. 31st Internat. Sympos. Theoret. Aspects Comput. Sci., Leibniz International Proceedings in Informatics (LIPIcs), vol. 25 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 433–444.Google Scholar
• [58] Kamenica E, Gentzkow M (2011) Bayesian persuasion. Amer. Econom. Rev. 101(6):2590–2615.Crossref, Google Scholar
• [59] Karakostas G, Kolliopoulos S (2004) Edge pricing of multicommodity networks for heterogeneous users. FOCS’04: Proc. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 268–276.Google Scholar
• [60] Klimm M, Warode P (2022) Parametric computation of minimum-cost flows with piecewise quadratic costs. Math. Oper. Res. 47(1):812–846.Link, Google Scholar
• [61] Lianeas T, Nikolova E, Stier-Moses NE (2019) Risk-averse selfish routing. Math. Oper. Res. 44(1):38–57.Abstract, Google Scholar
• [62] Liu HX, Ban X, Ran B, Mirchandani P (2002) Analytical dynamic traffic assignment model with probabilistic travel times and perceptions. Transportation Res. Record 1783(1):125–133.Crossref, Google Scholar
• [63] Macfarlane J (2019) When apps rule the road: The proliferation of navigation apps is causing traffic chaos. It’s time to restore order. IEEE Spectrum 56(10):22–27.Crossref, Google Scholar
• [64] Massicot O, Langbort C (2019) Public signals and persuasion for road network congestion games under vagaries. IFAC-PapersOnLine 51(34):124–130.Crossref, Google Scholar
• [65] Meir R, Tennenholtz M, Bachrach Y, Key PB (2012) Congestion games with agent failures. Hoffmann J, Selman B, eds. AAAI’12: Proc. 26th Conf. Artificial Intelligence (AAAI Press, Washington, DC), 1401–1407.Google Scholar
• [66] Milchtaich I (2006) Network topology and the efficiency of equilibrium. Games Econom. Behav. 57(2):321–346.Crossref, Google Scholar
• [67] Mirchandani P, Soroush H (1987) Generalized traffic equilibrium with probabilistic travel times and perceptions. Transportation Sci. 21(3):133–152.Link, Google Scholar
• [68] Nachbar J, Xu H (2021) The power of signaling and its intrinsic connection to the price of anarchy. Chen J, Lang J, Amato C, Zhao D, eds. Distributed Artificial Intelligence. DAI 2021, Lecture Notes in Computer Science, vol. 13170 (Springer, Cham, Switzerland), 1–20.Google Scholar
• [69] Nie YM (2011) Multi-class percentile user equilibrium with flow-dependent stochasticity. Transportation Res. Part B 45(10):1641–1659.Crossref, Google Scholar
• [70] 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
• [71] O’Hare S, Connors R, Watling D (2016) Mechanisms that govern how the price of anarchy varies with travel demand. Transportation Res. Part B: Methodological 84(10):55–80.Crossref, Google Scholar
• [72] Ordóñez F, Stier-Moses NE (2010) Wardrop equilibria with risk-averse users. Transportation Sci. 44(1):63–86.Link, Google Scholar
• [73] Paccagnan D, Chandan R, Ferguson B, Marden J (2021) Optimal taxes in atomic congestion games. ACM Trans. Econom. Comput. 9(3):19:1–19:33.Google Scholar
• [74] Patriksson M (2004) Sensitivity analysis of traffic equilibria. Transportation Sci. 38(3):258–281.Link, Google Scholar
• [75] Roughgarden T (2003) The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2):341–364.Crossref, Google Scholar
• [76] 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
• [77] Roughgarden T (2012) Intrinsic robustness of the price of anarchy. Comm. ACM 55(7):116–123.Crossref, Google Scholar
• [78] Roughgarden T, Tardos É (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• [79] Rubinstein A (2017) Honest signaling in zero-sum games is hard, and lying is even harder. ICALP’17: Proc. 44th Internat. Colloquium Automata Languages Programming, Leibniz International Proceedings in Informatics (LIPIcs), vol. 80 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 77:1–77:13.Google Scholar
• [80] Ruszczyński A (2006) Nonlinear Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [81] Transportation Networks for Research Core Team (2022) Transportation networks for research. Accessed January 14, 2022, https://github.com/bstabler/TransportationNetworks.Google Scholar
• [82] Valiant G, Roughgarden T (2010) Braess’s paradox in large random graphs. Random Structures Algorithms 37(4):495–515.Crossref, Google Scholar
• [83] Vasserman S, Feldman M, Hassidim A (2015) Implementing the wisdom of Waze. Yang Q, Wooldridge M, eds. IJCAI’15: Proc. 24th Internat. Joint Conf. Artificial Intelligence (AAAI Press, Washington, DC), 660–666.Google Scholar
• [84] Virtanen P, Gommers R, Oliphant TE, Haberland M, Reddy T, Cournapeau D, Burovski E, et al. (2020) SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods 17:261–272.Crossref, Google Scholar
• [85] 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
• [86] Warode P (2022) Parametric computation of equilibria and flows. PhD thesis, Technische Universität Berlin, Berlin.Google Scholar
• [87] Wu M, Amin S, Ozdaglar A (2021a) Value of information in Bayesian routing games. Oper. Res. 69(1):148–163.Link, Google Scholar
• [88] Wu Z, Möhring RH, Chen Y, Xu D (2021b) Selfishness need not be bad. Oper. Res. 69(2):410–435.Link, Google Scholar
• [89] Wu Z, Möhring RH, Ren C, Xu D (2023) A convergence analysis of the price of anarchy in atomic congestion games. Math. Programming 199:937–993.Crossref, Google Scholar
• [90] Xu H (2020) On the tractability of public persuasion with no externalities. SODA’20: Proc. 31st Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 2708–2727.Google Scholar
• [91] Youn H, Gastner MT, Jeong H (2008) Price of anarchy in transportation networks: Efficiency and optimality control. Phys. Rev. Lett. 101:128701.Crossref, Google Scholar
• [92] Zhou C, Nguyen TH, Xu H (2022) Algorithmic information design in multi-player games: Possibilities and limits in singleton congestion. EC’22: Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 869.Google Scholar
• [93] 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
• [94] Zu Y, Iyer K, Xu H (2021) Learning to persuade on the fly: Robustness against ignorance. EC’21: Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 927–928.Google Scholar