A lady and a monster

Question

A famous problem:

A lady is in the center of the circular lake and a monster is on the boundary of the lake. The speed of the monster is $v_m$, and the speed of the swimming lady is $v_l$. The goal of the lady is to come to the ground without meeting the monster, and the goal of the monster is to meet the lady.

Under some conditions on $v_m,v_l$ the lady can always win. What if these conditions are not satisfied?

Edited: the monster cannot swim.

If the conditions are not satisfied, then monster can always perform a strategy such that the lady will not escape the lake. On the other hand this strategy is not desirable for both of them because they do not reach their goals.

As there was mentioned, this deals with undecidability of the problem. On the other hand, if you imagine yourself to be this lady/monster, you can be interested in the strategy which is not optimal. What is it? If there are such strategies in the game theory?

---

Edited2: My question is more general in fact. If we have a game with one parameter $v$ when two players $P_1, P_2$ are enemies and if $v>0$ then for any strategy of $P_2$ the player $P_1$ wins.

If $v\leq 0$ then for any strategy of $P_2$ there is a strategy of $P_1$ such that $P_2$ does not win and vice versa. I am interested in this case. From the mathematical point of view as I have understood the problem is undecidable since there is no an ultimate strategy neither for $P_1$ nor for $P_2$. But we are solving somehow these problem IRL.

Imagine that you are a lady in this game - then you would like to win anyway even while knowing that your strategy can be covered by the strategy of the monster. On the other hand, the monster knows that if he will cover all strategies of the lady she will never reach the shore and he will never catch her. I mean they have to develop some non-optimal strategies. I hope now it's more clear.

Answer 1

I was thinking about this problem and it seems to me that in a given formulation this game is somehow equaivalent to the following game.

If $v_m/v_l>k$ then on any action of the lady monster can either move (M) and follow her an catch her if she will come to the shore or stay (S) on the same place and wait (and thus let the lady run away). The lady also has to possibilities - either to move (M) and get out of the lake - or to stay (S) always inside the lake.

From these arguments it's easy to see that M is a dominating strategy for the monster (if we don't consider a penalty for the moving), hence it's optimal for the monster to follow the lady. Hence the lady on her side have to stay inside the lake.

For a pair (Lady, Monster) if $v_m/v_l>k$ there is a Nash equilibrium (Stay, Move).

Answer 2

I don't see that there is any game theory to be done here.

For the lady to have a winning strategy means that there exists a legal lady path $\gamma_l$, which reaches the shore, such that for all legal monster paths $\gamma_m$, a monster following path $\gamma_m$ does not catch the lady.

For any choice of $v_l$ and $v_m$, either the lady has a winning strategy or she doesn't, and it sounds like you know how to find out which is which. If she doesn't, then inverting the quantifiers, for every legal lady path which reaches the shore there exists a monster path which catches it. So in this case she cannot reach the shore without being caught.

However, the lady can always force a draw by not reaching the shore.

Answer 3

The monster can know if he can win or not at any time, likwise the lady.
They can't agree to enter a phase where the probability that either wins is something other than 0% or 100%.

If the lady can't win, so the monster won't win if she stays in the lake, they can toss a coin to determine her faith.

Answer 4

Since you seem to know the answer, I will give it here.

Suppose that $v_l = v_m / k $ and the radius of the lake is $r$. Then the lady can reach a distance $\frac{r}{k}$ from the centre and keep the monster directly behind her, a distance $r\left(1 + \frac{1}{k}\right)$ away. One way would be to swim in a spiral gradually edging outwards as the monster runs trying to close the distance; another would be to swim in a semi-circle of radius $\frac{r}{2k}$ away from the monster once it starts to run. And the lady can sustain this distance by going round in a circle as the monster tries in vain to close the distance.

The next stage is for the lady to try to swim direct to shore at some point away from the direction the monster is running. If the monster starts at the point $(-r,0)$ running anti-clockwise and the lady starts at the point $\left(\frac{r}{k},0\right)$ her best strategy is to head off in a straight line initially at right angles to the line between her and the monster: a less steep angle and the monster has proportionately less far to run than the lady has to swim, but a steeper angle and it is worth the monster changing direction. (If the monster changes direction in this right-angle case, the lady changes too but now starts closer to shore.) As they are both trying to get to the point $\left(\frac{r}{k},r \sqrt{1-\frac{1}{k^2}}\right)$ then they will arrive at the same time if $ \pi + \cos^{-1}(1/k) = k \sqrt{1 -1/k^2}$ which by numerical methods gives $k \approx 4.6033$.

So if the monster is less than 4.6033 times as fast as the lady, the lady can escape; if not then she stays in the lake and the monster stays on the edge and they live unhappily ever after.

Answer 5

edit: I corrected a silly mistake, now I get the same answer as Henry.

Let $k=v_m/v_l$. We can suppose $v_l=1$, hence $v_m=k$, and that the radius of the lake is 1. Let's reformulate the problem in this way: lady swims as before, but monster stands still and turns the lake with speed $\leq k$. The (vector) speed of the lady is a point in a disc of radius $1$, and the monster can control the center of the disc - he can move it from $0$ in the tangent direction by at most $kr$, where $r$ is the distance of the lady from the center.

If $r<1/k$ then $0$ is inside the disc, so the monster has no control over the direction of lady's movement. She can therefore get to $r=1/k$ to the point away from monster.

When $r>1/k$ then $0$ is no longer in the disc and the monster can force (by turning at full speed) the constraint $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (where $\phi$ is the angle of the position of the lady). The question is whether she can get from $r=1/k$, $\phi=0$, to $r=1$, $\phi<\pi$ ($r=1$, $\phi=\pi$ is the position of monster). This is possible iff $\int_{1/k}^1 \sqrt{k^2-r^{-2}}\, dr <\pi$.

edit: Here is why $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (it's a bit difficult to explain without a picture, but I'll try). The possible speeds of the lady form a disc with the center at $(0,kr)$ and with the radius $1$. The speed with the largest slope is the point of tangency from $0$ to the circle. Its slope can be seen from the right-angled triangle, with hypotenuse $kr$ and two other sides $1$ and $\sqrt{(kr)^2-1}$ - so the slope is $1/\sqrt{(kr)^2-1}$.