Scalable Bid Landscape Forecasting in Real-Time Bidding

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

TL;DR

This paper tackles the challenge of accurately forecasting winning bid prices in real-time advertising auctions, which is crucial for advertisers to optimize their bidding strategies. The authors propose a novel Mixture Density Censored Network (MCNet) that overcomes limitations of existing methods by handling arbitrarily distributed winning prices and partially observed data, achieving significant performance improvements.

What Problem Does This Paper Address?

In real-time bidding (RTB) for online advertising, ad slots are auctioned off to advertisers. A common auction mechanism is the second-price auction, where the highest bidder wins but pays the second-highest bid (the winning price). For an advertiser to bid optimally, especially under budget constraints, they need to accurately predict the distribution of these winning prices. However, this is challenging because advertisers only observe the winning price if they win an auction; otherwise, they only know that the winning price was at least as high as their own bid (right-censored data).

Traditional methods like censored regression often assume that winning prices follow a simple, unimodal distribution (like Gaussian) with a fixed variance. The authors argue that these assumptions are frequently violated in real-world data, leading to suboptimal bidding strategies. They aim to develop a more flexible and scalable approach that can model complex, arbitrary winning price distributions from partially observed data.

Methods

The paper builds upon censored regression but relaxes its restrictive assumptions.

  • Fully Parametric Censored Regression (P-CR): This approach relaxes the homoscedasticity assumption (fixed variance) by allowing the variance of the winning price distribution to depend on the bid request features. This is achieved by modeling the standard deviation as an exponential function of the features.
  • Mixture Density Censored Network (MCNet): This is the core novel contribution. MCNet extends the idea of Mixture Density Networks (MDNs) to handle censored data. MDNs are known for their ability to approximate arbitrary continuous distributions. MCNet uses a neural network to learn the parameters (mean, standard deviation, and weights) of a mixture of Gaussian distributions, allowing it to model multi-modal and complex winning price distributions. This approach is more general than standard censored regression and can capture the nuances of real-world data.

Both proposed methods are framed as optimization problems to maximize the likelihood of observed data, and they are trained using the Adam optimizer.

Datasets

The authors evaluated their methods on two main datasets:

  • iPinYou Dataset: A publicly available dataset containing censored winning price information from online advertising auctions. They used sessions 2 and 3 of this dataset, splitting it into training, validation, and testing sets.
  • Adobe Adcloud Dataset: A proprietary dataset collected from Adobe's demand-side platform (DSP). This dataset was used to assess the scalability and efficacy of their approach on real-world industry data.

Key Insights and Ideas

  • Violation of Standard Assumptions: The paper strongly demonstrates that real-world winning price distributions are often not unimodal or homoscedastic, invalidating common assumptions in traditional censored regression.
  • Importance of Distributional Forecasting: Predicting the entire distribution of winning prices, rather than just a point estimate, is crucial for optimal bidding strategies, especially for budget pacing and maximizing utility.
  • Flexibility of Mixture Models: Mixture density models, when combined with neural networks and adapted for censored data, offer a powerful and flexible way to capture complex, arbitrary distributions that simple parametric models miss.
  • Scalability Matters: While non-parametric methods can be accurate, their computational cost can be prohibitive for large-scale RTB systems. The proposed MCNet offers a scalable parametric approach.

Key Results

  • Significant Improvement: MCNet consistently outperformed existing methods, including Censored Regression (CR), Fully Parametric Censored Regression (P-CR), and non-parametric methods like Kaplan-Meier (KM) and Survival Trees (ST).
  • MCNet vs. CR: MCNet improved upon CR by more than 30% on average across dates in the iPinYou dataset, highlighting the benefit of modeling arbitrary distributions.
  • P-CR vs. CR: P-CR showed improvements over CR (around 5-10%), confirming the importance of relaxing the fixed variance assumption.
  • MCNet vs. ST: MCNet performed comparably to or better than Survival Trees (ST), a strong non-parametric baseline, especially when using similar feature sets.
  • Adobe Adcloud Results: On the proprietary Adobe dataset, MCNet improved CR by 25% and ST by over 10%, demonstrating its effectiveness on industry-scale data.

Limitations and Future Work

  • Non-Identifiability in Censored Region: The paper acknowledges that without any assumptions, predicting the winning price distribution beyond the maximum observed bid price (the censored region) is inherently non-identifiable. MCNet, like KM, faces this limitation.
  • Base Distribution Choice: While MCNet can approximate any smooth distribution, further research is needed on the optimal choice of base distributions for the mixture model.
  • Combining Parametric and Non-Parametric Ideas: The authors suggest exploring ways to combine distributional assumptions with MCNet to better handle the censored region where winning prices are never observed.
  • Deep Network Architectures: The current MCNet uses a single hidden layer; exploring deeper neural network architectures could potentially further improve performance.

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},
}

Loading related content...

Figure