• Hierarchy of Hungry Cannibals

    Here’s another fun problem the solution to which illustrates fundamental concepts in game theory. (Other game theory problems and posts are listed under the game theory tag.) This problem is not hard to grasp but it takes a lot of words to set it up:

    Ten cannibals live on an island. Their culture is very hierarchical and highly values rationality. To make the hierarchy explicit they’ve named themselves 1, 2, 3, …, 10. The order of the hierarchy corresponds to their number-name. Number 1 is dominant, 2 is second, and so on down to the lowly number 10.

    A week ago they ate the last humans on the island, and they aren’t interested in the other flora or fauna available. The cannibals are now very hungry.

    A moment ago a human named “Meathead” showed up, his sailboat having blown off course. Being the dominant cannibal, number 1 has the first option of eating Meathead. No other cannibal is permitted to touch Meathead before number 1 makes a decision as to whether or not he eats Meathead himself.

    If number 1 eats Meathead he will get drowsy and fall asleep. (We assume cannibals always sleep after eating and at no other time. So these cannibals are very tired, as well as hungry.) If number 1 eats and sleeps, the number 2 cannibal has an opportunity to eat the number 1 cannibal while his defenses are down. But if number 2 eats number 1 he himself will fall asleep and he may be prey to number 3, and so on to number 10. If a cannibal eats the next dominant one he risks being eaten himself by his immediate subordinate during his slumber.

    However, number 1 may choose not to eat Meathead. In that case, number 2 gets to make a decision about eating Meathead. If he eats Meathead he will sleep. If he sleeps he may get eaten by number 3 (and number 3 may then be eaten by number 4, and so forth). If number 2 passes on Meathead then number 3 gets a crack at Meathead…and so on.

    Just to be explicit, cannibal number n may only eat Meathead (if given the option) or eat cannibal number n-1 (and only if n-1 is asleep). Cannibal n is not permitted to eat any other cannibal.

    Number 1 gets the first move. What does he decide? What are the decisions of the other cannibals? Which cannibal, if any, eats Meathead? Which other cannibals, if any, eat? Which cannibals, if any, are eaten? Remember, these are rational cannibals. In fact, you can assume they all know the others are rational. (If you like, assume common knowledge of rationality.) That is, each will eat if (s)he can do so risk free. None will eat if it means certain death. I’ll post analysis on Monday and discuss an application in a subsequent post.

    • Do we assume that one cannibal can eat an entire person by himself?

      If so, then it would seem that if No. 1 eats, all will die except No. 10, who presumably would then eventually die of starvation. (although he would have about 1000 pounds of meat in his belly beforehand!)

      If not, then all can eat, and the only risk is to Meathead.

      Regardless of who it may be, eventually someone will eat, implying that in the long run all but one will be eaten. So it would seem that the smart strategy would be to be the last one left.. difficult since the individual cannot decide the order; it is up to the next-highest in hierarchy to decide that he will eat.

      I guess the best strategy would be to leave the game by becoming a vegetarian! But that’s probably not the answer you’re looking for.

      • @Bob Harnsberger – When a cannibal eats (whether Meathead or another cannibal) he eats the whole person. You’re right that if No. 1 eats then it will start a cascade of eating down to 10 who will live (since nobody can eat him). But that is not the way rational cannibals would act (other than no. 10).

        It is not the case that all can eat and live. While it may be true that someone can eat one of the tasks is to find who, if any that is. Is it only one cannibal or more? Which if any die?

        The order and rules are important. Cannibal n (other than n = 1) only has the option of eating n-1 if n-1 falls asleep (or can eat Meathead if given that option). Cannibal n has no other eating options. Also, cannibal n will only eat if he is not at risk of being eaten. He prefers to die by starvation than to die by being eaten.

        If you would like a hint send me a message (see Contact on the nav bar at the top of the page).

    • Yes, forgot the rule that they will only eat if there is no risk. When I stated that eventually someone will eat, I was not following the game rules. Thanks.

    • What confuses me is that if cannibal one declines to eat meatead and cannibal 2 does, that then cannibal 1 would be at highest hirarchy again and would have to redecide again, which kinda also muddles up the order meaning that number 1 could also survive.

      my guts personally are shouting at me saying: if you’re so rational then why not share? but that’s i guess not possible since they all eat one.

      other thought: if all cannibals refuse but cannibal 10 does cannibal 1 then decide again whether to eat cannibal 10?

      • @simone – Once cannibal 1 makes his decision about Meathead he has no further choices. Each cannibal makes one and only one decision to either (a) eat if given the opportunity or (b) not eat.

        The game is linear, not a circular. Cannibal 1 may only choose whether or not to eat Meathead. Every other cannibal n makes a decision whether or not to eat cannibal n-1 if given the chance. Once every cannibal makes his decision the game is over, with possibly some eating and some not, some eaten and some not.