The Man and the Lion Puzzle: Pursuit and Evasion Game Theory

http://mindyourdecisions.com/blog/2013/06/25/the-man-and-the-lion-puzzle-pursuit-and-evasion-game-theory/#.UerLUo2sjTo

by strategy • 13 years ago

37 9 13 years ago

eru• 13 years ago

Pretty nice post. I hope to be able to follow all the math tomorrow.

greatzebu• 13 years ago

I usually enjoy math problems that are motivated by some interesting real scenario like a man evading a lion, but in this case I don't think it works very well. You end up concluding that the man can evade the lion, but the solution only works if the man and the lion have zero volume and you don't mind getting arbitrarily close to the lion. So the math ends up being very much at odds with the physical scenario that's ostensibly motivating it. And this solution doesn't say anything about the possible existence of a solution that maintains a finite distance between the man and the lion, so you're left wondering whether or not a real solution might still exist. Still a neat technique, but the motivating scenario doesn't work for me.

Strilanc• 13 years ago

Note that it's assumed the man and the lion are points with no width. The lion doesn't have to get close to win, it has to be in the exact same position. This is mentioned near the end of the post (should be at the start).

If the lion only had to get close, it would clearly win by just continuously running directly towards the target. The curve it traced would cover less distance whenever the target was forced to turn, and so the lion can get arbitrarily close (assuming things like an instantaneous reaction time).

The important detail, that allows the man to escape when the positions must match exactly, is that the lion's tracing-smaller-curve advantage goes down as it gets closer. It has to match the turns being made by the man more and more exactly in order to not lose ground. Work out the result, and the corresponding infinite sequence fails to converge.

gizmo6862• 13 years ago

This solution seems like it has the man 'orbit' the lion, the same way that a planet travels perpendicular to the sun. The lions strategy is also running in a straight line to where the man is going to be, similar to how the sun accelerates to where the planet is.

There are a few obvious differences. The first being, in orbits, we (intuitively) use a time interval of 0. More importantly, in orbits, the sun is accelerating to the planets current position, not moving towards it. Formally speaking, I cannot see the connection between the stragety presented in the article and orbits, but intuitivly I feel like there is one.

wikkiwa• 13 years ago

There's actually a pretty fascinating branch of game theory devoted to these kinds of problems.

Differential game theory poses these situations as optimal control problems, with evaders and pursuers each having a separate control and opposite objective functions.

http://en.wikipedia.org/wiki/Differential_game

ultrafilter• 13 years ago

The man's escape strategy described in the post was discovered in 1952 by Besicovitch. It has a kind of discontinuity because, quoting the post, "There are 2 perpendicular paths. Choose the one closest to the center, or if the two paths are equally close, then either one is fine." In simple terms, the man will eventually make a wrong turn (with probability 1) unless he can instantaneously measure distances with perfect accuracy.

Surprisingly, for every continuous man strategy, there is a continuous lion strategy that can catch the man by time T where T is the disc radius divided by the lion's speed.

Restricting to continuous strategies in some other lion-man games actually leads to other paradoxes such as both lion and man having a "winning" strategy. The shallow resolution of the paradox is that two such winning strategy cannot actually be played against each other.

http://arxiv.org/abs/0909.2524

The deeper resolution is that even continuous strategies can be unphysical if they allow for information to travel at infinite speed (e.g., if the man is modelled as knowing the lion's current speed and velocity, special relativity notwithstanding). I'm not aware a proof in the literature, but presumably continuity of strategies plus an information speed limit will avoid the above paradoxes. (Continuous-time game theory is still very immature compared to discrete-time game theory.)

robotcookies• 13 years ago

I didn't (couldn't) go through all the math, but it would seem to me that the lion would get closer and closer to the man on each turn, while never touching (assuming points without width). Kind of like the graph where the line approaches zero without every reaching it.

gizmo6862• 13 years ago

That is correct. The distance gets 'very close' to zero very quickly, and gets arbitrarily close to zero given enough time.

tzs• 13 years ago

Another nice pursuit problem is the Homocidal Chauffeur problem. Pedestrian (slow but highly maneuverable) vs car (fast but limited maneuverability).

[1] http://en.wikipedia.org/wiki/Homicidal_chauffeur_problem

The Man and the Lion Puzzle: Pursuit and Evasion Game Theory

Related Stories