CPC模式下保量合同的在线展示广告投放策略优化

doi:10.16381/j.cnki.issn1003-207x.2021.2559

摘要/Abstract

摘要：

在线展示广告发展迅猛，按点击付费（cost per click，CPC）的保量合同是在线展示广告的一种重要合同形式。基于实际，在制定广告投放决策时曝光供应量通常是不确定的，其概率分布难以精确获知，仅知部分分布信息。本文利用分布鲁棒优化框架，构建寻求以已知信息为特征的不确定集，并在最坏情形下寻求最优广告投放策略。建立分布鲁棒机会约束模型并给出求解算法，进行了仿真分析。数值算例结果显示，设计的广告投放优化模型和相应的求解算法具有较好的表现。

关键词: 在线展示广告, 点击付费, 保量, 随机优化, 分布鲁棒

Abstract:

Online display advertising is developing rapidly， and the cost-per-click （CPC） contract is an important form of contract for online display advertising. Based on reality， the impression supply is usually uncertain when making advertising delivery decisions， and its probability distribution is difficult to accurately know， and only partial distribution information is known. Using the distributionally robust optimization framework， an uncertain set characterized by known information is constructed， and the optimal advertising strategy in the worst case. Then a distributionally robust chance-constrained formulation is established and a solution algorithm is given， and some numerical experiments are carried out. The results of the numerical experiments show that the designed advertising optimization model and the corresponding solution algorithm have good performance.

Key words: online display advertising, CPC, guaranteed delivery, stochastic optimization, distributionally robust

中图分类号:

O221.7

代文强,初维佳,钟婧. CPC模式下保量合同的在线展示广告投放策略优化[J]. 中国管理科学, 2024, 32(10): 256-264.

Wenqiang Dai,Weijia Chu,Jing Zhong. Online Display Advertising Optimization Based on Guaranteed Delivery Contract under CPC Model[J]. Chinese Journal of Management Science, 2024, 32(10): 256-264.

图/表 9

表1

参数γ1、γ2的影响"

变量	(0.1,0.2)	(0.1,0.4)	(0.1,0.6)	(0.1,0.8)	(0.1,1)
服务水平	0.985	1	1	0.897	1
风险水平	0	0.003	0	0	0.001
运行时间( $s$ )	241.35	240.76	193.87	330.87	211.50
	(0.2,0.4)	(0.2,0.6)	(0.2,0.8)	(0.2,1)	(0.3,0.4)
服务水平	1	1	1	1	1
风险水平	0.203	0.065	0.076	0.074	0.153
运行时间( $s$ )	262.63	230.98	286.49	210.64	215.62
	(0.3,0.6)	(0.3,0.8)	(0.3,1)	(0.4,0.6)	(0.4,0.8)
服务水平	1	1	0.977	1	1
风险水平	0	0	0	0	0
运行时间( $s$ )	293.15	395.80	225.13	211.49	206.94
	(0.4,1)	(0.5,0.6)	(0.5,0.8)	(0.6,0.8)	(0.7,0.8)
服务水平	1	1	1	1	1
风险水平	0	0	0	0.023	0.021
运行时间( $s$ )	271.82	208.36	220.71	302.52	230.64

表1

图1

表2

测试例子的输入数据"

参数	平均供给 $μ i$	预算 $d j$	保证点击量 $g j$	每点击价格 $b i j$	点击率 $C T R i j$
值	[1000,2000]	[2000,4000]	[500,700]	[1,3]	[0.05,0.3]

表2

表3

不同规模随机实例的影响"

序号	$m$	$n$	服务水平	风险水平	运行时间( $s$ )
1	3	3	1	0	89.27
2	5	3	1	0.001	160.04
3	5	5	0.998	0	182.54
4	7	5	1	0	254.53
5	7	7	0.995	0.002	665.53
6	9	7	1	0	1667.24

表3

表4

基于SAA/MISOCP下不同规模随机实例结果对比"

