Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items

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 9nm‾‾‾√. When n≤m, the first bound is optimal up to constant factors, even when the items are i.i.d. and regular. When n≥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≥m regime, the competition complexity of n bidders with additive valuations over even 2 i.i.d. regular items is indeed ω(1).
Our main technical contribution is a reduction from analyzing the Eden et al. benchmark to proving stochastic dominance of certain random variables.