An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications

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 it 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 it dominant strategy incentive compatibility (DSIC) is shown to be at least a constant fraction of that achievable in it 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 Theta(k(r+int0mr (1-F(x)n) ud x)) where r= supx≥ 0 , x(1 - F(x)n) and m=lceil k/nrceil; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.