# How to Sell Information Optimally: an Algorithmic Study

Source: [How to Sell Information Optimally: an Algorithmic Study](<https://www.sota2.com/research/paper/68fa68fb1e209131cea1f845>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:45.965Z

Authors: Yang Cai, Grigoris Velegkas

Published: 2020-11-30T06:18:03.000Z

## Abstract

We investigate the algorithmic problem of selling information to agents who face a decision-making problem under uncertainty. We adopt the model recently proposed by Bergemann et al. \[BBS18\], in which information is revealed through signaling schemes called experiments. In the single-agent setting, any mechanism can be represented as a menu of experiments. Our results show that the computational complexity of designing the revenue-optimal menu depends heavily on the way the model is specified. When all the parameters of the problem are given explicitly, we provide a polynomial time algorithm that computes the revenue-optimal menu. For cases where the model is specified with a succinct implicit description, we show that the tractability of the problem is tightly related to the efficient implementation of a Best Response Oracle: when it can be implemented efficiently, we provide an additive FPTAS whose running time is independent of the number of actions. On the other hand, we provide a family of problems, where it is computationally intractable to construct a best response oracle, and we show that it is NP-hard to get even a constant fraction of the optimal revenue. Moreover, we investigate a generalization of the original model by Bergemann et al. \[BBS18\] that allows multiple agents to compete for useful information. We leverage techniques developed in the study of auction design (see e.g. \[CDW12a\], \[AFHHM12\], \[CDW12b\], \[CDW13a\], \[CDW13b\]) to design a polynomial time algorithm that computes the revenue-optimal mechanism for selling information.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [Data Pricing on Data Pricing Problem Settings](<https://www.sota2.com/research/sota/data-pricing-on-data-pricing-problem-settings.md>): Data Pricing; Data Pricing Problem Settings; Time Complexity: 2.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2011.14570>)

[PDF](<https://arxiv.org/pdf/2011.14570.pdf>)
