Automatic Waterfall Auction Optimization
By Dan Halbersberg
In this blog, we will share how publishers can optimize their revenues from online advertisement sales, as part of a waterfall auction.
If you don’t know what a waterfall auction is, or how AI tools can be utilized to optimize the revenue from the publisher’s side, don’t worry. We’ll cover all of that and more, after going over the basics of online advertising and defining key players of this process.
Online advertising is a major source of income for many online companies. During the online advertisement process, whenever a user surfs on a website or utilizes a mobile app, advertisement real-estate, called an ad slot is allocated. The process through which an ad slot is populated by a relevant advertisement is called an impression. The slot owner is called a publisher, and the advertisement owner is called an agency. The publisher sells ad slots to the advertiser via a mediator entity called an ad network. Examples of ad networks include Facebook, Google, Unity, etc. Both the publisher and the agency buy and sell advertisements using supply-side-platform (SSP) and demand-side platform (DSP), respectively. The SSP enables the publishers to manage their advertising inventory, fill it with ads, and receive revenue, while the DSP allows the agency to participate in auctions and buy advertising inventory.
Figure 1: A diagram of the online advertisement ecosystem.
There are several auction protocols for buying and selling advertisements. One of the most relevant and widely used auction protocols is called a waterfall, through which the publisher makes sequential ad requests to ad networks. Each ad request targets a specific ad network with a specific price. The sequence of ad requests is pre-defined by the publisher, and it is known as the waterfall’s auction strategy. For the waterfall strategy to succeed, the publisher must determine the order of ad networks and their associated prices, ahead of time. Note that the strategy is common to all users; namely, the waterfall is not user-specific.
Figure 2: A synthetic example of a waterfall strategy.
Why is optimization necessary?
As different waterfall strategies could potentially lead to diverse total revenue gains, it is extremely beneficial for publishers to optimize the strategy they use. However, as the number of possible waterfall strategies grows exponentially with respect to the number of ad networks and prices in the mix, waterfall optimization is quite the formidable task. Therefore, most publishers perform this optimization based on human experience, trial & error, or other similar inefficient and unscalable methods.
How to optimize the waterfall strategy
The main purpose of this blog is to propose a framework for publishers to automatically optimize their waterfall strategies, using AI tools. The main concept behind our approach is to utilize user-accumulated data that is measured during multiple visits to the publisher’s website or app. In other words, we leverage historical data to estimate the valuation of each user, by each ad network.
We call this processed data the valuation matrix; rows in this matrix are distinct users, and columns are ad networks. Each cell in the matrix stores the specific parameters of a known statistical distribution; be it Normal, Beta, Gamma, Dirichlet, or any other statistical distribution. The parameters are inferred from the user’s past auctions in various waterfalls. Once we estimate how each user is perceived by each ad network, we can simulate how changes within the waterfall might influence bottom-line revenues, over the entire population. We could do so by “running” the users’ valuation through the changed waterfall, and then calculating the total revenue. The term “running” simply means that we sample a price from the user’s valuation distribution and compare it to the waterfall instance price. We repeat this process for each instance in the waterfall, until the sampled price is higher than the current instance price, i.e., until a successful ad event is achieved. Algorithm 1 formally describes how we run users in a candidate waterfall:
In an ideal world, we would score all possible waterfalls (in terms of revenue) and adopt the one with the highest total returns. However, as we mentioned earlier, the number of possible waterfalls is almost infinite (depending on the waterfall length), and thus, defining an intelligent search procedure over the space of valid candidate waterfalls remains a significant challenge.
To resolve this issue, we present a well-known regulated search procedure; the simple hill-climbing search (Algorithms 2, below). This greedy, iterative algorithm starts with a random waterfall, and then, at each iteration, adapts a neighbor waterfall; the waterfall from the previous iteration that exhibits a single change, such as an increase/decrease in the price of an instance by $X, or the introduction of a new instance/removal of an existing instance. The result: the ability to drive the highest improvement in revenue, possible.
As this algorithm aims to output an improved waterfall, we thoroughly evaluated it in real business environments. In one of the experiments, we applied the algorithm to real-world data collected over 7, 14, 21, and 28 days and measured how the revenue increases. Figure 3 shows the improvement achieved by the algorithm in this experiment. On average, we demonstrated an improvement of 5%–10%, as compared to human expert manual optimization.
Figure 3: The learning curve, measured as the improvement in revenue of four real-world waterfalls (A – D). Each color represents a point in time (d), to which the algorithm was applied.
For more details, we encourage you to read our online paper: “Search and Score-based Waterfall Auction Optimization,” >> https://arxiv.org/pdf/2201.06409.pdf