The Reserve Price Optimization for Publishers on Real-Time Bidding on-Line Marketplaces with Time-Series Forecasting
Published Online: Nov 07, 2020
Page range: 167 - 180
DOI: https://doi.org/10.2478/fman-2020-0013
Keywords
© 2020 Andrzej Wodecki, published by Sciendo
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.
This work was supported by Europejski Fundusz Rozwoju Regionalnego (European Regional Development Fund), grant number: RPMA.01.02.00-14-9523/17.
Internet advertising has become a multi-billion dollar industry in recent years. According to Zenith Agency (Austin, Barnard, and Hutcheon, 2019), global digital advertising spend in 2019 exceeded 290 billion US dollars, with more than 320 billion US dollars expected in 2020.
Advertisers may purchase the so-called ad slots both through direct contracts (non-programmatic) or by means of real-time auctions (programmatic marketing)
An interesting overview of on-line advertising industry can be found, for example, in (Choi, et al. 2019).
Real-time bidding (RTB), as a way of trading digital ads through real-time auctions, is the most popular mechanism of programmatic marketing. On the RTB market, one can, in a nutshell, distinguish between the demand side (organizations interested in purchasing advertising space), the supply side (providing this space), the market organizer, and the companies supporting the transaction in various ways. In practice, in each of these segments, there are many actors with different business models and target functions. A simplified market diagram is presented in Fig. 1.
Figure 1
Online advertising ecosystem (
A typical transaction process on the RTB market is as follows. An Internet user visits one of the advertising spaces displayed by the Publisher, most often through a web browser or mobile application. The Publisher passes this information (so-called bid request: (1)) to the Supply Side Platform (SSP) enhanced by a description of the available advertisement inventories.
The SSP platform (there may be many of them on the market) transmits this information to Ad Exchange, which initiates the auction: it distributes information about inventories, enriched with user data (demography, behavioral profile) obtained from Data Management Platforms (DMP), among many Demand Side Platforms (DSP) waiting for the Advertisers’ offers.
On the DSP, the bid request is initially adjusted to the previously registered space and user requirements (advertising campaigns). Advertisers receive bidding data and, most often using the algorithms implemented in their systems, specify the price they are willing to pay (so-called bid response: (2)). Bid responses are transmitted, via the DSP, to the Ad Exchange, where the auction is finalized (3), and the so-called win notice is transmitted to the Advertiser.
The Advertiser passes his advertisement (via DSP, Ad Exchange, and SSP) to the Publisher, who emits it on the indicated inventory. After the emission, its details, in particular information about the user feedback (5), are forwarded to the Advertiser. The transaction is finalized, the auction ends. The whole process (from the user entering the Publisher website to the display of the advertisement) takes about 0.1 sec.
The RTB market can be compared to a multi-player game, each with its own goal function. The Publisher wants to maximize profits from advertisements, which requires pricing to be as high as possible on the one hand, and competitive with other publishers on the other.
The Advertiser must also bid intelligently: offer prices that minimize the cost of acquiring a customer, but are higher than those of other advertisers.
This is hindered by the lack of information transparency in the market:
DSP and SSP platforms are its active participants: DSPs often buy space en masse from publishers and only bid on known prices; advertisers do not have information about the auction sale price they have not won; and publishers do not know all the prices offered by the advertisers at the auction.
No wonder that all market participants are actively looking for solutions (methods, algorithms, technologies) that would optimize their goal function. In this article we focus on the Publisher perspective, the Advertisers’ one briefly described (for the reference in the literature review section).
The main goal is to identify the so-called reserve (minimal) price optimization strategy, which is not only efficient, but also possible to implement in the mid-size RTB marketing agency. Present strategies (presented in different research papers displayed below) in most cases try to forecast advertisers’ strategies to maximize the profit from a given advertisement emission, what 1. makes it computationally challenging for small RTB agencies and 2. doesn’t take into account other Publishers’ goals like optimal ad space utilization (measured by so-called Coverage parameter).
In this paper, we recommend significantly different heuristics: instead of guessing the add value for the advertisers, we use advanced time-series algorithms to short-term (3 days) forecasting of the Coverage parameter and adopt reserve price to keep this parameter on the maximal possible level. Thus, it is not only computationally efficient (feasible to retrain the model on a daily basis), but also easy to understand and interpret by RTB agency consultants. The strategy presented below may increase competitive advantage of such agencies and increase its customers’ (Publishers’) profits.
After a brief presentation of the state of the research, in the main part of the work, we present the method of optimization of reserve prices at publishers using the modelling of time series of key space utilization parameters. We show the effectiveness of various models and heuristics created in cooperation with Yield Riser Ltd.: a company representing Publishers in the RTB market. The whole is summarized by recommendations for further research.
Each of the participants of the RTB market described above has its own function of purpose, which it tries to maximize. Due to information asymmetry and the complexity of auction mechanisms, this raises many challenges. Access to data and the high practical importance of the problem motivates researchers to formulate and test hypotheses that help to achieve a competitive advantage in these markets. Below we will present an outline of current research challenges and the attempts to solve them both from the publishers’ and advertisers’ perspectives.
The main goal of advertisers is to buy the best possible advertising space at the lowest possible price. In most cases, this purchase is part of a broader advertising campaign having some specific goals (product, audience, etc.), budget, and lead time. The Advertiser, after receiving information about the currently available advertising space and the visiting client (bid request enhanced by user information data), must very quickly decide on the participation of the auction and determine the price she will be willing to pay. It does so under conditions of incomplete information: it does not know both the minimum (reserve) price set by the Publisher and the prices offered by other Advertisers. In second-price auctions, only the winner of the auction knows the selling price - the other bidders only know that someone has offered a higher price, which is called right-censored data.
One of the most popular strategies to deal with such cases is the so-called landscape forecasting, which involves forecasting the probability distribution of prices offered by the market for each auction. There are many approaches to solving this problem. One group of methods based on survival analysis in medical science, taking into account only the loosing logs (cf. Wang, et al., 2016; Wu, Yeh, and Chen, 2018; Wu, Yeh, and Chen, 2015). Ren, et al. (2019) in turn use survival analysis methods for censorship handling, and recurrent deep neural networks for modeling conditional winning probability with respect to each bid price.
Another approach, based on reinforcement learning (RL), is described in (Cai, et al., 2017). The Algorithm representing the Advertiser (called
The most common approach to solve this issue is to simulate the RTB market with historical data, but that approach can’t be implemented in real-life applications (
Another challenge addressed in contemporary research on the optimization of space purchase price determination processes on RTB markets is the high dynamics of these environments. As a result, the process of making purchase decisions cannot be treated as a stationary optimization problem. This problem is addressed by many groups of researchers (Cai, et al., 2017; Lu, et al., 2019; Yang, et al., 2020), as a solution proposing various reinforcement learning options.
The perspective of advertisers presented above is often the basis for the creation of price optimization strategies by publishers, which will be briefly presented later in this work.
The main objective of the Publishers is to maximize the profit from the sale of their advertising space, both in off-line channels (e.g., via direct contracts) and online (e.g., on RTB markets). For each new issue, they must make an immediate decision on the distribution channel and the minimum price level. Too low a price generates a risk of loss of profit, too high - a risk of no emissions (Li, Ni, and Yuan, 2018). In second-price auction systems, the situation is further complicated by the fact that there are many advertisers in the market offering very low purchase prices. This motivates the creation of a strategy for setting reserve prices, protecting publishers from practically free access to their space.
The strategy of setting reserve prices is very important, not only for publishers (who are guaranteed a certain level of selling prices for advertising space), but also for the entire RTB ecosystem (determining the balance between supply and demand) (Li, et al., 2017). Publishers, like advertisers, do not know the behavior of their competitors (other publishers) and potential customers. The situation is complicated by the fact that advertising space is sold both on-line (currently dominant) and off-line (direct B2B sales). As a result, the Publisher must set separate reserve prices for both channels, but also decide very quickly which channel to offer given advertising space.
Researchers have for years been dealing with the issue of optimizing reserve prices in auction systems (Myerson, 1981; Riley and Samuelson, 1981). The most common current reserve selling price strategies focus on the forecasting of the advertisers’ pricing strategies (Li, et al., 2017). Other methods apply iterative price change in the direction of the gradient of an appropriately constructed Lagrangian relaxation (Radovanovic and Heavlin, 2012).
A similar, iterative, real-time approach to price optimization, was proposed by Austin et al. (Austin, et al., 2016). In turn, Li et al. investigated the theoretical and empirical methods of the impact of reserve price levels on the profits of publishers offering their space simultaneously in multiple channels (Li, Ni and Yuan, 2018).
As can be seen, there are many strategies for determining the purchase and sale prices of advertising space in RTB markets. Most of them focus on “revenue” indicators, which can be calculated from parameters such as Ad Request eCPM or Estimated Revenue. It turns out, however, that effective management of Publisher's advertising space cannot focus only on profit: it is also very important that the space is used to its maximum extent, which is measured by the so-called Coverage ratio.
Next, strategies based on advertisers’ pricing policies in most cases (especially when supported by Reinforcement Learning algorithms) consume significant computing power to (re)train algorithms and make predictions. Moreover, in our approach, we should take into account market dynamics. And, finally, every decision supporting system needs to be well understood by its users (in our case RTB consultants) which is not the case for advanced market simulations systems based on, e.g. deep learning algorithms.
Therefore, the research problem boils down to proposing such a strategy setting reserve prices for publishers, which satisfies the following conditions:
achieves high margins on particular ad emissions while taking care of the level of advertising filling of the whole site (measured by Coverage parameter); treats and RTB market as a dynamic environment (real-time dynamics); is easy to understand and interpret by RTB consultants responsible for setting reserve price levels; is computationally efficient: a model for hundreds of inventories can be re-trained on a daily basis on reasonably priced servers.
The method of determining reserve prices described below was developed in cooperation with Yield Riser Ltd (YR). YR operates on a Supply Side of RTB Market, and manages its’ customers (Publishers) portals via Google AdManager (GAM). Each day YR consultants monitor the efficiency of inventories (called AdUnits) analyzing a lot of available data, but focusing on three of the most important efficiency measures: Estimated Revenue (an estimation of revenue from a given AdUnit), Ad request eCPM (which measures the income from a given ad placement per 1000 displays) and Coverage (a measure of how efficiently a given inventory is utilized).
In their daily practice, YR consultants create the so-called pricing rules to set the optimal minimal bidding prices for their customers (Publishers) inventories, basing on Ad Exchange reports and personal experience. This “manual” process is time-consuming and prone to errors. The main goal of the project was to automate this process using state of the art, self-optimizing machine learning algorithms.
The main research problem is to formulate a method for determining the reserve prices of advertised space offered by publishers on the RTB market. In the heuristics proposed, time series forecasting of the Coverage coefficient turned out to be crucial, which determined the second of the research objectives: to identify the machine learning algorithm that best predicts this measure. The last goal was to indicate potential directions of research aimed at optimizing the economic efficiency of advertising space sales on the RTB market.
This research project, implemented in the period from October 2019 to February 2020, according to CRISP-DM methodology (Chapman, et al., 2004), was divided into the following, about 3 months long, stages:
The
In mid-2019, Google announced a gradual transition from the second-price auction to the first-price auction, which had a strong impact on the strategy for reserve prices optimization. Coverage (a measure of how efficiently a given inventory is utilized) was identified as the key indicator for maximizing customer profits. Next, based on the analysis of GAM reports and YR consultants experience, a reserve price strategy was developed based on the prediction of this indicator for the next thres days:
If the predicted Coverage is higher than 95%: increase the price; If the predicted Coverage is between 90% and 94: hold the existing price; If the predicted Coverage is lower than 90%: decrease the price.
The practical implementation of this strategy required the creation of a Coverage prediction model. The first stage was to acquire, analyze, and prepare for modeling the appropriate time series (
The best one was implemented in the production system with a dedicated Business Intelligence (BI) dashboard, for a given inventory visualizing selected GAM parameters, many additional data aggregates, time series with forecasts and recommendations to reduce, maintain or increase the reserve price. Details of the methods used at these stages are presented below, and the results of research in the next part of this study.
As mentioned above, the main source of data was Google AdManager (GAM), which offers many configurable reports (for all definitions, dimensions, and measures, see e.g., Ad Exchange historical report - Google Ad Manager Help, 2020). Sample dimensions are buyers (e.g., brands and their verticals), inventory segments (including pricing rules, sites, sizes, and channels), geography (countries), mobile devices details (device, operating systems) and time (days, weeks, and months, 2 years back). For each of these dimension, we can obtain many different measures, the most important being ad requests (all, matched, and CTR), ad request estimated Cost Per Mile (areCPM), matched eCPM, and Coverage.
Data may be obtained directly from GAM interface or via Application Programming Interface (API). In this analysis (univariate time series analysis and planning), we use a small subset of available data, literary one
Although data obtained from GAM is very clean, the most important and time-consuming part of this project was data preparation. That process was split into two phases: datasets preparation for time series forecasting and feature engineering for additional analysis, later on displayed in a dedicated BI dashboard.
The main goal of the modelling phase was to identify the best possible time series forecasting algorithm for the Coverage parameter. In our analysis, we investigated a large spectrum of prediction algorithms - since it's impossible to present all of them in details; below we display only their most important aspects.
For an interesting study of these algorithms for time series forecasting, especially it's comparative analysis, see e.g. (Makridakis, Spiliotis and Assimakopoulos; 2018), and for implementation in Python, see e.g. (Brownlee, 2018b; and Brownlee, 2018a). In this project we apply only the so called
There are 2 different simple (naïve) forecasting strategies (for more details see e.g. (Brownlee, 2018a)): naïve, where past observations are used directly to forecast future values and average, where to forecast the future different statistics of past observations are used. A naïve forecast involves using the previous observations directly as the forecast without any change (so called a persistence forecast). In case we want to adjust this naïve forecast for seasonal effects, we can offset the historical data by a seasonal time lag. E.g., with seasonality = 7 days (which is our case), as a persistence forecast, we can take the observation with 7 timestep (days) back.
An average forecast strategy uses averaging prior value as predictions. All prior observations are collected and averaged, either using the mean or the median, with no other treatment to the data (Brownlee, 2018a). The number of prior observations averaged is controlled by the model parameter, which later on may be grid-searched in the model optimization procedure. Since
Auto Regressive Integrated Moving Average (ARIMA) models proved to be very effective in modeling Coverage time series. In brief,
Each of these aspects is reflected in ARIMA model parameters. With standard notation in the form ARIMA (p, d, q), where:
p - stands for the number of lag observations included in the model (also called d - is the number of times that the row observations are differenced ( q - is the size of the moving average window.
In ARIMA, a regression model is constructed (see e.g.: Brownlee, 2018b; Autoregressive integrated moving average, 2020) using the prepared data, specifically differenced to make a time series stationary. Differencing is a relatively simple transformation applied to a time series, where we eliminate trend and seasonal structures by computing the difference between consecutive observations:
Sometimes this process may be repeated – the number of these iterations is called a
SARIMA (Hipel and McLeod, 1994) extension supports the direct modeling of the seasonal component of the series. It uses differencing to remove addictive seasonal effects. In that case, four additional seasonal parameters are introduced:
P - seasonal autoregressive order, D - seasonal difference order, Q - seasonal moving average order, and m - the number of time steps for a single seasonal period.
These seasonal parameters may be identified by a careful study of autocorrelation plots (correlations of recent time steps).
The general procedure for all the algorithms implemented was the following. After loading the dataset, we prepared the test harness: split the dataset in train and test dataset in proportion 9:1, and applied a walk-forward validation procedure (very efficient in case of time series forecasting model evaluation). Next, the model was defined, and appropriate (model-depending) hyperparameter space configured and grid-search performed. Finally, models were evaluated (using RMSE as a quality measure), and the best performing model configuration was identified.
After the basic time-series analysis, including autocorrelation and stationarity checks, in order to identify the best forecasting model, we implemented the score and evaluate models described above. With Root Mean Square Error (RMSE) as a forecast quality measure, our goal is to identify the best one. In case we get satisfactory forecasting (prediction error at the level of 10% of Coverage or lower), we will suggest this as a first, simple method of setting up a pricing rule.
As an evaluation metric for time series forecasting models, we propose RSME (Root Mean Squared Error) as easy to understand measure of the prediction quality:
Compared to an alternative measure - Mean Absolute Error (MAE):
RMSE gives a relatively high weight to large errors (errors are squared before averaging). Since in our analysis large errors are undesirable, we choose RMSE as a metric to score forecasting models.
To evaluate the model a
As first, the exploratory data analysis (EDA) was performed. The dataset, with Coverage time series of app. 600 AdUnits for the period 01.2019–11.2019, was divided into three tertiles containing low, medium and high Coverage ones.
Next, we randomly picked three representatives for each category. Exploratory visualization for these nine representative AdUnits is presented in Fig. 2.
Figure 2
Line plot of Coverage time series for low, medium and high Coverage AdUnits (
Additionally, we performed Coverage time series decomposition - an example for the same is displayed on Fig. 3
Figure 3
Coverage time series decomposition for a sample AdUnit (
As can be seen, on average, it's hard to identify any trends or seasonality (which is obvious taking into account that AdUnits belong to very different website categories). Some obvious outliers are present in most of the sample AdUnits. To check time-series stationarity, we performed a series of AdFuller (ADF) tests. In most, they appeared to be stationary: for four (out of nine), ADF Statistics are larger than the critical value at 1%, thus these datasets seem NOT to be stationary. But at 5% level, most of the time series are stationary. Autocorrelation plots showed that, with some small exceptions, we don’t observe a significant autocorrelation.
Having analyzed the data and prepared for modelling, according to our research methodology, we started with the benchmark model identification. For that we chose the persistence forecast model: a very simple heuristics, where the value from step “t” is used as a prediction for step t+1. The RMSE for this baseline model, averaged over 9 AdUnits = 11.20.
Next, we applied different time series modelling techniques to nine representative AdUnits. We started with autoregressive models. Following results of our previous research (not covered in this paper), we focused on Seasonally adjusted ARIMA. We searched over the following parameter values:
p = (0, 1, 2), d = (0, 1), q = (0, 1, 2), t = ‘n’ (no trend), ‘c’ (constant), ‘t’ (linear) and ‘ct’ (constant with linear trend), P = (0, 1, 2), D = (0, 1), Q = (0, 1, 2), m = (0, 7).
The grid search over this parameter space showed that the best model has the following configuration: Model (2, 1, 2), (0, 0, 2, 7), ‘n’], which reads:
for trend elements:
p = 2 < trend autoregression order, d = 1 < trend difference order, q = 2 < trend moving average order; for seasonal elements:
P = 0 < seasonal autoregressive order, D = 0 < seasonal difference order, Q = 0 < seasonal moving average order, m = 7 < the number of time steps for a single seasonal period, t = ‘n’ < no trend parameter.
It's RMSE (averaged over 9 AdUnits, excluding one outlier) equaled to 8.48. In conclusion: SARIMA model significantly improves our benchmark, although computations were extremely time consuming.
Next, we evaluated Exponential Smoothing (ETS) models. Since ETS computations are also extremely time consuming, we didn’t perform a systematic grid search, but tried different manual configurations. Approximately 10 experiments over these models showed resulted in the best model with the following hyper-parameter set-up:
T = None (trend is dropped), D = False (trend shouldn’t be damped), s = Additive (seasonal component is additive), p = 7 (seasonal period = 7 time steps), and b = False (we do not perform power transform of the series).
It's (averaged over 9 AdUnits) RMSE = 8.37, which is better than our benchmark and SARIMA models. Other model setup's, with a bit worse (but comparable) RMSEs, were with t = ‘add’ (additive trend), s = ‘mul’ (multiplicative seasonality), and different values of seasonal period p (1, 2, 20).
Conclusion:
ETS model significantly improves our benchmark, and it's quality is comparable to the best SARIMA model.
Finally, we evaluated a Facebook Prophet library. Interestingly, its basic configuration resulted in RMSE (averaged over 9 AdUnits) = 10.6, what is worse than ETS and SARIMA, with low-Coverage AdUnits representatives being significant “outliers” (in terms of RMSE). Computation for medium and high coverage representatives, combined with
The evaluation of all the time series forecasting models evaluations is presented in Table 1.
Evaluation of time series forecasting models (
| Model | RMSE |
|---|---|
| Baseline (persistance) | 11.20 |
| SARIMA | 8.48 |
| ETS | 8.37 |
| Facebook Prophet (Medium and High Coverage) | 6.71 |
Since, in 1. YR focused mostly on high Coverage AdUnits, 2. it's heuristics for setting up the minimal bidding prices takes into account high (>90%) Coverage values and 3. Facebook Prophet model training was significantly faster than SARIMA and ETS, we have identified Facebook Prophet as the most promising set of models.
To support YR consultants in their daily practice, a dedicated, interactive BI dashboard has been implemented.
For a given AdUnits, it displays:
basic statistics; time series forecasting for key parameters: Coverage, AreCPM, and Estimated Revenue; and a set of advanced AdUnit features, useful in in-depth analysis.
An example screen of this dashboard is presented in Fig. 4.
Figure 4
An interactive dashboard with recommendations based on Coverage forecasting (
The main goal of the research was to recommend a method for setting minimal prices for Publishers’ inventories on RTB markets focusing on both profit and Coverage optimization. Based on the research presented in this paper, hundreds of experiments and YR consultants’ experience, we derived the following heuristics:
Set up app. 10 so called pricing baskets for minimal prices, the first one being “no minimal price”, the 10th one being a maximum reasonable minimal price; For a given AdUnit, predict the Coverage value for next three days using the best possible prediction algorithm; If the predicted Coverage is:
higher than 95%: increase the price (move the reserve price to a “higher” basket, if possible), between 90% and 94: hold the existing price, lower than 90%: decrease the price (move the reserve price to a “lower” basket, if possible).
The quality of minimal price recommendations is driven by the quality of forecasting algorithms. Thus, the second main goal of this project was to identify the best possible forecasting model for
The dataset used for a procedure was 1-years’ historical
As a measure of model accuracy, we choose Root Mean Squared Error (RMSE). Facebook Prophet algorithm has been found as the most promising one: not only did it scored the minimal RMSE error (for medium and high values Coverage representatives), but it was also the fastest (in terms of computing time) one.
The third goal of this research was to lay the foundations for future recommendation algorithms. The most natural approach would be to use Reinforcement Learning (RL). As shown in the Literature Review part of this paper, RL algorithms are being commonly applied in the bidding price optimization problem on RTB markets.
The main concern with such approaches lies in fact that most (if not all) approaches are based on historical data as a foundation of RL environment simulation, while to prove RL efficiency in practice, it should be applied to real-life situations. This is possible to implement, but since market feedback to price changes are counted in hours, there is a risk that it will take years (thousands of interactions needed) literally to train the final algorithm.
To sum up, the study proposed a new method of optimizing the prices of minimum advertising space offered by the publishers on the RTB markets, focusing not only on the profits from individual issues, but also on ensuring maximum filling (Coverage) of advertising space.
The latest machine learning algorithms were used for this purpose, identifying the