Editing Braess's paradox (section)

== Mathematical approach ==

=== Example ===
[[Image:Braess paradox road example.svg|right|500px]]

Consider a road network as shown in the adjacent diagram on which 4000 drivers wish to travel from point Start to End. The travel time in minutes on the Start–A road is the number of travellers (T) divided by 100, and on Start–B is a constant 45 minutes (likewise with the roads across from them). If the dashed road does not exist (so the traffic network has 4 roads in total), the time needed to drive Start–A–End route with <math>a</math> drivers would be <math>\tfrac{a}{100} + 45</math>. The time needed to drive the Start–B–End route with <math>b</math> drivers would be <math>\tfrac{b}{100} + 45</math>. As there are 4000 drivers, the fact that <math>a + b = 4000</math> can be used to derive the fact that <math>a = b = 2000</math> when the system is at equilibrium. Therefore, each route takes <math>\tfrac{2000}{100} + 45 = 65</math> minutes. If either route took less time, it would not be a Nash equilibrium: a rational driver would switch from the longer route to the shorter route.

Now suppose the dashed line A–B is a road with an extremely short travel time of approximately 0 minutes. Suppose that the road is opened and one driver tries Start–A–B–End. To his surprise he finds that his time is <math>\tfrac{2000}{100} + \tfrac{2001}{100} = 40.01</math> minutes, a saving of almost 25 minutes. Soon, more of the 4000 drivers are trying this new route. The time taken rises from 40.01 and keeps climbing. When the number of drivers trying the new route reaches 2500, with 1500 still in the Start–B–End route, their time will be <math>\tfrac{2500}{100} + \tfrac{4000}{100} = 65</math> minutes, which is no improvement over the original route. Meanwhile, those 1500 drivers have been slowed to <math> 45 + \tfrac{4000}{100} = 85</math> minutes, a 20-minute increase. They are obliged to switch to the new route via A too, so it now takes <math>\tfrac{4000}{100} + \tfrac{4000}{100} = 80</math> minutes. Nobody has any incentive to travel A-End or Start-B because any driver trying them will take 85 minutes. Thus, the opening of the cross route triggers an irreversible change to it by everyone, costing everyone 80 minutes instead of the original 65. If every driver were to agree not to use the A–B path, or if that route were closed, every driver would benefit by a 15-minute reduction in travel time.

=== Existence of an equilibrium ===
If one assumes the travel time for each person driving on an edge to be equal, an equilibrium will always exist.

Let <math>L_e(x)</math> be the formula for the travel time of each person traveling along edge <math>e</math> when <math>x</math> people take that edge. Suppose there is a traffic graph with <math>x_e</math> people driving along edge <math>e</math>. Let the energy of <math>e</math>, <math>E(e)</math>, be

: <math>\sum_{i=1}^{x_e} L_e(i) = L_e(1) + L_e(2) + \cdots + L_e(x_e)</math>

(If <math>x_e = 0</math> let <math>E(e) = 0</math>). Let the total energy of the traffic graph be the sum of the energies of every edge in the graph.

Take a choice of routes that minimizes the total energy. Such a choice must exist because there are finitely many choices of routes. That will be an equilibrium.

Assume, for contradiction, this is not the case. Then, there is at least one driver who can switch the route and improve the travel time. Suppose the original route is <math>e_0, e_1, \ldots, e_n</math> while the new route is <math>e'_0, e'_1, \ldots, e'_m</math>. Let <math>E</math> be total energy of the traffic graph, and consider what happens when the route <math>e_0, e_1, ... e_n</math> is removed. The energy of each edge <math>e_i</math> will be reduced by <math>L_{e_i}(x_{e_i})</math> and so the <math>E</math> will be reduced by <math display="inline">\sum_{i=0}^n L_{e_i}(x_{e_i})</math>. That is simply the total travel time needed to take the original route. If the new route is then added, <math>e'_0, e'_1, \ldots, e'_m</math>, the total energy <math>E</math> will be increased by the total travel time needed to take the new route. Because the new route is shorter than the original route, <math>E</math> must decrease relative to the original configuration, contradicting the assumption that the original set of routes minimized the total energy.

Therefore, the choice of routes minimizing total energy is an equilibrium.

=== Finding an equilibrium ===
The above proof outlines a procedure known as [[best response]] dynamics, which finds an equilibrium for a linear traffic graph and terminates in a finite number of steps. The algorithm is termed "best response" because at each step of the algorithm, if the graph is not at equilibrium then some driver has a best response to the strategies of all other drivers and switches to that response.

Pseudocode for Best Response Dynamics:
 Let ''P'' be some traffic pattern.
 '''while''' ''P'' is not at equilibrium:
     compute the potential energy ''e'' of ''P''
     '''for each''' driver ''d'' in ''P'':
         '''for each''' alternate path ''p'' available to ''d'':
             compute the potential energy ''n'' of the pattern when ''d'' takes path ''p''
             '''if''' ''n'' < ''e'':
                 modify ''P'' so that ''d'' takes path ''p''
 '''continue''' the topmost '''while'''

At each step, if some particular driver could do better by taking an alternate path (a "best response"), doing so strictly decreases the energy of the graph. If no driver has a best response, the graph is at equilibrium. Since the energy of the graph strictly decreases with each step, the best response dynamics algorithm must eventually halt.

=== How far from optimal is traffic at equilibrium? ===
If the travel time functions are linear, that is <math>L_e(x) = a_e x + b_e</math> for some <math>a_e, b_e \geq 0</math>, then at worst, traffic in the energy-minimizing equilibrium is twice as bad as socially optimal.<ref name="EasleyKleinberg"><!-- please do not point the URL to http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch08.pdf, as it does not contain the reference cited by Easley and Kleinberg -->
{{cite web|url=http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf|title=Networks, Crowds, and Markets: Reasoning about a Highly Connected World (8.3 Advanced Material: The Social Cost of Traffic at Equilibrium)|last2=Kleinberg|first2=Jon|publisher=Jon Kleinberg|last1=Easley|first1=David|website=Jon Kleinberg's Homepage|access-date=2015-05-30|archive-url=https://web.archive.org/web/20150316015111/http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book.pdf|archive-date=2015-03-16|url-status=live}} – This is the preprint of {{ISBN|9780521195331}}</ref>

Proof: Let <math>Z</math> be some traffic configuration, with associated energy <math>E(Z)</math> and total travel time <math>T(Z)</math>. For each edge, the energy is the sum of an [[arithmetic progression]], and using the formula for the sum of an arithmetic progression, one can show that <math>E(Z)\leq T(Z)\leq 2E(Z)</math>. If <math>Z_o</math> is the socially-optimal traffic flow and <math>Z_e</math> is the energy-minimizing traffic flow, the inequality implies that <math>T(Z_e) \leq 2E(Z_e) \leq 2E(Z_o) \leq 2T(Z_o)</math>.

Thus, the total travel time for the energy-minimizing equilibrium is at most twice as bad as for the optimal flow.

=== Effect of network topology ===
Mlichtaich<ref>{{Cite journal |last=Milchtaich |first=Igal |date=2006-11-01 |title=Network topology and the efficiency of equilibrium |url=https://www.sciencedirect.com/science/article/pii/S0899825605001284 |journal=Games and Economic Behavior |language=en |volume=57 |issue=2 |pages=321–346 |doi=10.1016/j.geb.2005.09.005 |issn=0899-8256|hdl=10419/259308 |hdl-access=free }}</ref> proved that Braess's paradox may occur if and only if the network is not a [[Series–parallel graph|series-parallel graph]].