Multiple-Choice Secretary Problem with Predictions
Organizations: University of North Texas · University at Buffalo
Abstract
We study the multiple-choice secretary problem, in which candidates arrive in uniformly random order and the goal is to select at most candidates to maximize their total value. We consider a setting where predictions of individual candidate values are available before any candidate arrives. Fujii and Yoshida's Learned Kleinberg algorithm achieves competitive loss , where is the selection capacity and is the maximum multiplicative prediction error. We remove the logarithmic factor through a sharper analysis of the same switching algorithm with a retuned threshold. The resulting competitive ratio is at least . In particular, exact predictions () achieve the offline optimum on every arrival order.
Figures & tables
| Work | Prediction | Competitive guarantee |
|---|---|---|
| Kleinberg [ 14 ] | None | |
| Qiao–Zhang [ 17 ] | None | with memory |
| Fujii–Yoshida [ 11 ] | Candidate values | |
| This paper | Candidate values |
Sequential Decision Making
Sequential Decision Making studies how to choose actions over time when outcomes, information, resources, or goals can change.
See all 149 papers