Introduction The Monty Hall problem remains durable even after years of controversy ([4], [5], [6], [7], [8]). A contestant, say Elaine, stands before three curtains on the stage. Elaine is told that behind one curtain is a brand-new car; behind each of the remaining curtains hides a goat; and the car is equally likely to lie behind any curtain.
Elaine then chooses one curtain, but before opening that curtain the master of ceremonies, Monty Hall, opens another curtain, revealing a goat. He then offers Elaine the chance to switch her choice to the remaining unopened curtain.
Our purpose is not to rehash this well-worn problem, but to show how some recent theoretical advances in game theory allows us to model this situation more realistically than has been done heretofore.
The Monty Hall problem has been modeled decision-theoretically by assuming that Monty Hall follows fixed rules, like a blackjack dealer, and that the only decision-maker is Elaine. With this assumption, the question posed above has a clear answer: Elaine should always switch curtains. In an interview ([5]), however, the real Monty Hall argued that the answer is not so simple. Had it been so, the show would have been too predictable and would soon have been pulled off the air. In reality, Monty Hall was an active, unpredictable player, with his own objectives. Sometimes he would not allow a contestant to change curtains; sometimes he offered players cash on the spot if they would ([5]). Modern game theory can be used to model the strategic situation that faced real contestants on the real game show.
The game The Monty Hall game is diagrammed in FIGURE 1. Technically, FIGURE 1 shows what happens if Elaine initially chooses curtain 2. (That is why the arrows that correspond to other choices at nodes B, C, and D have white heads.) The omitted parts of the game are essentially the same as what is shown. Each rectangular box in the diagram represents a decision node, i.e., a moment in the game at which a player must act. The decision nodes are labeled A-H. Each arrow represents a possible move by a player. Decision nodes enclosed within a dotted oval form an information set for a player. Elaine has seven information sets, three of which appear in FIGURE 1, labeled I, II, and III. When Elaine reaches one of her information sets, she does not know which of the nodes in the set has been reached. Monty knows where the car is.
This fact is captured in FIGURE 1 by the lack of dotted ovals around any of his decision nodes. Monty has ten possible decision nodes, only four of which are displayed in FIGURE 1.
Monty Hall first hides the car behind one of the curtains (node A). Elaine next chooses a curtain (nodes B, C, or D). For simplicity, FIGURE 1 assumes that Elaine chooses curtain 2. Monty then opens one of the three curtains (nodes E, F, or G). If he opens either Elaine's curtain or the curtain hiding the car, then the game ends. But if he opens a curtain hiding a goat, the car's location remains unknown. At this point
Monty can allow Elaine to make her second and final move: she can stay with her initial choice or she can switch to the remaining unopened curtain (nodes H, I, J, or K). The game then ends with two possible outcomes: Elaine gets either a new car or a goat. Though this game seems simple, the game tree is rather complicated.
Depending on the players' moves, the game can evolve along 39 paths (of which 13 appear in FIGURE 1).
The solution To solve the Monty Hall game we will find its Nash equilibrium. A Nash equilibrium is a pair of strategies, one for each player, such that each player's strategy is optimal given the strategy of the other player. (For a discussion of Nash equilibrium, see [1].) To find the Nash equilibrium, we first describe each player's objective. Elaine's objective is obvious: she wants to win the car. Monty's objective is less transparent, but we conjecture that he wants to maximize the number of viewers.
Other shows-not Elaine-were Monty's competitors. The show's rules and Monty's behavior are designed to make the show entertaining. We conjecture that the show is more entertaining the harder it is for the audience to predict the outcome.
One way to model this idea is to add a third player-the television audience. While the audience does not move in the game, it does try to predict Monty and Elaine's moves. Monty's payoff is a function of the accuracy of these predictions. Games of this type are called psychological games; they differ from normal games in that the players' payoffs can depend not only on what the players do, but also on what they believe others will do. A psychological Nash equilibrium is a collection of pairs of strategies and beliefs, one pair for each player, such that the collection of strategies form a Nash equilibrium and the beliefs are consistent with the players' strategies and the laws of probability. A more precise definition of this equilibrium concept can be found [3]. A psychological Nash equilibrium exists under the same conditions as does an ordinary Nash equilibrium in conventional non-cooperative game theory.
The game is easiest to predict if it always results in the same outcome-and hence is uninteresting-and it is hardest to predict if each of the 39 possible decision sequences is equally likely. To this end, clearly, Monty should hide the car behind each curtain with equal probability. Suppose Elaine chooses curtain 2. Now Monty has to decide whether to open a curtain and allow Elaine to switch. He wants to do this in such a way that Elaine will be indifferent between switching and not switching, for then she will be unpredictable. She is indifferent between switching and not switching if and only if the conditional probability that the car is behind curtain 2 given that Monty allows her to switch equals the conditional probability that the car is behind the unopened curtain given that Monty allows her to switch.
Let C2 denote the event "Monty hides the car behind curtain 2," let C13 denote the event "Monty hides the car behind curtains 1 or 3," let M denote the event
"Monty allows Elaine to switch curtains," and let PX IY denote the conditional probability that the event X occurs given that Y occurs. Also let P2 = PMIC2 and let P13 = PM IC 13. Then Bayes' theorem implies
Thus Elaine is indifferent between switching and staying with her initial choice if and only if P2 = 2 P13. That is, Monty should be twice as likely to let a contestant switch curtains when she initially chooses the curtain hiding the car as when she chooses a curtain hiding a goat.
The game has six possible outcomes, which are displayed in Table 1. Table 1 also gives the probabilities of these outcomes as functions of three parameters PE, P13, and P2, where PE is the probability that Elaine switches curtains if given the chance.
Elaine's behavior, as encapsulated by the parameter PE, would seem to be an exogenous behavioral parameter that Monty has to take as given. In fact, Monty has years of experience with contestants, and, therefore, has developed tricks with which to manipulate the contestants' behavior. For example, if Monty senses that Elaine's PE parameter value is below the optimal level (whose value we have not yet determined), then he can drive up PE by offering Elaine cash to switch. Similarly, Monty can lower PE by offering cash for not switching. We will therefore treat all three parameters PE, Pl3, and P2 as decision variables under Monty's control. It remains only to determine their optimal values.
Conclusion Why have so many people, including mathematicians, come to such different conclusions about the Monty Hall problem? One possibility is that the concept of conditional probability is poorly understood. Another explanation is that the precise game being played has not been articulated clearly. Careful gametheoretic modeling may help resolve the seemingly endless debate.
Acknowledgment Our thanks to our colleagues Jeff Witmer, Sam Goldberg, and Richard Salter for their helpful comments and suggestions.
REFERENCES
1. H. Scott Bierman and Luis Fernandez, Game Theory with Economic Applications, 2nd Edition, Addison-Wesley-Longman, Reading, MA, 1999.
2. Avinnash Dixit and Barry Nalebuff, Thinking Strategically: The Competitive Edge in Business, Politics, and Everyday Life, W. W. Norton and Company, New York, NY, 1991.
3. John Geanakoplos, David Pearce, and Ennio Stacchetti, Psychological games and sequential rationality, Games and Economic Behavior 1 (1991), 60-79.
4. Leonard Gillman, The 'car' and the `goats,' Amer. Math. Monthly 99 (1992), 3-7.
5. John Tierney, Behind Monty Hall's doors: puzzle, debate and answer, The New York Times (July 21, 1991), 1.
6. Marilyn vos Savant, Ask Marilyn, Parade, September 9, 1990.
7. Marilyn vos Savant, Ask Marilyn, Parade, December 2, 1990.
8. Marilyn vos Savant, Ask Marilyn, Parade, February 17, 1991.
