Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items

DOI10.1145/3313276.3316405zbMATH Open1437.91214arXiv1812.01794OpenAlexW2902767316MaRDI QIDQ5212809FDOQ5212809

Authors: Hedyeh Beyhaghi, S. Matthew Weinberg 

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: The Competition Complexity of an auction setting refers to the number of additional bidders necessary in order for the (deterministic, prior-independent, dominant strategy truthful) Vickrey-Clarke-Groves mechanism to achieve greater revenue than the (randomized, prior-dependent, Bayesian-truthful) optimal mechanism without the additional bidders. We prove that the competition complexity of $n$ bidders with additive valuations over $m$ independent items is at most $n(ln(1+m/n)+2)$, and also at most $9sqrtnm$. When $nleqm$, the first bound is optimal up to constant factors, even when the items are i.i.d. and regular. When $ngeqm$, the second bound is optimal for the benchmark introduced in [EFFTW17a] up to constant factors, even when the items are i.i.d. and regular. We further show that, while the Eden et al. benchmark is not necessarily tight in the $ngeqm$ regime, the competition complexity of $n$ bidders with additive valuations over even $2$ i.i.d. regular items is indeed $omega(1)$. Our main technical contribution is a reduction from analyzing the Eden et al. benchmark to proving stochastic dominance of certain random variables.

Full work available at URL: https://arxiv.org/abs/1812.01794

Recommendations

• On the competition complexity of dynamic mechanism design
• Optimal competitive auctions
• The complexity of optimal mechanism design
• An \(n\)-to-\(1\) bidder reduction for multi-item auctions and its applications
• On the complexity of simple and optimal deterministic mechanisms for an additive buyer

zbMATH Keywords

stochastic dominancedualityauctionsmulti-dimensional mechanism design

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Auctions, bargaining, bidding and selling, and other market models (91B26) Algorithmic game theory and complexity (91A68) Mechanism design theory (91B03)

Cited In (5)

• On symmetries in multi-dimensional mechanism design
• Interview hoarding
• Pandora's problem with nonobligatory inspection: optimal structure and a PTAS
• On the competition complexity of dynamic mechanism design
• A Simple and Approximately Optimal Mechanism for an Additive Buyer

This page was built for publication: Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212809)