一种视频广告的预算约束限制拍卖机制

杨 雪 董红斌 滕旭阳

(哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001) (yangxue@hrbeu.edu.cn)

一种视频广告的预算约束限制拍卖机制

杨 雪 董红斌 滕旭阳

(哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001) (yangxue@hrbeu.edu.cn)

视频广告作为新兴互联网广告的一个重要的分支，为广告商带来巨大的收益，目前对于视频广告的拍卖方式主要采用关键字拍卖中的广义第二价格拍卖机制.但由于视频广告的时间可分性，使得视频广告与关键字拍卖内在上成为2个不同的问题.针对这些问题，主要工作如下：1)定义在线视频广告的形式化模型.该模型是有公共预算限制和私有价格信息的异质多物品拍卖模型，且该模型不限制竞价者的收益函数分布.2)前期工作已经证明了不同时存在具有个体理性、激励相容性和帕累托最优性质的预算约束拍卖的确定性机制.所以针对视频广告拍卖问题，基于预算约束的嵌钉拍卖基础，提出不限制竞拍者Agent的边际效益形式且满足激励相容性、个体理性激励相容的随机机制.3)定性及定量分析了该机制的收益性质.通过定义分配因子和支配因子证明了该机制收益的下界，并通过针对不同分布的收益函数和预算约束的实验，在系统收益和社会效用2个指标上验证了该机制的有效性.

多Agent系统;拍卖机制设计;在线视频广告;预算约束;非线性边际价值

在线广告系统作为IT产业中最重要的一个部分每年为出版商带来巨大的利润.作为一种高质量的传播媒体，视频广告将会成为增长最快的广告形式，而且在2018年年增长率将会达到23.8%，领先于手机广告21.5%[1-2].YouTube是全球最大的视频服务商，每年从其广告产品TrueView中赢取巨大收益.当YouTube的用户点击观看某一视频时，网站会选择一个广告在视频播放前进行播放.用户可以有2种选择：观看或者跳过.用户观看广告则会对广告商产生收益，如直接购买或者品牌价值提升等.出版商，即视频网站，需要从众多的广告投放者中选择广告，通常是通过以最大化收益为目的拍卖的形式进行选择.众多的视频网站都选择广义第二价格拍卖(generalized second price auction, GSP)，因为这种拍卖形式在理论上会带来较高收益且容易实现，其次作为关键词广告所采用的拍卖形式，其也被广泛接受.

但是视频广告服务网站往往需要广告商提供预算来控制其成本.在这种情况下，作为非激励相容拍卖机制的广义第二价格拍卖很容易被策略性的竞价来操纵.对于可以顺序播放数个广告的视频广告系统来说，每一个广告商对物品的需求也从单一的广告位变为既对广告顺序的需求且同时对其所获得的时间长度2种需求的混合形式，这使得视频广告系统成为了比关键字广告更加复杂的拍卖问题.在这种情况下简单地使用广义第二价格拍卖机制会对广告商和发布商的收益产生影响.

因此本文提出一种新的视频广告市场模型，与YouTube现有模型不同，该模型允许可以播放多个预播广告.每个广告商都有多个任意长度的广告，播放这些广告会为他们带来一定的私有价值.此外，每一个竞价者对他支付的价格总额都有预算约束.拍卖的输出是为每一个竞价者分配一个播放的时长、确定播放的顺序和对每一次播放需要支付的价格.因此，该问题可以抽象为基于预算约束的异质多物品拍卖问题.

从之前的对于视频广告的研究中，针对基于预算约束的异质多物品拍卖问题，不存在能同时满足个体理性、激励相容和帕累托最优等性质的机制.此外，关于这个领域的大部分研究是基于边际效益递减假设，这严重限制了机制在实际中的应用.基于上述原因，本文关注于设计基于多样性的价值分布的激励相容机制.首先在激励相容的确定性机制基础之上提出一种随机机制，然后分析了本文提出的机制的收益性质，并与最优定价拍卖进行了比较.对预算及用户的价值函数对于拍卖商收益的影响进行了讨论.尤其是给出了线性边际效益的条件下，有2个竞价者参与时的收益区间.随后按照竞价者收益边际效益不变、递增和递减几种情况，将本文提出的机制在收益和社会福利2个指标上与定价机制和维克利拍卖机制进行了比较.

1 相关工作

