The maths behind internet ads

The decision process behind websites serving specific ads was something I had wondered about for a while, so today I took the plunge and did some digging. Here’s what I came up with.

When you perform a Google search, you usually get a list of ads that are relevant to your search at the top of the page (for which Google gets per-click pay). These are related to the search terms you enter by keywords the advertisers associate with their adverts, so if you search for “mountain bike” then you’ll probably get a sponsored list of bike shops at the top.

To decide on exactly which of the myriad of potentially relevant ads to list, Google uses a generalised second-price (GSP) auction mechanism. The advertisers bid the maximum amount they are willing to pay per click, this bid then gets multiplied by a “quality score”, and the ads are listed in decreasing order of this multiple. For the purposes of this post, I’m assuming the quality score is the same for all ads.

What makes this auction “second-price” is that an advertiser doesn’t actually pay what they bid, but instead the amount the advertiser one position lower on the list had bid. This is to avoid gaming the system: if all advertisers paid what they bid, the advertiser on spot j would only be willing to pay exactly one increment above what advertiser on spot j-1 pays. If all advertisers coordinated, they could bid much lower than the actual amount their ads are worth.

While using the second price mechanism does encourage advertisers to bid the real value of a click on their ad, it’s not foolproof. It turns out that, from the advertiser’s perspective, paying the full amount is not an optimal strategy — in the jargon, this makes GSP a non-truthful auction. Little doubt can be cast about its transparency and practical effectiveness, though: Google’s been wildly successful since they implemented the system in 2002.

There are other auctioning mechanisms that are truthful, however. One of them is the Vickrey-Clarke-Groves (VCG) mechanism, which is used by Facebook to place sponsored posts in users’ news feed. Instead of paying the amount they bid, or the amount for the next position down the list, an advertiser instead pays the harm they cause by being present in the auction. To be precise, they pay the difference in total value generated by the list of ads between the case of the advertiser being present and the case of them being absent (see this paper for more details). Facebook’s found success using VCG, but it lacks the simplicity of GSP — Google also considered implementing VCG, but shelved the idea since it’s more difficult to explain to advertisers.

Further reading