¿Cómo conseguir el mejor resultado con una sola declaración en este juego?

Question

Este juego está sacado de La teoría de los juegos de Schelling: cómo tomar decisiones de R.V. Dodge, en el que los contendientes practican el brinkmanship en beneficio propio. Dice lo siguiente:

Anderson, Barnes y Cooper se batirán en un duelo de pistolas. Se colocarán cerca el uno del otro, para que cada uno pueda matar a uno de los otros de un solo disparo o fallar deliberadamente. El primero en disparar será elegido al azar y rotarán en el orden Anderson, Barnes y Cooper, cada uno disparando un tiro a la vez.

Si hay más de un superviviente después de varias rondas, se elegirá al azar a uno de los contendientes y se le obligará a matar a uno de los otros, y esto se repetirá si sigue habiendo más de uno vivo después de algunas rondas más.

Antes de que comience el duelo, Anderson puede hacer cualquier declaración, seguida de una declaración de Barnes, y finalmente una de Cooper. Se adherirán a las siguientes reglas:

1. Las declaraciones son irrevocables. Un contendiente no puede actuar para contradecir su declaración.
2. Actuará en su propio interés cuando no entre en conflicto con la Primera Regla.
3. Actuará al azar cuando no entre en conflicto con las Reglas Uno y Dos.

Hay árbitros que velan por el cumplimiento de las normas. Si un contendiente se compromete a una estrategia mixta (por ejemplo, a fallar con una probabilidad de 1/3), la probabilidad se determinará de forma objetiva (lanzando dados, etc.).

Q1 : ¿Qué declaración hará Anderson? ¿Cuál es su mejor estrategia y su probabilidad de sobrevivir?

Q2 : Si tres contendientes tienen que hacer sus declaraciones en el orden de la ACB, ¿cuál sería la mejor declaración para Anderson?

Q3 : Si hay más de tres contendientes, ¿el juego se vuelve más sencillo o más difícil? ¿Podemos decir algo sobre el $N$ caso de los contendientes para $N\gt 3$ ?

---

Obsérvese que si nadie hace ninguna declaración, nadie disparará, y todos tienen una probabilidad de supervivencia de 1/3. Si sólo se permite a Anderson hacer una declaración, puede garantizar una supervivencia casi segura haciendo esta declaración a B y C: "Si no os matáis entre vosotros en vuestras primeras oportunidades, mataré al primero de vosotros que no lo haga en mi primera oportunidad; de lo contrario, dispararé al superviviente de vosotros con un 1% de posibilidades de fallar."

En el libro, una de las mejores soluciones sugeridas para Q1 es que A diga: "Si B no se compromete a disparar incondicionalmente a C, le dispararé". El argumento es que B no tiene más remedio que aceptar, porque rechazar la propuesta de A supondría una muerte segura para B. ¡Pero eso es claramente erróneo! Porque B puede decir: "Si C no promete matar a A en su primera oportunidad, yo mataré a C en la mía; si C lo hace, mataré a A en mi primera oportunidad y dispararé a C con un 1% de posibilidades de fallar si él mata a A primero". Rechazando la propuesta de B, C tiene 2/3 de posibilidades de sobrevivir (1/3 para que A dispare primero y 1/3 para que C dispare primero); aceptando tiene 2/3+0,33% de posibilidades (1/3 para que A dispare primero, 1/3 para que B dispare primero y 0,33% para que C dispare primero). Por tanto, C aceptará. Entonces A está condenado, obligado por su propia declaración inconveniente.

Answer 1

A advertencia En realidad, esto no es una respuesta, sino más bien un comentario extendido, por eso lo he puesto como wiki de la comunidad. Este es un juego genial, uno de compromiso.

Voy a intentar formalizar el problema. Esta es una primera pasada, así que la gente debe editar lo que considere oportuno.

Probablemente sea más fácil resolver el caso en el que, $T$ el número de rondas antes de una ejecución forzada es $1$ . Que cada jugador obtenga $1$ si disparan a otra persona y $-1$ si ellos mismos son disparados.

Hay dos etapas del juego, la etapa de compromiso y la etapa de tiro. La etapa secuencial es (apropiadamente) un movimiento secuencial y la etapa de compromiso no es realmente un juego, ya que los jugadores son autómatas (sus estrategias están predeterminadas). Volveré sobre esto en breve.

