Monty Hall revisited

When Sasha Gnedin was interviewed for his position here, he had lunch with me and told me about his new take on the Monty Hall problem. It has now appeared here in the Mathematical Intelligencer.

To summarise briefly: you are a contestant on a game show, where the host, Monty Hall, shows you three doors. Behind one of the doors is a car, and the other two conceal goats. Assume that you really want to win the car, and have no use whatever for goats. Monty invites you to choose a door. He then opens a different door from the one you chose and reveals a goat; he asks you do you want to hold your original choice or switch to the third door. What should you do?

This is usually analysed as a problem in probability. Indeed, much of the misunderstanding arises from the assumption that, when one door has been opened, the car is equally likely to lie behind either of the other doors, so it doesn’t matter what you choose. I have previously quoted Einstein as saying,

In calculating entropy by molecular-theoretic methods, the word “probability” is often used in a sense differing from the way the word is defined in probability theory. In particular, “cases of equal probability” are often hypothetically stipulated when the theoretical methods employed are definite enough to permit a deduction rather than a stipulation.

In other words, don’t assume that outcomes are equally likely,
especially if you have enough information to show that they are not!

However, Sasha contends that probability doesn’t really come into it: this is a problem in game theory. The whole procedure is a very simple game with four moves. First (before the show), Monty chooses a door to conceal the car. Then you choose a door. Next, Monty chooses (if the option exists) which door to open. Finally, you choose whether to hold or switch.

What are all the possible strategies available to you and to Monty? A pure strategy is a rule telling a player what to do at each possible stage of the game. As von Neumann and Morgenstern observed, there are also mixed strategies, where a player choose at random among the pure strategies available. This will come in later, but for the first part of the analysis, only pure strategies arise; I will simply call them strategies.

Monty Hall has six possible strategies. Each can be described by a pair of distinct integers from the set {1,2,3}. Thus, for example, 32 means that Monty hides the car behind door 3; if you choose door 3, he opens door 2 rather than door 1. (If you choose a door other than 3, Monty’s move is forced; the strategy simply stores the information in case it is needed.)

You, the contestant, have twelve possible strategies. First you choose a door; then you have to know whether to hold or switch when Monty opens either of the other two doors. I will regard the doors as being circularly ordered for the purpose of writing down the strategy, so that if H and S denote “hold” and “switch”, the first letter refers to the next door in the circular order and the second to the last door. Thus, for example, strategy 2HS means “Choose door 2; if Monty opens door 3 then hold; if Monty opens door 1 then switch”.

Now the heart of Sasha’s proof that it is always better to switch is the following observation:

Any strategy A of the contestant which involves holding in any circumstance is dominated by another strategy B which switches in both cases, in the sense that, no matter what Monty does, the outcome of B is at least as good as the outcome of A.

To see this, we first observe that the “always switch” strategy 1SS loses if the car is behind door 1 and wins in all other cases. Now consider, for example, the strategy 2HS. This strategy only ever ends up with door 2 or door 3, and so it loses if the car is behind door 1 (and in another case as well, namely if the car is behind door 2 and Monty opens door 1). So it does worse than 1SS in all cases. The arguments for other strategies are almost identical.

So it is always better to switch, and nine of the twelve possible strategies for the contestant can be disregarded.

At this point one can reintroduce some classical game theory. If the game is a “zero-sum game” (in other words, if your gain in winning the car is Monty Hall’s loss), then the game is completely specified by the pay-off matrix (written with Monty’s strategies labelling columns and the contestant’s labelling rows)

	12	13	21	23	31	32
1SS	0	0	1	1	1	1
2SS	1	1	0	0	1	1
3SS	1	1	1	1	0	0

From this it can be shown that the contestant should adopt a mixed strategy by choosing the door at random with probability 1/3 and then always switching. It is also possible to discover the best mixed strategy for Monty Hall, as Sasha points out in the paper.

However, now (like Bob Dylan in the final stanza of “Black Diamond Bay”) let us step back and observe that we are really watching this on television. The contestant’s strategy is to win the car, but Monty Hall’s strategy is to increase the ratings for his show (if they fall too low, he will be out of a job). The way to do this may not be to try to defeat the contestant if at all possible. It may be that, the more prizes are given away (up to a point), the higher the ratings; so Monty may have some interest in the contestant winning from time to time. In this case, the analysis of mixed strategies falls down. If the contestant finds that Monty is dropping hints about where the car is, she may be best off to abandon her strategy and follow these hints!