Does the Multisecretary Problem Always Have Bounded Regret?
Robert Louis Bray · arXiv (Cornell University) · 2019
Arlotto and Gurvich (2019) showed that the regret in the multisecretary problem is bounded in the number of job openings, $ n $, and the number of applicants, $ k $, provided that the applicant valuations are drawn from a distribution with finite support. I show that this result does not hold when applicant valuations are drawn from a standard uniform distribution. In this case, the regret is between log(n)/16 - 1/4 and log(n+1) / 8, when k = n/2 and n >= 16. I establish these bounds by decomposing the regret into a sum of expected myopic regrets. This decomposition also yields a shorter proof of Arlotto and Gurvich's original result.