  The Competition Complexity of an auction setting refers to the number of
additional bidders necessary in order for the (deterministic,
prior-independent, dominant strategy truthful) Vickrey-Clarke-Groves mechanism
to achieve greater revenue than the (randomized, prior-dependent,
Bayesian-truthful) optimal mechanism without the additional bidders.
  We prove that the competition complexity of $n$ bidders with additive
valuations over $m$ independent items is at most $n(\ln(1+m/n)+2)$, and also at
most $9\sqrt{nm}$. When $n \leq m$, the first bound is optimal up to constant
factors, even when the items are i.i.d. and regular. When $n \geq m$, the
second bound is optimal for the benchmark introduced in [EFFTW17a] up to
constant factors, even when the items are i.i.d. and regular. We further show
that, while the Eden et al. benchmark is not necessarily tight in the $n \geq
m$ regime, the competition complexity of $n$ bidders with additive valuations
over even $2$ i.i.d. regular items is indeed $\omega(1)$.
  Our main technical contribution is a reduction from analyzing the Eden et al.
benchmark to proving stochastic dominance of certain random variables.
