8 votos

Juego de escoger el número más cercano

Supongamos que tres jugadores juegan al siguiente juego: El jugador 1 elige un número en $[0,1]$ . Entonces el jugador $2$ elige un número en el mismo rango pero diferente del número del jugador $1$ elegido. Jugador $3$ también escoge un número en el mismo rango pero diferente a los dos anteriores. A continuación, elegimos un número al azar en $[0,1]$ uniformemente al azar. Quien tenga un número más cercano al número aleatorio que hemos elegido gana la partida. Supongamos que todos los jugadores juegan de forma óptima con el objetivo de maximizar su probabilidad de ganar. Si uno de ellos tiene varias opciones óptimas, elige una de ellas al azar.

1)Si el jugador 1 elige cero, ¿cuál es la mejor opción para el jugador 2?

2)¿Cuál es la mejor opción para el jugador 1?

Me cuesta ver que este problema esté bien definido. Por ejemplo, si el jugador $1$ elige $0$ y Jugador $2$ elige el 1, entonces no puedo ver cuál sería la elección óptima para el último jugador ya que tiene que elegir diferentes números. ¿Puede alguien ayudar?

EDIT: Ahora entiendo mejor cómo funciona el problema, pero sigo sin tener idea de cómo enfocar esto. ¿Puede alguien darme algunas pistas?

2 votos

Si el jugador 1 elige $0$ y el jugador 2 elige $1$ entonces no importa qué jugador 3 elija, tendrá un $50\%$ oportunidad de ganar el juego.

0 votos

Ya veo. ¿Pero qué pasa si el jugador 2 elige 0,5? Obviamente, el jugador 3 debería elegir algo más grande que 0,5 pero muy cercano a él, pero no veo cuál es el óptimo.

2 votos

Eso es cierto, no hay un único número "óptimo". Sin embargo, "elija un número realmente cercano, pero mayor que $0.5$ " sigue siendo en cierto sentido una descripción de una estrategia óptima.

5voto

Marksu Teoren Puntos 33

La primera parte. Que los tres jugadores elijan $x,y,z$ en orden. Supongamos que $x=0$ y considerar la elección del tercer jugador.

Opción A: Elija $z>y$ . Entonces la elección óptima es arbitrariamente cercana a $y$ para que la probabilidad de ganar se acerque arbitrariamente a $1-y$ . En este caso, la probabilidad de que el segundo jugador gane se aproxima arbitrariamente a (y es un poco mayor que) $y/2$ .

Opción B: Elija $z<y$ . La probabilidad de ganar es siempre $y/2$ por lo que la elección es un elemento aleatorio en $(0,y)$ . En este caso, la probabilidad de ganar del segundo jugador es $(1-y)+y/2=(1-y)/2$ . [La probabilidad de que el elemento aleatorio sea $\geq y$ ) $+$ (la probabilidad de que esté más cerca que $z$ a $y$ condicionada a que sea menor que $y$ ) $\times$ (probabilidad de que el número aleatorio sea menor que $y$ )].

El tercer jugador elegirá A si $1-y>y/2$ es decir, si $y<2/3$ y elegirá B si $y \geq 2/3$ .

Tanto si se hace elegir al tercer jugador la opción A como la B, podemos ver que la elección óptima de $y$ es $2/3$ .

La segunda parte. Se trata de una solución más intuitiva que analítica. Después de que los dos primeros jugadores hayan hecho su elección, la probabilidad máxima que puede obtener el tercer jugador está entre $x,(y-x)/2,1-y$ . Igualando los tres, obtenemos $x=1/4,y=3/4$ Así que ambos $1/4$ y $3/4$ debería ser óptimo para el primer jugador.

0 votos

¿Es el segunda parte ¿Generalizable para N+1 jugadores? Me estoy acercando a la teoría de juegos y he encontrado este ejercicio complicado. Si queremos que la elección del jugador N+1 sea indiferente deberíamos simplemente igualar todas las longitudes de los segmentos del intervalo, ¿no?

