双11技术分享 | “喵糖”背后的商业化流量投放算法

▐ 前言

品牌合约保量广告被广泛应用于电商营销中，为广告主提供合同约定的目标人群触达次数。服务于品牌合约广告的投放分配算法，需要对每个请求分配、展示广告，以完成合约订单的展示量要求。在传统的 APP 开屏品牌合约保量场景下，我们先后设计研发了XSHALE算法[1]和AUAF算法[2]，兼顾展示量及投放效果，取得了显著的业务效果，并总结为有资源约束下的最优化投放分配解决方案。针对双十一互动城的特殊业务需求，我们形式化投放目标，基于泛化的投放分配问题建模模板，快速开发上线了服务于双11互动城的保量下线订单原始对偶算法、与保量不下线订单溢出流量均衡重排算法。

▐ 背景

每年双十一互动游戏都会吸引大量用户关注和参与，这部分流量会以保量合约广告的形式，打包为多级别的套餐包售卖给广告主，在活动期间为广告主带来确定性的曝光和进店流量，助力广告主完成双十一的“大卖”。2021年的双十一互动玩法是“赚喵糖、占地盘、抢红包”的模式，这个场景提供了多样的商业化资源位(如下图所示)。这些资源位带来的商业化流量，需按照合约承诺，分配给各个广告主，满足业务诉求。除此之外，我们需要在业务约束内，尽可能地提升广告主的投放效果，以提高平台价值与竞争力，赢得更多长期合作。

超级互动双11业务图

根据业务规则，双十一互动城的广告位均由招商广告主填充，以保量合约的形式售卖，订单类型大体分为精准保量下线广告和泛精准保量不下线广告：

• 精准保量下线广告，定向客户的精准人群进行投放，到量后不再继续投放；
• 泛精准保量不下线广告，定向所有人群，但优先展现到精准人群，订单到量也继续投放，根据业务规则平衡订单间对于溢出流量的竞得；

除了共同的保量要求，两种广告的业务诉求也有不小的差异：精准保量下线广告的诉求有时间平滑、提效等；而泛精准保量不下线广告的诉求则为尽量精准、订单间进度近似、不同级别的商家控制不同溢出比例等。

▐ 技术方案与实现

方案选择出发点

目前主流的流量调控策略框架，主要分为两类：

• 离线训练分配模型，根据模型参数在线实时计算分配概率 + 近线pacing调控进行流量优选；

• 近线调整对偶参数，根据参数实时计算竞价。

承接互动合约业务之前，团队在 APP 开屏合约投放分配场景，有大量的技术积累，形成了离线最优化分配求解 + 近线pacing调控相结合的成熟技术方案[2]。之所以在 APP 开屏品牌投放场景选用这套投放分配方案，原因有以下几点：

• APP开屏订单售卖率高，缺量订单多，独立调控容易参数“内卷”，采用这套方案，在大促保量压力较大时可临时下线pacing模块，只保留离线训练的分配模型，以最大程度保量；
• APP开屏存在一些预定量极小调控难度较大的长尾订单，离线分配模型可以利用较长时间的日志，分配结果更稳定。

另外，离线模型+近线pacing调控也存在一些劣势：

• 链路相对复杂，开发成本略高，时效性不如第二种方法；
• 实际最优分配存在gap，提效能力偏弱。

大促互动场景流量充足，缺量风险很低，不用考虑下线pacing，且套餐包金额较大，每个订单均有置信的投放数据做反馈。基于以上原因，我们在大促互动场景均采用近线调整对偶计算公式的方法，可以带来更优的投放效果。针对“保量下线合约”和“保量不下线合约”不同的广告特点，我们采用了不同算法方案进行广告投放与流量分配。

保量下线合约的优选提效算法

对于精准保量下线订单，由于投放前经过了询锁量步骤，缺量风险较小，因此可以在保量的前提下，通过流量的pacing优选来最大化订单的投放效果。这种属于经典的品牌合约投放形式，有较多的经验积累，我们结合互动场注重后链路效果的业务特点，基于PrimalDual算法[3]，使用brandScore（品牌价值分）来优化投放效果。

最大化后链效果的投放公式推导

在无缺量风险的背景下，我们投放的最优化目标函数为最大化预估品牌价值分效果：

对偶问题为：

对一次请求i，召回m个订单，对偶问题的约束为：

根据松弛条件，以排序，若最高，则本次请求以相对影子价格的最高溢价广告填充；若所有广告的，则本次流量抛弃。因此线上的投放“价格”计算公式为：

同时“保留价”为0

对偶变量的近线调控

经典的近线对偶调控算法是基于线上订单的超投、缺量反馈，调整对偶变量α。但“喵糖”互动城比较特殊，“冷启即实战”，流量趋势难以拟合，波动极大，且直接受游戏规则影响。我们与主互动和业务同学密切配合，基于互动的玩法设计来预估流量趋势，极大平滑了品牌合约单的释放。

保量不下线合约的在线分配算法

