Fishing For Better Constants: The Prophet Secretary Via Poissonization
share
Given n random variables X_1, … , X_n taken from known distributions, a gambler observes their realizations in this order, and needs to select one of them, immediately after it is being observed, so that its value is as high as possible. The classical prophet inequality shows a strategy that guarantees a value at least half (in expectation) of that an omniscience prophet that picks the maximum, and this ratio is tight. Esfandiari, Hajiaghayi, Liaghat, and Monemizadeh introduced a variant of the prophet inequality, the prophet secretary problem in [1]. The difference being that that the realizations arrive at a random permutation order, and not an adversarial order. Esfandiari et al. gave a simple 1-1/e ≈ 0.632 competitive algorithm for the problem. This was later improved in a surprising result by Azar, Chiplunkar and Kaplan [2] into a 1-1/e + 1/400 ≈ 0.634 competitive algorithm. In a subsequent result, Correa, Saona, and Ziliotto [3] took a systematic approach, introducing blind strategies, and gave an improved 0.669 competitive algorithm. Since then, there has been no improvements on the lower bounds. Meanwhile, current upper bounds show that no algorithm can achieve a competitive ratio better than 0.7235 [4]. In this paper, we give a 0.6724-competitive algorithm for the prophet secretary problem. The algorithm follows blind strategies introduced by [3] but has a technical difference. We do this by re-interpretting the blind strategies, framing them as Poissonization strategies. We break the non-iid random variables into iid shards and argue about the competitive ratio in terms of events on shards. This gives significantly simpler and direct proofs, in addition to a tighter analysis on the competitive ratio. The analysis might be of independent interest for similar problems such as the prophet inequality with order-selection
READ FULL TEXT