Un resultado fácil: existe un equilibrio en el que las reglas 2 y 3 se vuelven superfluas, ya que cada jugador puede comprometerse con todas las contingencias posibles.

Hay una fuente de aleatoriedad exógena, un estado aleatorio del mundo $\Theta = \Theta_{1} \times \Theta_{2}$ , $i = 1,2$ , donde $\Theta_{i}$ es el conjunto de permutaciones de $\left\{A,B,C\right\}$ . Estas son las posibles órdenes en la parte de tiro.

El conjunto de acciones del jugador $A$ es $\mathcal{A} = \mathcal{A}_{1} \times \mathcal{A}_{2}$ donde $\mathcal{A}_{i} = \left\{B,C,\emptyset\right\}$ para $i = 1,2$ (correspondiente a "disparar $B$ "," "dispara $C$ y "no disparar a nadie", respectivamente). Los conjuntos de acciones para los otros dos jugadores, $\mathcal{B}$ y $\mathcal{C}$ se definen de forma análoga.

Una estrategia de compromiso (mixta) de $A$ es un mapeo $$\sigma_{A}: \Theta \times \Sigma_{B} \times \Sigma_{C} \to \Delta\left(\mathcal{A}\right)$$ donde $\Sigma_{i}$ , $i = A, B, C$ es el conjunto de todas las estrategias mixtas (factibles). Un ejemplo de estrategia no factible para el jugador $A$ es uno que no tiene $\emptyset$ jugado con probabilidad $1$ cuando el estado y las estrategias mixtas de los otros jugadores son tales que $A$ se ha disparado con seguridad.

Tenga en cuenta que estoy utilizando el hecho de que la parte de los disparos del juego puede ser visto como un resultado instantáneo (al azar) de la parte de compromiso, que es el real juego.

No estoy muy seguro de las estrategias de compromiso para $B$ y $C$ debido a la naturaleza de movimiento secuencial de la etapa de compromiso. Sospecho que eso no importa, y que se definen de forma análoga. No estoy completamente convencido de esto y estoy abierto a ser convencido de lo contrario.

La retribución de cada jugador se define de forma obvia.

Answer 2

He aquí una prueba de que la respuesta dada por Schelling en la respuesta de Eric es (tan buena como) lo mejor que puede hacer A.

A no puede hacer mucho en represalia porque B y C se alían contra él. Puede amenazar con disparar a B con certeza, amenazar con disparar a C con certeza, o alguna mezcla de ambas. Llamemos y a la probabilidad de que dispare a C si se alían contra él, donde disparará a B con una probabilidad de 1-y (no tiene mucho sentido que dispare a ninguno de los dos).

Independientemente de lo que haya dicho A, B siempre puede hacer la declaración:

"Si C se compromete a disparar a A en la primera ronda, haré lo siguiente:

-Si soy el primero en disparar, dispararé a A con una precisión x (donde x es algún número entre 0 y 1)

-Si soy el segundo en disparar voy a disparar A con una precisión perfecta.

-Si soy el tercero en el orden (lo que significa que A ya estará muerto) dispararé al aire y dejaré que C gane el duelo.

Si C no se compromete a disparar a A, dispararé a C pase lo que pase".

Si C sigue el plan de B, tendrán al menos un $\frac{2+x-y}{3}$ de sobrevivir, mientras que B tendrá al menos una $\frac{1-x+y}{3}$ posibilidad de sobrevivir. Si C ignora el plan de B, tendrá como mucho 2/3 de posibilidades de sobrevivir, ya que si B es elegido para disparar primero, C morirá con toda seguridad. Si C es indiferente entre formar un equipo o ignorarlo, elegirán al azar formar un equipo la mitad de las veces, mientras que ignorarán la otra mitad.

Para cualquier y, B puede elegir x=y, lo que garantiza que C aceptará la oferta al menos la mitad de las veces, y B tendrá al menos 1/6 de posibilidades de sobrevivir. Dado que B puede garantizarse a sí mismo una probabilidad de supervivencia de 1/6, no puede darse el caso de que A pueda garantizarse a sí mismo una probabilidad de supervivencia superior a 5/6.

Answer 3

El propio Schelling dio una respuesta para Q1 en la que A puede alcanzar una probabilidad de supervivencia arbitrariamente cercana a 5/6. Cito el libro a continuación. La redacción es dolorosamente tortuosa a veces. Pero la respuesta parece correcta. No sé si es LO MEJOR resultado que puede conseguir A.

