Externalities in Online Advertising

Опубликовано 8 сентября 2016, 18:54

Most models for online advertising assume that each ad has an inherent clickthrough-rate/conversion-rate, regardless of other ads served in the same session. This ignores an important externality effect: 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. 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 model 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.