Mohammad Mahdian

Yahoo Research

3:00pm - 4:30 pm

Wu & Chen Auditorium

101 Levine Hall

"Externalities in Online Advertising"

Following the fast growth in the popularity and availability of the Internet during the past decade, online advertising has emerged as the dominant business model for providing online services.  This trend has posed new challenges on how to optimally allocate and price online advertising space and has sparked interdisciplinary research in the fields of computer science, economics, and sociology.  In this talk, we will present some of these challenges, focusing on the problem of externalities in online advertising: as the advertising audience has a limited attention span, a high-quality ad on a page can detract attention from other ads on the same page. This effect is largely ignored by the currently standard models in the business.  In this talk, we will describe two models for online advertising that take this effect into account, and discuss the computational complexity of the winner determination problem in these models. One of our models is based on a rational-choice model on the audience side, and the other is based on a probabilistic view of the user behavior. We show that in the most general case of the rational-choice model, the winner determination problem is hard even to approximate. However, there are several interesting special cases, such as when the audience preferences are single peaked, that the problem can be solved efficiently. In such cases, the winner determination algorithm can be combined with standard VCG techniques to yield truthful mechanisms.  In the probabilistic model, which is inspired by a cascade model proposed and empirically evaluated by Craswell et al. for organic search results, we show that the winner determination problem can be solved in polynomial time. 

This talk is based on joint work with Arpita Ghosh and David Kempe.