An online mechanism for ad slot reservations with cancellations
An online mechanism for ad slot reservations with cancellations
复制标题
DOI：
10.1137/1.9781611973068.137
复制
发表时间：
2009-01
期刊：
影响因子：
--
通讯作者：
Florin Constantin;J. Feldman;S. Muthukrishnan;Martin Pál
中科院分区：
文献类型：
--
作者：
Florin Constantin;J. Feldman;S. Muthukrishnan;Martin Pál
许多广告商(投标人)使用互联网系统在出版商的网页上或在广播、电视和新闻纸等传统媒体上购买展示广告。他们寻求一种简单的在线机制来提前预订广告时段。另一方面，媒体出版商(销售商)代表着一个庞大而多样的库存，他们也寻求自动的在线定价和分配这种预订的机制。我们提出并研究了一种简单的提前拍卖广告时段预订的模型。卖家将在将来的某个点T处显示一组槽。直到T，投标者按顺序到达，并对他们感兴趣的空位出价。卖家必须立即决定是否给予预订。我们的模型允许卖家在任何时候取消先前所做的任何预订，在这种情况下，预订的持有者将产生相当于其预订价值的一小部分的效用损失，并可能从卖家那里获得取消费用。我们的主要结果是该模型中的在线分配和定价机制具有许多理想的博弈论性质。这是个人理性的。获胜者有诚实的动机，竞价的真正价值决定了任何较低的出价。此外，它还限制了参与游戏的投机者获得取消费用的收益。此外，该机制还具有优化保证。它的收入在Vickrey-Clarke-Groves(VCG)机制的后验收入的恒定分数内，后者被认为是真实的(在线下情况下)。我们的机制的效率在后验最优解的恒定分数内。如果效率还考虑了预订被取消的投标人的效用损失，我们证明了我们的机制(对于适当的参数值)与任何确定性在线算法的竞争比的上界相匹配。我们机制的技术核心是在线加权二部匹配问题的一个变体，其中不像以前的变体中随机边到达或边权重的界限，我们可以撤销先前承诺的边。我们的结果没有对投标人的到达顺序或价值分布做出任何假设。如果我们用拟阵的元素替换项目，用独立的集合匹配，或者如果所有投标人都对一组项目具有附加值，它们仍然成立。
Many advertisers (bidders) use Internet systems to buy display advertisements on publishers' webpages or on traditional media such as radio, TV and newsprint. They seek a simple, online mechanism to reserve ad slots in advance. On the other hand, media publishers (sellers) represent a vast and varying inventory, and they too seek automatic, online mechanisms for pricing and allocating such reservations. We propose and study a simple model for auctioning such ad slot reservations in advance. A seller will display a set of slots at some point T in the future. Until T, bidders arrive sequentially and place a bid on the slots they are interested in. The seller must decide immediately whether or not to grant a reservation. Our model allows the seller to cancel at any time any reservation made earlier, in which case the holder of the reservation incurs a utility loss amounting to a fraction of her value for the reservation and may also receive a cancellation fee from the seller. Our main result is an online mechanism for allocation and pricing in this model with many desirable game-theoretic properties. It is individually rational. Winners have an incentive to be honest and bidding one's true value dominates any lower bid. Further, it bounds the earnings of speculators who are in the game to obtain the cancellation fees. The mechanism in addition has optimization guarantees. Its revenue is within a constant fraction of the a posteriori revenue of the Vickrey-Clarke-Groves (VCG) mechanism which is known to be truthful (in the offline case). Our mechanism's efficiency is within a constant fraction of the a posteriori optimally efficient solution. If efficiency also takes into account the utility losses of bidders whose reservation was canceled, we show that our mechanism matches (for appropriate values of the parameters) an upper bound on the competitive ratio of any deterministic online algorithm. Our mechanism's technical core is a variant of the online weighted bipartite matching problem where unlike prior variants in which one randomizes edge arrivals or bounds edge weights, we may revoke previously committed edges. Our results make no assumptions about bidders' arrival order or value distribution. They still hold if we replace items with elements of a matroid and matchings with independent sets, or if all bidders have additive value for a set of items.