Sunday, August 13, 2006

Slides from sponsored search talk

Jan Pedersen (Chief Scientist at Yahoo) posted the slides (PDF) from his SIGIR AIRWeb invited talk, "Sponsored Search: Theory and Practice".

It is an interesting overview of web search advertising, including history of sponsored search, results of game theoretic analysis of efficient web advertising auctions, and various forms of click fraud. Well worth a look.

By the way, if there are any other game theory geeks out there that like punishing themselves on a Sunday afternoon, I spent a little time trying to track down Jan's reference to "Edleman et al." on slide 21. My best guess is that it is a reference to Edelman et al., "Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords" (PDF), a November 2005 paper out of Harvard, Stanford, and Berkeley.

This Edelman et al. paper makes the claim that the Generalized Second Price (GSP) auction used by Google and Yahoo "does not have an equilibrium in dominant strategies, and truth-telling is generally not an equilibrium strategy." The difference is due to the way advertisers bid on advertising slots. As the authors explain, "GSP essentially charges bidder i the bid of bidder i + 1, VCG [Vickrey-Clarke-Groves] charges bidder i the externality that he imposes on others, i.e., the decrease in the value of clicks received by other bidders because of i's presence." As examples in the paper show, under some scenarios, GSP gives advertisers some opportunities to shave their bids instead of bidding at their true value.

The authors go on to argue that VCG "would reduce incentives for strategizing and make life easier for advertisers" and "new entrants such as Ask Jeeves and Microsoft Network have a comparative advantage over the established players in implementing VCG." However, they temper that by admitting that "VCG is hard to explain to typical advertising buyers" and "the revenue consequences of switching to VCG are uncertain."

In the end, I was not able to determine if the theoretical inefficiencies of GSP described in the paper were substantial compared to implementation problems like various forms of click fraud. Interesting nonetheless.

Anyway, definitely check out Jan's slides and afterward, if you also want to beat yourself with a game theory pain stick, download the Edelman et al. paper.


John K said...

Greg, the Edelman et al. paper has a very serious flaw. It assumes a spherical cow, basically:

"In our analysis, we assume
that all bidders have identical CTRs, in which case Google’s and Yahoo!’s mechanisms are identical."

Independent of this massive over-simplification, Google's auction model has a different set of rules than Yahoo's and is not anything like a GSP auction.

Just one example would be Google's quality score mechanism which effectively puts a fixed minimum price on bidding and has a huge impact on the game theory nature.

But is seems likely that the authors apparently don't really buy any advertising on the search engines.

Greg Linden said...

Thanks, John. That's a good point.

searchquant said...

Please dumb it down for a knucklehead like me.

What did the Y! guy's presentation make you think about the relative a) ROI for advertisers; b) monetization characteristics for Y! and Google of their respective auction engines. When I say you I'm referring to the soon-to-be-released Panama platform.

Thanks much for the great reading, even if it is a bit over my head.

Greg Linden said...

Hi, Searchquant. Nothing specific about that, I'm afraid.

The talk is more background for researchers interested in web advertising platforms that anything that gives specific conclusions about current or future advertising engines.