Optimal strategy for game of 'online sorting' into a poset

Question

Consider a single-player game played with an arbitrary finite poset, and a random number generator with a known distribution:

Each turn, the RNG produces a number, and the player must assign that number to an element of the poset as a label. A new label may replace one already present, and each individual assignment need not respect the partial ordering. However, the goal of the player is to minimize the expected number of turns needed to label all elements of the poset such that the labels are consistent with the relation.

Is there a demonstrably optimal strategy more elegantly expressible than a brute force game tree analysis? (particularly in the case where the RNG has a continuous distribution?)

Has this or a similar process already been considered in some other guise? \

Edit to add: Do posets with the same counts of elements and linear extensions necessarily share a common optimal expected time to completion?

Answer 1

I worked out the case of a two-element chain and the uniform distribution on [0,1]. This was more complicated than I expected, and although the same sort of approach should allow one to compute chains of length 3, 4, 5, etc., it looks messy. However, maybe someone else will see a clean way to argue the general case.

Let $r_1, r_2, \ldots$ denote the sequence of random numbers generated. It is pretty clear that the optimal algorithm for labeling a two-element chain is the following:

If $r_1>1/2$ then label the larger element $r_1$; otherwise label the smaller element $r_1$. On each subsequent turn, if labeling the unlabeled element with $r_i$ wins at once, then do so; otherwise, relabel the already-labeled element with $r_i$.

Let $N$ be the number of turns; then $N$ is a random variable, and we want to find the expected value of $N$. So we need to compute $\Pr(N=k)$ for each integer $k$. There are two ways that $N$ can equal $k$: Either $$1/2 \le r_1 \le r_2 \le \cdots \le r_{k-1} > r_k $$ or $$1/2 \ge r_1 \ge r_2 \ge \cdots \ge r_{k-1} < r_k.$$ By symmetry we may focus on the latter case and multiply by 2. The calculation splits into two cases depending on whether $r_k > 1/2$ or $r_k \le 1/2$. The case $r_k > 1/2$ has probability $${(1/2)^{k-1}\over (k-1)!} \cdot {1\over 2}$$ where $(1/2)^{k-1}$ is the probability that $r_1, \ldots, r_{k-1}$ are all less than $1/2$ and $1/(k-1)!$ is the probability that they are in decreasing order and the final $1/2$ is the probability that $r_k >1/2$. The case $r_k \le 1/2$ has probability $$ {1 \over 2^k} \cdot {k-1\over k!}$$ where $1/2^k$ is the probability that $r_1, \ldots, r_k$ are all less than $1/2$ and $(k-1)/k!$ is the probability that they are in decreasing order except that $r_{k-1} > r_k$. So the expected value of $N$ is $$E[N] = 2 \sum_{k\ge 2} k \cdot \left( {(1/2)^{k-1}\over (k-1)!} \cdot {1\over 2} + {1 \over 2^k} \cdot {k-1\over k!}\right) = 2\exp(1/2) - 1 \approx 2.29744.$$

To analyze the three-element chain, it seems that one will need to consider partially labeled posets. The above analysis easily generalizes to show that the expected number of turns to finish labeling a two-element chain whose smaller element is already labeled with some number $x<1/2$ is $$\sum_{k\ge 1} k \cdot \left( {x^{k-1}\over (k-1)!} \cdot {(1-x)} + x^k \cdot {k-1\over k!}\right) = \exp(x). $$ However, as I said, extending the analysis to larger chains looks messy.