Optimal auctions for correlated buyers with sampling

Hu Fu, Nima Haghpanah, Jason D Hartline, Robert Kleinberg

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

7 Scopus citations

Abstract

Crémer and McLean [1985] showed that, when buyers' valuations are drawn from a correlated distribution, an auction with full knowledge on the distribution can extract the full social surplus. We study whether this phenomenon persists when the auctioneer has only incomplete knowledge of the distribution, represented by a finite family of candidate distributions, and has sample access to the real distribution. We show that the naive approach which uses samples to distinguish candidate distributions may fail, whereas an extended version of the Crémer-McLean auction simultaneously extracts full social surplus under each candidate distribution. With an algebraic argument, we give a tight bound on the number of samples needed by this auction, which is the difference between the number of candidate distributions and the dimension of the linear space they span.

Original languageEnglish (US)
Title of host publicationEC 2014 - Proceedings of the 15th ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery
Pages23-35
Number of pages13
ISBN (Print)9781450325653
DOIs
StatePublished - 2014
Event15th ACM Conference on Economics and Computation, EC 2014 - Palo Alto, CA, United States
Duration: Jun 8 2014Jun 12 2014

Publication series

NameEC 2014 - Proceedings of the 15th ACM Conference on Economics and Computation

Other

Other15th ACM Conference on Economics and Computation, EC 2014
CountryUnited States
CityPalo Alto, CA
Period6/8/146/12/14

Keywords

  • correlated value distributions
  • revenue maximization
  • sample access

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'Optimal auctions for correlated buyers with sampling'. Together they form a unique fingerprint.

Cite this