Skip to main content

Smoothed Analysis of Multi-Item Auctions with Correlated Values

Author(s): Psomas, Alexandros; Schvartzman, Ariel; Weinberg, S Matthew

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorPsomas, Alexandros-
dc.contributor.authorSchvartzman, Ariel-
dc.contributor.authorWeinberg, S Matthew-
dc.identifier.citationPsomas, Alexandros, Ariel Schvartzman, and S. Matthew Weinberg. "Smoothed Analysis of Multi-Item Auctions with Correlated Values." In ACM Conference on Economics and Computation (2019): pp. 417-418. doi:10.1145/3328526.3329563en_US
dc.description.abstractConsider a seller with m 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. 2015, Hart and Nisan 2012), even when m=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 above 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.en_US
dc.format.extent417 - 418en_US
dc.relation.ispartofACM Conference on Economics and Computationen_US
dc.rightsFinal published version. Article is made available in OAR by the publisher's permission or policy.en_US
dc.titleSmoothed Analysis of Multi-Item Auctions with Correlated Valuesen_US
dc.typeConference Articleen_US

Files in This Item:
File Description SizeFormat 
SmoothedAnalysisMultiItemAuctionsCorrelatedValues.pdf972.07 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.