论文标题
价格水平数量有限和批处理先知不等式的降价拍卖
Descending Price Auctions with Bounded Number of Price Levels and Batched Prophet Inequality
论文作者
论文摘要
我们认为，出售$ M $ M $单位的单位需求的价格下降拍卖。买家在拍卖时钟可以使用的价格水平数量上有$ k $的外源性。拍卖师的问题是选择价格水平$ p_1> p_2> \ cdots> p_ {k} $用于拍卖时钟，以使拍卖预期收入最大化。价格水平是在拍卖之前宣布的。我们将这个问题减少到了先知不平等的新变体中，我们称之为\ emph {批处理的先知不平等}，其中决策者选择$ k $（降低）阈值，然后顺序收集奖励（最多$ m $），这些奖励是在随机均匀均匀均匀均匀的阈值之上的。对于$ m = 1 $的特殊情况（即出售单个商品），我们表明，以$ k $的价格水平的下降拍卖可实现$ 1-1/e^k $的无限制（无$ K $）最佳收入。这意味着只有4个价格水平的下降拍卖可以获得最佳收入的98％以上。然后，我们将结果扩展到$> 1 $，并根据拍卖的竞争比率提供了封闭形式的限制，这是单位$ m $和价格水平$ k $的数量的函数。
We consider descending price auctions for selling $m$ units of a good to unit demand i.i.d. buyers where there is an exogenous bound of $k$ on the number of price levels the auction clock can take. The auctioneer's problem is to choose price levels $p_1 > p_2 > \cdots > p_{k}$ for the auction clock such that auction expected revenue is maximized. The prices levels are announced prior to the auction. We reduce this problem to a new variant of prophet inequality, which we call \emph{batched prophet inequality}, where a decision-maker chooses $k$ (decreasing) thresholds and then sequentially collects rewards (up to $m$) that are above the thresholds with ties broken uniformly at random. For the special case of $m=1$ (i.e., selling a single item), we show that the resulting descending auction with $k$ price levels achieves $1- 1/e^k$ of the unrestricted (without the bound of $k$) optimal revenue. That means a descending auction with just 4 price levels can achieve more than 98\% of the optimal revenue. We then extend our results for $m>1$ and provide a closed-form bound on the competitive ratio of our auction as a function of the number of units $m$ and the number of price levels $k$.
