Robust advertisement allocation

Internet advertising revenue has surpassed broadcast revenue (including cable televisions) very recently due to the rapid growth of e-commerce and information technology. As online advertising has become a major source of revenue for online publishers, such as Google and Amazon, one problem facing them is to optimize the ads selection and allocation in order to maximize their revenue. Although there is a rich body of work that has been devoted to this field, uncertainty about models and parameter settings is largely ignored in existing algorithm design. To fill this gap, we are the first to formulate and study the Robust Ad Allocation problem, by taking into account the uncertainty about parameter settings. We define a Robust Ad Allocation framework with a set of candidate parameter settings, typically derived from different users or topics. Our main aim is to develop robust ad allocation algorithms, which can provide satisfactory performance across a spectrum of parameter settings, compared to the (parameter-specific) optimum solutions. We study this problem progressively and propose a series of algorithms with bounded approximation ratio.