---
abstract: |
    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 [@bulow1996auctions], states that the Competition Complexity of VCG, in the case of $n$ i.i.d. buyers and a single item, is $1$. In other words, it is better to invest in recruiting one extra buyer and run a second price auction than to invest in learning *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 problem: a monopolist is auctioning off $\days$ items in $\days$ consecutive stages to $n$ interested buyers. A buyer realizes her value for item $k$ in the beginning of stage $k$. *How many additional buyers are necessary and sufficient for a second price auction at each stage to extract revenue at least that of the optimal dynamic auction?* 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. This assumption can be relaxed if one settles for independent stages. 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*. For example, under the same mild assumptions on the stage distributions we prove that one extra buyer suffices for a $\frac{1}{e}$-approximation. 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 @cai2016 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.
author:
- |
    Siqi Liu\
    UC Berkeley\
    <sliu18@berkeley.edu>
- |
    Christos-Alexandros Psomas\
    Carnegie Mellon University\
    <cpsomas@cs.cmu.edu>
bibliography:
- 'refs.bib'
title: On the Competition Complexity of Dynamic Mechanism Design
---