与关键字拍卖类似，在线视频广告也是一种异质多物品拍卖，但其是一种更加复杂的异质多物品拍卖的变体形式.GSP机制是目前应用最广泛的关键字拍卖机制，Varian[3]和Edelman等人[4]对原始的GSP拍卖机制的均衡性等问题进行了分析.而在加入预算约束的情况下，原始的GSP机制变得不再适用.Díaz等人[5]对GSP机制进行了改进，他们提出了几个不同的考虑预算约束的GSP机制，并证明了在改进的机制中纳什均衡和局部无嫉妒均衡存在的稳定性.而在考虑设计激励相容的机制方面，Borgs等人[6]2005年在竞价者的价格和预算都是私有信息的条件下提出一种随机机制，将所有参与者随机分成2个集合，并互相使用另一集合的最优价格作为其支付价格.Borgs等人证明了这个机制是收益最大化的激励相容机制.同时该文章还指出在预算信息下，没有任何的激励相容机制可以满足社会福利最大化的性质.

而在另一方面，嵌钉拍卖给研究人员提供了很好的思路.Ausubel[7]在2004年首次针对同质物品分配提出了嵌钉拍卖.该拍卖机制被证明与Vickrey 拍卖有相同的输出，但是其具有更易懂和私有性更好等特点而易于推广.而2012年Dobzinski等人[8]将预算约束加入到嵌钉拍卖中，并指出在有2个参与者存在的情况下，具有预算约束的嵌钉拍卖机制是唯一能同时满足个体理性、激励相容、和帕累托最优条件的机制.他对基于预算约束的研究引导了很多不同方向的研究.但是这个工作是针对同质物品进行分配，并且假设所有的商品的边际价值为恒定值.Colini-Baldeschi等人[9]基于嵌钉拍卖方法在关键字拍卖问题上，加入了点击率，分别对广告位可分和不可分的情况提出了确定的和随机的2种机制，并证明了他们都是满足帕累托最优性质的.而Goel等人[10]提出了一种多角嵌钉拍卖，该机制保证了嵌钉拍卖的基本性质，并且其更加易于扩展.他们还进一步对非硬约束的情况进行了研究[11]，在嵌钉拍卖的框架下使用下降价格，保证了算法的激励相容和帕累托最优的性质.但是目前主要的研究都是基于拟线性收益或边际价值递减的假设的基础之上，当这个约束条件被放松后，有约束限制的异质物品拍卖机制的性质很难被保证.

此外，也有很多学者致力于研究在基于预算约束下的异质多物品拍卖问题中的不可能性结果[9-10,12].在预算约束为公共信息的条件下，对于单调的递减边际价值分布的情况，文献[13]指出对于异质可加物品拍卖没有确定性机制能同时满足个体理性、帕累托最优和激励相容的性质.但是对于一维拍卖问题，存在不确定性机制同时满足以上3个条件.此外对于可分物品拍卖也进行了研究，综合以上文献对该问题的研究结果如表1所示[12,14-17]：

Table 1 The Status of Divisible Items Auction Under Budget Limits

Fig. 1 Video ad agents system图1 视频广告Agent系统

2 视频广告拍卖形式化模型

在视频广告投放市场中，有3种Agent：视频网站用户、广告商和出版商.当用户播放某一特定的视频时，将会被展示一些广告.对于某特定视频，在其之前播放的广告集合、播放顺序以及对该广告需要支付的价格通过拍卖的程序决定.当用户观看这些广告时，可以选择点击或者在播放几秒之后跳过.如果某条广告被观看完成、被点击或者观看超过一定的时长(如30 s或广告长度的50%)，则投放该广告的广告商需要向出版商支付一定的费用.拍卖的过程结合了确定将会被展示的广告集合和为每一个展示了广告的视频广告商确定合理的支付价格2个过程.广告商可能有不同时长的广告可以参与竞拍，并且其对于全部可支付的价格存在预算约束.图1是对视频广告市场的简单概述.

假设市场中有3个广告商，每个广告商有3个不同市场的广告可以播放，且其播放成本约束于其预算.如果用户进入到视频播放页面，出版商将会要求所有广告商提交竞价、组织拍卖并最终确定需要播放的广告的集合和广告播放的顺序以及需要支付的价格.用户可以选择观看或者跳过某广告，如果用户观看了该广告，则出版商将会对这次广告的展示收取费用，但是这个费用将会严格低于该广告商的预算约束.下面对这个市场模型进行形式化的描述.

2.1 市场定义

首先考虑一个简单的在线视频广告发布环境.在某视频发布平台上，播放某一特定视频之前会有一些广告首先播放.假设可以播放广告的总时间为M，对该广告位有兴趣的竞拍者集合为N.每一个竞拍Agenti(i∈N)的广告被视频网站的用户浏览之后都会获得一定的私有价值，即用户在观看广告后潜在地产生购买行为等.进一步假设每一个广告商都有不同长度的广告可以被播放，而且不同长度的广告会带来不同的价值.因此，每一个广告商Agenti的价值定义为函数vi,其输入为广告的长度(单位s)，输出是其相对应的收益价值.

