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:

- Don’t eat
- Eat
- Don’t eat
- Eat
- Don’t eat
- Eat
- Don’t eat
- Eat
- Don’t eat
- 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:

- Doesn’t eat
- Eats Meathead
- Doesn’t eat
- Doesn’t eat
- Doesn’t eat
- Doesn’t eat
- Doesn’t eat
- Doesn’t eat
- Doesn’t eat
- 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).

by Jim on August 31st, 2009 at 11:53

So the rules of the island preclude cannibal 1 from eating the sleeping cannibal 2? That seems strange.

by Austin Frakt on August 31st, 2009 at 13:39

@Jim – I know it is odd to think the dominant cannibal cannot just do what he likes. However, it is a logic puzzle. As such, the rules are not meant to accurately reflect cannibal society, about which I know nothing. In this strict sense, “strangeness” has no meaning.

by Bob on September 2nd, 2009 at 09:30

So if 8 eats, and 9 rejects eating 8 to avoid getting eaten by 10, then what stops 10 from eating 8 instead?

by Austin Frakt on September 2nd, 2009 at 09:52

@Bob – Only that it is against the rules. Cannibal n (other than n = 1) may only eat n-1. I confess I didn’t make this as clear as I could have in the original posting of the problem statement. It was quickly clarified in the comments to the post. I’ve since edited the original post to make it explicit.

by amesiana on July 8th, 2013 at 23:33

cannibal n can only eat n-1 but it does not apply to eating the meatballs?

if 2 decided to eat the meatballs, will it not make him the first one to eat the meatball? the only reason 1 decided not to eat the meatball is because he will be eaten by 2.. disregarding 1 in the original scenario.. lets make 2 number 1 from this point.. since he eat the meatball.. how can you justify that the one next to him will not eat him?

by amesiana on July 8th, 2013 at 23:52

the answer is.. if we only have 9 of them left disregarding 1 who decided not to eat.. we will arrive to this scenario:

1 eat

2 dont eat

3 eat

4 dont eat

5 eat

6 dont eat

7 eat

8 dont eat

9 eat

since 2 decided not to eat.. the rest cannot eat..

i guess the only confusing part is.. if 2 can eat,in the original problem.. so can 4 or 6 or 8 or 10?