Adivina el número más pequeño

Question

Tres personas juegan a un juego en el que cada una de ellas escribe un número entero positivo al mismo tiempo. El que escribe un número único y más pequeño gana un dólar de cada una de las otras personas. Esto significa que si dos personas escriben por casualidad el mismo número, el tercero recibe un dólar de cada una de ellas. Ahora bien, ¿qué número pondrías tú si tuvieras que jugar a este juego?

Answer 1

Este es un problema de Teoría de juegos. Aclaración: El enunciado del problema parece implicar que si todos 3 seleccione el mismo número, a continuación, el dinero no cambia de manos. Voy a suponer que.

Henry ha llegado con la solución. La siguiente es la justificación.

El objetivo es maximizar el jugador del beneficio esperado. Cada jugador actúa de forma independiente de los demás. Este problema es un caso especial de uno que fue resuelto en el período 2007-2008. Se llama Menos la Única Oferta de la Subasta. Hace unos 10 años una promoción especial fue utilizado en Europa. "Subastados" fuera de un elemento, por ejemplo un $\$100$ bill. The special rules: You can make a sealed bid in multiples of a unit (assume a dollar). The winning bidder is the one with the smallest unique bid out of $n$ players. The person with the winning bid must also pay his bid amount. So a winning bid of $\$b$ tiene un $\$$100 a-b de lucro. El problema que se plantea aquí es mucho más sencillo, ya que la ganancia no depende de que el valor de mi oferta (sólo su tamaño relativo en comparación con otras ofertas.)

No es pura estrategia de equilibrio de Nash para el plantea un problema. Esto significa que cuando cada jugador elige un número fijo. Si todos los tres pick número 1, por ejemplo, cualquier jugador prefiere (después del hecho) para elegir el número 2 (con otros usuarios de picking 1) y que ganar todo el tiempo. Esto significa que todos los 1 no es un equilibrio, ya que no todos los jugadores están satisfechos con el status quo. Así que en lugar de buscar una estrategia mixta equilibrio de Nash (NE). Así que queremos elegir una distribución de probabilidad sobre las elecciones 1,2,3...

Nos damos cuenta de que no importa qué número tenemos que elegir nosotros siempre ganamos. Es decir, el ganador de la rentabilidad es una constante $\$2$ rather than $\$100$-b en el caso general. Por lo tanto, nuestro comportamiento debe ser "el mismo" en cada número posible opción ya que el problema es el mismo. (Esto puede ser hecho preciso el uso de un estado de absorción de la cadena de Markov.) Esto requiere un poco de explicación.

Cada jugador especifica su distribución de probabilidad. A continuación, un árbitro (o el subastador) pueden utilizar las distribuciones para generar una "oferta". Si la distribución es $p_1,p_2,...$ para uno de los jugadores, a continuación, lanzamos una moneda con probabilidad de $p_1$ de los jefes. Si cae de cabeza, podemos seleccionar el número 1. Pero si las colas, no se selecciona 1 y espere a la siguiente ronda. Si el juego continúa hasta después de la número 1 (dependiendo de las otras opciones) podemos entonces decidir si para seleccionar el número 2. $p_2/(1-p_1)$ es la probabilidad de seleccionar 2 dado que yo no seleccionar 1. Desde nuestro comentario anterior, esta probabilidad debe ser el mismo que $p_1.$ por lo Tanto,

$$ p_1=\frac{p_2}{1-p_1} \text{ or } p_2=p_1(1-p_1)$$

Podemos seguir esta lógica a la conclusión de que la distribución debe ser geométrico. Así que cuando se busca una estrategia mixta NE podemos limitarnos a distribuciones geométricas. Esto es enorme simplificación. (A la hora de resolver el problema general en el 2007, no me doy cuenta de que este caso especial del problema permite una para restringir la búsqueda de un NE geométrica de las distribuciones. Sólo me di cuenta de que el día de hoy.)

Deje que las distribuciones para el jugador a, B y C se indican: $$ a(1-a)^{k-1}, b(1-b)^{k-1}, c(1-c)^{k-1}. $$

