Matroids Are Immune to Braess’ Paradox

References

• Ackermann H, Röglin H, Vöcking B (2008) On the impact of combinatorial structure on congestion games. J. ACM 55(6):1–22.Crossref, Google Scholar
• Ackermann H, Röglin H, Vöcking B (2009) Pure Nash equilibria in player-specific and weighted congestion games. Theoret. Comput. Sci. 410(17):1552–1563.Crossref, Google Scholar
• Balinski ML (1961) On the graph structure of convex polyhedra in n-space. Pacific J. Math. 11(2):431–434.Crossref, Google Scholar
• Beckmann M, McGuire C, Winsten C (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• Bhaskar U, Fleischer L, Hoy D, Huang C (2015) On the uniqueness of equilibrium in atomic splittable routing games. Math. Oper. Res. 40(3):634–654.Link, Google Scholar
• Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258–268.Google Scholar
• Braess D, Nagurney A, Wakolbinger T (2005) On a paradox of traffic planning. Transportation Sci. 39(4):446–450.Link, Google Scholar
• Catoni S, Pallotino S (1991) Traffic equilibrium paradoxes. Transportation Sci. 25(3):240–244.Link, Google Scholar
• Cenciarelli P, Gorla D, Salvo I (2016) Graph theoretic investigations on inefficiencies in network models. Preprint arXiv:1603.01983.Google Scholar
• Chen X, Diao Z, Hu X (2015) Excluding Braess’s paradox in nonatomic selfish routing. Hoefer M, ed. Proc. 8th Internat. Sympos. Algorithmic Game Theory, Lecture Notes in Computer Science, Vol. 9347 (Springer, Berlin), 219–230.Crossref, Google Scholar
• Cohen J, Kelly F (1990) A paradox of congestion in a queuing network. J. Appl. Prob. 27(3):730–734.Crossref, Google Scholar
• Cohen JE, Horowitz P (1991) Paradoxial behaviour of mechanical and electrical networks. Nature 352(6337):699–701.Crossref, Google Scholar
• Cominetti R, Correa JR, Stier-Moses NE (2009) The impact of oligopolistic competition in networks. Oper. Res. 57(6):1421–1437.Link, Google Scholar
• Correa JR, Stier-Moses NE (2011) Wardrop equilibria. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, New York).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
• Dafermos S, Nagurney A (1984) On some traffic equilibrium theory paradoxes. Transportation Res. Part B: Methodological 18(2): 101–110.Crossref, Google Scholar
• Edmonds J (1971) Submodular functions, matroids, and certain polyhedra. Guy R, ed. Combinatorial Structures and Their Applications (Gordon and Breach, New York), 69–87.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
• Fotakis D, Kaporis AC, Lianeas T, Spirakis PG (2013) Resolving Braess’s paradox in random networks. Chen Y, Immorlica N, eds. Proc. 9th Internat. Conf. Web Internet Econom. (Springer, Berlin), 188–201.Crossref, Google Scholar
• Frank M (1981) The Braess paradox. Math. Programming 20(1):283–302.Crossref, Google Scholar
• Fujishige S (2005) Submodular Functions and Optimization (Elsevier, Amsterdam).Google Scholar
• Hagstrom JN, Abrams RA (2001) Characterizing Braess’s paradox for traffic networks. Proc. IEEE 2001 Conf. Intelligent Transportation Systems (IEEE, Piscataway, NJ), 836–841.Crossref, 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
• Harks T, Peis B (2014) Resource buying games. Algorithmica 70(3):493–512.Crossref, Google Scholar
• Harks T, Klimm M, Peis B (2014) Resource competition on integral polymatroids. Liu T-Y, Qi Q, Ye Y, eds. Web and Internet Economics. Lecture Notes in Computer Science, Vol. 8877 (Springer, Berlin), 189–202.Crossref, Google Scholar
• Holzman R, Law-Yone N (1997) Strong equilibrium in congestion games. Games Econom. Behav. 21(1–2):85–101.Crossref, Google Scholar
• Holzman R, Law-Yone N (2003) Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46(2):193–205.Crossref, Google Scholar
• Kameda H (2002) How harmful the paradox can be in the Braess/Cohen-Kelly-Jeffries networks. IEEE INFOCOM (IEEE, Piscataway, NJ), 437–445.Crossref, Google Scholar
• Kameda H, Altman E, Kozawa T, Hosokawa Y (2000) Braess-like paradoxes in distributed computer systems. IEEE Trans. Automatic Control 45(9):1687–1691.Crossref, Google Scholar
• Korilis YA, Lazar AA, Orda A (1999) Avoiding the Braess paradox in noncooperative networks. J. Appl. Probab. 36(1):211–222.Crossref, Google Scholar
• Lin HC, Roughgarden T, Tardos É, Walkover A (2011) Stronger bounds on Braess’s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4):1667–1686.Crossref, Google Scholar
• Milchtaich I (1996) Congestion models of competition. Amer. Naturalist 147(5):760–783.Crossref, Google Scholar
• Milchtaich I (2005) Topological conditions for uniqueness of equilibrium in networks. Math. Oper. Res. 30(1):225–244.Link, Google Scholar
• Milchtaich I (2006) Network topology and the efficiency of equilibrium. Games Econom. Behav. 57(2):321–346.Crossref, Google Scholar
• Murota K (2003) Discrete Convex Analysis (SIAM, Philadelphia).Crossref, Google Scholar
• Oxley JG (1992) Matroid Theory (Oxford University Press, Oxford, UK).Google Scholar
• Pas EI, Principio SL (1997) Braess’ paradox: Some new insights. Transportation Res. Part B: Methodological 31(3):265–276.Crossref, Google Scholar
• Pöppe C (1992) Paradoxes Verhalten physikalischer und ökonomischer Systeme. Spektrum der Wissenschaft (November):23–26.Google Scholar
• Qiu L, Yang Y, Zhang Y, Shenker S (2006) On selfish routing in Internet-like environments. IEEE/ACM Trans. Networking 14(4): 725–738.Crossref, Google Scholar
• Richman O, Shimkin N (2007) Topological uniqueness of the Nash equilibrium for selfish routing with atomic users. Math. Oper. Res. 32(1):215–232.Link, Google Scholar
• Rosenthal R (1973) A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory 2(1):65–67.Crossref, Google Scholar
• Rosenthal R (1973) The network equilibrium problem in integers. Networks 3(1):53–59.Crossref, Google Scholar
• Roughgarden T (2002) Selfish routing. Unpublished doctoral dissertation, Cornell University, Ithaca, NY.Google Scholar
• Roughgarden T (2002) 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
• Samuelson P (1992) Tragedy of the open road: Avoiding paradox by use of regulated public utilities that charge corrected Knightian tolls. J. Internat. Comparative Econom.: JOICE 1(1):3–12.Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Smith M (1978) In a road network, increasing delay locally can reduce delay globally. Transportation Res. 12(6):419–422.Crossref, Google Scholar
• Steinberg R, Zangwill W (1983) The prevalence of Braess’s paradox. Transportation Sci. 17(3):301–318.Link, Google Scholar
• Thomas RR (1998) Applications to integer programming. Cox DA, Sturmfels B, eds. Proc. Symposia Appl. Math., Vol. 53 (American Mathematical Society, Providence, RI), 119–141.Google Scholar
• Valiant G, Roughgarden T (2010) Braess’s paradox in large random graphs. Random Structures Algorithms 37(4):495–515.Crossref, Google Scholar
• Wardrop J (1952) Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrg. 1(Part II):325–378.Crossref, Google Scholar
• Welsh DJA (2010) Matroid Theory. First published by Academic Press, 1976 (Dover, New York).Google Scholar