ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (2): 415-427.doi: 10.7544/issn1000-1239.2017.20160491

• 信息处理 • 上一篇    下一篇



  1. (哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001) (
  • 出版日期: 2017-02-01
  • 基金资助: 

Budget Constraint Auction Mechanism for Online Video Advertisement

Yang Xue, Dong Hongbin, Teng Xuyang   

  1. (College of Computer Science and Technology, Harbin Engineering University, Harbin 150001)
  • Online: 2017-02-01

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

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

Abstract: 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.

Key words: multi-agent system, auction mechanism design, online video advertisement, budget constraints, non-linear marginal valuation