Namespaces
Variants
Actions

Difference between revisions of "Braess paradox"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (AUTOMATIC EDIT (latexlist): Replaced 52 formulas out of 55 by TEX code with an average confidence of 2.0 and a minimal confidence of 2.0.)
Line 1: Line 1:
 +
<!--This article has been texified automatically. Since there was no Nroff source code for this article,
 +
the semi-automatic procedure described at https://encyclopediaofmath.org/wiki/User:Maximilian_Janisch/latexlist
 +
was used.
 +
If the TeX and formula formatting is correct, please remove this message and the {{TEX|semi-auto}} category.
 +
 +
Out of 55 formulas, 52 were replaced by TEX code.-->
 +
 +
{{TEX|semi-auto}}{{TEX|partial}}
 
The words  "Braess's paradox"  refer to a surprising decrease in performance for some network, which is a result of it being improved locally. The occurrence of this decrease has been studied in mathematical models of equilibrium flow in road/rail traffic, computer networks, telephone networks, water supply systems, electrical circuits, spring systems, and so on. This has been done under various assumptions on routing schemes, such as being state-dependent or fixed.
 
The words  "Braess's paradox"  refer to a surprising decrease in performance for some network, which is a result of it being improved locally. The occurrence of this decrease has been studied in mathematical models of equilibrium flow in road/rail traffic, computer networks, telephone networks, water supply systems, electrical circuits, spring systems, and so on. This has been done under various assumptions on routing schemes, such as being state-dependent or fixed.
  
 
Below, the occurrence of Braess's paradox in a classical model of user equilibrium traffic flow is given.
 
Below, the occurrence of Braess's paradox in a classical model of user equilibrium traffic flow is given.
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302101.png" /> be a finite directed [[Graph|graph]], with node set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302102.png" /> and arc, branch or link set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302103.png" /> (cf. also [[Graph, oriented|Graph, oriented]]). A path in which all links are similarly directed is called a route, with the initial and final nodes forming an origin/destination pair (or O/D pair). One considers a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302104.png" /> of O/D pairs, and for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302105.png" />, supposes a flow demand <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302106.png" /> to be given. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302107.png" /> be a set of routes joining <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302108.png" />. For each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b1302109.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021010.png" />, one considers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021011.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021012.png" />, giving a route flow vector <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021013.png" />. This route flow induces a link flow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021014.png" />, by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021015.png" /> for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021016.png" />, where one identifies a route with the set of its links. For each link <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021017.png" />, one supposes a link cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021018.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021020.png" /> are given. For <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021021.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021022.png" />, one defines a route cost by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021023.png" />.
+
Let $( N , B )$ be a finite directed [[Graph|graph]], with node set $N$ and arc, branch or link set $B$ (cf. also [[Graph, oriented|Graph, oriented]]). A path in which all links are similarly directed is called a route, with the initial and final nodes forming an origin/destination pair (or O/D pair). One considers a set $W$ of O/D pairs, and for each $w \in W$, supposes a flow demand $d _ { w } &gt; 0$ to be given. Let $R _ { w }$ be a set of routes joining $w$. For each $w \in W$, and $r \in R _ { w }$, one considers $F _ { r } \geq 0$ such that $\sum _ { r \in R _ { W } } F _ { r } = d _ { W }$, giving a route flow vector $F = ( F _ { r } ) _ { r \in R _ { W } , w \in W }$. This route flow induces a link flow $f = ( f _ { b } ) _ { b \in B }$, by $f _ { b } = \sum _ { r \ni b } F _ { r }$ for each $b$, where one identifies a route with the set of its links. For each link $a$, one supposes a link cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021018.png"/>, where $g _ { ab }$ and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021020.png"/> are given. For $r \in R _ { w }$, $w \in W$, one defines a route cost by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021023.png"/>.
  
