Sameer Mehta

The unprecedented rate at which data are being generated has led to the growth of data markets where valuable data sets are bought and sold. A salient feature of this market is that a data‐buyer (agent) is endowed with multidimensional private information, namely, her “ideal” record that she values the most and how her valuation for a given record changes as its distance from her ideal record changes. Consequently, the revenue‐maximization problem faced by a data‐seller (principal), who serves multiple buyers, is a multidimensional mechanism‐design problem, which is well recognized as being difficult to solve. Our main result in this paper is an approximation scheme that guarantees a revenue within as close a positive amount from the optimal revenue as desired. The scheme generates a posted‐price menu consisting of a set of item–price pairs—each entry in the menu consists of an item, that is, a set of records from the data set, and the price corresponding to that item. As a trade‐off, the length of the menu resulting from the scheme increases as the desired guarantee gets closer to zero. For convenience in practice, data‐sellers may want the ability to limit the length of the menu used by the scheme. To facilitate this, we extend our analysis to obtain a general approximation guarantee corresponding to a menu of any given length. We also demonstrate how the seller can exploit buyers' preferences to generate intuitive and useful rules of thumb for an effective practical implementation of the scheme.