Prior Robust Optimization

The focus of this talk is optimization in the presence of uncertain inputs. We model uncertainty as input being drawn from one among a large known class of distributions; however the specific distribution is unknown to the algorithm. The goal is to develop a single algorithm that for every distribution in this class, performs approximately as well as the optimal algorithm tailored for that specific distribution. Such algorithms are robust to assumptions on prior distributions and are good candidates for deployment in real systems.

In this talk, we present general techniques for developing prior robust algorithms for two distinct lines of research — online algorithms and mechanism design. In online algorithms, we present our results for a very general class of resource allocation problems with several applications, including to internet advertising. We develop a simple-to-implement prior robust algorithm with near optimal profit guarantee. Our algorithm has been deployed globally along with Microsoft MSN’s display ads serving engine. In mechanism design, we focus on the well-studied makespan minimization problem in machine scheduling. Here, our goal is to schedule jobs with stochastic runtimes on machines which are operated by strategic agents who hold the runtimes private. We design simple-to-implement truthful prior robust mechanisms that under different distributional assumptions provide constant and sub-logarithmic approximations to expected makespan.