Wednesday, June 25, 2008

Advertising auctions and modeling externalities

Googlers Gagan Aggarwal, Jon Feldman, S. Muthukrishnan, and Martin Pal have an upcoming paper, "Sponsored Search Auctions with Markovian Users", with a new model of people's behavior that captures the idea that some ads may cause people to stop looking at the other ads.

An excerpt:
[Prior] models assume that the probability of an ad getting clicked is independent of other ads that appear with it on the same page, an assumption made without much justification. It is hard to imagine that seeing an ad, perhaps followed by a click, has no effect on the subsequent behavior of the user.

We propose a model based on a user who starts to scan the list of ads from the top, and makes decisions (about whether to click, continue scanning, or give up altogether) based on what he sees.

More specifically, we model the user as the following Markov process: "Begin scanning the ads from the top down. When position j is reached, click on the ad i with probability pi. Continue scanning with probability qi."

It turns out that the structure of this [auction] is different than that of [generalized second price] ... The presence of the qi's requires a delicate tradeoff between the click probability of an ad and its effect on the slots below it.
I have been bothered for some time by the assumption that crappy ads have no impact on the ads around them. It seems likely that bad ads make things worse for everyone and should be penalized beyond the higher bids they have to pay for their low clickthrough rates.

Please see also Craswell et al., "An Experimental Comparison of Click-Position Bias Models" (PDF), a WSDM 2008 paper that proposes a similar "cascade model" not for ads, but for search results.

Please see also my earlier post, "Hal Varian on advertising auctions", which talks about an Ad Quality Score that Google uses and how it may be an attempt to patch a problem in current advertising auction models. While I doubt the Ad Quality Score is trying to exactly produce the model this paper advocates, the two efforts may be targeting the same problem.

1 comment:

Joe Reis said...

Can't wait to read this paper. Like you, I also find it hard to believe that clicks are independent random variables, and that surrounding ads have no affect on click behavior. The very fact ads are clustered around certain attributes (due to keyword targeting) would seem to heuristically throw this idea out the window. Do you know of any Markovian-like research done on other advertising mediums?