(updated  31st August 2007)

Keywords: simulating people, simulating crowds, simulating crowd dynamics

Braess’s paradox is an important consideration for the analysis of any network system that has alternative routes. To summarise Braess’s paradox: you sometimes increase congestion by increasing a choice of routes. This is a similar finding to the interaction-based paradox, where an increase in the number of interactions can reduce the overall system flow performance. Typically you find examples of the paradox in city traffic design and network analysis.

Mark Wainwright has turned a description of Braess’s paradox into an excellent html. The following description is very heavily paraphrased from his website.

To illustrate this paradox will consider a network of roads between two sites (A and D in Figure 1). These types of networks are typically described in economic terms, associating a cost for travelling on a particular edge of the network. Each edge in this example is labelled with some function of the number of cars on that edge: the more cars the longer the journey time, the more frequent the number of accidents, the longer delays become, hence the greater the fuel consumption will be. The function of cost will in general be complex but for the purposes of illustration we shall assume a simple linear function for each road (Figure 1).

We have to examine the paradox in more detail. First let us consider the assumptions we have made in this model.

• Cars enter the system in a single file. We have allowed each driver to enter in turn and make a decision based on their perceived congestion in the network.

• The Greedy algorithm is implicit. We have allowed each driver to take the route with the lowest cost/least density.

These assumptions may be incorrect, so let us first examine the network in more detail. In our original network, the solution we found (three drivers going each way) is stable. This means that once the cars are arranged this way there is no advantage in changing routes. Any route changes will cost more (travelling back down the network).

It is also the only stable solution. If we arrange the cars in a different way, say four to the left and two to the right, then one driver will soon notice that he can lower his own journey cost by taking a different route. So, if we start with any arrangement of cars on roads, but let the cars change to a different route if it is cheaper, they will soon arrive at the stable solution. This is also the one we find by the greedy algorithm.

What is particularly interesting is that these properties apply to the modified network. The solution given by the greedy algorithm, with four cars taking A-B-C-D, and one each A-B-D and A-C-D, is stable, and it is the only stable solution. If the six cars start off by using their old route to work - three each to the left and the right - one driver will soon notice that he can improve his time by cutting across between B and C, and gradually others will also change until the cars are arranged in the new formation where everyone's journey is more expensive.

We have a solution where every car is careful to take the cheapest available route, and yet the total cost has increased. How is it that by adding an extra road to a network increases the overall costs?

The key is how the cost of using a road varies with the number of cars. Using our linear functions, we can imagine the constant term as representing the road's length, and the term in x an indication of how prone the road is to congestion. Note that this idea supposes that the `cost' of a journey is purely a matter of how long it takes. Then the new road allowed a shortcut between the two North Westerly roads, which are shorter than the alternatives, but suffer from substantially worse congestion.

The result is that each driver in turn takes this slightly quicker route, at a small saving for himself, but causing substantial extra delay to a number of other drivers. By the time everyone has decided whether to take the short cut, the total congestion gained by the system far outweighs the savings in distance.

The modified network is really a classic example of the Prisoner's Dilemma (PD), a paradox with many applications. Adding the extra road gave the commuters the opportunity to `defect', in PD terms. In this particular case it did not even have any compensating benefits.

When we consider the paradox with respect to egress systems, we have many examples of Braess’s paradox in building design. Specifically, the assumption that adding addition exit routes it will increase the overall egress capacity. This also applies to the addition of ingress routes to a stadium. Simply adding more may not solve the problem of how to increase the ingress capacity.

We can see that even a simple calculation based on a network can have unexpected results. This is relevant to the network example in the Green Guide for two main reasons. Network analysis is oversimplified, and the impact of the local geometry on crowd behaviour has not been sufficiently highlighted.

The time taken to exit a system in an emergency is a critical factor for crowd safety. For safety analysis, every factor has to be considered. This includes the paradox posed by Braess. The oversimplification of network analysis in the Green Guide can have hidden and potentially catastrophic consequences. When a network system offers alternatives for egress, the impact of losing some of these in an emergency has to be part of the safety calculations. The Green Guide alludes to this but does not consider the impact that Braess’s paradox can have on an emergency egress system design.

The impact of local geometry also includes the visibility of signage in crowded situations, the dynamics of crowd flows (as they merge together) and the relationship between speed and density in confined spaces.

As previously stated the Green Guide has been revised considerably in light of recent disasters; however, with respect to this particular issue there are problems that need to be addressed. When a system is complex, it should not be reduced to the simplistic analysis presented in the Green Guide.

By using an agent based software system coupled with local/global feedback, it is possible to analyse, predict, navigate and reroute the entire network on a dynamic basis. David Kelly has written some papers on the problems with Braess's paradox with respect to network routing in general. The issue of how to solve, in real-time, the dynamic routing problem is at the cutting edge of technology. Two outstanding problems have prevented the solution to date.

• The fundamental model is not correct. Applying a greedy algorithm is assuming the fluidic nature of the system. Systems which has route decisions do not behave like a fluid. Therefore the solution to the problem has to start with different, more appropriate assumptions.

• Coupling both local and global information (such as the global information is to maximise the flow through the network but the local information has no global view) has to function to the benefit of the whole system. Individuals will choose routes through a system which has their own optimal - but have no consideration, or view, of the whole system. Therefore unless the local and global objectives are the same the system will either develop a chaotic character - or settle into a sub-optimal flow.

Solving both of these problem is now possible within the suite of tools developed under the Myriad framework. The understanding of these types of systems has been the primary research goal of the author for the last decade. His thesis Crowd Dynamics describes the process of using a simulation system to the problems of crowd safety.