Bi-Objective Contract Allocation for Guaranteed Delivery Advertising
Pages 1691 - 1700
Abstract
Contemporary systems of Guaranteed Delivery (GD) advertising work with two different stages, namely, the offline selling stage and the online serving stage. The former deals with contract allocation, and the latter fulfills the impression allocation of signed contracts. Existing work usually handles these two stages separately. For example, contracts are formulated offline without concerning practical situations in the online serving stage. Therefore, we address in this paper a bi-objective contract allocation for GD advertising, which maximizes the impressions, i.e., Ad resource assignments, allocated for the new incoming advertising orders, and at the same time, controls the balance in the inventories. Since the proposed problem is high dimensional and heavily constrained, we design an efficient local search that focuses on the two objectives alternatively. The experimental results indicate that our algorithm outperforms multi-objective evolutionary algorithms and Gurobi, the former of which is commonly applied for multi-objective optimization and the latter of which is a well-known competitive commercial tool.
Supplemental Material
MP4 File - Bi-Objective Contract Allocation for Guaranteed Delivery Advertising
We can represent this problem using a bipartite graph: on the left-hand side are the inventory supply nodes, which are forecasted and inaccurate. On the right-hand side are the demand nodes with contracts. When new advertisers approaches the platform, they inquire about the maximum number of supply they can purchase. If the platform oversells its supply, it may face shortages during the online allocation stage, failing to fulfill contracts. Conversely, underselling the supply leads to wasted inventory resources. To address this problem, we developed a model with two objectives: maximizing selling revenue while minimizing the risk of inventory shortages during the online allocation stage. We designed a local search algorithm that focuses on the two objectives alternatively to get high quality solution.When you visit Alibaba?s website, you will see various advertisements. Advertisers sign contracts with the platform weeks before the target dates to secure the desired inventory in advance.
- Download
- 2.71 MB
References
[1]
Nader Al Theeb, Hazem J Smadi, Tarek H Al-Hawari, and Manar H Aljarrah. 2020. Optimization of vehicle routing with inventory allocation problems in Cold Supply Chain Logistics. Computers & Industrial Engineering, Vol. 142 (2020), 106341.
[2]
Vijay Bharadwaj, Peiji Chen, Wenjing Ma, Chandrashekhar Nagarajan, John Tomlin, Sergei Vassilvitskii, Erik Vee, and Jian Yang. 2012. Shale: an efficient algorithm for allocation of guaranteed display advertising. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data mining. 1195--1203.
[3]
Shaowei Cai. 2015. Balance between complexity and quality: Local search for minimum vertex cover in massive graphs. In Proceedings of the 24th International Joint Conference on Artificial Intelligence.
[4]
Bili Chen, Wenhua Zeng, Yangbin Lin, and Defu Zhang. 2014. A new local search-based multiobjective optimization algorithm. IEEE Transactions on Evolutionary Computation, Vol. 19, 1 (2014), 50--73.
[5]
Lingen Chen, Shuangshuang Shi, Yanlin Ge, and Huijun Feng. 2023. Ecological function performance analysis and multi-objective optimization for an endoreversible four-reservoir chemical pump. Energy, Vol. 282 (2023), 128717.
[6]
Peiji Chen, Wenjing Ma, Srinath Mandalapu, Chandrashekhar Nagarjan, Jayavel Shanmugasundaram, Sergei Vassilvitskii, Erik Vee, Manfai Yu, and Jason Zien. 2012. Ad serving using a compact allocation plan. In Proceedings of the 13th ACM Conference on Electronic Commerce. 319--336.
[7]
Xiao Cheng, Chuanren Liu, Liang Dai, Peng Zhang, Zhen Fang, and Zhonglin Zu. 2022. An Adaptive Unified Allocation Framework for Guaranteed Display Advertising. In Proceedings of the 15th ACM International Conference on Web Search and Data Mining. 132--140.
[8]
Sam Daulton, Maximilian Balandat, and Eytan Bakshy. 2023. Hypervolume knowledge gradient: a lookahead approach for multi-objective bayesian optimization with partial information. In International Conference on Machine Learning. PMLR, 7167--7204.
[9]
Kalyanmoy Deb. 2011. Multi-objective optimisation using evolutionary algorithms: an introduction. In Multi-objective Evolutionary Optimisation for Product Design and Manufacturing. Springer, 3--34.
[10]
Kalyanmoy Deb and Himanshu Jain. 2013. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Transactions on Evolutionary Computation, Vol. 18, 4 (2013), 577--601.
[11]
Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol. 6, 2 (2002), 182--197.
[12]
Matthias Ehrgott. 2005. Multicriteria optimization. Vol. 491. Springer Science & Business Media.
[13]
Zhen Fang, Yang Li, Chuanren Liu, Wenxiang Zhu, Yu Zheng, and Wenjun Zhou. 2019. Large-scale personalized delivery for guaranteed display advertising with real-time pacing. In IEEE International Conference on Data Mining. IEEE, 190--199.
[14]
Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and Shan Muthukrishnan. 2009. Online stochastic matching: Beating 1--1/e. In 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 117--126.
[15]
LLC Gurobi Optimization. 2022. Gurobi Optimizer Reference Manual (Gurobi Optimization, LLC). (2022).
[16]
Gregor Hendel. 2022. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation (2022), 1--37.
[17]
Ali Hojjat, John Turner, Suleyman Cetintas, and Jian Yang. 2014. Delivering guaranteed display ads under reach and frequency requirements. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, Vol. 28.
[18]
Ali Hojjat, John Turner, Suleyman Cetintas, and Jian Yang. 2017. A unified framework for the scheduling of guaranteed targeted display advertising under reach and frequency requirements. Operations Research, Vol. 65, 2 (2017), 289--313.
[19]
Yicun Hua, Qiqi Liu, Kuangrong Hao, and Yaochu Jin. 2021. A survey of evolutionary algorithms for multi-objective optimization problems with irregular Pareto fronts. IEEE/CAA Journal of Automatica Sinica, Vol. 8, 2 (2021), 303--318.
[20]
Andrzej Jaszkiewicz. 2002. Genetic local search for multi-objective combinatorial optimization. European Journal of Operational Research, Vol. 137, 1 (2002), 50--71.
[21]
Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online bipartite matching with unknown distributions. In Proceedings of the 43rd annual ACM Symposium on Theory of Computing. 587--596.
[22]
Borhan Kazimipour, Xiaodong Li, and A Kai Qin. 2014. A review of population initialization techniques for evolutionary algorithms. In IEEE Congress on Evolutionary Computation. IEEE, 2585--2592.
[23]
Abdullah Konak, David W Coit, and Alice E Smith. 2006. Multi-objective optimization using genetic algorithms: A tutorial. Reliability engineering & system safety, Vol. 91, 9 (2006), 992--1007.
[24]
Ke Li, Renzhi Chen, Guangtao Fu, and Xin Yao. 2018. Two-archive evolutionary algorithm for constrained multiobjective optimization. IEEE Transactions on Evolutionary Computation, Vol. 23, 2 (2018), 303--315.
[25]
Sedigheh Mahdavi, Mohammad Ebrahim Shiri, and Shahryar Rahnamayan. 2015. Metaheuristics in large-scale global continues optimization: A survey. Information Sciences, Vol. 295 (2015), 407--428.
[26]
Wuyang Mao, Chuanren Liu, Yundu Huang, Zhonglin Zu, M Harshvardhan, Liang Wang, and Bo Zheng. 2023. End-to-End Inventory Prediction and Contract Allocation for Guaranteed Delivery Advertising. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1677--1686.
[27]
Vahab S Mirrokni, Shayan Oveis Gharan, and Morteza Zadimoghaddam. 2012. Simultaneous approximations for adversarial and stochastic online budgeted allocation. In Proceedings of the 23rd annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1690--1701.
[28]
Hans Mittelmann. [n.,d.]. Visualizations of mittelmann benchmarks. https://mattmilten.github.io/mittelmann-plots/.
[29]
Indranil Mondal, Anushree Neogi, Prasanna Chaporkar, and Abhay Karandikar. 2017. Bipartite graph based proportional fair resource allocation for D2D communication. In IEEE Wireless Communications and Networking Conference. IEEE, 1--6.
[30]
Luis Paquete and Thomas Stützle. 2018. Stochastic local search algorithms for multiobjective combinatorial optimization: A review. Handbook of Approximation Algorithms and Metaheuristics (2018), 411--425.
[31]
Haitham Seada and Kalyanmoy Deb. 2015. A unified evolutionary optimization procedure for single, multiple, and many objectives. IEEE Transactions on Evolutionary Computation, Vol. 20, 3 (2015), 358--369.
[32]
Ye Tian, Tao Zhang, Jianhua Xiao, Xingyi Zhang, and Yaochu Jin. 2020. A coevolutionary framework for constrained multiobjective optimization problems. IEEE Transactions on Evolutionary Computation, Vol. 25, 1 (2020), 102--116.
[33]
Yulia Tseytlin and H Sebastian Heese. 2023. Inventory allocation with full downward substitution and monotone cost differences. European Journal of Operational Research, Vol. 307, 1 (2023), 130--139.
[34]
Laurence A Wolsey. 2020. Integer programming. John Wiley & Sons.
[35]
Hong Zhang, Lan Zhang, Lan Xu, Xiaoyang Ma, Zhengtao Wu, Cong Tang, Wei Xu, and Yiguo Yang. 2020. A request-level guaranteed delivery advertising planning: Forecasting and allocation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2980--2988.
Index Terms
- Bi-Objective Contract Allocation for Guaranteed Delivery Advertising
Index terms have been assigned to the content through auto-classification.
Recommendations
End-to-End Inventory Prediction and Contract Allocation for Guaranteed Delivery Advertising
KDD '23: Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data MiningGuaranteed Delivery (GD) advertising plays an essential part in e-commerce marketing, where the ad publisher signs contracts with advertisers in advance by promising delivery of advertising impressions to fulfill targeting requirements for advertisers. ...
Ad serving using a compact allocation plan
EC '12: Proceedings of the 13th ACM Conference on Electronic CommerceA large fraction of online display advertising is sold via guaranteed contracts: a publisher guarantees to the advertiser a certain number of user visits satisfying the targeting predicates of the contract. The publisher is then tasked with solving the ...
Fairness-aware Guaranteed Display Advertising Allocation under Traffic Cost Constraint
WWW '23: Proceedings of the ACM Web Conference 2023Real-time Bidding (RTB) and Guaranteed Display (GD) advertising are two primary ways to sell impressions for publishers in online display advertising. Although GD contract serves less efficiently compared to RTB ads, it helps advertisers reach numerous ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2024
6901 pages
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution-NonCommercial International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 24 August 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
August 25 - 29, 2024
Barcelona, Spain
Acceptance Rates
Overall Acceptance Rate 66 of 1,115 submissions, 6%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 215Total Downloads
- Downloads (Last 12 months)215
- Downloads (Last 6 weeks)75
Reflects downloads up to 16 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in