Online ads are delivered in a real-time fashion under uncertainty in an environment with strategic agents. Making such real-time (or online) decisions without knowing the future results in challenging stochastic optimization problems for ad selection and dynamic mechanism design problems for repeated auctions. In this talk, I will present a number of recent theoretical models and results in this area inspired by applications in reservation and exchange markets in display advertising.
In particular, after a short introduction, I will first highlight the practical importance of considering “hybrid” models that can take advantage of forecasting for stochastic models and at the same time, are robust against adversarial changes in the input such as traffic spikes and discuss our recent results combining stochastic and adversarial input models from recent SODA and EC papers. Then I will present more recent results concerning online bundling schemes that can be applied to repeated auction environments. In particular, we discuss ideas from our recent papers about contract design, online bundling, stateful pricing, bank account mechanisms, and Martingale auctions. We will conclude by stating a number of open problems in this area.