CaltechAUTHORS
  A Caltech Library Service

Third-Party Data Providers Ruin Simple Mechanisms

Cai, Yang and Echenique, Federico and Fu, Hu and Ligett, Katrina and Wierman, Adam and Ziani, Juba (2018) Third-Party Data Providers Ruin Simple Mechanisms. . (Unpublished) http://resolver.caltech.edu/CaltechAUTHORS:20190626-155536214

[img] PDF - Submitted Version
See Usage Policy.

232Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20190626-155536214

Abstract

This paper studies the revenue of simple mechanisms in settings where a third-party data provider is present. When no data provider is present, it is known that simple mechanisms achieve a constant fraction of the revenue of optimal mechanisms. The results in this paper demonstrate that this is no longer true in the presence of a third party data provider who can provide the bidder with a signal that is correlated with the item type. Specifically, we show that even with a single seller, a single bidder, and a single item of uncertain type for sale, pricing each item-type separately (the analog of item pricing for multi-item auctions) and bundling all item-types under a single price (the analog of grand bundling) can both simultaneously be a logarithmic factor worse than the optimal revenue. Further, in the presence of a data provider, item-type partitioning mechanisms---a more general class of mechanisms which divide item-types into disjoint groups and offer prices for each group---still cannot achieve within a log log factor of the optimal revenue.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1802.07407arXivDiscussion Paper
ORCID:
AuthorORCID
Ligett, Katrina0000-0003-2780-6656
Additional Information:Cai thanks the NSERC for its support through the Discovery grant RGPIN-2015-06127 and FRQNT for its support through the grant 2017-NC-198956. Echenique thanks the National Science Foundation for its support through grants SES-1558757 and CNS-1518941. Fu thanks the NSERC for its support through Discovery grant RGPAS-2017-507934 and Accelerator grant RGPAS-2017-507934. Ligett’s work was supported in part by NSF grants CNS-1254169 and CNS-1518941, US-Israel Binational Science Foundation grant 2012348, Israeli Science Foundation (ISF) grant 1044/16, a subcontract on the DARPA Brandeis Project, and the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Directorate (INCD) in the Prime Ministers Office. Wierman thanks the National Science Foundation for its support through grants NSF AitF-1637598, CNS-1518941, as well as the Linde Institute of Economic and Management Science at Caltech. Ziani thanks the National Science Foundation for its support through grants CNS-1331343 and CNS-1518941, and the US-Israel Binational Science Foundation through grant 20122348. We thank Noam Nisan for extremely useful comments and discussions.
Funders:
Funding AgencyGrant Number
Natural Sciences and Engineering Research Council of Canada (NSERC)RGPIN-2015-06127
Fonds de recherche du Québec – Nature et technologies (FRQNT)2017-NC-198956
NSFSES-1558757
NSFCNS-1518941
Natural Sciences and Engineering Research Council of Canada (NSERC)RGPAS-2017-507934
NSFCNS-1254169
NSFCNS-1518941
Binational Science Foundation (USA-Israel)2012348
Israel Science Foundation1044/16
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Hebrew University of JerusalemUNSPECIFIED
Israel National Cyber Directorate (INCD)UNSPECIFIED
NSFAitF-1637598
Linde Institute of Economic and Management ScienceUNSPECIFIED
NSFCNS-1331343
Record Number:CaltechAUTHORS:20190626-155536214
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20190626-155536214
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96757
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:27 Jun 2019 01:49
Last Modified:27 Jun 2019 01:49

Repository Staff Only: item control page