Multi-Unit Bayesian Auction with Demand or Budget Constraints
Multi-Unit Bayesian Auction with Demand or Budget Constraints
复制标题
具有需求或预算约束的多单位贝叶斯拍卖
DOI：
10.1111/coin.12056
复制
发表时间：
2014
影响因子：
2.8
通讯作者：
Deng X
中科院分区：
文献类型：
--
作者：
Deng X
我们考虑了多单位拍卖中的收益最大化问题，其中物品以其相对价值区分；任何一对物品对所有买家的价值比率都是相同的。在收入最大化问题的研究中很常见，我们假设买家的估值是从公开的已知分布中得出的，他们对多个物品具有相加的估值。我们的问题很好地受到了赞助搜索拍卖的推动，这些拍卖为谷歌和雅虎赚钱！在实践中。在这次拍卖中，每个广告商出价一定数量，以争夺网页上的广告位。每个广告时段的价值与其点击率相对应，每个买家都有自己的每次点击估值，这是她的私人信息。显然，战略竞购者可能会出价与其真实估值不同的金额，以提高她的效用。我们的目标是设计真实的机制，避免这种误报。我们开发了最优(具有最大收益)的真实拍卖，适用于放松需求模型(其中每个买家都想要最少的物品)和硬需求模型(其中买家想要的是最少的物品)。我们还发现，当买家受到预算限制时，拍卖总是保证至少一半的最优拍卖收入。此外，我们设计的所有拍卖都可以高效地计算，也就是在多项式时间内。
We consider the problem of revenue maximization on multi‐unit auctions where items are distinguished by their relative values; any pair of items has the same ratio of values to all buyers. As is common in the study of revenue maximizing problems, we assume that buyers' valuations are drawn from public known distributions and they have additive valuations for multiple items. Our problem is well motivated by sponsored search auctions, which made money for Google and Yahoo! in practice. In this auction, each advertiser bids an amountbito compete for ad slots on a web page. The value of each ad slot corresponds to its click‐through‐rate, and each buyer has her own per‐click valuations, which is her private information. Obviously, a strategic bidder may bid an amount that is different with her true valuation to improve her utility. Our goal is to design truthful mechanisms avoiding this misreporting.We develop the optimal (with maximum revenue) truthful auction for arelaxed demandmodel (where each buyeriwants at mostdiitems) and asharp demandmodel (where buyeriwants exactlydiitems). We also find an auction that always guarantees at least half of the revenue of the optimal auction when the buyers are budget constrained. Moreover, all of the auctions we design can be computed efficiently, that is, in polynomial time.