2024/11/02 by Chen, Ziyun, Huang, Zhiyi, Li, Dongchen +1 · 3 citations
#Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2411.01191
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).