Editing Braess's paradox (section)

== Discovery and definition ==
Dietrich Braess, a mathematician at [[Ruhr University]], [[Germany]], noticed the flow in a road network could be impeded by adding a new road, when he was working on [[traffic modelling]]. His idea was that if each driver is making the [[optimization|optimal]] self-interested decision as to which route is quickest, a shortcut could be chosen too often for drivers to have the shortest travel times possible. More formally, the idea behind Braess's discovery is that the [[Nash equilibrium]] may not equate with the best overall flow through a network.<ref name="ReferenceA">New Scientist, [https://www.newscientist.com/article/mg22129520-600-42nd-st-paradox-cull-the-best-to-make-things-better/  42nd St Paradox: Cull the best to make things better], 16 January 2014 by Justin Mullins</ref>

The paradox is stated as follows:<blockquote>"For each point of a road network, let there be given the number of cars starting from it and the destination of the cars. Under these conditions, one wishes to estimate the distribution of traffic flow. Whether one street is preferable to another depends not only on the quality of the road, but also on the [[flow density|density of the flow]]. If every driver takes the path that looks most favourable to them, the resultant running times need not be minimal. Furthermore, it is indicated by an example that an extension of the road network may cause a redistribution of the traffic that results in longer individual running times."</blockquote>

Adding extra capacity to a [[network (mathematics)|network]] when the moving entities selfishly choose their route can in some cases reduce overall performance. That is because the [[Nash equilibrium]] of such a system is not necessarily optimal. The network change induces a new game structure which leads to a (multiplayer) [[prisoner's dilemma]]. In a Nash equilibrium, drivers have no incentive to change their routes. While the system is not in a Nash equilibrium, individual drivers are able to improve their respective travel times by changing the routes they take. In the case of Braess's paradox, drivers will continue to switch until they reach Nash equilibrium despite the reduction in overall performance.

If the latency functions are linear, adding an edge can never make total travel time at equilibrium worse by a factor of more than 4/3.<ref name="RoughgardenTardos">
{{cite web|url=http://theory.stanford.edu/~tim/papers/routing.pdf|title=How Bad is Selfish Routing?|last2=Tardos|first2=Éva|publisher=Journal of the ACM|last1=Roughgarden|first1=Tim|access-date=2016-07-18|archive-url=https://web.archive.org/web/20160409061229/http://theory.stanford.edu/~tim/papers/routing.pdf|archive-date=2016-04-09|url-status=live}}</ref>