Optimal Strategy Game of Communicating without Overlap

Question

Today, I had a conversation which proceeded very poorly; indeed, I had this conversation with $n$ people, including myself, and everyone had something to say. Problem was that, for an unreasonably long time, it was always two or more people trying to speak at once - and everything was indecipherable. Then, people backed off and there were periods when no one was talking - only to trigger a few people to try to jump into the conversation, and overlap again! Eventually, by pure chance, one person got to talking alone (and never had to talk again), and, slowly but surely, everyone got their turn to speak.

Now, being the mathematician that I am, I figured, hey, I can solve this problem. I want to give all $n$ people a sheet of paper describing the rules of conversation - a simple solution would be to assign each a time to speak, but that's not fair to the people who have to wait. So, I want to give all $n$ people the same set of rules to follow. I assume I recognize that, this means, at the first opportunity to speak, everyone will speak with equal probability, and it seems likely that there will be overlap - but then the strategies can differentiate based on the results of that first opportunity (though these people are poor listeners; from each opportunity, they only know whether they tried to speak, and whether there were multiple people, a single person, or no one speaking).

To be very formal, define the problem as follows:

A conversation is a series of discrete opportunities to talk, at which each player may choose either to attempt to talk, or to be silent. Anyone who successfully talks without interruption will not attempt to speak again. The conversation ends when everyone has spoken. The history of a conversation, will be a finite sequence of the three possible outcomes of an opportunity (no one talks, one person talks, many people talk) - it does not distinguish between $2$ and $3$ people talking. A strategy is a map taking the history of a conversation, and determining whether a given player will talk. A mixed strategy is a probability distribution over of the set of possibly strategies, and represents, essentially, a non-deterministic strategy.

And my question is thus:

For what mixed strategy is the expected length of the conversation (measured in opportunities missed) minimized when $n$ people play the strategy against itself?

What I know so far are the following strategies:

• $n=1$: The person should talk at the first opportunity. The conversation will have length $1$ and will be very lonely.

• $n=2$: The people should maximize the probability that exactly one of them talks at each turn - and, if they both choose to talk or both not to, they gain no useful information about the other, and hence should continue with the same strategy. Thus, the best strategy is to talk with probability $\frac{1}2$ until one of them is successful, after which the other one speaks, yielding an expected length of $3$.

• $n=3$: This one is trickier and I don't have a proof. I'm fairly certain that the following strategy is locally optimal, and I suspect that it is the best, but I'm not sure. We use three states for which a person can be in - everyone starts in state A:

  (State A) Speak with probability $p$ at the next opportunity. If no one speaks, remain in state A. If one person speaks, transition to the two person game. If many people, including yourself, speak, go to state B. If many people, not including yourself speak (implying the two others spoke), go to state C.

  (State B) Don't speak at the next opportunity, then transition to state A if no one speaks. If one person speaks, transition to the two state game. (No more than one person will ever speak in this state)

  (State C) Speak at the next opportunity; you are guaranteed to be successful.

The idea here is that we either escape the dilemma when one person speaks out of the three, or when two people do (and then the other person talks while the two who overlapped are in state B, silent). Using that the expected length of a conversation for two people is $3$, we can find the expected length $\ell$ of this conversation as $$\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)$$ which yields the minimum, according to 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.$$

Given that the problem of characterizing the optimal strategy for arbitrary $n$ may be extremely difficult, I would not expect answers to find one (but, if you find one, or have something you suspect to be optimal, I'd love to see it)- indeed, even the case of $n=4$ is interesting to me, since I have no handle on what the strategy might be.

(The account given in this post is purely fictional; any resemblance to real conversations is purely coincidental)

Answer 1

I spent quite some time today trying to improve on your solution for $n=3$. Not only did I not come up with anything better; I convinced myself that the tradeoff you make in gaining certainty about the history at the cost of wasting an opportunity in case all three people spoke is probably optimal.

I think the following strategy for $n=4$ (inspired by yours) is also likely to be optimal:

Speak with probability $p$. If no one speaks, try again. If one person speaks, transition to the game with $3$ people. Otherwise, everyone who didn't speak speaks at the next opportunity.

If no one speaks, start over. If one person speaks, transition to the game with $3$ people. Otherwise, exactly two people must have spoken at each opportunity; transition to two consecutive games with $2$ people each (in arbitrary but prescribed order).

This yields

$$ \ell_4=1+(1-p)^4\ell_4+4(1-p)^3p\ell_3+6(1-p)^2p^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 $q$ on the next try (or possibly even renders it preferable to start with the other group). Since every opportunity leads to a different Bayesian update of the probabilities, this time dependence isn't cyclic, so we can no longer express the initially expected length in terms of itself and expected lengths of smaller games. Thus, it seems unlikely that an optimal strategy can be constructed by hand, or even by a finite computation, but it should be possible to find near-optimal strategies computationally by discarding state information after a certain time.