[1] |
D. Acemoglu, A. Ozdaglar, Flow control, routing, and performance under monopoly pricing, Technical Report WP-1696, MIT LIDS, 2003 |

[2] |
Aho, A. V.; Hopcroft, J. E.; Ullman, J. D.: The design and analysis of computer algorithms. (1974) · Zbl 0326.68005 |

[3] |
Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B.: Network flows: theory, algorithms, and applications. (1993) · Zbl 1201.90001 |

[4] |
E. Altman, R. El Azouzi, O. Pourtallier, Avoiding paradoxes in routing games, in: Proceedings of the 17th International Teletraffic Conference, 2001 · Zbl 1069.68507 |

[5] |
E. Anshelevich, A. Dasgupta, É. Tardos, T. Wexler, Near-optimal network design with selfish agents, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 511 -- 520 · Zbl 1192.68019 |

[6] |
Arnott, R.; De Palma, A.; Lindsey, R.: Properties of dynamic traffic equilibrium involving bottlenecks, including a paradox and metering. Transportation sci. 27, No. 2, 148-160 (1993) · Zbl 0788.90028 |

[7] |
Arnott, R.; Small, K.: The economics of traffic congestion. American scientist 82, No. 5, 446-455 (1994) |

[8] |
Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45, No. 3, 501-555 (1998) · Zbl 1065.68570 |

[9] |
Arora, S.; Safra, S.: Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, No. 1, 70-122 (1998) · Zbl 0903.68076 |

[10] |
Bass, T.: Road to ruin. Discover 13, No. 5, 56-61 (1992) |

[11] |
Bean, N.: Secrets of network success. Phys. world 9, No. 2, 30-33 (1996) |

[12] |
Bean, N. G.; Kelly, F. P.; Taylor, P. G.: Braess’s paradox in a loss network. J. appl. Probab. 34, No. 1, 155-159 (1997) · Zbl 0883.60088 |

[13] |
Beckmann, M.; Mcguire, C. B.; Winsten, C. B.: Studies in the economics of transportation. (1956) |

[14] |
Boyce, D. E.; Soberanes, J. L.: Solutions to the optimal network design problem with shipments related to transportation cost. Transportation res. Ser. B 13, No. 1, 65-80 (1979) |

[15] |
Braess, D.: Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12, No. 4, 258-268 (1968) · Zbl 0167.48305 |

[16] |
Calvert, B.: The downs -- thomson effect in a Markov process. Probab. engrg. Inform. sci. 11, No. 3, 327-340 (1997) · Zbl 1096.60520 |

[17] |
Calvert, B.; Keady, G.: Braess’s paradox and power-law nonlinearities in networks. J. austral. Math. soc. Ser. B 35, No. 1, 1-22 (1993) · Zbl 0788.90018 |

[18] |
Calvert, B.; Solomon, W.; Ziedins, I.: Braess’s paradox in a queueing network with state-dependent routing. J. appl. Probab. 34, No. 1, 134-154 (1997) · Zbl 0872.90039 |

[19] |
Catoni, S.; Pallottino, S.: Traffic equilibrium paradoxes. Transportation sci. 25, No. 3, 240-244 (1991) · Zbl 0729.90987 |

[20] |
Chau, C. K.; Sim, K. M.: The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands. Oper. res. Lett. 31, No. 5, 327-335 (2003) · Zbl 1052.91009 |

[21] |
Cocchi, R.; Shenker, S. J.; Estrin, D.; Zhang, L.: Pricing in computer networks: motivation, formulation, and example. IEEE/ACM trans. Networking 1, No. 6, 614-627 (1993) |

[22] |
Cohen, J. E.: The counterintuitive in conflict and cooperation. American scientist 76, No. 6, 577-584 (1988) |

[23] |
Cohen, J. E.; Horowitz, P.: Paradoxical behavior of mechanical and electrical networks. Nature 352, 699-701 (August 1991) |

