Externalities in Online Advertising

  • Mohammad Mahdian | Yahoo!

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.

Speaker Details

Mohammad Mahdian is a research scientist at Yahoo! Research microeconomics and social systems group. Prior to joining Yahoo! in September 2006, he spent two years at Microsoft Research theory group as a postdoctoral researcher. He has a B.Sc. in computer engineering from Sharif University of Technology, an M.Sc. in computer science from University of Toronto, and a Ph.D. in applied mathematics from MIT. His current research interests include algorithmic game theory, in particular problems arising from online advertising and social networks.

Watch Next