Pregunta de entrevista sobre Teoría de juegos / Probabilidad

Question

Recibí esto para una entrevista y no lo entendí. ¿Cómo lo resuelvo?

Tú y tu oponente tienen un muestreador aleatorio uniforme de 0 a 1. Ambos tomamos muestras de nuestras propias máquinas. Quien tenga el número más alto gana. La trampa es que cuando ves tu número, puedes tomar otra muestra. El oponente puede tomar otra muestra una vez, pero tú puedes tomar otra muestra dos veces. ¿Cuál es la probabilidad de que gane?

Mi enfoque no muy seguro: Para cada jugador, se crea una estrategia basada en la idea de "si este número es demasiado bajo, tomar otra muestra". Sabes que para mí, tengo tres muestras, y el valor esperado de la tercera muestra es 1/2. Entonces, para la segunda muestra, si es menor de 1/2, deberías tomar otra muestra; si es mayor de 1/2, no tomes otra muestra. Y haces lo mismo para la primera muestra con un umbral ligeramente más alto. Y luego asumiendo que nuestro jugador es el oponente, seguirán el mismo enfoque, pero solo tienen dos lanzamientos.

De cualquier manera, sabemos que el juego puede terminar con seis resultados: puede terminar conmigo terminando en la primera, segunda o tercera muestra, y ellos terminando en el primer o segundo resultado. Simplemente condicionamos cada uno de esos seis casos y encontramos la probabilidad de que mi lanzamiento sea mayor que el de ellos en esa distribución uniforme condicional.

Answer 1

Primero, proponemos un método para calcular la mejor respuesta para una cierta política del oponente.

Por ejemplo, suponiendo que el oponente juega con una política de umbral con umbral = 1/2. Con una sola muestra, tengo una probabilidad de ganar de 3/8. Por lo tanto, en la segunda ronda, solo volveré a muestrear si mi probabilidad de ganar es menor que 3/8. Podemos calcular que el umbral es 7/12. Luego puedo calcular la probabilidad de ganar condicional si vuelvo a muestrear en la primera ronda, suponiendo que sea $1/2+a$. Luego puedo usar este valor de manera similar para determinar mi umbral para la primera ronda.

Con esta idea, si ambos jugadores pueden volver a muestrear una vez, entonces se puede calcular que el equilibrio de Nash de estrategia pura único es $(x_1,x_2)=(\frac{\sqrt{5}-1}{2},\frac{\sqrt{5}-1}{2})$, donde $x_1$ y $x_2$ son los umbrales de los dos jugadores. De manera similar, se puede calcular un equilibrio de Nash de estrategia pura para el problema original, pero será bastante complicado.

Answer 2

Mis cálculos no son iguales a los de los demás, así que comparemos.

Si los relanzamientos del Jugador 1 son cuando $x_1$ y $x_2$, y el relanzamiento del Jugador 2 es cuando $y_1$ o menos, pienso (asumiendo $x_2 \le y_1\le x_1$) que la probabilidad de que el Jugador 2 gane es

$$\int_0^{x_2} y_1(x_1x_2y)\, dy \\+\int_{x_2}^{y_1} y_1(x_1x_2y+x_1y- x_1x_2)\, dy \\+ \int_{y_1}^{x_1} (y_1+1)(x_1x_2y+x_1y- x_1x_2)\, dy \\+ \int_{x_1}^1 (y_1+1)(x_1x_2y+x_1y- x_1x_2+y-x_1)\, dy$$ dando

$$p_2=\tfrac12(1-x_1x_2y_1^2-x_1y_1^2+x_1x_2^2y_1+x_1x_2y_1+x_1^2y_1-x_1y_1+y_1-x_1x_2+x_1^2-x_1)$$ y $p_1=1-p_2$. Entonces pienso que las derivadas son cero cuando

• $\frac{dp_1}{dx_2}=0 \implies x_2= \frac{y_1^2-y_1+1}{2y_1}$ y
• $\frac{dp_1}{dx_1}=0 \implies x_1=\frac{\left( x_2+1\right) {{y_1}^{2}}+\left( -{{x_2}^{2}}-x_2+1\right) y_1+x_2+1}{2 (y_1+1)}$ y
• $\frac{dp_2}{dy_1}=0 \implies y_1=\frac{x_1 {{x_2}^{2}}+x_1 x_2+{{x_1}^{2}}-x_1+1}{2 x_1 (x_2+1)}$

