# Online Ad Allocation with Predictions

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 3 Feb 2023.

## Builds on (most cited first, 8 of 8)

- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms](https://mlsanity.com/paper/2010.11443/) (2020)
- [Revenue Optimization with Approximate Bid Predictions](https://mlsanity.com/paper/1706.04732/) (2017)
- [Real-Time Bidding Benchmarking with iPinYou Dataset](https://mlsanity.com/paper/1407.7073/) (2014)
- [Online Bipartite Matching with Advice: Tight Robustness-Consistency Tradeoffs for the Two-Stage Model](https://mlsanity.com/paper/2206.11397/) (2022)
- [Using Predicted Weights for Ad Delivery](https://mlsanity.com/paper/2106.01079/) (2021)
- [Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model](https://mlsanity.com/paper/2007.12823/) (2020)

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

- [Learning-Augmented Online Bipartite Fractional Matching](https://mlsanity.com/paper/2505.19252/) (2025)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Parsimonious Learning-Augmented Online Metric Matching](https://mlsanity.com/paper/2605.26886/) (2026)
- [Online and Streaming Algorithms for Constrained k-Submodular Maximization](https://mlsanity.com/paper/2305.16013/) (2023)
- [The Secretary Problem with a Stochastic Precursor](https://mlsanity.com/paper/2605.22653/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)

## Abstract (arXiv)

Display Ads and the generalized assignment problem are two well-studied online packing problems with important applications in ad allocation and other areas. In both problems, ad impressions arrive online and have to be allocated immediately to budget-constrained advertisers. Worst-case algorithms that achieve the ideal competitive ratio are known, but might act overly conservative given the predictable and usually tame nature of real-world input. Given this discrepancy, we develop an algorithm for both problems that incorporate machine-learned predictions and can thus improve the performance beyond the worst-case. Our algorithm is based on the work of Feldman et al. (2009) and similar in nature to Mahdian et al. (2007) who were the first to develop a learning-augmented algorithm for the related, but more structured Ad Words problem. We use a novel analysis to show that our algorithm is able to capitalize on a good prediction, while being robust against poor predictions. We experimentally evaluate our algorithm on synthetic and real-world data on a wide range of predictions. Our algorithm is consistently outperforming the worst-case algorithm without predictions.