(1)

从收益的定义中可知，Agent的收益函数是非拟线性的.

2.2 重要性质

在给定了市场模型的形式化描述之后，下面将会定义一些本文机制需要满足的性质.

给定一个分配，所有交易者的效用总和称为社会福利，则机制的有效性可以定义如下.

换句话说，当广告商对于其要播放的广告所付出的价格不会高于其真实估价，且他的支付不会超过其预算时，该机制符合个体理性性质.

在具有激励相容性的机制中，参与竞价者上报自己真实报价能获得不低于其他竞价策略的效用.该性质使得系统在分配时能同时兼顾最大化社会总效用与最大化竞价者效用.

3 机制设计

第2节形式化地定义了对于公共预算情况下的拍卖机制.针对该模型，本文基于Dobzinski等人[8]的工作，在嵌钉拍卖的基础之上进一步研究.首先讨论了VCG(Vickrey-Clarke-Groves auction)模型和基本的嵌钉拍卖在视频广告模型中的不适用性;然后给出了一种激励相容的拍卖机制模型，并证明了该模型的一些基本性质;最后通过算例来解释该模型.

3.1 VCG模型

当参与者具有拟线性收益函数时，VCG机制是一种最大化社会效用的激励相容机制.但是当参与者的收益函数为非拟线性设置时，VCG机制的激励相容性就难以被保证.如在添加了预算约束的情况下，竞拍者的收益函数变为

(2)

若在VCG机制中，分配给竞拍者的物品价格高于其预算约束，则该分配会被取消，竞拍者效用为0.此时竞拍者可能会改变其报价，使得在其预算约束内获得较少的物品而达到高于0的效用.此时的VCG机制就不再激励相容.

3.2 基本的嵌钉拍卖

基本的嵌钉拍卖是 Ausubel[7]首次提出的，嵌钉拍卖是一种升价拍卖，在每一次价格升高时，竞价者会提交一个对于该价格的物品需求数量.该拍卖机制对于复杂的多物品拍卖与VCG机制具有相同的输出，但是同时具有易于理解和实现等优点.Dobzinski等人在Ausubel工作的基础上对于嵌钉拍卖进行了改进，他们提出了一种在预算约束下的嵌钉多物品拍卖机制.特别地,他们指出，在私有预算约束和私有价值函数信息的条件下，不存在同时满足激励相容性和帕累托最优的机制.而在公共预算和私有价值函数以及所有竞拍者的边际价值是固定不变的情况下，基于预算约束的嵌钉拍卖是唯一同时满足激励相容性和帕累托最优的机制.

在嵌钉拍卖中首先定义参与竞拍者的需求为:

(3)

在基于预算约束的嵌钉拍卖问题中，基础价格逐步增加，而每一个竞价者对于物品的需求随着价格的增加逐步降低.每一个物品给竞价者所带来的价值在竞价的过程中是稳定不变的.而需求则被定义为在当前的价格下，每一个竞价者在其预算约束下能负担的最多的个体数量.在除了某竞价者i之外的所有人的需求之和小于当前市场可提供的物品总量时，该竞价者i则会以当前的价格“钉住”满足所有其他竞价者需求时的剩余物品.因此，在不同的价格下，每一个竞价者所能获得的价格不同.在拍卖最后，每一个竞价按照其所钉住的物品的数量和对应的价格的总和支付.

在基本嵌钉拍卖中讨论的是离散的同质多物品拍卖，对于每一个竞价者来说，其边际价值在拍卖过程中是恒定不变的.但是，在线视频广告问题中，拍卖的标的物品为播放时长，该物品是无限可分的，且不同长度的广告会为广告商带来不同的利润.此外，每一个广告的位置也会影响到每一个竞价者的效用，这使得本文的问题变成了一种复杂的异质多物品拍卖问题.接下来的内容会给出一种改进的嵌钉拍卖算法，来解决这些问题.

3.3 同质约束嵌钉拍卖

为方便讨论，首先考虑一个同质连续物品拍卖的问题，即假设所有的广告的关注程度与播放顺序无关.视频广告拍卖机制的输出则为：为每一个竞价者分配一个播放时长xi并为其确定支付价格{pi}.那么对于广告商i，其获得任何不同的一个时长对于其效用不会产生影响.广告商Agenti的效用计算方式为

(4)

