Abstract
The elements of a finite nonempty partially ordered set are exposed at independent uniform times in [0, 1] to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector's task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability 1/e and that this is best possible. We describe a strategy for the general problem that achieves success probability at least 1/e for an arbitrary partial order.
| Original language | English |
|---|---|
| Pages (from-to) | 504-507 |
| Number of pages | 4 |
| Journal | Electronic Communications in Probability |
| Volume | 15 |
| Publication status | Published - 2010 |
| MoE publication type | A1 Journal article-refereed |
Keywords
- Best choice problem
- Partial order
- Secretary problem