10
$\begingroup$

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...).

$\endgroup$
  • 4
    $\begingroup$ Take the bus, instead. $\endgroup$ – Gerry Myerson Oct 7 '15 at 11:23
  • 2
    $\begingroup$ By a parking lot do you mean a parking spot (that is, a place for an individual car)? ¶ @GerryMyerson: Haha. $\endgroup$ – Brian Tung Oct 8 '15 at 17:57
  • $\begingroup$ Ops, indeed. I am going to edit it. $\endgroup$ – Kolmin Oct 8 '15 at 18:00
  • 1
    $\begingroup$ You need to be much more concrete about the model if you want to get any good answers. The question at the moment basically says: "make up a model and solve it". $\endgroup$ – Winther Oct 13 '15 at 21:58
  • $\begingroup$ @Winther: I do not really agree. What I am saying is that there are various points that should/could be relevant. A complete answer is one that takes into account all this points (if they are all relevant afterall). $\endgroup$ – Kolmin Oct 13 '15 at 22:32
3
+25
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. As a matter of fact, I see the mathematical model (I was not explicit in writing it formally form some aesthetic appeal and in order to not lose contact with the story behind). Still, I don't see an answer to the best strategy that can be implemented given certain explicit assumption. $\endgroup$ – Kolmin Oct 8 '15 at 19:10
  • 2
    $\begingroup$ It's not clear to me that there is a 'best strategy' in this scenario, because you haven't outlined what your 'opponents' are doing. As things stand, the problem is still too ambiguously posed to have a proper mathematical answer. $\endgroup$ – Steven Stadnicki Oct 13 '15 at 21:56
  • $\begingroup$ @StevenStadnicki: I don't agree in the sense that the other players do exactly the same as us, they look for a free parking spot, that's why we don't really think to look at this problem in terms of a game. So, a potential situation is one with uncountable parking spots, countably other agents, where everybody can see no more than a quarter of the circle ahead of her/himself, where the probability distribution of finding a free parking spot in function of time for the interval 20:00/00:00 is uniformly distributed. In that case what is the best strategy: stop in a place and wait or move around? $\endgroup$ – Kolmin Oct 13 '15 at 22:29
  • $\begingroup$ Under appropriate conditions, a Nash equilibrium is guaranteed to exist. pnas.org/content/36/1/48.full $\endgroup$ – Robert Israel Oct 13 '15 at 22:49
  • $\begingroup$ @RobertIsrael: I agree. I think it is not particularly difficult to describe a NE equilibrium given the conditions I wrote down in the comment above to StevenStadnicki. But I still don't think this is the proper way to look at this problem. $\endgroup$ – Kolmin Oct 14 '15 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.