Sunday, January 10, 2016

Sadistic Car Salesman

Solution to @ollie's Car Salesman Problem

120 elementary orderings. 
Never take 1st card.  Upon 2nd card, if difference (2nd minus 1st) is
·         -400: Take it (6 outcomes, E=N+0)
·         -300: Take it (12 outcomes, E=N+50; 50% chance of N, 50% of N+100)
·         400:  Wait for N+100 (because you now know N) (6 outcomes, E=N+100)
·         300:   Define the first card as X.  Take X+100 when it comes, or take X-100 if that comes first.  (12 outcomes, E=N+100)
·         -200, -100, 100, 200:  Choose next card that is better than *both* of the first two, with two exceptions:
·         If the sequential differences are +200, +100, -200, or if they are -200, +300, -200, then see the 4th card.  It is in between the 1st and 2nd card (not below both) but you get a better expectation than waiting for the 5th card.
·         If you come to know the optimal remaining choice (because you’ve seen values 400 apart), take it. This occurs when you see sequential diffs of -100/+400, or +100/+300, you know what N+200 is and that it is your optimal choice.  Or if you see +200/+200 or -200/+400, you know what N+100 is and that it is your optimal choice.
·         This strategy (including exceptions) gives you E=N+88.9 when the first difference is +/-200, 18 outcomes each.  And gives you E=N+108.3 when the first difference is +/-100 (24 outcomes each).

1st Difference     Outcomes:     E(as amount over N)
-400                  6                  0
-300                 12                 50
400                   6                100
300                  12                100
+/-200               36                 88.9
+/-100               48                108.3

Total overage = 10,800 out of 120 cases, average overage of 90 (N+90)


Trying to write it as efficiently as possible:

  • Never take 1st card (C1).  Upon C2, calculate difference (D1=C2-C1).
  • If D1 in (-400,-300) then choose C2
  • Else if D1=400 then wait for N+100 and choose it
  • Else if D1=300 then choose the next card that is equal to C1+100 or C1-100.
  • Else if D1 in (-200,-100,100,200) then see C3:
    • If C3 < min (C1,C2) then choose it, else see C4
    • If C4 < min (C1,C2) then choose it,
    • Else if C3 is N+400 (i.e., C3 – min (C1,C2) = 400) then the optimal remaining card is known (could be N+200 or N+100).  It could be C4 (choose it now) or C5 (wait for it).*
    • Else if the sequential differences (D1/D2/D3) are +200/+100/-200, or -200/+300/-200, then choose C4.**

*     [Note: this affects 8/120 elementary orderings, with differences of -200/+400, or -100/+400, or +100/+300, or +200/+200]
**   [Note: This affects 4/120 elementary outcomes.  The basic strategy of “wait for 1 better than both of C1/C2” results in N twice and N+400 twice.  Choosing C4 results in N+100 twice and N+200 twice.]

There are 120 (5!) possible orderings.  Among those, you pay
N:           53 times
N+100:  42
N+200:  15
N+300:  4
N+400:  6