Prophet Secretary Through Blind Strategies 2: No Stopping Strategy Can Guarantee More Than √3 − 1 of the Prophet's Expected Maximum in Random OrderResearch Paper
Motivation
In a prophet inequality a gambler sees the realizations of independent nonnegative random variables one at a time and must decide irrevocably, at each step, whether to stop and keep the current value. Her performance is compared with that of a prophet who sees everything in advance and takes the maximum. The ratio between the two is the standard benchmark for online selection, and through the correspondence between threshold stopping rules and posted prices it governs the efficiency of sequential posted-price mechanisms in algorithmic mechanism design.
The constant depends on the order in which the values arrive. In adversarial order the best guarantee is (Krengel and Sucheston; Samuel-Cahn). For independent and identically distributed values it is about (Hill and Kertz 1982 gave the upper bound; Correa, Foncea, Hoeksma, Oosterwijk and Vredeveld 2017 proved it tight). The prophet secretary problem sits between these two: the distributions may differ, but the values arrive in a uniformly random order.
Timeline.
- 2015: Esfandiari, HajiAghayi, Liaghat and Monemizadeh introduce the prophet secretary problem and give a guarantee of with nonincreasing thresholds.
- 2018: Ehsani, Hajiaghayi, Kesselheim and Singla obtain with a single threshold and random tie-breaking.
- 2018: Azar, Chiplunkar and Kaplan beat slightly. They also show that deterministic distribution-insensitive algorithms cannot beat .
- 2019 (arXiv:1807.07483v2): Correa, Saona and Ziliotto prove a guarantee of for blind strategies. They also prove the upper bound of for all strategies, the subject of this mission.
Before this bound no separation between the prophet secretary problem and the i.i.d. prophet inequality was known.
Setting
An instance with variables is a family of laws on . The values are independent. A permutation of , uniform and independent of the values, fixes the arrival order: at time the gambler sees which variable arrives and its value .
A strategy decides at each time whether to stop. The decision may use the observed history and an independent seed , uniform on , and must depend on them measurably. These are the randomized stopping times of the gambler's information. The gambler knows the distributions, so a strategy may be chosen after the instance. The reward is : the value at the first stop, and if she never stops. The value of a strategy is , and the prophet's value is .
A strategy guarantees if on every instance.
The §5 instance has variables, for and . Each of equals with probability and otherwise, and . For , the time- rule accepts a value whenever one appears, and accepts exactly when it arrives at time or later.
Formalization targets
Goal: Theorem 1.3 (p. 4)
For every there is an instance with on which every strategy satisfies
The instance comes first and all strategies second. This is what "no strategy can guarantee more than " means once strategies may depend on the distributions. Universally quantifying a fixed strategy first would describe a weaker gambler.
Milestones (all from §5, p. 19)
- The prophet's value on the §5 instance:
- The elementary bound , which is a published platform theorem ( for ).
- The conditional values of the time- rule given that arrives at position : for , and for .
- For every strategy on the §5 instance,
At the ratio of milestones 4 and 1 tends to .
Significance
The bound shows that random order with non-identical distributions is strictly harder for the gambler than i.i.d. values: the constant cannot exceed , which is below . It improves the bound of Azar, Chiplunkar and Kaplan and extends it from deterministic distribution-insensitive algorithms to all strategies, including randomized ones that know the distributions. With the guarantee of the same paper, it brackets the optimal prophet secretary constant in . Later work raised the lower end, but the exact value is still open.
The result is proved in the paper. It is not formalized anywhere we know of, and no prophet secretary statement exists on the platform. Formalizing it means writing down a general model of randomized stopping strategies in random order, which other random-order results can reuse. The heart of the proof is a dynamic-programming argument that is easy to state informally and has never been machine-checked. The finite- bound of milestone 4, with an explicit constant in place of , is also a welcome contribution.
Difficulty
Computing the value of one good strategy on the §5 instance is routine (milestone 3). The goal, though, quantifies over every strategy, including randomized ones that observe identities and the whole history. The paper's sentence "Solving the dynamic programming, the algorithm picks the value if and only if it appears at time or later" carries the whole reduction. It requires:
- showing that accepting a value is always optimal;
- showing that accepting a never helps;
- showing that randomization does not help;
- showing that the only relevant state is the time and whether has already passed.
Bounding a few natural strategies does not suffice. The asymptotic analysis must also be made uniform in the strategy, so that a single constant in works for all of them.
Formalization scope
- Indices are 0-based. The paper's is coordinate of
Fin (n+1), and isFin.last n. - Independence is built in through the product measure
Measure.pi μ. - The uniform order is the average over all permutations.
- The seed is uniform on (
volume.restrict (Icc 0 1)). - Expectations are lower Lebesgue integrals in of
ENNReal.ofRealof the reward, so no integrability hypotheses appear. - A conditional expectation given is written in joint form, as times the expectation on that event.
- The strategy class (
Strategy N) is the class of all measurable decision rules on the full observed history plus an independent seed, and it is quantified after the instance. Restricting it to threshold rules, time- rules or deterministic rules would make the goal a different, weaker theorem; that restriction is ruled out. The class is nonempty, and its measurability requirement is satisfiable:jRulecarries its proof. - The instance is not required to have continuous laws. The paper assumes continuity only for its blind strategies, and the §5 instance has atoms.
- The goal adds , which the §5 instance satisfies; this excludes a degenerate instance.
- §5 writes , but the maximum is over all variables, since the formula contains . The Lean states the corrected reading.
- The PDF used is arXiv:1807.07483v2. Pages are PDF pages, because the preprint prints no page numbers.
Reusable infrastructure includes the random-order stopping model, the reward of the first stop, and the dynamic-programming reduction for a single deterministic variable. Contributions are welcome on any milestone, and on an explicit in milestone 4.
Selected references
- J. Correa, R. Saona, B. Ziliotto, Prophet Secretary Through Blind Strategies, arXiv:1807.07483v2, 2019; Mathematical Programming, 2021. https://arxiv.org/abs/1807.07483
- S. Esfandiari, M. HajiAghayi, V. Liaghat, M. Monemizadeh, Prophet Secretary, ESA 2015; SIAM J. Discrete Math. 31(3), 2017. https://doi.org/10.1137/15M1029394
- S. Ehsani, M. Hajiaghayi, T. Kesselheim, S. Singla, Prophet Secretary for Combinatorial Auctions and Matroids, SODA 2018. https://arxiv.org/abs/1710.11213
- Y. Azar, A. Chiplunkar, H. Kaplan, Prophet Secretary: Surpassing the 1 − 1/e Barrier, EC 2018. https://arxiv.org/abs/1711.01834
- T. P. Hill, R. P. Kertz, Comparisons of stop rule and supremum expectations of i.i.d. random variables, Annals of Probability 10(2), 1982. https://doi.org/10.1214/aop/1176993772
- J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, T. Vredeveld, Posted Price Mechanisms for a Random Stream of Customers, EC 2017. https://doi.org/10.1145/3033274.3085137