论文标题
自动铸件中的拍卖设计：随机化提高了VCG以外的效率
Auction Design in an Auto-bidding Setting: Randomization Improves Efficiency Beyond VCG
论文作者
论文摘要
自动投标是在线广告领域中越来越重要的领域。我们研究在自动铸造环境中设计拍卖的问题，目的是在系统平衡处最大化福利。先前的结果表明，VCG下的无政府状态（POA）价格为2，即使有两个投标人也很紧。这就提出了一个有趣的问题，即VCG在这种情况下是否产生最佳效率，或者是否可以改善POA。我们提出了一个先前的随机拍卖，其中POA约为。 1.896对于两个竞标者来说，证明在这种情况下，一个竞标者可以严格地实现效率，而在这种情况下，效率比VCG的效率更好。由于投标人的数量增加，我们还为问题提供了一个明显的不可能结果 - 我们表明，随着每个查询的竞标数增加，没有（随机的）匿名真实拍卖可以严格地比2个渐近的POA更好。虽然在先前的工作中表明，如果允许拍卖除了投标人的出价之外，我们可以在询问查询中使用竞标者的价值，但我们注意到，我们注意到我们的随机拍卖是没有事先的，并且不使用此类其他信息；我们的不可能结果也适用于没有其他价值信息的拍卖。
Auto-bidding is an area of increasing importance in the domain of online advertising. We study the problem of designing auctions in an auto-bidding setting with the goal of maximizing welfare at system equilibrium. Previous results showed that the price of anarchy (PoA) under VCG is 2 and also that this is tight even with two bidders. This raises an interesting question as to whether VCG yields the best efficiency in this setting, or whether the PoA can be improved upon. We present a prior-free randomized auction in which the PoA is approx. 1.896 for the case of two bidders, proving that one can achieve an efficiency strictly better than that under VCG in this setting. We also provide a stark impossibility result for the problem in general as the number of bidders increases -- we show that no (randomized) anonymous truthful auction can have a PoA strictly better than 2 asymptotically as the number of bidders per query increases. While it was shown in previous work that one can improve on the PoA of 2 if the auction is allowed to use the bidder's values for the queries in addition to the bidder's bids, we note that our randomized auction is prior-free and does not use such additional information; our impossibility result also applies to auctions without additional value information.
