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 (2020) Third-Party Data Providers Ruin Simple Mechanisms. ACM SIGMETRICS Performance Evaluation Review, 48 (1). p. 103. ISSN 0163-5999. https://resolver.caltech.edu/CaltechAUTHORS:20200709-084932341

[img] PDF - Published Version
See Usage Policy.

996Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200709-084932341

Abstract

Motivated by the growing prominence of third-party data providers in online marketplaces, this paper studies the impact of the presence of third-party data providers on mechanism design. When no data provider is present, it has been shown that simple mechanisms are "good enough" -they can 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, even with a single seller, a single bidder, and a single item of uncertain type for sale, the strategies of pricing each item-type separately (the analog of item pricing for multiitem 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. Thus, our results highlight that the presence of a data-provider forces the use of more complicated mechanisms in order to achieve a constant fraction of the optimal revenue.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3410048.3410108DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20190626-155536214Related ItemConference Paper
ORCID:
AuthorORCID
Echenique, Federico0000-0002-1567-6770
Ligett, Katrina0000-0003-2780-6656
Ziani, Juba0000-0002-3324-4349
Additional Information:© 2020 Copyright held by the owner/author(s). Cai thanks the Sloan Foundation for its support through a Sloan Foundation Research Fellowship. Part of Cai’s work was done under the support of the NSERC Discovery grant RGPIN-2015-06127 and the FRQNT 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, the United States Air Force and DARPA under contracts FA8750-16-C-0022 and FA8750-19-2-0222, 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, the US-Israel Binational Science Foundation through grant 2012348, and the Linde Graduate Fellowship at Caltech. We thank Noam Nisan for extremely useful comments and discussions.
Funders:
Funding AgencyGrant Number
Alfred P. Sloan FoundationUNSPECIFIED
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
Air Force Office of Scientific Research (AFOSR)FA8750-16-C-0022
Air Force Office of Scientific Research (AFOSR)FA8750-19-2-0222
HUJI Cyber Security Research CenterUNSPECIFIED
Israel National Cyber Directorate (INCD)UNSPECIFIED
NSFAitF-1637598
NSFCNS-1518941
Linde Institute of Economic and Management ScienceUNSPECIFIED
NSFCNS-1331343
NSFCNS-1518941
Binational Science Foundation (USA-Israel)2012348
Subject Keywords:mechanism design; ad auctions; simple mechanisms; information asymmetries; signaling
Issue or Number:1
Record Number:CaltechAUTHORS:20200709-084932341
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200709-084932341
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104308
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Jul 2020 19:14
Last Modified:04 Nov 2020 19:43

Repository Staff Only: item control page