Una dama y un monstruo

Question

Un famoso problema: una señora está en el centro del lago circular y un monstruo que está en el límite del lago. La velocidad del monstruo es $v_m$, y la velocidad de la natación señora es $v_l$. El objetivo de la señora que va a venir a la tierra sin cumplir con el monstruo, y el objetivo de que el monstruo es atender a la señora.

Bajo algunas condiciones en $v_m,v_l$ la señora siempre se puede ganar. Lo que si estas condiciones no son satisfechas?

Editado: el monstruo no puede nadar.

Si las condiciones no son satisfechas, entonces el monstruo siempre puede realizar una estrategia para que la señora no se escape el lago. Por otro lado, esta estrategia no es deseable para ellos, ya que no alcanzan sus metas.

Como se había mencionado, se trata de una undecidability del problema. Por otro lado, si te imaginas como esta señora/monster, usted puede estar interesado en la estrategia que no es óptimo. ¿Qué es? Si existen tales estrategias en la teoría de juegos?

Edited2: Mi pregunta es más general en el hecho. Si tenemos un juego con un parámetro $v$ cuando dos jugadores de $P_1, P_2$ son enemigos y si $v>0$, entonces para cualquier estrategia de $P_2$ el jugador $P_1$ gana.

Si $v\leq 0$, entonces para cualquier estrategia de $P_2$ no es una estrategia de $P_1$ tal que $P_2$ no gana, y viceversa. Estoy interesado en este caso. Desde el punto de vista matemático, como tengo entendido, el problema es indecidible ya que no hay una estrategia fundamental ni para $P_1$ ni $P_2$. Pero nos van a resolver de alguna manera estos problemas IRL.

Imagínese que usted es una dama en este juego, a continuación, le gustaría ganar de todos modos, aun sabiendo que su estrategia puede ser cubierto por la estrategia del monstruo. Por otro lado, el monstruo sabe que si él va a cubrir todas las estrategias de la señora, ella nunca va a llegar a la orilla y él nunca va a cogerlo. Me refiero a los que tienen que desarrollar algunas no las estrategias óptimas. Espero que ahora es más clara.

Answer 1

Ya que parece que sabes la respuesta, voy a dar aquí.

Supongamos que $v_l = v_m / k $ y el radio del lago es $r$. Entonces la señora se puede llegar a una distancia de $\frac{r}{k}$ desde el centro y mantener el monstruo directamente detrás de ella, a una distancia $r\left(1 + \frac{1}{k}\right)$ distancia. Una forma sería la de nadar en una espiral en la que poco a poco bordes hacia el exterior como corre el monstruo tratando de cerrar la distancia; otro sería nadar en un semi-círculo de radio $\frac{r}{2k}$ lejos del monstruo una vez que se empieza a ejecutar. Y la señora puede mantener esta distancia por dar la vuelta en un círculo como el monstruo intenta en vano para cerrar la distancia.

La siguiente etapa es para la señora tratar de nadar directa a la orilla en algún punto alejado de la dirección en la que el monstruo se está ejecutando. Si el monstruo se inicia en el punto de $(-r,0)$ corriendo en sentido anti-horario y la señora se inicia en el punto de $\left(\frac{r}{k},0\right)$ su mejor estrategia es la de la cabeza en línea recta inicialmente en ángulos rectos a la línea entre ella y el monstruo: un menor ángulo pronunciado y el monstruo tiene proporcionalmente menos ahora que la señora tiene que nadar, pero un ángulo más pronunciado y vale la pena el monstruo de cambiar de dirección. (Si el monstruo que cambia de dirección en este ángulo recto caso, la señora cambia demasiado, pero ahora comienza cerca de la costa.) Como que están tratando de llegar al punto de $\left(\frac{r}{k},r \sqrt{1-\frac{1}{k^2}}\right)$ a continuación, se llegará a la misma hora si $ \pi + \cos^{-1}(1/k) = k \sqrt{1 -1/k^2}$ que por métodos numéricos da $k \approx 4.6033$.

Así que si el monstruo está a menos de 4.6033 veces tan rápido como el de la dama, la dama puede escapar; si no, entonces ella se queda en el lago y el monstruo se queda en el borde y viven, por desgracia, nunca después.

