关键词: 多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