The Sadistic Car Salesman

This has some people stumped. I'm a little hesitant to put this out there because it may not be optimal yet, but I'm somewhat confident.  Here is the riddle quoted from FiveThirtyEight: 

You go to buy a specific car, whose fair price we’ll call N. You have absolutely no idea what N is and the dealer, sadistic capitalist that he is, won’t tell you. The dealer enjoys a good chase, though, so without directly revealing the value of N, he takes five index cards and writes down a number on each of them: N, N+100, N+200, N+300 and N+400. Important: the guy’s sadistic but not a math major. The numbers on the cards are numbers, not algebra equations.

He presents the cards to you, one at a time, in random order. (For example, if the price on the second card is $100 more than the first, you can’t be sure if those are the two smallest prices, the two largest, or somewhere in between.) Each time he shows you a card, you must either pay the price on that card, or ask to see the next card. You cannot go back to previous cards. If you make it to the fifth and final card, then that is what you must pay. If you play the dealer’s game optimally, how much should you expect to pay on average above the fair price N?

If we use a naive strategy in taking the first card presented to us, then we will be overpaying $200 on average.  We would like to bring that down a bit.

We know that 4/5 of the time, there will be a smaller card in the remaining 4 cards not yet shown.  So, it seems worth our time exploring a strategy beyond just stopping at the first card.

Let's explore the 20 possible cases of being shown 2 cards in order in a condensed version.  Let N0 be the card with the smallest value, N1 the card with N+100, and so on, up to N4.

Let's look at the difference between the first two cards.

When the order is (N4,N0), we've lucked out and have been shown the largest and smallest card in order with a difference of 400.  We stop here and pay the fair price!

With the order (N4,N1) or (N3,N0), we have a difference of 300.  It doesn't take long to figure out that in this scenario, you should stop. This gives us an average of $50 over if the difference is 300.

With the order (N4,N2), (N3,N1), or (N2,N0), we have a difference of 200. Given a difference of 200, you will have an average of $100 over fair price if you stop.  If we use the strategy of having more cards shown to us until the first time we see something smaller we will end up only paying $94.44 over the fair price on average.  Let me try to explain.

Given the (N4,N2) scenario, we have a 50/50 chance of spending 0 or 100 over using this strategy.  Given the (N3,N1) scenario, we have a 100% chance of spending 0 over.  The (N2,N0) case is a bit tricky, since we are given all information if N4 comes up before N1.  This will happen half the time for a payment of only 100 over.  One-sixth of the time you will pay 300 over, while 1/3 of the time you will pay 400 over.  This averages out to $233.33.

Since these three cases are equally likely (1/3 a piece), we have an average of (50+0+233.33)/3=94.44.

We can have a difference of 100 with the orders (N4,N3), (N3,N2), (N2,N1), or (N1,N0).  Again, employing the strategy of taking the next lowest valued card is to our advantage.  It will have us pay $108.33 over the fair price on average.  This takes a similar analysis to the one above.

When we take the reverse order of those above, we can find an average of $108.33 and $94.44 over the fair price by using the same strategies for -100 and -200 as we do for 100 and 200 respectively.

For a difference of -300 with (N1,N4) or (N0,N3), we should take the card that is either next higher or next lower than our first card as the optimal strategy.  This leaves us with an average of $100 over.

If we happen to get (N0,N4) with a difference of -400, then we can be absolutely sure that we will pay only $100 over.

In summary, we pay fair price (0 over) with probability 1/20, we pay an average of $50 over with probability 2/20, an average of $94.44 over with probability 6/20, an average of $108.33 over with probability 8/20, and an average of $100 over with probabilities 2/20 and 1/20 (or a total of 3/20).

This gives us a total average of $91.67 over the asking price, or 275/3 to be exact.