两阶段定向展示广告保量鲁棒投放问题

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

摘要/Abstract

摘要：

具有不确定性的曝光供应量给广告资源的合理分配带来了极大挑战。针对这种不确定性，本文提出了两阶段定向展示广告保量投放分配模型。第一阶段，发布商做出分配策略，最优化分配的公平性；第二阶段，在随机曝光供应量实现以后，对未满足需求或超出需求的分配部分进行惩罚并计算实际收益。考虑到现实中曝光供应量极易受到社会热点等因素的影响，其精确分布难以获知，但发布商可获知分布的部分信息，因此，利用分布鲁棒方法，本文构建了两阶段分布鲁棒模型，进一步设计出割平面算法进行求解，进行了仿真分析，在大规模样本外测试中，通过与抽样平均近似（sample average approximation， SAA）方法进行对比，验证了模型和求解算法的可行性、鲁棒性以及有效性，同时给出了管理学启示。

关键词: 定向展示广告, 保量投放, 两阶段, 分布鲁棒优化

Abstract:

As technology advances and the economy experiences rapid growth， the internet advertising has witnessed an unprecedented boom. Guaranteed display advertising plays a significant role in internet advertising. A successful display ad must not only offer a wide range of presentation styles but should also aim for widespread exposure. However， guaranteed delivery strategy is influenced by various factors， with the greatest challenge being the uncertainty in the online behavior of internet users. In this context， the study of guaranteed display ad delivery strategy that considers uncertainty holds practical significance. Additionally， strategy is typically determined before the arrival of internet users and advertising placements， and the effectiveness of strategy can be validated through the recourse of performance. Therefore， adopting a two-stage model to address guaranteed display ad delivery issues provides more valuable guidance. In the realm of display advertising， the publisher owns advertising platforms， where advertisers represent products. When users browse the publisher's website， impressions （random variable） are generated， with each impression corresponding to an opportunity for a user to view an ad on the webpage. As users browse web pages， the publisher can categorize them into different segments based on characteristics. Once the publisher identifies the specific target segments of advertisers， ads on ad slots can be automatically loaded and displayed to users with different characteristics. Regarding guaranteed delivery， the publisher signs contracts with advertisers in which advertisers require demands， target segments and specific period. The contract also specifies penalties for shortage and excess of demand. Based on this， a two-stage distributionally robust model is formulated from the perspective of the publisher with the objective of maximizing overall revenue， in which the mean and variance of impression supply as the only known distribution information. The objective function consists of two parts： the fairness of allocation in the first stage and the publisher's expected revenue in the second stage. To better solve the proposed model， a cutting-plane algorithm is designed. Experimental results compared with the benchmark model（Sample Average Approximation - SAA） demonstrates the delivery strategy based on the method proposed in this paper effectively mitigates the interference caused by uncertainty and exhibits robustness. At the same time， some management insights are provided for the publisher.

Key words: targeted display advertising, guaranteed delivery, two-stage, distributionally robust optimization

中图分类号:

O221.7

隋鑫,代文强,王子绮. 两阶段定向展示广告保量鲁棒投放问题[J]. 中国管理科学, 2026, 34(9): 133-141.

Xin Sui,Wenqiang Dai,Ziqi Wang. Two-stage Robust Guaranteed Delivery in Targeted Display Advertising[J]. Chinese Journal of Management Science, 2026, 34(9): 133-141.

图/表 6

表1

割平面算法"

割平面算法：

输入：问题参数 $μ, σ 2, [q n - 1, q n), p n, c P, c f, [l j, u j]$

ITER=1000(迭代次数)

$τ = 0$ （迭代计数）

While $τ$ ≤ITER:

求解主问题MP

if $τ ≥ 1$ :

添加约束： $α ≤ θ (l - 1) - ∑ i ∈ I ξ i (l - 1) ⋅ w i - ∑ i ∈ I ξ i (l - 1) 2 ⋅ v i, l = 1,2, …, τ$

得到 $x (τ), α (τ), w (τ), v (τ)$

利用 $x (τ), α (τ), w (τ), v (τ)$ ,求解子问题SP,得到 $θ (τ), y + (τ), y - (τ), t (τ), z (τ), g (τ), ξ (τ), O b j S P (τ)$

if $α (τ) > O b j S P (τ)$ :

$τ = τ + 1$

else:

输出 $τ, x$

break

end

表1

表2

不同分布下［DRCC］模型与［SAA］模型样本外测试表现"

测试算例	问题规模			正态分布				两点分布				均匀分布
	$\| I \|, \| J \|, \| N \|$			[DRCC]		[SAA]		[DRCC]		[SAA]		[DRCC]		[SAA]
	$\| I \|$	$\| J \|$	$\| N \|$	EL	SL	EL	SL	EL	SL	EL	SL	EL	SL	EL	SL
1	3	2	2	0.5000	0.5000	0.2365	0.5000	0.5000	0.5000	0.1145	0.5000	0.5000	0.5000	0.3195	0.5000
2			3	0.5000	0.5000	0	0.5010	0.5000	0.5000	0	0.6235	0.5000	0.5000	0	0.5010
3			4	0.5000	0.5000	0.1655	0.5000	0.5000	0.5000	0.4225	0.5000	0.5000	0.5000	0.2650	0.5000
4	5	3	2	0.2313	0.6667	0.3287	0.6667	0.2270	0.6667	0.3263	0.6667	0.2486	0.6667	0.3287	0.6667
5			3	0.0010	0.3333	—	—	0.3313	0.4986	—	—	0	0.3426	—	—
6			4	0.3323	0.6667	—	—	0.2213	0.6667	—	—	0.3309	0.6667	—	—
7	7	4	2	0	0.5000	0.2118	0.5000	0.1220	0.5730	0.3558	0.5205	0	0.5000	0.2322	0.5000
8			3	0.0005	0.9402	—	—	0.2237	0.5120	—	—	0	0.9667	—	—
9			4	0.2267	0.7000	—	—	0.1300	0.7557	—	—	0.2400	0.7500	—	—
10	9	5	2	0	1	0.2698	0.0080	0	0.9571	0.5456	0.0596	0	1	0.2690	0.0122
11			3	0	1	—	—	0.0066	0.7145	—	—	0	0.9073	—	—
12			4	0	1	—	—	0	0.9577	—	—	0	1	—	—

