We look forward to seeing you in person in 3124 Siebel Center on Monday, September 18.
Abstract: This talk will be about the prophet secretary problem, a variant of the prophet inequality problem, which has been well studied. In this problem, you are given n non-negative and independent (but not necessarily identical) random variables X1, .., Xn. A random permutation σ is drawn from Sn, and the variables arrive in the order X_{σ(1)}, ..., X_{σ(n)}. At iteration t, a sample is drawn from X_{σ(t)}, and you must choose to either accept it, ending the game, or irrevocably rejecting the sample, and continuing to iteration t+1. The goal is to devise an algorithm that maximizes the competitive ratio: the ratio between the expected value your algorithm gets and the expected value of max(X1, ..., Xn) (i.e an offline optimal solution).
The first online algorithm for the problem had a competitive ratio guarantee of 1-1/e ~ 0.632 due to Esfandiari et al. This was followed by a series of papers improving the competitive ratio to 1-1/e+1/400~ 0.634 by Azar et al and finally ~0.669 by Correa et al. which is the current best competitive ratio for the problem. The analysis for these algorithms are fairly nontrivial and depend on heavy case by case analysis and numerical methods.
In this talk, I will present a new algorithm with a ~0.6724 competitive ratio, improving upon the best known competitive ratio. The analysis is extremely simple and will assume no prior knowledge of the existing literature. It uses a subtle shift in perspective when thinking about the sampling process, and a coupling argument to get rid of all the tedious case by case analysis. Finally, I'll end with a few open problems that I think might be of interest.
