Finding the Cheapest Gas

A friend posed the following puzzle:
Suppose one is driving through a town with N motels or gas stations or whatever. N is known. One sees the prices posted. One is not allowed to turn around. The puzzle is this: what's the optimum strategy for finding the best price for a motel or gas? There is an optimum strategy.

I'll expand a few points:

You might want to think about the problem before going on.

Whilst in the process of corresponding with the poser of the puzzle about his notion of "optimum strategy" or "maximizing the outcome", I wrote a program to compare gas-buying strategies according to my notion of optimum--the strategy with the best

expected price-- the price the strategy picks, averaged over possible worlds.
SPOILER: Here is where the puzzle poser's answer is given. His answer, a strategy I'll call "hold_out", goes through an "information gathering" phase, looking at N / e prices (about 38% of the prices), and then holds out for a price that is as good as or better than the best seen in the "gathering". If no such price is seen, it takes the last price.

I whomped up a strategy I called "linear_slide", which goes through the same information gathering phase, then slides its buying threshold starting at the best price seen, and moving so that the threshold reaches the average price seen (the running average, so it's really a wiggly slide) by the time it reaches the second-to-the-last price. (If the slide starts at the second-to-the last, use the average as the threshold.) As with hold_out, if you get to the end, take the last price.

These I subjected to trials where the prices are set like this:

  for( i = 0;  i < n;  i++ ) {
    prices[i] = (double) rand() / RAND_MAX;
  }
...a block-shaped distribution, but the puzzler said the price distribution doesn't matter.

Calculemus! (Let us calculate.)

Here are some results. The "price" column shows the average price a strategy picked through all the runs. "got min" shows how often it picked the smallest price in the set of n. "got better" shows how often it picked a better price than its competitor did.

n = 3, 10000000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
  *  4.165912e-01    *  5.000318e-01    *  0.000000e+00    hold_out
  *  4.165912e-01    *  5.000318e-01    *  0.000000e+00    linear_slide

n = 4, 7500000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     3.748170e-01    *  4.585467e-01       3.140600e-02    hold_out
  *  3.644970e-01       4.376440e-01    *  5.192840e-02    linear_slide

n = 6, 5000000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     3.331782e-01    *  4.278488e-01       7.340940e-02    hold_out
  *  3.006933e-01       3.843516e-01    *  1.302930e-01    linear_slide

n = 10, 3000000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     2.749750e-01    *  3.986953e-01       1.293170e-01    hold_out
  *  2.187899e-01       3.191723e-01    *  1.997420e-01    linear_slide

n = 30, 1000000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     2.246291e-01    *  3.787530e-01       2.595500e-01    hold_out
  *  1.104394e-01       2.076570e-01    *  3.266040e-01    linear_slide

n = 100, 300000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     1.975867e-01    *  3.719933e-01    *  3.794967e-01    hold_out
  *  5.739023e-02       1.224833e-01       3.484133e-01    linear_slide

n = 1000, 30000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     1.864774e-01    *  3.665667e-01    *  5.302000e-01    hold_out
  *  1.759512e-02       4.113333e-02       3.641667e-01    linear_slide

n = 10000, 3000 runs    (< = minimize, > = maximize, * = winner)
  <         price    >       got min    >    got better    
     1.847001e-01    *  3.760000e-01    *  5.960000e-01    hold_out
  *  5.481258e-03       1.733333e-02       3.663333e-01    linear_slide
When n = 3, the two strategies behave identically.

From then on, hold_out always gets the minimum price more often than linear_slide, and as n approaches infinity, it seems to settle on getting the minimum price about 37% of the time, while linear_slide gets it less and less often.

However, starting when n = 4, linear_slide's average price is better than hold_out's. As n approaches infinity, linear_slide's average approaches 0, while hold_out's average approaches .19, because 38% of the time hold_out takes the last price (a random price that averages .5).

The last column is interesting. At first, linear_slide gets a better price than hold_out most of the time, but starting around n = 100, hold_out beats linear_slide more often. (The two numbers in the "got better" column add up to the frequency that the two strategies get different prices.)

To summarize, whenever the strategies act different:

And that's why I had asked my friend about his notion of "optimum strategy", "maximizing the outcome," or "getting the best price, all things considered".

Check out the simulator source code and the text file of the output.

--Steve