así que tres ecuaciones simultáneas no lineales con tres incógnitas y la solución de $(x_1,x_2,y_1) \approx (0.697910,0.593225,0.651477)$ dando $p_1 \approx 0.576461$ y $p_2 \approx 0.423539$.

Comparemos esto con una simulación (usando la misma semilla para reproducibilidad):

firstplayerwins <- function(x1,x2,y1){
  x <- runif(1)
  if (x < x1){x <- runif(1)}
  if (x < x2){x <- runif(1)}
  y <- runif(1)
  if (y < y1){y <- runif(1)}
  return(x > y)
  }

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.697910, 0.593225, 0.651477))
c(mean(sims), mean(!sims))
# 0.57728 0.42272

así que cerca, teniendo en cuenta el ruido de la simulación.

La respuesta de AnCars parece sugerir el uso de $(\frac23,\frac12,\frac12)$ (como también lo hace Paul Smith) lo cual da

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(2/3, 1/2, 1/2))
c(mean(sims), mean(!sims))
# 0.58361 0.41639

lo cual es peor para el segundo jugador, pero el Jugador 2 cambiando $y_1$ mejorarían la probabilidad $p_2$ (en este caso óptimamente en $c=\frac{23}{36}\approx 0.6389$)

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(2/3, 1/2, 23/36))
c(mean(sims), mean(!sims))
# 0.574 0.426

aunque entonces el Jugador 1 podría cambiar $x_1$ y $x_2$, y así sucesivamente hasta llegar a la solución de derivada cero.

Harish Vemuri sugiere $(0.69,0.55,0.74)$ lo cual nuevamente da una ventaja al Jugador 1

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.69, 0.55, 0.74))
c(mean(sims), mean(!sims))
# 0.58287 0.41713

y nuevamente cambiando $y_1$ mejorarían la probabilidad para el Jugador 2

set.seed(2023)
sims <- replicate(10^5, firstplayerwins(0.69, 0.55, 0.62976))
c(mean(sims), mean(!sims))
# 0.57578 0.42422 

De hecho, podemos utilizar las consecuencias de las derivadas cero para iterar hacia la solución de equilibrio:

iterated <- function(x1, x2, y1, rounds=20){
  for (n in 1:rounds){
    x1[n+1] <- ((x2[n]+1)*y1[n]^2 + (-x2[n]^2-x2[n]+1)*y1[n] + x2[n] + 1) / 
               (2*(y1[n]+1))
    x2[n+1] <- (y1[n]^2 - y1[n] + 1) / (2*y1[n])
    y1[n+1] <- (x1[n]*x2[n]^2 + x1[n]*x2[n] + x1[n]^2 - x1[n] + 1) / 
               (2*x1[n]*(x2[n]+1))
    }
  print(cbind(x1,x2,y1))
  }

iterated(2/3, 1/2, 1/2)

dando (a pesar de un pequeño desliz en $x_2$ al principio y luego en $y_1$)

             x1        x2        y1
 [1,] 0.6666667 0.5000000 0.5000000
 [2,] 0.6666667 0.7500000 0.6388889
 [3,] 0.6909134 0.6020531 0.7083333
 [4,] 0.7115098 0.5600490 0.6562810
 [5,] 0.6988111 0.5900093 0.6380170
 [6,] 0.6949647 0.6026866 0.6502897
 [7,] 0.6976317 0.5940330 0.6550889
 [8,] 0.6987173 0.5907996 0.6517936
 [9,] 0.6979795 0.5930108 0.6505392
[10,] 0.6977016 0.5938628 0.6513951
[11,] 0.6978917 0.5932808 0.6517233
[12,] 0.6979648 0.5930584 0.6514990
[13,] 0.6979149 0.5932104 0.6514132
[14,] 0.6978958 0.5932686 0.6514718
[15,] 0.6979088 0.5932288 0.6514943
[16,] 0.6979138 0.5932136 0.6514789
[17,] 0.6979104 0.5932240 0.6514730
[18,] 0.6979091 0.5932280 0.6514771
[19,] 0.6979100 0.5932253 0.6514786
[20,] 0.6979104 0.5932242 0.6514775
[21,] 0.6979101 0.5932249 0.6514771

Answer 3

Consulte la respuesta de AnCar.

