One of the things I like about recreational maths is how we can start with a simple game, play around a bit, poke in the corners, and suddenly fall down a deep hole into some serious mathematics. In this article we start with some well-trodden ground, which some readers will find familiar. However, we quickly find that all is not as it seems, and we soon stumble over a veritable pot of gold. To see how, read on…
Does this person have ginger hair? Is this person a boy? Is she wearing a hat? Is your person Anita?
Maybe everyone has played Guess Who?: the board game where you try to guess which character your opponent has before they find out yours. For those who have never played Guess Who?, the game goes as follows: each player picks a card at random, on which will be drawn the face of a character. In turns, the two players ask each other yes/no questions to try and guess who their opponent has picked. A board with all the images of the characters initially standing up helps the player keep track of which ones have been eliminated along the way. Continue reading
Traffic presents a nightmare for city planners. As well as being a pain for commuters, the environmental, financial and social cost of traffic is huge. Cities are still plagued with traffic jams, with rush ‘hour’ being a far too kind a name for the three hour period during which many of the roads are gridlocked. A possible solution to seemingly never ending traffic jams is to add additional infrastructure, but is this always the best solution? Consider the following (made up) scenario.
The school runEvery weekday, 8am sharp, 40 people drive their children from Aelston (A) to Deephurst (D). As things stand, there are two possible routes, going north via Byfair (B) or south via Churchgate (C). The roads connecting AB and CD have lots of lights and a slow speed limit, fixing the flux of traffic, with both roads taking 27 minutes to traverse. The roads connecting BD and AC have no traffic lights but are more prone to jams, taking 5 minutes to travel, plus half a minute for every other car using the road.
The local council, keen to win votes for the upcoming election, have tarmacked the local green space and built a new multilane motorway connecting BC. This 4-lane monstrosity is very fast and only takes 2 minutes to traverse. To the council’s dismay, the travel time for the school run has increased for everyone! Disgruntled and embarrassed, the council have brought in a mathematician to explain what has happened.
When considering how to present the information above, one might quite naturally draw a network (often called a graph). We represent the areas A to D as ‘nodes’ and the roads as ‘edges’. We assign ‘weights’ to each road, the value being the number of minutes it takes to go from one end of the road to the other. Allowing the edges to have directions, we obtain the following graphs for the pre and post-motorway systems:
Traffic assignment before building the road
Traffic assignment after building the road
where T represents the number of cars on the road.
Now for both systems, we shall seek the user-optimised configuration. This models the selfish nature of individuals using the network. Every driver will, if possible, change their route to the quickest path,
without concern whether the change will slow down everyone else’s journey. This is in contrast with the system-optimised configuration: the routes are assigned by someone who determines the optimal way to minimise the amount of time cars are collectively on the road.
Before the motorway was constructed, it is clear that the user-optimised configuration is to have 20 cars take ABD and 20 take ACD. In this case:
\begin{equation}
\lvert ABD \rvert = \lvert ACD \rvert = 5 + \frac{20}{2} + 27 = 42 ,
\end{equation}
where $\lvert – \rvert$ represents the time taken to complete the route $-$.
After the motorway was constructed, people taking the southern route noticed that avoiding CD would at worst take the same amount of time as going via CBD. This is because T satisfies $T\leq 40$, and hence
\begin{equation*}
\lvert CBD \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert CD \rvert .\\
\end{equation*}
The drivers initially taking the northern route also noticed that the slow road AB could be avoided in a similar manner:
\begin{equation*}
\lvert ACB \rvert = 2 + 5 + \frac{T}{2} \leq 27 = \lvert AB \rvert .\\
\end{equation*}
Hence, no matter what the other 39 cars are doing, it is always beneficial for the selfish driver to take the route ACBD. But, since all the drivers think the same thing, these roads are more congested than before, and the new travel time is
\begin{equation*}
\lvert ACBD \rvert = 5+\frac{40}{2} +2+5+\frac{40}{2} = 52,
\end{equation*}
10 minutes slower than before! However, no driver is willing to change, since any other route in this network with such a configuration is slower! Only if all the drivers cooperate, and agree to resist the temptation of avoiding the slow roads, can the previous system-optimised configuration be achieved. Hence, we see that in user-optimised networks, improved connectivity between two points does not imply a more efficient system. This phenomenon in networks was first demonstrated by Dietrich Braess in 1968, and is aptly named “Braess’ paradox”.
In our model, before the new motorway, there were two balanced options. The addition of the motorway then created a new preferable route, with the negative result that all traffic chose to take it, causing congestion. Although this model may seem far from realistically modelling roads, it demonstrates that networks can have this characteristic. Braess’ paradox is seriously discussed in traffic flow literature, and real life examples of this phenomenon are documented. In New York, there were reports of improved traffic when 42nd Street was shut for Earth Day in 1990. In Seoul, South Korea, the government went as far as demolishing a highway near the centre of the city to avoid the road being overused.
Picture of Seoul before and after the destruction of the freeway.
This result is a nice example of how our intuition can be tricked.
In a previous blog post I argued that my favourite number is the average number of friends that a person might have, known as Dunbar’s Number. You might immediately think “That is highly subjective, not even the definition of a friend or social relation is clear” or “It changes from one person to another”. This is obviously true, but the same questions have been posed by anthropologists, psychologists and sociologists, and they have come to a certain agreement about that subject.
Continue reading
Have you ever browsed one of your friend’s playlists and discovered that you both share almost the same music? Maybe you have some additional songs and perhaps he has a band that you have never heard of before, but basically you have the same music. Is there a way to get a proper measure of how similar your music is? If you could compare your music with every person you know, is there a way of ranking playlists according to which is most similar to yours? It is possible that the playlist that is closest to yours contains songs that you have never heard before but that you will really enjoy.
