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 (-5[1])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 (15[1])arduous search for a (*) partner after the death of his first wife. The best strategy for this problem, (-5[1])which succeeds with probability approaching 1 (10[1])over e, is to always look at the first n over e options (10[1])and choose the next option that’s better than all of them. For 10 points, name this problem central to optimal (10[1])stopping theory, whose most common formulation involves a manager hiring the best assistant. ■END■ (10[1])

Back to tossups