Algorithmic Aspects of Online Advertising

on YouTube ↗38m

" summary

Defines the online budgeted ad-allocation (AdWords) model, proves greedy can be as bad as 1/2 worst-case and gives a multiplicative pacing algorithm that achieves 1-1/e (≈0.63) which is optimal under small bid-to-budget ratios. Uses a primal-dual LP view, extends to stochastic i.i.d. arrivals (learning LP duals) with near-optimal loss, generalizes to display auctions with additive pacing, and reports Microsoft deployed a continuous-learning variant at scale.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 2:44HOW ADS ARE SOLD
3. 6:21GREEDY ALGORITHM
4. 7:48COMPETITIVE RATIO
5. 8:11OPTIMAL ONLINE ALLOCATION
6. 10:00A FEW COMMENTS ABOUT THE MODEL
7. 12:52PRIMAL-DUAL INTERPRETATION
8. 17:55DISPLAY ADS OPTIMIZATION AKA ONLINE WEIGHTED MATCHING
9. 20:31GENERALIZATIONS
10. 22:20IMPLEMENTATIONS IN PRACTICE
11. 23:36SUMMARY • A lot of progress in budget optimization
12. 26:57ONLINE ALGORITHMS
13. 28:29ONLINE MATCHING
14. 29:54ONLINE STOCHASTIC MATCHING