Skip to main content

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

Author(s): Eden, Alon; Feldman, Michal; Friedler, Ophir; Talgam-Cohen, Inbal; Weinberg, S Matthew

To refer to this page use:
Abstract: A seminal result of Bulow and Klemperer [1989] demonstrates the power of competition for extracting revenue: when selling a single item to n bidders whose values are drawn i.i.d. from a regular distribution, the simple welfare-maximizing VCG mechanism (in this case, a second price-auction) with one additional bidder extracts at least as much revenue in expectation as the optimal mechanism. The beauty of this theorem stems from the fact that VCG is a prior-independent mechanism, where the seller possesses no information about the distribution, and yet, by recruiting one additional bidder it performs better than any prior-dependent mechanism tailored exactly to the distribution at hand (without the additional bidder). In this work, we establish the first full Bulow-Klemperer results in multi-dimensional environments, proving that by recruiting additional bidders, the revenue of the VCG mechanism surpasses that of the optimal (possibly randomized, Bayesian incentive compatible) mechanism. For a given environment with i.i.d. bidders, we term the number of additional bidders needed to achieve this guarantee the environment's competition complexity. Using the recent duality-based framework of Cai et al. [2016] for reasoning about optimal revenue, we show that the competition complexity of n bidders with additive valuations over m independent, regular items is at most n+2m-2 and at least log(m). We extend our results to bidders with additive valuations subject to downward-closed constraints, showing that these significantly more general valuations increase the competition complexity by at most an additive m-1 factor. We further improve this bound for the special case of matroid constraints, and provide additional extensions as well.
Publication Date: Jun-2017
Citation: Eden, Alon, Michal Feldman, Ophir Friedler, Inbal Talgam-Cohen, and S. Matthew Weinberg. "The Competition Complexity of Auctions: A Bulow-Klemperer Result for Multi-Dimensional Bidders." In ACM Conference on Economics and Computation (2017): pp. 343. doi:10.1145/3033274.3085115
DOI: 10.1145/3033274.3085115
Pages: 343
Type of Material: Conference Article
Journal/Proceeding Title: ACM Conference on Economics and Computation
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.