Frequency capping in online advertising
Buchbinder, Niv ; Feldman, Moran ; Ghosh, Arpita ; Naor, Joseph
In: Journal of Scheduling, 2014, vol. 17, no. 4, p. 385-398
Ajouter à la liste personnelle- Summary
- We study the following online problem. There are n advertisers. Each advertiser $$a_i$$ a i has a total demand $$d_i$$ d i and a value $$v_i$$ v i 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 $$a_i$$ a i is willing to accept no more than $$f_i$$ f i units associated with any single user (the value $$f_i$$ f i is called the frequency cap of advertiser $$a_i$$ a i ). The goal is to design an online allocation algorithm maximizing the total value. We first show a deterministic $$3/4$$ 3 / 4 -competitiveness upper bound, which holds even when all frequency caps are $$1$$ 1 , and all advertisers share identical values and demands. A competitive ratio approaching $$1-1/e$$ 1 - 1 / e 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 $$3/4$$ 3 / 4 -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$$ 1 - 1 / e .