TY - GEN
T1 - Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items
AU - Beyhaghi, Hedyeh
AU - Weinberg, S. Matthew
N1 - 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 -