TY - GEN

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

AU - Beyhaghi, Hedyeh

AU - Weinberg, S. Matthew

N1 - Funding Information:
*Supported by NSF CCF-1717899.
Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.

PY - 2019/6/23

Y1 - 2019/6/23

N2 - 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 bidders with additive valuations over independent items is at most (ln(1 + /) + 2), and also at most 9 . When ≤ , the first bound is optimal up to constant factors, even when the items are i.i.d. and regular. When ≥ , the second bound is optimal for the benchmark introduced by Eden et al.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 ≥ regime, the competition complexity of bidders with additive valuations over even 2 i.i.d. regular items is indeed (1). Our main technical contribution is a reduction from analyzing the Eden et al. benchmark to proving stochastic dominance of certain random variables.

AB - 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 bidders with additive valuations over independent items is at most (ln(1 + /) + 2), and also at most 9 . When ≤ , the first bound is optimal up to constant factors, even when the items are i.i.d. and regular. When ≥ , the second bound is optimal for the benchmark introduced by Eden et al.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 ≥ regime, the competition complexity of bidders with additive valuations over even 2 i.i.d. regular items is indeed (1). Our main technical contribution is a reduction from analyzing the Eden et al. benchmark to proving stochastic dominance of certain random variables.

KW - Auctions

KW - Duality

KW - Multi-dimensional mechanism design

KW - Stochastic dominance

UR - http://www.scopus.com/inward/record.url?scp=85068758473&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068758473&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316405

DO - 10.1145/3313276.3316405

M3 - Conference contribution

AN - SCOPUS:85068758473

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 686

EP - 696

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

Y2 - 23 June 2019 through 26 June 2019

ER -