Abstract

Every time a user types a query into a search engine, an auction is run to decide which ads (if any) to show in response, and where to place them on the results page. When a user clicks on an ad, the publisher is paid by the advertiser. This happens in real time, thousands of times every second, and generates billions of dollars in revenue. It is Google’s main source of income. Current auctions run by Google or Bing use a ranking algorithm which is a variant of a Generalised Second Price Auction. This e-commerce example is a rich area for research which lies at the intersection of mathematics, economics and computer science. For example, advertisers need to determine how to bid in the face of uncertainty, a machine learning problem, while the auction designer wants to design a robust mechanism that balances the competing demands of users, advertisers and publisher.

We describe such ad-auctions, and illustrate how current systems have adapted insights taken from auction theory and optimisation to design mechanisms that can be used at scale. Examples from live auctions are used for demonstration. Yet despite their ubiquity, such repeated auctions are not fully understood: the simplifications typically needed for analysis of single-shot auctions rarely hold in practice, new methodology is required, while new forms of advertising stretch the existing models. We give examples of some recent research.