Game Theory (Part 3) - Weak Dominance, Iterated Deletion and Common Knowledge

This is part 3 of my series on game theory. For an index, see here. The series follows the lectures of Ben Polak which are available on the Open Yale Courses website.

In the previous entry, we introduced some of the formal notation needed for game theory and used it to give a formal definition of the concept of strict dominance. In this entry, we continue by first examining the concept of weak dominance and by then exploring the iterated deletion of dominated strategies, as well as the concept of common knowledge.


1. The Hannibal Game
Hannibal Barca was a famous Carthaginian military commander and tactician. He is most renowned for marching an army, complete with war elephants, through the Pyrenees and the Alps into Northern Italy, during the Second Punic War. Following his arrival in Italy he won a number of notable victories over the Roman army.

His choice of invasion route is widely held-up as an example of shrewd military planning. But was it really that shrewd? We can’t provide a definitive analysis here, but we can construct a simple game theoretic model that provides some insight.

Here’s the set up: An invader is thinking of invading a country and there are two passes through which they can choose to invade. One of the passes is hard and one is easy (from the invader's perspective). The defender must defend but only has enough troops to defend one pass.

Payoffs in this game will be measured in terms of the number of battalions that the invader will arrive with (or are captured by the defender). There is a maximum of two battalions. Suppose that if both players choose the easy path, the defender can expect to win one battalion from the invader. Suppose that if both choose the hard pass, the defender will win both battalions. Finally, suppose that the hard pass is so difficult that even if the invader is unimpeded, he can expect to lose a battalion.

The following is the game matrix for this game:

If you were the defender in this game, what would you choose to do? Think about it for a moment or two and then come back to me....


What did you decide? It is suggested that you should choose to defend the easy pass even though it is not a strictly dominant strategy. Why do we make this suggestion? Well consider the following:

• (i) If you defend the easy pass, then the invader is indifferent between the easy pass and the hard pass. In other words, he could choose either since they both yield the same payoff for him.

• (ii) If you defend the hard pass, then the invader definitely prefers the easy pass.

Technically, what we say is that for the invader, the easy pass weakly dominates the hard pass. Which gives us the following definition:

Weak Dominance: Player i’s strategy Si* is weakly dominated by strategy Si if: 

• Ui (Si, S-i) ≥ Ui (Si*, S-i) for all S-i and; 

• Ui (Si, S-i) > Ui (Si*, S-i) for some S-i.

Clearly, this holds true for the invaders strategy e relative to strategy h.

According to this model, Hannibal’s decision to invade via the Alps seems irrational. But the model is only as good as the assumptions that go into it. In our case, we simplified massively from the original set of circumstances. In reality, it is likely that there were uncertainties about the payoffs associated with the different routes. These uncertainties could have made Hannibal’s decision more rational.


2. The Numbers Game
One of the key ideas in game theory is dominance solvability. This is when you solve a game through the iterated deletion of dominated strategies. Here’s a simple game that illustrates this phenomenon:

Suppose you are in a class of 50 students (the precise number doesn’t matter) and you are all asked to play the following game. You are given a sheet of paper on which you must write a number between 1 and 100. You are told that the average number for the class will be calculated and the person who writes the number that is closest to being 2/3 of that average will win a prize of some kind. Assuming you would like to win, what number should you write on the sheet of paper?

This game forces you to make use of one of the lessons from part one: namely, putting yourself in other people’s shoes, imagining what they are likely to do, and then determining your own strategy in response to your assumptions about the other player.

To solve the game, I suggest picking an expected average number (pretty much at random) and see whether writing a number that is two thirds of this average holds up to scrutiny. As follows:

• (1) If everyone were to write a number at random, then we might expect the average number in the class to be 50, thus if you wrote a number that was roughly two thirds of 50, you could expect to win. Therefore, you should write 33 or 34.

• (2) The problem is that people don’t choose at random. If they follow the same reasoning pattern as you do, then 33-34 would be the expected average. So you should write a number that is two thirds of this average, i.e. approx. 22.

• (3) But, of course, this reasoning process is available to all players, and if they follow it, then 22 would be the expected average. So you should write a number that is two thirds of this.

• (4) This reasoning process continues on and on until you reach the number 1.

What’s happening in this game? The answer: an iterated deletion of dominated strategies. To see this in more detail, start the analysis once again from scratch. Note that any number chosen above 67 is going to be weakly dominated by 67, so you can remove any number above 67 from the set of viable strategies. Once you do this, any number above 45 becomes weakly dominated and so must be removed from the set of viable strategies. This process of elimination continues until you reach the number one.

Of course, if you really did have to play this game, you should take into account how strategically savvy your opponents are.


3. Common Knowledge
The numbers game illustrates another important phenomenon in game theory: common knowledge. Two examples will help us to understand this phenomenon.

Consider first the following diagram. It depicts two people wearing pink hats. Person X can see that person Y is wearing a pink hat; person Y can see that person X is wearing a pink hat; but neither knows the colour of their own hat. In this case, the fact that both are wearing pink hats is not common knowledge, it is only mutual knowledge.

This example suggests that common knowledge is a pretty subtle thing. Formally, it is defined as follows:

Common Knowledge: Proposition P is common knowledge between X and Y, iff X knows P and Y knows P, X knows that Y knows P and Y knows that X knows P, X knows that Y knows that X knows P and so on ad infinitum.

Common knowledge is thought to underly much of social life and can create enormous problems. This is humorously illustrated by our second example: a famous scene from the movie The Princess Bride.