Using Predicted Weights for Ad Delivery

Thomas Lavastida, Benjamin Moseley, R. Ravi, Chenyang Xu

Abstract: This paper introduces the Improved Proportional Weights (IPW) algorithm, a novel approach for the capacitated online bipartite matching problem in real-time ad delivery. By integrating machine-learned predictions from historical data, IPW optimizes the allocation of ad impressions to advertisers under budget constraints. Evaluated on large-scale Yahoo! search data, IPW consistently achieves competitive ratios near 0.99, significantly outperforming traditional greedy and ranking-based baselines. The algorithm demonstrates remarkable robustness to prediction errors and adversarial arrival orders, maintaining high efficiency even with training samples as small as 1%.

Introduction

In the ecosystem of online advertising, platforms must decide in milliseconds which advertiser should receive a specific user impression. This challenge is formally defined as a capacitated online bipartite matching problem: impressions arrive sequentially and must be matched to advertisers who have finite budgets or capacities.

Traditional algorithms, such as the well-known Ranking algorithm, are designed to provide theoretical guarantees for the "worst-case" scenario (e.g., matching at least 63.2% of the optimal). However, these methods often fail to leverage the wealth of historical data available in modern systems. This research explores how "predictions" about future traffic—derived from past data—can be used to beat worst-case bounds without becoming fragile to prediction inaccuracies.

Methodology: The IPW Algorithm

The authors focus on the Proportional Weights (PW) algorithm, which assigns a weight ($\alpha$) to each advertiser based on historical demand. When an impression arrives, it is split fractionally among eligible advertisers in proportion to these weights.

The paper's primary contribution is the Improved Proportional Weights (IPW) algorithm. While standard PW can waste impressions by attempting to assign them to advertisers who have already reached their capacity, IPW dynamically redistributes the impression only among "unfull" advertisers. This simple yet effective modification makes the algorithm "instance-robust," allowing it to handle moderate errors in predicted weights gracefully.

Furthermore, the researchers demonstrate that these optimal weights can be learned efficiently from a small random sample of the day's impressions, which can then be applied to the remainder of the traffic.

Experimental Evaluation

The algorithms were tested using a massive dataset of nearly 78 million records from Yahoo! Search Marketing, encompassing advertiser bids, impressions, and clicks. To ensure the results were not dependent on a specific budget configuration, the authors employed three synthetic quota schemes:

  1. Random Quota: Budgets assigned randomly.
  2. Max-min Quota: Budgets designed to balance allocation.
  3. Least-degree Quota: Budgets assigned based on the number of eligible advertisers.

Results and Discussion

Across all tested scenarios, IPW consistently outperformed the Greedy (water-filling) and Ranking baselines.

Competitive ratios for IPW and baselines across three synthetic quota distributions: (a) Random, (b) Max-min, and (c) Least-degree.

As illustrated in the figure above, IPW maintains a competitive ratio near 0.99 regardless of the training ratio $\sigma$. Notably, even a 1% sample ($\sigma = 0.01$) was sufficient to learn weights that outperformed non-predictive algorithms. This indicates high data efficiency and suggests that underlying traffic patterns are stable enough for yesterday's data to effectively guide today's delivery.

Adversarial Resilience

A critical concern for predictive algorithms is their performance when predictions are wrong or the environment is hostile. The authors found that while traditional greedy methods saw their performance drop significantly in challenging arrival orders, the weight-based IPW remained stable.

Performance comparison under challenging arrival conditions, demonstrating IPW's stability compared to the degradation of Greedy and Ranking baselines.

In these more difficult instances, the competitive ratio for Greedy and Ranking algorithms fell to approximately 0.83, whereas IPW continued to perform near the 0.99 mark. This resilience confirms that proportionality keeps allocation options open, leading to a more globally optimal result than myopic greedy strategies.

Conclusion

The IPW algorithm represents a significant step forward in combining machine learning with online algorithm design. By using predicted weights, ad platforms can achieve near-optimal matching efficiency that is robust to the inherent uncertainties of real-time traffic. Future work may extend this framework from simple cardinality matching to the full "AdWords problem," where different impressions carry varying monetary values (bids).

Summary updated

BibTeX
@inproceedings{lavastida2021using,
  author = {Thomas Lavastida and Benjamin Moseley and R. Ravi and Chenyang Xu},
  title = {{Using Predicted Weights for Ad Delivery}},
  booktitle = {ACDA},
  year = {2021},
  url = {https://openreview.net/forum?id=vV8xvaT0zug},
}
Figure