Scalable Bid Landscape Forecasting in Real-Time Bidding

Aritra Ghosh, Saayan Mitra, Somdeb Sarkhel, Jason Xie, Gang Wu, Viswanathan Swaminathan

Abstract

In programmatic advertising, ad slots are usually sold using second-price (SP) auctions in real-time. The highest bidding advertiser wins but pays only the second-highest bid (known as the winning price). In SP, for a single item, the dominant strategy of each bidder is to bid the true value from the bidder's perspective. However, in a practical setting, with budget constraints, bidding the true value is a sub-optimal strategy. Hence, to devise an optimal bidding strategy, it is of utmost importance to learn the winning price distribution accurately. Moreover, a demand-side platform (DSP), which bids on behalf of advertisers, observes the winning price if it wins the auction. For losing auctions, DSPs can only treat its bidding price as the lower bound for the unknown winning price. In literature, typically censored regression is used to model such partially observed data. A common assumption in censored regression is that the winning price is drawn from a fixed variance (homoscedastic) uni-modal distribution (most often Gaussian). However, in reality, these assumptions are often violated. We relax these assumptions and propose a heteroscedastic fully parametric censored regression approach, as well as a mixture density censored network. Our approach not only generalizes censored regression but also provides flexibility to model arbitrarily distributed real-world data. Experimental evaluation on the publicly available dataset for winning price estimation demonstrates the effectiveness of our method. Furthermore, we evaluate our algorithm on one of the largest demand-side platforms and significant improvement has been achieved in comparison with the baseline solutions.

1. Introduction

In Real-time Bidding (RTB), Demand-Side Platforms (DSPs) must forecast the "bid landscape"—the probability distribution of winning prices—to optimize bidding strategies under budget constraints. A primary obstacle in this task is right-censored data. When a DSP wins an auction, it observes the winning price. However, when it loses, it only knows that the winning price was higher than its own bid.

Traditional censored regression models typically assume that winning prices follow a unimodal Gaussian distribution with fixed variance (homoscedasticity). In practice, these assumptions are frequently violated by the complex, multi-modal nature of real-world auction data.

2. Methodology

To overcome the limitations of standard models, this research introduces two primary advancements:

  1. Fully Parametric Censored Regression (P-CR): Unlike standard models that assume a constant variance ($\sigma$), P-CR models variance as a function of input features. This accounts for heteroscedasticity, acknowledging that different ad traffic segments have varying levels of predictability.
  2. Mixture Density Censored Network (MCNet): This core contribution utilizes a neural network to output parameters (weights, means, and variances) for multiple Gaussian distributions. By combining these components, MCNet can approximate nearly any continuous probability density function, effectively capturing multi-modal bid landscapes.

2.1 Handling Censored Data

Both models utilize a specialized loss function for training. For winning auctions, the model maximizes the probability density at the observed price. For losing (censored) auctions, it maximizes the cumulative probability that the winning price is greater than the placed bid.

3. Experimental Evaluation

The proposed methods were evaluated on two datasets: iPinYou (a public benchmark) and Adobe AdCloud (a proprietary dataset with over 31 million samples and 33,000 features). Performance was measured using Average Negative Log Probability (ANLP).

  • Accuracy Gains: MCNet improved upon standard Censored Regression by over 30% on the iPinYou dataset.
  • Superiority over Baselines: MCNet outperformed Survival Trees, a common non-parametric baseline, by more than 10% across both datasets.
  • Scalability: While non-parametric methods often require aggressive feature trimming to handle high-dimensional data, MCNet scales efficiently to the full feature set of production-scale datasets.

4. Discussion and Key Insights

The effectiveness of MCNet stems from its ability to model the inherent complexity of bid landscapes that simpler models ignore.

Comparison of Kaplan-Meier (KM) estimates and Gaussian fits for two distinct clusters, illustrating the multi-modal and heteroscedastic nature of bid landscapes.

As illustrated in Figure 1, empirical bid distributions (blue lines) are often multi-modal (Cluster 1) or extremely peaked (Cluster 2). Standard Gaussian fits (red lines) provide poor approximations in these scenarios. By modeling variance dynamically and allowing for multiple distribution components, MCNet captures these nuances, leading to more accurate winning price forecasts.

5. Conclusion

MCNet provides a scalable, flexible framework for bid landscape forecasting by integrating deep learning with censored regression. While the current implementation uses Gaussian mixtures, future work could explore alternative base distributions or more complex neural architectures to further refine performance in diverse auction environments.

Summary updated

Abstract

In programmatic advertising, ad slots are usually sold using second-price (SP) auctions in real-time. The highest bidding advertiser wins but pays only the second-highest bid (known as the winning price). In SP, for a single item, the dominant strategy of each bidder is to bid the true value from the bidder's perspective. However, in a practical setting, with budget constraints, bidding the true value is a sub-optimal strategy. Hence, to devise an optimal bidding strategy, it is of utmost importance to learn the winning price distribution accurately. Moreover, a demand-side platform (DSP), which bids on behalf of advertisers, observes the winning price if it wins the auction. For losing auctions, DSPs can only treat its bidding price as the lower bound for the unknown winning price. In literature, typically censored regression is used to model such partially observed data. A common assumption in censored regression is that the winning price is drawn from a fixed variance (homoscedastic) uni-modal distribution (most often Gaussian). However, in reality, these assumptions are often violated. We relax these assumptions and propose a heteroscedastic fully parametric censored regression approach, as well as a mixture density censored network. Our approach not only generalizes censored regression but also provides flexibility to model arbitrarily distributed real-world data. Experimental evaluation on the publicly available dataset for winning price estimation demonstrates the effectiveness of our method. Furthermore, we evaluate our algorithm on one of the largest demand-side platforms and significant improvement has been achieved in comparison with the baseline solutions.
BibTeX
@inproceedings{ghosh2019scalable,
  author = {Aritra Ghosh and Saayan Mitra and Somdeb Sarkhel and Jason Xie and Gang Wu and Viswanathan Swaminathan},
  title = {{Scalable Bid Landscape Forecasting in Real-Time Bidding}},
  booktitle = {ECML/PKDD},
  year = {2019},
  doi = {10.1007/978-3-030-46133-1\_27},
}
Figure