Answer 2

edit: he corregido un pequeño error, ahora tengo la misma respuesta como Henry.

Deje $k=v_m/v_l$. Podemos suponer $v_l=1$, por lo tanto $v_m=k$, y que el radio del lago es de 1. Vamos a reformular el problema de esta manera: la dama nada como antes, pero el monstruo se detiene y se convierte en el lago con velocidad de $\leq k$. El vector de velocidad de la señora es un punto en un disco de radio $1$, y el monstruo se puede controlar el centro del disco se puede mover de $0$ en la dirección de la tangente a la mayoría de los $kr$ donde $r$ es la distancia de la virgen desde el centro.

Si $r<1/k$ $0$ está dentro del disco, por lo que el monstruo no tiene ningún control sobre la dirección de la dama del movimiento. Ella puede, por lo tanto, a $r=1/k$ para el punto de distancia del monstruo.

Al $r>1/k$ $0$ ya no está en el disco y el monstruo de la fuerza (girando a toda velocidad) la restricción $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (donde $\phi$ es el ángulo de la posición de la señora). La pregunta es si ella puede obtener de $r=1/k$, $\phi=0$, a $r=1$, $\phi<\pi$ ($r=1$, $\phi=\pi$ es la posición de monstruo). Esto es posible iff $\int_{1/k}^1 \sqrt{k^2-r^{-2}}\, dr <\pi$.

edit: he Aquí el porqué $|dr/d\phi|\leq r/\sqrt{k^2r^2-1}$ (es un poco difícil de explicar sin una foto, pero voy a tratar). Las posibles velocidades de la señora formar un disco con el centro en $(0,kr)$ y con el radio de $1$. La velocidad con la mayor pendiente es el punto de tangencia de $0$ a del círculo. Su pendiente puede ser visto desde el ángulo recto de un triángulo, con la hipotenusa $kr$, y otras dos lados $1$ $\sqrt{(kr)^2-1}$ - por lo que la pendiente es $1/\sqrt{(kr)^2-1}$.

Answer 3

No veo que hay algún juego de la teoría a hacer aquí.

La señora tiene una estrategia ganadora significa que existe una legal señora path $\gamma_l$, que llega a la orilla, tal que para todo legal monstruo de las rutas de $\gamma_m$, un monstruo de la siguiente ruta de acceso $\gamma_m$ no captura la dama.

Para cualquier elección de $v_l$$v_m$, la señora tiene una estrategia ganadora o no, y parece que usted sabe cómo averiguar cual es cual. Si no lo hace, entonces la inversión de los cuantificadores, para cada jurídica señora camino que llega a la costa existe un monstruo en el camino que coge. Así que en este caso ella no puede llegar a la orilla sin ser atrapado.

Sin embargo, la señora siempre se puede forzar un empate por no llegar a la orilla.

Answer 4

El monstruo puede saber si él puede ganar o no, en cualquier momento, likwise la señora.
Ellos no pueden estar de acuerdo para entrar en una fase en la que la probabilidad de que cualquiera gana es algo distinto de 0% o 100%.

Si la señora no puede ganar, por lo que el monstruo no va a ganar si ella permanece en el lago, se puede tirar una moneda al aire para determinar su fe.

Answer 5

Yo estaba pensando acerca de este problema y me parece que en una determinada formulación de este juego es de alguna manera equaivalent para el siguiente juego.

Si $v_m/v_l>k$, a continuación, en cualquier acción de la dama monstruo puede mover (M) y seguir una captura si ella va a venir a la costa o estancia (S) en el mismo lugar y esperar (y por lo tanto vamos a la señora huir). La señora también tiene posibilidades, ya sea para mover (M) y salir del lago - o de estancia (S) siempre en el interior del lago.

A partir de estos argumentos es fácil ver que M es una estrategia dominante para el monstruo (si no consideramos una penalización para el movimiento), por lo tanto es óptimo para el monstruo a seguir a la señora. De ahí la señora a su lado tiene que permanecer en el interior del lago.

Un par (Señora, Monstruo) si $v_m/v_l>k$ no es un equilibrio de Nash (Estancia, Mover).