# Using Predicted Weights for Ad Delivery

arXiv: https://arxiv.org/abs/2106.01079 · HTML: https://mlsanity.com/paper/2106.01079/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2021.

## Built on by (most cited first, 7 of 7)

- [Permutation Predictions for Non-Clairvoyant Scheduling](https://mlsanity.com/paper/2202.10199/) (2022)
- [Online bipartite matching with imperfect advice](https://mlsanity.com/paper/2405.09784/) (2024)
- [Online Ad Allocation with Predictions](https://mlsanity.com/paper/2302.01827/) (2023)
- [Scheduling with Predictions](https://mlsanity.com/paper/2212.10433/) (2022)
- [Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model](https://mlsanity.com/paper/2402.13530/) (2024)
- [On Optimal Consistency-Robustness Trade-Off for Learning-Augmented Multi-Option Ski Rental](https://mlsanity.com/paper/2312.02547/) (2023)
- [Online and Streaming Algorithms for Constrained k-Submodular Maximization](https://mlsanity.com/paper/2305.16013/) (2023)

## Abstract (arXiv)

We study the performance of a proportional weights algorithm for online capacitated bipartite matching modeling the delivery of impression ads. The algorithm uses predictions on the advertiser nodes to match arriving impression nodes fractionally in proportion to the weights of its neighbors. This paper gives a thorough empirical study of the performance of the algorithm on a data-set of ad impressions from Yahoo! and shows its superior performance compared to natural baselines such as a greedy water-filling algorithm and the ranking algorithm. The proportional weights algorithm has recently received interest in the theoretical literature where it was shown to have strong guarantees beyond the worst-case model of algorithms augmented with predictions. We extend these results to the case where the advertisers' capacities are no longer stationary over time. Additionally, we show the algorithm has near optimal performance in the random-order arrival model when the number of impressions and the optimal matching are sufficiently large.