document: Externalities in online advertising Most models for online advertising assume that an advertiser 's value from winning an ad auction , which depends on the clickthrough rate or conversion rate of the advertisement , is independent of other advertisements served alongside it 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 . 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 externalities in online advertising , and study the winner determination 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 approximation 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 audience preferences are single peaked , where the problem can be solved exactly in polynomial time . For all these algorithms , we prove that the winner determination algorithm can be combined with VCG-style payments to yield truthful mechanisms .
doc_bio_tags: B O O B O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O