El profesor Schelling ofreció una solución que garantiza a Anderson una casi certeza de supervivencia, al incluir probabilidades en sus tiros. En esta solución Anderson se compromete a disparar con una pequeña probabilidad de fallar a quien haya matado al otro, pero si Cramer no mata a Barnes, a matar a Cramer. Debe incluir algo que impida cualquier compromiso unilateral que Barnes o Cramer puedan hacer para superar el suyo, por lo que añadiría que si cualquiera de ellos hace un compromiso distinto al de aceptar el suyo, matará a esa persona en su turno o disparará al aire si la persona está muerta. Si ambos hacen compromisos unilaterales, Anderson garantiza matar a Cramer o, si éste ya está muerto, disparar al aire (se aplicarán las reglas del duelo). Respuesta de Schelling:

Anderson tiene que impedir un compromiso de Barnes que dé a Cramer más posibilidades de sobrevivir, lo que podría hacer diciendo: "Si no aceptas mi propuesta, te mataré a mi vez. Si la aceptas, te garantizo dos tercios de posibilidades de vivir, como sigue: Si Anderson se compromete a matarme si aceptas mi propuesta, entonces yo prometo matar a Anderson si tú prometes matar a Anderson. Si Anderson no se compromete a quién dispara una vez que usted haya aceptado mi oferta, hay un 50% de posibilidades de que me dispare a mí. Si eres tú quien lo mata, yo te dispararé con un 50% de posibilidades de matarte a ti. Por último, si Anderson se compromete a matar a cada uno de nosotros con probabilidades específicas tales como 0,8 te disparará a ti y 0,2 me disparará a mí si ambos nos comprometemos, entonces te dispararé a ti con una probabilidad de 0,2 de matarte después de que hayas matado a Anderson".

Si Anderson no hace una oferta tan buena a Cramer, la oferta de Barnes será aceptada y Anderson seguramente estará muerto. Si Anderson hace una oferta equivalente a Cramer, Cramer tiene 2/3 de posibilidades de sobrevivir o acepta la oferta de Barnes. Si acepta la oferta de Barnes hay 1/3 de posibilidades de que Anderson le mate, de lo contrario vive porque mata a Anderson si Barnes es asesinado primero. Si no acepta la oferta de Barnes, Barnes lo matará si tiene la oportunidad, de lo contrario Anderson matará a Barnes. Dado que las posibilidades de Cramer son las mismas tanto si acepta como si no la oferta de Barnes, la regla tres dice que decide al azar, por lo que Barnes tiene un 50-50 de posibilidades de conseguir un 1/3 de posibilidades de vivir si lo acepta.

Si Anderson no puede superar el 1/6 de posibilidades de vivir de Barnes, que vendría con propuestas iguales, no puede anticiparse al compromiso, lo que le deja con la misma probabilidad. Tiene que hacer algo mejor para que Barnes mantenga la boca cerrada.Entonces, la declaración de Anderson: "Si Barnes hace una oferta y Cramer la acepta, mataré a Cramer en mi turno o dispararé al aire si Cramer ya está muerto. Si Barnes hace una oferta y Cramer no la acepta, mataré a Barnes en mi turno o dispararé al aire si ya está muerto. Si alguien hace un compromiso unilateral que no depende de una respuesta, mataré al último que lo haga o dispararé al aire si ya está muerto. De lo contrario, si Cramer no mata a Barnes en su primera oportunidad, estando Barnes aún vivo, lo mataré. Si Cramer mata a Barnes le dispararé con un 1% de probabilidad de fallar. Si Barnes mata a Cramer le dispararé con un 27% de probabilidad de fallar".

Si Barnes y Cramer mantienen la boca cerrada hay 2/3 de posibilidades de que los despidan primero. Si Anderson es el primero disparará al aire y Barnes matará a Cramer y tendrá un 27% de posibilidades de sobrevivir. Si Cramer es el primero Barnes está muerto, por lo que la probabilidad de Barnes de sobrevivir es 2/3 del 27% o 18%. Cramer se mantiene callado y tiene un 1% de posibilidades de sobrevivir si es el primero en disparar, y un 0,33% de posibilidades en general. Eso deja a Anderson con un 71,67% de probabilidad de sobrevivir.

Schelling concluye que dando a Cramer una probabilidad aún menor que el 1% y a Barnes un incremento por encima de 1/6 Anderson puede hacer que sus propias probabilidades se acerquen tanto a 5/6, o al 84%, como desee.