表2

表3

表4

cf取值对［DRCC］模型公平性的影响"

$c f / c P$	公平性	$c f / c P$	公平性
10	4.01E-23	60	9.29E-25
20	6.86E-24	70	8.21E-25
30	2.43E-24	80	8.89E-25
40	2.44E-24	90	7.75E-31
50	1.20E-24	100	8.04E-31

表4

图1

图2

参考文献 25

[1]	Sayedi A. Real-time bidding in online display advertising［J］. Marketing Science， 2018， 37（4）： 553-568.
[2]	Sang Q， Kant R， Karlsson N. Feedback control of in-target rate for probabilistic frequency cap in online advertising［C］//Proceedings of the 2022 American Control Conference （ACC）， Atlanta， GA， USA，June 8-10， IEEE， 2022： 5354-5359.
[3]	Fang Z， Li Y， Liu C， et al. Large-scale personalized delivery for guaranteed display advertising with real-time pacing［C］//Proceedings of the 2019 IEEE International Conference on Data Mining （ICDM） 2019， Beijing， China， November 8-11， IEEE， 2019： 190-199.
[4]	Zhang H， Zhang L， Xu L， et al. A request-level guaranteed delivery advertising planning： Forecasting and allocation［C］//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，CA， USA， July 6-10， ACM， 2020： 2980-2988.
[5]	Bharadwaj V， Chen P， Ma W， et al. SHALE： An efficient algorithm for allocation of guaranteed display advertising［C］//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，Beijing， China， August 12-16， ACM， 2012： 1195-1203.
[6]	Yang J， Vee E， Vassilvitskii S， et al. Inventory allocation for online graphical display advertising using multi-objective optimization［J］.ICORES，2012， 12： 293-304.
[7]	Hojjat A， Turner J， Cetintas S， et al. A unified framework for the scheduling of guaranteed targeted display advertising under reach and frequency requirements［J］. Operations Research， 2017， 65（2）： 289-313.
[8]	Lejeune M A， Turner J. Planning online advertising using gini indices［J］. Operations Research， 2019， 67（5）： 1222-1245.
[9]	Delage E， Ye Y. Distributionally robust optimization under moment uncertainty with application to data-driven problems［J］. Operations Research， 2010， 58（3）： 595-612.
[10]	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.
[11]	Xie W. On distributionally robust chance constrained programs with Wasserstein distance［J］. Mathematical Programming， 2021， 186（1-2）： 115-155.
[12]	Postek K， Ben-Tal A， den Hertog D， et al. Robust optimization with ambiguous stochastic constraints under mean and dispersion information［J］. Operations Research， 2018， 66（3）： 814-833.
[13]	Ghosal S， Wiesemann W. The distributionally robust chance-constrained vehicle routing problem［J］. Operations Research， 2020， 68（3）： 716-732.
[14]	Shen Y. Pricing contracts and planning stochastic resources in brand display advertising［J］. Omega， 2018， 81： 183-194.
[15]	Celis E， Mehrotra A， Vishnoi N. Toward controllingdiscrimination in online ad auctions［C］//Preceedings of the International Conference on Machine Learning，Long Beach，California， USA， June 9-15， 2019：4456-4465
[16]	Gelauff L， Goel A， Munagala K，et al. Advertising for demographically fair outcomes［EB/OL］.（2020-06-06）［2026-08-05］.
[17]	McAfee R P， Papineni K， Vassilvitskii S. Maximally representative allocations for guaranteed delivery advertising campaigns［J］. Review of Economic Design， 2013， 17（2）： 83-94.
[18]	Ghosh A， McAfee P， Papineni K， et al. Bidding for representative allocations for display advertising［M］//Leonardi S.Internet and Network Economics. Berlin， Heidelberg：Springer，2009： 208-219.
[19]	Deza A， Huang K， Metel M R. Chance constrained optimization for targeted Internet advertising［J］. Omega， 2015， 53： 90-96.
[20]	Sherali H D， Tuncbilek C H. A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization Technique［J］. Journal of Global Optimization， 1992， 2（1）： 101-112.
[21]	Bertsimas D， Popescu I. Optimal inequalities in probability theory： A convex optimization approach［J］. SIAM Journal on Optimization， 2005， 15（3）： 780-804.
[22]	Nakao H， Shen S， Chen Z. Network design in scarce data environment using moment-based distributionally robust optimization［J］. Computers & Operations Research， 2017， 88： 44-57.
[23]	Zhang Y， Dong J. Building load control using distributionally robust chance-constrained programs with right-hand side uncertainty and the risk-adjustable variants［J］. INFORMS Journal on Computing， 2022， 34（3）： 1531-1547.
[24]	Wang Y， Sun B. Multiperiod optimal emergency material allocation considering road network damage and risk under uncertain conditions［J］. Operational Research， 2022， 22（3）： 2173-2208.
[25]	代文强，李丹阳. 考虑不确定协变量下的在线广告鲁棒分配策略［J］.中国管理科学，2025，33（8）： 230-237.
	Dai W Q， Li D Y. Robust guaranteed delivery and allocation optimization for online display advertising with covariate-based information［J］. Chinese Journal of Management Science， 2025， 33（8）： 230-237.