Optimal delivery in display advertising

In display advertising, a publisher targets a specific audience by displaying ads on content web pages. Because the publisher has little control over the supply of display opportunities, the actual supply of ads that it can sell is stochastic. We consider the problem of optimal ad delivery, where an advertiser requests a certain number of impressions to be displayed by the publisher over a certain time horizon. Time is divided into periods, and in the beginning of each period the publisher chooses a fraction of the still unrealized supply to allocate towards fulfilling the advertiser's demand. The goal is to be able to fulfill the demand at the end of the horizon with minimal costs incurred from penalties associated with shortage or over-delivery of ads. We describe optimal policies that are both simple in structure and easy to implement for several variations of this problem.