Answer 4

Si sólo se permite que un jugador haga una declaración, tenemos los siguientes teoremas :

Teorema 1 : Si $N\gt 3$ entonces la probabilidad de supervivencia de ese contendiente debe ser estrictamente inferior a $\frac{N-1}N$ .

Prueba :

WLOG, suponga que el único jugador $1$ puede hacer una declaración y los jugadores $2$ ~ $N$ debe guardar silencio. Observe que al matar al jugador $1$ en sus turnos, los jugadores $2$ ~ $N$ llevará el juego a un subjuego donde $N-1$ los jugadores están vivos y nadie ha hecho ninguna declaración. En este subjuego cada jugador tiene $\frac1{N-1}$ probabilidad de supervivencia. Así que en el juego original los jugadores $2$ ~ $N$ cada uno tiene una probabilidad de supervivencia de al menos $\frac1{N(N-1)}$ . Esto significa que el jugador $1$ tiene una probabilidad de supervivencia estrictamente inferior a $1-\frac{N-1}{N(N-1)}=\frac{N-1}N$ . QED

Teorema 2 : Para $N=4$ , el Teorema 1 da el mínimo límite superior, es decir $\forall \varepsilon\gt 0$ Hay una declaración para el jugador $1$ tal que su probabilidad de supervivencia $P_{1}^{4}=3/4-\varepsilon$ .

Prueba : Similar a la prueba del Teorema 3.

Teorema 3 : Para $N=5$ podemos probar que hay una declaración para el jugador $1$ tal que $P_{1}^{5}=3/5-\varepsilon$ , $\forall \varepsilon\gt 0$ . La declaración del jugador $1$ será demasiado largo para ponerlo en palabras reales, pero funciona como abajo.

Prueba :

Nombre de los jugadores $A_i$ para $i=1$ a $5$ . $A_1$ La estrategia del jugador es persuadir a quien está disparando en ese momento para que dispare a un jugador después de él, prometiéndole una probabilidad de supervivencia de $\frac1{M-1}+\varepsilon$ , hasta que sólo $3$ jugadores, donde $M$ es el número de jugadores vivos. Cuando los jugadores se reducen a tres, $A_1$ puede entonces asignar las probabilidades que prometió a los otros dos jugadores. Hay 5 posibilidades que corresponden a quién es elegido para disparar primero por los árbitros. Lo ilustraremos con el caso en que $A_2$ es el primero en disparar.

$A_1$ habrá declarado que en este caso, $A_2$ debe matar $A_3$ Después de eso, $A_4$ debe matar $A_5$ . Para que esto ocurra, debe prometerles probabilidades de supervivencia $\frac1{4}+\varepsilon$ y $\frac1{3}+\varepsilon$ respectivamente, de lo contrario será mejor que maten $A_1$ (si las probabilidades prometidas son menores que $\frac1{4}$ y $\frac1{3}$ ), o por la regla 3 aleatorizar (si las probabilidades prometidas son iguales a $\frac1{4}$ y $\frac1{3}$ ). Las probabilidades prometidas pueden realizarse en los duelos a tres bandas entre $A_1$ , $A_2$ , $A_4$ mediante algún compromiso apropiado como éste: " $A_2$ disparará a $A_3$ con $\frac1{4}+\varepsilon$ probabilidad de matar. Si mata, fallaré y dejaré que me mate también; si falla, $A_3$ debe matarlo, entonces dispararé a $A_3$ con $\frac{\frac1{3}+\varepsilon}{\frac3{4}-\varepsilon}$ probabilidad de matar. Mataré a quien primero viole esta propuesta en mi primera oportunidad". Esto deja $A_1$ con probabilidad de supervivencia $\frac5{12}-2\varepsilon$ .

Las otras 4 posibilidades se calculan de forma similar, dando lugar a probabilidades de supervivencia para $A_1$ como $\frac5{12}-2\varepsilon$ , $\frac3{4}-2\varepsilon$ , $\frac3{4}-2\varepsilon$ , $\frac2{3}-2\varepsilon$ correspondiente a $A_3$ , $A_4$ , $A_5$ , $A_1$ disparando en primer lugar, respectivamente. Al sumarlos y dividir el resultado entre 5 se obtiene $P_{1}^{5}=3/5-2\varepsilon$ . QED