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

DOI10.1145/3313276.3316405MaRDI QIDQ5212809zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1812.01794, https://dl.acm.org/doi/pdf/10.1145/3313276.3316405?download=true

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)

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.

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

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)