在同质约束嵌钉拍卖中，为每一个参与者i记录已经分配给其的物品数量xi，当前的全部需要支付价格pi，以及其剩余预算Bi=βi-pi.机制也会记录基础价格b*和剩余物品的数量q.价格p*随着需求严格大于全部可供应量而逐步上升.在基于预算约束的嵌钉拍卖中，每一个参与者Agent的边际效益在拍卖过程中保持不变，则其需求定义为能使得竞拍Agenti带来最高收益的单元数量.但是在考虑不限制边际价值分布的情况下，为了保持机制的激励相容性，本文定义最大需求(max-demand)，即在不考虑竞价者的估值情况下，基于当前的价格，其所能负担的最多物品的数量：

Di=Bip.

(5)

则机制按如下步骤运行：

2) 通过价格增量ε持续增加基础价格，同时竞拍Agent的max-demand持续降低.直到对于竞价者i，除其以外的其他所有人的max-demand之和严格小于剩余物品的数量，计算这个差值为πi.πi为当价格为p时，竞价者i可以获得的最多物品量：

(6)

为每一个Agent计算其max-demand的差值后，机制储存每一轮为Agent分配的时长及价格.根据以下的公式更新相关变量：

(7)

3) 重复步骤2.直到所有人的最大需求之和小于当前系统所能提供的全部物品的数量∑D(bp)≤q，则按照当前的价格满足所有人的最大需求.

4) 在拍卖结束后，按照Agenti对于不同长度广告所获的的效用， 选择使得Agenti收益最大的时长最终分配给该Agent，将剩余的物品丢弃.至此完成了对所有竞价者时长的分配.

3.4 异质约束嵌钉拍卖

本节将同质约束嵌钉拍卖扩展到异质物品的情况，即对于不同的广告，先播放能使其获得更高的关注率.机制的输出为分配X={di,q∈M×Q}和支付{pi}.此时竞价者的效用函数改变为

(8)

由Colini-Baldeschi[9]和Goel等人[10]的工作，对于异质拍卖，并且估值函数并不是拟线性情况下，不存在确定性的算法满足IC和PO的性质.所以选择一种简单的方式来保证算法激励相容性，将所有的竞价者以分布为U(0，m)的情况随机取样，来决定最终Agent的分配顺序.

3.5 性 质

对于上述的同质和异质约束嵌订拍卖机制，由于每一个竞价者的全部支付不会超过其预算，个体理性的性质可以立刻得到.

定理1. 竞价者的支付将永远不会高于其预算.

(9)

证毕.

定理2. 在任意的边际效益分布条件下，同质拍卖机制是激励相容的.

证明. 对于每一个i和v-i来说，由于其满足以下条件，该机制是激励相容的：

1) 支付pi只依赖于其预算约束，而不依赖于vi.此外由于预算是公共信息，则对于每一个vi，θi∈θ存在着价格pθ∈，因此对于所有使得f(vi,v-i)=x的vi，都有p(vi,v-i)=pθ.

证毕.

定理3. 同质机制总是销售市场上的所有单元.

定理4. 异质约束嵌钉拍卖机制在所有的边际效益分布情况下都是满足IC，IR的.

异质物品拍卖机制并不改变每一个竞价者的支付规则，所以IR和IC等性质可以容易地从同质物品拍卖的情况得到.

4 收益分析

4.1 最优收益定价拍卖机制

为了方便比较分析，首先定义定价最优收益拍卖机制.在Borgs等人[6]的工作中，他们描述了一种对于所有Agent都以确定的价格进行销售，该机制可以在不考虑其他性质的前提下最大化拍卖者的收益.假设在该机制中，分配给竞价者i的物品数量为xi, 且所有的物品以确定价格p销售.针对视频广告拍卖环境下，满足个体理性的分配中可行的定价拍卖需要满足以下条件：xi≥0，βi≥xip且vi,xi≥xip.假设当价格p=p*时，此时分配X={x*}，能最大化拍卖商的收益：

,

(10)

本文和Dobzinski等人[8]的工作一样，定义竞价者支配因子：

.

(11)

4.2 同质物品拍卖收益

本节分析对于同质物品拍卖情况下的收益.

(12)

证毕.

进而可以得到如下的引理.

证毕.

4.3 支付和分配分析

在确定性同质约束嵌钉拍卖机制中，支付和分配规则都是由预算确定的.现在讨论在不同的估值函数下，机制的收益与预算之间的关系.首先考虑一种简单的情况，假设市场中有m个单元需要出售，2个竞价Agent参与竞拍，其预算分别为β1,β2，且β1>β2.

(13)

且F(x)为

(14)

(15)

(16)

(17)

(18)

剩下的物品的单位价格可以通过归纳法获得：

(19)

通过非齐次线性方程，可求得，

(20)

所以对于任意数量的物品所需要支付的价格为

F(x)=∫p(x)dx=

(21)

证毕.

