Earlier today I spotted this video, featuring the stand-up mathematician Matt Parker and all-round interesting person Tom Scott exploring some oddities of the tube:
Matt’s ability to beat Tom around the network depended on local knowledge of hidden shortcuts. You might wonder why these quicker options aren’t indicated by signs, but as they explain in the video, for some the problem is that they’re only quicker because they’re secret. Were the full force of the travelling public to try and use them, the resulting congestion would lead to travel times even worse than the officially sanctioned route.
This is a real-world manifestation of the price of anarchy, an area of maths I find fascinating, as it collides game theory with networks. An obvious starting point is `Pigou’s Example’, which I’ll simplify here slightly.
Suppose there are two choices for a journey across a valley: a long but reliable bypass that loops around it, taking ten minutes to complete the journey; and a direct bridge that suffers badly from congestion, so that journey times grow with the number of users. To be precise, let’s imagine that if x people cross the bridge, they each take x minutes to do so. Now imagine that ten people want to travel across the valley. Which route should they take?
With a bit of thought, we can see that they should all try for the bridge: at worst it only takes ten minutes anyway, but for each person that opts for the bypass you’ll save a minute by sticking with the bridge. Put another way, if you’ve opted for the bridge, you gain nothing by switching to the bypass, regardless of the choices of the other travellers. In game theory terms, everyone using the bridge is a Nash equilibrium – a stable situation in the sense that no-one can improve their journey by changing strategy (from bridge to bypass).
However, it’s not a social optimum: with ten people on the bridge, they each have a journey time of ten minutes each; but if we could force five to take the bypass instead (requiring the same ten minutes) then those on the bridge now have a journey time of five minutes. This means that the population as a whole spends 75 minutes travelling, rather than a hundred. This is a genuine improvement for all concerned, with no-one being asked to take a longer journey than before, and some experiencing a shorter one. (One can devise scenarios where forcing a longer journey on a few makes things better on average, but that seems less fair.)
Unfortunately, allowing selfish travellers to self-organise, this arrangement is not stable: those on the bypass will look enviously at the speedsters on the bridge, and opt for it next time. The problem is choice, or rather that we can’t trust others not to make a choice that gives them an advantage. If our valley crossers could enter into a gentleman’s agreement that half of them would use the bridge on the opposite day to the rest, all would be well. But the non-cooperative approach to game theory takes the pessimistic view that people will agree to anything – particularly if that puts you on the bypass! – then proceed to selfishly use the bridge every day anyway. Under such assumptions, we then need an external authority – be it a government, the mafia code of honor, or Transport for London’s crafty signwriters – to force us to take action that’s for the greater good: even if it’s good for us too.
This sheds some light on a related problem that seems at first counter-intuitive, and has thus become known as Braess’ Paradox: adding more capacity can make everyone’s journey slower! This will occur if the network is already experiencing congestion, and once again is due to the perils of choice. If the new route becomes the obvious way to go, it can create an even greater bottleneck than before as everyone tries to save some time by using it.
As an example, consider our same ten travellers, now trying to get from A to B via two alternatives C and D as follows:
As before, we have a social optimum by sending half of the traffic via C, and the rest via D. In this way, everyone has a journey time of 17 minutes. But as both routes involve a road that is subject to congestion, this is also a Nash equilibrium: if C and D are equally used, then you make your journey worse by swapping to the other. However, a well-meaning city planner can ruin everything by adding a new, fast road between those two:
Now a Nash Equilibrium arises in which everyone takes the route A-C-D-B: for a total travel time of 21 minutes, four worse than before! We see that this is an equilibrium because if you switch to A-D-B your journey time becomes 22 minutes (because everyone is still on D-B); A-C-B also takes 22 minutes since then everyone uses A-C. Of course, with a benign dictator we can ignore the C-D road entirely and have 17-minute journeys for all. But that can’t arise from selfish decisions, as anyone on the A-C-B route will try to trade the 12 minutes of C-B for the 1+x of C-D-B, and similarly A-D-B travellers will spot that A-C-D is more appealing than A-D. So everyone defects to A-C-D-B in the hopes of a 12 minute journey- and they all end up worse off than before…
Such phenomena are not just mathematical curiosities, as they’ve been encountered in real travel networks too. A New York Times article, What if They Closed 42d Street and Nobody Noticed?, discusses Braess’ paradox in reverse- closing a road in a notoriously busy city sounds like a recipe for travel disaster, but by removing an option the flow of traffic actually improved. Similarly travel times in Seoul were reduced after a 6-lane highway was demolished in favour of a park: a double-win for the environment!
Still, as a fairly-frequent user of the Underground, I can’t help but fear I’ll be selfishly adopting some of Matt and Tom’s hacks- at least until everyone else catches on…