[24] |
Cohen, J. E.; Jeffries, C.: Congestion resulting from increased capacity in single-server queueing networks. IEEE/ACM trans. Commun. 5, No. 2, 305-310 (1997) |

[25] |
Cohen, J. E.; Kelly, F. P.: A paradox of congestion in a queuing network. J. appl. Probab. 27, No. 3, 730-734 (1990) · Zbl 0718.60105 |

[26] |
R. Cole, Y. Dodis, T. Roughgarden, How much can taxes help selfish routing? in: Proceedings of the Fourth Annual ACM Conference on Electronic Commerce, 2003, pp. 98 -- 107; J. Comput. System Sci., in press · Zbl 1103.68018 |

[27] |
R. Cole, Y. Dodis, T. Roughgarden, Pricing network edges for heterogeneous selfish users, in: Proceedings of the 35th Annual ACM Symposium on the Theory of Computing, 2003, pp. 521 -- 530 · Zbl 1192.68032 |

[28] |
Correa, J. R.; Schulz, A. S.; Moses, N. E. Stier: Computational complexity, fairness, and the price of anarchy of the maximum latency problem. Lecture notes in comput. Sci. 3064, 59-73 (2004) · Zbl 1092.90515 |

[29] |
Correa, J. R.; Schulz, A. S.; Moses, N. E. Stier: Selfish routing in capacitated networks. Math. oper. Res. 29, No. 4, 961-976 (2004) · Zbl 1082.90009 |

[30] |
Cottle, R. W.; Pang, J.; Stone, R. E.: The linear complementarity problem. (1992) · Zbl 0757.90078 |

[31] |
A. Czumaj, P. Krysta, B. Vöcking, Selfish traffic allocation for server farms, in: Proceedings of the 34th Annual ACM Symposium on the Theory of Computing, 2002, pp. 287 -- 296 · Zbl 1192.68033 |

[32] |
A. Czumaj, B. Vöcking, Tight bounds for worst-case equilibria, in: Proceedings of the 13th Annual Symposium on Discrete Algorithms, 2002, pp. 413 -- 420 · Zbl 1092.91508 |

[33] |
Dafermos, S. C.; Nagurney, A.: On some traffic equilibrium theory paradoxes. Transportation res. Ser. B 18, No. 2, 101-110 (1984) |

[34] |
Dafermos, S. C.; Sparrow, F. T.: The traffic assignment problem for a general network. J. res. National bureau standards ser. B 73, No. 2, 91-118 (1969) · Zbl 0197.46003 |

[35] |
Daganzo, C. F.: Queue spillovers in transportation networks with a route choice. Transportation sci. 32, No. 1, 3-11 (1998) · Zbl 0987.90508 |

[36] |
Dionne, R.; Florian, M.: Exact and approximate algorithms for optimal network design. Networks 9, No. 1, 37-59 (1979) · Zbl 0397.94024 |

[37] |
Downs, A.: The law of peak-hour expressway congestion. Traffic quarterly 16, No. 3, 393-409 (1962) |

[38] |
Dubey, P.: Inefficiency of Nash equilibria. Math. oper. Res. 11, No. 1, 1-8 (1986) · Zbl 0592.90100 |

[39] |
R. El Azouzi, E. Altman, O. Pourtallier, Properties of equilibria in competitive routing with several user types, in: Proceedings of the 41st IEEE Conference on Decision and Control, vol. 4, 2002, pp. 3646 -- 3651 |

[40] |
A. Fabrikant, A. Luthra, E. Maneva, C.H. Papadimitriou, S.J. Shenker, On a network creation game, in: Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing, 2003, pp. 347 -- 351 · Zbl 1322.91013 |

[41] |
Feige, U.; Goldwasser, S.; Lovász, L.; Safra, S.; Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43, No. 2, 268-292 (1996) · Zbl 0882.68129 |

