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 May 2020 | Published + Submitted
Journal Article Open

Third-Party Data Providers Ruin Simple Mechanisms

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 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 $łog łog$ 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). Publication rights licensed to ACM. Received October 2019; revised December 2019; accepted January 2020. 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 - 3379478.pdf

Submitted - 1802.07407.pdf

Files

1802.07407.pdf
Files (1.2 MB)
Name Size Download all
md5:1b0176ab50bd9b31f2936f664b47fde9
237.9 kB Preview Download
md5:62aed5e96976929140bc1344105b32a7
927.3 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 20, 2023