How to Allocate Massive Volumes of Bid Traffic According to Need
The Mobile and Cross-Device Research Team develops new algorithms for targeting mobile web and application advertising. We work primarily with advertisers who want a performance-focused mobile presence. A key component of Quantcast’s inventory procurement strategy involves interacting with real-time-bidding (RTB) exchanges.
These RTB exchanges offer advertising placements and auction massive amounts of inventory of variable quality. Some placements never even appear on visible regions of the screen, while others appear directly in the sight of high value consumers. We must respond to RTB requests in real time — within 100 ms or less — and so must almost instantly adjust the prices we pay and the volume on which we bid depending on the quality and available supply. We handle this using a control system that:
- Determines prices on up to 2 million bid requests entering our systems every second
- Creates strategies that can accommodate different ad pricing models
- Distributes the client’s spend across thousands of individual contracts before we enter a bid in market
- Delivers uniform advertising results over the term of a contract
- Balances an often unpredictable flow of inventory
This post gives a more in-depth view of the specific challenges Quantcast faces in controlling volume and spend, challenges that demand the use of our innovative automated control system.
The Core Problem — What does our control problem for RTB look like and why does it exist?
Fundamentally, we design our control system to accommodate different ad pricing models, and deliver the highest quality opportunities for each client. We support several forms of pricing models. For a cost-per-thousand (CPM) model, the client pays Quantcast based on the numbers of advertisements we show. We quote prices per thousand units: e.g. the client pays $6 for every thousand impressions we show. This pricing model requires us to meet two constraints:
- Spend a particular amount of money
- Show a particular number of advertisements
We support another more flexible pricing model called “cost per acquisition” (CPA). In this type of model, Quantcast drives an “acquisition,” an outcome defined by the advertiser. An example of a common acquisition is a visit to an advertiser’s “thank you” page, which often indicates that a consumer has bought a product.
To satisfy the this pricing model, we must meet a core goal:
- Deliver the amount of acquisitions requested by the client over the term of the contract
So, where does the control problem come in? Our control system balances the constraints set forth by thousands of individual contracts, as it responds to tens of billions of daily individual bid requests from around the world. This system considers each of our clients’ contracts before submitting a single bid in market — while ensuring that we assign the highest-quality inventory to each of our clients. Simultaneously, we deliver advertisements in a consistent way for each client drawn from an only partially predictable flow of available inventory coming from the RTB system.
Control Parameters — How to Maintain Control of a Small Scale System
To drive the above concepts home, let’s look at a simple control system that meets system constraints for a CPM pricing model on an individual campaign. I’ll progressively introduce the complexity that our actual system fields, demonstrating the need for an automated control. (Note: This won’t cover CPA control, as that is just a simplification of CPM control.)
To start, suppose we have a human operator who controls a pricing function facing a uniform flow of inventory. The simplest control system you might imagine has a flat line pricing function (Figures 1 and 2). The pricing function translates a bid request from RTB into a price based on a quality metric. How far up the Y-axis your line sits determines the amount you spend. A gate set at a particular value of the bid quality determines the amount of inventory on which you bid.
Conceivably, a human could control this sort of system. The spend per bid and the volume are relatively decoupled — You can change one without affecting the other too much with relatively few exceptions. However, even a casual observer will notice that you ignore key elements of bid quality. Shouldn’t you bid more for high quality requests and less for low quality ones?
The quality metric communicates something about the worth of the particular bidding request. High values of this metric indicate superior opportunities for which we will pay a high price. Low values of the quality metric indicate inferior bids deserving a cheaper price. A more sophisticated pricing function is a line with a positive slope going through the origin (Figure 3).
As with the flat line pricing function, one control parameter determines the price we pay for bids on behalf of a client; the other controls how much volume we need to satisfy the impression constraint. Observing the curve below, the first parameter controls the slope and the second parameter controls the minimum bid quality. The human proceeds as follows:
- Measure the realized volume (how many advertisements we actually showed) and how much we spent on them on an hourly basis
- Predict, given the amount spent and the volume achieved up to now, how much we should spend and how much volume we should acquire in the future and translate that into control parameters
Suppose we begin bidding with a configuration like the one in Figure 3 and find that we achieve too much volume. Our human controller would change our bidding strategy to look more like the one in Figure 4.
Similarly, if we find ourselves spending too little, we increase the slope of the line, giving the incremental bid quality a higher relative value.
(The analogous controller for the CPA pricing model simply leaves out the parameter that controls for volume. This controller only attenuates spend.)
Introduction to Practical CPM Control for a Single Campaign
The coordinates we control under this plan are coupled, so even the simpler way described requires several steps to reach a steady state when we ignore details of parameter coupling. That said, there are several automated approaches that solve this problem quite well so long as we have the right pricing function. These range from simple approaches such as proportional-integral control to more sophisticated schemes like optimal control.
Using the approach to spending detailed in figures 3 and 4, the operator iteratively adjusts parameters to bid on an appropriate amount of volume at a given bid price. This means a more sophisticated method than a human pushing around couple of levers.
Even in simple situations, an automated method of making adjustments simplifies the function of such a high-touch mechanism. In the above case with incoming inventory held constant, the controller’s job is pretty simple: methodically find the set-point where you get the amount of inventory you want at the price you want.
The Trouble with Periodic Changes in Inventory Availability
Now, imagine that the amount of inventory you see changes over time, as it does in RTB. In this case, even if you find the correct set of parameters at one moment, you’ll have to find a new setting in another moment. With the goal of serving the same number of advertisements at the same price at every hour of the day, the controller bids on a higher fraction of inventory when supply is low and lower fraction of inventory when supply is plentiful. The controller we explained above will now have to dynamically tune into time dependent set-points throughout the course of the day by adjusting its volume and pricing control parameters. The frequency of adjustments here requires that we automate our control system.
The fluctuation of inventory throughout the day is uncertain because there’s only a finite amount of good inventory. As such, when we bid on a higher fraction of inventory, we expose ourselves to lower-quality opportunities. Conversely, when we bid on a lower fraction, we miss out on otherwise good opportunities. To overcome the lack of consistency, we must devise control plans that favor a dynamically changing supply of higher quality inventory.
One way to remedy this problem is to program in a model of how you think the stream of inventory changes through the course of the typical day. With the right projection of inventory, you’ll serve an amount of advertisements proportional to the amount of available supply. Pinning the controller’s delivery to the amount of available inventory is one way to minimize the number of corrections the control algorithm will need to apply in order to stay within the controller’s parameters. So, if the controller knows there’s more inventory in the morning than in the afternoon, it keeps itself more stable by serving more impressions in the morning. Hence the quality of inventory will shift less during the day, exposing us to better opportunities.
A perfect inventory supply model still doesn’t prevent the need for adjusting control parameters, because the fraction of the distribution with high quality changes through the course of the day. Inventory price fluctuations result from this. To be concrete, online sales peak at 5 PM on weekdays, so impressions cost more. Similarly, online sales hit a low point at around 3 AM and impressions cost less. In the simple example we described above, we tune into a fixed spend. In reality, we need to adjust the amount we expect to spend on quality inventory through the course of the day. Therefore, to stabilize the parameter that controls spend, we need an additional estimate of what prices should look like throughout the day. Different time zones add additional layers of complication.
The Trouble with (you guessed it) Scaling
This still leaves two major sources of disturbance. The controller must be ready to respond to random shocks to the system from either unexpected changes in available exchange inventory or sudden inventory price fluctuations.
As we increase the amount of inventory available through our RTB system by adding new exchanges, the size of random shocks also increases. In an extreme example, imagine we’re cruising along and spending as expected when suddenly an exchange goes offline, stopping its delivery of RTB inventory to us. Our controller will then automatically buy a higher fraction of available inventory, simply because a large amount of it has disappeared. Then, the exchange comes back online. This introduces a substantial amount of more opportunities for us to buy, resulting in a flood of purchased inventory. We call this a spend spike.
The size of this spike is dependent on the time of day it happens. Obviously these spikes are larger at high volume times than at low volume times. There’s simply more inventory we can purchase, causing misjudgments in buying to affect us more drastically. Our controller must react quickly and without human intervention to prevent us from buying too much inventory.
Even if you factor in seasonal phenomena and react to noise correctly, increasing the number of campaigns presents interesting challenges. The plan described does not explicitly take into account the interactions between campaigns and how to optimally distribute spend loads among them. Distributing these spend loads often leads to conflicts. For example, imagine you have two very similar advertising campaigns. These campaigns are so similar that the RTB bid request quality metric returns the same score for both campaigns. Interaction between campaigns can become toxic at this point, with the campaign configured to spend more effectively starving the other one. This is a not uncommon occurrence and adds to the depth of the control problems we address at Quantcast.
Summary
This covers some of the basics behind the control problems Quantcast faces as a player in the RTB space, offering details of simple controller implementations. I’ve shown that we need an automated control even in the rather basic case of controlling a single CPM deal.
As the complexity builds from introducing more optimal price curves to gracefully dealing with the seasonality of RTB requests, the need for an automated control system becomes even more apparent. More sophisticated approaches facilitate support for multiple campaigns and we’ll touch on this in a future post.