We've discussed before planning strategies, such as the MiniMax algorithm, and how a limiting factor is how far ahead you plan. The planning horizon limits your options, and often the game is won by whoever plans furthest ahead.
We are perfectly happy with a planning horizon of one: what is the next thing in your way. However, we are pretty unimpressed by this video which was sent to us of a car in Clifton who'se planning horizon was zero. When a car is coming towards you, you either do two things -commit at speed or back off. What you don't do is go alongside the bicycle at 15 mph with a car coming towards you at 20 mph, as that leads to an exchange of details and some insurance premiums, especially now that tax-dodgers are starting to carry cameras and no doubt willing to supply their videos as evidence.
If you are going to overtake with oncoming traffic, put your foot down!
Game theory divides games into those in which all information is visible to all players (like chess), and those where each side holds secrets (like poker). There are different tactics in each. In a game when the position and intent of all players is visible the Nash Equilibrium -the steady state reached when every player can predict the optimal moves of their opponents and act accordingly- is easier to reach.
In junctions, it comes down to "do you block the junction or not". Here on Cheltenham Road the taxi says yes.
Then, just before the lights change, it moves forward and another car makes the same decision.
Here in this video from the St Michaels Hill roundabout, you can see another taxi making the same decision.
In highway-code theory, blocking junctions is selfish and can lead to total gridlock.
In Game Theory, as applied to Bristol City streets, blocking the junction is the correct thing to do. why?
You know that nobody is going to penalise anyone who blocks a junction.
If you block a junction, when the road ahead eventually moves, you will get through.
If the other players in the game -the other vehicles who get time at the lights, block the junction, you don't get a chance to drive yourself, hence will never make progress.
You are therefore forced to pull out and block the lane -if you know the other players will do the same thing.
The other players know the same thing, -that your best strategy to make progress is to pull out and block the lane.
Therefore they will pull out and block the lane themselves, as it is the only way they make progress.
Therefore your best strategy, given your knowledge of their best strategy, is to pull out.
This is the Nash Equilibrium: the steady state where no player in the game has any incentive to change their strategy. If any driver at the front of the lights doesn't pull out and block the junction, all they will do is annoy the cars behind.
This is why drivers in the city don't get annoyed by other cars doing this. They'd do the same thing. The only way to change this would be to change assumption (1), that there is no penalty for blocking a junction.
Game Theory: the maths you can play on the commute. Even if you don't realise it.
We are aware that we are the highest ranked site when you search blogspot for alloy wheels, and therefore that a comment with some banal chat and back links to your own site would help your page rank. However, as well as using nofollow links to remove them from google's PageRank scores, we have a policy that says if you spam us with attempted to links, we only make fun of you. Therefore, please accept this posting as a gift, but note that the nofollow tag above renders your link worthless and all that you will get is more spam to your email address. Sorry.
There is no point trying to push alloy wheel services to our readers, despite our broad readership in Bristol, because (a) you have a Southampton postcode and are therefore unimportant, and (b) we don't think alloy wheels have a place in the city.
Every driver who has alloy wheels values their wheels. Not only does this prevent them doing operations in the city, it holds up other traffic. Takes this video of the bottom of St Michael's Hill from last month.
The car in front of us is waiting to turn slide into the left turn lane -which has a green light onto Park Row. But it cannot do that as the car in front of it values their wheels too much to scrape against the kerb or to commit more aggressively and get both wheels entirely on the pavement, and they still have a driver-side wingmirror to lose. The selfish decision of the first car to have alloy wheels not only slows them down, it slows down the rest of the city's traffic. And this is on a Sunday! Imagine how much congestion one selfish alloy-wheel owning outsider would cause on a busy weekday morning!
Drivers who value their vehicle's bodywork and paintwork are as much an inconvenience to us locals as pedestrians on zebra crossings and cyclists pootling along. You may not realise this as you live in the provinces and dream of day trips to Portsmouth where you can see three cars in a row, but we city folk know the harsh truth: from a game-theory perspective, alloy wheels place you at a disadvantage. They are easily damaged and, as they are a visible status symbol, everyone else sees that you value your car, therefore are more likely to give way on high conflict roads, such as here, the Horfield Road/St Michael's Hill junction.
Please do not bother posting any more spam advertisement comments, as we will only continue to criticise you for your naive lack of understanding of modern driving techniques and issues, as well as your complete ignorance of game theory and its application in city driving.
We recently nipped over to Cotham Hill was to see if another rumour -parking restrictions removed- was true.
And yes, you can see, while they are resurfacing this road there are no limited waiting markings on the right-hand side of the photo, no double yellows on the other, even the zebra-crossing zig zags are gone.
And look! No vans forced to park on either pavement, leaving the approaching pedestrian to walk down the pavement without getting in our way on the road (merely the pavement, of course), no congestion caused by delivery vans forced to park half on the road, half on the pavement, no meandering cyclists in our way.
This provides clear proof that the cause of congestion is not traffic lights, the way our fellow travellers, the Drivers Alliance, or bus lanes, the way our-man-in-whitehall so believes. No, it is the restrictions on drivers parking where they need to that causes traffic problems in British cities!
We have another tax-dodging cyclist being monitored through a camera secretly mounted onto their vehicle, awpsbristol.
This is good as it gives us better coverage of more of the city, and we can see how these tax-dodgers are a threat to safe travel around the city. Here we can see ThyssenKrupp Elevator Van YD09FCP only just managing to squeeze past the subversive cyclist, so enabling him to reach his parking area three seconds ahead of the cyclist.
Remember: game theory and the minimax strategy requires vehicles to pull in as soon as they can; anything else would encourage more of these bicycle-terrorists. It's not that you don't gain anything in journey time, these overtakes are needed to assert your authority over the cyclists, to show them that they are unwelcome, near-stationary objects, on the roads we pay for.
One question that has to be raised here is why are there people cycling around this part of St Philips, the light-engineering core of the working inner city. Well, it could be because they and pedestrians are banned from the flyover the cyclist is about to go under at the end of the video -which shows the problem. When they built the flyover, they mistakenly added some through routes for bicycles, making this one of the routes between the railway path and temple meads. It would be good to blame Blair and Nu-Labour for this, but this was actually built by that Bristol Development Corporation under the conservative governments of yore, showing you can't trust them either.
When looking at road conditions near the bus station, a commentator said "On a more serious point, when I overtake a cyclist I give them plenty of room but when I pass them in the opposite direction I don't see why I should - I trust other motorists are like minded - see 12 secs in!"
Whoever wrote this does not do any driving round Bristol. Otherwise, they would have realised that the oncoming car gave the cyclist exactly as much room as they would any oncoming car. Bristol's streets are narrow, and the easiest way to ensure that you don't bash your car against parked vehicles is simple: drive as close as you can to the oncoming vehicle. That usually works. The only time it does not is when there isn't room for two vehicles to pass. And then? Negotiation time. The Nash Equilibrium: whoever has the least to lose wins. Sometime's that's hidden in phrases like "Best Alternative To a Negotiated Agreement", but what it comes down to is if you value the extremities of your vehicle, there are some parts of the city you should not go.
Some people with 4X4s often fall for the belief that their vehicles are more robust, that they should automatically get through first. But that's a lie, made worse by the way the raised seating position makes it harder to see where the ends of their vehicles lie. No, the driver who gets the right of way is the one driving the 1970s volvo: indestructible and fully depreciated, or the battered ex-minicab: nothing left to lose.
Accordingly cyclists are in trouble. Their body parts are where wing mirrors go, so their cue that something has gone wrong is not a noise from their car, more sharp pains in their hands. Which is why we think they should be banned from Montpelier. It's too narrow, and the Nash Equilibrium ends up with them in Accident and Emergency, rather than the usual scene of us drivers shouting at each other, flipping back or picking up their mirrors, and driving off.
Look at the video of Picton Street. There isn't room for the bicycle to pass the oncoming car just where one of the residents has parked up on the pavement with the double yellow lines. Both parked car and oncoming car are vehicles their owners don't value much, and their wing mirrors are stronger than the cyclists hands. Fortunately, the driver is paying attention -Montpelier is to narrow for phone conversations- and the negotiation is completed quickly and safely.
But the bicyclist is at a disadvantage: they rely on the voluntary goodwill of the car drivers. Normal wingmirror negotiations are between near-equals, and now there are these bicycle people demanding more rights. It isn't going to work
Some postings of this blog are sponsored by the EPSRC as a form of community outreach, primarily to popularise mathematics. Like Bang Goes The Theory on the BBC (also sponsored by EPSRC) only without the bang. Or the bouncy presenters. Or the coke budget needed to make kids tv presenters so bouncy.
Given the current politicians-versus-science disasters, from cannabis risk assessment to the technically unworkable three-strikes-and-out downloading proposals, the need to cover such topics is stronger than ever. Otherwise the politicians get their beliefs from the daily mail, and that can't be considered "rational" by post-enlightenment standards. Indeed, most of our mathematics outreach budget is spent in whitehall, trying to explain to ministers how negative numbers work.
For Bristol, Game Theory, again. Not the Nash Equilibrium, this time, but minimax game algorithms and alpha-beta pruning, and the consequence, the Horizon Effect.
This coverage was triggered by someone commenting on our Save Double Parking posting, asking why cars always overtake bicycles just before they do some other operation, such as stop suddenly:
"When you're on a bicycle, many drivers think they have a right, nay a
prerogative, nay a DUTY, to overtake you, no matter how dangerous, or
pointless it may be."
Well, yes they do have a right, but the question is, is it a duty? And if not, why, as these tax-dodgers claim, do we overtake them so often?
One hypothesis is that it is because the tax dodgers are effectively stationary objects, of course you have to swing past them. But that isn't enough, as we have data which implies it happens regardless of bicycles speeds. No, a better explanation is needed: game theory.
The first point to consider: what is the game. The bicyclist is trying to reach their destination alive, their "moves" are decisions about pedalling and braking, routes to take, what to do at lights.
Motor vehicle drivers are trying to reach their destination in a timely manner.
Both groups of players have a key feature: the happiness of other road users is not a concern. Most car drivers in the city would gladly overtake anyone not doing the speed limit, anyone pootling along radiating hints that it wants to pull over -it's just harder to to pass a car. When there is a bike on the road, it is easy to pass, but as a price, it slows you down more until you get that moment to pass.
Returning to the game that is "Traversing the City". Cars, vans, buses have moves too: the steering wheel, the accelerator, the brake pedal, the gears, the indicators. These can be used to implement the decisions to make: where to go, when to pass,when to stop, whether to indicate your plans in advance.
Consider also the fact there is effectively a conflict in the city between competing road users: pedestrians, cyclists, motor vehicles. Bicycles get in the way of cars rather than staying in the gutter to punish cars, so cars and vans pass bicycles punish bicycles by braking or turning after overtaking. It's not that they have to, but that they can. By making the journey by bicycle more miserable, it will discourage them.
This is the essence of the minimax strategy (wikipedia entry, Manchester CS Dept slides). Minimax is the foundation of computer gaming, whether the games is something the kids are playing on their DS in the back of your SUV, or a US Department of Defence mainframe plotting the warplan between Nato and the Warsaw Pact back in the 1980s, when the moves involved tanks and strategic armaments whose deployment took cities off the game board called Europe.
The Minimax Strategy: applying a scoring assessment to the game, the minimax strategy says:
pick the moves that deliver the best score to your player, and the worst score to the opponent.
That is profound, and kills the whole concept of "let's just coexist", because if you are driving, that's a losing strategy. The very presence of bicycles inconveniences you -and encourages more cyclists. So yes, you do overtake them, you give them a bad experience -otherwise they come back. That is not malicious, that is minimax.
Some issues with minimax:
Scoring -how do you score the game? Arrival time isn't enough, you need to include discomfort. Now the rainy season is returning, splashing bicycles and pedestrians by driving through puddles helps
The Horizon Effect. How many moves ahead do you look? There is always going to be a horizon, beyond which you stop looking, and there's a risk that you end up choosing the wrong moves, because you didn't look far enough ahead.
The reason, therefore, that cars stop immediately after passing a bicycle is for two reaons. One: it helps produce a worse outcome for the bicycle. Two: they only had a lookahead of one move, and the next operation was not planned for.
That's Minimax then; a good strategy for games where the scoring is possible. Bluff games are trickier; it was always one of the issues of the Cold War: the USSR played Chess; the US played Poker.
Now, let's look at this in the context of Bristol, along Shaldon Road, Lockleaze. This is a good road for our experiment as it is a continuous straight road, and there are lots of left turns off it, so we can see how different vehicles behave with a bicycle slowly pootling up a hill.
Time
Event
0:05
Lorry passes bicycle, gives 20-50cm of clearance. The URL on the side of the vehicle, williamstewart.uk.com, is close enough for the cyclist to remember and comes out well in the video.
0:09
Lorry #2 passes bicycle, unusually gives more clearance. The logo says "Welsh Pantry"; presumably they are visitors to the city from overseas. We shall complain to their firm about failing to blend in.
0:15-0:18
Vehicles are held up briefly by the bicycle and oncoming traffic, but do manage to get past.
0:23
A red polo passes, indicating right.
0:24
A silver Vauxhall Vectra KF04FBE passes. This car has been held up by all bicycle-initiated delays, and applies minimax to punish the bicycle; refusing to pull out much and swerving in early. However, it brakes at the same time. This a sign of the horizon effect -it has been so busy planning the minimised score of the bicycle that it failed consider what its next move would be -and whether that red car was indicating its intent to turn right.
0:31
The red polo turns, so KF04FBE can go ahead and do its left turn. The delays caused by the bicycle here have cost it time, that has to be regained by a bit of speed before slowing and turning left. This waste of fuel is caused entirely by the so-called green transport.
0:38 -1:28
Dull bits that remind us why cycling is so boring that we hate it.
1:32
Kellaway Building Supplies. In our discreet post-mortem with our unsuspecting cyclist, apparently having a lorry overtake you near here with its left turn indicators on is very disconcerting. Well, they can always drive can't they?
1:34
Van somewhat inconvienced by bicycle positioning -too far out-comes past and speeds up.
1:43
Ford Ka comes past, indicating left, then starts turning over the bicycle. Then it decides that in fact it does not want any bicycle marks on its paintwork, and comes to a complete halt, leaving the bicycle to continue on straight. Again, a mixture of minimax and horizon effect. If the car had driven faster it could have cleared the corner.
Notice how nearly all of these vehicles give the bicycle room. including the Vauxhall Vectra that has to do a hard brake after pulling in, and the Ford Ka, which gives the bicycle incredible amounts of clearance before starting to turn over it.
While some of the drivers may resent the bicycles, may want to discourage them from cycling, nobody wants a collision. It's not just the injuries you cause, it's the fact that bicycles rarely have insurance and the damage they can do to your vehicle can be quite serious. The short term gain of running over one bicycle is lost by the delays and the insurance.
There you have it then, minimax. The cyclist's goal was to position themselves where tyey felt safe (their Max) -not merely regardless of inconvenience to tax payers, but precisely because it slowed the cars down (the car's Min). The cars and lorries mostly reacted by passing the bicycle as soon as they could (their Max), and, for some of the players, trying to reduce the cyclist's experience -be it pulling in and braking, or simply turning while partially past the bicycle.
This concludes this week's Game Theory session. For further details, please consult this MIT coursework. As we said before, bluff is the other game aspect, which comes up in "wing-mirror bluff" and negotiation over who gains ownership of a single lane road.
This research was supported by the United States Air Force Office of Scientific Research and Development Command, and by the EPSRC.
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
follows:
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
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.
A hold and wait condition exists: it is possible to claim one resource (the junction or an exit) before acquiring the other.
Resources cannot be taken by force. There is no easy way to remove a vehicle from the junction or an exit.
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.
Posts
