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

Hedyeh Beyhaghi, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages686-696
Number of pages11
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period6/23/196/26/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Auctions
  • Duality
  • Multi-dimensional mechanism design
  • Stochastic dominance

Fingerprint Dive into the research topics of 'Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items'. Together they form a unique fingerprint.

  • Cite this

    Beyhaghi, H., & Weinberg, S. M. (2019). Optimal (and benchmark-optimal) competition complexity for additive buyers over independent items. In M. Charikar, & E. Cohen (Eds.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (pp. 686-696). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3313276.3316405