Friday, December 09, 2005

Lion Bait

For those who enjoyed the hand-shaking puzzle, here's a problem from the mid-term exam of my undergraduate Economics game-theory class...

A sheep sits in the middle of a field surrounded by n lions (where n is some number greater than 10). Any lion can eat the sheep but, as each lion knows, it would become so tired that it would be as defenseless as a sheep itself--easy prey for another hungry lion who would in turn become tired and defenseless. The lions are all hungry (equally so for lamb or lion meat), super rational, but naturally not suicidal. Does the nearest lion, or any lion for that matter, pounce on the tasty ovine?

The solution to this puzzle illustrates a point that I will reference in my next post. Eventually, I really will show some relevance to venture capital (beyond the obvious metaphor of nasty lions devouring poor helpless lambs).

Meanwhile, be the "first person on the blog" to post the correct answer (a simple yes or no without proof will not suffice)!

49 comments:

  1. Anonymous7:20 PM

    None pounces.


    Each lion is better off not pouncing, regardless of the actions of each other lion. Hence, all will wait.

    ReplyDelete
  2. I think I'm missing something, but on first pass...

    For the parameters of the puzzle to work, all lions must survive (not being suicidal) and one will have eaten or not eaten. Any other solution means that some lion chose to 'eat' knowing that he would, himself, be consumed.

    Since all lions want to "eat" the first lion to get to the sheep can eat. Any lion attacking that lion would himself be consumed so it would be possible to eat and be left alone. The only "special" cases are the first lion, and the last lion. The 'first' lion is counting on the self preservation of the rest to avoid being eaten. I can think of no way to gurantee being last, but you could be first by getting there first.

    Therefore I say the nearest lion will definitely pounce on the sheep.

    The n>10 part is throwing me though, so I think I'm missing something.

    ReplyDelete
  3. Anonymous7:47 PM

    I assumed that 1 sheep was surrounded by N identical lions, N > 1. I also do not see why the specific value of N matters.

    If a lion is dumb enough to pounce, he simply becomes the sheep for the next round, and the payoff matrix is the same.

    Consider the two-lion case:

    Pounce Chill
    Pounce -5, -5 -10, 5

    Chill 5, -10 0, 0

    Clearly, each lion will chill.

    ReplyDelete
  4. Anonymous8:02 PM

    Grrr. So much for showing the payoff matrix.

    Imagine tabs in the right places :^)

    ReplyDelete
  5. So far, these answers do not qualify as correct. To simply say that the sheep doesn't get eaten, or that one lion eats and the rest stop, ignores a potential lion strategy of figuring that if no one (else) is going to eat the sheep, then I might as well eat it, since, logically, no would then eat me either!

    MikePK, I think your answer might have worked if I hadn't since clarified, post initial posting, that when a lion eats another lion it, too, becomes tired and helpless.

    ReplyDelete
  6. Anonymous1:10 AM

    mikepk, should the nearest lion eat the sheep, the next-nearest lion would eat the first, for the same reasons. should a lion eat the sheep, he becomes the sheep in the same problem with n' = n - 1.

    Perhaps the lions would share the sheep?

    ReplyDelete
  7. Anonymous7:32 AM

    The algorithm to wait and not pounce until someone else pouces is suicidal - they all will starve.

    Hence, the algorithm shall be to pounce. Now, the question is when. Clearly, timing calculated with relation to the distance the prey. The closer the distance, the longer the wait, with the goal to arrive at the sheep at the same time as others. For the farthest lion the time is 0 (pounce immediately), the nearest one waits the longest.

    The situation where two or more lions arrive at the target simultaneously is not defined, but assuming that this is possible, there will be a big fight and hopefully the strongest will survive. From a VC point of view, at least there is a chance to feed...

    So, if the answer is pounce after waiting t(n)=(Dist(N-1)-Dist(n))/S, where N is the number of lions, n runs from 0 to (N-1), and S is speed of a lion

    Assumptions:
    all lions have same speed
    all lions programmed to identical behaviour
    every lion knows its and and all others' distance from the prey
    lions do not know the relative strengths of each other
    situation where all arrive at the prey simultaneously leads to a fight and survival of the fittest.

    ReplyDelete
  8. MN,
    No, I specifically referred to the "nearest lion" in order to avoid any talk about sharing or fighting (the economics teacher hadn't found this necessary). And the lions won't necessarily starve if they pass on lunch--they can always leave the field and hunt for food elsewhere.
    You will see that the answer (like in the handshaking puzzle) is purely logical and requires none of the assumptions you make (other than that the lions think and therefore behave identically).
    David

    ReplyDelete
  9. The solution is based on the number of lions in the circle - if it's odd or even.

    Start with the most basic - if there is one lion and one lamb the lamb get's eaten - there is no threat of him being devoured after getting a little tired. If there are two lions and one lamb the lamb is safe because the act of devouring the lamb puts the first lion to react at risk of being eaten.

    Now extend that to three lions. One lion will eat the lamb and the other two will look at each other and realize that they don't want to be eaten by the other so the new "lamb" in the middle is now safe (and not as hungry!).

    This can then be extended to any n quantity of lions.

    ReplyDelete
  10. Anonymous8:16 AM

    @Rob:

    Nice. The payoff matrix depends on the value of N mod 2! I would not have seen that in a million years.

    Now, if this had been framed as a *voting* game...

    ReplyDelete
  11. Darn,
    I circled in on this answer and didn't quite get there. I drew a diagram where I had the following assumptions

    For a lion to act in round x he mustn't be threatened in round x+1
    for a lion to threaten the 'prey' in round x he must be able to act in round x

    I even had an alternating act-no/act diagram, but I didn't take that to it's logical conclusion. I had assumed there must be one correct answer.

    Good work Rob. Gah, I need to get back to work. :)

    ReplyDelete
  12. Anonymous8:48 AM

    I think the super-rational lion wanders off to find a gazelle, leaving his venture capitalist friends to starve while trying to decide if the lamb market is hot.

    ReplyDelete
  13. the best question is what in the world am i doing sitting on a beautiful (but chilly!) Saturday morning reading my RSS feeds and solving logic problems when my holiday shopping isn't even done yet!!

    ReplyDelete
  14. Anonymous9:40 AM

    Well, if walking away is an option for any lion, then the nearest lion in odd-lions situation is not safe from being eaten and therefore shouldn't jump...

    Say, there are three lions and the nearest one makes a decision to pounce and feed on the sheep. What are the two remaining unfed beasts to do? If, as David suggests, they have an option to leave and hunt elsewhere, one (say, farthest from the prey) would immediately leave and the other would feed on the weak lion.

    ReplyDelete
  15. Anonymous9:52 AM

    ...which makes me think that since the lions are super-rational, and they know that the only safe bet for the nearest (or any for that matter) lion to feed is to wait until all other leave, all other than the nearest shall leave immediately to feed elsewhere, and then the nearest one feeds.

    The assumption here is that all lions are on different distance from the prey.

    ReplyDelete
  16. Anonymous12:07 PM

    Wow...yet again I would be deeply troubled by using this as an indicator of future talent as a VC or technology investor. Putting this in a real life context, Rob's answer for 1 = fine, but there's no way on Earth 3 or 5 [or any odd N] would result in the same outcome.

    If there were 11 lions of equivalent strength, speed, hunger and logic...absolutely no way would one opt to take the "risk" as he would KNOW he would be killed, much like the two sitting together would opt out.

    Being on a game theory exam, I'm not surprised by the question. However, I would worry that if a student answered this with the "right" answer, they were too much of an automaton and not capable of examining the real-life factors that play in making any difficult decision.

    Any lion that has reasonable access to alternative food would in no way, shape or form step into that circle and eat the sheep with another 10+ lions waiting to pounce on him.

    ReplyDelete
  17. Jason,
    Settle down--you are the first to say anything about using this puzzle this as an indicator of VC skills. However it is a great test of game theory skills, which is what it was designed for. Whether or not you could solve it, there is indeed value in recursive logic (computers are more predictable than people and lions).
    But you are right that super-rational lions are more theoretical than practical. While not the solution of this puzzle, that is indeed the point of it, which leads to my next blog post, tomorrow, on the limits of purely rational economics...
    David

    ReplyDelete
  18. Anonymous2:41 PM

    David,

    You're right in that I extended this exercise into the context of our last conversation which did relate to using logic puzzles as an evaluation tool in the hiring process. My apologies for making the leap there. In the interim, I look forward to your rational economics post.

    Kind regards,

    Jason

    ReplyDelete
  19. Anonymous7:53 PM

    Clearly, the lions will share the snack.

    ReplyDelete
  20. Anonymous7:55 PM

    And to expound further, the first rule of games is that if the rules don't favour you, change the rules.

    --
    :) MG

    ReplyDelete
  21. Anonymous11:08 AM

    Am I missing something? Rob said "the solution is based on the number of lions in the circle - if it's odd or even."
    But his example only show why 2 lions produce a different result from 3 or more lions.
    I thought the answer is the closest lion should pounce as long as there are at least 2 lions remaining.

    ReplyDelete
  22. Dylan,

    Consider that if there are 3 lions, the closest lion will pounce because with 2 lions left he's safe. Therefore with 4 lions no one would pounce, since 3 would be left, and 3 is unstable. Therefore with 5 lions left the closest will pounce since then there will be 4 left, which is safe. Etc...

    Mark,

    You are right but you are also wrong. Indeed, all rational lions must think alike. The solution to the puzzle assumes that in fact they do. If there is an odd number of lions, the closest one will pounce knowing that others will back off because they too understand the decision tree.

    Look, everyone, this is a logic problem. It's not meant to be a serious training session for sheep. Obviously lions aren't super-rational. I assure you that not a single student in the class pontificated about lion psychology--we simply applied game theory, as this puzzle was meant to allow. Drone on, if you will, about our lack of "imagination" or "jungle smarts", but in the process you might as well dismiss every theoretical branch of math and science.

    ReplyDelete
  23. Anonymous1:02 PM

    Rob, I'm impressed.

    Eventually, however, the super-rational lions would become super-engorged lions, and the marginal benefit of eating a nasty hulking cannibalistic lion would no longer exceed the marginal cost of the monster hairballs. We see this in the world of mergers & acquisitions -- the market always turns.

    Besides, what if some of those rational lions are vegetarians? That's not lion psychology, that's hard lion veterinary nutrition!

    ReplyDelete
  24. Anonymous9:31 PM

    If all the lions think identically, that would mean that just like the first lion, the rest of the lions will also simultaneously realise that should there be an odd number of lions, the nearest will pounce, at which point the rest pretty much don't stand any chance (as suggested by the actual answer), so the option of walking off and hunting other prey becomes the only choice they have of getting any lunch, and since the lions are all assumed to be identical in thought and super rational, they will all walk off in search of other prey at the exact same moment, but the fact that they are super rational (again), they will all also know that if this happens then the prey would be theirs if they stayed behind while the rest take their leave, but since all of them are identical in thinking, the result is that all of them will end up staying put, but if all of them stay put, then the option of walking off for other prey will be the logical option, and the loop goes on and on.

    Since the lions are all super rational, they will not act before arriving at the best answer, but since the answer cannot be found as demonstrated above, the lions' brains hang as they get caught in the infinite loop trying to reach for the answer. This answer assumes that the sheep in question is somehow a superior lunch when compared to other prey in other fields, because if other prey in other fields are equal in reward, then the lions will realise that the sheep causes a loop in logic that will result in no action taken, and they will all just head off and hunt other prey because that way, they all get the reward of lunch without putting any of themselves at risk.

    ReplyDelete
  25. Anonymous3:07 PM

    the sheep will eat the nearest lion

    ReplyDelete
  26. Anonymous8:42 AM

    The lion will transport the sheep to a safe local and eat him in privacy.

    ReplyDelete
  27. Crap, i had the solution when i read the original comment.

    It seems to me like the sheep is going to live a long time, hahhahaha

    ReplyDelete
  28. Anonymous2:54 PM

    First, in reality, the lion wouldn't become all that tired by eating a sheep, and lions don't eat other lions (as far as I know), and lions aren't super-rational. They are often hungry. But my answer is yes. A lion(ess) pounces on the sheep, because she knows that the energy gained from eating the sheep will likely outweigh, or at least be equal to, the energy spent eating it. Being at least as strong or stronger than the starving, and thus weakened, lions surrounding her, she will be able to strike successfully at them too and will end up fat as a pig by the end of her n lion slaughter.

    ReplyDelete
  29. Anonymous12:16 AM

    What if there were two sheep?

    ReplyDelete
  30. This is interesting artcile.
    I hope you will post the explanation is future.
    I am Arindam. I am Communication egineer working as program director in a large telecom company in India.
    I assist people in money management as economics and financial engineering is my favourite subject
    Arindam ( www.nectarofwisdom.com)

    ReplyDelete
  31. Anonymous,

    Two sheep--I like that twist. If a lion can eat both sheep at once, it's the same problem as before so I presume that in your variation, each lion can eat one sheep before growing tired. But to apply game theory, we need to understand the rules--with a tired lion and a sheep to choose from, which would a hungry lion eat? Is it random? If n=2, could the two lions effectively safely split the two sheep up (that's quite an assumption)? This assumption directly impacts the answer...

    If it's random as to which prey dies, then it's not a stretch to say that with n=2, the sheep don't get eaten because lions wouldn't eat if it meant a 50% chance of dying in the jaws of the other. In that case, the answer remains the same as before--a sheep gets eaten if n is odd, but under no circumstances do both sheep get eaten!

    But if the lions even slightly prefer mutton to cannibalism, then that precisely flips the answer, so that for n greater than 2, one sheep gets eaten if n is even, but again the second sheep is always safe. (For n<=2 the formula doesn't apply--all lions will eat all available sheep.)

    Thank you for the stimulating variation. But now we must endure the torrent of posts on feline and bovine psychology...

    ReplyDelete
  32. Anonymous6:46 PM

    Don't know how i got here, but lions aren't cannibals, nor can they count. Why don't you use entities that make sense for your example, like people and parking spaces?

    ReplyDelete
  33. I believe Rob's solution is too limited, even if you only use logic to solve the puzzle.

    Suppose there are an even number of lions. The sheep is safe, and every lion knows it (since they're all super-rational and excellent at using recursive logic).

    However, a logical lion could also kill another lion *first*, thus creating an odd number of lions. Then it would be free to eat the sheep. I don't believe the puzzle's rules explicitly forbid this.

    Of course, if all the lions realized this simultaneously, it could either produce a bloodbath, or a dead standstill where no one moves.

    However, the puzzle's rules did not stipulate that all the lions think at the same speed. Therefore, given an even number of lions, the super-rational lion who thinks the fastest would kill another lion and then eat the sheep. Or, assuming he has no preference for bovine over feline meat, he may just eat another lion and leave the sheep to graze in peace.

    If the idea is to solve the puzzle using only logic and the rules provided in the puzzle itself, then this scenario is impossible to ignore.

    ReplyDelete
  34. Bapudi,

    Your scenario does not apply. I think you must have missed this sentence when your read the problem:

    "Any lion can eat the sheep but, as each lion knows, it would become so tired that it would be as defenseless as a sheep itself--easy prey for another hungry lion..."

    The lions become tired and defenseless only after eating the huge meal.

    Thanks,
    David

    ReplyDelete
  35. Anonymous9:26 AM

    Many of you people are colossal nerds, but I say so with utmost admiration as I can only sniff at such intellectual calisthenics. I am now hooked on this blog after stumbling across it in a random moment of boredom.

    Jeff - Calgary

    ReplyDelete
  36. Anonymous10:50 PM

    Ok, I'm fascinated but confused... and almost a month late on this topic (but I just found your blog so cut me some slack).

    You say that if there are two lions neither will eat the lamb because they fear being eaten (therefore fear of being eaten is stronger than their hunger). Why does this change with 3 lions? The first lion to pounce would surely know he would be killed just as he did when there was only 2 right?

    So why are lions only suicidal when they travel in odd numbers?

    Seems to me the lions that are able to form the largest power block to defeat the other lions and get the sheep will be the ones to survive (assuming there is no other source of food). But that's probably going outside the rules of the game.

    ReplyDelete
  37. Cisco

    If there are 3 lions, the nearest will in fact pounce, secure in the knowledge that now, effectively, n=2. With only two lions left, the tired lion is safe. That is, the condition of two hungry lions and one defenseless animal (be it feline or bovine) is stable, but 3 hungry lions is not. 4 hungry lions is therefore stable (no one wants to be the defenseless animal in the unstable situation of 3 hungry lions). And so 5 is unstable, and 6 is stable...

    ReplyDelete
  38. Anonymous4:02 PM

    Ok... I think I understand now. The assumption is that not only are the lions equal in being superlogical, but they are also each aware that the other lions are all equal and superlogical (and therefor super-predictable).

    Ok, thanks for the explanation. I'll have to read about game theory. Sounds interresting.

    ReplyDelete
  39. David,
    No, I didn't miss that statement, and my scenario does not ignore it. Allow me to explain.

    You stated a good summary of Rob's solution in your last post:
    "....the condition of two hungry lions and one defenseless animal (be it feline or bovine) is stable, but 3 hungry lions is not. 4 hungry lions is therefore stable (no one wants to be the defenseless animal in the unstable situation of 3 hungry lions)."

    Here is what I am proposing: suppose there are 4 lions. The condition is stable, and all the lions know it. No one can touch that sheep.

    Knowing this, one lion could kill another lion and NOT EAT IT. Now there are *only 3 hungry lions*, an unstable number. Now one of the 3 remaining lions can eat the sheep with perfect impunity. After he eats the sheep, he will be defenseless, but there will only be 2 hungry lions left, and neither one will dare attack him.

    Also, since the puzzle explicitly makes lion and lamb meat equivalent, a lion could totally ignore the sheep, and eat the dead lion. Either way, after he has eaten, there are only two hungry lions left, and he's safe.

    To state it another way, what Rob has missed is that a super-rational lion could undertake to CHANGE THE NUMBER OF LIONS PRESENT by commiting felicide.

    In other words, an even number of lions can be made into an odd number of lions by lion murder.

    If all the lions realized this scenario at the same time, they could potentially all try to kill each other at once (a bloodbath). Or, if they all realized the potential for bloodbath, it may be that none of them move (paralysis).

    An interesting problem, to be sure.

    ReplyDelete
  40. I re-read my initial comment, as well as your response to it, and I am puzzled.

    I didn't miss that sentence in the puzzle, and I can't figure out how it seems that I did.

    Maybe I have been unclear. I'll try to map out more clearly what I am saying:

    Starting state: 4 hungry lions, 1 sheep = stable (no one gets eaten)

    Action: One lion kills another lion.

    New State: Three hungry lions and one sheep = unstable

    Action: The murdering lion eats the sheep (or the dead lion).

    New State: 1 defenseless lion, 2 hungry lions (and possibly a sheep, depending on whether the lion eats the sheep or the dead lion) = stable. The full, defenseless lion is safe.

    ReplyDelete
  41. Bapudi,

    You are introducing a new assumption when you say that even though the lions are the same, one can confidently kill another even though the vicitm is NOT tired and defenseless. There is a reason that in the problem statement lions are said to be defenseless only AFTER eating an animal. Prior, they can defend themseleves quite well, and trying to kill one isn't advisable.

    David

    ReplyDelete
  42. Ah, yes, that's true. :)

    I assumed that the other lions would be thinking so hard, it wouldn't be difficult to slip a quick paw under someone's chin and slit their throat.

    MAN, this is a violent math problem, huh?

    I'm always trying to break things. Would you be so kind as to let me try again?

    Suppose an even number of lions. One lion could walk away from the situation, leaving behind an odd number. Then, one of the lions who is left would eat the lamb, ensured of his safety. The first lion could, after waiting a reasonable amount of time behind the nearest baobab tree, come back and have an excellent meal of lion stuffed with lamb.

    Of course, the other lions, being super-rational, might guess what he's up to, and not fall for the trick.

    What do you think?

    Are you getting tired of this puzzle? I'll stop if you are.

    ReplyDelete
  43. Anonymous1:50 AM

    I blogged about these and other puzzles today. Thanks for my resurgent interest in logic games.

    ReplyDelete
  44. I know this is a old post but wanted to add this...
    The first lion doesn't want to risk being eaten so he walks away after some time, the second does the same and the third and so on the Nth lion gets to eat the lamb as it needn't worry about being eaten. Good things come to those who wait in lion (sorry)!

    ReplyDelete
  45. Anonymous11:15 AM

    Peace, they are not threatened by one another they feel calm and comfortable and in this particular interaction they feel no need or desire to feed.

    Good example of what it is to just be.

    Friends yet one prey and one a carnivore .... we tend to look at the evil that the world portrays aka the NEWS but rarely are we aware that with all the evil in this world there is just as much good to go along with it!!

    Yin~Yang baby....this is hot ....love it!

    ReplyDelete
  46. Anonymous2:48 PM

    the lion is pretecting the sheep. Like how even though God could tear us up and torture us he dosent/ Because he loves us

    ReplyDelete
  47. I just found out this blog.
    This puzzle was actually asked to during my Oxford Interview in 2006.

    ReplyDelete