这个结果也很容易扩展到多个Agent的市场中.

4.4 丢弃物品后的收益

4.1～4.3节分析了算法1中的前3步的收益.然而，最终的收益会受到被丢弃的物品数量的影响.因此，本节分析不同的边际函数的收益损失.

(22)

假设竞价者i有最高的预算，则拍卖商最终从i处获得的收益为

(23)

(24)

为了简化分析，定义xmax是在市场中最后被分配的单元，则

(25)

Fig. 2 An example of revenue analysis图2 收益分析实例

5 实 验

由于拍卖者的收益和社会总效用受竞拍者的价值函数和预算约束的影响.所以在本节中，设计了3个实验来分析不同情况下的价值函数分布以及预算约束对算法效果的影响.实验运行在Windows 7平台上，处理器为core 2 2.66 GHz，内存为2.00 GB，采用的运行环境为matlab2015b.

5.1 拟线性价值函数对收益影响分析

在实际应用中竞拍者的收益函数可能是多样的.所以在本节中，对竞拍者边际价值(marginal value,mv)的几种不同情况进行了实验分析，比较本文提出的H-Clinching拍卖机制、VCG机制和定价拍卖的收益和社会效用.

1) 边际价值为固定值

设置2个竞价者的预算约束都为100，拍卖者提供的播放时长为15 s.竞价者1的边际效益为100;竞价者2的边际价值在[0,100]区间线性增加.

图3是社会效用受拍卖者边际效益变化的影响.

Fig. 3 The revenue from various fix marginal valuations图3 不同定值边际价值对拍卖者收益的影响

从图3中可以看出，随着竞价者2的边际效益的增加，定价拍卖和H-Clinching拍卖机制的收益都随之增加.但是对于定价拍卖机制来说，当竞价者2的价值小于10时，由于价值过低的情况导致了机制无法收取其全部的预算，所以系统的收益随着竞价者的边际价值递增而线性增加；但是当边际收益增加到10以后，此时机制会收取其全部的预算作为支付价格.对于H-Clinching来说，由于其预算固定不变，Agent的价值函数会影响其弃掉的物品个数.随着竞价者2的边际价值升高，丢弃的物品会越来越少，从而使得整个系统的收益值增加.当Agent 2的边际价值达到60时，其收益值大于系统分配给其最后一个物品所应该付出的最高价格，则任何分配给竞价者2的物品都不会被弃掉，此时系统达到了最大收益.而对于VCG机制，根据机制的分配方式，其会将物品分配给对其最有价值的Agent.但是由于基于预算约束的VCG机制是选取了预算和价值函数的最小值作为其分配过程中的价值函数.则由于竞价者2的存在，不会对竞价者1所获得的价值产生任何影响，同理竞价者1也如此，则对于2个Agent所收取的价格都为0，此时系统的收益为0.

图4展示了固定边际效益值下不同边际效益对拍卖效率的影响.

Fig. 4 Social welfare from various fix marginal valuations图4 不同的定值边际价值对拍卖效率的影响

从图4可知，可以看出对于拍卖效率来说,VCG机制和H-Clinching 机制都远远高于定价拍卖机制，这是由于定价拍卖机制仅考虑最优化其收益值，其总是将物品分配给首先达到最优收益的Agent，导致其社会总福利非常低.在基于预算约束的VCG机制总是最优化当前社会福利，但由于预算约束，其按照Agent的收益函数和预算约束的最小值作为其新的收益函数.竞价者1的收益值较高，从而其分配受到了预算约束的限制.但是当竞价者2的收益值较小时，反而没有受到预算约束限制，这导致了改进的VCG机制将更多的资源分配给了价值较小的竞价者2.对于H-Clinching拍卖机制，其按照竞价者的收益函数从高到低丢弃物品，所以其社会总福利随着边际效益的增加而线性增加.

2) 边际收益线性增加

在本实验中，设置竞价者1的边际价值为100；Agent 2的边际价值函数为：mv2=kx.此时，对于竞价者2，获得新的物品会对其带来更高的收益.2个竞价者对应的收益函数为

(26)

设置2个竞价者的预算约束均为100，当竞价者2的递增边际价值系数k∈[0,25]时，比较基于预算约束的VCG机制、定价拍卖机制和H-Clinching拍卖机制的收益和社会福利，如图5、图6所示.

从图5中可以看出，随着竞价者的边际价值的增加，定价拍卖和H-Clinching机制的收益都会增加，但是当边际效益增加到一定程度时，由于预算约束的限制，2个拍卖机制的收益都趋于稳定.当边际效益线性增加时，3个机制的社会总效用也产生了和固定边际价值相同的结果.