保量不下线合约订单是互动城大促特有的一种广告售卖形式，订单的释放完全由业务规则约束下的算法控制，由于没有结算、召回控制等策略兜底，业务目标对算法的精度和实时性提出了更高的要求。相比于传统合约的保量下线，保量不下线订单会将互动城全部流量包断，并根据订单级别和运营诉求分配给广告主，根据售卖价格分为多层，越贵的套餐包，覆盖资源位更多、展现机会更多、业务溢出率更高。在此基础上，还需要根据广告主要求在不同的日期进行爆发期，以配合商家营销节奏。综合运营诉求及效果目标，我们设计了“保量及均衡约束下的效果最大化”投放算法，基于投放目标推导对偶投放公式用于线上流量分配，并在近线基于当前投放进度和业务设定目标溢出比例调整对偶变量。

保量一致性对偶投放公式推导

基于业务目标的最优化目标公式如下：

其中：

• 表示流量节点 的供给量
• 表示第 个订单的预订量
• 表示第 个流量节点对第 个订单的分配概率
• 表示实时的品牌价值预估分
• 表示节点 可以召回订单
• 表示订单 的初始均匀分配比例，

目标函数第一项是二次正则项，虽然可能使分配结果不一定是最优解，但是通过设置合理超参数，正则项的值比真正优化的目标项小一到两个数量级，所以对解的影响并不会很大，正则项的主要作用还有以下几点：

• 使得目标函数变成一个强凸函数，最优解具有唯一性
• 可以让订单在保量前提下，让流量尽量均匀分配，分配的结果更鲁棒
• 根据拉格朗日乘子法和KKT条件，加入正则项之后，可以通过约束的对偶变量推导出 ，这样求解的模型不用直接保存分配概率，而是保存对偶变量，从而具有紧凑解的优势

上面的目标函数用 表示，采用拉格朗日乘子法可以表示为：

目标取得最优解时，需要满足KKT条件：

由第一个条件推导：

当上式 时， 可以逐步增大直到 并且不能再增大，否则会破坏KKT条件；当 时，根据第KKT条件，必定有 ，所以的对偶形式可以写成下面样式，记为 函数：

假设我们通过离线大规模分配模型或者启发式方法，已经求解并保存了各个广告订单的对偶变量 。当一个流量请求过来时，得到召回的广告以及每个对应的对偶变量 ，可以通过二分法等实时求解以下方程得到，从而最终得到 。

近线策略 && 目标释放速度求解

在互动保量不下线的场景中，我们基于近线分钟级调度，采用线性插值方法，根据线上实时结算反馈调整每个订单对应的对偶变量α。由于订单释放量可以溢出，大于其预定量，但需保证各订单间的溢出率相似。除此之外，不同套餐包的优先等级不同，优先级从高到低的溢出率需要呈阶梯递减的形态。我们需要实时地调整 我们假设调控的时间为，当日（即广告计划j）已释放量为,原始天预定量为,所对应套餐包理想业务溢出率为。此外，为了调控速率，我们需要预估出campaign每天实际可释放量【由于是保量不下线场景，该值不等于】。每个都可以根据昨日其对应pid请求数分布得到其释放曲线,即可知当天0时至t时的预估释放量当天占比。首先，我们需要预估出当天所有campaign总释放量:

然后，根据其理想业务溢出率重新加权分配得到:

最后我们可知求得当天还需释放量。根据以及时间t，我们即可预估出下个时间切片所需的目标释放速度，然后根据历史对偶值和历史释放速度利用线性插值算法，求解出下一个时间切片的对偶值。

▐ 总结&规划

今年双十一，我们基于“喵糖”互动商业化的业务特点，为“保量下线合约”和“保量不下线合约”两种合约广告类型，分别设计了提效更佳的brandScore原始对偶投放算法，和保量及均衡约束下的效果最大化投放算法，成功地达成业务放量预期，并在保量基础上提升了投放的后链路效果：

• 针对“保量下线合约”订单的品牌价值提效实验，相比无调控基线，实验桶深度互动率、店铺二次访问率及店铺内平均浏览时长均有所提升；
• 针对“保量不下线合约”订单，业务进度均衡误差减少，提效实验桶相比基线，深度互动率、店铺二次访问率及店铺内平均浏览时长均大幅提升。

同时，我们更多地关注业务侧的放量需求，及品牌粒度的后链路效果，并以此为目标设计了投放算法，得到不错的结果。后面我们将在精准投放提效和业务定制两个方向进一步优化算法：

• 深入挖掘精准合约的细分人群价值，开发序列化投放算法促进人群流转；
• 面向泛精准合约的复杂业务诉求，开发投放需求定制接口，针对业务特殊诉求，基于难度和复杂度，自动完成定价和投放策略配置。

注释及参考文献

1. Fang Z, Li Y, Liu C, et al. Large-Scale Personalized Delivery for Guaranteed Display Advertising with Real-Time Pacing[C]//2019 IEEE International Conference on Data Mining (ICDM). IEEE, 2019: 190-199.
2. An Adaptive Unified Allocation Framework for Guaranteed Display Advertising, accepted by WSDM2022
3. Chen Y, Berkhin P, Anderson B, et al. Real-time bidding algorithms for performance-based display ad allocation[C]//Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 2011: 1307-1315.

END

欢迎关注「阿里妈妈技术」，了解更多~

疯狂暗示↓↓↓↓↓↓↓