Secretaries and Prophets: Problems in Decision-Making Under Uncertainty

Abstract

In this honors thesis, we will provide a guide to the most important life questions. How do you hire the best employee or choose the best romantic partner? What's the strategy to win most often at a gambling game? How do you sell things for a lot of money? Although seemingly unrelated, these settings are united by a common theme: irreversible and time-sensitive decision-making under uncertainty about future outcomes. Referred to as online selection problems, they comprise a fascinating field at the intersection of probability theory and theoretical computer science. Along the way to helping you live your best life in an uncertain world, we will exposit the interesting mathematics of this area and present novel results of our research.