Sequential Decision Making: Prophets and Secretaries

Lecture 1: Sequential Decision Making: Prophets and Secretaries I 
Lecture 2: Sequential Decision Making: Prophets and Secretaries II 
 

This series of talks is part of the Algorithms and Uncertainty Boot Camp. Videos for each talk area will be available through the links above.

Speaker: Matt Weinberg, Princeton University

In this tutorial, I'll cover two popular versions of online selection problems - secretary problems and prophet inequalities. In the vanilla version of both, elements of a set are revealed to you one at a time. When an element is revealed, you learn its "weight," and must immediately and irrevocably decide whether to accept, claiming its weight as your reward but forgoing the opportunity to see the remaining elements, or reject, bypassing the element forever (but you will see future elements). In secretary problems, the weights are chosen by an adversary and the elements are revealed in a uniformly random order. In prophet inequalities, the weights are drawn independently from known distributions, and an adversary chooses the order (and distributions). Your goal is to maximize your expected reward.

There is a ton of recent work solving multiple-choice online selection problems, where you may now accept multiple elements, but are subject to some feasibility constraints (often related to matroids). The tutorial will cover in detail the solutions to both vanilla problems (Dynkin for the secretary problem and Krengel-Sucheston for prophet inequalities), as well as a subset of these recent works.