THE GRAPH REVENUE OPTIMIZED WATERFALL STRATEGY (GROWS)
By Dan Halbersberg
In this blog post, we will expand upon the information provided in our previous post, “Automatic Waterfall Auction Optimization”. Therefore, we will assume that you have already read the previous blog and have a basic understanding of online advertising and the key players in the process.
Once again, we will focus on the publisher’s side, who wishes to sell ad slots to advertisers, and on one auction protocol known as the waterfall strategy. Through this method, the publisher makes sequential and pre-defined ad requests to ad suppliers via third-party ad networks.
Why do we propose a different solution?
In our previous post, we introduced an algorithm that promised to optimize the waterfall strategy; however, since it is based on heuristics, it can only provide a sub-optimal solution.
If you are wondering if you should read on, we’ve got two compelling reasons for you to continue: First, we’ve formulated an intriguing problem as a trellis graph, allowing us to solve it using a Viterbi-based algorithm, which is cool. But it’s not just about the cool factor – our solution is also optimal under several reasonable assumptions and boasts a polynomial time complexity. Therefore, our method outperforms other state-of-the-art techniques for optimizing the waterfall strategy.
How to optimize the waterfall strategy
Before introducing our Graph Revenue Optimized Waterfall Strategy (or GROWS for short), we’d like to provide you with the notations in Table 1 and explain the calculation of revenue for a given waterfall.
Table 1: Notations
The daily revenue of a waterfall, denoted by the \({\Theta}\)(W), is calculated by summing the product of price and the number of impressions for all instances, or formally:
\({\Theta}\)(W) \( = \sum_{i=1}^{r}q_i*u_i\)
Figure 1 illustrates a waterfall strategy, its associated notations, and an example of the revenue calculation process.
Figure 1: A waterfall with a revenue of $1,031.85
With the aim of optimizing the waterfall strategy, we will reformulate the problem as an optimal path searches over a trellis graph (Figure 2). The graph is comprised of nodes and edges, and serves as a compact representation of all possible waterfalls!
The graph is defined as follows:
- The graph has \(\mathrm{L}\) layers, where \({\mathrm{L}}\)\( = \sum_{k=1}^{K}C_k\) is the total capacity of all ad networks (the number of allowed instances).
- Each layer contains \(\mathrm{N=}\mathrm{Qx K}\) nodes, i.e., the number of combinations of price and ad network.
- Each node is a pair of a specific price, \({q}\), and an ad network, \({k}\).
- Each layer, \({j}\), represents all possible ad network instance couples. Therefore, in the optimal solution, one node per layer is selected to construct the optimal path (e.g., the green dashed lines in Figure 2).
Figure 2: Trellis graph for solving the waterfall optimization problem. The gray-shadowed nodes connected by green dashed arrows represent the best path in the graph
The relationship between any pair of nodes from two consecutive layers in the trellis graph is described by the zero-one loss function.
That is, a value of 1 is assigned if an edge exists, or 0 if the edge is missing. Note that the presence of an edge does not necessarily imply that it is part of the optimal path. The presence or absence of an edge is determined by whether it violates the constraints of the problem.
The constraints
The constraints determine which paths are valid, i.e., if \({e(z,z,j) = 0/1,}\). We distinguish between local and global constraints and between active and non-active constraints. Specifically, the local constraints define the edges in the trellis graph while global constraints influence which paths are valid, and which are not.
Example of a local constraint: two consecutive instances cannot belong to the same ad network. Figure 3 shows a waterfall that violates this constraint, as it shows two consecutive instances belonging to Facebook. The motivation for this constraint is that Facebook would quickly realize that if they choose to give up X random users for $82, then 100% of these X random users will be offered to them again for a lower price of $66 (if there were another instance between the two, it is likely that at least one user would be bought by this intermediate instance).
Figure 3: Invalid waterfall with two consecutive Facebook instances
Example of a global constraint: each ad network restricts the number of allowed instances in any waterfall.
An inactive global constraint is one that, if not considered during the learning phase, the solution for the waterfall strategy does not violate it. While an active global constraint is one that, if ignored during the learning phase, the solution violates it.
How to calculate a node’s revenue
We need to estimate
\({\theta_i{(q_i,k_i)}}\)\( =S\int_{q_i}^{q_i-1}f_i(q)dq\),
where \({f_i}\) is the ad slot price probability distribution function and \({S}\) is the number of ad slot sell opportunities. Since it is hard to estimate \({\theta_i}\) directly, we approximate the revenue function using Table M, which contains historical auction data (Table 2).
Table 2: Discrete price distribution per ad network
We replace the integral with the summation, where entries in M are the results of a certain function of past auctions:
\({\theta_i{(q_i,k_i)}}\)\( =q_i \sum_{p=q_i}^{min(Q,q_i{\prime})}M(p,K_i)\)
We have thoroughly evaluated the performance of the algorithm using real-world data and have demonstrated its superiority. Additionally, we conducted an A/B test in a real business environment. For this, we selected a real-world waterfall and split it into two: one was managed manually by a human expert, and the other by our proposed algorithm, GROWS. Users were randomly split between the waterfalls (based on the 5th digit of their DeviceID). Once a week, the human expert and GROWS modified their corresponding waterfall independently, but at the same time. The results of the six-iteration experiment can be seen in Figure 4.
Figure 4: The difference in revenue between the human expert and GROWS over the course of six iterations
For more details, including a more in-depth, theoretical analysis and additional experimental results, we encourage you to read our online paper, “Revenue Maximization at Waterfall Auctions with Dynamic Programming”, which was presented at the 2022 IEEE International Conference on Big Data.
