上传到博客上公式没法看了，感兴趣的同学到我的github博客上去看吧 http://tongming.github.io

转载请注明来源

简介

合约广告是一种基于合约的广告模式，在线广告中的一种主流方式是担保式投放（Guaranteed Delivery，GD）。GD是一种量优于质的广告投放方式，需要保证广告主能够获得在合约中约定的受众用户的流量。GD中，媒体的流量按照属性划分，媒体要给不同的广告主按照合同分配约定好的流量。Ad Server的准则是希望在每一次展现满足多个合约时，选择合适的广告主，以使得每个广告主效果最好，同时能够更有效的分配流量。如下图所示，supply为媒体方，提供流量，媒体的流量可以按照性别、年龄、地域划分；demand为广告主，不同的广告主需要不同细分的流量（或者说流量背后的用户），比如第一个广告主需要200K的男性流量。流量分配问题就是把不同细分的流量分配给不同的广告主，尽可能满足所有广告主的需求。比如下图中的问题，怎样把六部分流量分配给三个广告主才能满足所有广告合约的需求了？我们可以先分配CA的流量都给第二个广告主，然后就比较容易分配流量给另外两个广告主了。

对于上述问题的求解，已经有较多的工作展开，并且有一些不错的方法。为了理解不同方法的优点与弱点，需要先了解两个基本概念。第一个概念是流量到达顺序（input order），由于在实际广告分配中，我们不知道流量按照什么顺序达到，也不清楚会有哪些流量到达。显而易见的是，不同流量到达顺序对算法最终效果有很强的影响。为了更加客观的衡量不同算法的效果，需要比较在相同的流量到达顺序时，不同算法的效果。一般来讲对于流量到达顺序的模型有四种：

一、流量以最坏情况的顺序到达。这种流量到达模型假设有一个对手已经知道你的流量分配算法，并且对手可以操纵流量到达的顺序，从而产生一个使得你的流量分配算法效果最差的流量到达序列。

二、流量以随机的顺序到达。

三、流量以未知的独立同分布（IID）方式到达。

四、流量以已知的独立同分布（IID）方式到达。

第二个概念是竞争率（Competitive Ratio），竞争率是衡量算法效果的指标。竞争率的定义是算法得到的目标值与最优分配算法得到的目标值的比值。如果流量是以IID方式到达，则为目标值期望的比值。有了流量到达顺序以及竞争率的概念，就可以分析不同算法的优劣。下面我们由简单到复杂考察一些已有算法的特性。

贪心分配算法

第一个考察的算法是贪心分配算法，贪心分配算法运行方式如下：

每一次请求，找到能够匹配的广告中，出价最高的广告投放。

现在需要考虑的是贪心分配算法最终效果如何，可以证明在流量输入顺序为最坏情况时，贪心算法的竞争率为0.5，并且只能到达0.5。这里对结果不加以证明，举一个例子说明贪心算法的竞争率最多为0.5。

如上图，黑点代表一个流量，流量到达顺序由上而下，两个广告主需要的流量单元都为1，对流量的出价分别是1与M。当M大于1时，贪心算法的分配方案使得媒体最终收入是M，而最优分配方案媒体的收入为1+M，因此在这种顺序下，贪心分配算法的竞争率为。因此当M无限接近1时，贪心分配算法的竞争率无限接近为0.5，而当M远大于1，贪心分配算法的竞争率接近1，分配效率接近最优分配算法。因此贪心分配算法在广告主出价差异大的时候，是一种比较好的分配算法。

上面考察的是流量到达序列的顺序在最差情况下，贪心分配算法的竞争率。在真实环境中，流量到达顺序一般不会是最差情况。因此考察流量到达序列为IID分布时，贪心分配算法的竞争率更符合真实应用场景。Goel等在他们的论文（Online budgeted matching in random input models with applications to adwords）中证明了在输入序列为随机情况下，贪心算法对Adwords问题的竞争率为。需要注意的是Adwords问题与GD流量分配问题并不等价，很多问题的结论并非一致，因此对与流量分配问题，在输入序列为随机时，贪心算法的竞争率依然没有明确的答案，感兴趣的同学可以仿照Goel的思路，看是否能得到相同的结论。下面一种出价缩放算法中，Adwords问题与展示广告的流量分配问题的结论也非常不一样，展示广告的流量分配算法相对于Adwords问题要更加困难。

