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…
In your final case, It looks like you’re assuming that the last leg (D-to-B) takes as much time as the number of people who will _ever_ use that road in a given trip, not the number of people who are on it at that moment. Essentially, you’re assuming that everyone starts down that leg at the same time. However, if all the users leave A at the same time, and one user goes A-D instead of A-C-D, then the defector will only reach D at T=12; the other 9 will reach D at T=10, meaning that D-B will have one less user between T=10 and T=12. In that case, it looks like the main group will take 19 7/9 seconds, and the defector will take 20 seconds (which means the “everyone through A-C-D-B” path isn’t a Nash equilibrium – an individual defector gains something from doing so).
Of course, graph theory doesn’t literally represent linear-speed travel down a path, and other applications may not behave that way. I just wondered if I’m missing something in this specific case.
Hi, that’s an angle I never even thought to consider! The analysis as written is based on all resource usage somehow happening simultaneously, rather than precisely tracking flow through the network with respect to time. I believe that is consistent with the setup used for the original formulation of Braess’ paradox. But your idea would be an interesting model to play with and see what carries through.
I’d say you’re right about the “resource usage happening simultaneously” assumption. The quick bit of Web research I did was consistent with that, and it jives with what I remember from graph theory. Of course, my assumption that “road speed scales exactly with users on the road at a given time” doesn’t quite match the real world either, but it’s an interesting alternative. 🙂
I did the analysis, and it actually gets interesting. If “M” represents the number in the main group (A-C-D-B), and “D” represents the defectors, then for M between 6 and 9 the formulas are:
T-sub-M = 32 – 110/M
T-sub-D = 11 + M
For M between 1 and 5, things actually get simpler. In that case, the main group is finished before the defectors even make it from A to D, so neither group is on the D-to-B road at the same time. That makes the formulas:
T-sub-M = 2M + 1
T-sub-D = 22 – M
With these formulas, it looks like we get a Nash equilibrium at M = 7. Interestingly enough, this brings us closer to the original example – the Nash equilibrium is at a point that isn’t socially optimal (which is M = 5).
I can show you my derivations for these formulas, as well as a chart with all the results, but I don’t even know how this will show up, so I’ll keep it simple for now 🙂 If you’d like to take a look we can find a way.
Aha, this is great. I’ll admit that your original comment came in at 1am local time, so I didn’t think too deeply about it then- so I’m glad you did. In my ponderings today I was trying to patch up the problem description to match the simultaneous usage sense, but without stipulating that. I *think* that can be achieved by considering, say, a steady flow of ten travellers per unit time arriving at A, then asking what proportion should be assigned to which route (be it via selfish routing or socially-optimal dictatorship). Then after a certain amount of ‘burn in’ to saturate links I’d expect the flow through intermediate nodes to correspond to the original interpretation – it’s just that you’d be held up by travellers who didn’t set out at the same time as you.
However, that still requires care on exactly what it means for the cost of an edge to be ‘x’ – should that be the number of passengers assigned to that route at the same time as you (which I hope gives the desired interpretation) or (more realistically, and in keeping with your approach) depend on traffic still working along it from earlier assignments?
Reverting to your original problem of just moving N travellers through the network, but tracking precise progress, it’s also interesting to think about edge costs that have both a fixed component, plus a congestion contribution: say, 3+x. Then it’s not just a case of how many are assigned to each route, but the order in which you do it- alternating between routes causes different congestion to sending the first N/2 one way, and the rest the other. I also wonder if it can be the case that it’s socially optimal to deliberate hold someone back at a node until congestion reduces!