Fig. 5 The revenue from various increasing marginal valuations图5 不同的递增边际价值对拍卖者收益的影响

Fig. 6 Social welfare from various increasing marginal valuations图6 不同的递增边际价值对拍卖效率的影响

3) 边际收益线性递减

下面我们将讨论边际价值递减的情况下3个拍卖机制在收益和社会总效用2个指标上的异同.在这个实验中，假设竞价者1的边际价值为mv1=100; Agent2的边际价值函数为

mv2=-kx+200.

(27)

2个竞价者对应的收益函数为

(28)

设置2个竞价者的预算约束均为100，当竞价者2的递增边际价值系数k∈[0,375]时，比较基于预算的VCG机制、定价拍卖机制和H-Clinching拍卖机制的收益和社会福利，如图7、图8所示.

Fig. 7 Revenue from various decreasing marginal valuations图7 不同的递减边际价值对拍卖者收益的影响

Fig. 8 Social welfare from decreasing marginal valuations图8 不同的递增边际价值对拍卖效率的影响

从图7可以看出，H-Clinching拍卖机制和定价拍卖机制的收益仍远高于VCG机制.当竞价者2的单位价值很高时，其收益较高.但是随着k的增加，竞价者的收益值下降，由于H-Clinching拍卖的价格随着物品的增加呈指数增长, 这是由于首先丢弃的物品是为拍卖商带来最大利润的物品，所以收益值下降较快.在下降一段区间内，收益呈平稳趋势.而对于定价拍卖机制来说，当竞价者的边际效益较高时，其收取竞价者全部预算作为支付;当边际价值降低到一定阶段，定价拍卖机制的收益也会降低.VCG机制与固定边际价值相同的原因，使得其收益一直为0.

从图8可以看出，VCG机制和H-Clinching机制都可以达到较高的社会福利.k<12.5时，相比较VCG和定价拍卖来说，H-Clinching机制最优化的分配了全部物品.由于H-Clinching在边际价值开始降低时会放弃较多的物品，随着竞价者的收益降低而趋于稳定.而VCG机制中，由于竞价者1的收益受到其约束的限制，当竞价2的边际价值较高时，它会将更多的物品分配给竞价者2，为系统带来更高的福利.随着竞价者2的边际价值降低，系统的福利降低.直到竞价者2的边际价值与竞价者1的边际价值持平或更低时，2个竞价者同样受到其预算约束的限制，此时的社会总福利不再变化.

5.2 非拟线性价值函数对收益影响

在本节我们假设竞价者的边际价值是先上升后下降，这种问题在现实生活中是可能发生的，即当竞价者拿到一定数量的播放时长之前，每多获得1 s所能带来的利润增加，但是当其获得的时长超过某一固定的广告长度之后，边际价值会降低.这种设置的边际效益可以形式化表示为

(29)

其价值函数可以表示为

v=∫mv(x)dx=

(30)

假设竞价者的预算约束均为100.竞价者1的边际价值为固定值100，而竞价者2的边际收益遵循上面的函数，且假设x*=5.当k在[0,100]区间内变化时对3个不同机制的收益以及社会效用产生的影响如图9、图10所示:

Fig. 9 Revenue from various non-qusi linear marginal valuations图9 非线性边际价值对拍卖者收益的影响

Fig. 10 Social welfare from various non-qusi linear marginal valuation图10 非线性边际价值对拍卖者收益的影响

