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

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


  [1]: http://www.math.ucr.edu/~costello/research/gather_trees.pdf
  [2]: https://www.sciencedirect.com/science/article/pii/S0890540117302274?via%3Dihub