A route flow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021024.png" /> is a user equilibrium if it satisfies the condition that for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021026.png" />, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021027.png" /> then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021028.png" />. In other words, there is, for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021029.png" />, a common route cost <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021030.png" /> for all routes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021031.png" /> with non-zero <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021032.png" />. A user equilibrium flow exists always [[#References|[a5]]], and if the matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021033.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021034.png" /> is positive-definite, then the equilibrium link flows, and hence the route costs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021035.png" />, are unique. In [[#References|[a3]]], Braess's paradox is said to occur if adding a new route <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021036.png" /> to some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021037.png" /> results in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021038.png" /> being increased. See also [[#References|[a3]]] for necessary and sufficient conditions for this to happen under the assumption that there is a strictly positive equilibrium flow in all routes.
+
A route flow $H$ is a user equilibrium if it satisfies the condition that for all $r , s \in R _ { w }$, $w \in W$, if $C _ { r } &lt; C _ { s }$ then $H _ { S } = 0$. In other words, there is, for each $w$, a common route cost $\gamma _ { w }$ for all routes $r \in R _ { w }$ with non-zero $H _ { r }$. A user equilibrium flow exists always [[#References|[a5]]], and if the matrix $g = g _ { a b }$ is such that $g + g ^ { T }$ is positive-definite, then the equilibrium link flows, and hence the route costs $\gamma _ { w }$, are unique. In [[#References|[a3]]], Braess's paradox is said to occur if adding a new route $r$ to some $R _ { w }$ results in $\gamma _ { w }$ being increased. See also [[#References|[a3]]] for necessary and sufficient conditions for this to happen under the assumption that there is a strictly positive equilibrium flow in all routes.
  
There is no fixed definition of Braess's paradox in all systems, but there is a common theme. One assumes some measure of performance, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021039.png" />, such as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021040.png" />. On the network given by any one link <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021041.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021042.png" /> depends on the flow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021043.png" /> and a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021044.png" />. For example, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021045.png" /> if the link is given by an M/M/1 queue (cf. also [[Queue|Queue]]). Note that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021046.png" /> decreases if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021047.png" /> increases, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021048.png" /> fixed. Suppose some flow demand is fixed and link flows are given by some requirement about equilibria, or by a given dynamical process not in equilibrium. One says that Braess's paradox occurs if, for the network as a whole, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021049.png" /> increases when some <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021050.png" /> increases. Adding links may be thought of as changing a parameter <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021051.png" /> from zero or infinity. A different language would be used to describe certain other types of networks, such as electrical circuits.
+
There is no fixed definition of Braess's paradox in all systems, but there is a common theme. One assumes some measure of performance, $t$, such as $\gamma _ { w }$. On the network given by any one link $b$, $t$ depends on the flow $f$ and a parameter $k_b$. For example, $t = 1 / ( k _ { b } - f )$ if the link is given by an M/M/1 queue (cf. also [[Queue|Queue]]). Note that $t$ decreases if $k_b$ increases, for $f$ fixed. Suppose some flow demand is fixed and link flows are given by some requirement about equilibria, or by a given dynamical process not in equilibrium. One says that Braess's paradox occurs if, for the network as a whole, $t$ increases when some $k_b$ increases. Adding links may be thought of as changing a parameter $k_b$ from zero or infinity. A different language would be used to describe certain other types of networks, such as electrical circuits.
  
Under this description, the Downs–Thomson paradox [[#References|[a4]]] is a particular type of Braess's paradox. If one distinguishes these paradoxes mathematically, it is by requiring the link costs <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021052.png" /> in the Braess paradox to be increasing functions of the link flow <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021053.png" />, while in the Downs–Thomson paradox there is a link with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021054.png" /> a decreasing function of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b130/b130210/b13021055.png" />.
+
Under this description, the Downs–Thomson paradox [[#References|[a4]]] is a particular type of Braess's paradox. If one distinguishes these paradoxes mathematically, it is by requiring the link costs $t$ in the Braess paradox to be increasing functions of the link flow $f$, while in the Downs–Thomson paradox there is a link with $t$ a decreasing function of $f$.
  
 
Independent discoveries of Braess's paradox can be attributed to D. Braess [[#References|[a1]]], A. Downs [[#References|[a4]]], J.M. Thomson [[#References|[a6]]] and C.A. Zukowski and J.L. Wyatt [[#References|[a7]]].
 
Independent discoveries of Braess's paradox can be attributed to D. Braess [[#References|[a1]]], A. Downs [[#References|[a4]]], J.M. Thomson [[#References|[a6]]] and C.A. Zukowski and J.L. Wyatt [[#References|[a7]]].
Line 16: Line 24:
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  D. Braess,  "Über ein Paradoxon aus der Verkehrsplannung"  ''Unternehmensforschung'' , '''12'''  (1968)  pp. 258–268</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Braess,  ''http://homepage.ruhr-uni-bochum.de/Dietrich.Braess''  (2000)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  S. Dafermos,  A. Nagurney,  "On some traffic theory equilibrium paradoxes"  ''Transportation Res. B'' , '''18'''  (1984)  pp. 101–110</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A. Downs,  "The law of peak-hour expressway congestion"  ''Traffic Quart.'' , '''16'''  (1962)  pp. 393–409</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  M.J. Smith,  "The existence, uniqueness, and stability of traffic equilibria"  ''Transportation Res. B'' , '''13'''  (1979)  pp. 295–304</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  J.M. Thomson,  "Great cities and their traffic" , Gollancz, London  (1977)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  C.A. Zukowski,  J.L. Wyatt,  "Sensitivity of nonlinear one-port resistor networks"  ''IEEE Trans. Circuits Syst.'' , '''CAS-31'''  (1984)  pp. 1048–1051</TD></TR></table>
+
<table><tr><td valign="top">[a1]</td> <td valign="top">  D. Braess,  "Über ein Paradoxon aus der Verkehrsplannung"  ''Unternehmensforschung'' , '''12'''  (1968)  pp. 258–268</td></tr><tr><td valign="top">[a2]</td> <td valign="top">  D. Braess,  ''http://homepage.ruhr-uni-bochum.de/Dietrich.Braess''  (2000)</td></tr><tr><td valign="top">[a3]</td> <td valign="top">  S. Dafermos,  A. Nagurney,  "On some traffic theory equilibrium paradoxes"  ''Transportation Res. B'' , '''18'''  (1984)  pp. 101–110</td></tr><tr><td valign="top">[a4]</td> <td valign="top">  A. Downs,  "The law of peak-hour expressway congestion"  ''Traffic Quart.'' , '''16'''  (1962)  pp. 393–409</td></tr><tr><td valign="top">[a5]</td> <td valign="top">  M.J. Smith,  "The existence, uniqueness, and stability of traffic equilibria"  ''Transportation Res. B'' , '''13'''  (1979)  pp. 295–304</td></tr><tr><td valign="top">[a6]</td> <td valign="top">  J.M. Thomson,  "Great cities and their traffic" , Gollancz, London  (1977)</td></tr><tr><td valign="top">[a7]</td> <td valign="top">  C.A. Zukowski,  J.L. Wyatt,  "Sensitivity of nonlinear one-port resistor networks"  ''IEEE Trans. Circuits Syst.'' , '''CAS-31'''  (1984)  pp. 1048–1051</td></tr></table>

Revision as of 16:55, 1 July 2020

The words "Braess's paradox" refer to a surprising decrease in performance for some network, which is a result of it being improved locally. The occurrence of this decrease has been studied in mathematical models of equilibrium flow in road/rail traffic, computer networks, telephone networks, water supply systems, electrical circuits, spring systems, and so on. This has been done under various assumptions on routing schemes, such as being state-dependent or fixed.

Below, the occurrence of Braess's paradox in a classical model of user equilibrium traffic flow is given.

Let $( N , B )$ be a finite directed graph, with node set $N$ and arc, branch or link set $B$ (cf. also Graph, oriented). A path in which all links are similarly directed is called a route, with the initial and final nodes forming an origin/destination pair (or O/D pair). One considers a set $W$ of O/D pairs, and for each $w \in W$, supposes a flow demand $d _ { w } > 0$ to be given. Let $R _ { w }$ be a set of routes joining $w$. For each $w \in W$, and $r \in R _ { w }$, one considers $F _ { r } \geq 0$ such that $\sum _ { r \in R _ { W } } F _ { r } = d _ { W }$, giving a route flow vector $F = ( F _ { r } ) _ { r \in R _ { W } , w \in W }$. This route flow induces a link flow $f = ( f _ { b } ) _ { b \in B }$, by $f _ { b } = \sum _ { r \ni b } F _ { r }$ for each $b$, where one identifies a route with the set of its links. For each link $a$, one supposes a link cost , where $g _ { ab }$ and are given. For $r \in R _ { w }$, $w \in W$, one defines a route cost by .

A route flow $H$ is a user equilibrium if it satisfies the condition that for all $r , s \in R _ { w }$, $w \in W$, if $C _ { r } < C _ { s }$ then $H _ { S } = 0$. In other words, there is, for each $w$, a common route cost $\gamma _ { w }$ for all routes $r \in R _ { w }$ with non-zero $H _ { r }$. A user equilibrium flow exists always [a5], and if the matrix $g = g _ { a b }$ is such that $g + g ^ { T }$ is positive-definite, then the equilibrium link flows, and hence the route costs $\gamma _ { w }$, are unique. In [a3], Braess's paradox is said to occur if adding a new route $r$ to some $R _ { w }$ results in $\gamma _ { w }$ being increased. See also [a3] for necessary and sufficient conditions for this to happen under the assumption that there is a strictly positive equilibrium flow in all routes.

There is no fixed definition of Braess's paradox in all systems, but there is a common theme. One assumes some measure of performance, $t$, such as $\gamma _ { w }$. On the network given by any one link $b$, $t$ depends on the flow $f$ and a parameter $k_b$. For example, $t = 1 / ( k _ { b } - f )$ if the link is given by an M/M/1 queue (cf. also Queue). Note that $t$ decreases if $k_b$ increases, for $f$ fixed. Suppose some flow demand is fixed and link flows are given by some requirement about equilibria, or by a given dynamical process not in equilibrium. One says that Braess's paradox occurs if, for the network as a whole, $t$ increases when some $k_b$ increases. Adding links may be thought of as changing a parameter $k_b$ from zero or infinity. A different language would be used to describe certain other types of networks, such as electrical circuits.

Under this description, the Downs–Thomson paradox [a4] is a particular type of Braess's paradox. If one distinguishes these paradoxes mathematically, it is by requiring the link costs $t$ in the Braess paradox to be increasing functions of the link flow $f$, while in the Downs–Thomson paradox there is a link with $t$ a decreasing function of $f$.

Independent discoveries of Braess's paradox can be attributed to D. Braess [a1], A. Downs [a4], J.M. Thomson [a6] and C.A. Zukowski and J.L. Wyatt [a7].

[a2] contains an ample list of references.

References

[a1] D. Braess, "Über ein Paradoxon aus der Verkehrsplannung" Unternehmensforschung , 12 (1968) pp. 258–268
[a2] D. Braess, http://homepage.ruhr-uni-bochum.de/Dietrich.Braess (2000)
[a3] S. Dafermos, A. Nagurney, "On some traffic theory equilibrium paradoxes" Transportation Res. B , 18 (1984) pp. 101–110
[a4] A. Downs, "The law of peak-hour expressway congestion" Traffic Quart. , 16 (1962) pp. 393–409
[a5] M.J. Smith, "The existence, uniqueness, and stability of traffic equilibria" Transportation Res. B , 13 (1979) pp. 295–304
[a6] J.M. Thomson, "Great cities and their traffic" , Gollancz, London (1977)
[a7] C.A. Zukowski, J.L. Wyatt, "Sensitivity of nonlinear one-port resistor networks" IEEE Trans. Circuits Syst. , CAS-31 (1984) pp. 1048–1051
How to Cite This Entry:
Braess paradox. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Braess_paradox&oldid=16356
This article was adapted from an original article by B.D. Calvert (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article