[42] |
Fisk, C.: More paradoxes in the equilibrium assignment problem. Transportation res. Ser. B 13, No. 4, 305-309 (1979) |

[43] |
Florian, M.; Hearn, D.: Network equilibrium models and algorithms. Network routing, 485-550 (1995) · Zbl 0864.90042 |

[44] |
Fortune, S.; Hopcroft, J. E.; Wyllie, J. C.: The directed subgraph homeomorphism problem. Theoret. comput. Sci. 10, No. 2, 111-121 (1980) · Zbl 0419.05028 |

[45] |
Frank, M.: The braess paradox. Math. program. 20, No. 3, 283-302 (1981) · Zbl 0468.90078 |

[46] |
Frank, M.: Cost-deceptive links on ladder networks. Methods oper. Res. 45, 75-86 (1983) · Zbl 0524.90036 |

[47] |
Friedman, E. J.: Genericity and congestion control in selfish routing. Proceedings of the 43rd annual IEEE conference on decision and control (CDC), 4667-4672 (2004) |

[48] |
Garcia, C. B.; Zangwill, W. I.: Pathways to solutions, fixed points, and equilibria. (1981) · Zbl 0512.90070 |

[49] |
Garey, M. R.; Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness. (1979) · Zbl 0411.68039 |

[50] |
Goemans, M. X.; Williamson, D. P.: The primal-dual method for approximation algorithms and its application to network design problems. Approximation algorithms for NP-hard problems, 144-191 (1997) |

[51] |
Grötschel, M.; Lovász, L.; Schrijver, A.: Geometric algorithms and combinatorial optimization. (1988) · Zbl 0634.05001 |

[52] |
J.N. Hagstrom, R.A. Abrams, Characterizing Braess’s paradox for traffic networks, in: Proceedings of the Fourth IEEE Conference on Intelligent Transportation Systems, 2001, pp. 837 -- 842 |

[53] |
Hall, M. A.: Properties of the equilibrium state in transportation networks. Transportation sci. 12, No. 3, 208-216 (1978) |

[54] |
Hoc, H. H.: A computational approach to the selection of an optimal network. Management sci. 19, No. 5, 488-498 (1973) · Zbl 0249.90024 |

[55] |
Irvine, A. D.: How braess’ paradox solves newcomb’s problem. Int. stud. Philos. sci. 7, No. 2, 141-160 (1993) |

[56] |
H. Kameda, How harmful the paradox can be in the Braess/Cohen -- Kelly -- Jeffries networks, in: Proceedings of 21st INFOCOM Conference, vol. 1, 2002, pp. 437 -- 445 |

[57] |
Kameda, H.; Altman, E.; Kozawa, T.; Hosokawa, Y.: Braess-like paradoxes in distributed computer systems. IEEE trans. Automat. control 45, No. 9, 1687-1691 (2000) · Zbl 0972.68012 |

[58] |
H. Kameda, E. Altman, J. Li, Y. Hosokawa, Paradoxes in performance optimization of distributed systems, in: Proceedings of the International Conference on Advances in Infrastructure for Electronic Business, Science, and Education on the Internet, 2000 · Zbl 0972.68012 |

[59] |
G. Keady, The Colebrook -- White formula for pipe networks, Electronic report, Department of Mathematics, University of Western Australia, 1995 |

[60] |
Kelly, F. P.: Network routing. Philos. trans. R. soc. London ser. 337, No. 1641, 343-367 (1991) · Zbl 0746.90023 |

[61] |
Khuller, S.: Approximation algorithms for finding highly connected subgraphs. Approximation algorithms for NP-hard problems, 236-265 (1997) |

[62] |
Knight, F. H.: Some fallacies in the interpretation of social cost. Quart. J. Econ. 38, No. 4, 582-606 (1924) |

[63] |
G. Kolata, What if they closed 42nd Street and nobody noticed? New York Times, December 25, 1990, p. 38 |

