Abstract:
A common tension in market scenarios is choosing the right timing to commit to a decision. This tension is captured by the mathematical literature of optimal stopping theory, within two models that have become to be known as the secretary problem and the prophet inequality. In these models, a sequence of originally-unknown values arrive one by one. Upon arrival, the online algorithm observes the value and should decide whether or not to accept it. In secretary settings, the value sequence is arbitrary, but the values arrive in a uniformly random order. In prophet settings, every value is drawn from a known probability distribution, but the arrival order is arbitrary.

In this talk I will shortly review the basic settings of secretary and prophet, and will present extensions to graph matching. These include matching in bipartite graphs with 1-sided vertex arrival and matching in general graphs (with general arrival).

Joint work with Tomer Ezra, Nick Gravin, and Zhihao Tang.

Go to recording (introduction of speaker starts at 5:10, lecture starts at 10:00)