Vamos a hallar la probabilidad de que el jugador a gana en juegos decididos con la primera licitación: $ a(1-b)(1-c)+(1-a)bc. $ El primer término es el caso cuando Un jugador hace una selección de 1 y B y C no, mientras que el segundo término es para el caso de que él no elige 1, pero tanto B y C sí. Además, existe una probabilidad de $g:=(1-a)(1-b)(1-c)$ que nadie elige 1 y el juego continúa hasta la ronda 2. Como se mencionó anteriormente, el juego es idéntico a partir de esa etapa de avance. Por lo tanto, la probabilidad de que el jugador a gana a la oferta de $k$: $[a(1-b)(1-c)+(1-a)bc]g^{k-1}.$ por lo Tanto las probabilidades de ganar para todo el juego son: $$ P(A)=\frac{a(1-b)(1-c)+(1-a)bc}{1-g} $$

$$ P(B)=\frac{(1-a)b(1-c)+a(1-b)c}{1-g} $$

$$ P(C)=\frac{(1-a)(1-b)c+ab(1-c)}{1-g} $$

Suponemos que jugador C. queremos maximizar nuestro beneficio esperado. Nos gustaría encontrar una $symmetric$ estrategia mixta NE, es decir, con $a=b=c.$ Esto es debido a que todos los jugadores son equivalentes y es difícil justificar acciones diferentes en equilibrio. Podemos empezar por asumir que nuestros rivales han seleccionado $a=b.$, Entonces si podemos elegir cualquier valor de $c$ nuestro beneficio esperado es de $ E(C)= 2P(C)-2P(A).$, Entonces, después de algunos álgebra: $$ \frac{\partial E( C )}{\partial c}=\frac {2(1-2a)[1-(1-a)^3]} {[1-(1-a)^2(1-c)]^2} $$

Queremos que parcial a ser $0$ así que el jugador C no desea cambiar su actual valor de $c.$

si $a=0.5$ cada $c$ es una solución. Esto significa $a=b=0.5$ y cualquier $c$ será una relación asimétrica de NE y obtener toda la ganancia esperada $0$. Esta un poco sorprendente, pero el simétrica caso de $a=b=c=0.5$ es de interés primordial. Así que si todos juegan estrategia de 0.5, ningún jugador quiere cambiar su estrategia ya que el parcial es $0$.

si $a\ne 0.5$, entonces no hay ningún valor de $c$ es una solución.

En resumen, el jugador C (y cada jugador es el jugador C) debe elegir a $c=0.5 .$ Si sus rivales son inteligentes, que también elige $0.5$ y todos los jugadores consiguen la ganancia esperada $0$. Si los oponentes no son inteligentes, reproductor de C va a lograr la rentabilidad esperada. Además, C podría ajustar su estrategia para aumentar su beneficio esperado por la observación (estimación) de los oponentes estrategia a lo largo del juego repetido. Mediante el uso de la derivada parcial, por ejemplo, si los oponentes uso $a=b=0.4$ o algo menos de $0.5$, entonces C debe usar $c=1$, lo que significa jugar la oferta 1. Y si $a=b=0.6$ o algo mayor que $0.5,$, entonces C debe elegir a $c=0$, lo que significa nunca hacer una oferta (o hacer una gran oferta.)

Answer 2

Empíricamente, si dos de los tres individuos escriben cada uno un número entero positivo $N_i$ de forma independiente con probabilidad $$P(N_i=n)=2^{-n}$$ entonces cualquiera que sea el tercero escribe, el resultado esperado para cada uno de los tres es $0$ por lo que el tercero puede seguir también esta estrategia (en cuyo caso habría entonces un empate con probabilidad $\frac17$ ).

También parece que los dos primeros siguen una estrategia iid diferente entonces la estrategia anterior producirá un resultado esperado positivo para el tercero. Así que parece la estrategia óptima en ausencia de colusión.

Los dos primeros pueden desarrollar una estrategia colusoria: supongamos que el primero siempre escribe $1$ y el segundo $2$ y se reparten las ganancias después del juego. El tercer jugador perdería siempre.