zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
On the severity of Braess’s paradox: designing networks for selfish users is hard. (English) Zbl 1094.68122
Summary: We consider a directed network in which every edge possesses a latency function that specifies the time needed to traverse the edge given its congestion. Selfish, noncooperative agents constitute the network traffic and wish to travel from a source vertex $s$ to a destination $t$ as quickly as possible. Since the route chosen by one network user affects the congestion experienced by others, we model the problem as a noncooperative game. Assuming that each agent controls only a negligible portion of the overall traffic, Nash equilibria in this noncooperative game correspond to $s-t$ flows in which all flow paths have equal latency. A natural measure for the performance of a network used by selfish agents is the common latency experienced by users in a Nash equilibrium. Braess’s Paradox is the counterintuitive but well-known fact that removing edges from a network can improve its performance. Braess’s Paradox motivates the following network design problem: given a network, which edges should be removed to obtain the best flow at Nash equilibrium? Equivalently, given a network of edges that can be built, which subnetwork will exhibit the best performance when used selfishly? We give optimal inapproximability results and approximation algorithms for this network design problem. For example, we prove that there is no approximation algorithm for this problem with approximation ratio less than $n/2$, where $n$ is the number of network vertices, unless P = NP. We further show that this hardness result is the best possible, by exhibiting an $(n/2)$-approximation algorithm. We also prove tight inapproximability results when additional structure, such as linearity, is imposed on the network latency functions.Moreover, we prove that an optimal approximation algorithm for these problems is the trivial algorithm: given a network of candidate edges, build the entire network. As a consequence, we show that Braess’s Paradox -- even in its worst-possible manifestations -- is impossible to detect efficiently. En route to these results, we give a fundamental generalization of Braess’s Paradox: the improvement in performance that can be effected by removing edges can be arbitrarily large in large networks. Even though Braess’s Paradox has enjoyed 35 years as a textbook example, our result is the first to extend its severity beyond that in Braess’s original four-node network.

MSC:
68W25Approximation algorithms
68Q17Computational difficulty of problems
90B10Network models, deterministic (optimization)
90B20Traffic problems
91A10Noncooperative games
WorldCat.org
Full Text: DOI
References:
[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)