Analysis of the “Hierarchy of Hungry Cannibals” Game

Last week I posted a game theory problem I called “Hierarchy of Hungry Cannibals.” Though it is a simple idea the problem statement is long so I won’t re-post it here (go back and read it if you need to).

I think most people can put themselves in cannibal number 1’s shoes (or whatever) and make what seems to be the best choice. If cannibal 1 doesn’t eat Meathead he won’t fall asleep and he won’t be at risk of being eaten. That’s safe. In fact, every cannibal could make that choice. But, perhaps surprisingly, not all have to.

This is an iterative game. That is, the players (cannibals) do not all chose their strategy (eat or not eat) simultaneously. Each waits for his turn while other players (cannibals) make their moves. Cannibal 2 can’t decide what to do until cannibal 1 does so. 3 has to wait for 2, and so on.

There are two key ideas in solving iterative games. One, which applies to all problems in game theory, is to put yourself in the shoes (or whatever footwear) of each player (cannibal) in turn. The second key idea for iterative games is to start your analysis at the end of the game, with the choices of the last player to move. After thinking about the last move, work backward through the choices of the other players: cannibal 10, then 9, then 8, then 7, etc. This solution method is known as backward induction.

The last cannibal to make a decision is number 10. He has to wait until numbers 1, 2, …, 9 decide whether or not to eat, in turn. Since number 10 is the lowest in the hierarchy there is no cannibal below him who will eat him if he sleeps. He can eat without risk. Therefore, if given the chance, he eats.

Having figured out what cannibal number 10 will do, conditional on number 9’s choice, let’s work backward to cannibal number 9. He knows cannibal 10 will eat him for sure if he eats and sleeps (because as we argued above, cannibal 10 can eat risk free). So cannibal 9 will certainly not eat (and, so, not fall asleep), whether given the choice or not.

Now move back a step to cannibal 8. He knows cannibal 9 will certainly not eat him (he can’t or he’ll be eaten, as argued above). So cannibal 8 can eat risk free if given the chance, just like cannibal 10. So far we have determined that cannibal 10 will eat if given the option, cannibal 9 will not, and cannibal 8 will. We can continue the backward induction making the same arguments as above (exercise left to reader). What we will find is that the strategies the cannibals will adopt if given the choice are:

1. Don’t eat
2. Eat
3. Don’t eat
4. Eat
5. Don’t eat
6. Eat
7. Don’t eat
8. Eat
9. Don’t eat
10. Eat

So every even cannibal can eat without risk and will do so if the opportunity presents itself. Every odd cannibal cannot eat or he will be eaten. Thus, number 1 will pass on Meathead, and Number 2 will eat Meathead. Though number 2 will fall asleep, number 3 can’t eat number 2 or he will himself be eaten because that is the preferred strategy of number 4. Since number 4 isn’t given a chance to eat he can’t do so. The same goes for the rest of the cannibals 5, 6, 7, …, 10. None are given a chance to eat, even though some would if they could. That is, the final outcome is:

1. Doesn’t eat
2. Eats Meathead
3. Doesn’t eat
4. Doesn’t eat
5. Doesn’t eat
6. Doesn’t eat
7. Doesn’t eat
8. Doesn’t eat
9. Doesn’t eat
10. Doesn’t eat

Therefore one cannibal eats (number 2) and no others do, and all cannibals live (for today). My next post about this game will show how it is a (very) simple model of nuclear proliferation (far too simple, really).