BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T052419Z
UID:Seminar-EcCo-604@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20190605T130000
DTEND:20190605T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Nicos Protopapas: Prophet Inequalities for Independent Random Variables from an Unknown Distribution\n\nA central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables drawn independently from a distribution F, the goal is to choose a stopping time ? so as to maximize a guarantee ? such that for all distributions F, the expected value on stopping at time ?, is at least ? times greater than the expected value in hindsight. \nWhat makes this problem challenging is that the stopping decision may only depend on the values of the random variables and on the distribution F. For quite some time the best known bound for the problem was ? ? 1 ? 1/e ? 0.632 [Hill and Kertz, 1982]. Only recently this bound was improved by Abolhassani et al. [2017], and a tight bound of ? ? 0.745 was obtained by Correa et al. [2017]. \nThe case where F is unknown, such that the stopping decision may depend only on the values of the first t random variables but not on F, is equally well motivated (e.g., [Azar et al., 2014]) but has received much less attention. A straightforward guarantee for this case of ? ? 1/e ? 0.368 can be derived from the solution to the secretary problem. The main result is that this bound is tight. Motivated by this impossibility result the authors investigate the case where the stopping time may additionally depend on a limited number of samples from F. An extension of the main result shows that even with o(n) samples ? ? 1/e, so that the interesting case is the one with ?(n) samples. Here they show that n samples allow for a significant improvement over the secretary problem, while O(n^2 ) samples are equivalent to knowledge of the distribution: specifically, with n samples ? ? 1 ? 1/e ? 0.632 and ? ? ln(2) ? 0.693, and with O(n^2 ) samples ? ? 0.745 ? ? for any ? > 0.\n\nAuthors: J.R. Correa, P. Dutting, F. Fischer, K. Schewior\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=604
LOCATION:
END:VEVENT
END:VCALENDAR