Speaker: Morteza Zadimoghaddam, Google Research

Title: Algorithmic Challenges in Computational Advertising

Abstract:

Over the last few decades, a wide variety of allocation markets emerged from the Internet and introduced interesting algorithmic challenges, e.g., ad auctions, online dating markets, matching skilled workers to jobs, etc. I focus on the use of allocation algorithms in computational advertising. In all these practical situations, we should focus on solving the allocation problems in an online setting since the input is being revealed during the course of the algorithm, and at the same time we should make irrevocable decisions. We can formalize these types of computational advertising problems as follows. We are given a set of online items, arriving one by one, and a set of advertisers. The goal is to assign the online nodes to advertisers maximizing some objective functions like revenue or welfare given some capacity and budget constraints. The online nature of the problem makes it hard to achieve reasonable revenue guarantees if we assume that the online nodes are arriving based on an adversarial order. On the other hand, it is too optimistic to assume that the arrival order is governed by some nice stochastic model. We show how to find and analyze algorithms that are robust to the arrival order.

Another challenge is having multiple objective functions to optimize. In many applications, we care about both revenue and welfare of the allocation. We show how to deal with multiple objectives, and find a smooth trade-off between them.

Finally, we focus on the problem of dealing with the uncertainty hidden in the allocation process. In some cases, we benefit from an assignment only if the online node clicks on the advertisement, and we will know about it after the assignment is done. This adds a stochastic dimension to the problem, and we show how we could analyze some of the natural algorithms in this setting.