Frequency capping in online advertising

We study the following online problem. There are n advertisers. Each advertiser has a total demand and a value for each supply unit. Supply units arrive one by one in an online fashion, and must be allocated to an agent immediately. Each unit is associated with a user, and each advertiser is willing to accept no more than units associated with any single user (the value is called the frequency cap of advertiser ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic -competitiveness upper bound, which holds even when all frequency caps are , and all advertisers share identical values and demands. A competitive ratio approaching can be achieved via a reduction to a different model considered by Goel and Mehta (WINE '07: Workshop on Internet and Network, Economics: 335-340, 2007). Our main contribution is analyzing two -competitive greedy algorithms for the cases of equal values, and arbitrary valuations with equal integral demand to frequency cap ratios. Finally, we give a primal-dual algorithm which may serve as a good starting point for improving upon the ratio of 1-1/e..