Smoothed analysis of multi-item auctions with correlated values?

Alexandros Psomas, Ariel Schvartzman, S. Matthew Weinberg

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

2 Scopus citations

Abstract

Consider a seller withm heterogeneous items for sale to a single additive buyer whose values for the items are arbitrarily correlated. It was previously shown that, in such settings, distributions exist for which the seller's optimal revenue is infinite, but the best "simple" mechanism achieves revenue at most one (Briest et al. [2], Hart and Nisan [6]), even whenm = 2. This result has long served as a cautionary tale discouraging the study of multi-item auctions without some notion of "independent items". In this work we initiate a smoothed analysis of such multi-item auction settings. We consider a buyer whose item values are drawn from an arbitrarily correlated multi-dimensional distribution then randomly perturbed with magnitude δ under several natural perturbation models. On one hand, we prove that the [2, 6] construction is surprisingly robust to certain natural perturbations of this form, and the infinite gap remains. On the other hand, we provide a smoothed model such that the approximation guarantee of simple mechanisms is smoothed-finite. We show that when the perturbation has magnitude δ, pricing only the grand bundle guarantees an O(1/δ)-approximation to the optimal revenue. That is, no matter the (worst-case) initially correlated distribution, these tiny perturbations suffice to bring the gap down from infinite to finite. We further show that the same guarantees hold when n buyers have values drawn from an arbitrarily correlated mn-dimensional distribution (without any dependence on n). Taken together, these analyses further pin down key properties of correlated distributions that result in large gaps between simplicity and optimality.

Original languageEnglish (US)
Title of host publicationACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages417-418
Number of pages2
ISBN (Electronic)9781450367929
DOIs
StatePublished - Jun 17 2019
Event20th ACM Conference on Economics and Computation, EC 2019 - Phoenix, United States
Duration: Jun 24 2019Jun 28 2019

Publication series

NameACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation

Conference

Conference20th ACM Conference on Economics and Computation, EC 2019
CountryUnited States
CityPhoenix
Period6/24/196/28/19

All Science Journal Classification (ASJC) codes

  • Economics and Econometrics
  • Statistics and Probability
  • Computer Science (miscellaneous)
  • Computational Mathematics
  • Marketing

Keywords

  • Approximate mechanism design
  • Correlated distributions
  • Multi-item mechanism design
  • Smoothed analysis

Fingerprint Dive into the research topics of 'Smoothed analysis of multi-item auctions with correlated values?'. Together they form a unique fingerprint.

  • Cite this

    Psomas, A., Schvartzman, A., & Weinberg, S. M. (2019). Smoothed analysis of multi-item auctions with correlated values? In ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation (pp. 417-418). (ACM EC 2019 - Proceedings of the 2019 ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3328526.3329563