SHALE

在广告投放系统中，广告分为保量交付（GD，合约广告）与不保量交付（NGD，竞价广告）两种类型。GD广告需提前与特定人群签定合约，若投放量不足，系统将面临惩罚。因此，如何确保GD广告完成投放且最大化广告系统收益成为首要问题。同时，不同广告主追求不同的目标，有的侧重于触达目标人群的数量，有的则关注点击率与转化率，且支付方式多样，包括CPM、CPC、CPA等。问题随之而来：如何在满足不同广告主目标的同时，最大化广告系统收益？库存分配问题可通过二部图模型简化，流量与广告活动之间的连线表示分配关系。NGD广告按竞价方式售卖，目标是最大化系统收益，GD广告则侧重保量与效果。库存分配需兼顾NGD广告收益、GD广告保量与效果，以实现整体收益最大化。

HWM算法概述与实现

为解决库存分配问题，【2】提出了一种算法——HWM（High Water Mark Algorithm），旨在通过简化的方法解决流量分配问题。HWM的核心思想是首先考虑满足合约的所有流量，流量越少其重要性越高，然后将流量按照所需量平分，转换为概率。算法分为两部分：离线计算合约分配概率与分配顺序，以及在线部分实时计算用户的广告分配概率。看似复杂，实则基于简单贪心策略。

HWM算法流程

算法流程如下：
1. 计算各合约的用户流量值和分配概率。
2. 排序，优先分配流量较少的广告。
3. 按顺序计算各合约概率。
4. 预估流量对分配影响，通过调整分配概率优化算法性能。

SHALE算法及其优化目标

为了进一步优化分配问题，【3】提出SHALE算法，其目标函数考虑了广告需求、用户流量约束及非负约束。算法定义了理想分配比例与实际分配量之间的关系，通过拉格朗日对偶性将问题转换为对偶问题，利用KKT条件进行求解。SHALE算法优化目标在于使分配比例与理想比例接近，同时减少流量不足导致的惩罚。

SHALE算法流程与推导

SHALE算法采用坐标下降法求解，首先初始化所有参数，然后重复迭代，直至满足退出条件。输出每一合约的分配量与理想比例。在线分配时，根据合约输出的分配量与理想比例，进行流量分配，确保分配流量不超过约定上限。

总结与比较

HWM算法基于贪心策略实现简单快速的流量分配，但对流量预估敏感，未考虑后续合约流量占用及广告重要程度。SHALE算法通过优化目标函数，利用拉格朗日对偶性与KKT条件进行求解，实现了更精确的流量分配，但在实现复杂度上相比HWM更高。两者均在广告投放系统中发挥着关键作用，HWM适用于快速响应场景，而SHALE算法适用于追求更高收益与更精确分配的场景。在实际应用中，可依据广告主需求与系统资源选择合适的分配算法。