[64] |
Korilis, Y. A.; Lazar, A. A.; Orda, A.: Achieving network optima using Stackelberg routing strategies. IEEE/ACM trans. Networking 5, No. 1, 161-173 (1997) |

[65] |
Korilis, Y. A.; Lazar, A. A.; Orda, A.: Capacity allocation under noncooperative routing. IEEE trans. Automat. control 42, No. 3, 309-325 (1997) · Zbl 0872.90035 |

[66] |
Korilis, Y. A.; Lazar, A. A.; Orda, A.: Avoiding the braess paradox in noncooperative networks. J. appl. Probab. 36, No. 1, 211-222 (1999) · Zbl 0942.60091 |

[67] |
Körner, T. W.: The pleasures of counting. (1996) · Zbl 0865.00003 |

[68] |
E. Koutsoupias, C.H. Papadimitriou, Worst-case equilibria, in: Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1999, pp. 404 -- 413 · Zbl 1099.91501 |

[69] |
Leblanc, L. J.: An algorithm for the discrete network design problem. Transportation res. 9, No. 3, 183-199 (1975) |

[70] |
Libman, L.; Orda, A.: The designer’s perspective to atomic noncooperative networks. IEEE/ACM trans. Networking 7, No. 6, 875-884 (1999) |

[71] |
H. Lin, personal communication, December, 2003 |

[72] |
H. Lin, T. Roughgarden, É. Tardos, A stronger bound on Braess’s Paradox, in: Proceedings of the 15th Annual Symposium on Discrete Algorithms, 2004, pp. 333 -- 334 · Zbl 1318.90016 |

[73] |
Lin, H.; Roughgarden, T.; Tardos, É.; Walkover, A.: Braess’s paradox, Fibonacci numbers, and exponential inapproximability. Lecture notes in comput. Sci. 3580, 497-512 (2005) · Zbl 1084.90044 |

[74] |
Magnanti, T. L.; Wong, R. T.: Network design and transportation planning: models and algorithms. Transportation sci. 18, No. 1, 1-55 (1984) |

[75] |
Marinoff, L.: How braess’ paradox solves newcomb’s problem: not!. Int. stud. Philos. sci. 10, No. 3, 217-237 (1996) |

[76] |
M. Mavronicolas, P. Spirakis, The price of selfish routing, in: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, 2001, pp. 510 -- 519 · Zbl 1323.91006 |

[77] |
I. Milchtaich, Network topology and the efficiency of equilibrium, Working paper 12-01, Department of Economics, Bar-Ilan University, Israel, 2001 |

[78] |
Murchland, J. D.: Braess’s paradox of traffic flow. Transportation res. 4, No. 4, 391-394 (1970) |

[79] |
Nagurney, A.: Network economics: A variational inequality approach. (1993) · Zbl 0873.90015 |

[80] |
Nagurney, A.: Sustainable transportation networks. (2000) |

[81] |
Newell, G. F.: Traffic flow on transportation networks. (1980) |

[82] |
C.H. Papadimitriou, Algorithms, games, and the Internet, in: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing 2001, pp. 749 -- 753 · Zbl 1323.68022 |

[83] |
Pas, E. I.; Principio, S. L.: Braess’ paradox: some new insights. Transportation res. Ser. B 31, No. 3, 265-276 (1997) |

[84] |
Penchina, C. M.: Braess paradox: maximum penalty in a minimal critical network. Transportation res. Ser. A 31, No. 5, 379-388 (1997) |

[85] |
Peterson, I.: Strings and springs net mechanical surprise. Science news 140, No. 8, 118 (1991) |

[86] |
Pigou, A. C.: The economics of welfare. (1920) |

[87] |
Raghavachari, B.: Algorithms for finding low degree structures. Approximation algorithms for NP-hard problems, 266-295 (1997) |

