Batalla frontal cinco

Question

Dos generales que están luchando contra un cinco frente de batalla. Cada general tiene 1 unidad de ejército, que se divide en los cinco ejércitos que se envía a los cinco frentes. Si uno general envía un ejército más fuerte del frente de la otra, el otro ejército al instante se da por vencido y la parte delantera es asumida por el general. Si se envía exactamente la misma cantidad de ejército del frente, entonces los líderes de los ejércitos jugar una partida de Backgammon para determinar el propietario de la frente. Lo general toma más de al menos tres de los frentes gana la batalla (el otro lo general se da por vencido).

Ni el general tiene espías, y partieron a sus ejércitos, simultáneamente, de modo que cada uno de los generales gustaría encontrar un probabilística de la estrategia que garantiza que no va a perder la batalla más de la mitad del tiempo.

Antecedentes: he encontrado los tres frente a la versión de este problema en los foros de xkcd. No sé si las generalizaciones del problema a un mayor número de frentes se han considerado antes.

Como punto de partida, aquí es una clase de estrategias que nunca puede funcionar:

Supongamos que usted tiene una distribución tal que el número esperado de frentes que ganar al menos $\frac52$ independientemente de que el otro jugador de la estrategia. Entonces usted va a perder contra una permutación aleatoria de la división de $(0, 0, \frac3{10}, \frac3{10}, \frac25)$ más de la mitad del tiempo.

Prueba: Supongamos que su estrategia ha probabilidad $f(x)$ de envío de al menos $x$ unidades de ejército del frente. A continuación, esperando ganar $\frac52$ frentes implica que para todo $a + b + c+d+e = 1$, tenemos $f(a)+f(b)+f(c)+f(d)+f(e) \ge \frac52$, y combinando esto con el hecho de que la cantidad media de ejército enviado a un delantero es de $\frac15$ no es difícil mostrar que el número de los ejércitos enviados a cualquier particular frente debe estar distribuido uniformemente entre $0$ y $\frac25$. Por lo tanto, el número de frentes que espera ganar en contra de una permutación aleatoria de $(0, 0, \frac3{10}, \frac3{10}, \frac25)$ es exactamente $\frac52$.

No es difícil calcular que la probabilidad de ganar la batalla está dada por (E(frentes de ganado) - Pr(gana hasta el número de frentes) - 1)/2. Así, sólo tenemos que comprobar que la probabilidad de ganar un número de frentes es más de la mitad. Para empezar, siempre vamos a perder la frente le envía $\frac25$ ejércitos, y ganar los frentes de enviar $0$ ejércitos. Por lo tanto, la probabilidad de ganar dos frentes debe ser de al menos el combinado de la probabilidad de ganar tres o cuatro frentes (ya que nunca ganar uno solo de frente), por lo que se perderán más de la mitad de la época como el tiempo que tienen un valor distinto de cero posibilidades de ganar cuatro frentes, y usted tendrá un valor distinto de cero posibilidades de ganar cuatro frentes mientras envíe al menos $\frac3{10}$ unidades de ejército a dos de los frentes. Pero la posibilidad de envío de al menos $\frac3{10}$ para un delantero es de $f(\frac3{10}) = \frac14$, y si su estrategia nunca envía $\frac3{10}$ a dos frentes a la vez, entonces la probabilidad de que el envío de al menos $\frac3{10}$ a un particular frente sería en la mayoría de los $\frac15$, lo cual es imposible.

Answer 1

Este es un ejemplo de una clase de juegos conocido como 'el Coronel Blotto' los juegos. Wikipedia afirma que el papel de Roberson, B. (2006), "El Coronel Blotto Juego," la Teoría Económica del 29, 1-24. proporciona una solución para cualquier número de campos de batalla y cualquier número de recursos, pero no he confirmado de forma independiente de este.

Actualización: En respuesta a zeb el comentario de abajo, si bien es cierto que el juego descrito es diferente Blotto, también se da el caso de que, a través de la simetría de la naturaleza del problema, la estrategia será el óptimo para cualquiera de juego si y sólo si el número esperado de victorias es de $n/2$, independientemente de la estrategia del oponente. Así que la solución de Blotto es equivalente a resolver la cuestión que se le pidió.

También me dio la vuelta para mirar a Roberson del papel, y lo hace, de hecho, resolver el problema. Primero demuestra que cualquier distribución que los proyectos a los Uniformes de$[0,2/n]$ en cada coordenada de trabajo. A continuación, se construye una distribución de $n$. (En realidad lo hace un poco más, ya que no se asume que los dos jugadores tienen la igualdad de recursos.) Los detalles son un poco mucho para poner en un MO post, pero cualquier persona interesada debe comprobar hacia fuera; el papel no es muy largo y no demasiado difícil de leer.

Answer 2

Estoy traspaso notzeb la solución a las 3 de la parte frontal de la funda aquí, y hacer algunos comentarios sobre el mismo. En particular, debo señalar que la solución no es única; mientras que notzeb utilizado fractal métodos, voy a dar una seccionalmente suave solución usando las mismas ideas.

La Idea de la solución:

Me dicen que es suficiente para encontrar cualquier distribución de probabilidad en $\{(p,q,r): p+q+r=1, \ p,q,r \geq 0 \}$, cuya proyección para cada coordenada es el uniforme de la medida en $[0,2/3]$.

La prueba de que tal medida funciona:

(Por simplicidad, me caso omiso de los lazos.) Observar que es imposible para cualquiera de general a ganar en todos los frentes. Por lo tanto, si puedo encontrar una estrategia que garantiza que voy a esperar a ganar por lo menos 1.5 frentes contra cualquier oposición de la estrategia, esto significa que he probabilidad de al menos 1/2 de ganar 2 frentes contra cualquier oposición de la estrategia. (Esta lógica no se extiende a las 5 de la parte frontal de la funda.)

Supongamos que mi enemigo envía $p$ tropas del primer frente. Me golpearon con una probabilidad de $\max(1-(3/2)p, 0)$. Por la linealidad de la expectativa, si mi enemigo envía tropas $(p,q,r)$, mi número esperado de victorias es $$\max(1-(3/2)p, 0)+\max(1-(3/2)q, 0)+\max(1-(3/2)r, 0)$$ $$\geq 3-(3/2)(p+q+r) = 3/2.$$ Si mi oponente se adopta una estrategia mixta, la linealidad muestra de que todavía tengo espera que el número de victorias en menos de $3/2$. QED

notzeb de la medida:

Tomar el triángulo de las posibles soluciones y de inscribir un hexágono en el que, con vértices en las permutaciones de $(0,1/3,2/3)$. Todas nuestras soluciones serán dentro de ese hexágono.

Ahora, toma ese hexágono y en lugar de 6 pequeños hexágonos en como se muestra a continuación.

Elegir uno de los 6 hexágonos uniformemente al azar. Al cabo de 6 pequeños hexágonos que dentro de uno, y elegir uno de estos uniformemente al azar de nuevo. A seguir adelante. Los hexágonos de tamaño en el tamaño de cada tiempo; el punto límite es tu ejército de distribución.

Observe que el espacio de posibles soluciones es un Sierpinski-junta-como el de la figura, de la dimensión de Hausdorff $\log 6/\log 3$. Es lindo observar que el blanco de la estrella de David en el centro se convierte en un copo de nieve de Koch de excluidos puntos en la solución final.

Mi alternativa de medir

Inscribir un círculo en el triángulo. En ese círculo, en lugar de la medida $dA/\sqrt{1-r^2}$, como se describe en la Harald Hanche-Olsen respuesta a una pregunta diferente.