4voto

JiminyCricket Puntos 143

He pensado un poco más en esto y me he dado cuenta de por qué la pregunta está planteada así, en dos pasos. Podemos utilizar el primer caso para resolver el caso general de forma recursiva.

Como han establecido las respuestas existentes, la respuesta a la parte $1$ ) es $2/3$ y los pagos en este caso son $(\frac16,\frac12,\frac13$ ).

En el caso general, al jugar en $x_1$ Jugador $1$ crea efectivamente dos nuevos juegos a cada lado de $x_1$ uno reducido por $x_1$ y uno reducido por $1-x_1$ y estos subjuegos funcionan como el juego en parte $1$ ), ya que ambos están delimitados por una jugada del jugador $1$ en un extremo y un límite normal en el otro.

De nuevo, sin pérdida de generalidad, supongamos que $x_1\le\frac12$ . O bien los otros dos jugadores juegan en el mismo subjuego, o en subjuegos diferentes. Si juegan en el mismo subjuego, debe ser el más grande, de tamaño $1-x_1$ , ya que el jugador $3$ no jugaría en el partido menor si el jugador $2$ ya ha tocado allí. En $1)$ sabemos que en este caso los pagos son $(1-x_1)(\frac16,\frac12,\frac13)$ , además $x$ para el jugador $1$ que consigue en el otro lado, para un total de $(5x_1+1)/6$ para el jugador $1$ .

Jugador $3$ juega en el subjuego menor si el jugador $2$ ha jugado en el más grande y el pago $x_1-\epsilon$ en el subjuego más pequeño es mayor que el pago $\frac13(1-x_1)$ en el subjuego mayor, y por tanto si $x_1\gt\frac14$ . En este caso, el jugador $2$ jugaría en $1-x_1+\delta$ para disuadir al jugador $3$ de jugar en $x_2+\epsilon$ por lo que la recompensa para el jugador $1$ sería $\frac\epsilon2+\frac\delta2+\frac12((1-x_1)-x_1)=\frac\epsilon2+\frac\delta2+\frac12-x_1$ .

Jugador $2$ juega en el subjuego menor si el pago $x_1-\delta$ en el subjuego más pequeño es mayor que el pago $\frac12(1-x_1)$ en el subjuego mayor, y por tanto si $x_1\gt\frac13$ . Jugador $3$ jugaría entonces en $x_1+\epsilon$ . Esto dejaría al jugador $1$ con sólo $\frac\delta2+\frac\epsilon2$ para que evite este resultado.

Ya que en $x_1=\frac14$ ya tenemos $(5x_1+1)/6\gt\frac12-x_1$ , Jugador $1$ juega en $x_1=\frac14$ .

2voto

JiminyCricket Puntos 143

Dejemos que $x_1$ denota el número elegido por el jugador $i$ . Sea $x_\lt$ y $x_\gt$ sea el menor y el mayor de $x_1$ y $x_2$ . Además, utilizaré $\delta$ y $\epsilon$ para representar desplazamientos arbitrariamente pequeños.

Jugador $3$ escoge cualquiera de los dos $x_\lt-\epsilon$ o $x_\gt+\epsilon$ o cualquier número (no importa cuál) en $(x_<,x_>)$ . Los pagos para el jugador $3$ en estos casos son $x_\lt-\epsilon$ , $1-x_\gt-\epsilon$ y $(x_\gt-x_\lt)/2$ respectivamente, y elige el más grande entre estos tres. Nótese que en el tercer caso, la mitad del intervalo $[x_\lt,x_\gt]$ ese Jugador $3$ no gana va a Jugadores $1$ y $2$ en partes iguales (es decir, cada uno recibe un cuarto del intervalo), ya que en este caso Player $3$ elige uniformemente al azar dentro de ese intervalo.

Podemos suponer sin pérdida de generalidad que $x_1\le\frac12$ .

