  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
{\em 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 {\em full Bulow-Klemperer} results in
{\em 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 {\em 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.
