Secretaries with Advice

Understand

The secretary problem is probably the purest model of decision making under uncertainty.

• In this paper we ask which advice can we give the algorithm to improve its success probability? We propose a general model that unifies a broad range of problems: from the classic secretary problem with no advice, to the variant where the quality of a secretary is drawn from a known distribution and the algorithm learns each candidate's quality on arrival, to more modern versions of advice in the form of samples, to an ML-inspired model where a classifier gives us noisy signal about whether or not the current secretary is the best on the market.
• Our main technique is a factor revealing LP that captures all of the problems above.
• We use this LP formulation to gain structural insight into the optimal policy.