¿La forma más rápida de encontrarse, sin comunicación, en una esfera?

Question

Me desconcertó una pregunta que me hizo mi colega, y ahora busco su ayuda.

Supón que tú y tu amigo* acabáis en una gran esfera. No hay señales visuales sobre el lugar de la esfera en el que os encontráis, y la esfera es mucho más grande que vosotros dos. No hay medios de comunicación. Puedes determinar tu posición relativa y tu dirección navegando por las estrellas**. Puedes moverte a cualquier lugar, y tu amigo también.

Al inspeccionar la esfera, ves que es sólida como una roca, por lo que no puedes crear marcas. Para proteger el medio ambiente, no puedes dejar otras cosas, como un rastro de sangre o migas de pan.

Te han puesto en la esfera sin ser capaz de comunicar un plan.

¿Cómo podríais encontraros (acercaros a cierta distancia $\epsilon$ ?) ¿Cuál sería la estrategia óptima para moverse?

*Puesto que estás aquí, debes ser una persona racional. Para este rompecabezas asumimos que tu amigo es racional también.. _{Lo que hace que sea impar que termines en esa esfera de todos modos}

**Aunque puedes determinar tu posición relativamente, estás en una esfera en una galaxia tan lejana que no puedes determinar el "norte", el "sur", etc. absolutos por las estrellas.

Answer 1

Muévete al azar.

Cualquier estrategia determinista que elijas tiene la posibilidad de que tu compañero elija la estrategia exactamente opuesta, por lo que acabáis avanzando por caminos más o menos antípodas y nunca os encontráis. Así que hay que evitar las estrategias deterministas.

Podrías hacer algunos ajustes en tu estrategia aleatoria. Por ejemplo, podrías preferir caminar distancias más largas en línea recta en lugar de elegir una dirección completamente nueva tras cada centímetro de movimiento. Dependiendo de lo que haga tu compañero, algo de eso podría mejorar las cosas. Pero para juzgar con precisión si lo hace, necesitarías algún modelo probabilístico de qué plan es probable que elija tu compañero, y acertar con eso equivaldría más o menos a un plan preacordado. Así que ni siquiera puedes conocer la distribución de probabilidad de los planes de tu compañero, por lo que no puedes comparar cuantitativamente las estrategias entre sí.

Answer 2

En cuanto a "Te han puesto en la esfera sin ser capaz de comunicar un plan". Voy a suponer que no puedes ni siquiera suponer el plan que tu compañero puede llegar a tener y que no hay colaboración previa.

Dada la potencial naturaleza simétrica del problema, debe haber un elemento aleatorio que rompa esa simetría, en caso de que ambos elijan accidentalmente estrategias espejo. El problema es que no hay garantía de que tu amigo seleccione una estrategia óptima, sin embargo, si tu amigo es inteligente y/o exhaustivo, se dará cuenta de dos cosas:

1. Si los dos se mueven, las posibilidades de cruzarse pueden ser nulas si los patrones no se solapan.
2. Si uno de vosotros se queda quieto, el otro puede acabar encontrándolo con una búsqueda exhaustiva.

Así que lo primero que hay que hacer es calcular el tamaño de la esfera (eligiendo una dirección y caminando hasta llegar al punto de partida o alguna otra técnica más eficiente). En ese momento, puedes elaborar un patrón de búsqueda exhaustivo y la duración para realizarlo (un patrón en espiral es casi óptimo, pero difícil de realizar para un humano). Esa duración se convierte en la frecuencia de la toma de decisiones.

Una vez por período, se lanza una moneda. Si sale cara, se hace una búsqueda exhaustiva. Si sale cara, te quedas quieto. Cada uno de los periodos más largos (por ejemplo, el patrón de búsqueda menos eficiente), tienes un 50/50 de posibilidades de hacer lo contrario que tu compañero y así descubrirte en el transcurso de la búsqueda exhaustiva.

Hay dos casos extremos que están cubiertos por este enfoque. Si tu pareja decide no moverse nunca, obviamente se encontrará en tu primera búsqueda exhaustiva. Si decide moverse permanentemente, ya sea de forma aleatoria o según algún patrón, siempre existe la posibilidad de encontrarlo accidentalmente durante tus barridos de búsqueda, en los que tienes que confiar si no está siendo exhaustivo y su movimiento no cubre tu punto de "permanencia". De lo contrario, cuando te quedas quieto te garantizas que acabarán encontrándote.

