License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.81
URN: urn:nbn:de:0030-drops-136205
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13620/
Cai, Yang ;
Velegkas, Grigoris
How to Sell Information Optimally: An Algorithmic Study
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. [Bergemann et al., 2018], 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. [Bergemann et al., 2018] that allows multiple agents to compete for useful information. We leverage techniques developed in the study of auction design (see e.g. [Yang Cai et al., 2012; Saeed Alaei et al., 2012; Yang Cai et al., 2012; Yang Cai et al., 2013; Yang Cai et al., 2013]) to design a polynomial time algorithm that computes the revenue-optimal mechanism for selling information.
BibTeX - Entry
@InProceedings{cai_et_al:LIPIcs.ITCS.2021.81,
author = {Yang Cai and Grigoris Velegkas},
title = {{How to Sell Information Optimally: An Algorithmic Study}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {81:1--81:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13620},
URN = {urn:nbn:de:0030-drops-136205},
doi = {10.4230/LIPIcs.ITCS.2021.81},
annote = {Keywords: Mechanism Design, Algorithmic Game Theory, Information Design}
}
|
Keywords: |
|
Mechanism Design, Algorithmic Game Theory, Information Design |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
