Written by Colin+ in game theory, modelling, probability.

From time to time, I come across a problem that has me scratching my head. In a good way. I like brain-teasers. Sometimes I solve them, sometimes I don't.

This is one that I haven't solved -- but I wanted to share the thought process that goes into modelling the situation so that you could, if you wanted to. An insight into my mind, if you like.

I was driving home the other night. I don't have a garage and the street parking in my neighbourhood is first come, first served. It was about 8pm, so most people were already home -- meaning most of the spaces were taken. The question that sprang to mind was, how close to home would a space need to be before I'd consider parking in it?

There are a few things I'd need to consider:

- how far away the space is from my house
- how annoyed I'd be if I walked from there (the cost of walking home);
- how likely I am to find a better space;
- how annoyed I'd be if I kept on driving without finding a closer space (the cost of driving on).

This is a problem of game theory, although it's not a very interesting game: it'll end after this move. Game theorists talk about the annoyance factors as costs -- walking home might 'cost' me, say, 0.3 goves per kilometre, while driving on might be as low as 0.07 goves. The important thing isn't so much the numbers or the units (repeat after me: the gove is not important), as finding a relative cost for each choice of action.

The likelihood of finding a better space is an interesting problem in itself. In my neighbourhood, I've no particular reason to believe that one space is more likely to be filled than any other, so it'd be reasonable to assume that each space is equally likely to be filled. I could come up with an estimate of the probability by counting the ratio of filled to unfilled spaces so far, and then estimate the number of empty spaces I'd expect to see between now and home.

(This wouldn't work so well in, say, a big car park. You'd need to take into account the fact that cars are more likely to park close to the ticket machines and close to the exit and come up with a complex model relating your observations to the probabilities.)

The trick in the solution will be to compare the annoyance of parking up and walking to the *expected* annoyance of driving on -- including how far I'd expect to have to drive to a better space and then how far I'd have to walk home.

As I say, I didn't come up with an actual proper solution to the problem -- my feeling was that there'd be a better space around the corner, and there was -- but I don't know whether I got lucky. But I know how I'd work it out if I needed to.

## splittter

Is annoyance at carrying on something like:

P(Finding a space after here)*(annoyance at walking halfway home from here) + P(Not finding a space after here)*(annoyance at walking home from that spot) + P(Not finding a space after here)*(annoyance at not having taken this space)

So when that\’s less than (annoyance at walking home from this spot) carry on.

I think this assumes annoyance at walking home is linear, which seems fine – and that the space you just passed remains open, which obviously isn\’t always true but not terrible.

Other factors to consider are (joy at finding a space right next to my door), and how to account for Murphy\’s law, specifically that there\’s never a parking spot after the one that you thought you maybe should take but didn\’t 🙂

But, it occurs to me that if you correctly worked out & applied this forumla you should eliminate (annoyance at not having taken this space), as your actions would be mathematically 100% sound!

## Colin Beveridge

Ha! 😀