Robust Online Selection with Uncertain Offer Acceptance: The Best Robust Ratio Equals the Value of an Explicit Linear Program, and Its Optimal Solutions Give Optimal PoliciesResearch Paper
In the classical secretary problem a decision maker sees candidates in random order, learns only how each compares with those already seen, and must decide irrevocably whether to hire. Many real selection processes add one more source of uncertainty: the chosen candidate may refuse. Job offers are declined, customers ignore promotions, admitted students…