Secretaries with Advice

Paul Dütting (), Silvio Lattanzi (), Renato Paes Leme () and Sergei Vassilvitskii ()
Additional contact information
Paul Dütting: Google Research, 8002 Zurich, Switzerland
Silvio Lattanzi: Google Research, 8002 Zurich, Switzerland
Renato Paes Leme: Google Research, New York, New York 10011
Sergei Vassilvitskii: Google Research, New York, New York 10011

Mathematics of Operations Research, 2024, vol. 49, issue 2, 856-879

Abstract: The secretary problem is probably the purest model of decision making under uncertainty. In this paper, we ask which advice we can 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, more modern versions of advice in the form of samples, and a machine-learning inspired model where a classifier gives us a noisy signal about whether the current secretary is the best on the market. Our main technique is a factor-revealing linear program (LP) that captures all of these problems. 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 optimal algorithms for a new noisy binary advice model.

Keywords: Primary: 60G40; secretary problem; machine learning advice; prophet inequality (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.1384 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:856-879

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().