In this paper, we introduce a novel approach for reducing the k-item n-bidder auction with additive valuation to k-item 1-bidder auctions. This approach, called the Best-Guess reduction, can be applied to address several central questions in optimal revenue auction theory such as the power of randomization, and Bayesian versus dominant-strategy implementations. First, when the items have independent valuation distributions, we present a deterministic mechanism called Deterministic Best-Guess that yields at least a constant fraction of the optimal revenue by any randomized mechanism. Second, if all the nk valuation random variables are independent, the optimal revenue achievable in dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in Bayesian incentive compatibility (BIC). Third, when all the nk values are identically distributed according to a common one-dimensional distribution F , the optimal revenue is shown to be expressible in the closed form Θ(k(r + mr 0 (1 − F (x) n ) dx)) where r = sup x≥0 x(1 − F (x) n ) and m = ⌈k/n⌉; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.
REF introduced a new approach for reducing the k-item n-bidder problem to the k-item 1-bidder setting and gave a deterministic mechanism that yields at least a constant fraction of the optimal revenue for the more general k-item n-bidder setting.
An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
ArXiv
ArXiv
Mathematics Computer Science