Whole-Page Optimization and Submodular Welfare Maximization with Online Bidders

Abstract

In the context of online ad serving, display ads may appear on different types of webpages, where each page includes several ad slots and therefore multiple ads can be shown on each page. The set of ads that can be assigned to ad slots of the same page needs to satisfy various prespecified constraints including exclusion constraints, diversity constraints, and the like. Upon arrival of a user, the ad serving system needs to allocate a set of ads to the current webpage respecting these per-page allocation constraints. Previous slot-based settings ignore the important concept of a page and may lead to highly suboptimal results in general. In this article, motivated by these applications in display advertising and inspired by the submodular welfare maximization problem with online bidders, we study a general class of page-based ad allocation problems, present the first (tight) constant-factor approximation algorithms for these problems, and confirm the performance of our algorithms experimentally on real-world datasets.

A key technical ingredient of our results is a novel primal-dual analysis for handling free disposal, which updates dual variables using a “level function” instead of a single level and unifies with previous analyses of related problems. This new analysis method allows us to handle arbitrarily complicated allocation constraints for each page. Our main result is an algorithm that achieves a 1 - 1 / e - o(1)-competitive ratio. Moreover, our experiments on real-world datasets show significant improvements of our page-based algorithms compared to the slot-based algorithms.

Finally, we observe that our problem is closely related to the submodular welfare maximization (SWM) problem. In particular, we introduce a variant of the SWM problem with online bidders and show how to solve this problem using our algorithm for whole-page optimization.

References

1. G. Agarwal, G. Goel, C. Karande, and A. Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocation. In SODA. SIAM.
2. G. Aggarwal, J. Feldman, S. Muthukrishnan, and M. Pál. 2008. Sponsored search auctions with Markovian users. WINE (2008), 621--628.
3. S. Agrawal, Z. Wang, and Y. Ye. 2014. A dynamic near-optimal algorithm for online linear programming. Operations Research 62.4 (2014), 876--890.
4. S. Athey and G. Ellison. 2011. Position auctions with consumer search. Quarterly Journal of Economics 126, 3 (2011), 1213--1270.
5. M. Babaioff, J. Hartline, and R. Kleinberg. 2009. Selling ad campaigns: Online algorithms with cancellations. In EC. 61--70.
6. L. Blumrosen and N. Nisan. 2009. On the computational power of demand queries. SIAM Journal on Computing 39, 4 (2009), 1372--1391.
7. N. Buchbinder, K. Jain, and J. S.fi Naor. 2007. Online primal-dual algorithms for maximizing ad-auctions revenue. In ESA. Springer, 253--264.
8. R. R. Burke and T. K. Srull. 1988. Competitive interference and consumer memory for advertising. Journal of Consumer Research (1988), 55--68.
9. F. Constantin, J. Feldman, S. Muthukrishnan, and M. Pal. 2009. Online ad slotting with cancellations. In SODA. 1265--1274.
10. N. Devanur and T. Hayes. 2009. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In EC. 71--78.
11. N. R. Devanur, K. Jain, and R. D. Kleinberg. 2013. Randomized primal-dual analysis of RANKING for online bipartite matching. In SODA.
12. N. R. Devanur, K. Jain, B. Sivan, and C. A. Wilkens. 2011. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. In EC. ACM, 29--38.
13. U. Feige, N. Immorlica, V. Mirrokni, and H. Nazerzadeh. 2008. A combinatorial allocation mechanism for banner advertisement with penalties. In WWW. 169--178.
14. J. Feldman, M. Henzinger, N. Korula, V. S. Mirrokni, and C. Stein. 2010. Online Stochastic Ad Allocation: Efficiency and Fairness. Technical Report.
15. J. Feldman, N. Korula, V. Mirrokni, S. Muthukrishnan, and M. Pal. 2009a. Online ad assignment with free disposal. In WINE.
16. J. Feldman, A. Mehta, V. Mirrokni, and S. Muthukrishnan. 2009b. Online stochastic matching: Beating 1-1/e. In FOCS. 117--126.
17. G. Goel and A. Mehta. 2008. Online budgeted matching in random input models with applications to adwords. In SODA. 982--991.
18. B. Haeupler, V. Mirrokni, and M. ZadiMoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In WINE. 170--181.
19. B. Kalyanasundaram and K. R. Pruhs. 2000. An optimal deterministic algorithm for online b-matching. Theoretical Computer Science 233, 1--2 (2000), 319--325.
20. C. Karande, A. Mehta, and P. Tripathi. 2011. Online bipartite matching with unknown distributions. In STOC. 587--596.
21. R. M. Karp, U. V. Vazirani, and V. V. Vazirani. 1990. An optimal algorithm for online bipartite matching. In STOC. 352--358.
22. K. L. Keller. 1991. Memory and evaluation effects in competitive advertising environments. Journal of Consumer Research (1991), 463--476.
23. D. Kempe and M. Mahdian. 2008. A cascade model for externalities in sponsored search. In WINE. Springer, 585--596.
24. R. J. Kent and C. T. Allen. 1994. Competitive interference effects in consumer memory for advertising: The role of brand familiarity. Journal of Marketing (1994), 97--105.
25. M. Mahdian and Q. Yan. 2011. Online bipartite matching with random arrivals: A strongly factor revealing LP approach. In STOC. 597--606.
26. J. Mandese. 1991. Rival spots cluttering TV. Advertising Age 18 (1991).
27. A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani. 2007. AdWords and generalized online matching. Journal of the ACM 54, 5 (2007), 22. DOI:http://dx.doi.org/10.1145/1284320.1284321
28. V. H. Menshadi, S. O. Gharan, and A. Saberi. 2011. Online stochastic matching: Online actions based on offline statistics. In SODA. 1285--1294.
29. V. S. Mirrokni, S. O. Gharan, and M. ZadiMoghaddam. 2011. Simultaneous approximations of stochastic and adversarial budgeted allocation problems. In SODA. 1690--1701.
30. PwC and IAB. 2011. IAB Internet Advertising Revenue Report, 2011. PricewaterhouseCoopers and the Interactive Advertising Bureau. Retrieved from http://www.iab.net/media/file/IAB-HY-2011-Report-Final.pdf.
31. B. Tan and R. Srikant. 2011. Online advertisement, optimization and stochastic networks. In CDC-ECC. IEEE, 4504--4509.
32. E. Vee, S. Vassilvitskii, and J. Shanmugasundaram. 2010. Optimal online assignment with forecasts. In EC. 109--118.
33. J. Vondrak. 2008. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC. 67--74.

Index Terms

• Theory of computation

  • Design and analysis of algorithms

    • Online algorithms

  • Theory and algorithms for application domains

    • Algorithmic game theory and mechanism design

      • Algorithmic game theory