另外一种和贪心算法同样简单的算法是随机算法。随机算法对每一次广告请求，从满足要求的合约广告中随机选择一个展现。大家可以思考一下，对于随机算法，在不同流量到达模型时，竞争率分别是多少。在何种输入情况下，随机算法表现比贪心算法的表现要好。

出价缩放算法（bid scaling）

下面需要考察的是一种更加一般的算法，可以把这种算法称为出价缩放算法。出价缩放算法顾名思义就是每一次广告请求，对每一个符合要求的广告的出价乘以/减去一个缩放因子（对于Adwords问题是乘以一个因子，对于Display Ad是减去一个因子），选择值最大的广告投放。为了理解bid scaling算法，需要对问题进行数学的形式化描述：

如上公式，左边为原问题，右边为对偶问题。其中为流量V分配给广告主U的量（值为1或0），为广告主U对流量V的出价，为广告主U一共需要的流量。现在的问题是流量V未知，我们需要在线求解上述问题。由KKT条件，可知上述问题的最优解需要满足如下条件：

由上述KKT条件可以知道，当流量v分配给最大的广告主时，可以得到最优解。因此，bid scaling的算法如下：

对每一个广告请求，对于满足要求的广告主计算，将流量分配给值最大的广告主。（对于Adwords问题，此时计算的是）

Bid scaling算法的核心是怎么选择。贪心算法也可以看作是一种bid scaling算法，该算法选择当广告主预算未消耗完时，当预算消耗完后为。

J. Feldman等在文章Online ad assignment with free disposal中提出了一种选择的方式，这种方式在最坏情况下，并满足广告主预算较大的条件时，竞争率为，他们的选择方式如下：

SHALE算法

之前考察的算法都没有考虑流量到达的分布。在现实环境中，我们对流量具有一定的预测能力，SHALE算法试图通过预测的流量，线下算法流量分配方法，从而指导在线的流量分配。另外SHALE算法对于流量分配问题的建模也与bid scaling算法有一定的差别（不过其本质依然可以将其归类为bid scaling算法），SHALE算法的收益不再考虑广告主的出价，更多的考虑未完成合约的损失，其数学模型如下：

在上式中，把流量按照属性划分为不同的单元，线下预测不同的流量单元的流量大小，式中为预测的流量单元i的流量，为广告主j的合约流量数目。，其中为符合广告主j要求的流量总和，用来衡量对广告主j的流量分配是否均匀。需要求解的为，表示流量单元i分配给广告主j的流量比例。

因此，SHALE算法包括两部分，一部分为线下计划部分，利用预测的每个流量单元的流量，求出，另一部分为online serve部分，利用指导流量的分配。需要指出来的是对于bid scaling算法，对于每个广告主只需要保存一个数，就可以进行在线分配，而naïve的SHALE算法需要保存，这样对每个广告主需要的数大大增加，增大的内存的消耗。为了解决这个问题，SHALE算法借鉴了bid scaling算法的思想，利用KKT条件，实现了只需要对每个广告主保存一个值，在线求出，从而使得分配过程不需要消耗大量内存。

对SHALE算法而言，如果流量预测算法能够精确的预测流量单元中的流量数目，那么SHALE算法的解为最优解。因此主要的问题是，如果预测算法有误差，SHALE算法是否具有鲁棒性呢？这里，对于流量到达顺序可以看作是已知分布的IID序列，实际上，我们可以把每个单元的流量数目看作是高斯分布，我们能够预测到流量的期望值，但是对于一些流量单元流量波动较大（方差较大），可能也会有较大的预测误差。SHALE算法考虑到预测的误差，一般如果线下计划部分计算间隔缩短，同时使用反馈校正的算法（如PID控制器）能够在很大程度上降低预测误差对于算法的影响。遗憾的是，并没有理论分析能够给出在这种情况下SHALE算法能够达到的竞争率。J.Feldman等在文章Online stochastic matching: Beating 1-1/e中给出了一种利用线下计划指导在线分配的二分图匹配的算法，给出的竞争率是0.67，但是从J.Feldman的理论分析推广的SHALE算法几乎不可能，因此到目前为止还没有关于SHALE算法竞争率的理论分析。

