Online Advertisements and Online Algorithms
summary
Shows that the balanced discount rule gives a 1-1/e competitive guarantee for online budgeted allocation via a primal‑dual LP view, then proves stochastic models (IID, random order, adversarial‑stochastic) let dual estimates be learned so competitive ratio tends to 1. It links dual updates to no‑regret expert algorithms and deploys continuous dual updates at Microsoft, improving convergence to ε^2/log N and working well in production. Also proves a stark game‑theory limit: no truthful deterministic mechanism achieves any bounded approximation for even two items.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:29ONLINE ALGORITHMS
- 3:421. ADWORDS. MERTA, SABERI, VAZIRANI, VAZIRANI, 2007.
- 6:10PRIMAL-DUAL. BUCHBINDER, JAIN, NAOR, 2007.
- 9:51STOCHASTIC MODEL. D, HAYES, 2009.
- 13:36DISPLAY ADS OPTIMIZATION AKA ONLINE WEIGHTED MATCHING
- 18:01CONTINUOUS LEARNING.
- 23:12NO-REGRET LEARNING.
- 27:55GENERALIZATIONS
- 29:42FLUID MEAN FIELD EQUILIBRIA
- 35:52ONLINE MECHANISM DESIGN
- 39:54SUMMARY
related talks
25mBudget Pacing in Repeated Auctions: Regret and Efficiency without Convergence
50mDiversity in Matching Markets
49mAlgorithmic Mechanism Design with Investment
52mDashboard Mechanisms for Online Marketplaces
29mClearing Matching Markets Efficiently: Informative Signals and Match Recommendations
32mDynamic Matching Models
56mMarket Design and Computer-Assisted Markets: An Economist's Perspective
50mQuality Selection in Two-Sided Markets: A Price Discrimination Approach