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

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