序号	$m$	$n$	求解方法	服务水平	风险水平	运行时间( $s$ )
1	3	3	SAA	1	0.027	60.89
1	3	3	MISOCP	1	0	89.27
2	5	5	SAA	0.994	0.032	389.51
2	5	5	MISOCP	0.998	0	182.54
3	7	7	SAA	0.989	0.018	1308.76
3	7	7	MISOCP	0.995	0.002	665.53
4	9	9	SAA	0.995	0.012	4898.20
4	9	9	MISOCP	1	0	3220.91

表4

表5

广告活动预算的影响"

预算 $d 1$	1600	1800	2000	2200	2600	3000	3400
服务水平	0.944	0.992	0.998	1	0.998	0.998	1
风险水平	0.262	0.108	0.026	0	0	0	0
预算 $d 2$	1600	1800	2000	2200	2600	3000	3400
服务水平	——	0.998	1	1	1	1	1
风险水平	——	0.082	0.038	0.024	0	0	0
预算 $d 3$	1600	1800	2000	2200	2600	3000	3400
服务水平	——	0.996	1	0.998	0.998	1	0.996
风险水平	——	0	0	0	0	0	0
预算 $d 4$	1600	1800	2000	2200	2600	3000	3400
服务水平	1	1	1	1	1	1	1
风险水平	0	0	0	0	0	0	0
预算 $d 5$	1600	1800	2000	2200	2600	3000	3400
服务水平	——	1	1	1	1	1	1
风险水平	——	0.048	0	0	0	0	0

表5

图2

表6

广告活动保证点击量的影响"

点击量 $g 1$	550	600	650	700	750	800
服务水平	1	1	0.988	0.981	0.974	0.910
风险水平	0	0	0	0.018	0.024	0.204
点击量 $g 2$	550	600	650	700	750	800
服务水平	1	1	0.902	——	——	——
风险水平	0	0	0	——	——	——
点击量 $g 3$	550	600	650	700	750	800
服务水平	1	1	0.984	——	——	——
风险水平	0	0	0	——	——	——
点击量 $g 4$	550	600	650	700	750	800
服务水平	1	——	——	——	——	——
风险水平	0	——	——	——	——	——
点击量 $g 5$	550	600	650	700	750	800
服务水平	1	1	1	0.964	0.944	0.940
风险水平	0	0	0.002	0.014	0.020	0.105

表6

图3

参考文献 27

1	Shen Y.Pricing contracts and planning stochastic resources in brand display advertising［J］.Omega，2018，81： 183-194.
2	Salomatin K， Liu T Y， Yang Y. A unified optimization framework for auction and guaranteed delivery in online advertising［C］// Proceedings of the 21st ACM International Conference on Information and Knowledge Management，Hawaii USA， Oct29-Novo2，Association for Computing Machinery， 2012： 2005-2009.
3	Bruner R E. The decade in online advertising 1994-2004［R］.Double Click White Paper，Double Chick，2005.
4	Taylor A. Size， quantity and management capabilities： How Google updates AdWords to increase revenue［J］. Journal of Digital Social Media Marketing， 2017， 5（1）： 18-27.
5	Fjell K. Online advertising： Pay-per-view versus pay-per-click — A comment［J］. Journal of Revenue and Pricing Management， 2009， 8（2）： 200-206.
6	Najafi-Asadolahi S， Fridgeirsdottir K. Cost-per-click pricing for display advertising［J］. Manufacturing & Service Operations Management，2014，16（4）： 482-497.
7	Choi H， Mela C F， Balseiro S R， et al. Online display advertising markets： A literature review and future directions［J］. Information Systems Research， 2020， 31（2）： 556-575.
8	Turner J. The planning of guaranteed targeted display advertising［J］. Operations research， 2012， 60（1）： 18-33.
9	Tomlin J A. An entropy approach to unintrusive targeted advertising on the Web［J］. Computer Networks， 2000， 33（1-6）： 767-774.
10	张梦玲，王晶，黄钧.不确定需求下考虑供应商参与机制的应急资源配置鲁棒优化研究［J］.中国管理科学，2020，28（7）：102-111.
	Zhang M L， Wang J， Huang J.Research on robust optimization of emergency resource allocation based on supplier participation mechanism under uncertain demand［J］.Chinese Journal of Management Science，2020，28（7）：102-111.
