Secretary Problem - The Game of Googol

The Game of Googol

According to Ferguson 1989 the Secretary Problem appeared for the first time in print in Martin Gardner's column of Scientific American in 1960. Here is how Martin Gardner formulated the problem: "Ask someone to take as many slips of paper as he pleases, and on each slip write a different positive number. The numbers may range from small fractions of 1 to a number the size of a googol (1 followed by a hundred 0s) or even larger. These slips are turned face down and shuffled over the top of a table. One at a time you turn the slips face up. The aim is to stop turning when you come to the number that you guess to be the largest of the series. You cannot go back and pick a previously turned slip. If you turn over all the slips, then of course you must pick the last one turned."

In the paper "Who solved the Secretary problem?" Ferguson 1989 pointed out that the Secretary Problem remained unsolved as it was stated by M. Gardner, that is as a two-person zero-sum game with two antagonistic players. In this game Alice, the informed player, writes secretly distinct numbers on cards. Bob, the stopping player, observes the actual values and can stop turning cards whenever he wants, winning if the last card turned has the overall maximum number. The difference with the basic Secretary Problem is that Bob observes the actual values written on the cards which he can use in his decision procedures. The numbers on cards are analogous to the numerical qualities of applicants in some versions of the Secretary Problem. The joint probability distribution of the numbers is under the control of Alice.

Bob wants to guess the maximum number with highest possible probability, while Alice' goal is to keep this probability as low as possible. It is not optimal for Alice to sample the numbers independently from some fixed distribution, and she can play better by choosing random numbers in some dependent way. For Alice has no minimax strategy, which is closely related to a paradox of T. Cover. But for the game has a solution: Alice can choose random numbers (which are dependent random variables) in such a way that Bob cannot play better than using the classical stopping strategy based on the relative ranks (Gnedin 1994).