Abstract

In pay-per-click online advertising systems like Google, Overture, or MSN, advertisers are charged for their ads only when a user clicks on the ad. While these systems have many advantages over other methods of selling online ads, they suffer from one major drawback. They are highly susceptible to a particular style of fraudulent attack called click fraud. Click fraud happens when an advertiser or service provider generates clicks on an ad with the sole intent of increasing the payment of the advertiser. Leaders in the pay-per-click marketplace have identified click fraud as the most significant threat to their business model. We demonstrate that a particular class of learning algorithms, called click-based algorithms, are resistant to click fraud in some sense. We focus on a simple situation in which there is just one ad slot, and show that fraudulent clicks can not increase the expected payment per impression by more than o(1) in a click-based algorithm. Conversely, we show that other common learning algorithms are vulnerable to fraudulent attacks.