Understanding the solution of a riddle about lions and sheep.

I heard a riddle once, which goes like this:

There are N lions and 1 sheep in a field. All the lions really want to eat the sheep, but the problem is that if a lion eats a sheep, it becomes a sheep. A lion would rather stay a lion than be eaten by another lion. (There is no other way for a lion to die than to become a sheep and then be eaten).

I was presented with this solution:

If there were 1 lion and 1 sheep, then the lion would simply eat the sheep.

If there were 2 lions and 1 sheep, then no lion would eat the sheep, because if one of them would, it would surely be eaten by the other lion afterwards.

If there were 3 lions, then one of the lions could safely eat the sheep, because it would turn in to the scenario with 2 lions, where no one can eat.

Continuing this argument, the conclusion is as follows:

If there is an even number of lions, then nothing happens.
If there is an odd number of lions, then any lion could safely eat the sheep.

But to me this seems utterly absurd. I think this is similar to the Unexpected Hanging Paradox (Link: http://en.wikipedia.org/wiki/Unexpected_hanging_paradox). I might have forgotten some assumptions, and those assumptions might actually solve this problem.

Is there a fault in the argument which I haven't discovered? Does anyone have any insights? Is the argument sound?

Solution 1:

Maybe you have doubts whether lions can count up to 101 or have the notion of odd and even. So here is another version of the story:

A certain university has just one math chair, which is inhabited right now. There are $N$ (male) mathematicians aspiring for that chair, and the guy who kills the prof becomes his successor.

Solution 2:

None of the answers posted here are actually fully correct.

Let us use the formulation of the problem as posted on the braingle website: http://www.braingle.com/brainteasers/teaser.php?id=9026&comm=0

The backward induction solution to the problem (where the sheep survives if the number of lions is even, and gets eaten if the number of lions is odd) can only be applied if lions have common knowledge of lion rationality. It is not enough for lions to just be "infinitely logical, smart, and completely aware of their surroundings". It is even not enough for lions to know that all other lions are rational! Common knowledge is much stronger than that, and means that everyone knows that everyone knows that everyone knows ... etc. etc.

Only then can we start applying backward induction! And the original problem formulation makes no such statement about common knowledge of rationality - which is a very strong statement to make!

Note that when I used the word "knowledge" above, I used a very strict definition of knowledge - knowledge is a true belief, which holds regardless of any new information becoming available.

Merely having common belief in rationality is not enough for a backward induction solution here! Imagine a situation with 4 lions: what happens if the 4th lion decides to eat the sheep, contrary to what the backward induction solution says he should do? This will invalidate the common belief of all the other lions in common rationality, which was the prerequisite for the backward induction solution! So lion 3 can no longer assume that lion 2 will never eat the sheep - after all, lion 4 just did! And since above all, lions do not want to be eaten, lion 3 will no longer eat the sheep. Turns out the behavior of lion 4 was rational after all, assuming lions did not have common knowledge in rationality at the start!

This explains why a lot of people feel unsatisfied with the backward induction solution to this problem, and why they feel that this problem is a paradox. They are completely right to be unsatisfied! Common knowledge in rationality is an extremely strong condition, and is unrealistic in most practical scenarios. And in fact in this problem, even common belief in rationality is not stated, merely the rationality of each individual lion, which completely invalidates the backward induction solution - even with only 2 lions, lion 2 cannot reason about what 1 lion would do if he doesn't hold a belief or knowledge of that lion's rationality (which cannot automatically be assumed)!

Solution 3:

The answer is you have missed an assumption at your question which you have brought it at your comments, "lions want to eat the sheep but not in cost of death". You have mentioned at your question that lions want to eat the sheep and if a lion eats the sheep, it will become the sheep himself and then it is in danger of being eaten and death. The argument you have brought after it is using the statement "A lion eat the sheep if and only if it won't die." and your argument currently is using the induction so the fault is not using induction or not, the fault is you didn't mention that is the key statement a fact or a guess.

Solution 4:

My guess is the Lion will think only in the short term.

Lion sees sheep, eats it, become one.
Lion sees sheep, eats it, become one.
Lion sees sheep, eats it, become one.
Lion sees sheep, eats it, become one.

Note that at any point in this process there is only one sheep in your arrangement.

~~If these lion agents are more cognizant, maybe they will notice their colleagues turning in to sheep and refrain. They seem to be indifferent about whether or not they are sheep?~~ From a game theory point of view, there is a slight Prisoner's Dilemma situation. The optimal strategy is unstable. If the lions do not fully cooperate, they all kill each other in succession.

If even one lion does not cooperate at any time, it renders the situation unstable for all lions.

I have been thinking about what happens if one of the lions temporarily leaves the room, and it becomes optimal to eat the sheep once. Then if the lion returns, and it becomes optimal for the sheep to be eaten again.

These propositions I make need proof, but I feel your solution has some instability. You might see this discussion in philosophy class, and I have pointed to Stanford's encyclopedia.

Solution 5:

Some insight comes from experimental game theory. What we find is that equilibrium solutions that should hold in theory and use induction often don't hold in practice. I think one reason that the theory doesn't correspond to the empirical evidence is because the induction argument is very hard to grasp when we are far away from the base case. One example, among many, is the Centipede game (http://en.wikipedia.org/wiki/Centipede_game) where the best response is always to defect and accept a small prize but in practice we always find that the players continue until near the final stages.