Krishnan, Harish

A Mathematical Model to Solve Google’s Ad Allocation Problem

Harish Krishnan and Andrew Mason

Department of Engineering Science, University of Auckland

Sponsored search auctions are ubiquitous these days and search engine marketing companies such as Google make billions of dollars in revenue. These auctions are usually second price auctions. Advertisers spend significant portion of their marketing budget on sponsored search and this is only expected to increase in the future. Search Engines are likely to solve a complex optimization problem of allocating ads to different advertisers to achieve one or all of the following objectives.

  1. Maximize Ad Revenue
  2. Improve User Experience
  3. Maximize Return on Investment for Advertisers.

In this paper, the auction process is explained formally. Empirical data collected from experiments to understand the auction process is analyzed. Slates based optimization model - a model from the existing literature is explained and critiqued using the empirical data and a new slots based optimization model that is consistent with the data is proposed.

Simulated results indicate that the slots based optimization model outperforms the random allocation of ads by 22% and a Greedy Approach based on Google’s documented rules by 12%.

YoungPrac This presentation is eligible for the ORSNZ Young Practitioners Prize.