A ‘Price is Right’ Algorithm

You’ve probably watched The Price is Right TV game show. On it they run the Clock Game.

The game is played for two prizes. The actual price of the first prize is shown to the studio and home audiences. After the contestant gives their first bid, a 30 second clock is started and the host tells the contestant whether the actual price is higher or lower than the bid. The contestant continues to bid, responding to the host’s clues, until either the contestant wins by correctly guessing the price of the prize or the time expires. If time remains after the first prize is won, the process is repeated for the second prize.…With few exceptions, only prizes valued below $1,000 have traditionally been offered in the Clock Game.

The algorithm to use is simple:

  • Pick a ceiling ($1000) and a floor ($0)
  • Bid the average ($500)
  • If the bid is too low, the bid becomes the floor
  • If the bid is too high, the bid becomes the ceiling
  • Repeat

Being computer types, we’ll put the ceiling at $1024. For a $407-priced prize, your guesses would look like this:

  C D E F
1   407 <-- Price  
2 Floor BID   Ceiling
3 0 512 Too High 1024
4 0 256 Too Low 512
5 256 384 Too Low 512
6 384 448 Too High 512
7 384 416 Too High 448
8 384 400 Too Low 416
9 400 408 Too High 416
10 400 404 Too Low 408
11 404 406 Too Low 408
12 406 407 Stop 408

 
Ten guesses, and you’ve won a washing machine. Here are the formulas that make this work.

  • D1: = 407 (the unknown price)
  • C3: = 0 (the initial floor)
  • F3: = 1024 (the initial ceiling)
  • D3: = (C3+F3)/2 (512—the initial bid)
  • E3: = IF(D3=$D$1,”Stop”,IF(D3>$D$1,”Too High”,”Too Low”)) (the host’s clues)
  • C4: = IF(E3=”Stop”,””,IF(E3=”Too Low”,D3,C3))
  • D4: = IF(E3=”Stop”,””,(C4+F4)/2)
  • E4: = IF(D4=$D$1,”Stop”,IF(D4>$D$1,”Too High”,”Too Low”))
  • F4: = IF(E3=”Stop”,””,IF(E3=”Too High”,D3,F3))

Watch out for “curly quotes” if you copy and paste in. Filldown C4:F13. So what’s the point? We knew the “unknown price” going in. Here’s a recent prospective employee question the BBC got from Qualcomm:

Given 20 ‘destructible’ light bulbs (which break at a certain height), and a building with 100 floors, how do you determine the height the light bulbs break?

You watch The Price is Right or you read DDoE, and you think “Clock Game!” In 20 bulbs, if they break from a 407.407 foot drop, and a floor = 10 feet:

    407.407 <-- Break  
  Floor BID   Ceiling
1 0 512 Too High 1024
2 0 256 Too Low 512
3 256 384 Too Low 512
4 384 448 Too High 512
5 384 416 Too High 448
6 384 400 Too Low 416
7 400 408 Too High 416
8 400 404 Too Low 408
9 404 406 Too Low 408
10 406 407 Too Low 408
11 407 407.5 Too High 408
12 407 407.25 Too Low 407.5
13 407.25 407.375 Too Low 407.5
14 407.375 407.4375 Too High 407.5
15 407.375 407.4063 Too Low 407.4375
16 407.4063 407.4219 Too High 407.4375
17 407.4063 407.4141 Too High 407.4219
18 407.4063 407.4102 Too High 407.4141
19 407.4063 407.4082 Too High 407.4102
20 407.4063 407.4072 Too High 407.4082

 
You’re 2-ten-thousandths of a foot off. You get the job, a great way to start the new year.

 
…mrt
©¿©¬

5 thoughts on “A ‘Price is Right’ Algorithm

  1. Binary search. Why not juice it up with exponential extrapolation to bracket the target value?

    With the target value in a cell named target, start off with 500 as the initial guess in cell A4, and hi/lo/done in B4, so

    A4: 500

    B4: =LOOKUP(SIGN(target-A4),{-1;0;1},{“hi”;”done”;”lo”})

    Either A4 is the target value, or it still needs to be bracketed.

    A5: =ROUND(IF(B4=”done”,A4,IF(B4=”hi”,A4/2,A4*2)),0)

    B5 is just B4 filled down.

    The rest could be accomplished with formulas only in column A.

    A6:
    =ROUND(IF(B5=”done”,A5,IF(SIGN(COUNTIF(B$4:B5,”<>”&B5))=0,IF(B5=”hi”,A5/2,A5*2),
    AVERAGE(A5,LOOKUP(2,1/(B$4:B5<>B5),A$4:A5)))),0)

    with B5 filled down as far as needed.

  2. I haven’t quite watched this show to comment, but to comment on your procedure, I believe this is called the Bisection method of root-finding approximation.

    There are many methods that can be employed, like Regula Falsi method which uses the secants to derive the next interval [a,b] or the Newton Raphson method which uses a tangent to derive the [a,b]. These might be faster converging, hence lesser steps, but what could be a problem is deriving a functional form for the root in question!

    Just curious – within a 30 sec time limit, how many ppl crack this? Are you given additional computing help or just mental math? And is there a limit to the number of trials other than time?

  3. Hi Arun –

    Thanks. I only watch when I’m sick, so I don’t see it very often. I’ve never seen anyone win the two prizes, but most everyone gets one. They all do it differently/sub-optimally. They go in half-steps until they’re close and below, and then they just count up by ones not waiting for clues. Which maybe is why they don’t win twice.

    They get no other help than the host. This is one game that the audience is quiet for.

    …mrt

  4. @Arun, secant and Newton-Raphson require you know the function, actually the latter requires that you also know the derivative of the function. You don’t derive it/them. If you don’t know the function, you use nonparametric methods.

    Secant and Newton-Raphson also require that the function be continuously differentiable. That’s not the case with the Price Is Right function. It’s discontinuous, trivalent: LOW if the current guess is below the actual price, HIGH if the current guess is above the actual price, or YOU WIN. That’s amenable to binary search, but not to these other approaches.

  5. @fzz – That’s exactly what I stated in my comment “finding the functional form for the root is a problem!”. It’s probably suited better for a different type of game, you’re right about this is suitable for this game.

Leave a Reply

Your email address will not be published. Required fields are marked *