Cada jugador intenta maximizar su propia puntuación. Supongamos que tienes $n$ lanzamientos. Lo más que puedes esperar de estos $n$ lanzamientos es terminar con una puntuación mayor a $1 - 1/2^n$ con una probabilidad de $1/2$ (asumiendo que simplemente pueden elegir el máximo de sus lanzamientos). La dificultad radica en que, en cada punto, te quedas con lo que fue tu último lanzamiento y sabes cuántos lanzamientos te quedan. Entonces, supongamos que estás en tu lanzamiento número $k$ del juego y obtuviste un lanzamiento de $\alpha \in [0,1]$. Puedes esperar, con una probabilidad de $1/2$, obtener una puntuación mayor a $1 - 1/2^{n - (k - 1)}$ con tus restantes $n - k$ lanzamientos. Así que, solo deberías lanzar de nuevo si $\alpha < 1 - 1/2^{n - (k - 1)}$. Suponiendo que esta estrategia es óptima, podemos calcular el valor esperado (puntuación promedio) al jugar con esta estrategia. Hay una probabilidad de $1/2^n$ de que obtengas una puntuación mayor a $1 - 1/2^n$ en tu primer lanzamiento. Hay una probabilidad de $1/2^{n - 1}$ de que obtengas una puntuación mayor a $1 - 1/2^{n - 1}$ en tu segundo lanzamiento. Y así sucesivamente. $$E(\text{puntuación}) = \frac{1 - 1/2^n}{2^n} + \frac{1 - 1/2^{n - 1}}{2^{n - 1}} + \cdots + \frac{1 - 1/2^2}{2^2} + \frac{1 - 1/2^1}{2^1}$$ Pongamos todo esto bajo un denominador común: $$\begin{align*} E(\text{puntuación}) &= \frac{2^0(1 - 1/2^n) + 2^1(1 - 1/2^{n - 1}) + \cdots + 2^{n - 2}(1 - 1/2^2) + 2^{n - 1}(1 - 1/2^1)}{2^n} \\ &= \frac{(2^0 + 2^1 + \cdots + 2^{n - 2} + 2^{n - 1}) - (\overbrace{1/2^n + 1/2^n + \cdots + 1/2^n}^{n \text{ veces}})}{2^n} \\ &= \frac{(2^n - 1) - n/2^n}{2^n} \\ &= 1 - \frac{1 + n/2^n}{2^n} \\ &= 1 - \frac{1}{2^n} - \frac{n}{2^{2n}}. \end{align*}$$ Ten en cuenta que todo esto es especulación. No estoy seguro de si la estrategia que he seleccionado es óptima. Por favor, señala una estrategia mejor si encuentras una. En el contexto de este problema. Esto haría que la puntuación esperada del primer jugador (el que tiene tres lanzamientos) sea de aproximadamente $0.828$ y la puntuación esperada del segundo jugador (el de dos lanzamientos) sea de $0.625$. Estos valores son algo esperados: $0.828$ es ligeramente menor que $1 - 2^3 = 0.875$ y $0.625$ es ligeramente menor que $1 - 2^2 = 0.75$.

Esto aún no responde a la pregunta de la probabilidad de que el primer jugador gane. Solo hemos mostrado que el primer jugador ganará más a menudo. Puede que piense más sobre el problema, pero esto es todo lo que tengo que decir por ahora.

Answer 4

Con un lanzamiento, las probabilidades de obtener 1/2 o mejor son del 50/50. Con dos lanzamientos, las probabilidades de obtener 2/3 o mejor son del 50/50. Para maximizar mi lanzamiento, Si mi primer lanzamiento es menor que 2/3, vuelvo a lanzar. Si mi segundo lanzamiento es menor que 1/2, vuelvo a lanzar.

Mi oponente solo tiene un lanzamiento para mejorar, debería volver a lanzar si obtiene menos de 1/2. Así que las probabilidades de que yo gane son del 50/50 más las probabilidades de obtener entre 1/2 y 2/3 en mi primer lanzamiento, que son de 1/6. Espero ganar cuatro juegos de seis.

---- Editar para la respuesta de Henry Henry tiene la respuesta más correcta hasta ahora, ¿pero crees que podrías llegar a ella en una entrevista? Forcé una optimización utilizando el algoritmo de Henry y los resultados me sorprendieron. Fue muy difícil obtener un mejor escenario por encima del 60% y aún más difícil encontrar un peor escenario por debajo del 55%.