Answer 3

Moverse en espirales como esta:

_{(fuente: <a href="http://forum.cad.de/foren/ubb/uploads/Markus.g/Kugel_spirale.jpg" rel="nofollow noreferrer">foro.cad.de </a>)}

donde la distancia entre los brazos espirales es $2\epsilon$ .

Supongo que tienes una medida de la distancia en tu esfera, si no, no podrías determinar la condición ganadora.

Answer 4

Aquí hay algunos puntos.

1. Aquí me parece un poco redundante hablar de estrategias, porque se trata más bien de juego estático con información completa que un juego dinámico .

   En primer lugar, supongo que para usted esto es un juego con información completa . Para hacerlo de forma más explícita, simplemente tenemos que añadir a su frase "No hay señales visuales sobre el lugar de la esfera en el que os encontráis, y la esfera es mucho más grande que vosotros dos. No hay medios de comunicación. Puedes determinar tu posición y dirección navegando por las estrellas. Puedes moverte a cualquier parte, y tu amigo también". las palabras "Los dos saben esto, los dos saben que los dos saben esto, y así sucesivamente".

   Entonces, el juego es estático porque el elemento temporal no es realmente relevante. Eliges una acción, tu amigo otra, y eso es todo, porque realmente no puedes cambiar lo que estás haciendo teniendo en cuenta lo que está haciendo tu amigo , teniendo en cuenta que usted no tiene acceso a esa información. Por lo tanto, podemos deshacernos del término "estrategia", que en los juegos estáticos con información completa se reduce al término " acción ".

2. Ahora bien, ¿alguna de tus acciones está dominada (es decir, podrías realizar una acción que te diera una mayor recompensa, independientemente de lo que haga tu amigo)? La verdad es que no. Por lo tanto, básicamente todas tus acciones pueden ser racionalizado por alguna conjetura de su amigo. Por supuesto, debido a la naturaleza simétrica del juego, lo mismo se aplica a usted.

3. ¿Tiene el juego una solución? Pues sí, depende del criterio de solución que pienses, y también de cómo lo concibas. Por ejemplo, OMI el juego tiene un Equilibrio de Nash obvio (por favor, ten en cuenta que no soy astrónomo de cohetes...): tú y tu amigo vais hacia el norte, hasta que ambos podáis encontrar con alguna estimación aproximada que estáis en el polo norte de vuestra esfera, y entonces esperáis que el otro aparezca. Deberíais acabar en algún $\varepsilon$ distancia entre ellos. Nótese que aquí estoy asumiendo la interpretación del Equilibrio de Nash como un acuerdo que se refuerza a sí mismo. Nótese también, que este perfil de acción debería corresponder en un equilibrio objetivo correlacionado, donde el dispositivo objetivo es aproximadamente la estrella polar.

P.D.: Por supuesto, todo el punto detrás de los puntos (2) y (3) es para definir exactamente lo que crees que significa "óptimo" aquí (algo que siempre es problemático). Un punto adicional es que estoy asumiendo que para coordinar, los jugadores necesitan tener algún punto de referencia objetivo (polo norte - estrella polar).

Answer 5

Como has incluido en el enunciado del problema estrellas tales que pueden ser navegadas, esto significa que al menos una única "configuración" de posiciones estelares es visible desde cualquier punto de la esfera.

A partir de esto, plantearía que una solución mejor que la aleatoria incluiría encontrar la configuración más "interesante" de este tipo (por lo que primero hay que mapearlas todas recorriendo la esfera metódicamente) y dirigirse hacia ella como punto de Schelling. Si el nivel de confianza en que una configuración determinada actúe como punto de Schelling para el otro jugador es insuficiente, se podría elaborar una estrategia que distribuya aleatoriamente el tiempo empleado en cada punto de interés en función del tamaño de la esfera, ϵ, y el nivel de confianza en lo "interesante" de cada punto.

Por ejemplo, un punto de Schelling "por defecto" para dos jugadores que piensan como yo sería buscar la configuración estelar única con el menor número de estrellas componentes. O, para decirlo de otra manera para un cielo como el de la Tierra, la constelación reconocible formada por la menor cantidad de estrellas -- o posiblemente la estrella más brillante del cielo, si hay una suficientemente más brillante que las demás.