  The competition complexity of an auction setting is the number of additional
bidders needed such that the simple mechanism of selling items separately (with
additional bidders) achieves greater revenue than the optimal but complex
(randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the
additional bidders. Our main result settles the competition complexity of $n$
bidders with additive values over $m < n$ independent items at
$\Theta(\sqrt{nm})$. The $O(\sqrt{nm})$ upper bound is due to [BW19], and our
main result improves the prior lower bound of $\Omega(\ln n)$ to
$\Omega(\sqrt{nm})$.
  Our main result follows from an explicit construction of a Bayesian IC
auction for $n$ bidders with additive values over $m<n$ independent items drawn
from the Equal Revenue curve truncated at $\sqrt{nm}$ ($\mathcal{ER}_{\le
\sqrt{nm}}$), which achieves revenue that exceeds
$\text{SRev}_{n+\sqrt{nm}}(\mathcal{ER}_{\le \sqrt{nm}}^m)$.
  Along the way, we show that the competition complexity of $n$ bidders with
additive values over $m$ independent items is exactly equal to the minimum $c$
such that $\text{SRev}_{n+c}(\mathcal{ER}_{\le p}^m) \geq
\text{Rev}_n(\mathcal{ER}_{\le p}^m)$ for all $p$ (that is, some truncated
Equal Revenue witnesses the worst-case competition complexity). Interestingly,
we also show that the untruncated Equal Revenue curve does not witness the
worst-case competition complexity when $n > m$: $\text{SRev}_n(\mathcal{ER}^m)
= nm+O_m(\ln (n)) \leq \text{SRev}_{n+O_m(\ln (n))}(\mathcal{ER}^m)$, and
therefore our result can only follow by considering all possible truncations.