11	邱若臻，初晓晶，孙月.价格和交货期敏感需求下基于鲁棒优化的双渠道供应链决策模型［J］.中国管理科学，2023，31（9）：114-126.
	Qiu R Z， Chu X J， Sun Y.Dual-channel supply chain decision model based on robust optimizationunder price and delivery-time dependent demand［J］.Chinese Journal of Management Science， 2023，31（9）：114-126.
12	Yao F， Dong Z Y， Meng K， et al. Quantum-inspired particle swarm optimization for power system operations considering wind power uncertainty and carbon tax in Australia［J］. IEEE Transactions on Industrial Informatics， 2012， 8（4）： 880-888.
13	Peng C， Sun H， Guo J， et al. Dynamic economic dispatch for wind-thermal power system using a novel bi-population chaotic differential evolution algorithm［J］. International Journal of Electrical Power & Energy Systems， 2012， 42（1）： 119-126.
14	Ghaoui L E， Oks M， Oustry F. Worst-case value-at-risk and robust portfolio optimization： A conic programming approach［J］. Operations research， 2003， 51（4）： 543-556.
15	Calafiore G C， Ghaoui L E. On distributionally robust chance-constrained linear programs［J］. Journal of Optimization Theory and Applications， 2006， 130（1）： 1-22.
16	Delage E， Ye Y. Distributionally robust optimization under moment uncertainty with application to data-driven problems［J］. Operations Research， 2010， 58（3）： 595-612.
17	Cheng J， Lisser A， Letournel M. Distributionally robust stochastic shortest path problem［J］. Electronic Notes in Discrete Mathematics， 2013， 41： 511-518.
18	Zhang Y， Shen S， Erdogan S A. Solving 0-1 semidefinite programs for distributionally robust allocation of surgery blocks［J］. Optimization Letters， 2018， 12（7）： 1503-1521.
19	杨洪明，刘俊鹏，梁芮，等.考虑动态功率调节裕度的高比例风电系统水-火-荷分布鲁棒优化调度［J］.系统工程理论与实践， 2021， 41（9）： 2327-2337.
	Yang H M， Liu J P， Liang R， et al.Distributionally robust optimal dispatching of hydrothermal-load resources for high penetration of wind system with dynamic power regulation margin［J］.Systems Engineering -Theory & Practice，2021，41（9）：2327-2337.
20	Liu M， Liu X， Chu F， et al. Distributionally robust inventory routing problem to maximize the service level under limited budget［J］. Transportation Research Part E： Logistics and Transportation Review， 2019， 126： 190-211.
21	Richardson M， Dominowska E， Ragno R. Predicting clicks： Estimating the click-through rate for new ads［C］//Proceedings of the 16th International Conference on World Wide Web， Alberta Canada， May 8-12 ， Association for Computing Machinery，2007： 521-530.
22	Zhu Z A， Chen W， Minka T， et al. A novel clickmodel and its applications to online advertising［C］//Proceedings of the Third ACM International Conference on Web Search and Data Mining， New York， USA， February 4-6 ， Association for Computing Machinery， 2010： 321-330.
23	Sun H， Gao Z， Szeto W Y， et al. A distributionally robust joint chance constrained optimization model for the dynamic network design problem under demand uncertainty［J］. Networks and Spatial Economics， 2014， 14（3）： 409-433.
24	Do Chung B， Yao T， Zhang B. Dynamic traffic assignment under uncertainty： A distributional robust chance-constrained approach［J］. Networks and Spatial Economics， 2012， 12（1）： 167-181.
25	Zymler S， Kuhn D， Rustem B. Distributionally robust joint chance constraints with second-order moment information［J］. Mathematical Programming， 2013， 137（1）： 167-198.
26	Kayacık S E， Kocuk B. An MISOCP-based solution approach to the reactive optimal power flow problem［J］. IEEE Transactions on Power Systems， 2020， 36（1）： 529-532.
27	Zhang Y， Jiang R， Shen S. Ambiguous chance-constrained binary programs under mean-covariance information［J］. SIAM Journal on Optimization， 2018， 28（4）： 2922-2944.