{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:32:05Z","timestamp":1767339125658,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,6]],"date-time":"2016-04-06T00:00:00Z","timestamp":1459900800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Simons Graduate Fellowship for Theoretical Computer Science","award":["252128"],"award-info":[{"award-number":["252128"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n            In the context of online ad serving, display ads may appear on different types of web\n            <jats:italic>pages<\/jats:italic>\n            , where each page includes\n            <jats:italic>several<\/jats:italic>\n            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.\n          <\/jats:p>\n          <jats:p>\n            A key technical ingredient of our results is a novel primal-dual analysis for handling free disposal, which updates dual variables using a \u201clevel function\u201d 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 -\n            <jats:italic>o<\/jats:italic>\n            (1)-competitive ratio. Moreover, our experiments on real-world datasets show significant improvements of our page-based algorithms compared to the slot-based algorithms.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/2892563","type":"journal-article","created":{"date-parts":[[2016,4,7]],"date-time":"2016-04-07T22:16:10Z","timestamp":1460067370000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":29,"title":["Whole-Page Optimization and Submodular Welfare Maximization with Online Bidders"],"prefix":"10.1145","volume":"4","author":[{"given":"Nikhil R.","family":"Devanur","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}]},{"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong"}]},{"given":"Nitish","family":"Korula","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}]},{"given":"Vahab S.","family":"Mirrokni","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, USA"}]},{"given":"Qiqi","family":"Yan","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View, CA, USA"}]}],"member":"320","published-online":{"date-parts":[[2016,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133131"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_68"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2765026.2765038"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1093\/qje\/qjr028"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566383"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958003"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"R. R. Burke and T. K. Srull. 1988. Competitive interference and consumer memory for advertising. Journal of Consumer Research (1988) 55--68.  R. R. Burke and T. K. Srull. 1988. Competitive interference and consumer memory for advertising. Journal of Consumer Research (1988) 55--68.","DOI":"10.1086\/209145"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496907"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627824"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993581"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367521"},{"key":"e_1_2_1_14_1","unstructured":"J. Feldman M. Henzinger N. Korula V. S. Mirrokni and C. Stein. 2010. Online Stochastic Ad Allocation: Efficiency and Fairness. Technical Report.  J. Feldman M. Henzinger N. Korula V. S. Mirrokni and C. Stein. 2010. Online Stochastic Ad Allocation: Efficiency and Fairness. Technical Report."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1347082.1347189"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_15"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"volume-title":"Memory and evaluation effects in competitive advertising environments. Journal of Consumer Research","year":"1991","author":"Keller K. L.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_65"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"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.  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.","DOI":"10.1177\/002224299405800307"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"volume-title":"Rival spots cluttering TV. Advertising Age 18","year":"1991","author":"Mandese J.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133134"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095250"},{"volume-title":"IAB Internet Advertising Revenue Report","year":"2011","author":"C","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"B. Tan and R. Srikant. 2011. Online advertisement optimization and stochastic networks. In CDC-ECC. IEEE 4504--4509.  B. Tan and R. Srikant. 2011. Online advertisement optimization and stochastic networks. In CDC-ECC. IEEE 4504--4509.","DOI":"10.1109\/CDC.2011.6161009"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807360"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2892563","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2892563","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:55:55Z","timestamp":1750272955000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2892563"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,6]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2892563"],"URL":"https:\/\/doi.org\/10.1145\/2892563","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"type":"print","value":"2167-8375"},{"type":"electronic","value":"2167-8383"}],"subject":[],"published":{"date-parts":[[2016,4,6]]},"assertion":[{"value":"2013-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}