Optimal (and Benchmark-Optimal) Competition Complexity for Additive Buyers over Independent Items
share
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((1+m/n)+2), and also at most 9√(nm). 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.
READ FULL TEXT