Online Matching and Ad Serving: Theory and Practice

STOC'13 Workshop, June 1st, 2013

   Nikhil Devanur, Microsoft Research, MountainView
  Vahab Mirrokni, Google Research, New York

  • Discuss recent results in online stochastic matching and applications in ad serving,
  • Pose interesting research directions and open problems in the area,
  • Study new more realistic models in the presence of strategic agents,
Online advertising is a fast growing business on the Internet with tens of billions of dollars in annual revenue. Online ads appear in various forms such as sponsored search ads, contextual ads, and 
display or graphical ads. An important part of all advertising systems which are delivering various types of ads is the ad serving or ad delivery component that decides on the set of ads to show to users for their online activities like search, watching videos, or surfing the web. 

Motivated by such applications, there has been a rich theory of online algorithms for many problems, from the basic bipartite matching to more general resource allocation problems, in a variety of models,  including the worst-case competitive analysis and many stochastic models.  This has also been a exemplary case of theory being applied to and having an impact on important practical problems. 

In this workshop, we plan to survey key theoretical results in this area and practical applications of these results, and pose some new research directions and open problems.
  • Worst-case competitive analysis: The goal would be cover the ideas behind the randomized online matching algorithm and the primal dual technique, describe online matching, online weighted matching, and online budgeted allocation problems and recent generalizations to online submodular social welfare maximization.
  • Stochastic models with unknown distribution or random arrival order: The goal in this part is to cover ideas behind the dual-based online stochastic approximation, adaptive potential-based techniques, re-optimization techniques, and simultaneous approximation.
  • Stochastic models with known distributions: The goal in this part is to cover ideas from the primal sampling-based algorithms applying the idea of power-of-two-choices.