On the Competition Complexity of Dynamic Mechanism Design

Understand

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.