从图9可以看出，对于H-Clinching机制，当竞价者的边际价值较低(k<2)时，分配给竞价者2的物品被全部被丢弃；但是当k持续增加(25之后迅速达到了收益最大化，其收益占定价拍卖机制的92%.而对于VCG机制的收益，与上节讨论的内容相同.

从图10可以看出，VCG机制和H-Clinching机制的拍卖效率都远远高于定价拍卖机制，这是由于定价拍卖机制仅考虑最优化其收益值，而不考虑社会效用，所以其总是将物品分配给首先达到最优收益的Agent，导致其社会总福利非常低.在图10中，H-Clinching机制产生的社会福利甚至超过了VCG机制，这是由于约束限制的存在，当竞价者2的价值增加超过竞价者1时，在VCG机制中体现不出竞价者2的优势，从而将更多的物品分配给了价值较低的竞价者1.但是在H-Clinching机制中，价值更大的拍卖者的物品会被保留而不是丢弃，从而保证了总体社会效用.

5.3 预算约束对收益的影响

在本节中，我们将对2个竞价者预算约束值的分布不同对收益产生的影响进行讨论.为了减少其他因素对结果的影响，简单化设置:2个Agent的边际收益10，竞价者1的预算约束固定为100，竞价者2的预算约束从20线性增加到120.图11和图12分别展示了3个机制的收益和社会效用值的关系.

Fig. 11 Revenue from various budget limits图11 预算约束对拍卖者收益的影响

Fig. 12 Social welfare from various budget limits图12 预算约束对拍卖效率的影响

从图11可以看出随着竞价者2预算约束的增加，定价拍卖机制和H-Clinching拍卖的收益都随其增加.在[20, 80]的区间上，H-Clinching拍卖机制的收益增加较快，达到80之后线性增加.而VCG机制由于预算对其价值的受约束，使得2个竞拍者在彼此不存在的条件下都无法获得更高的收益，其收益一直为0.从图11可以看出，H-Clinching 拍卖机制在2个竞价者的预算相差较大时收益值较低，但是随着2个Agent预算差距的减小，其收益增加较快，在达到一个稳定状态之后，整个系统的收益与定价拍卖机制一样线性增加.

在社会效用方面，对于VCG机制预算的大小不影响其分配，其一直是处于最大化社会效用的分配方式.在H-Clinching机制中而随着竞价者2预算的增加，其可以获得更多的物品，由于竞价者2的边际效益较高，则所有竞价者带来的社会福利缓慢增加.直到竞价者2的预算约束增加到80时，2个竞价者所获得的所有物品都不会被丢弃掉，此时达到了社会福利最大化.定价拍卖机制不考虑激励相容和社会福利的性质，使得社会福利在竞价者的预算约束增加时仅仅小幅增加.

6 结 论

本文提出了一种形式化的视频广告拍卖模型.特别地，和YouTube现在运行的广告系统不同，在该模型中可以有多个广告同时在视频播放前被播放.并且对于每一个参与竞拍的广告商，他们拥有一些不同时长的广告，同时每个广告都有一个对应的私有价值信息.每一个参与竞拍的Agent对于其要支付的价格都有一个公共信息的预算约束限制.最终拍卖会为每一个Agent分配一个播放时长用以播放其广告，确定所有广告的播放次序和为每个广告展示确定一个支付价格.这是一个基于约束限制的异质多物品拍卖问题.之前的研究已经指出，对于公共信息的预算约束限制的多物品拍卖问题，不存在着同时满足激励相容、个体理性和有效性性质的机制.且之前的研究工作基本上都是以边际价值非增为条件展开的.所以，在不限制价值的分布条件下，提出了一种IC、IR和无正向传播的机制, 并且通过推导证明给出了这个激励相容机制的收益的下限.最后，本文通过对3种不同的线性收益函数和一种非线性收益函数的实验分析，对比与能带来最大收益的定价拍卖和改进的VCG机制，证明了本文提出的机制在收益和社会效用指标上的有效性,并分析了不同的预算约束对3种机制的收益和社会效用的影响.

本文的工作是首次将在线视频广告拍卖与预算约束限制结合研究，对于未来还有很多方向可以研究.首先，在确定性机制中，为了保证效用最大化，将Agent所获得的多余物品丢弃，而且，在随机机制中，是利用均匀分布的方法对所有的Agent进行排序.这保证了系统的激励相容的性质，但是可能会降低系统的效率.所以未来可以对这种次序分配进行研究，在保证激励相容的条件下，将被丢弃的物品重新分配，并且找到更合理的次序分配方式，提高系统的效率.另外对于机制的收益进行分析的部分，本文仅考虑了边际价值呈线性变化的条件下的收益，接下来希望能对单位估值的一般分布情况进行分析，得出一般性的结果.未来我们也希望对非硬性预算约束限制进行研究，即Agent的支付可以在不超过非硬预算的区间内进行浮动，这将是一个非常有挑战性的工作.

[1]Braude N. Global entertainment and media outlook 2015-2019: Hot topics: PwC[R]. London: Price Waterhouse and Coopers & Lybrand, 2014

[2]Kumar S. Evolution of Web advertising[M] //Optimization Issues in Web and Mobile Advertising. Berlin: Springer International Publishing, 2016

[3]Varian H R. Online ad auctions[J]. American Economic Review, 2009, 99(2): 430-34

[4]Edelman B, Schwarz M. Internet advertising and the generalized second price auction: Selling billions of dollars worth of keywords[J]. American Economic Review, 2015, 97(1): 242-259

[5]Díaz J, Giotis I, Kirousis L, et al. On the stability of generalized second price auctions with budgets[C] //Proc of Latin American Symp on Theoretical Informatics. Berlin: Springer, 2014: 695-706

[6]Borgs C, Chayes J, Immorlica N, et al. Multi-unit auctions with budget-constrained bidders[C] //Proc of the 6th ACM Conf on Electronic Commerce. New York: ACM, 2005: 44-51

[7]Ausubel L M. Efficient ascending-bid auction for multiple objects[J]. American Economic Review, 2004, 94(5): 1452-1475

[8]Dobzinski S, Lavi R, Nisan N. Multi-unit auctions with budget limits[J]. Games and Economic Behavior, 2012, 74(2): 486-503

[9]Colini-Baldeschi R, Henzinger M, Leonardi S, et al. On multiple keyword sponsored search auctions with budgets[M] //Automata, Languages, and Programming. Berlin: Springer, 2012: 1-12

[10]Goel G, Mirrokni V, Leme R P. Polyhedral clinching auctions and the AdWords polytope[C] //Proc of the 44th ACM Symp on Theory of Computing. New York: ACM, 2012: 107-122

[11]Goel G, Mirrokni V, Paes L R. Clinching auctions beyond hard budget constraints[C] //Proc of the 15th ACM Conf on Economics and Computation. New York: ACM, 2014: 167-184

[12]Lavi R, May M. A note on the incompatibility of strategy-proofness and pareto-optimality in quasi-linear settings with public budgets[J]. Economics Letters, 2012, 115(1): 100-103

[13]Sakurai Y, Saito Y, Iwasaki A, et al. Beyond quasi-linear utility: Strategy/false-name-proof multi-unit auction protocols[C] //Proc of Web Intelligence and Intelligent Agent Technology. New York: ACM, 2008: 417-423

[14]Bhattacharya S, Conitzer V, Munagala K, et al. Incentive compatible budget elicitation in multi-unit auctions[J]. Computer Science, 2009, 107(5): 1472-1478

[15]Itai A, Mark B, Avinatan H, et al. Position auctions with budgets: Existence and uniqueness[J]. The BE Journal of Theoretical Economics, 2010, 10(1): 1-32

[16]Wu Fan, Zheng Zhenzhe. Game theory based spectrum dynamic management[J]. Journal of Computer Research and Development, 2016, 53(1): 38-52 (in Chinese)(吴帆, 郑臻哲. 基于博弈论的频谱动态管理研究[J]. 计算机研究与发展, 2016, 53(1): 38-52)

[17]Poole L D, Mackworth A. Artificial Intelligence Foundations of Computational Agents[M]. Translated by Dong Hongbin, et al. Beijing: China Machine Press, 2015 (in Chinese)(Poole L D, Mackworth A. 人工智能：计算Agent基础[M]. 董红斌等译, 北京: 机械工业出版社, 2015)

Yang Xue, born in 1986. PhD candidate in Harbin Engineering University. Her main research interests include intelligent optimization algorithm and auction online advertising.

Dong Hongbin, born in 1963. Professor and PhD supervisor in Harbin Engineering University. His main research interests include multi-agent system and machine learning.

Teng Xuyang, born in 1987. PhD candidate in Harbin Engineering University. His main research interests include machine learning and intelligent information processing.

Budget Constraint Auction Mechanism for Online Video Advertisement

Yang Xue, Dong Hongbin, and Teng Xuyang

(CollegeofComputerScienceandTechnology,HarbinEngineeringUniversity,Harbin150001)

As an important segment in IT industry, online advertising brings huge revenue to publishers. Most of the video advertisement auction are traded as keyword action. Due to the selling object are divisible in video ad auction, these two issues are two internal different problems. Hence, we formulate a novel market model to allocate video advertisements in a playing order as a pre-roll ads sequence. In this model each bidder holds various ads with diverse durations, private valuations and public budget limit. It has been proved that there is no individual rationality, positive transfer and Pareto optimal deterministic mechanism for private budget assumption case. Hence for this heterogeneous commodities allocation problem with budget constrain, we develop a randomize mechanism based on “Clinching auction” frame. In particular, we study no limited valuation distribution setting and show that this mechanism is incentive compatible, individually ration and no positive transfer. Furthermore, compared with the fixed price revenue optimize auction, our mechanism has lower bound revenue based on a dominance parameter which measures the size of the budget of a single agent relative to the maximum revenue. And the availability on revenue and efficiency of H-Clinching auction has been proved by several experiments.

multi-agent system; auction mechanism design; online video advertisement; budget constraints; non-linear marginal valuation

2016-06-27；

2016-10-10

国家自然科学基金项目(61472095，61502116，41306086)；黑龙江省教育厅智能教育与信息工程重点实验室开放基金项目 This work was supported by the National Natural Science Foundation of China (61472095, 61502116, 41306086) and the Open Foundation of the Heilongjiang Provincial Education Department Key Laboratory of Intelligent Education and Information Engineering.

董红斌(donghongbin@hrbeu.edu.cn)

TP301