Cinco frentes de batalla

Question

Dos generales libran una batalla en cinco frentes. Cada general tiene 1 unidad de ejército, que divide en cinco ejércitos separados que envía a los cinco frentes. Si un general envía más ejército a un frente que el otro, entonces el otro ejército se rinde instantáneamente y el frente es tomado por ese general. Si envían exactamente la misma cantidad de ejército a un frente, entonces los líderes de los ejércitos juegan una partida de Backgammon para determinar el propietario del frente. El general que se haga con al menos tres de los frentes gana la batalla (el otro general se rinde).

Ninguno de los generales tiene espías, y dividen sus ejércitos simultáneamente, por lo que a cada general le gustaría que usted le encontrara una estrategia probabilística que le garantice que no perderá la batalla más de la mitad de las veces.

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

Como punto de partida, he aquí una clase de estrategias que nunca pueden funcionar:

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

Pruebas: Suponga que su estrategia tiene probabilidad $f(x)$ de enviar al menos $x$ unidades de ejército a un frente. Entonces esperando ganar $\frac52$ implica que para cualquier $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 enviada a un frente es $\frac15$ no es difícil demostrar que el número de ejércitos enviados a un frente determinado debe distribuirse uniformemente entre $0$ y $\frac25$ . Por lo tanto, el número de frentes que se espera ganar contra 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 viene dada por (E(frentes ganados) - Pr(ganar número par de frentes) - 1)/2. Por lo tanto, sólo tenemos que comprobar que la probabilidad de ganar un número par de frentes es superior a la mitad. Para empezar, siempre perderemos el frente que envíe $\frac25$ ejércitos, y ganar los frentes que envíe $0$ ejércitos a. Así, la probabilidad de ganar dos frentes debe ser al menos la probabilidad combinada de ganar tres o cuatro frentes (ya que nunca se gana un solo frente), por lo que perderá más de la mitad de las veces siempre que tenga una probabilidad no nula de ganar cuatro frentes, y tendrá una probabilidad no nula de ganar cuatro frentes siempre que envíe al menos $\frac3{10}$ unidades del ejército a dos de los frentes. Pero la posibilidad de enviar al menos $\frac3{10}$ a un frente es $f(\frac3{10}) = \frac14$ y si su estrategia nunca envía $\frac3{10}$ a dos frentes a la vez entonces la posibilidad de enviar al menos $\frac3{10}$ a un frente concreto sería como máximo $\frac15$ lo cual es imposible.

Answer 1

Estoy reposting notzeb's solución al caso de los 3 frentes y hacer algunos comentarios al respecto. En particular, señalaré que la solución no es única; mientras que notzeb utilizó métodos fractales, yo daré una solución suave a trozos utilizando las mismas ideas.

Idea de solución:

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

Prueba de que tal medida funciona:

(Obsérvese que es imposible que un general gane en todos los frentes. Por lo tanto, si encuentro una estrategia que me garantice ganar al menos 1,5 frentes contra cualquier estrategia contraria, esto significa que tengo probabilidad de al menos 1/2 de ganar 2 frentes contra cualquier estrategia contraria. (Esta lógica no se extiende al caso de 5 frentes).

Supongamos que mi enemigo envía $p$ tropas al primer frente. Le gané con probabilidad $\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 adopta una estrategia mixta, la linealidad demuestra que sigo teniendo un número esperado de victorias de al menos $3/2$ . QED

medida de notzeb:

Tomemos el triángulo de posibles soluciones e inscribamos en él un hexágono con vértices en las permutaciones de $(0,1/3,2/3)$ . Todas nuestras soluciones estarán dentro de ese hexágono.

Ahora, toma ese hexágono y coloca 6 hexágonos más pequeños en él, como se muestra a continuación.

6 Hexágonos en 1 http://www-math.mit.edu/~speyer/3front.

Elige uno de esos 6 hexágonos uniformemente al azar. Coloca 6 hexágonos más pequeños dentro de ese y vuelve a elegir uno de ellos uniformemente al azar. Sigue así. Los hexágonos se reducen de tamaño cada vez; el punto límite es la distribución de tu ejército.

Obsérvese que el espacio de posibles soluciones es una figura similar a un gásket de Sierpinski, de dimensión Hausdorff $\log 6/\log 3$ . Es bonito observar que la estrella de David blanca del centro se convierte en un copo de nieve Koch de puntos excluidos en la solución final.

Mi medida alternativa

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

Answer 2

Este es un ejemplo de una clase de juegos conocidos como juegos del "Coronel Blotto". Wikipedia afirma que el documento Roberson, B. (2006), "The Colonel Blotto Game", Economic Theory 29, 1-24. proporciona una solución para cualquier número de campos de batalla y cualquier número de recursos, pero no lo he confirmado de forma independiente.

Actualización: En respuesta al comentario de zeb más abajo, si bien es cierto que el juego descrito es diferente al Blotto, también lo es que, por la naturaleza simétrica del problema, una estrategia será óptima para o bien juego si y sólo si el número esperado de victorias es $n/2$ independientemente de la estrategia del adversario. Así que resolver Blotto es equivalente a resolver la pregunta que se planteó.

También he mirado el artículo de Roberson, y efectivamente resuelve el problema. En primer lugar demuestra que cualquier distribución que se proyecta a Uniforme $[0,2/n]$ en cada coordenada funcionará. A continuación, construye dicha distribución para cualquier $n$ . (En realidad hace bastante más, ya que no asume que los dos jugadores tienen los mismos recursos). Los detalles son demasiado extensos para ponerlos en un post de MO, pero quien esté interesado debería echarle un vistazo; el artículo no es muy largo ni difícil de leer.