20
$\begingroup$

$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.

$\endgroup$
  • 2
    $\begingroup$ I'm not sure what "replaced" means in this context; they are not picking balls out of a common bin. Each person independently picks a subset of $1,2,\ldots,n$. $\endgroup$ – alex Jul 14 '10 at 23:44
  • 2
    $\begingroup$ Regardless of n/k it seems to me that the most likely optimum is where each randomly picks a set of size $\lfloor n/2 \rfloor$. If everyone is always picking sets of the same size, then they lose only when two of them pick the same set, so it makes sense to have as many sets available as possible. $\endgroup$ – Michael Albert Jul 15 '10 at 1:17
  • 4
    $\begingroup$ @Michael Albert, that's not true: if we're picking pairs and we get {1, 2} and {1, 3} and {2, 3}, we lose. $\endgroup$ – JBL Jul 15 '10 at 1:19
  • 4
    $\begingroup$ (In fact, for $n = k$ I think it shouldn't be hard to show that a uniform distribution over singletons is optimal, since any positive probability on a non-singleton is completely wasted, no?) $\endgroup$ – JBL Jul 15 '10 at 1:57
  • 3
    $\begingroup$ The conjecture is false for $k=3$. If $n=6$ it's better to choose random singletons (the probability to lose is $4/9$) than random doubletons (the probability to lose is, counting conditionally on the number of elements in the intersection of doubletons of the first two players, $\frac1{15} + \frac8{15}\times \frac{9}{15} + \frac{6}{15}\times \frac{6}{15} = \frac{41}{75}$, unless I messed up). In fact, for $n$ big enough, when $k=3$ it is better to pick random singletons than random doubletons. $\endgroup$ – zhoraster Oct 17 '10 at 16:07
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks; maybe I was too hasty in conjecturing an answer. I'll write some maple code to evaluate the probability explicitly for various $n,k$. $\endgroup$ – alex Jul 16 '10 at 1:46
4
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.