[Math] Best strategy to find a parking spot

decision-theoryprobabilitypuzzlerecreational-mathematics

New Bounty Edit (2 days remaining on the Bounty):
To point out that the only answer given at this time cannot be considered an answer, because it simply gives a hint on how to formally model the problem, which is not what I was looking for, considering I wrote it informally on purpose. Still looking forward to some analyses of this problem!

I was wondering about the following problem.

Assume the following.

  • you have to find a parking spot for your car in a very busy saturday night to go in a restaurant;
  • you search for this parking spot by basically going around (literally) in the hope to get a spot;
  • of course, (the saturday night is really busy) other people are in the same situation as you are and they are running in circle like you are;
  • the direction of the movement is only one (again, you literally go around);
  • the time frame of the problem lies between 20:00 and 00:00. Finally (of course!);
  • when you start your search at 20:00 there are no free parking spots.

Question:
What is the best strategy you can use to find a parking spot?

  1. Should you stop in a place and wait until one of the cars that you can cover with your eyesight leaves?

  2. Or is it better to move around in the hope to find a free parking spot?

I was thinking about the following few variables that I think should essentially change the nature of the problem:

  • Cardinality of the set of parking spots (countable vs. uncountable);

  • Cardinality of the set of agents involved in this situation (countable vs. uncountable);

  • Probability of having a car that already occupies a parking spot leaving that lot in function of time (normally distributed, uniformly distributed, etc);

  • Farsightedness of the agents (extreme cases: one place ahead of you, whole circle ahead of you)

Hence, a solution should be explicit about what is assumed concerning those variables.

[Notice that the in general I assume that the space where you are looking for a spot is homeomorphic to a circle]

Any feedback as always is most welcome.

PS: As you can guess, where I live it is very (very!) difficult to find a parking spot on Saturday nights…

Bounty Edit:
As in the bounty text, I would like to know what are reasonable answers to this question (without considering as options using the bus, the tram, a bicycle or an helicopter…).

Best Answer

Here's an attempt at a reasonable mathematical model for this. We'll suppose you're on a circular road with $N$ parking spots (numbered $0$ to $N-1$) and $N$ corresponding waiting positions (also $0$ to $N-1$) for your car. At each waiting position $x$ , you can see $m$ parking spots ahead (positions $x$ to $x+m-1 \mod N$). Yours is one of $p$ cars waiting for a spot. Parking spots become available one-by-one in random order. If one of the $m$ spots you can see (say position $y$) becomes available, you can get that spot unless one of your competitors ahead of you (in position $x+1$ to $y$) can get it. You can also move to the next available position. Your competitors have the same abilities.
We need a way to resolve conflicts where two competitors want to move to the same position at the same time: let's say that competitors who desire to move are given that opportunity in random order.

We will assume no collaboration or communication. The object is to be the first car to find a parking spot.

EDIT: There are some more details to be decided: how much can you see of the positions of the other competitors, what is the probability of a position becoming available between one move and another?

Related Question