  The Competition Complexity of an auction measures how much competition is
needed for the revenue of a simple auction to surpass the optimal revenue. A
classic result from auction theory by Bulow and Klemperer [9], states that the
Competition Complexity of VCG, in the case of n i.i.d. buyers and a single
item, is 1, i.e., it is better to recruit one extra buyer and run a second
price auction than to learn exactly the buyers' underlying distribution and run
the revenue-maximizing auction tailored to this distribution.
  In this paper we study the Competition Complexity of dynamic auctions.
Consider the following setting: a monopolist is auctioning off m items in m
consecutive stages to n interested buyers. A buyer realizes her value for item
k in the beginning of stage k. We prove that the Competition Complexity of
dynamic auctions is at most 3n, and at least linear in n, even when the buyers'
values are correlated across stages, under a monotone hazard rate assumption on
the stage (marginal) distributions. We also prove results on the number of
additional buyers necessary for VCG at every stage to be an
{\alpha}-approximation of the optimal revenue; we term this number the
{\alpha}-approximate Competition Complexity. As a corollary we provide the
first results on prior-independent dynamic auctions. This is, to the best of
our knowledge, the first non-trivial positive guarantees for simple ex-post IR
dynamic auctions for correlated stages.
  A key step towards proving bounds on the Competition Complexity is getting a
good benchmark/upper bound to the optimal revenue. To this end, we extend the
recent duality framework of Cai et al. [12] to dynamic settings. As an aside to
our approach we obtain a revenue non-monotonicity lemma for dynamic auctions,
which may be of independent interest.