Supongamos primero que el jugador $2$ escoge un número por encima de $x_1$ . Entonces hay que distinguir dos casos.

Para los pequeños $x_1$ No pagará por el jugador $3$ para utilizar su primera opción. Entonces hay un límite para $x_2$ en la que el jugador $3$ cambia de su segunda a su tercera opción. Este es el movimiento óptimo para el jugador $2$ ya que jugar a cualquier lado de ella sólo cedería territorio. La condición para el jugador $3$ ser indiferente entre estas dos opciones es $1-x_2=(x_2-x_1)/2$ y por lo tanto $x_2=(x_1+2)/3$ . En este punto $x_2-x_1=(2-2x_1)/3$ . Si el jugador $3$ opta por su segunda opción, ese intervalo se reparte a partes iguales entre los Jugadores $1$ y $2$ , por lo que los pagos son $((2x_1+1)/3,(1-x_1)/3+\frac\epsilon2,(1-x_1)/3-\frac\epsilon2)$ ; mientras que si el jugador $3$ va por su tercera opción, ese intervalo se divide en proporciones $\frac14:\frac14:\frac24$ (ver arriba), por lo que los pagos son $((5x_1+1)/6,(1-x_1)/2,(1-x_1)/3)$ . En el punto de equilibrio, el $\epsilon$ la diferencia favorece al Jugador $3$ La tercera opción de la señora, en la que no pierde $\frac\epsilon2$ y como esto es favorable para el jugador $2$ (que recibe $(1-x_1)/2$ en lugar de $(1-x_1/3)$ ), Jugador $2$ puede jugar exactamente en el punto de equilibrio y no tiene que añadir un $\delta$ propia para inducir a Player $3$ para elegir su tercera opción.

Para los más grandes $x_1$ se convertirá en algo rentable para $x_3$ para cambiar a su primera opción. El punto de indiferencia para este cambio es $(1-x_1)/3=x_1$ o $x_1=\frac14$ . Para $x_1\gt\frac14$ , Jugador $2$ juega lo más cerca posible de Player $1$ sin dejar de forzar al jugador $3$ para usar su primera opción. El punto de indiferencia para esto es $x_2=1-x_1$ , pero Player $2$ tiene que jugar en $x_2=1-x_1+\delta$ para asegurarse de que el jugador $3$ utiliza su primera y no su segunda opción. Los resultados son entonces $((1-2x_1)/2+\frac\delta2+\frac\epsilon2,\frac12-\frac\delta2,x_1-\frac\epsilon2)$ .

Hemos comprobado que eligiendo un número superior a $x_1$ , Jugador $2$ consigue $\frac12-\frac\delta2$ si $x_1\gt\frac14$ y $(1-x_1)/2\ge\frac38$ si $x_1\le\frac14$ . Así que nunca pagará por el jugador $2$ para jugar a continuación $x_1$ y así hemos agotado todos los casos.

Para resumir: Si el jugador $1$ juega en $x_1\le\frac14$ , entonces Jugador $2$ juega en $x_2=(x_1+2)/3$ , Jugador $3$ utiliza su tercera opción, y los resultados son $((5x_1+1)/6,(1-x_1)/2,(1-x_1)/3)$ . Si el jugador 1 juega a $x_1\gt\frac14$ , entonces Jugador $2$ juega en $x_2=1-x_1+\delta$ , Jugador $3$ utiliza su primera opción, y los resultados son $((1-2x_1)/2+\frac\delta2+\frac\epsilon2,\frac12-\frac\delta2,x_1-\frac\epsilon2)$ .

En el primer caso, la recompensa para el jugador $1$ aumenta con $x_1$ y en el segundo caso disminuye con $x_1$ por lo que el máximo es alrededor de $\frac14$ . En el primer caso, se obtiene un resultado de $\frac38$ para el jugador $1$ mientras que en el segundo caso la recompensa no es superior a $\frac14$ . Así, el jugador $1$ elige $\frac14$ , Jugador $2$ elige $\frac34$ y Jugador $3$ utiliza su tercera opción, con los pagos esperados $(\frac38,\frac38,\frac14)$ .

