Prior-free multi-unit auctions with ordered bidders
Prior-free multi-unit auctions with ordered bidders
复制标题
DOI：
10.1016/j.tcs.2020.09.030
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Sayan Bhattacharya;E. Koutsoupias;Janardhan Kulkarni;S. Leonardi;Tim Roughgarden;Xiaoming Xu
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;E. Koutsoupias;Janardhan Kulkarni;S. Leonardi;Tim Roughgarden;Xiaoming Xu
无先验拍卖是一种稳健的拍卖，它假定竞标者的估值没有分布，并提供最坏情况（逐个输入）的近似保证。与此主题的先前工作相反，我们追求具有非相同投标人的良好无先验拍卖。只有当有关竞标者不对称的充分定性信息公开时，无先验拍卖才能近似地为非相同竞标者提供有意义的基准。我们认为，在数字商品拍卖中，卖家知道竞标者的总顺序，在某种意义上，早期的竞标者被认为有更高的估值。我们使用Hartline和Roughgarden （STOC'08）的框架来定义一个适当的收入基准：使用投标人订单中不增加的价格，并以第二高的出价为上限，可以从投标向量中获得的最大收入。这种单调价格基准总是与众所周知的固定价格基准F(2)一样大，因此设计具有良好近似保证的无先验拍卖只会更加困难。通过设计，近似于单调价格基准的拍卖满足了一个非常强的保证：特别是，对于基本上每个贝叶斯环境来说，它同时是接近最优的，在这种环境中，竞标者的估值分布具有不增加的垄断价格，或者每个竞标者的分布随机地支配下一个竞标者的分布。即使没有对竞标者的估值进行分配，这样的拍卖仍然提供了一种可量化的投入对投入的绩效保证。在本文中，我们设计了一个简单的O(1)竞争的数字商品无先验拍卖。我们还将单调价格基准和我们的O(1)竞争性无先验拍卖扩展到供应有限的多单元设置。
Prior-free auctions are robust auctions that assume no distribution over bidders' valuations and provide worst-case (input-by-input) approximation guarantees. In contrast to previous work on this topic, we pursue good prior-free auctions with non-identical bidders. Prior-free auctions can approximate meaningful benchmarks for non-identical bidders only when sufficient qualitative information about the bidder asymmetry is publicly known. We consider digital goods auctions where there is a total ordering of the bidders that is known to the seller, where earlier bidders are in some sense thought to have higher valuations. We use the framework of Hartline and Roughgarden (STOC'08) to define an appropriate revenue benchmark: the maximum revenue that can be obtained from a bid vector using prices that are nonincreasing in the bidder ordering and bounded above by the second-highest bid. This monotone-price benchmark is always as large as the well-known fixed-price benchmark F (2), so designing prior-free auctions with good approximation guarantees is only harder. By design, an auction that approximates the monotone-price benchmark satisfies a very strong guarantee: it is, in particular, simultaneously near-optimal for essentially every Bayesian environment in which bidders' valuation distributions have nonincreasing monopoly prices, or in which the distribution of each bidder stochastically dominates that of the next. Even when there is no distribution over bidders' valuations, such an auction still provides a quantifiable input-by-input performance guarantee. In this paper, we design a simple O (1)-competitive prior-free auction for digital goods with ordered bidders. We also extend the monotone-price benchmark and our O (1)-competitive prior-free auction to multi-unit settings with limited supply.