Fr. 28.02.2020, Oberseminar Mathematische Optimierung
Thema: Sample-Based Prophet Inequalities. Referent: Dr. Kevin Schewior (Universität zu Köln), Raum: ENC-D 201, Zeit: 10:00 Uhr c.t.
Oberseminar Mathematische Optimierung
Sample-Based Prophet Inequalities.
Freitag, den 28.02.2020, 10:00 Uhr c.t., Raum: ENC-D 201,
Referent: Dr. Kevin Schewior (Universität zu Köln)
Abstrakt: Consider a gambler who observes independent draws from a known sequence of positive-valued distributions. Upon observation of any value, the gambler has to decide whether to keep it as final reward or to discard it forever. The prophet inequality (Krengel, Sucheston and Garling 1978) states that there is a strategy whose expected accepted value is at least half of the expected maximum of all draws (the prophet's value). We first review the recent result (Wang 2018) that the following simple strategy also achieves the same ratio: Sample one value from each of the distributions, and set their maximum as a threshold for accepting any value. We then turn to the case in which all distributions are identical. It is a simple corollary from results on the secretary problem that a ratio of 1/e is achievable without samples (again with respect to the expected maximum). We show using Ramsey's Theorem that this is best possible. We also show that knowing O(n^2) samples is essentially as good as knowing the distribution, meaning that a ratio of 0.745 can be approached in that case (Correa et al. 2017). For the remainder of the talk, we work towards understanding the case with O(n) samples, but, unlike for the distinct-distributions case, open questions remain. All results without references are joint work with José Correa, Paul Dütting, and Felix Fischer.