Juego de estrategia óptima de comunicación sin solapamiento

Question

Hoy he tenido una conversación que se ha desarrollado muy mal; de hecho, he tenido esta conversación con $n$ personas, incluido yo mismo, y todos tenían algo que decir. El problema fue que, durante un tiempo excesivamente largo, siempre había dos o más personas intentando hablar a la vez, y todo era indescifrable. Luego, la gente se retiró y hubo periodos en los que nadie estaba hablando - sólo para provocar que algunas personas intentaran saltar a la conversación, ¡y se solaparan de nuevo! Finalmente Por pura casualidad, una persona llegó a hablar sola (y no tuvo que volver a hacerlo) y, poco a poco, todos tuvieron su turno para hablar.

Ahora, siendo el matemático que soy, pensé, Oye, yo puedo resolver este problema. Quiero dar a todos $n$ personas una hoja de papel en la que se describen las reglas de la conversación; una solución sencilla sería asignar a cada uno un tiempo para hablar, pero eso no es justo para las personas que tienen que esperar. Así que quiero dar a todos $n$ personas el mismo conjunto de reglas a seguir. Supongo que reconozco que, esto significa que, en la primera oportunidad de hablar, todo el mundo hablará con la misma probabilidad, y parece probable que haya un solapamiento - pero entonces las estrategias pueden diferenciarse en base a los resultados de esa primera oportunidad (aunque estas personas son pobres oyentes; de cada oportunidad, sólo saben si intentaron hablar, y si había varias personas, una sola persona, o nadie hablaba).

Para ser muy formal, defina el problema como sigue:

A conversación es una serie de oportunidades discretas para hablar, en las que cada jugador puede elegir entre intentar hablar o permanecer en silencio. El que consiga hablar sin ser interrumpido no volverá a intentar hablar. La conversación termina cuando todos han hablado. La página web historia de una conversación, será una secuencia finita de los tres posibles resultados de una oportunidad (nadie habla, una persona habla, muchas personas hablan) - no distingue entre $2$ y $3$ gente hablando. A estrategia es un mapa que toma el historial de una conversación y determina si un determinado jugador hablará. A estrategia mixta es una distribución de probabilidad sobre el conjunto de estrategias posibles, y representa, esencialmente, una estrategia no determinista.

Y mi pregunta es la siguiente:

¿Para qué estrategia mixta se minimiza la duración prevista de la conversación (medida en oportunidades perdidas) cuando $n$ la gente juega la estrategia contra sí misma?

Lo que sé hasta ahora son las siguientes estrategias:

• $n=1$ : La persona debe hablar a la primera oportunidad. La conversación tendrá una duración $1$ y se sentirá muy solo.

• $n=2$ : Las personas deben maximizar la probabilidad de que exactamente uno de ellos hable en cada turno - y, si ambos deciden hablar o ambos no hacerlo, no obtienen ninguna información útil sobre el otro, y por lo tanto deben continuar con la misma estrategia. Así, la mejor estrategia es hablar con la probabilidad $\frac{1}2$ hasta que uno de ellos tiene éxito, después de lo cual el otro habla, dando una duración esperada de $3$ .

• $n=3$ : Esta es más complicada y no tengo una prueba. Estoy bastante seguro de que la siguiente estrategia es localmente óptima, y sospecho que es la mejor, pero no estoy seguro. Usamos tres estados en los que una persona puede estar - todos comienzan en el estado A:

  (Estado A) Hablar con probabilidad $p$ en la próxima oportunidad. Si nadie habla, permanece en el estado A. Si una persona habla, pasa al juego de dos personas. Si hablan muchas personas, incluido usted, pase al estado B. Si hablan muchas personas, sin incluirse usted (lo que implica que los otros dos hablaron), pase al estado C.

  (Estado B) No hablar en la siguiente oportunidad, luego pasar al estado A si nadie habla. Si una persona habla, transición al juego de dos estados. (En este estado no hablará más de una persona)

  (Estado C) Habla en la próxima oportunidad; tienes garantizado el éxito.

