Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 2020 | Published
Journal Article Open

Third-Party Data Providers Ruin Simple Mechanisms


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.

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.

Attached Files

Published - 3410048.3410108.pdf


Files (1.0 MB)
Name Size Download all
1.0 MB Preview Download

Additional details

August 22, 2023
August 22, 2023