Cannibal game theory – a cool math puzzle

I came across a really interesting game theory problem at David Cowan’s blog.

The problem not only is about strategy, but its proof is interesting mathematically too. Here is the puzzle:

A traveler gets lost on a deserted island and finds himself surrounded by a group of n cannibals.

Each cannibal wants to eat the traveler but, as each knows, there is a risk. A cannibal that attacks and eats the traveler would become tired and defenseless. After he eats, he would become an easy target for another cannibal (who would also become tired and defenseless after eating).

The cannibals are all hungry, but they cannot trust each other to cooperate. The cannibals happen to be well versed in game theory, so they will think before making a move.

Does the nearest cannibal, or any cannibal in the group, devour the lost traveler?

As usual, I have given a solution in the comments section.

Can you figure it out?

(Also, after writing this post I found the same puzzle appeared on the Incidental Economist with a nice explanation too)



Share this post:

| More

Previous post:

Next post:



  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    Answer to the puzzle

    I find the problem interesting because the solution uses two types of induction: the strategy depends on backwards induction, and the proof is based on mathematical induction.

    The short answer is the traveler’s fate depends on the parity of the group. If there is an odd number of canibals, the traveler will be eaten, but if there is an even number, the traveler will survive.

    To prove this, we will consider small groups and use mathematical induction to explain the solution for larger groups.

    Case n = 1: this is an obvious case. If there is one cannibal, the traveler will be eaten. It doesn’t matter that the cannibal will get tired because there are no other cannibals around as a threat.

    Case n = 2: this is a more interesting case. Each cannibal wishes to each the traveler, but each knows he cannot. If either cannibal eats the traveler, then he will become defenseless and the other one will eat him. So each cannibal uses backwards induction to realize that the only strategy is to not eat the traveler. The hapless traveler finds a bit of luck, therefore, and actually survives.

    Case n = 3: this is where the problem gets interesting. The best strategy is for the closest cannibal to make a move and eat the traveler. The cannibal will be defenseless after eating, but ultimately he will be safe. Why is that? The reasoning is due to induction: once the cannibal eats the traveler, the resulting situation has 2 unfed cannibals and the 1 defenseless cannibal. But as we just showed above, when there are 2 unfed cannibals, neither will make a move for fear of being eaten by the other! Thus the first cannibal to make a move will be safe as the remaining 2 cannibals block each other.

    We can prove the higher cases using mathematical induction. If the number n is odd, then the closest cannibal can safely eat the traveler because the remaining number of unfed cannibals is even (and by induction, with an even number of unfed cannibals no one makes a move). If the number n is even, then no cannibal will eat the traveler, for if he did, the remaining number of cannibals would be odd, meaning he will get eaten by the induction hypothesis.

  • http://www.mindyourdecisions.com/blog/ Presh Talwalkar

    I should point out this problem highlights one of the problems with game theory and backwards induction.

    If a group had 20 cannibals, the traveler would be safe. But if the group had 19, the traveler would die. That’s all fine in theory, but that’s a HUGE difference in outcomes for a detail like group size.

    What if some of the cannibals counted wrong, or if as the action took place another cannibal appeared to throw off the rational outcome?

    So unfortunately there are games that have mathematical elegance but shed light on how seemingly minor details can have profound effects on the game theory prediction.

  • Michael

    Sounds like the premise for an interesting movie… someone trapped on an island with cannibals, but for some reason none of them make a move. Then, just as the castaways is ready to relax, a new cannibal shows up and all hell breaks loose…

    Another thought… what if there are n cannibals and m travelers?

  • drobviousso

    Brilliant puzzle design. The traveler isn’t really a traveler. He’s an exhausted and defenseless cannibal, but if you tell us that, it’s easy to figure out the answer.

  • Sliquid

    what if there are 6 cannibals? the 5th eats the 6th, 4th the  5th and 3rd the 4th but the second wont eat the 3rd? i dont think it matter if its an odd or even number as long as there is more than 3 of them

Previous post:

Next post:

This site is for recreational and educational purposes only (privacy policy)

Powered by WordPress