Competition Complexity in Multi-Item Auctions: Beyond VCG and Regularity

Hedyeh Beyhaghi, Linda Cai, Yiding Feng, Yingkai Li and S. Matthew Weinberg

Papers from arXiv.org

Abstract: We quantify the value of the monopoly's bargaining power in terms of competition complexity--that is, the number of additional bidders the monopoly must attract in simple auctions to match the expected revenue of the optimal mechanisms (c.f., Bulow and Klemperer, 1996, Eden et al., 2017)--within the setting of multi-item auctions. We show that for simple auctions that sell items separately, the competition complexity is $\Theta(\frac{n}{\alpha})$ in an environment with $n$ original bidders under the slightly stronger assumption of $\alpha$-strong regularity, in contrast to the standard regularity assumption in the literature, which requires $\Omega(n \cdot \ln \frac{m}{n})$ additional bidders (Feldman et al., 2018). This significantly reduces the value of learning the distribution to design the optimal mechanisms, especially in large markets with many items for sale. For simple auctions that sell items as a grand bundle, we establish a constant competition complexity bound in a single-bidder environment when the number of items is small or when the value distribution has a monotone hazard rate. Some of our competition complexity results also hold when we compete against the first best benchmark (i.e., optimal social welfare).

Date: 2025-06
New Economics Papers: this item is included in nep-com, nep-des and nep-mic
References: Add references at CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2506.09291 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2506.09291

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().