``Linear'' decision making

. Many decision problems (and some of the most frustrating ones), involve choosing one out of a number of choices where future choices are uncertain. For example, when getting (or not getting!) a series of job offers, you may have to make a decision on a job before knowing if another job is going to be offered to you. Here is a simplification of these types of problems:

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