A probability question related to extremal combinatorics

Question

$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same distribution $p$. If some $S_i$ is contained in $\cup_{j \neq i} S_j$, they all lose; else, they all win. What distribution $p$ maximizes the probability of winning?

I am actually only interested in the case where $n/k$ is an integer, in which case I would conjecture that the optimal distribution is for each person to pick a random subset with $n/k$ elements. I can prove this only for $k=2$, in which case it follows straightforwardly from Sperner's theorem.

Edit: JBL points out in the comments that its also easy to confirm the $n=k$ case of the conjecture in the previous paragraph.

Answer 1

Here's a quick thought about the case k=3. Let's suppose we go for the uniform distribution on sets of size cn. Then with very high probability the union of the first two sets has size about (2c-c^2)n, so that almost all the time the conditional probability that the third set is contained in the union is about $\binom{(2c-c^2)n}{cn}/\binom n{cn}.$

This isn't necessarily a very good heuristic, since if the first two sets are more disjoint, then it becomes much more likely that the third will be contained in the union, so the fact that the probability is small doesn't mean that one can disregard the possibility. But if one does the calculation more carefully, it doesn't seem obvious that the optimum will be at c=1/3.

Actually, for comparison let's look at the probability that the first two sets are disjoint and that their union contains the third. This is $\binom{(1-c)n}{cn}/\binom n{cn}$ multiplied by $\binom {2cn}{cn}/\binom n{cn}$. Again, we get an unpleasant enough number that I would be surprised if it were optimized at c=1/3.

So this isn't exactly an answer. It's just a suggestion that it ought to be instructive to think about which layer is best if you want to take the uniform distribution on some layer.

Answer 2

Marek Chrobak, Leszek Gasieniec, Dariusz Kowalski, and I looked at the following variant of this problem in section $8$ of this paper (published version):

Let $k$ be large. For what $n$, as a function of $k$, is it possible for the players to win with high probability?

Our original motivation here was a problem in communication: If you have a large number of identical sensors, each transmitting randomly to the same receiver, how long do you need to have them transmitting to guarantee that (with probability approaching $1$) each one transmits at least once without interference from the other sensors? The $S_j$ from your problem correspond to the set of times at which each sensor transmits.

It turns out that the sharp threshold here is $n=\frac{k \ln k}{(\ln 2)^2}$, in the following sense:

• If $n=ck \ln k$ and $c < \frac{1}{(\ln 2)^2}$, then the players lose with probability $1-o(1)$ as $k$ tends to infinity, regardless of what $p$ is. Here the $o(1)$ error term is a function depending on $c$ and $k$ (but not on $p$) that tends to $0$ as $k$ tends to infinity for any fixed $c$.

• If $n=c k \ln k$ and $c > \frac{1}{(\ln 2)^2}$, then the players can win with probability $1-o(1)$.

  The distribution $p$ we use for the second part is to divide the interval into subintervals of length $\frac{k}{\ln 2}$, and have players choose exactly one number from each subinterval. This should be pretty much equivalent to choosing uniform subsets of size $\frac{n}{k/\ln 2}$ -- the main reason we used subintervals was to make the calculation cleaner.

So in a sense, choosing uniform subsets of a given size is, asymptotically, optimal in this regime of $n$ and $k$. The size just ends up being slightly smaller than $n/k$.