Data-Driven Decision Processes - Whiteboard Talk

Speakers: Sahil Singla (Georgia Tech) and Ola Svensson (EPFL)

Abstract: Online contention resolution schemes is a general technique for Bayesian selection problems such as prophet inequalities, oblivious posted pricing mechanisms, and stochastic probing models.

In this tutorial we are going to introduce these techniques in the simplest single item setting and then discuss how to generalize it to the more rich matroid constrained setting. We also point out close connections to matroid secretary and matroid prophet problems.

References: 
Moran Feldman, Ola Svensson, Rico Zenklusen: Online Contention Resolution Schemes with Applications to Bayesian Selection Problems. SIAM J. Comput. 50(2): 255-300 (2021)

Euiwoong Lee, Sahil Singla: Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. ESA 2018: 57:1-57:14

Shaddin Dughmi: Matroid Secretary Is Equivalent to Contention Resolution. ITCS 2022: 58:1-58:23