Question

Solving this problem is essentially equivalent to the mechanism design problem of making an adaptive limited-supply auction. A problem similar to this one but with a fixed order is called the prophet inequality problem, where “prophet” is spelled P-R-O-P-H-E-T. Martin Gardner first formulated this problem as a game involving slips of paper with numbers from zero to a googol. The first chapter of the bestseller Algorithms to Live By centers on this problem and cites the example of Johannes Kepler’s arduous search for a (*) partner (10[1])after the death of his first wife. (-5[1])The best strategy (10[1])for this problem, (10[1])which succeeds with probability approaching 1 over e, is to always look at the first n over e options and choose the next option that’s better than all of them. For 10 points, name this problem central to optimal stopping theory, whose most common formulation involves a manager hiring the best assistant. ■END■ (0[1])

Back to tossups