模式生成算法

SHALE算法的模型中有一个缺陷：没有考虑频次控制的影响，因此SHALE算法离线计划即使在预测算法精确预测流量的前提下，也不是一个最优的分配方案。有一些在线的改进方案，能够改进SHALE算法在具有频次要求的情况下的效果。下面介绍一种利用模式生成算法来对SHALE算法进行改进的方法。模式生成算法产生一些投放广告的模式，对每一个用户按照模式进行广告投放，从而保证广告主的频次要求。这里说的模式即是一段广告投放序列，如：

上图为两个广告投放模式，如果一个用户被分配按照模式1投放，当用户第一次到达时展示广告A，第二次为B，第三次为C，第四次为A，第五次为B。模式生成算法假设能够预测每个用户在频次控制时间段内访问网站的次数，通过生成模式控制广告的频次。模式生成算法的数学模型与SHALE的数学模型类似，如下：

其中为所有的模式库，和分别表示在流量单元i中用户访问类型（用户访问类型由用户在一段时间内的访问次数决定）的流量数目与独立用户数目；表示流量单元i中用户访问类型为中用模式n作为广告投放模式的用户数目；表示广告j在模式n中出现的次数，表示在模式n中，广告j出现的次数是否在要求的频次数目范围内；表示广告主j要求的独立用户数。用来描述模式n的好坏，比如广告的多样性、频次控制等。还可以根据业务需求对上述数学模型进行修改。

现在的问题在于怎么求解上述数学模型，和SHALE算法相同，我们利用预测的流量进行线下计划。但是和SHALE不同的是，模式生成算法不仅要求预测每个流量单元的流量，还要求预测每个流量单元中每种用户类型的数目以及每个用户属于哪种类型。另外模式生成算法的目标函数比SHALE算法复杂很多，SHALE算法只是一个二次规划问题，离线计划非常容易求解。然而在模式生成算法中，目标函数包含整数规划，我们需要去构造一个模式库，然后再优化整个目标函数。在模式库中构造所有的模式显然是不可行的（指数复杂度），幸运的是已经有成熟的算法求解此类型的优化问题，感兴趣的同学可以去查看列生成算法，这里不详细叙述。总之，借助列生成算法，可以产生所有有用的模式，并且对每一个类型的用户分配不同的模式。

在线投放广告时，当用户当天第一次访问网站时，通过用户类型以及所处的流量单元，查找，可以得到用户投放模式n的比例为。按照比例选择模式n作为用户的广告投放模式，并记下模式n，当用户第二次访问时，按照模式n继续给用户投放广告。

模式生成算法并没有解决广告投放中的所有问题，一个问题是利用模式生成算法需要对每一个用户记住一个广告投放模式，非常消耗内存。另外一个问题是，模式生成算法假设用户只属于一个流量单元，实际中用户有可能属于多个流量单元。对于模式生成算法的理论分析也非常复杂，因此目前对于模式生成算法的竞争率仍然是未知的。

结语

对于广告分配算法领域，研究工作一直都很活跃，每年都会有新的工作发表。本文总结的是展示广告guaranteed delivery中应用到的分配算法。其中有一些算法，由于理论方面过于复杂，我并没有包含（如利用强化学习的算法学习到bid scaling算法中的值，从而得到一个接近最优的分配算法）。另外Adwords problem领域的广告分配算法也有很多重要的工作，有一些方法可以扩展到展示广告中，但是另外一些扩展起来并不是很简单，虽然两个问题看起来非常类似。以后有时间或者等我把这几个问题都弄明白了，再扩展这个算法文档。