论文名称：Optimal Delivery with Budget Constraint in E-Commerce Advertising
1.摘要
电子商务平台上的在线广告为广告主提供了一个触达不同潜在受众的机会。分配广告的广告服务系统(如展示和搜索广告系统)应该满足品牌广告主的受众广泛、效果广告主的点击和转化等目标，同时努力最大化平台的整体收入。本文提出了一种以线性规划为基础的优化方法来优化收入，同时提升其它效果指标。我们在阿里巴巴电子商务平台上实现了一个线下模拟系统，并在考虑系统性能、排名和定价模式的情况下运行在线请求的拍卖，从而验证了我们的算法。我们还将我们的算法与相关工作进行了对比，结果表明我们的算法可以有效提高平台的运行性能和收益。
2.介绍
亚马逊(Amazon)、eBay和阿里巴巴(Alibaba)等电子商务平台开展了数亿次拍卖，出售广告机会。在线广告在连接广告主和受众方面起着至关重要的作用，为电子商务平台创造了巨大的价值。有多种不同类型的在线广告，如效果广告、品牌广告等，本文主要关注效果广告。在这个市场中，广告主可以指定他们每天愿意支付的最大金额，并通过电子商务平台的各个页面获得受众。效果广告的广告主的目标通常是将预算最大化效果目标（如提升点击率、转化率等）。同时，广告服务系统也会代表平台优化整体收入。
电子商务平台广告服务系统的核心问题之一是将广告与上述目标匹配起来，这可以表述为一个有约束的优化问题。在一个复杂的竞争环境中，同时实现所有的目标有诸多挑战。每个单独的广告活动都有自己的预算和效果目标，成千上万的活动相互竞争以获取市场中的广告展现机会，这使得优化变得极其困难。
本文提出了电子商务平台中广告的最优分配问题，该问题可以表述为一个约束优化问题，在预算约束下最大化指定的目标。本文的贡献可总结如下：
提出了一种基于线性规划的方法来优化平台的整体收益，同时提高活动层面的效果目标。与以前的工作相比，我们的方法可以运行在所有流量上，并在展示和搜索广告中实现 我们设计了一个模拟系统，通过重现历史请求来评估不同分配计划的效果。将该方法与阿里巴巴电子商务平台的定价和排名方案结合实施，结果表明，该方法既能有效提高营收，又能有效提高各项效果指标
3.问题定义
3.1 相关术语与符号
大多数广告服务系统所做的是让广告主尽可能多地参与拍卖，直到他们的预算被耗尽，然后让他们在一天的剩余时间里没有资格参与拍卖。这种策略在一天的开始会带来非常激烈的拍卖竞争，给广告主带来非常偏颇的流量，很难最大化广告主的效果目标。本文研究了一种同时实现不同效果指标和最大收益的在线分配策略。在阐述这个问题之前，我们先定义一些基本概念。
当一个用户在推荐系统浏览一个页面或者在搜索引擎里面输入一个关键词查询，一个请求就会发送到广告服务系统。是一整天的请求流
表示广告集合
表示广告活动，每个广告活动有个预算限制。广告主将活动作为其实现效果目标的最小营销单位
对于每个请求中的拍卖，竞价者参与竞争P个广告位。参与拍卖的广告集合，也叫做竞价空间(bidding landscape)，其中，是竞价空间的广告数量，会被广告服务系统进行排序。每个bidding landscape可以被转化为一系列set of slates
代表请求i的slate j,其中表示该页面能够展示的最大广告数量。slate可以通过以下方式获取：删除中的某些广告(同时保证广告的顺序)，然后截断广告序列使得序列里的广告数量为。一般情况下，比要小，slate代表bidding landscape的一个子集
表示包含广告的set of slates
是一个二进制变量，它表示请求i是否采用slate j
bidding landscape：在某次特定请求中，参与拍卖竞争的广告主数量
set of slates：bidding landscape的一个子集
3.2 问题定义
根据上面定义的概念与符号，可以将上述问题表述为一个多目标线性规划问题(MLOP)：
在等式(1)中，表示当请求j采用slate i时的期望收入。表示当请求i采用slate j时广告k的期望消耗。第一个目标函数是平台的期望收入。在真实场景中，广告主经常在不同的广告活动中考虑不同的效果指标。等式(1)中的其它目标函数是广告活动层面的不同效果指标，如点击和转化。由于通常存在多个(可能是无限个)帕累托最优解，这类多目标优化问题的求解非常困难。尽管多目标线性规划问题试图最大化每个广告活动的效果指标，但我们的模型无法保证每个广告活动都能获得理论上的最优效果。因此，我们将广告活动的所有效果指标合并为多个效果约束，将原来的多目标优化问题转化为带约束的单目标约束问题。最后，我们将广告活动表述为一个带约束的单目标线性规划问题(SLOP)，该问题的约束条件是广告主的点击量和转化率等效果指标。表述如下：
和表示请求i中slate j中广告k的预估点击率和预估转化率。和分别表示希望获取更多点击或转化的广告活动集合。因此，这个问题定义的前提是将具有相同效果目标的广告活动分组，并设置点击约束和转化约束。等式(2)可被重写如下：
等式(3)中的约束参数是对偶变量
3.3 实时算法
基于互补松弛定理开发了实时算法来解决上面提到的多约束优化问题。算法描述如下：
对于请求 i，广告服务系统将会通过检索和排序广告获得bidding landscape。slate_{j}可以通过以下方式获取：删除中的某些广告(同时保证广告的顺序)，然后截断广告序列使得序列里的广告数量为，下文将会描述如何产生slate候选。接着，我们需要计算，我们按照如下公式计算请求i的每个slate的得分：
最终，我们会选择得分最高的slate
4.实现
在实践中，有一些必须考虑和克服的实际问题。其中包括指标预估、在线服务系统和离线仿真系统的性能挑战
4.1 指标预估
我们首先介绍，它表示请求i中slatej中广告k的预估点击率。slate j中每个广告都有一个特定位置p，因此，也可以被表示为。考虑到位置偏差，我们使用了检验假设来评估。这个假设的含义是用户有更大概率出去点击排在前面的结果，有更小概率去点击排在后面的结果。这意味着每个排名都有被检验的可能性：
其中，是请求i中广告k的点击率。在PPC(pay per click)广告模型中，我们将广告k的消耗分配给请求i中的slate j：
在我们的广告系统中，每产生一次点击，广告主真正需要付的钱取决于GCP机制。当slate固定时，点击价格和广告k的期望消耗是很容易计算出来的
假设同一个页面上不同广告的CTR是独立的，我们可以使用每次曝光的期望消耗之和来表示请求i中slate j的收入：
这个假设并不一定总是成立，但它是易于实现且有效的
4.2 产生Slate
生产slate的最初方案是删除bidding landscape的某些广告，这样最多会产生个slate。这种方案的时间复杂度是，这会给离线训练和线上服务带来巨大的挑战。这里我们提出了一个简单的方法来解决这个问题。在Algorithm 1中，我们选择得分最高的slate:
这意味着我们需要计算每个slate的得分。我们使用sum method来逼近公式(7):
因此，我们可以根据下式计算bidding landscape中每个广告的得分：
我们根据广告得分对广告进行排序，并选取个广告构建最佳slate。值得注意的是，由于位置偏差和GSP机制的影响，这些预估值，如可能会有一些轻微误差
5.附录
线性规划是目标函数和所有约束函数均为线性函数的优化问题，可表述如下：
对于任意线性规划问题(无论是标准形式还是不等式形式)，只要原问题成立，强对偶性都成立。将此结论应用到对偶问题，可以得出结论，如果对偶问题可行，强对偶性成立。对线性规划问题，只有一种情况下强对偶性不成立：原问题和对偶问题均不可行
