Prophet Secretary and Matching: the Significance of the Largest Item

The prophet secretary problem is a combination of the prophet inequality and the secretary problem, where elements are drawn from known independent distributions and arrive in uniformly random order. In this work, we design 1) a 0.688-competitive algorithm, that breaks the 0.675 barrier of blind strategies (Correa, Saona, Ziliotto, 2021), and 2) a 0.641-competitive algorithm for the prophet secretary matching problem, that breaks the 1 — 1/e ≈ 0.632 barrier for the first time. Our second result also applies to the query-commit model of weighted stochastic matching and improves the state-of-the-art ratio (Derakhshan and Farhadi, 2023).