Externalities in online advertising

Authors:

Abstract
Most models for online advertising assume that an adver- tiser's value from winning an ad auction, which depends on the clickthrough rate or conversion rate of the advertise- ment, is independent of other advertisements served along- side it in the same session. This ignores an important ex- ternality eect : as the advertising audience has a limited attention span, a high-quality ad on a page can detract at- tention from other ads on the same page. That is, the utility to a winner in such an auction also depends on the set of other winners. In this paper, we introduce the problem of modeling ex- ternalities in online advertising, and study the winner de- termination problem in these models. Our models are based on choice models on the audience side. We show that in the most general case, the winner determination problem is hard even to approximate. However, we give an approx- imation algorithm for this problem with an approximation factor that is logarithmic in the ratio of the maximum to the minimum bid. Furthermore, we show that there are some interesting special cases, such as the case where the audi- ence preferences are single peaked, where the problem can be solved exactly in polynomial time. For all these algo- rithms, we prove that the winner determination algorithm can be combined with VCG-style payments to yield truthful mechanisms.

This publication has 10 references indexed in Scilit: