The Competition Complexity of Auctions: Bulow-Klemperer Results for Multi-Dimensional Bidders

A seminal result of Bulow and Klemperer (1996) shows the power of competition for extracting revenue: When selling a single item to bidders with i.i.d. values, the welfare-maximizing VCG mechanism (in this case, a simple second price-auction) with one additional bidder extracts at least as much revenue as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a prior-independent mechanism, in which the seller needs no information about the values’ distribution, and yet with an extra bidder it performs better than any mechanism tailored to the distribution.

Recent years have seen great progress in extending our understanding of revenue-maximizing mechanisms to multiple items. These extensions have so far focused almost exclusively on approximation results obtained by prior-dependent mechanisms. I will show Bulow-Klemperer-style results for multi-dimensional bidders, in which the VCG mechanism surpasses the revenue of the (unknown) optimal mechanism by recruiting additional bidders. We term the number of additional bidders needed “the competition complexity” of the auction environment, and give several upper and lower bounds for different environments.

Based on recent joint work with Alon Eden, Michal Feldman, Ophir Friedler and Matt Weinberg, and on previous joint work with Tim Roughgarden and Qiqi Yan.