Tutorial: Prior-Robust Optimization
Presenters : Nikhil Devanur (MSR) and Balasubramanian Sivan (U. Wisconsin-Madison)
Room: Berger Autitorium, Skirkanich Hall
The focus of this tutorial is optimization in the presence of uncertain inputs.
In a broad class of algorithmic problems, uncertainty is modeled as input being
drawn from one among a large known universe of distributions, however the
specific distribution is unknown to the algorithm. The goal then is to develop
a single algorithm that for every distribution in this universe, performs
approximately as well as the optimal algorithm tailored for that specific
distribution. Such algorithms are robust to assumptions on prior
distributions.
Prior robust optimization retains the robustness of worst-case analysis while
going beyond the pessimistic lower bounds of worst-case analysis. Apart from
this theoretical appeal, the ability to use the same algorithm for every prior
distribution makes prior robust algorithms well-suited for deployment in
real systems. Indeed, most prior robust algorithms in literature are simple to
implement and some of them have been observed to perform well in large-scale
systems.
In this tutorial, we present general techniques for developing prior robust
algorithms for two distinct lines of research: online algorithms and mechanism
design. In online algorithms, we do this by surveying a recent series of results
on resource allocation problems, whose several applications including to
internet ad serving is of interest to the EC community. In mechanism design, we
illustrate the techniques by surveying classic and recent results on revenue
maximization in auctions, as well as recent results on makespan minimization in
machine scheduling. No prior knowledge of mechanism design will be assumed.
Finally, since developing prior robust algorithms is a relatively new research
agenda, several interesting open questions remain, and will be pointed out along
the way.
|
