.jpg)
Refereed Papers
Track: Internet Monetization: Online Advertising
Paper Title:
Externalities in Online Advertising
Authors:
- Arpita Ghosh(Yahoo! Research)
- Mohammad Mahdian(Yahoo! Research)
Abstract:
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 {em 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.
Inquiries can be sent to:
