Cómo elegir el número más pequeño no elegido?

Question

Así que hay $n$, cada uno, la elección de algunas de cero conteo de número. Usted no sabe lo que cualquiera de ellos elija. Para ganar, usted debe elegir el número más pequeño; pero si usted elige el mismo número como alguien más, estás descalificado. ¿Cómo decidir qué número de $k$ es mejor elegir? Me siento como $k\le n$, pero aparte de que no tengo idea de por donde empezar. Alguna idea?

EDIT: por Lo que para evitar un trivial paradoja y un tanto modelo real del comportamiento humano, queremos que la $n$ a las personas a elegir los números razonablemente, pero no necesariamente a la perfección. Por ejemplo, nadie va a elegir a $k > n$, ya que eso sería tonto. Desde la elección de 1 siendo irrazonable llevaría a la paradoja, también diremos 1 podría ser elegido, pero no necesariamente ser recogidos.

Answer 1

Contrario a la intuición, el equilibrio de Nash de este juego (suponiendo $n\geq 2$) tienen probabilidad positiva de elegir cualquier número entero positivo. Supongamos que no, así que hay algunos entero $m$ de manera tal que el equilibrio de Nash recoge $m$ con una probabilidad de $p_m>0$ pero nunca recoge $m+1$. Supongamos que todos los demás están jugando a una estrategia, y considerar lo que sucede si usted juega la modificación de la estrategia que, en cambio, recoge $m+1$ con una probabilidad de $p_m$ y nunca recoge $m$. Esto se realiza exactamente el mismo si usted toma algún otro número de $m+1$. Si usted escoge $m+1$ y hubiera ganado hubiera escogido $m$, entonces usted va a ganar, ya que nadie ha escogido $m+1$ (porque no pueden) o $m$ (por supuesto que habría ganado mediante la selección de $m$). Usted también gana en el caso de que usted escoja $m+1$ y todos los demás selecciones $m$, que tiene probabilidad positiva. Así que la estrategia original no era un equilibrio de Nash, ya que este supera.

Answer 2

Dado que no se $n$ a los jugadores, vamos a suponer que cada jugador debe elegir un número $k \in \{z \in \mathbb{Z} | 1 \le z \le n\}$. Tenga en cuenta que el orden de los jugadores escoger un número no afecta el resultado.

Algunas ideas:

Al $\textbf{n = 2}$ equilibrio se logra cuando ambos jugadores elegir el número más pequeño es decir $1$.

Para el caso de $\textbf{n = 3}$, vamos dos números de $\{1,2,3\}$ ser ya elegir, entonces

es imposible ganar siempre $\{1, 2\}$, $\{1, 3\}$ son elegidos por los demás.

es posible ganar cuando $\{2, 3\}$, $\{1, 1\}$, $\{2, 2\}$ o $\{3, 3\}$ por otros.

Vamos a considerar lo que sucede si elegimos

$\rightarrow$ número ganador

$1$

$\{1, 2\} \rightarrow 2$

$\{1, 3\} \rightarrow 3$

$\{2, 3\} \rightarrow 1$ Que ganar!

$\{1, 1\}$ Ningún ganador.

$\{2, 2\} \rightarrow 1$ Que ganar!

$\{3, 3\} \rightarrow 1$ Que ganar!

$2$

$\{1, 2\} \rightarrow 1$

$\{1, 3\} \rightarrow 1$

$\{2, 3\} \rightarrow 3$

$\{1, 1\} \rightarrow 2$ Que ganar!

$\{2, 2\}$ Ningún ganador.

$\{3, 3\} \rightarrow 2$ Que ganar!

$3$

$\{1, 2\} \rightarrow 1$

$\{1, 3\} \rightarrow 1$

$\{2, 3\} \rightarrow 2$

$\{1, 1\} \rightarrow 3$ Que ganar!

$\{2, 2\} \rightarrow 3$ Que ganar!

$\{3, 3\}$ Ningún ganador.

Por lo tanto, se ha demostrado que la elección de $1$ al $n = 3$ nos da la mejor oportunidad de ganar. Por lo tanto, $k = 1$ es el equilibrio.

Este enfoque puede ser generalizada para más jugadores.

Answer 3

Ampliación de Maciej Caputa la respuesta, he generalizado a $n=3$ con cualquier función de densidad de probabilidad, no sólo aleatorio uniforme opciones. Deje $P(\text{Our Success})=K$ $P(\text{A player chooses n)}=p_n.$ Si elegimos 1,

$\{1,1\} \rightarrow $Nadie con $P=p_1p_1$

$\{1,2\} \rightarrow 2$ $P=p_1p_2$

$\{1,3\} \rightarrow 3$ $P=p_1p_3$

$\{2,2\} \rightarrow $Que ganar! con $P=p_2p_2$

$\{2,3\} \rightarrow $Que ganar! con $P=p_2p_3$

$\{3,3\} \rightarrow $Que ganar! con $P=p_3p_3$ $$\text{If we choose 1, } K_1=p_2^2+p_2p_3+p_3^2$$ Del mismo modo, $K_2=p_1^2+p_3^2$$K_3=0$. Por lo que el número que usted elija debe ser determinado por $K=max(p_2^2+p_2p_3+p_3^2,p_1^2+p_3^2,0).$

Pero generalizar a cualquier $n$ está resultando más difícil de lo esperado.

Answer 4

Una regla de oro es que habrá un único número en algún lugar entre el$1$$n/\ln(n)$.

Si todo el mundo elige un valor entre 1 y $n/\ln(n)$, cada valor se recoge $\ln(n)$ veces en promedio.

Para un valor dado, el número de veces que se ha seleccionado sigue una distribución de Poisson, con $\lambda = \ln(n)$. La posibilidad de que se recoge cuando se $\lambda e^{-\lambda}=\ln(n)/n$.

En promedio, un valor único.

Si la gente elige los números más grandes de $n/\ln(n)$, habrá varios números únicos. Ya que sólo el más bajo de estos triunfos, que estarían mejor con números más pequeños - así que esto no es fructífera. Si la gente se extendió más de dos veces el intervalo, es probable que se $\sqrt{n}$ valores únicos.

Si la gente sólo seleccionar valores mucho menos de $n/\ln(n)$, entonces cada valor es recogido varias veces. Todo el mundo está eliminado, y una estrategia ganadora es para evitar el aplastamiento mediante la selección de un gran valor. De nuevo, no es fructífera para concentrarse en los valores pequeños. Si la gente restringir a la mitad del intervalo, existe una posibilidad en $n$ de los valores únicos.