La idea aquí es que salimos del dilema cuando una persona habla de las tres, o cuando lo hacen dos (y entonces la otra persona habla mientras las dos que se solapan están en el estado B, en silencio). Utilizando que la duración esperada de una conversación para dos personas es $3$ podemos encontrar la longitud esperada $\ell$ de esta conversación como $$\ell = p^3\cdot(2+\ell)+3p^2(1-p)\cdot (2+3)+3p(1-p)^2\cdot (1+3)+(1-p)^3\cdot(1+\ell)$$ que da el mínimo, según Mathematica $$p=\frac{1}{4} \left(2-\sqrt{6}+\sqrt{4 \sqrt{6}-6}\right)\approx .37$$ $$\ell=\frac{1}{6} \left(21+\sqrt{9+24 \sqrt{6}}\right)\approx 4.87.$$

Dado que el problema de caracterizar la estrategia óptima para un $n$ puede ser extremadamente difícil, no esperaría respuestas para encontrar una (pero, si encuentras una, o tienes algo que sospeches que es óptimo, me encantaría verlo) - de hecho, incluso el caso de $n=4$ es interesante para mí, ya que no tengo idea de cuál puede ser la estrategia.

(El relato que se hace en este post es puramente ficticio; cualquier parecido con conversaciones reales es pura coincidencia)

Answer 1

Pasé algún tiempo en la actualidad tratando de mejorar su solución para $n=3$. No sólo no he llegado a algo mejor; me convencí de que el compromiso que hacer en la obtención de la certeza acerca de la historia en el costo de perder una oportunidad en caso de que todas las tres personas hablaban probablemente es óptima.

Creo que la siguiente estrategia para $n=4$ (inspirado en el tuyo) también es probable que sea óptimo:

Hablar con una probabilidad de $p$. Si nadie habla, inténtelo de nuevo. Si una persona habla, la transición al juego con $3$ de la gente. De lo contrario, todos los que no hablan, habla en la siguiente oportunidad.

Si nadie habla, empezar de nuevo. Si una persona habla, la transición al juego con $3$ de la gente. De lo contrario, exactamente dos personas debe haber hablado en cada oportunidad; transición a dos juegos consecutivos con $2$ personas cada uno (en arbitrario, sino orden prescrito).

Este rendimientos

$$ \ell_4=1+(1-p)^4\ell_4+4(1-p)^3p\ell_3+6(1-p)^2^2(1+2\ell_2)+4(1-p)p^3(1+\ell_3)+p^4(1+\ell_4)\;. $$

The minimum can't be expressed in closed form; the following Sage program computes it:

var ('p,x')
l = [0,1,3]
for n in (3..4):
    [ln,p0] = find_local_minimum (solve (x == (1 + (1-p)^n * x + n * p * (1 - p)^(n-1) * l [n - 1] + (binomial (4,2) * p^2 * (1 - p)^2 * (1 + 2 * l [2]) if n == 4 else 0) + n * p^(n-1)*(1 - p) * (1 + l [n - 1]) + p^n*(1 + x)).full_simplify (),x) [0].rhs (),0,1)
    print p0, ln
    l = l + [ln]

The result is $p\simeq0.289723$ and $\ell_4\simeq7.061657$, which seems reasonable for an optimum.

Unfortunately this approach doesn't generalize beyond $n=4$. If "many" talk at both opportunities, say for $n=5$, then all we know is that $2$ talked at one and $3$ at the other, but we don't know which is which. Not only does this require a new kind of protocol to return to a more sharply defined state; what's worse is that it introduces time dependence. For instance, if we let one of the groups of $2$-or-$3$ people speak with probability $q$ and no one speaks, that changes the probabilities for which group is which, and thus presumably leads to a different optimal $p$ en el siguiente intento (o, posiblemente, incluso la hace preferible empezar con el otro grupo). Desde cada oportunidad que conduce a una diferente Bayesiana de la actualización de las probabilidades, en este momento la dependencia no es cíclica, por lo que no podemos expresar el principio de la longitud esperada en términos de sí misma y espera que las longitudes de pequeños juegos. Por lo tanto, parece poco probable que una estrategia óptima puede ser construido por la mano, o incluso por un número finito de cálculo, pero debería ser posible encontrar cerca de las mejores estrategias de cómputo descartando la información de estado después de un cierto tiempo.