Suppose we are trying to find a parking space near a restaurant. This
restaurant is on a long stretch of road, and our goal is to park as
close to the restaurant as possible. There are *T* spaces leading up
to the restaurant, one spot right in front of the restaurant, and *T*
after the restaurant as follows:

Each spot can either be full (with probability, say, .9) or empty
(.1). As we pass a spot, we need to make a decision to take the spot
or try for another (hopefully better) spot. The value for parking in
spot *t* is . If we do not get a spot, then we slink
away in embarrasment at large cost *M*. What is our optimal decision
rule?

We can have a stage for each spot *t*. The states in each stage are
either *e* (for empty) or *o* (for occupied). The decision is whether to
park in the spot or not (cannot if state is *o*). If we let
and be the values for each state, then we have:

In general, the optimal rule will look something like, take the first
empty spot on or after spot *t* (where *t* will be negative).

Tue Jun 16 13:34:09 EDT 1998