0voto

Saurav Goyal Puntos 8

Dejemos que $x,y,z$ son las elecciones de los jugadores 1,2 y 3 respectivamente. Sea $a$ representan el número aleatorio nosotros elegir.

Función de mejor respuesta de $z$ dado que algunos $x=0$ y dado algunos $y$ :

La probabilidad de que el jugador 3 gane:

Caso: $z>y$ $$\int_{z}^{1} da\ +\ \int_{\frac{z+y}{2}}^{z}da$$ $$=1-z+z-\frac{z+y}{2}=1-\frac{z}{2}+\frac{y}{2}$$ Maximizando esto con respecto a $z$ el jugador 3 querrá que esté lo más cerca posible de $y$ como sea posible mientras sea mayor que $y$ .

Caso: $z<y$ $$\int_{\frac{z}{2}}^{\frac{y+z}{2}}da$$ $$=\frac{y+z}{2}-\frac{z}{2}=\frac{y}{2}$$

Así que si $1-y>\frac{y}{2}$ o $y<\frac{2}{3}$ el jugador 3 elegirá jugar $z>y$ (lo más cercano a $y$ como sea posible),

De lo contrario, el jugador 3 puede elegir cualquier $z<y$

Función de mejor respuesta de $y$ dado $x=0$ es:

La probabilidad de que el jugador 2 gane:

Caso: $y\leq\frac{2}{3}$ $$\int_{\frac{y}{2}}^{y}da=\frac{y}{2}$$

Caso: $y>\frac{2}{3}$ $$\int_{\frac{y+z}{2}}^{1}da=1-\frac{y}{2}-\frac{z}{2}$$

Así que $y=\frac{2}{3}$

0voto

Yubin Hu Puntos 1

Explicación intuitiva de la parte 2 (coincidiendo con la respuesta de @Aravind pero aportando más explicaciones):

Después de que los dos primeros jugadores hayan elegido sus posiciones, se fija la jugada óptima para el jugador 3. La línea se divide en 3 segmentos, cada uno con una recompensa máxima esperada para el jugador 3 de $p_1 = \frac{x}{2}$ , $p_2=\frac{y-x}{2}$ y $p_3=\frac{y}{2}$ , suponiendo que $0 \leq x \leq y \leq 1$ son las posiciones que eligieron las dos primeras personas. Y el jugador 3 va a elegir $$max\{p_1, p_2, p_3\}$$

Sin pérdida de generosidad, supongamos que el jugador 1 está en $x$ .

Desde la perspectiva del jugador 2 : Después de elegir su posición 2 tiene alguna ganancia original si 3 no existiera. Ahora incluye a 3 en el cuadro.

  • Si 3 elige $p_3$ , 2 pierde de su beneficio original todo lo que 3 gana.
  • Si 3 elige $p_2$ 2 pierde la mitad de lo que gana 3
  • Si 3 elige $p_1$ , 2 no pierde nada.

Como es probable que 3 pueda obtener alguna ganancia considerable (~1/3), que 3 "tome más del tazón de 2" es muy poco preferible para 2. Por lo tanto, en situaciones no muy extremas, 2 optimiza su propia ganancia en la restricción de que $$p_1 \geq p_2 \geq p_3$$

Por simetría entre 1 y 2 en la instancia que estamos viendo (cuando ambos han elegido posiciones y 3 no), sabemos que 1 optimiza su ganancia mientras espera que $$p_3 \geq p_2 \geq p_1$$

Esto es similar a un minimax situación, y la estrategia óptima para 1 satisfaría ambas desigualdades, dando $$p_1 = p_2 = p_3$$ $$\frac{x}{2} = \frac{y-x}{2} = \frac{y}{2}$$

Resolviéndolo obtenemos $x = 1/4$ , $y = 3/4$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X