Two players play as follows. Player one chooses a secret finitely supported probability distribution $P$ on $ω_k$ (or another known set with $\aleph_k$ elements), and randomly takes $n+1$ samples using $P$, sending the first $n$ samples to the second player, while keeping the last sample, $x$, hidden. The second player responds with a finite set $S$ and wins iff $x∈S$. What is the highest/supremum probability $p$ such that the second player has a strategy that wins with probability $≥p$?

Note that allowing mixed player 2 strategies would not change the answer since one can send an $S$ that approximately covers the possibilities of a given mixed strategy.

The problem is inspired by Learnability can be undecidable in Nature Machine Intelligence. Note that the second player tries to learn about $P$ from a finite sample. The paper notes that if the data points are real numbers, then the independence (from ZFC) of the size of the continuum leads to undecidability about learnability. Now in practice, in machine learning, real numbers are not used in the discrete topology (and furthemore, player 2 strategies here use the axiom of choice), but it is still an interesting abstract problem.

I expect that the answer is $\max(0,(n-k)/(n+1))$, but I only have a proof that $p$ is at least this high. A second player strategy is as follows. Of the $n$ given ordinals $ < ω_k$, pick the largest one $α$. Choose a well-ordering of $α+1$ of length $≤ω_{k-1}$, and using it, apply the $ω_{k-1}$ strategy. In the base case (finite $α$), set $S=α+1$ (i.e. all natural numbers $≤α$). With probability at least $n/(n+1)$, we have $x≤α$, and by induction we get $(n-k)/(n+1)$ as lower bound.