Procedia Computer Science 83 ( 2016 ) 946 – 951
1877-0509 © 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
(http://creativecommons.org/licenses/by-nc-nd/4.0/).
Peer-review under responsibility of the Conference Program Chairs
doi: 10.1016/j.procs.2016.04.190
ScienceDirect
Available online at www.sciencedirect.com
5th International Workshop on Agent-based Mobility, Traffic and Transportation Models,
Methodologies and Applications, ABMTRANS 2016
Braess’s paradox in an agent-based transport model
Theresa Thuniga,∗, Kai Nagela
aTechnische Universit¨at Berlin, Transport Systems Planning and Transport Telematics, Salzufer 17-19, 10587 Berlin, Germany
Abstract
Braess’s paradox states that adding a link to the network can increase total travel time in a user equilibrium. In this paper, Braess’s
paradox is analyzed in the agent-based transport simulation MATSim. It can be observed, that two different types of the paradox
occur: In the absence of spill back effects, the delay per agent caused by adding a new link is bounded, i.e. the delay per agent
will not increase by extending the time span during which agents depart and, therefore, increasing the number of agents. In the
presence of spill back effects, the delay per agent is unbounded. The same holds for the price of anarchy in both cases which gets
unbounded if spill back effects are considered. As a consequence, Braess’s paradox tends to be underestimated in models that do
not capture spill back effects.
c
2015 The Authors. Published by Elsevier B.V.
Peer-review under responsibility of the Conference Program Chairs.
Keywords: Braess’s paradox, agent-based simulation, spill back effects, price of anarchy
1. Introduction
Braess’s paradox states that adding a link to the network or reducing the travel time on a link can increase total
travel time in a user equilibrium. Examples in New York or Stuttgart verified that it is not only a theoretical concept7.
Transport models that are used to give guidelines to improve traffic should, therefore, be able to reproduce the paradox.
In this paper, an approach to model Braess’s paradox with the transport simulation MATSim5,3is presented. In contrast
to static flow models that have usually been used to analyze Braess’s paradox, MATSim is an agent-based transport
model with time dependent travel times and a microscopic representation of travelers. To clarify model differences,
the original static version of Braess’s paradox is presented in the following section.
1.1. Braess’s original paradox
Braess’s paradox1was originally studied in a static flow model, i.e. a model where travel times do not vary over
time. Static flow models consider a directed graph where link travel times are given by travel time functions that
∗Corresponding author. Tel.: +49-30-314-78783 ; fax: +49-30-314-26269.
© 2016 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license
(http://creativecommons.org/licenses/by-nc-nd/4.0/).
Peer-review under responsibility of the Conference Program Chairs
947
Theresa Thunig and Kai Nagel / Procedia Computer Science 83 ( 2016 ) 946 – 951
depend on link flow values. In Braess’s setting, there is a fixed amount of traffic that wants to travel from a source to a
sink node. It is assumed that travelers are infinitesimally small so that they can arbitrarily split up to different routes.
Every traveler routes selfishly intending to minimize his travel time. This results in a so-called user equilibrium,
where no user has the incentive to unilaterally change his route. It is well known that a user equilibrium does not
necessarily minimize the total travel time, which is the sum of all individual travel times. The relation between total
travel time in user equilibrium and system optimum can be interpreted as the inefficiency of selfish routing and is
called price of anarchy (PoA)6. Formally, it is defined as PoA =C(UE)/C(SO),with C(·) giving the total travel time.
It may become arbitrarily large even in very simple networks.6Braess’s paradox is based on the difference of user
equilibrium and system optimum: Consider the network in Fig. 1.There are three routes from source sto sink t: the
upper one s→v→t, the middle one s→v→w→tand the lower one s→w→t. Demand consists of one
flow unit. Travel time functions are given next to each link. In the user equilibrium, all users use the middle route
with a total travel time of two time units. This can be seen as follows: With these loads, travel times are 1 +1=2,
1+0+1=2, and 1 +1=2 on the upper, middle, and lower route, respectively. A deviation of flow units from
the middle to the upper or lower route does not lead to a shorter travel time for the shifted flow but decreases travel
time for the middle route, such that shifted flow units switch back to the middle route. By removing the middle link
(v,w) from the network, the users split up uniformly to the remaining outer routes in the user equilibrium. Thereby,
ashorter total travel time of 3
/2time units is obtained, which is the system optimum. Thus, one can, paradoxically,
reduce the total travel time in a user equilibrium by increasing link travel times. Analogously, “improving” the traffic
network (e.g. by decreasing a link travel time or adding a link) can increase the total travel time in user equilibria.
1.2. Braess’s paradox in a time dependent setting
Static flow theory has been the basic framework for many years. However, considering more realistic dynamic
flow models, where flow values on links and link travel times may vary over time, a lot of results that hold for static
flows cannot be transfered. In dynamic flow models, link travel times are given by constant free flow travel times
plus waiting times that users spend in the queue at the end of the links in case link flow capacities are exceeded.
Thereby, one can distinguish between models with point queues in which vehicles have no physical length, and
models with spatial queues in which queuing vehicles may fill the link such that spill back effects occur. It is well
known that Braess’s paradox is extendable to time-dependent models. For example, Scarsini et al.9give a dynamic
formulation of Braess’s paradox in a point queue model. They observe that total travel time in the user equilibrium
may improve by removing a link, although the removed link has not been used in the equilibrium in steady state.
Crociani and L¨
ammel2study Braess’s paradox in a time-dependent model with spatial queues. They observe that
agents experience the congestion delay upstream of the branching point, where there are no possibilities to change the
route. In consequence, the travel time of the middle route remains the lowest even in the congested case. Crociani and
L¨
ammel use a cellular automaton based approach, which is a detailed and complex model. In the present paper it is
investigated if these observations can be reproduced with a much simpler queue model, and in how far the observations
hinge on details of the model such as the existence or not of spatial link representations.
In this paper, both mentioned dynamic versions of Braess’s paradox, the one discussed by Scarsini et al. and the
one discussed by Crociani and L¨
ammel, are modeled in MATSim. In the scenario that corresponds to the first version
(presented in section 2.1), no spill back effects do occur and the price of anarchy is bounded. It does not increase by
extending the time span during which agents depart because the delay that occurs only comes from a fixed number of
agents in the beginning of the simulation. In the scenario that corresponds to the second version (presented in section
2.2)spill back effects occur and the price of anarchy is unbounded. As a consequence, Braess’s paradox tends to be
underestimated in models that do not capture spill back effects. Additionally, this paper presents two methods to avoid
the occurrence of Braess’s paradox in the modeled scenario in section 3.This exemplifies that it is possible to evaluate
transport policies in MATSim that are intended to reduce the effect of Braess’s paradox.
2. Modeling Braess’s paradox as an agent-based scenario
To analyze Braess’s paradox in a dynamic traffic model with spatial queues, the agent-based traffic simulation
MATSim5is used. In MATSim, all agents start their trips from links where their activities are located. To bring this
948 Theresa Thunig and Kai Nagel / Procedia Computer Science 83 ( 2016 ) 946 – 951
st
w
v
x
1
1
x
0
d=1
l(x)
Fig. 1: Braess’s static paradox.
01 2 5
4
3
6
1s 1s
1 min
10 min
10 min
1 min
1 min 1s
Fig. 2: Braess’s paradox in MATSim.
together with Braess’s static paradox, where trips start on nodes, some additional links at the start and the end of all
routes were added (see Fig. 2). Since MATSim inserts (and removes) agents close to the downstream end of each link,
the links were added such that possible congestion at the agent insertion point would be visible.
All agents want to travel from link 0 1 to link 5 6 through the network. One agent is departing every second for one
hour, such that there are 3600 agents in total. As in the static case, there are three different routes: the upper, middle
and lower route. Additional network adaptions compared to the static Braess’s paradox were necessary because of
constant free flow travel times in MATSim. The used free-flow travel times of the links are given by the red values in
Fig. 2.Congestion is modeled in MATSim by choosing appropriate storage and flow capacities for the links, where the
flow capacity determines the number of agents that may exit the link per hour. The network used in this example has
a flow capacity of 3600 veh/h on the links that all agents have to use (i.e. links 0 1, 1 2 and 5 6) and a flow capacity
of 1800 veh/h on the other links. Agents exceeding this flow capacity have to wait before passing the link and build
spatial queues. By this, the link length works as a storage capacity and sets the upper bound for the number of agents
that fit onto the link. When this bound is reached, no more agents can enter the link. In other words, an agent may
exit its current link and enter the next link on its route if and only if it spent at least the free flow travel time on the
current link and the flow capacity of the current link and the storage capacity of the next link are not exceeded. The
travel time then is the sum of free flow travel times and waiting times.
2.1. Braess’s paradox with bounded price of anarchy
Because of the existence of spatial queues in MATSim, the price of anarchy may become unbounded. To illustrate
this condition, the first scenario is configured such that MATSim’s spatial queues never take effect. This is done by
using very long links (i.e. with a high storage capacity value), so that the number of agents that would cause spill back
is never reached. Queuing agents then increase link travel time arbitrary instead of spilling back. As a consequence,
previously slower routes become attractive and agents start to use them. Fig. 3a depicts the number of departures
and the average travel time on the routes over the time in seconds. The lower plot shows the average travel time for
an agent that departures at the specific time. The number of departures on the routes in the upper plot sums all past
departures of agents that use the specific route; if a line increases, currently starting agents use this route. For the
first ∼8 min. (until second 500) of this simulation run all agents use the middle route. The travel time of the route
increases, as the agents accumulate at link 2 3 without spilling back. Around second 500 the travel time on link 2 3
reaches 9 min. such that the lower route becomes attractive and agents start to use it. The visualization snapshot at
second 600 in Fig. 3b also illustrates this; agents are colored depending on their delay from green to red. For the next
∼8 min. (until second 1000) both routes are used alternately such that the agents accumulate at link 4 5. Travel time
at this link and therefore on both routes increases. Around second 1000, the upper route becomes attractive as the
snapshot of second 1800 in Fig. 3c shows. From now on, hardly any agent uses the middle route. Delay would only
increase on link 2 3or45, respectively. The agents uniformly distribute to the outer routes and experience free speed
travel time plus waiting time resulting from the initial “inefficient” usage of the middle route. Hence, the travel time
of all routes is balanced with ∼1200 s. (i.e. 20 min.) in steady state.
In this scenario, all delay results from the “inefficient” usage of the middle route in the initial phase. Once in
steady state, no more delay is accumulated. In other words, when extending the time span during which agents depart,
and therefore increasing the number of simulated agents, the travel time per agent in the user equilibrium would not
increase any further. The price of anarchy as the ratio of total travel time in user equilibrium and system optimum, is
therefore bounded.
949
Theresa Thunig and Kai Nagel / Procedia Computer Science 83 ( 2016 ) 946 – 951
(a) Number of agents and travel times on the routes over time. Initially, the
middle route is used, then increasingly the others, until at time ∼1000 flow
is distributed half/half between the outer routes.
(b) Visualization snapshot of second 600. The first agents start
to use the lower route.
(c) Visualization snapshots of second 1800. The first agents start
to use the upper route.
Fig. 3: Results for a run without spill back.
2.2. Braess’s paradox with unbounded price of anarchy
There is another dynamic version of Braess’s paradox that can be observed here: The case where agents still
accumulate delay in steady state. Hence, delay becomes unbounded: For every fixed delay one could construct a
scenario with a higher delay per agent; simply extend the time span during which agents depart because the delay
increases for every additional agent. In MATSim, an unbounded delay is reached by shorten links 2 3 and 4 5
(i.e. decreasing its storage capacity). Spatial queues then cause a spill back effect that expands the congestion ahead
of branching node 2. As shown in Fig. 4, all agents use the middle route. Delay increases unboundedly over time.
The agents do not switch to the outer routes because the number of agents that queue on link 2 3 is not high enough
to increase the travel time to 9 min. or more. Congestion spills back to the first links of the route as the visualization
snapshot of second 600 in Fig. 4b illustrates. Agents experience the congestion delay where there are no possibilities
to change the route. When an individual agent reaches node 2, the middle route is always the shortest.
A uniform distribution of the agents on the outer routes leads to shorter travel times. Still, this does not constitute a
user equilibrium since every single agent can reduce his travel time by switching to the middle route. Tab. 1compares
total travel times and route distributions of the different scenarios. It also contains the results of a perfect uniform
distribution of agents on the outer routes, i.e. the system optimum. In this setting (with one agent per second for one
hour) the total travel time in the user equilibrium of the scenario with bounded delay (3.7×106s.) is 1.6 times than the
system optimal total travel time (2.3×106s). The price of anarchy therefore is 1.6. In the scenario with unbounded
delay, the price of anarchy is 3.0 because total travel time (7.1×106s.) is 3.0 times than in the system optimum.
950 Theresa Thunig and Kai Nagel / Procedia Computer Science 83 ( 2016 ) 946 – 951
(a) Number of agents and travel times on the routes over time.
Flow only uses the middle route.
(b) Visualization snapshot of second 600. All agents use the
middle route and queue up to the first link.
Fig. 4: Results for a run with spill back.
scenario figure total tt #up #mid #low
no spill back 33795793 1269 816 1515
spill back 47133291 0 3600 0
SO - 2386634 1800 0 1800
without 3 4 5a 2462885 1828 0 1772
signal at 4 5b 2514324 1801 34 1765
Table 1: Comparison of total travel time (in seconds) and number of agents on the routes.
3. Avoiding Braess’s paradox in the agent based scenario
Motivated by the possibly unbounded price of anarchy in the dynamic version of Braess’s paradox discussed in
section 2.2, this section presents methods to reduce the price of anarchy in the given scenario by introducing some
transport policy. A well-known way to decrease the total travel time in the user equilibrium in Braess’s original
paradox is to delete the middle link 3 4. Fig. 5a shows the corresponding results in this setting. Without link 3 4, the
middle route is no longer available. The agents distribute themselves to the two remaining routes. As a consequence
of the strategy profile used in MATSim, this distribution cannot be perfect. A delay, which had at some point in time
been caused by a non-perfect distribution, can never be reduced. This is due to network capacities being defined as
equal to the demand on the corresponding route. Hence, by extending the time span during which agents depart,
they would accumulate increasingly. One can observe this accumulation in the lower part of Fig. 5a where travel
times increase with increasing departure times. The figure also shows that route travel times are not balanced at every
departure time, as it is the case in a user equilibrium. In comparison to the previous figures, the scaling of average
travel times has changed. Travel time differences in this scenario are at most 50 s. In previous figures, one would even
not be able to see such small differences. Nevertheless, the total travel time of this scenario without the middle link
nearly reaches the system optimal total travel time (see lower part of Tab. 1). In comparison to the previous scenario,
the total travel time reduces to a third (from 7.1×106s. to 2.4×106s.). The price of anarchy reduces to 1.0.
An alternative idea to avoid the occurrence of Braess’s paradox is to add signals that control traffic flow and reduce
capacity of the middle route. Clearly, installing a traffic signal on the middle link and setting it permanently to red
has the same effect as closing the link. However, with a signal that is only red most of the time, this is not as obvious:
For example, installing such a signal for the right turn at node 3 would cause a huge jam since cars going straight
would be caught behind queuing cars. This issue could be resolved by separate turning lanes. To show that this is
also feasible without separate turning lanes, we place a signal at node 4. At this node, there are two conflicting traffic
streams that enter link 4 5. Fig. 5b presents the results of this scenario with a signal at node 4 that only allows one
951
Theresa Thunig and Kai Nagel / Procedia Computer Science 83 ( 2016 ) 946 – 951
(a) Results for a run without the middle link.
(b) Results for a run with a signal at node 4.
Fig. 5: Number of agents and travel times on the routes over time. Flow distributes almost uniformly to the outer routes.
direction to pass the intersection at every time. To avoid the use of the middle route, the signal sets link 3 4 to ”green”
for only one second, while it sets link 2 4 to ”green” for the rest (59 s.) of the cycle time. The agents distribute almost
uniformly to the outer routes. Only a few agents use the middle route as depicted by the green dots in the lower part
of Fig. 5b. Total travel time in the user equilibrium reduces to 2.5×106, as shown in Tab. 1, which implies again a
reduction of the price of anarchy to 1.1. A green split optimization algorithm that minimizes total travel time4might
thus be able to detect such a solution.
4. Conclusion
In this paper, scenarios for the agent-based transport simulation MATSim that display the occurrence of Braess’s
paradox were presented. Two different scenarios were examined where the price of anarchy and the delay per agent
is bounded or unbounded, respectively, depending on the presence of spill back effects. This categorizes two types of
Braess’s paradox in the dynamic case and leads to the implication that Braess’s paradox tends to be underestimated in
models that do not capture spill back effects. Additionally, it was analyzed how to avoid the occurrence of Braess’s
paradox. A future challenge is to algorithmically determine a traffic policy that pushes agents to system-improving
routes. So far, the presented policies were only manually determined. This is not trivial, because the question whether
ascenario contains Braess’s paradox is NP-hard8, i.e. has a high complexity in theory. Therefore, finding a mechanism
that detects Braess links, i.e. links that should be removed, is even harder. Finally, the case study has shown that
MATSim is able to evaluate traffic policies that avoid the occurrence of Braess’s paradox.
References
1. Braess,D. ¨
Uber ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12 (1968), 258–268.
2. Crociani,L., and L¨
ammel, G. Multi-destination pedestrian flows in equilibrium: a cellular automaton based approach. Computer-Aided Civil
and Infrastructure Engineering (forthcoming).
3. Horni, A., Nagel, K., and Axhausen, K. W., Eds. The Multi-Agent Transport Simulation MATSim. Ubiquity Press, in preparation. See
http://matsim.org/the-book.
4. K¨
ohler, E., and Strehler,M.Traffic signal optimization using cyclically expanded networks. Networks (2015).
5. MATSim webpage. MultiAgent Transport Simulation, accessed 2016. See http://matsim.org/.
6. Pigou,A.The Economics of Welfare.MacMillan, New York, 1920.
7. Rapoport, A., Kugler, T., Dugar, S., and Gisches, E. J. Choice of routes in congested traffic networks: Experimental tests of the braess
paradox. Games and Economic Behavior 65, 2 (3 2009), 538–571.
8. Roughgarden, T. On the severity of braess’s paradox: Designing networks for selfish users is hard. Journal of Computer and System Sciences
72, 5 (2006), 922–953. Special Issue on FOCS 2001.
9. Scarsini, M., Schr ¨
oder, M., and Tomala, T. Dynamic atomic congestion games with seasonal flows. HEC Paris Research Paper,ECO/SCD-
2013-1016 (2015).
