The secretary problem bound for posets with a fixed number of maximal elements

From papers

Let (P,)(P,\prec) be a poset with kk maximal elements. Define

pk={1e,k=1,1kk1,k>1.p_k=\begin{cases}\frac{1}{e},&k=1,\\[0.3ex]\sqrt[k-1]{\frac{1}{k}},&k>1.\end{cases}

Secretary problem conjecture. There is an algorithm for the secretary problem on (P,)(P,\prec) that is successful with probability at least pkp_k.

The bound is proved in the source for posets of width kk and is expected to extend to all posets with kk maximal elements; it is not known from the supplied text whether the same algorithm works universally or another algorithm depending only on kk is required.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Bryn Garrod and Robert Morris, “The secretary problem on an unknown poset”, arXiv:1107.1379 (2012).

Solutions 0

No solutions have been posted yet.