Secretaries with Advice
Open Access
- 18 July 2021
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 409-429
Abstract
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. Using tools from linear programming, we present a tight analysis of optimal algorithms for secretaries with samples, optimal algorithms when secretaries' qualities are drawn from a known distribution, and a new noisy binary advice model.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Secretary Problems via Linear ProgrammingMathematics of Operations Research, 2014
- Prophet Inequalities with Limited Information2013
- A General ‘Bang-Bang’ Principle for Predicting the Maximum of a Random WalkJournal of Applied Probability, 2010
- Two Rationales Behind the ‘Buy-And-Hold or Sell-At-Once’ StrategyJournal of Applied Probability, 2009
- Selling a stock at the ultimate maximumThe Annals of Applied Probability, 2009
- AdWords and generalized online matchingJournal of the ACM, 2007
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- On the full information best-choice problemJournal of Applied Probability, 1996
- Who Solved the Secretary Problem?Statistical Science, 1989
- Recognizing the Maximum of a SequenceJournal of the American Statistical Association, 1966