Tuesday, 11 August 2009

Game Theory at Sussex Place junction

We are still seeking photos of the days when there was a mini-roundabout here, but until then we are blessed with this photograph of what the junction looked like pre-widening. Remember, at this time there was a bike lane and a pavement wide enough for a pedestrian to get past any parked cars. The improvements to the junction are to reduce pollution by helping traffic flow. Pedestrians and tax-dodging cyclists can use the back roads instead.

As to what is going on here, our Reporter "TJ", says
The picture was taken from Ashley Road and the sequence of events was as
  • Lights are green for traffic coming off Ashley Road
  • Lower Ashley Road was stationery and traffic from Ashley Road (white transit followed by green and black cars - hereafter Muppet Group A) moved forward onto the junction to avoid getting held all the way through another sequence.
  • Lights change to green for traffic coming off Sussex Place
  • Traffic moving from Sussex Place onto Lower Ashley Road (led by the yellow brakedown lorry) was unable to move forward much due to congestion on Lower Ashley Road and Muppet Group A.
  • Traffic moving from Sussex Place onto Ashley Road got fed up with sitting there and started to pull out from the queue and drive down the wrong side of Sussex Place to get past the blockage. Quite a lot of this traffic was overtaking 10+ cars queueing to turn left onto Lower Ashley Road (i.e. driving a long way down the wrong side of the road).
  • Lights change to green for traffic coming off Lower Ashley Road.
  • Several of the cars coming down the wrong side of Sussex Place were still trying to cross the junction, including the grey sports car and the silver Nissan Micra in the picture but with more infront and behind (hereafter Muppet Group B).
  • Traffic turning left from Lower Ashley Road into Ashley Road (led by lorry with white cab and blue body) is blocked by Muppet Group B.
  • Traffic turning right from Lower Ashley Road into Sussex Place (led by silver people carrier) is blocked by Muppet Group A but would be blocked by Muppet Group B even if Muppet Group A had moved in the two or three minutes since they pulled into the middle of the junction.
  • No-one can go anywhere until Muppet Groups A and B have managed to clear the junction.
I seem to remember that someone in Muppet Group B actually hooted at the traffic trying to go from Lower Ashley Road into Ashley Road under the green lights. They did manage to all clear the junction within a minute or two (the grey sports car on the right is just starting to move forward onto Ashley Road) but for a while it looked like being a really entertaining snarl up.

This is fascinating, as it is another classic example of real-world deadlock. In computing systems, a deadlock occurs when a number of entities are each blocked, waiting for the actions of the other entities. It can only occur if
  1. There is mutual exclusion: here, only one vehicle can fit into the middle of the junction at a time, or into any of the junction exits.
  2. A hold and wait condition exists: it is possible to claim one resource (the junction or an exit) before acquiring the other.
  3. Resources cannot be taken by force. There is no easy way to remove a vehicle from the junction or an exit.
  4. A circular wait exists: the chain of dependencies comes back to the original entity.
For more detail, there is a set of slides on the topic. While most people don't really care about such computing things, it is interesting to see it in the real world because of this:
  • The self-interested action of each driver is to pull out into the junction, to make some progress when you get a green light, because when the light changes, the car at the front of the other junction will do exactly that, regardless of whether it can get out. As a result, the system grinds to a halt; it enters a failed state.
This is pretty important, because the whole idea of choosing the best option for yourself regardless of the decision the others make is the whole foundation of Game Theory. And in Sussex Place, the Nash Equilibrium appears to result in the loss of traffic flow. (Yes, that is a university lecture, but its a political science one and doesn't have much maths in it)

So, why is that important? Because Game Theory was the underlying political science/mathematics of the cold war. And John Nash, the mathematician behind it. These are the equations you would use when planning a conflict escalation policy that starts off with tanks in Berlin or Vietnam, and ends with an exchange of strategic armaments in ballistic missiles over the Arctic Circle, and hence the end of humanity -the big Failed State.

The politicians, the soldiers, sat their with their maps, their tables, their graphs, got the mathematicians in and game up with plans that during the cold war came pretty close to that condition on a couple of occasions, but everyone always backed off. For which we all have to be very, very grateful.

Comparing the Cold War to Sussex Place then, we have to pretty glad that those people trying to drive across Bristol weren't involved in planning or managing the conflict, as we wouldn't have stood a chance of getting through it alive.

No comments: