10亿计算下的合约广告，如何做个性化投放？

一、导言

合约保量广告（Guaranteed Delivery）是一种常见的品牌展示广告采买方式，现有的技术解决方案通常是在人群粒度上对问题进行抽象和建模，这种建模方式一方面忽略了相同人群下用户行为的差异，另一方面无法对用户粒度的约束进行精确的控制。

目前学术界关于合约广告流量分配问题的研究，通常会将这个问题抽象为合约侧-供给侧的二部图匹配问题，但目前的分配策略是停留在人群和标签粒度上，这要求人群和标签的划分必须是正交化的；除此之外，在人群层次上进行合约保量分配也还有不少局限性。

首先，由于只在人群层面进行分配，无法通过精准的用户行为预测将用户的个性化行为匹配至正确的广告，会降低广告主的投资回报率，进一步的降低广告平台的未来收入。其次，广告主通常会提出复杂的投放控制要求，比如在用户粒度的频次控制约束，一个典型的做法是，为了能够提高固定预算下的uv触达，广告主往往会限制单个uv的曝光频次。因此，传统的人群标签粒度分配的低效性使得其很难适用于目前的合约广告投放产品。

在本文中，我们尝试建立一个大规模分布式的合约广告投放分配算法，并在其中引入用户个性化的投放指标，在考虑用户交互行为的基础上，在用户粒度进行合约广告的投放分配工作。我们的算法可以处理复杂的约束，例如广告优先级，广告的展示频控以及广告贴位容量限制等。在这个基础上，我们还开发了实时预算平滑策略，通过预算平滑控制进一步优化广告的投放效果（如单位点击成本CPC）。目前我们的系统在阿里妈妈品牌展示广告实际承载了十亿规模的离线计算任务并在线应用，我们也将在最后给出离线和在线的实验结果来验证方案的的准确性。

二、问题定义

针对合约广告的分配问题，我们很自然的可以想到用一个二部图结构来描述这个匹配方式，传统的业界做法通常基于定向人群的维度进行分配。如下图(a)所示，用

表示定向人群i上的流量，用