[88] |
Ridley, T. M.: An investment policy to reduce the travel time in a transportation network. Transportation res. 2, No. 4, 409-424 (1968) |

[89] |
Roughgarden, T.: Stackelberg scheduling strategies. SIAM J. Comput. 33, No. 2, 332-350 (2004) · Zbl 1080.90046 |

[90] |
T. Roughgarden, How unfair is optimal routing? In: Proceedings of the 13th Annual Symposium on Discrete Algorithms, 2002, pp. 203 -- 204 · Zbl 1258.90017 |

[91] |
Roughgarden, T.: The price of anarchy is independent of the network topology. J. comput. System sci. 67, No. 2, 341-364 (2003) · Zbl 1072.68025 |

[92] |
T. Roughgarden, The maximum latency of selfish routing, in: Proceedings of the 15th Annual Symposium on Discrete Algorithms, 2004, pp. 973 -- 974 |

[93] |
T. Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, 2005, in press · Zbl 1318.68065 |

[94] |
Roughgarden, T.; Tardos, É.: How bad is selfish routing?. J. ACM 49, No. 2, 236-259 (2002) · Zbl 1323.90011 |

[95] |
Roughgarden, T.; Tardos, É.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games econ. Behav. 47, No. 2, 389-403 (2004) · Zbl 1068.91002 |

[96] |
L. Schulman, personal communication, October, 1999 |

[97] |
Scott, A. J.: The optimal network problem: some computational procedures. Transportation res. 3, No. 2, 201-210 (1969) |

[98] |
Sheffi, Y.: Urban transportation networks: equilibrium analysis with mathematical programming methods. (1985) |

[99] |
Shenker, S. J.: Making greed work in networks: A game-theoretic analysis of switch service disciplines. IEEE/ACM trans. Networking 3, No. 6, 819-831 (1995) |

[100] |
Smith, M. J.: In a road network, increasing delay locally can reduce delay globally. Transportation res. 12, No. 6, 419-422 (1978) |

[101] |
Steinberg, R.; Stone, R. E.: The prevalence of paradoxes in transportation equilibrium problems. Transportation sci. 22, No. 4, 231-241 (1988) · Zbl 0661.90029 |

[102] |
Steinberg, R.; Zangwill, W. I.: The prevalence of braess’ paradox. Transportation sci. 17, No. 3, 301-318 (1983) |

[103] |
Straffin, P. D.: Game theory and strategy. (1993) · Zbl 0948.91502 |

[104] |
Taguchi, A.: Braess’ paradox in a two-terminal transportation network. J. oper. Res. soc. Japan 25, No. 4, 376-388 (1982) · Zbl 0502.90025 |

[105] |
É. Tardos, A. Walkover, personal communication, November, 2003 |

[106] |
Tarjan, R. E.: Data structures and network algorithms. (1983) · Zbl 0584.68077 |

[107] |
Thomson, J. M.: Great cities and their traffic. (1977) |

[108] |
A. Vetta, Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions, in: Proceedings of the 43rd Annual Symposium on Foundations of Computer Science, 2002, pp. 416 -- 425 |

[109] |
Vickrey, W. S.: Congestion theory and transport investment. Amer. econ. Rev. 59, No. 2, 251-260 (1969) |

[110] |
J.G. Wardrop, Some theoretical aspects of road traffic research, in: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, 1952, pp. 325 -- 378 |

[111] |
D. Weitz, The price of anarchy, unpublished manuscript, 2001 |

[112] |
Whitt, W.: Counterexamples for comparisons of queues with finite waiting rooms. Queueing syst. 10, No. 3, 271-278 (1992) · Zbl 0747.60091 |

[113] |
Wong, R. T.: Introduction and recent advances in network design: models and algorithms. Transportation planning models, 187-225 (1984) |

[114] |
Yang, H.; Bell, M. G. H.: A capacity paradox in network design and how to avoid it. Transportation res. Ser. A 32, No. 7, 539-545 (1998) |