To refer to this page use:
|Abstract:||A seminal result of Bulow and Klemperer  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.  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.|
|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|
|Type of Material:||Conference Article|
|Journal/Proceeding Title:||ACM Conference on Economics and Computation|
Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.