8
$\begingroup$

Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:

  • Alice picks $m$ sets, each of which has $k$ items.
  • Bob colors some items in green.
  • Bob's score is the number of distinct singletons, where a singleton is defined as a green item contained in a set in which all other $k-1$ items are uncolored (if there are several different sets with the same single green item, only one is counted towards Bob's score).

What is the highest score Bob can guarantee to himself, as a function of $m$ and $k$?

  • A lower bound is $\Omega(m^{1/k})$. Proof. Suppose Bob colors each item in the world (=the union of all Alice's sets) with probability $p$, independently of the others. The probability of each item to be a singleton is: $p\cdot(1-p)^{k-1}$; this is maximized when $p=1/k$, and the maximum is at least $1/(e\cdot k)$. Then, the expected number of singletons is at least $n/(e\cdot k)$, where $n$ is the world size. Therefore, Bob can always guarantee to himself a score in $\Omega(n/k)$. The number of sets $m$ is at most ${n \choose k}$ which is at most $(n\cdot e/k)^k$, so $n \in \Omega(k\cdot m^{1/k})$, so Bob's score is in $\Omega(m^{1/k})$.

  • An upper bound is $O(k\cdot m^{1/k})$. Proof. Alice can choose $n$ such that $m={n \choose k}$, and select all $k$-element subsets of the integers $1,\ldots,n$. Bob can get at most $n$ singletons. In fact he can get exactly $n-k+1$ singletons, by coloring all items except $1,...,k-1$. So Bob's score is in $O(n) = O(k\cdot m^{1/k})$.

So what is the correct expression? Can Alice always force Bob to get at most $O(m^{1/k})$? Or can Bob always get at least $\Omega(k\cdot m^{1/k})$?

$\endgroup$
  • $\begingroup$ Note: it is important that Bob's score is a function of $m$ and $k$, and not of the world size $n$. If Bob's score were a function of $n$ and $k$, then both the upper and lower bounds would have been $n/k$: lower bound same as above, and upper bound when Alice selects $n/k$ disjoint sets. $\endgroup$ – Erel Segal-Halevi May 2 '17 at 14:28
  • 3
    $\begingroup$ Clarification in case anybody read this the same way as me: we are counting green points with some property, not $k$-sets containing exactly one green point. $\endgroup$ – Ben Barber May 2 '17 at 15:03
  • $\begingroup$ @BenBarber yes, if there are several different sets with the same single green item, only one is counted towards Bob's score. Added clarification. $\endgroup$ – Erel Segal-Halevi May 3 '17 at 7:15
  • $\begingroup$ Doesn't the probability for an item $x$ to be a singleton depend on the number $m_x$ of sets (chosen by Alice) that contain it? In each of these, it has a probability of $p(1-p)^{k-1}$ of 'attaining singleton status through this set'. The chance of being singleton should be higher than that (depending on the structure of the sets chosen by Alice, though). $\endgroup$ – monkeymaths May 3 '17 at 12:48
  • $\begingroup$ @monkeymaths yes, you are right, this is only a lower bound. Maybe the same probabilistic algorithm can be better analyzed to give a better lower bound. $\endgroup$ – Erel Segal-Halevi May 3 '17 at 12:57
2
$\begingroup$

None of those seems correct if $k\ge \log m$. Consider your construction described for the upper bound, except that we make divide all elements into $s$ groups of size $\frac kt$, and Alice picks the $\binom st$ sets that contain exactly $t$ groups. Then, as you've mentioned, Bob's score is at most $s$, since he can win at most one singleton per group. In fact, Bob's score is $s-t+1$, which is independent of $k$. I'm not sure what choice of $s$ and $t$ optimizes this, but the best score should be around $\log m$, provided that $k\ge \log m$. Of course, this leaves the problem open and interesting for small $k$.

$\endgroup$
  • $\begingroup$ If $k\geq \log_2{m}$, then $m^{1/k}\leq 2$, so my upper bound gives $O(k)$. So your construction improves this to $O(\min(k,\log{m}))$, right? $\endgroup$ – Erel Segal-Halevi May 3 '17 at 12:49
  • $\begingroup$ @Erel I think so. $\endgroup$ – domotorp May 3 '17 at 13:01
  • $\begingroup$ This construction doesn't actually improve on Erel's construction. Take $m= { s \choose t}$ for some $t \leq k$. Let $n$ be so that $n-k = s-t$, in particular, $n \geq s$. Then we have ${ s\choose t} = { s \choose s-t} = { s \choose n-k} \leq {n \choose n-k} = {n \choose k}$ so Erel's construction gets the same upper bound with a larger $m$. Instead, your improvement comes from a better estimate of the inverse binomial function in this range. $\endgroup$ – Will Sawin May 4 '17 at 17:32
  • $\begingroup$ @Will I thought $m$ and $k$ were both parameters in which we try to optimize. $\endgroup$ – domotorp May 5 '17 at 0:06
  • $\begingroup$ @WillSawin Where did your answer go? I thought it was (almost) correct. $\endgroup$ – Erel Segal-Halevi May 6 '17 at 17:37

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.