A Simple Cover-Up Game
V. J. Baston, F. A. Bostock · American Mathematical Monthly · 1988
Two decks, each with n cards numbered 1 to n, are shuffled separately, and the top card from each deck is laid face down on the table. One of two players now looks at the numbers on the cards and chooses to turn one of them face up. The other player selects one of the cards and receives from his opponent an amount equal to the number of his selected card. What is a fair entrance fee for the second player to play this game? The problem can be modelled mathematically as a two-person, zero-sum game On as follows. Each element of an ordered pair (xl, x2) is chosen independently from {1, 2, .. ., n } with probability 1/n. Only player 1 sees (xl, x2) and, after seeing it, he covers either xi or x2 before showing it to player 2. Player 2 now either accepts the uncovered number or rejects it and chooses the covered one. The number so chosen is the payoff to player 2. Note that the value of O to player 2 is then the entrance fee required. Before presenting a solution of On we will find some preliminary discussion useful. We will denote by E(X, Y) the expectation to player 2 when player 1 plays the strategy X and player 2 the strategy Y. Notice that player 2 is trying to maximize E(X, Y) whilst player 1 is trying to minimize E(X, Y). If X is a fixed strategy for player 1, then a best reply to X is any strategy Y* such that E( X, Y*) is the maximum of E(X, Y) over all strategies Y for player 2. Similarly, a best reply to a strategy Y of player 2 is any strategy X* such that E(X*, Y) is the minimum of E(X, Y) over all strategies X for player 1. Let X* and Y* be strategies for the players such that X* is a best reply to Y* and Y* is a best reply to X*. Then it is immediate from the definition of optimal strategy that X* and Y* are optimal. Technically, a solution of the game is obtained when an optimal strategy for each player has been found. Although a game can have many solutions, E(X*, Y*) is the same whatever optimal strategies X* and Y* are used for the players, and it is referred to as the value of the game to player 2. The reader who is not familiar with the rudiments of elementary game theory is recommended to consult [3]. In playing On player 2 clearly has simpler decisions to make than player 1, so it is natural to first consider what strategies this player can adopt in order to do well. It is routine to calculate that the maximum and minimum of the two numbers seen by player 1 have expected values (n + 1)(4n 1)/6n and (n + 1)(2n + 1)/6n, respectively. Since player 2 knows he is seeing either the maximum or the minimum, a reasonable strategy for him to adopt is to accept the uncovered number if and only if it is at least (n + 1)/2. A consideration of cases in which n is small suggests that this strategy is indeed optimal and leads to the following theorem.