ABSTRACT
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 relative strength of simple versus complex mechanisms, 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. This also gives the first simple mechanism that achieves constant fraction optimal revenue for such multi-buyer multi-item auctions. 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 + ∫0mr(1 − F(x)n)dx)) where r = supx≥0 x(1 − F(x)n) and m = ļk/nr; this revenue is achievable by a simple mechanism called 2nd-Price Bundling. All our results apply to arbitrary distributions, regular or irregular.
Recommendations
Dominant-Strategy versus Bayesian Multi-item Auctions: Maximum Revenue Determination and Comparison
EC '17: Proceedings of the 2017 ACM Conference on Economics and ComputationWe address two related unanswered questions in maximum revenue multi-item auctions. Is dominant-strategy implementation equivalent to the semantically less stringent Bayesian one (as in the case of Myerson's 1-item auction)? Can one find explicit ...
Bidder Support in Multi-item Multi-unit Continuous Combinatorial Auctions: A Unifying Theoretical Framework
Combinatorial auctions have seen limited applications in large-scale consumer-oriented marketplaces, partly due to the substantial complexity to keep track of auction status and formulate informed bidding strategies. We study the bidder support problem ...
Despite known advantages of combinatorial auctions, wide adoption of this allocation mechanism, especially in consumer-oriented marketplaces, is limited partially by the lack of effective bidder support information that can assist bidders to make bidding ...
Simultaneous single-item auctions
WINE'12: Proceedings of the 8th international conference on Internet and Network EconomicsIn a combinatorial auction (CA) with item bidding, several goods are sold simultaneously via single-item auctions. We study how the equilibrium performance of such an auction depends on the choice of the underlying single-item auction. We provide a ...
Comments