Yale University, USA
yang.cai@yale.eduhttps://orcid.org/0000-0002-5426-1324Supported by a Sloan
Foundation Research Fellowship and the NSF Award CCF-1942583 (CAREER).Yale
University, USAgrigoris.velegkas@yale.eduhttps://orcid.org/0000-0001-7148-0548
Partially supported by a PhD Scholarship from the Onassis Foundation and a PhD
Scholarship from the Bodossaki Foundation. Yang Cai and Grigoris Velegkas
Theory of computation Algorithmic game theory A full version of the paper is
available at https://arxiv.org/abs/2011.14570

###### Acknowledgements.

We would like to thank Dirk Bergemann for helpful discussions and the
anonymous reviewers for their valuable comments and suggestions.James R. Lee 1
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) ITCS
2021 ITCS 2021 January 6–8, 2021 Virtual Conference 185 88

# How to Sell Information Optimally: an Algorithmic Study

Yang Cai  Grigoris Velegkas

###### 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. [4], 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. [4] that allows
multiple agents to compete for useful information. We leverage techniques
developed in the study of auction design (see e.g. [5, 1, 6, 7, 8]) to design
a polynomial time algorithm that computes the revenue-optimal mechanism for
selling information.

###### keywords:

Mechanism Design, Algorithmic Game Theory, Information Design

##  1 Introduction

Decision-making heavily relies on information availability. The uneven
distribution of information thus enables markets for trading information.
Imagine a bank reviewing a loan application. Information about the borrower’s
financial status clearly influences the bank’s lending decisions. In this
setting, the bank already has some private knowledge about the borrower, i.e.,
through prior interactions, but may still be willing to pay to acquire
supplemental information to guide its decision-making. Indeed, Equifax, the
credit report agency, provides its business consumers, e.g., banks and credit
card companies, a product called Undisclosed Debt Monitoring, that tracks
negative information about individual borrowers.
111https://www.equifax.com/business/undisclosed-debt-monitoring/

How should the information owner reveal and price the information? We adopt
the model introduced by Bergemann et al. [4] to study this problem. Their
model involves a data buyer and a data seller. The data buyer faces a decision
under uncertainty, and his payoff depends on the _action_ he decides to take
and the underlying _state_ of the world. Initially, the buyer only has some
_imperfect_ knowledge about the state, i.e. a prior distribution over the
possible states. This piece of information is private to the buyer. On the
contrary, the data seller knows the state of the world and can sell
supplemental information to the buyer. Since the buyer’s willingness to pay
for supplemental information is determined by the precision of his own prior
belief, we refer to the buyer’s prior belief as his type. How does the seller
optimize her revenue if the buyer’s type is assumed to be drawn from a known
distribution? To screen heterogeneous buyer types, the seller offers a menu of
information products. Each product has the form of a _statistical experiment_
, whose result reveals a signal that is correlated with the underlying state.
Bergemann et al. [4] investigate what experiments should be included and how
to price them. They obtain analytic solution of the revenue-optimal menu in
two special cases: (i) the case with only two possible buyer types and (ii)
the case with two states and two possible actions for the buyer to choose
from. However, general characterization of the revenue-optimal menu remains
elusive. In this paper, we initiate the algorithmic study of this problem and
investigate the computational complexity for finding the revenue-optimal menu.

Our first result considers an explicit representation of the problem, where
the input contains the buyer’s type distribution and his payoff for each
action and state pair.

  1. Result I:

We design an algorithm that computes the revenue-optimal menu in time
polynomial in the number of buyer types, the number of buyer actions, and the
number of underlying states. (Theorem 3.3)

For many settings of interest, the model is too expensive to be specified
explicitly but has a natural succinct implicit description. Consider the
following motivating example. Suppose there is a traffic network $G$, and a
binary state $\omega$ that indicates the level of congestion on the edges of
$G$. A driver wants to go from a vertex $s$ to another vertex $t$, and his
payoff is $H$ minus the expected travel time from $s$ to $t$ using the path he
picks. 222$H$ is a sufficiently large constant so that the payoff is always
nonnegative. Of course, which path is the fastest depends on the driver’s
belief of the state $\omega$. Suppose Waze is offering a service that provides
the driver supplemental information about the congestion. How should Waze
price its service? In this setting, the driver is the data buyer and the
number of actions available to him is exactly the number of $s-t$ paths, which
can be exponential in the size of the network $G$. Applying our first result
is thus computationally inefficient in this setting. Our second result
concerns exactly these settings with succinct implicit descriptions. We show
that the key to tractability is the existence of a computationally efficient
_Best Response Oracle_ , that is, an oracle that accepts a distribution over
the underlying state as input and outputs an action with the highest expected
payoff. Clearly, in the example above, it is straightforward to construct a
computationally efficient best response oracle – simply assign the expected
congestion on each edge as its length and run any shortest path algorithm on
the graph $G$. We show that finding the revenue-optimal menu is tractable as
long as there exists a best response oracle.

  1. Result II:

For any setting with a constant number of possible underlying states, we
design an FPTAS to compute an _up-to- $\varepsilon$ optimal menu_, i.e., a
menu whose revenue is at most $\varepsilon$ less than the optimum, given
access to a best response oracle. 333Our algorithm runs in time polynomial in
the total number of buyer types and $1/\varepsilon$. (Theorem 3.8)

Without the best response oracle, we show that it is NP-hard to even find a
constant factor approximation to the optimal revenue for a family of
succinctly describable instances with only two underlying states and one buyer
type. (Theorem 3.11)

We also investigate extensions of the basic model studied in Bergemann et al.
[4]. First, we consider the setting where multiple data buyers are competing
with each other to receive an informative signal from the data seller. We
obtain the following generalization of Result I.

  1. Result III:

We design an algorithm that computes the revenue-optimal mechanism in time
polynomial in the _total number of buyer types_ , the number of buyer actions,
and the number of underlying states. (Theorem 4.6)

Note that the straightforward generalization of Result I only gives an
algorithm that runs in time polynomial in the _total number of buyer type
profiles_ , which is exponential in the number of buyers. Our algorithm in
Result III runs in time polynomial in the _total number of buyer types_ ,
which is the description size for specifying each buyer’s type distribution.

In Section 5, we discuss another natural extension. We can treat a buyer’s
payoffs for taking actions in various states as the buyer’s private
information and may be different across buyers. In other words, a buyer type
is no longer just the buyer’s prior belief of the underlying state but also
his payoff function. We show that all our results (c.f. Result I, II, and III)
can be easily extended to handle this case, and the modification is summarized
in Section 5.

#### Our Approach:

In the explicit model, we first show that the revenue-optimal menu can be
captured by a LP with polynomially many decision variables but exponentially
many constraints. We leverage a technique introduced by Chen et al. [15] to
transform it to an equivalent LP with polynomially many constraints. In the
implicit model with a best response oracle, the main difficulty is that the
optimal menu may contain experiments that use an arbitrary number of signals,
and as a result the menu cannot even be represented in polynomial time. To
overcome this difficulty, we first argue that there always exists an up-
to-$\varepsilon$ optimal menu that only contains experiments that use a small
number of signals, then apply an algorithm similar to the one in the explicit
model to find such a menu. For the multi-agent setting, one can use a LP
similar to the one in the explicit model to capture the optimal mechanism. The
issue with this approach is that both of the number of variables and
constraints are exponential in the number of agents, which is too large to
solve. Our solution is inspired by an approach used to computing the revenue-
optimal multi-item auctions [5, 1, 6, 7, 8]. The key idea is to first
represent mechanisms in a succinct way known as the “reduced forms” and use a
LP to search for the revenue-optimal reduced form. However, as a reduced form
is only a succinct description, given a reduced form, it is not obvious what
mechanism it corresponds to. Indeed, it is not even clear whether it
corresponds to any mechanism. The main technical barrier we overcome is to
design efficient algorithms to (i) check the feasibility of a reduced form and
(ii) to implement a feasible reduced form as an actual mechanism.

###  1.1 Related Work

#### Relationship with Monopoly Pricing.

A well-studied problem from mechanism design, the _monopoly pricing problem_ ,
bears some resemblance to our problem. The monopoly pricing problem asks what
is the revenue-optimal mechanism to sell one or more items to a buyer, whose
valuation/willingness to pay for the items is drawn from a known distribution.
In single-dimensional settings, the problem is completely resolved by [35,
36]. In multi-dimensional settings, complete characterizations are known only
in several special cases [27, 28, 30, 18, 26, 22, 21], but simple and
approximately optimal mechanisms [13, 14, 31, 2, 34, 37, 9, 12], as well as
algorithmic characterizations [5, 1, 6, 7, 8] have been discovered in fairly
general settings. The nature of information goods adds an extra layer of
difficulty to the pricing problem. The value of information is determined by
how much such information can improve the quality of decision-making. Buyers
with different beliefs do not simply have different values for different
experiments, but they may even disagree on their ranking. This richness in
buyer valuations does not happen in single-dimensional monopoly pricing, but
already exists in single-dimensional information pricing, where there are only
two possible underlying states. 444In this case, the buyer’s prior belief can
be represented using a single real number in $[0,1]$. As a result, the optimal
menu in information pricing has a more complex structure. For example,
Bergemann et al. [4] showed that even in the two-state case, the seller
sometimes needs to use randomized experiments to maximize her revenue. In this
work, we show that despite the new challenges of selling information products,
some of the algorithmic ideas from monopoly pricing are still useful.

#### Relationship with Information Design.

Similar to our problem, the designer constructs a signaling scheme that
reveals partial information about the underlying state to influence the action
of the agents in information design [32]. There has been growing interest in
the algorithmic study of information design [24, 23, 25, 16, 19, 10]. The
fundamental difference between our setting and information design is that, in
our setting, the buyer’s action does not have direct effect on the seller’s
utility. The seller only derives utility from the monetary transfers received
from the buyer.

#### Relationship with other Information-Selling Models.

The work that is most related to the problem we are studying is by Babaoiff et
al. [3]. Similar to us, they consider a seller who knows the state of the
world $\omega$ and wants to sell information to a buyer whose prior is drawn
from some distribution $\Theta$. However, there is a subtle but crucial
difference between our models. In their work, the seller’s information
disclosure strategy and the price are allowed to be dependent on the realized
state of the world $\omega$. By contrast, our model requires the seller to
commit to a mechanism before the realization of the state $\omega$. Their main
results state that (i) when $\omega$ and the buyer’s type are independently
distributed, revelation principle holds, i.e., a single-round interaction
suffices; and (ii) when $\omega$ and the buyer’s type are correlated, a full
surplus extraction mechanism, similar to Crémer and McLean [17], exists and
can be computed efficiently. These results differ quite substantially from the
structural results for the model we study here [4]. For instance, full surplus
extraction is in general impossible in our model. In a recent work, Chen et
al. [15] extends the results by Babaioff et al. [3] to the setting where the
buyer is budget-constrained, and improves upon some of the algorithmic
results.

##  2 Preliminaries

#### Model and Notation.

The data buyer faces a decision problem under uncertainty. The state of the
world $\omega$ is drawn from a state space $\Omega$. The buyer chooses an
action $a$ from an action space $A$. Throughout the paper, we use $m$ to
denote the size of $A$. The buyer’s ex-post utility for choosing action $a$
under state $\omega$ is defined to be $u_{\omega,a}$ and is assumed to lie in
$[0,1]$. The buyer has some prior information about the state of the world
which is denoted by $\theta$ and comes from a set
$\Theta\subseteq\Delta\Omega$. We call $\theta$ the type of the buyer, and use
$\theta_{\omega}$ to denote the probability that the buyer assigns to the
event that the state of the world is $\omega$. The type of the buyer is
distributed according to $F$. Apart from the buyer, there is also a seller who
observes the state of the world and is willing to sell supplemental
information to the buyer. We refer to the buyer as he and to the seller as
she.

#### Experiment.

The seller provides supplemental information to the buyer via a signaling
scheme which we call experiment. A signaling scheme is a commitment to
$|\Omega|$ probability distributions over a set of different signals $S$, such
that when the state of the world is realized, the seller draws a signal from
the corresponding distribution and sends it to the buyer. We denote such an
experiment by $E=(S,\pi(E))$, where $\pi(E):\Omega\rightarrow\Delta S$ denotes
the distributions that experiment $E$ is using. We denote the probability that
experiment $E$ sends signal $s_{k}$ when the state of the world is $\omega$ by
$\pi_{\omega,k}(E)=\Pr[s_{k}|\omega]$. In this work, it is useful to think of
the experiment $\pi(E)$ as a matrix whose rows are indexed by the states of
the world and columns are indexed by the signals. A menu of experiments is a
collection $\mathcal{M}=\\{(E,t(E))\\}$, where $t(E)\in[0,1]$ is the payment
the buyer has to make when he purchases experiment $E$. In the multi-agent
setting, a menu is insufficient to generate the optimal revenue, and our goal
there is to compute the revenue-optimal _mechanism_. In the single-agent
setting, the interaction between the seller and the buyer works as follows:

  1. 1.

The seller posts a menu $\mathcal{M}$.

  2. 2.

The state of the world $\omega$ and the type of the buyer $\theta$ are
realized.

  3. 3.

The buyer chooses some experiment $E$ from the menu based on his type and pays
$t(E)$.

  4. 4.

The seller sends the buyer a signal $s$ that is drawn from
$\pi_{\omega,\cdot}(E)$.

  5. 5.

The buyer chooses an action $a$, based on his original belief $\theta$ and the
signal $s$, and receives utility $u_{\omega,a}$.

#### The Value of an Experiment.

To understand the behavior of the buyer, we first explain how the buyer
evaluates an experiment. We first explain how the buyer would act if the only
information available to him was his type $\theta$. Since the buyer picks an
action that maximizes his expected utility, his best move without receiving
any additional information from the seller is
$a(\theta)={\operatorname*{arg\,max}_{a}\sum_{\omega}\theta_{\omega}u_{\omega,a}}$
and his base utility following that move is
$u(\theta)=\max_{a}\sum_{\omega}\theta_{\omega}u_{\omega,a}$. If he receives
extra information from the seller, he updates his beliefs and may choose a new
action that induces higher expected value based on his posterior distribution
over the states. After receiving signal $s_{k}$ from experiment $E$ his belief
about the state of the world is

$\Pr[\omega|s_{k},\theta]=\frac{\theta_{\omega}\pi_{\omega,k}(E)}{\sum_{\omega^{\prime}\in\Omega}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},k}(E)}.$

Hence, the best action is

$a(s_{k}|\theta)\in\operatorname*{arg\,max}_{a}\sum_{\omega}\left(\frac{\theta_{\omega}\pi_{\omega,k}(E)}{\sum_{\omega^{\prime}\in\Omega}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},k}(E)}\right)u_{\omega,a},$

which yields conditional expected utility

$u(s_{k}|\theta):=\max_{a}\sum_{\omega}\left(\frac{\theta_{\omega}\pi_{\omega,k}(E)}{\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},k}(E)}\right)u_{\omega,a}.$

When it is clear from the context, we might drop $\theta$ in the previous
expressions. Notice that after computing his posterior, the buyer’s
conditional expected utility is linear in the actions so we can assume
w.l.o.g. that he picks a single action and not a distribution over actions.
Taking the expectation over the signal he will receive, we denote the value of
the experiment $E$ for type $\theta$ to be

$V_{\theta}(E)=\sum_{s_{k}\in
S}\max_{a}\left\\{\sum_{\omega}\theta_{\omega}\pi_{\omega,k}(E)u_{\omega,a}\right\\}.$

We assume that the buyer is quasilinear. We denote the expected net utility of
type $\theta$ for experiment $E$ as $V_{\theta}(E)-t(E)$.

Notice that two different types $\theta,\theta^{\prime}$ may have different
favorite actions under the same signal. As a result, $V_{\theta}(E)$ is not a
linear function over $\theta$ for a fixed experiment $E$ even when the type
$\theta$ is single-dimensional, i.e., $|\Omega|=2$. Consider the following
example.

######  Example 2.1.

There are two states of the world $\Omega=\\{\omega_{1},\omega_{2}\\}$, two
possible actions $A=\\{a_{1},a_{2}\\}$ and we have a _matching action-state_
environment, i.e. the ex-post utilities are as follows

$U=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}.$

Consider the following experiment $E$ that sends two different signals
$s_{1},s_{2}$ with

$E=\begin{pmatrix}0.7&0.3\\\ 0.3&0.7\end{pmatrix}.$

For a buyer whose prior is
$\theta_{\omega_{1}}=\theta,\theta_{\omega_{2}}=1-\theta$, after receiving
$s_{1},s_{2}$ the posteriors of the buyer are
$\left(\frac{0.7\theta}{0.4\theta+0.3},\frac{0.3(1-\theta)}{0.4\theta+0.3}\right)$
and
$\left(\frac{0.3\theta}{0.7-0.4\theta},\frac{0.7(1-\theta)}{0.7-0.4\theta}\right)$
respectively. Hence, we see that when $\theta\leq 0.3$ the buyer will take
action $a_{2}$ after receiving either $s_{1}$ or $s_{2}$. Similarly, if
$0.3<\theta\leq 0.7$ he will take action $a_{1}$ (or $a_{2}$) after receiving
$s_{1}$ (or $s_{2}$). Finally, when $\theta>0.7$ the buyer will take action
$a_{1}$ no matter which signal he receives. This leads to the following value
function for $E$

$V_{\theta}(E)=\begin{cases}1-\theta&\quad\text{if }0\leq\theta\leq 0.3\\\
0.7&\quad\text{if }0.3<\theta\leq 0.7\\\ \theta&\quad\text{if
}0.7\leq\theta\leq 1\\\ \end{cases}$

This is in sharp contrast to standard single-dimensional auction design
settings, where the agent’s value is always a linear function over the type
when the allocation is fixed. 555Indeed, this linearity even holds for quite
general multi-dimensional settings in auction design, for example, when the
buyer has additive valuations.

#### IC and IR Menu.

The buyer chooses the experiment that gives him the highest net utility, and
we slightly abuse notation and denote by $E(\theta)$ the experiment of the
menu $\mathcal{M}$ that type $\theta$ prefers

$E(\theta)=\operatorname*{arg\,max}_{E}V_{\theta}(E)-t(E).$

If all experiments give him expected net utility smaller than his base utility
$u(\theta)$, he will not purchase any experiment. For convenience, we assume
that there is a null experiment that provides no information offered at price
$0$, so now without loss of generality every type takes an experiment from the
menu. We sometimes abuse notation to call a menu Incentive Compatible (IC) and
Individually Rational (IR). By that, we mean that every buyer type $\theta$
selects the experiment $(E(\theta),t(\theta))$ that maximizes his expected net
utility. Formally, these constraints are captured by the following two sets of
inequalities:

$\displaystyle V_{\theta}(E(\theta))-t(\theta)$ $\displaystyle\geq
V_{\theta}(E(\theta^{\prime}))-t(\theta^{\prime}),\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\theta,\theta^{\prime}\in\Theta,$ $\displaystyle
V_{\theta}(E(\theta))-t(\theta)$ $\displaystyle\geq
u(\theta),\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\forall\theta\in\Theta.$

Once we have fixed the parameters of the model, we denote by
$\textsc{Rev}(\mathcal{M})$ the revenue that menu $\mathcal{M}$ generates and
by OPT the optimal revenue in this setting.

##  3 Optimal Menu for a Single Agent

In this section, we consider the problem of computing the optimal menu for a
single agent. As we will show, the computational complexity of the problem is
tightly related to the way that the problem is specified. We consider three
different models.

  * •

Explicit model: the distribution $F$ and the ex-post utility matrix $U$ are
given explicitly in the input.

  * •

Implicit model with a best response (BR) oracle: the distribution $F$ is given
along with a best response oracle. The best response oracle accepts a
distribution over the states as input and outputs the action that generates
the highest expected utility w.r.t. the input distribution.

  * •

Implicit model with succinct description: the distribution $F$ is given along
with the description of a Turing Machine that computes the ex-post utility of
any pair of state and action in time polynomial in the description size.

We summarize our results with respect to the three different models: (i) we
show that computing the optimal menu in the explicit model is captured by a
polynomial size LP; (ii) even though the number of actions in the implicit
model with BR oracle may be arbitrarily large, we provide an FPTAS to find an
up-to-$\varepsilon$ optimal menu for settings with a constant number of
underlying states; (iii) we construct a succinctly representable instance of
the problem such that computing a constant factor approximation or an up-
to-$\varepsilon$ optimal menu is NP-hard.

###  3.1 Explicit Model

In this section, we discuss the basic setting where the model is explicitly
given. First, we state a structural result of the optimal menu that allows us
to restrict the number of signals.

######  Definition 3.1 (Responsive Experiment).

A buyer type $\theta$ is _responsive_ to an experiment $E$ if every signal $s$
of $E$ leads $\theta$ to a different optimal choice of action and, in
particular $a(s_{k}\mid\theta)=a_{k}$ for all $s_{k}\in S$.

Note that if an experiment $E$ is responsive to any buyer type, $E$ has
exactly $m$ signals. An intuitive way to think about Definition 3.1 is that
signal $s_{i}$ of $E$ recommends the buyer to take a action $a_{i}$, and type
$\theta$ is responsive to $E$ if $\theta$ always follow the recommendation.
Importantly, a different type $\theta^{\prime}$ may not be responsive to
experiment $E$ and does not follow the recommendations. We now state the
structural result from [4] that states that it is without loss of generality
to consider a menu where each buyer type purchases a responsive experiment.

######  Lemma 3.2 (Adapted from Proposition 1 from [4]).

A menu $\mathcal{M}$ is _responsive_ if for every buyer type $\theta$, it
chooses a responsive experiment $E(\theta)$ from the menu. We define the
outcome of a menu as the joint distribution of states, actions, and monetary
transfers resulting from every buyer type’s optimal choice of experiment and
subsequent choice of action. The outcome of every menu can be attained by a
responsive menu.

The proof of Lemma 3.2 is based on a revelation-principle type of argument.
More precisely, assume that some type $\theta$ prefers an experiment
$E(\theta)$ for which he is not responsive. Then, we can merge all the signals
$s_{i_{1}},\ldots,s_{i_{\ell}}$ of $E(\theta)$ that lead the type to take the
same action $a_{k}$ and just send the merged signal as the new $k$-th signal
$s_{k}$. Equipped with the structural result, we are ready to show how to
capture the design of the optimal menu as a LP. Since there exists an optimal
menu that is responsive, every experiment in this menu has at most $m$
signals. For every buyer type $\theta$, we use $\pi(\theta)$ to denote the
experiment type $\theta$ purchases, where $\pi_{\omega,i}(\theta)$ is the
probability to send signal $s_{i}$ when the state is $\omega$.
$\\{\pi_{\omega,i}(\theta)\\}_{\omega\in\Omega,i\in[m],\theta\in\Theta}$ is
the first set of variables. We also have the prices for each experiment
$\\{t(\theta)\\}_{\theta\in\Theta}$ as variables. The main difference between
selling experiments and selling items is that different types may interpret
the same experiment differently. More specifically, for a responsive
experiment $(\pi(\theta),t(\theta))$, the optimal choice of action for type
$\theta$ after receiving signal $s_{i}$ is simply action $a_{i}$; while for a
different type $\theta^{\prime}$, the best action after receiving signal
$s_{i}$ can be a completely different action $a_{j}$ due to a different
induced posterior. As our LP is designed to compute the optimal and responsive
menu, we need to guarantee that for any type $\theta$, purchasing experiment
$(\pi(\theta,t(\theta))$ and following the recommendation is better than
purchasing any experiment $(\pi(\theta^{\prime}),t(\theta^{\prime}))$ for a
different type $\theta^{\prime}$ and subsequently choosing the optimal action
based on the induced posterior. We remark that the straightforward formulation
of the previous constraints requires one to consider all the possible mappings
from signals to actions, resulting in a LP that has exponentially many
constraints in $m$. Although this huge LP can be solved using the ellipsoid
algorithm, we use a technique inspired by Chen et al. [15] that allows us to
formulate it using only polynomially many constraints in $m$.

See Figure 1 for our LP. Besides the variables representing the experiments
and prices, we introduce a new set of variables
$\left\\{z_{i}(\theta,\theta^{\prime})\right\\}_{i\in[m],\theta,\theta^{\prime}\in\Theta}$.
$z_{i}(\theta,\theta^{\prime})$ serves as an upper bound of the conditional
expected utility that $\theta$ gets when he considers misreporting as
$\theta^{\prime}$ and receives signal $s_{i}$, which is guaranteed by the
second set of constraints. The first set of constraints make sure that for any
type $\theta$, the net utility of purchasing experiment $E(\theta)$ and
following its recommendations is no worse than the utility of purchasing any
other experiment and subsequently choosing the best action under each signal.
Note that we allow $\theta^{\prime}$ to be the same $\theta$ in the first set
of constraints, which guarantees that the menu is responsive. The third set of
constraints guarantees that purchasing experiment $(\pi(\theta),t(\theta))$ is
no worse than $\theta$’s base utility. We refer to these constraints as the
individual rationality (IR) constraints. The last two constraints guarantee
that $\pi(\theta)$ is indeed an experiment.

Variables: •
$\\{\pi_{\omega,i}(\theta)\\}_{\omega\in\Omega,i\in[m],\theta\in\Theta}$,
denoting the experiments in the menu. • $\\{t(\theta)\\}_{\theta\in\Theta}$,
denoting the prices of the experiments. •
$\\{z_{i}(\theta,\theta^{\prime})\\}_{i\in[m],\theta,\theta^{\prime}\in\Theta}$,
helper variables. $z_{i}(\theta,\theta^{\prime})$ represents an upper bound of
the conditional expected utility of signal $s_{i}$ from experiment
$E(\theta^{\prime})$ for type $\theta$. Linear Program:
$\begin{array}[]{ll@{}ll}\text{max}&\displaystyle\sum\limits_{\theta\in\Theta}F(\theta)t(\theta)&\\\
\text{s.t.}&\displaystyle\sum\limits_{i\in[m]}\displaystyle\sum\limits_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,i}(\theta)u_{\omega,a_{i}}-t(\theta)\geq\displaystyle\sum\limits_{i\in[m]}z_{i}(\theta,\theta^{\prime})-t(\theta^{\prime}),\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\forall\theta,\theta^{\prime}\in\Theta\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\text{IC})\\\
&z_{i}(\theta,\theta^{\prime})\geq\displaystyle\sum_{\omega}\theta_{\omega}\pi_{\omega,i}(\theta^{\prime})u_{\omega,a_{j}},&\forall\theta,\theta^{\prime}\in\Theta,\forall
i,j\in[m]\\\
&\displaystyle\sum\limits_{i\in[m]}\displaystyle\sum\limits_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,i}(\theta)u_{\omega,a_{i}}-t(\theta)\geq
u(\theta),&\forall\theta\in\Theta\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ (\text{IR})\\\
&\displaystyle\sum\limits_{i\in[m]}\pi_{\omega,i}(\theta)=1,&\forall\theta\in\Theta,\omega\in\Omega\\\
&\pi_{\omega,i}(\theta)\geq
0,&\forall\theta\in\Theta,\forall\omega\in\Omega,\forall i\in[m]\end{array}$

Figure 1: A linear program to find the revenue-optimal menu in the explicit
model.

######  Theorem 3.3.

The LP in Figure 1 can be solved in time polynomial in $m=|A|$, $|\Omega|$,
and $|\Theta|$, and its optimal solution is the revenue-optimal menu.

Proof of Theorem 3.3: The number of constraints and the number of variables of
the LP in Figure 1 is polynomial in $m,|\Omega|,|\Theta|$, so it is clear that
it can be solved in polynomial time. We now argue that its solution is indeed
the optimal responsive menu, hence the optimal menu as guaranteed by Lemma
3.2. Observe that every responsive menu corresponds to a feasible solution of
the LP. This is because if $\\{(\pi(\theta),t(\theta))\\}_{\theta\in\Theta}$
is a responsive menu, then we can satisfy all the constraints by setting
$z_{i}(\theta,\theta^{\prime})=\max_{a_{j}}\sum_{\omega}\theta_{\omega}\pi_{\omega,i}(\theta^{\prime})u_{\omega,a_{j}}$.
Conversely, note that every feasible solution of the LP induces a responsive
menu that simply chooses the experiment $E(\theta)$ as
$\left(\pi(\theta),t(\theta)\right)$ for each type $\theta\in\Theta$. This is
because (i) the first and second sets of constraints guarantee that
$E(\theta)$ is a responsive experiment for $\theta$ (this follows from setting
$\theta^{\prime}$ to be $\theta$ in both the first and second set of
constraints) and $V_{\theta}(E(\theta))-t(\theta)\geq
V_{\theta}(E(\theta^{\prime}))-t(\theta^{\prime})$ ; (ii) the IR constraints
ensure that $V(E(\theta))-t(\theta)\geq u(\theta)$. Hence, the optimal
solution corresponds to the revenue-optimal menu. $\Box$

###  3.2 Implicit Model with a Best Response Oracle

In this section, we study the case where the model is provided implicitly. We
prove that, given access to a best response oracle, our algorithm can compute
an up-to-$\varepsilon$ optimal menu in time ${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$,
which is independent of the number of actions.

We first prove a structural result which shows that no matter how large the
actual action set $A$ may be, there is some $A^{\prime}\subseteq A$ such that
a menu $\mathcal{M}$ that recommends actions only from $A^{\prime}$ has
negligible revenue loss compared to OPT. Moreover, $|A^{\prime}|$ depends only
on $|\Omega|$ and the additive approximation error. We also show that these
sets can be computed efficiently.

######  Theorem 3.4.

For any constant $\varepsilon>0$ , given access to a BR oracle we can compute
for each type $\theta\in\Theta$ a set of actions $A_{\theta}$ by querying
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
times the BR oracle, so that there exists an IC and IR menu $\mathcal{M}$,
whose experiments all contain no more than
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
many signals. Moreover, every type $\theta$ only uses actions from
$A_{\theta}$ upon receiving any of these signals generated by his experiment.
Finally, the revenue of $\mathcal{M}$ is at least
$\text{OPT}-O(\sqrt{\varepsilon})$.

We present some lemmas that are used in the proof of Theorem 3.4. Firstly, we
show that given a menu $\mathcal{M}$ and $\varepsilon$, we can create a menu
$\mathcal{M}^{\prime}$ with the following two properties: (i) the number of
signals that $\mathcal{M}^{\prime}$ uses depends only on $|\Omega|$ and
$\varepsilon$, and every type $\theta$ values the new experiment he gets at
most $O(\varepsilon)$ less than his original experiment. The proof is based on
the idea that merging signals of an experiment $E$ that are close does not
decrease the value of the experiment by much.

######  Lemma 3.5.

Let $\varepsilon>0$ be some given constant and let
$E=\\{E(\theta)\\}_{\theta\in\Theta}$ be a set of experiments, where each
$E(\theta)$ uses an arbitrary number of signals. Then, we can create a set of
experiments $E^{\prime}=\\{E^{\prime}(\theta)\\}_{\theta\in\Theta}$ that uses
$O((\frac{|\Omega|}{\varepsilon})^{|\Omega|})$ signals per player such that
$V_{\theta}(E^{\prime}(\theta))\geq V_{\theta}(E(\theta))-2\varepsilon$.

Proof of Lemma 3.5: Fix some $\theta\in\Theta$ and let $E(\theta)$ be the
experiment that is offered to this type. For any signal $s_{i}$ that the
experiment $E({\theta})$ sends we define
$\hat{\pi}_{\omega,i}(\theta)=\frac{\pi_{\omega,i}(\theta)}{\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)}$
to be the normalized probability of sending signals $s_{i}$ in state $\omega$.
We partition all the vectors $\hat{\pi}_{\cdot,i}$ according to the following
procedure. Let $\tilde{\pi}_{\cdot,i}$ be the vector that is created by
rounding the entries of $\hat{\pi}_{\cdot,i}$ to multiples of
$\varepsilon/|\Omega|$. We put $\hat{\pi}_{\cdot,i},\hat{\pi}_{\cdot,j}$ in
the same set of the partition if they round to the same vector, i.e.
$\tilde{\pi}_{\cdot,i}=\tilde{\pi}_{\cdot,j}$. Notice that this forms an
actual partition, all the $\hat{\pi}_{\cdot,i},\hat{\pi}_{\cdot,j}$ that are
in the same set have
$|\hat{\pi}_{\omega,i}-\hat{\pi}_{\omega,j}|\leq\frac{\varepsilon}{|\Omega|}$
and there are at most $O\left((|\Omega|/\varepsilon)^{|\Omega|}\right)$
different sets. We now describe a merging procedure of the signals that will
create $E^{\prime}(\theta)$ and guarantees that the number of signals that
$E^{\prime}(\theta)$ uses is bounded by a number that is independent of the
signals in $E(\theta)$. Moreover, $V_{\theta}(E^{\prime}(\theta))$ has a
negligible decrease compared to $V_{\theta}(E(\theta))$. Assume that
$\hat{\pi}_{\cdot,i},\hat{\pi}_{\cdot,j}$ are in the same set of the
partition. Without loss of generality, let
$\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)\leq\sum_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)$.
Then, we have that

$\displaystyle\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{j}}\geq\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{i}}$
$\displaystyle\implies$
$\displaystyle\frac{\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{j}}}{\sum_{\omega}\pi_{\omega,j}(\theta)}\geq\frac{\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{i}}}{\sum_{\omega}\pi_{\omega,j}(\theta)}$
$\displaystyle\implies$
$\displaystyle\frac{\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{j}}}{\sum_{\omega}\pi_{\omega,i}(\theta)}\geq\frac{\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{i}}}{\sum_{\omega}\pi_{\omega,i}(\theta)}-2\frac{\varepsilon}{|\Omega|}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \left(\text{as
}|\hat{\pi}_{\omega,i}-\hat{\pi}_{\omega,j}|\leq\frac{\varepsilon}{|\Omega|}\right)$
$\displaystyle\implies$
$\displaystyle\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{j}}\geq\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{i}}-2\frac{\varepsilon}{|\Omega|}\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)$
$\displaystyle\implies$
$\displaystyle\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}(\pi_{\omega^{\prime},i}(\theta)+\pi_{\omega^{\prime},j}(\theta))u_{\omega^{\prime},a_{j}}\geq\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{i}}$
$\displaystyle\qquad\qquad\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
+\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{j}}-2\frac{\varepsilon}{|\Omega|}\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)$
$\displaystyle\implies$ $\displaystyle\max_{a\in
A}\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}(\pi_{\omega^{\prime},i}(\theta)+\pi_{\omega^{\prime},j}(\theta))u_{\omega^{\prime},a}\geq\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)u_{\omega^{\prime},a_{i}}$
$\displaystyle\qquad\qquad\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
+\sum_{\omega^{\prime}}\theta_{\omega^{\prime}}\pi_{\omega^{\prime},j}(\theta)u_{\omega^{\prime},a_{j}}-2\frac{\varepsilon}{|\Omega|}\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)$

Hence, we see that when we merge two signals that are in the same set, the
value of the buyer for the experiment drops by at most
$2\varepsilon\sum_{\omega^{\prime}}\pi_{\omega^{\prime},i}(\theta)$, where
$\pi_{\cdot,i}(\theta)$ is the signal with the smallest sum. Let
$\pi_{\cdot,i+j}$ be the merged signal and assume that for $\omega$ we have
$\hat{\pi}_{\omega,i}\leq\hat{\pi}_{\omega,j}$. Then, it holds that
$\hat{\pi}_{\omega,i}\leq\hat{\pi}_{\omega,i+j}\leq\hat{\pi}_{\omega,j}$
because for any four positive numbers $a,b,c,d$ with
$\frac{a}{b}\leq\frac{c}{d}$ we have that
$\frac{a}{b}\leq\frac{a+c}{b+d}\leq\frac{c}{d}$. Thus, we see that the merged
signal will remain in the same set of the partition that the two original ones
were. Let $\pi_{\cdot,1},\ldots,\pi_{\cdot,N}$ be the signals that are in some
set $P$. Our previous discussion shows that we can merge
$\pi_{\cdot,1},\pi_{\cdot,2}$ to create $\pi_{\cdot,1+2}$, then merge
$\pi_{\cdot,1+2}$ with $\pi_{\cdot,3}$ and so on. Importantly, all these
signals will remain in $P$ and the amount by which they decrease the value of
the experiment is at most $2\frac{\varepsilon}{|\Omega|}\sum_{i\in
P}\sum_{\omega\in\Omega}\pi_{\omega,i}(\theta)$. If we do that for all sets
$P$, the total decrease in the value is at most
$2\frac{\varepsilon}{|\Omega|}\sum_{i}\sum_{\omega\in\Omega}\pi_{\omega,i}(\theta)=2\varepsilon$
$\Box$

We now argue that when we merge two signals, no type can value any experiment
more than he did before.

######  Claim 1.

Let $E({\theta})$ be the initial experiment that is offered to type $\theta$
and $E^{\prime}({\theta})$ the experiment that is offered to $\theta$ after
the merge. Then, for any type $\theta^{\prime}\in\Theta$ it holds that
$V_{\theta}(E^{\prime}({\theta}^{\prime}))\leq
V_{\theta}(E({\theta}^{\prime}))$.

Proof of Claim 1: Consider the first time that two signals $s_{i},s_{j}$ of
$E({\theta}^{\prime})$ are merged. Then, the value of $\theta$ for this new
experiment is

$\displaystyle V_{\theta}(E^{\prime}({\theta}^{\prime}))$
$\displaystyle=\sum_{l\neq
i,j}\max_{a}\sum_{\omega}\theta_{\omega}\pi_{\omega,l}(E(\theta^{\prime}))u_{\omega,a}+\max_{a}\sum_{\omega}\theta_{\omega}(\pi_{\omega,i}(E(\theta^{\prime}))+\pi_{\omega,j}(E(\theta^{\prime})))u_{\omega,a}$
$\displaystyle\leq\sum_{l\neq
i,j}\max_{a}\sum_{\omega}\theta_{\omega}\pi_{\omega,l}(E(\theta^{\prime}))u_{\omega,a}$
$\displaystyle\qquad\qquad\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
+\max_{a}\sum_{\omega}\theta_{\omega}\pi_{\omega,i}(E(\theta^{\prime}))u_{\omega,a}+\max_{a}\sum_{\omega}\theta_{\omega}\pi_{\omega,j}(E(\theta^{\prime}))u_{\omega,a}$
$\displaystyle=V_{\theta}(E({\theta}^{\prime}))$

Continuing inductively, we prove the claim. $\Box$

So far we have established the existence of a menu $\mathcal{M}^{\prime}$
whose number of signals is significantly smaller than the initial one.
However, if we do not have access to $\mathcal{M}$ we cannot compute
$\mathcal{M}^{\prime}$. Lemma 3.6 shows that we can overcome this issue. By
“rounding” the entries of the experiment so that for any type the value this
experiment generates does not change much. Now, since there is a small number
of signals, and the size of every experiment depends only on $\varepsilon$ and
$|\Omega|$, we can do an exhaustive search over the discretized entries.

######  Lemma 3.6.

Let $\\{E(\theta)\\}_{\theta\in\Theta}$ be a set of experiments, where each
$E(\theta)$ uses signals from $S$. We also let $0<\delta<1$ be a given number
such that $1/\delta\in\mathbb{N}$. Then, we can create a set of experiments
$\\{E^{\prime}(\theta)\\}_{\theta\in\Theta}$ that uses signals from
$S^{\prime}$ with $|S^{\prime}|=|S|$, such that $E^{\prime}(\theta)$ is a
valid experiment with $\pi_{\omega,s^{\prime}}(E^{\prime}(\theta))$ being a
multiple of $\delta$ for all $\omega\in\Omega,s^{\prime}\in
S^{\prime},\theta\in\Theta$, and
$|V_{\theta}(E^{\prime}(\theta^{\prime}))-V_{\theta}(E(\theta^{\prime}))|\leq\delta|S|$,
for all $\theta,\theta^{\prime}\in\Theta$.

Proof of Lemma 3.6: Fix some $\theta\in\Theta$ and consider any
$\theta^{\prime}\in\Theta$. We create $E^{\prime}(\theta^{\prime})$ by
rounding every entry of $\pi_{\cdot,\cdot}(E(\theta^{\prime}))$ to multiples
of $\delta$ in such a way that
$\sum_{i^{\prime}}\pi_{\omega,i^{\prime}}=1,\forall\omega\in\Omega$. Consider
a particular signal $s_{k}$ of $E(\theta^{\prime})$ that results in $\theta$
taking action $a(s_{k})$. After the rounding step, the rounded signal
$s^{\prime}_{k}$ might lead $\theta$ to take a different action
$a(s^{\prime}_{k})$. Thus, we have

$\displaystyle V_{\theta}(E^{\prime}({\theta}^{\prime}))$
$\displaystyle=\sum_{s_{k}^{\prime}\in
S^{\prime}}\sum_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,k^{\prime}}(E^{\prime}(\theta^{\prime}))u_{\omega,a(s_{k}^{\prime})}\geq\sum_{s_{k}^{\prime}\in
S^{\prime}}\sum_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,k^{\prime}}(E^{\prime}(\theta^{\prime}))u_{\omega,a(s_{k})}$
$\displaystyle\geq\sum_{s_{k}\in
S}\sum_{\omega\in\Omega}\theta_{\omega}(\pi_{\omega,k}(E(\theta^{\prime}))-\delta)u_{\omega,a(s_{k})}\geq
V_{\theta}(E(\theta^{\prime}))-\delta|S|$

The other direction is proved similarly. $\Box$

One construction that will be useful in our proofs is the $\varepsilon$-IC to
IC transformation. Lemma 3.7 shows that if we have a menu whose IC, IR
constraints are violated by at most $\varepsilon$, we can modify the prices so
that it becomes IC, IR and has negligible $O(\sqrt{\varepsilon})$ revenue
loss. The construction is based on a technique developed [20, 11] and
frequently used in the Mechanism Design literature. In the single agent
setting, the idea is to offer a small multiplicative discount to all types to
make sure that if they want to deviate to some other experiment, this will not
be much cheaper than the one they were buying in the initial $\varepsilon$-IC
menu.

######  Lemma 3.7.

Let $\mathcal{M}=\\{E_{i},t(E_{i})\\}_{i\in[k]}$ be a menu with $k$
experiments. Suppose that the IC, IR constraints are violated by at most
$\varepsilon$. Then, we can compute a new set of prices
$\\{\tilde{t}(E_{i})\\}_{i\in[k]}$ such that the menu
$\widetilde{\mathcal{M}}=\\{E_{i},\tilde{t}(E_{i})\\}_{i\in[k]}$ is IR, IC and
$\textsc{Rev}(\widetilde{\mathcal{M}})\geq(1-\sqrt{\varepsilon})\textsc{Rev}(\mathcal{M})-\sqrt{\varepsilon}-\varepsilon$,
in time $O(k)$.

Proof of Lemma 3.7: Let $\tilde{t}(E_{i})=(1-\eta)t(E_{i})-\varepsilon$, where
$\eta>0$. We immediately see that all the IR constraints are now satisfied.
Consider a type $\theta$ who buys experiment $E$ under the original prices.
Since the IC constraints are violated by at most $\varepsilon$, we know that

$V_{\theta}(E)-t(E)\geq
V_{\theta}(E^{\prime})-t(E^{\prime})-\varepsilon,\leavevmode\nobreak\ \forall
E^{\prime}\in\mathcal{M}.$

Now suppose that $\theta$ prefers $E^{\prime\prime}$ under the new prices.
Then

$V_{\theta}(E^{\prime\prime})-(1-\eta)t(E^{\prime\prime})\geq
V_{\theta}(E)-(1-\eta)t(E).$

Choosing $E^{\prime}$ to be $E^{\prime\prime}$ in the first inequality and
combining the two inequalities, we have that

$\displaystyle V_{\theta}(E^{\prime\prime})-(1-\eta)t(E^{\prime\prime})\geq
V_{\theta}(E^{\prime\prime})-t(E^{\prime\prime})-\varepsilon+\eta t(E)\implies
t(E)-t(E^{\prime\prime})\leq\frac{\varepsilon}{\eta}$

Hence, for the revenue we have
$\textsc{Rev}(\widetilde{\mathcal{M}})\geq(1-\eta)\textsc{Rev}(\mathcal{M})-\varepsilon-\frac{\varepsilon}{\eta}$.
By picking $\eta=\sqrt{\varepsilon}$ we get the result. $\Box$

We are now ready to present a sketch of the proof for Theorem 3.4. Assume that
we start with the optimal menu $\mathcal{M}^{*}$. By Lemma 3.5, Claim 1, and
Lemma 3.6, we know that we can modify the experiments in $\mathcal{M}^{*}$ so
that they use only discretized signals. Moreover, the new menu is
approximately IC and IR. We then apply Lemma 3.7 to obtain a menu that is IC
and IR by sacrificing a negligible amount of revenue. Finally, to compute the
collection of action sets that the types will choose after receiving the
signals, we query BR oracle on all the possible discretized distributions
where the signals are drawn from.

Proof of Theorem 3.4: Let $\\{E(\theta)\\}_{\theta\in\Theta}$ be a set of
experiments that use signals from $S$ and $\\{t(\theta)\\}_{\theta\in\Theta}$
be the corresponding set of prices that form a valid IC, IR menu. Let
$\\{E^{\prime}(\theta)\\}_{\theta\in\Theta}$ be the set of experiments that is
induced by first merging and then rounding the experiments of
$\\{E(\theta)\\}_{\theta\in\Theta}$. By Lemma 3.5 and Lemma 3.6, we have that
$V_{\theta}(E^{\prime}({\theta}))\geq
V_{\theta}(E({\theta}))-2\varepsilon-\delta|S^{\prime}|$, where
$|S^{\prime}|=\Theta\left((|\Omega|/\varepsilon)^{|\Omega|})\right)$. We pick
$\delta$ so that $\delta|S^{\prime}|\leq\varepsilon$. Thus,
$V_{\theta}(E^{\prime}({\theta}))\geq V_{\theta}(E({\theta}))-3\varepsilon$.
Moreover, Claim 1 and Lemma 3.6 guarantee that
$V_{\theta}(E^{\prime}(\theta^{\prime}))\leq
V_{\theta}(E(\theta^{\prime}))+\delta|S^{\prime}|\leq
V_{\theta}(E(\theta^{\prime}))+\varepsilon$ for any other experiment
$E^{\prime}(\theta^{\prime})$ . Hence, the IC and IR constraints for the menu
$\\{(E^{\prime}(\theta),t(\theta))\\}_{\theta\in\Theta}$ are violated by at
most $4\varepsilon$. Lemma 3.7 shows how we can transform the prices
$\\{t(\theta)\\}_{\theta\in\Theta}$ to
$\\{t^{\prime}(\theta)\\}_{\theta\in\Theta}$ so that the revenue drops by at
most $\Theta(\sqrt{\varepsilon})$, without modifying the experiments that are
offered. Considering $\\{E(\theta),t(\theta)\\}_{\theta\in\Theta}$ to be the
optimal menu concludes gives us the revenue guarantee. Consider some type
$\theta\in\Theta$. Note that if we let $\delta=\varepsilon/|S^{\prime}|$,
since every column of the experiment consists of $|\Omega|$ entries, we have
that there are at most
$(1/\delta)^{|\Omega|}=O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
different possible columns that we can send to $\theta$. Every such column
induces a posterior distribution for $\theta$, so by querying the BR oracle
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
many times, we find the set of actions $A_{\theta}$ that this type will ever
consider after receiving any of the signals from $S^{\prime}$. $\Box$

So far we have only shown a structural result about the existence of a menu
that uses
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
signals and gives an additive $O(\sqrt{\varepsilon})$-approximation to the
optimal revenue. We now argue that we can use a LP (Figure 2) to find such a
menu. This is done by combining the result of Theorem 3.4 and modifying the LP
we used in Section 3.1.

######  Theorem 3.8.

For any $\varepsilon>0$, any set $\Theta$ of types, given access to a BR
oracle, we can use the LP in Figure 2 to compute a menu $\mathcal{M}$ that
achieves $\textsc{Rev}(\mathcal{M})\geq\text{OPT}-O(\sqrt{\varepsilon})$. The
number of queries to the BR oracle is ${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
and the running time is ${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$.
Moreover, each experiment contains at most
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
many signals, and each type $\theta$ only chooses actions from a set of
actions $A_{\theta}$ with size
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$.

Proof of Theorem 3.8: By Theorem 3.4, we know that we can construct a
collection of actions sets $\\{A_{\theta}\\}_{\theta\in\Theta}$ in time
$O\left(|\Theta|\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
so that there exists a valid IC, IR menu $\mathcal{M}^{\prime}$ that only
recommends actions from $A_{\theta}$ to any type $\theta$. The running time of
this construction and the number of queries to the BR oracle are both
$O\left(|\Theta|\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$.
We assume set $A_{\theta}=\\{a_{\tau_{\theta}(i)}\\}_{i\in[|A_{\theta}|]}$ for
every type $\theta$. Now consider the LP in Figure 2, which is a modified
version of the one in Section 3.1.

First we query BR oracle for every $\theta\in\Theta$ to figure out what
$u(\theta)$ is for every type $\theta$. Since $\mathcal{M}^{\prime}$ is IC and
IR, we know that this menu is a feasible solution for the LP 666Some actions
may not be recommended in the experiment for $\theta$ in
$\mathcal{M}^{\prime}$. Simply set $\pi_{\omega,i}(\theta)$ to $0$ for those
actions.. However, in this case the second set of constraints may contain an
arbitrarily large number of inequalities. Nevertheless, we can construct a
polynomial time Separation Oracle that checks these constraints using the BR
oracle, hence we can solve the LP with the Ellipsoid Algorithm. The Separation
Oracle works as follows. Fix the value of the variables in the LP and consider
two types $\theta,\theta^{\prime}$ and some signal
$s_{i}\in[|A_{\theta^{\prime}}]|$. For the posterior of $\theta$ that this
signal induces, we can query the BR oracle to figure out what the best action
$a_{j}\in A$ is. Hence, we can find the “tightest” constraint regarding the
variable $z_{i}(\theta,\theta^{\prime})$ with one query. Since there are only
$O\left(|\Theta|^{2}\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
such variables, we need that many queries to the BR oracle to check if one of
them is violated. For the other set of constraints, it is easy to check
whether they are violated. So we can solve this LP in time ${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$.
Observe that, as in Theorem 3.3, every feasible point of this LP is a
responsive menu. Moreover, since there exists a feasible point that generates
revenue at least $\text{OPT}-O(\sqrt{\varepsilon})$ we know that every optimal
solution of the LP generates at least this much revenue. $\Box$

Variables: •
$\\{\pi_{\omega,i}(\theta)\\}_{\omega\in\Omega,i\in[|A_{\theta}|],\theta\in\Theta}$,
denoting the experiments in the menu. • $\\{t(\theta)\\}_{\theta\in\Theta}$,
denoting the prices of the experiments. •
$\\{z_{i}(\theta,\theta^{\prime})\\}_{i\in[|A_{\theta^{\prime}}|]\theta,\theta^{\prime}\in\Theta}$,
helper variables. $z_{i}(\theta,\theta^{\prime})$ represents an upper bound of
the conditional expected utility of signal $s_{i}$ from experiment
$E(\theta^{\prime})$ for type $\theta$. Linear Program:
$\begin{array}[]{ll@{}ll}\text{max}&\displaystyle\sum\limits_{\theta\in\Theta}F(\theta)t(\theta)&\\\
\text{s.t.}&\displaystyle\sum\limits_{i\in[|A_{\theta}|]}\displaystyle\sum\limits_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,i}(\theta)u_{\omega,a_{\tau_{\theta}(i)}}-t(\theta)\geq\displaystyle\sum\limits_{i\in[|A_{\theta^{\prime}}|]}z_{i}(\theta,\theta^{\prime})-t(\theta^{\prime}),\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\forall\theta,\theta^{\prime}\in\Theta\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\text{IC})\\\
&z_{i}(\theta,\theta^{\prime})\geq\displaystyle\sum_{\omega}\theta_{\omega}\pi_{\omega,i}(\theta^{\prime})u_{\omega,a_{j}},&\forall\theta,\theta^{\prime}\in\Theta,\forall
i\in[|A_{\theta^{\prime}}|],\forall a_{j}\in A\\\
&\displaystyle\sum\limits_{i\in[|A_{\theta}|]}\displaystyle\sum\limits_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,i}(\theta)u_{\omega,a_{\tau_{\theta}(i)}}-t(\theta)\geq
u(\theta),&\forall\theta\in\Theta\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ (\text{IR})\\\
&\displaystyle\sum\limits_{i\in[|A_{\theta}|]}\pi_{\omega,i}(\theta)=1,&\forall\theta\in\Theta,\omega\in\Omega\\\
&\pi_{\omega,i}(\theta)\geq
0,&\forall\theta\in\Theta,\forall\omega\in\Omega,\forall
i\in[|A_{\theta}|]\end{array}$

Figure 2: A linear program to find an approximately revenue-optimal menu in
the implicit model.

So far, the number of experiments in our constructions depends on the number
of types $|\Theta|$. We show that the number of experiments needed for an up-
to-$\varepsilon$ optimal menu is independent of $|\Theta|$. We achieve this by
dropping experiments that are offered to types who are close in TV-distance.
We show that this leads to a menu that preserves the revenue, is
$O(|\Omega|\varepsilon)$-IC, IR and has
$O\left(\frac{|\Omega|^{2|\Omega|}}{\varepsilon^{|\Omega|}}\right)$ different
experiments. Finally, we apply the $\varepsilon$-IC to IC transformation to
the modified menu.

######  Lemma 3.9.

Let $\mathcal{M}=\\{E(\theta),t(\theta)\\}_{\theta\in\Theta}$ be a menu of
experiments. Then, for any $\theta,\theta^{\prime}\in\Theta$ with
$d_{TV}(\theta,\theta^{\prime})\leq\varepsilon$ it holds that
$V_{\theta}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta}(E({\theta}))-t(\theta)-2|\Omega|\varepsilon$.

Proof of Lemma 3.9: Let $a(s_{k})$ be the action that type $\theta$ takes upon
receiving signal $s_{k}\in S_{\theta^{\prime}}$ from $E(\theta^{\prime})$ and
$a^{\prime}(s_{k})$ the action that $\theta^{\prime}$ takes upon reception of
the same signal. Then we have that

$\displaystyle V_{\theta}(E({\theta^{\prime}}))=\sum_{s_{k}\in
S_{\theta^{\prime}}}\sum_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,k}(E(\theta^{\prime}))u_{\omega,a(s_{k})}\geq\sum_{s_{k}\in
S_{\theta^{\prime}}}\sum_{\omega\in\Omega}\theta_{\omega}\pi_{\omega,k}(E(\theta^{\prime}))u_{\omega,a^{\prime}(s_{k})}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \geq\sum_{s_{k}\in
S_{\theta^{\prime}}}\left(\sum_{\omega\in\Omega}\theta^{\prime}_{\omega}\pi_{\omega,k}(E(\theta^{\prime}))u_{\omega,a^{\prime}(s_{k})}-\varepsilon\cdot\sum_{\omega\in\Omega}\pi_{\omega,k}(E(\theta^{\prime})\right)$
$\displaystyle\implies$ $\displaystyle V_{\theta}(E({\theta^{\prime}}))\geq
V_{\theta^{\prime}}(E({\theta^{\prime}}))-|\Omega|\varepsilon$

Similarly, we have that $V_{\theta^{\prime}}(E({\theta}))\geq
V_{\theta}(E({\theta}))-|\Omega|\varepsilon$.

Since $\mathcal{M}$ is IC, it holds that
$V_{\theta^{\prime}}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta^{\prime}}(E({\theta}))-t(\theta)$. Thus, using the inequalities
above we have that

$V_{\theta^{\prime}}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta^{\prime}}(E({\theta}))-t(\theta)\geq
V_{\theta}(E_{\theta})-t(\theta)-|\Omega|\varepsilon,$

and

$V_{\theta}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta^{\prime}}(E({\theta^{\prime}}))-t(\theta^{\prime})-|\Omega|\varepsilon,$

which implies

$V_{\theta}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta}(E({\theta}))-t(\theta)-2|\Omega|\varepsilon.$

$\Box$

We are now ready to prove that we can create a menu that offers a small number
of experiments and loses negligible revenue compared to OPT. We do that in two
steps, since we are dealing with an action space and type space that are
arbitrary. The first step is to shrink the action space that we are
considering. In order to do that, we use Theorem 3.4 that guarantees the
existence of a menu which loses negligible revenue and only considers actions
from smaller action spaces. The next step is to divide the state space into
regions in which all the types are within $\varepsilon$ in TV-distance. Lemma
3.9 shows us that if we consider offering a single experiment to all the types
in the same region, their values for the new experiment will not change much
compared to the one they were getting. Finally, we apply Lemma 3.7 to solve
the issue that the menu resulting from dropping experiments might not be IC,
IR.

######  Theorem 3.10.

Consider an environment with a type space $\Theta$, action space $A$ and state
space $\Omega$. Then, given some $\varepsilon>0$ and access to a BR oracle we
can find a menu $\mathcal{M}$ that generates revenue at least
$OPT-O(\sqrt{\varepsilon})$ and offers at most
$O\left(\frac{|\Omega|^{2|\Omega|}}{\varepsilon^{|\Omega|}}\right)$
experiments, in time ${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$.

Proof of Theorem 3.10: Let $\varepsilon_{1},\varepsilon_{2}>0$ be some
constants that will be specified later. Also, let $\mathcal{M}^{*}$ be the
optimal menu for this environment. We first observe that Theorem 3.8 shows
that we can get a menu $\mathcal{M}$ that sends at most
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon_{1}^{|\Omega|^{2}+|\Omega|}}\right)$
different signals and generates revenue
$\textsc{Rev}{(\mathcal{M})}\geq\text{OPT}-O(\sqrt{\varepsilon_{1}})$ in time
${\rm
poly}\left(|\Theta|,\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon_{1}^{|\Omega|^{2}+|\Omega|}}\right)$.
The number of experiments that $\mathcal{M}$ offers is at most $|\Theta|$. In
order to get rid of this dependence on $|\Theta|$ we partition the types into
regions in which all the types are within $\varepsilon_{2}$ in TV-distance.
One way to do that is to round every $\theta_{\omega}$ to multiples of
$\varepsilon_{2}/|\Omega|$, so after this step there will be at most
$O\left((|\Omega|/\varepsilon_{2})^{|\Omega|}\right)$ different types. Note
that this guarantees that all the types that are rounded to the same type are
within $\varepsilon_{2}$ TV-distance. Let $\tilde{\Theta}$ be the set of
rounded types. We consider a new menu $\mathcal{M}^{\prime}$ that offers all
the types $\theta\in\Theta$ who are rounded to the same
$\tilde{\theta}\in\tilde{\Theta}$ the most expensive expensive experiment
among $E(\theta)$ at price $t(\theta)$. It is clear that if the types are
willing to buy the experiments that $\mathcal{M}^{\prime}$ offers them then
$\textsc{Rev}{(\mathcal{M}^{\prime})}\geq\textsc{Rev}{(\mathcal{M})}$.
However, it could be the case that they actually deviate and buy some other
experiment in the menu. Consider some type $\theta$ who was getting
$E(\theta)$ from $\mathcal{M}$ and is now getting $E(\theta^{\prime})$ from
$\mathcal{M}^{\prime}$. Lemma 3.9 shows that
$V_{\theta}(E({\theta^{\prime}}))-t(\theta^{\prime})\geq
V_{\theta}(E({\theta}))-t(\theta)-2|\Omega|\varepsilon_{2}$. Moreover, for any
other experiment $E^{\prime\prime}\in\mathcal{M}^{\prime}$ we know that
$V_{\theta}(E^{\prime\prime})-t(E^{\prime\prime})\leq
V_{\theta}(E(\theta))-t(E(\theta))\leq
V_{\theta}(E(\theta^{\prime}))-t(E(\theta^{\prime}))-2|\Omega|\varepsilon_{2}$.
Hence, we see that the IC, IR constraints for $\mathcal{M}^{\prime}$ are
violated by at most $2|\Omega|\varepsilon_{2}$. Now Lemma 3.7 shows how to
modify the prices of $\mathcal{M}^{\prime}$ to create a menu that is exactly
IC, IR and loses at most $O(\sqrt{|\Omega|\varepsilon_{2}})$ revenue compared
to $\mathcal{M}^{\prime}$. We call this new menu $\widetilde{\mathcal{M}}$.
Plugging the values in, we see that
$\textsc{Rev}{(\widetilde{\mathcal{M})}}\geq\text{OPT}-O\left(\sqrt{|\Omega|\varepsilon_{2}}\right)-O(\sqrt{\varepsilon_{1}})$.
Thus, we see that we can set
$\varepsilon_{1}=\varepsilon,\varepsilon_{2}=\frac{\varepsilon}{|\Omega|}$ and
this would guarantee revenue at least $\text{OPT}-O(\sqrt{\varepsilon})$. The
number of signals is
$O\left(\frac{|\Omega|^{|\Omega|^{2}}}{\varepsilon^{|\Omega|^{2}+|\Omega|}}\right)$
and there are
$O\left(\frac{|\Omega|^{2|\Omega|}}{\varepsilon^{|\Omega|}}\right)$ different
experiments. $\Box$

###  3.3 Implicit Model with Succinct Description

In this section, we consider a setting where the model has a succinct implicit
description. We show that no algorithm can obtain even a constant factor
approximation to the optimal revenue for this setting, unless P = NP. To be
more precise, we consider the following problem.

Information Pricing SAT (IP-SAT): find the revenue-optimal menu in the
following setting:

  * •

State space $\Omega$, type space $\Theta$.

  * •

for each state $\omega$, $\Phi_{\omega}$ is a boolean formula in CNF over
variables in $X=\\{x_{1},\ldots,x_{n}\\}$

  * •

Action space $A$: all the possible truth assignments of the variables in $X$

  * •

$u_{\omega,a}=\frac{\text{$\\#$ satisfied clauses of $\Phi_{\omega}$ with
assignment $a$}}{\text{$\\#$ clauses of $\Phi_{\omega}$}}$

IP-SAT is a hard problem for the buyer in general, as maximizing his net
utility requires solving an NP-hard problem. We show here that designing an
approximately revenue-optimal menu for IP-SAT is also computationally
intractable for the seller. Of course, it is not even clear what the optimal
menu looks like in general for IP-SAT as we only have a limited
characterization of the optimal menu. In Theorem 3.11, we construct a special
family of IP-SAT instances with $2$ states and $1$ buyer type, and show how to
reduce SAT to it.

######  Theorem 3.11.

For any constant $\varepsilon>0$, there does not exit a polynomial time
algorithm $\mathcal{A}$ that computes an menu with revenue at least
$(1/2+\varepsilon)\text{OPT}-\frac{\varepsilon}{2m+4}$ in the IP-SAT problem
with $m+2$ clauses, unless $P=NP$.

Proof of Theorem 3.11: Let $\Phi=C_{1}\land\ldots\land C_{m}$ be any SAT
instance over variables $x_{1},\ldots,x_{n}$. We show that given $\mathcal{A}$
we can decide whether $\Phi$ is satisfiable. We create the following IP-SAT
instance: there are two states $\omega_{1},\omega_{2}$, a single type
$\theta=(\frac{1}{2},\frac{1}{2})$ and we set $\Phi_{\omega_{1}}=(C_{1}\lor
y)\land\ldots\land(C_{m}\lor y)\land(x_{1}\lor y)\land(\lnot x_{1}\lor
y),\Phi_{\omega_{2}}=(C_{1}\lor\lnot y)\land\ldots\land(C_{m}\lor\lnot
y)\land(x_{1}\lor\lnot y)\land(\lnot x_{1}\lor\lnot y)$ to be the two SAT
instances with $m+2$ clauses that the buyer faces. At each state, the actions
are the possible assignments of the variables $x_{1},\ldots,x_{n},y$. Let
$\Psi$ be some boolean formula in CNF and $a$ some assignment of its
variables. We define $z_{a}(\Psi)$ to be the number of clauses in $\Psi$ that
$a$ satisfies and $w(\Psi)$ the total number of clauses in $\Psi$. Then, at
each state $\omega$ when the agent chooses assignment $a$ we define his ex-
post utility to be
$u_{\omega,a}=\frac{z_{a}(\Phi_{\omega})}{w(\Phi_{\omega})}$.

From Bergemann et al. [4], we know the optimal menu should contain only the
fully informative experiment $E^{*}$, and the price for this experiment is
$V_{\theta}(E^{*})-u(\theta)$. 777The fully informative experiment simply
sends out a signal to reveal the state. Clearly, $V_{\theta}(E^{*})=1$,
because the buyer can pick $y$ to be $T$ and $F$ in states $\omega_{1}$,
$\omega_{2}$ respectively and satisfy all clauses. We now focus our attention
on $u(\theta)$. Assume that without receiving any information the buyer
decides to set $y=T$. This is w.l.o.g. since it is symmetric with the case he
decides to set $y=F$. When the state is $\omega_{1}$, he satisfies all the
clauses. According to his prior, this happens $1/2$ of the time, so we see
that so far $u(\theta)\geq 1/2$. Let us consider which assignment he should
pick when the state is $\omega_{2}$. Observe that no matter which value he
picks for $x_{1}$, he will always satisfy exactly one of the last two clauses
in $\Phi_{2}$. Hence, for variables $x_{1},\ldots,x_{n}$ he better pick the
assignment $a$ that maximizes $z_{a}(\Phi)$. Let $k=\max_{a}z_{a}(\Phi)$. Then
$u(\theta)=1/2+(k+1)/(2m+4)=\frac{m+k+3}{2m+4}$. Hence, the optimal revenue is
$V_{\theta}(E^{*})-u(\theta)=1-\frac{m+k+3}{2m+4}=\frac{m-k+1}{2m+4}$. If
$\Phi$ is satisfiable, then $k=m$, so $\text{OPT}=\frac{1}{2m+4}$. If $\Phi$
is not satisfiable then $k\leq m-1$ so $\text{OPT}\geq\frac{2}{2m+4}$. Now
assume that there is such an algorithm $\mathcal{A}$ and denote
$\textsc{Rev}(\mathcal{A})$ the revenue generated by the mechanism output by
$\mathcal{A}$. If $\Phi$ is not satisfiable, since
$\text{OPT}\geq\frac{2}{2m+4}$, it must be that
$\textsc{Rev}(\mathcal{A})>\frac{1}{2m+4}$. On the other hand, if $\Phi$ is
not satisfiable we have that $\textsc{Rev}(\mathcal{A})\leq\frac{1}{2m+4}$.
Hence, the existence of $\mathcal{A}$ allows us to distinguish between
satisfiable and unsatisfiable SAT formulas. $\Box$

######  Remark 3.12.

Since $m$ is linear in the description length of the problem, given access to
a BR oracle, for any $\varepsilon>0$ we can set
$\varepsilon^{\prime}=c(m\varepsilon)^{2}$, for some appropriate constant
$c>0$, and then apply Theorem 3.8. Since $|\Omega|=2$ and $|\Theta|=1$, the
revenue we get is at least $\text{OPT}-\varepsilon$ and the running time is
$O\left(\frac{1}{(m\varepsilon)^{10}}\right)$. However, this does not
contradict with the result of Theorem 3.11, since in this setting the BR
oracle solves an NP-hard problem.

##  4 Multi-Agent Setting

In this section, we consider a multi-agent generalization of the model by
Bergemann et al. [4]. More specifically, we assume that there are $n$ buyers
who are interested in acquiring extra information from the seller and each
buyer’s ex-post utility only depends on the state of the world and his own
action. We further assume that the types of the buyers are drawn independently
from their own type distributions. If there is no competition among them, the
solution to the problem follows immediately from the single-agent setting,
since the seller can offer each agent his optimal menu separately. Thus, we
focus on a more interesting case where the buyers are competitors and only one
of them can receive an informative signal.

#### Input Model and New Notation

We first need to introduce some new notation. We use $\Theta^{i}$ to denote
the type space of buyer $i$ and $F^{i}(\theta^{i})$ to denote the probability
that buyer $i$’s type is $\theta^{i}$. We use $\Theta$ to denote the set of
all type profiles and $F(\theta)$ to denote
$\times_{i\in[n]}F^{i}(\theta^{i})$. We assume the action space $A$ is the
same for each buyer $i$, but the ex-post utility $u^{i}_{\omega,a}$ for
choosing action $a$ under state $\omega$ may be different for different
buyers. We consider the _explicit model_ , that is, for each buyer $i$, both
$F^{i}$ and the ex-post utility matrix
$U^{i}=\\{u^{i}_{\omega,a}\\}_{\omega\in\Omega,a\in A}$ are given as input. We
use $u^{i}(\theta^{i})$ to denote the base utility of buyer $i$ for choosing
the best action under distribution $\theta^{i}$.

#### Interaction between the Seller and Buyers

The interaction happens in the following order:

  1. 1.

The seller commits to a mechanism
$\left\\{\left(\Pi(\theta)=\left(\Pi^{1}(\theta),\ldots,\Pi^{n}(\theta)\right)\right\\},\left\\{t(\theta)=\left(t^{1}(\theta),\ldots,t^{n}(\theta)\right)\right)\right\\}_{\theta\in\Theta}$,
and announces the mechanism to all buyers.

  2. 2.

The types of the buyers $\theta=(\theta^{1},\ldots,\theta^{n})$ are realized.

  3. 3.

Each buyer $i$ privately submits his type $\theta^{i}$ to the seller.

  4. 4.

The seller chooses buyer $i$ as the winner with probability $p^{i}(\theta)$.

  5. 5.

The seller observes the state of the world $\omega$ and sends buyer $i$ a
signal $s$ according to the signaling scheme $\Pi^{i}(\theta)$ and charges
buyer $i$ price $t^{i}(\theta)$.

  6. 6.

Each buyer $i$ chooses an action $a^{i}$ and receives ex-post utility
$u^{i}_{\omega,a^{i}}$.

There are some subtle issues in our model that require further clarification.
The most important of them being the following. After the winner has been
chosen, does he observe the signaling scheme $\Pi^{i}(\theta)$ that the seller
uses to generate the signal $s$? In this work, we consider the setting where
the signaling scheme $\Pi^{i}(\theta)$ is not revealed and the winner only
observes the realized signal. 888One may worry that the winner can obtain
extra information from the price $t^{i}(\theta)$. To avoid this, we will
design a mechanism so that the price for buyer $i$ only depends on $i$’s type
$\theta^{i}$. This is without loss of generality, as we can simply set the
price to be $\operatorname*{\mathbb{E}}_{\theta^{-i}}[t^{i}(\theta)]$. Some
remarks are in order. Firstly, the seller may want to preserve the privacy of
the buyers, and revealing $\Pi^{i}(\theta)$ allows the winner $i$ to infer the
other buyers’ priors. Secondly, hiding the implemented signaling scheme
$\Pi^{i}(\theta)$ from the winner allows the seller to design a mechanism with
less stringent IC constraints and thus generates higher revenue for the
seller. This is because the winner does not know the exact experiment he is
getting, if he wants to deviate from the recommendation he must map the same
signal to the same action for all potential experiments that he may win.
Therefore, he would map the signal to an action that induces the highest
_expected utility_ , where the expectation is over the other bidders’ types
and the chosen experiment. On the other hand, if the buyer knew which
experiment the signal is drawn from, he could use a mapping that is the best
for each particular experiment.

Our goal in this section is to design a polynomial time algorithm to find the
Bayesian Incentive Compatible (BIC) and Interim Individually Rational (IIR)
mechanism that achieves the highest revenue among all BIC and IIR mechanisms
for our model. It is not hard to see that Lemma 3.2 generalizes to our multi-
agent setting. We begin by introducing an extension of the LP in Figure 1 to
the multi-agent setting. Define
$\Pi^{i}(\theta)=\left(\pi^{i}_{\omega,j}(\theta)\right)_{\omega\in\Omega,j\in[m]}$,
$p^{i}(\theta)$, and $t^{i}(\theta)$ as the decision variables for every buyer
$i$ and type profile $\theta$. Recall that $m=|A|$.

$\begin{array}[]{ll@{}ll}\text{max}&\displaystyle\sum\limits_{\theta\in\Theta}F(\theta)\displaystyle\sum\limits_{i\in[n]}t^{i}(\theta)&\\\
\text{s.t}\par\par\par\par&\displaystyle\sum\limits_{\theta^{-i}}F^{-i}(\theta^{-i})\left(\displaystyle\sum\limits_{\begin{subarray}{c}\omega\in\Omega,\\\
j\in[m]\end{subarray}}\theta^{i}_{\omega}\pi^{i}_{\omega,j}(\theta^{i},\theta^{-i})u^{i}_{\omega,a_{j}}+(1-p^{i}(\theta))u^{i}(\theta^{i})-t^{i}(\theta^{i},\theta^{-i})\right)\geq\\\
&\displaystyle\sum\limits_{\theta^{-i}}F^{-i}(\theta^{-i})\left(\displaystyle\sum\limits_{j\in[m]}z^{i}_{j}(\theta^{i},\tilde{\theta^{i}},\theta^{-i})+(1-p^{i}(\tilde{\theta^{i}},\theta^{-i}))u^{i}(\theta^{i})-t^{i}(\tilde{\theta^{i}},\theta^{-i})\right),\nobreak\leavevmode\nobreak\leavevmode&\forall
i,\forall\theta^{i},\tilde{\theta}^{i}\leavevmode\nobreak\ (\text{BIC})\\\
&\displaystyle\sum\limits_{\theta^{-i}}F^{-i}(\theta^{-i})z^{i}_{j}(\theta^{i},\tilde{\theta^{i}},\theta^{-i})\geq\displaystyle\sum\limits_{\theta^{-i}}F^{-i}(\theta^{-i})\displaystyle\sum\limits_{\omega}\theta^{i}_{\omega}\pi^{i}_{\omega,j}(\tilde{\theta^{i}},\theta^{-i})u_{\omega,a_{k}},&\forall
i,\forall j,k,\forall\theta^{i},\tilde{\theta^{i}}\\\
&\displaystyle\sum\limits_{\theta^{-i}}F^{-i}(\theta^{-i})\left(\displaystyle\sum\limits_{\begin{subarray}{c}\omega\in\Omega,\\\
j\in[m]\end{subarray}}\theta^{i}_{\omega}\pi^{i}_{\omega,j}(\theta)u_{\omega,a_{j}}+(1-p^{i}(\theta))u^{i}(\theta^{i})-t^{i}(\theta)\right)\geq
u^{i}(\theta^{i}),&\forall i,\theta^{i}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\text{IIR})\\\
&\displaystyle\sum\limits_{j\in[m]}\pi^{i}_{\omega,j}(\theta)=p^{i}(\theta),\qquad\qquad\forall
i,\forall\theta,\forall\omega\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ (\text{feasibility})&\\\
&\displaystyle\sum\limits_{i\in[n]}p^{i}(\theta)\leq 1,\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\qquad\qquad\qquad\forall\theta\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ (\text{feasibility})&\\\ &\pi^{i}_{\omega,j}(\theta)\geq
0,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \qquad\qquad\qquad\forall
i,\forall\theta,\forall\omega,\forall j\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ (\text{feasibility})&\end{array}$

Observe that the number of variables is exponential in $n$ and the number of
constraints is exponential in both $n$ and $m$. There is no hope to solve this
LP in polynomial time. The main challenge is how to remove the exponential
dependence on $n$. To overcome this obstacle, we use a method that is powerful
in the study of multi-item auctions, that is, rewriting the LP using a more
succinct representation of the mechanism known as the reduced form [5, 1, 6,
7, 8]. We first define the reduced form of a mechanism.

######  Definition 4.1 (Reduced Form).

Given a mechanism
$\mathcal{M}=\left(\left\\{\Pi(\theta)\right\\}_{\theta\in\Theta},\\{t(\theta)\\}_{\theta\in\Theta}\right)$,
we define its reduced form
$\left\\{\hat{\Pi}^{i}(\theta^{i})\right\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$,
where
$\hat{\Pi}^{i}(\theta^{i})=\\{\hat{\pi}^{i}_{\omega,j}(\theta^{i})\\}_{\omega\in\Omega,j\in[m]}$
and
$\hat{\pi}^{i}_{\omega,j}(\theta^{i})=\operatorname*{\mathbb{E}}_{\theta^{-i}}[\pi^{i}_{\omega,j}(\theta)]$
for each state $\omega$ and $j\in[m]$, and its interim prices
$\\{\hat{t}^{i}(\theta^{i})\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$, where
$\hat{t}^{i}(\theta^{i})=\operatorname*{\mathbb{E}}_{\theta^{-i}}[t^{i}(\theta)]$.
We use ${\mathcal{P}}(F)$ to denote the set of all reduced forms for a
particular type distribution $F$.

It is not hard to see that ${\mathcal{P}}(F)$ is a closed convex set, as the
set of all mechanisms is clearly closed and convex, and ${\mathcal{P}}(F)$ is
simply a linear transformation of that set. Intuitively, the reduced form is
the “expected experiment and price” that the each buyer believes he will be
allocated when his type is realized, and the expectation is taken over the
randomness of the other buyers’ types.

######  Lemma 4.2.

For any type distribution $F$, ${\mathcal{P}}(F)$ is a closed convex set.

The LP in Figure 3 searches for the reduced form of the revenue-optimal
mechanism. Notice that the size of the reduced-form LP is substantially
smaller than the original one, and the number of variables is polynomial in
the number of agents. With these new variables we can still express the BIC
and IIR constraints of the initial LP. However, it is not yet clear how to
check whether these variables correspond to an actual feasible mechanism. In
the next section, we show how to design a separation oracle that checks the
feasibility efficiently.

Variables: •
$\\{\hat{\pi}^{i}_{\omega,j}(\theta^{i})\\}_{\omega\in\Omega,i\in[n],\theta^{i}\in\Theta^{i},j\in[m]}$,
denoting the reduced form of the mechanism. •
$\\{\hat{t}^{i}(\theta^{i})\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$, denoting
the interim prices. •
$\\{\hat{p}^{i}(\theta^{i})\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$, denoting
the allocation probabilities of the experiment •
$\\{\hat{z}^{i}_{j}(\theta^{i},\tilde{\theta^{i}})\\}_{i\in[n],j\in[m],\theta^{i},\tilde{\theta^{i}}\in\Theta^{i}}$,
helper variables. $\hat{z}^{i}_{j}(\theta^{i},\tilde{\theta^{i}})$ represents
an upper bound of the conditional expected utility of signal $s_{j}$ for type
$\theta^{i}$. Linear Program:
$\begin{array}[]{ll@{}ll}\text{max}&\displaystyle\sum\limits_{i\in[n]}\displaystyle\sum\limits_{\theta^{i}\in\Theta^{i}}F^{i}(\theta^{i})\hat{t}^{i}(\theta^{i})&\\\
\text{subject
to}\par&\displaystyle\sum\limits_{j\in[m]}\displaystyle\sum\limits_{\omega\in\Omega}\theta^{i}_{\omega}\hat{\pi}^{i}_{\omega,j}(\theta^{i})u^{i}_{\omega,a_{j}}+(1-\hat{p}^{i}(\theta^{i}))u^{i}(\theta^{i})-\hat{t}^{i}(\theta^{i})\geq\\\
&\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\
\displaystyle\sum\limits_{j\in[m]}\hat{z}^{i}_{j}(\theta^{i},\tilde{\theta^{i}})+(1-\hat{p}^{i}(\tilde{\theta^{i}}))u^{i}(\theta^{i})-\hat{t}^{i}(\tilde{\theta^{i}}),\nobreak\leavevmode\nobreak\leavevmode\nobreak\leavevmode&\forall
i,\forall\theta^{i},\tilde{\theta}^{i}\leavevmode\nobreak\ (\text{BIC})\\\
&\hat{z}^{i}_{j}(\theta^{i},\tilde{\theta^{i}})\geq\displaystyle\sum\limits_{\omega\in\Omega}\theta^{i}_{\omega}\hat{\pi}^{i}_{\omega,j}(\tilde{\theta^{i}})u^{i}_{\omega,a_{k}}&\forall
i,\forall\theta^{i},\tilde{\theta^{i}},\forall j,k\\\
&\displaystyle\sum\limits_{j\in[m]}\displaystyle\sum\limits_{\omega\in\Omega}\theta^{i}_{\omega}\hat{\pi}^{i}_{\omega,j}(\theta^{i})u^{i}_{\omega,a_{j}}+(1-\hat{p}^{i}(\theta^{i}))u^{i}(\theta^{i})-\hat{t}^{i}(\theta^{i})\geq
u^{i}(\theta^{i}),\nobreak\leavevmode\nobreak\leavevmode&\forall
i,\forall\theta^{i}\leavevmode\nobreak\ (\text{IIR})\\\
&\hat{p}^{i}(\theta^{i})=\displaystyle\sum\limits_{j\in[m]}\hat{\pi}^{i}_{\omega,j}(\theta^{i})&\forall
i,\forall\omega,\forall\theta^{i}\\\
&\\{\hat{\pi}^{i}_{\omega,j}(\theta^{i})\\}_{\omega\in\Omega,i\in[n],\theta^{i}\in\Theta^{i},j\in[m]}\in{\mathcal{P}}(F)&(\text{Feasibility})\end{array}$

Figure 3: A linear program to find the reduced form of the revenue-optimal
mechanism in the multi-agent setting.

###  4.1 Feasibility of Reduced Forms

To design a separation oracle for the set ${\mathcal{P}}(F)$, we invoke the
equivalence between Optimization and Separation in Linear Programming [29,
33], which states that being able to optimize any linear function over a
convex set $P$ is equivalent to having a separation oracle for $P$. It is a
well-known fact that given a separation oracle for $P$ one can optimize any
linear function using the ellipsoid method. Interestingly, the reverse is also
true. If there is an algorithm to optimize any linear function over $P$, one
can construct a separation oracle for $P$ using the ellipsoid method. We state
a strengthened version of the equivalence due to Cai et al. [7]. The reason
that we need to be able to decompose a feasible point into corners of the
polytope is that we eventually need to able to implement the reduced forms as
a feasible mechanism. We elaborate more on this later.

######  Theorem 4.3.

(Adapted from Theorem H.1 of [7]) Let $P$ be a $d$-dimensional closed convex
region, and let $\mathcal{A}$ be any polynomial-time algorithm that takes any
direction ${w}\in\mathbb{R}^{d}$ as input and outputs the extreme point
$\mathcal{A}({w})\in P$ in direction ${w}$ such that
$\mathcal{A}({w})\cdot{w}\geq\cdot\max_{{x}\in P}{x}\cdot{w}$ . Then we can
design a polynomial time separation oracle $SO$ for $P$ such that, whenever
$SO({x})=$ “yes”, the execution of $SO$ explicitly finds directions
${w}_{1},\ldots,{w}_{k}$ such that ${x}$ lies in the convex hull of
$\\{\mathcal{A}({w}_{1}),\ldots,\mathcal{A}({w}_{k})\\}$.

To apply this equivalence, we need to show how we can optimize a linear
function over the set of feasible reduced-form variables. Recall that we use
$\Pi^{i}(\theta)=\left(\pi^{i}_{\omega,j}(\theta)\right)_{\omega\in\Omega,j\in[m]}$
and
$\hat{\Pi}^{i}(\theta^{i})=\left(\hat{\pi}^{i}_{\omega,j}(\theta^{i})\right)_{\omega\in\Omega,j\in[m]}$
to denote the ex-post signaling scheme and its reduced form. We will treat
$\Pi^{i}(\theta)$ and $\hat{\Pi}^{i}(\theta^{i})$ as $m|\Omega|$-dimensional
vectors. The following maximization problem plays a crucial role in our
approach.

######  Definition 4.4.

Consider any type profile $\theta$. Let
$\\{X^{i}(\theta^{i})\\}_{i\in[n],\theta_{i}\in\Theta_{i}}$ be a collection of
$m|\Omega|$-dimensional vectors. We define a Virtual Payoff Maximizer (VPM)
w.r.t. these weight vectors
VPM$(\\{X^{i}(\theta^{i})\\}_{i\in[n],\theta_{i}\in\Theta_{i}})$ to be the ex-
post signaling scheme $\Pi(\theta)$ that maximizes the following quantity
$\sum_{i}\Pi^{i}(\theta^{i})\cdot X^{i}(\theta^{i})$ for every type profile
$\theta$. The corresponding reduced form $\hat{\Pi}(\theta)$ is called
rVPM$(\\{X^{i}(\theta^{i})\\}_{i\in[n],\theta^{i}\in\Theta^{i}})$. In order to
ensure that the maximizer is unique, we break ties lexicographically.

When there is no confusion, we also write $VPM({w}),rVPM({w})$ as the
maximizers for the weight vector ${w}$.

######  Lemma 4.5.

Given an arbitrary collection of weights
$\\{X^{i}(\theta^{i})\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$ we can find the
exact optimal solution of
$\max_{\hat{\Pi}\in{\mathcal{P}}(F)}\sum_{i\in[n]}\sum_{\theta^{i}\in\Theta^{i}}\hat{\Pi}^{i}(\theta^{i})\cdot
X^{i}(\theta^{i})$ in time
$O\left(m|\Omega|\left(\sum_{i\in[n]}|\Theta^{i}|\right)+\left(\sum_{i\in[n]}|\Theta_{i}|\right)^{2}\right)$.

Proof of Lemma 4.5: We first rewrite the maximization problem

$\displaystyle\max_{\hat{\Pi}\in{\mathcal{P}}(F)}\sum_{i\in[n]}\sum_{\theta^{i}\in\Theta^{i}}\hat{\Pi}^{i}(\theta^{i})\cdot
X^{i}(\theta^{i})=\max_{\Pi}\sum_{i,\theta^{i},\theta^{-i}}F^{-i}(\theta^{-i})\Pi^{i}(\theta^{i},\theta^{-i})\cdot
X^{i}(\theta^{i})=$
$\displaystyle\max_{\Pi}\sum_{i,\theta}F(\theta)\Pi^{i}(\theta)\cdot\frac{X^{i}(\theta^{i})}{F^{i}(\theta^{i})}=\max_{\Pi}\sum_{\theta}F(\theta)\sum_{i}\Pi^{i}(\theta)\cdot\tilde{X}^{i}(\theta^{i}),$

where $\tilde{X}^{i}(\theta^{i})=\frac{X^{i}(\theta^{i})}{F^{i}(\theta^{i})}$.

Let $\theta$ be a type profile. We now characterize the solution of
$\max_{\Pi(\theta)}\sum_{i}\Pi^{i}(\theta)\cdot\tilde{X}^{i}(\theta^{i})$. If
we allocate the experiment to buyer $i$, the maximum value we can derive is
$v^{i}(\theta^{i})=\sum_{\omega}\max_{a}\tilde{X}^{i}_{\omega,a}(\theta^{i})$.
Clearly, the optimal solution of the linear function above is to always
allocate the experiment to the buyer with the largest $v^{i}(\theta^{i})$.

The ex-post signaling scheme that maximizes
$\sum_{\theta}F(\theta)\sum_{i}\Pi^{i}(\theta)\cdot\tilde{X}^{i}(\theta^{i})$
is the one that always allocates the experiment to the buyer with the largest
$v^{i}(\theta^{i})$ for every type profile $\theta$. To solve
$\max_{\hat{\Pi}\in{\mathcal{P}}(F)}\sum_{i\in[n]}\sum_{\theta^{i}\in\Theta^{i}}\hat{\Pi}^{i}(\theta^{i})\cdot
X^{i}(\theta^{i})$, we only need to calculate the reduced form of this ex-post
signaling scheme and we denote it using $\hat{\Pi}_{*}$

We first compute
$v^{i}(\theta^{i})=\sum_{\omega}\max_{a}x^{i}_{\omega,a}(\theta^{i})$ for
every buyer $i$ and every type $\theta^{i}$. This step takes time
$O\left(m|\Omega|\left(\sum_{i\in[n]}|\Theta^{i}|\right)\right)$, and there
are $\sum_{i\in[n]}|\Theta^{i}|$ different such values. Next, for each buyer,
we sort $v^{i}(\theta^{i})$. This step takes time
$O\left(\sum_{i\in[n]}|\Theta^{i}|\log|\Theta^{i}|\right)$. To compute
$\hat{\Pi}_{*}^{i}(\theta^{i})$, we only need to calculate the probability of
the event that over the random draws of $\theta_{-i}$, there exists another
buyer $\ell\neq i$ either $v_{\ell}(\theta^{\ell})>v^{i}(\theta^{i})$ or
$\ell<i$ and $v_{\ell}(\theta^{\ell})=v^{i}(\theta_{i})$. This probability can
be computed in time $O\left(\sum_{i\in[n]}|\Theta^{i}|\right)$ for each buyer
$i$ and type $\theta^{i}$. Hence, in total we can optimize the linear function
in time
$O\left(m|\Omega|\left(\sum_{i\in[n]}|\Theta^{i}|\right)+\left(\sum_{i\in[n]}|\Theta_{i}|\right)^{2}\right)$.

$\Box$

Combining Theorem 4.3 and Lemma 4.5, we have a polynomial time algorithm to
solve the LP in Figure 3, but we still need to turn the reduced form into an
ex-post signaling scheme. We again use an idea from computing the optimal
multi-item auctions, that is, first decomposing the optimal reduced form into
a distribution over extreme points of ${\mathcal{P}}(F)$, then implementing
all the extreme points that appear in the distribution using a VPM ex-post
signaling scheme.

######  Theorem 4.6.

We design an algorithm to compute the revenue-optimal mechanism in time ${\rm
poly}\left(n,m,|\Omega|,\sum_{i\in[n]}|\Theta^{i}|\right)$. Moreover, the
mechanism can be implemented as a distribution over
$m|\Omega|\left(\sum_{i\in[n]}|\Theta^{i}|\right)+1$ VPM ex-post signaling
schemes.

Proof of Theorem 4.6: Combining Theorem 4.3 and Lemma 4.5, we have a
polynomial time algorithm to solve the LP in Figure 3. Let
$\Pi_{*}=\left\\{\hat{\Pi}_{*}^{i}(\theta^{i})\right\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$
be the optimal reduced form and
$\left\\{\hat{t}_{*}^{i}(\theta^{i})\right\\}_{i\in[n],\theta^{i}\in\Theta^{i}}$
be the optimal interim prices. Since the SO must return “yes” on $\Pi_{*}$, as
guaranteed by Theorem 4.3, the SO also finds a collection of directions
$w_{1},\ldots,w_{k}$ so that $\Pi_{*}$ lies in the convex hull of
$rVPM(w_{1}),\ldots,rVPM(w_{k})$. Due to the Carathéodory’s theorem, we can
decompose $\Pi_{*}$ into a distribution $D$ over at most
$m|\Omega|\left(\sum_{i\in[n]}|\Theta^{i}|\right)+1$ of the above rVPMs.
Moreover, we can use a LP to find this distribution in polynomial time. To
implement $\Pi_{*}$, we first sample a $rVPM(w)$ from the distribution $D$,
and implement the corresponding ex-post signaling scheme $VPM(w)$. Finally,
for each buyer $i$, we charge him $\hat{t}^{i}(\theta^{i})$ if he reports
$\theta^{i}$, so the mechanism is BIC and IIR, and we do not reveal extra
information through the prices. $\Box$

##  5 Further Extensions and Future Directions

In this section, we discuss further generalizations of the model by Bergemann
et al. [4] and future research directions that we believe are interesting to
pursue.

###  5.1 Extensions of the Original Model

#### Enlarged Buyer Type:

Recall that in the original model the only private information of the buyer is
his private belief of the underlying state, which is realized at the beginning
of the interaction with the seller. Importantly, the payoffs are public
knowledge and remain the same across different buyers. A natural
generalization one can consider is to allow the buyer to draw not only his
prior belief $\theta$, but also his payoff function $u:\Omega\times
A\rightarrow[0,1]$ from some distribution.

To be more specific, we consider the setting where a buyer’s type
$\rho=(\theta,u)$ is drawn from some distribution $F$ at the beginning of the
interaction between the buyer and the seller, and $\rho$ is private to the
buyer. As in the original model, we assume that the seller has access to this
distribution. We remark that all of our positive results from Section 3 and
Section 4, except for Theorem 3.10, hold in this extended model as well. The
only difference in our constructions is that instead of indexing the variables
by $\theta$ we now index them by $\rho$.

#### Misspecified Model:

Another generalization we consider in the single-agent setting is the
misspecified model. In this model the seller has access to some type
distribution $\tilde{F}$ which is within $\varepsilon$ in TV-distance with the
real type distribution $F$. Moreover, the seller has access to a type space
$\tilde{\Theta}$ with the following two properties:
$|\tilde{\Theta}|=|\Theta|$, for all $\tilde{\theta}\in\tilde{\Theta}$ there
is some $\theta\in\Theta$ for which
$d_{TV}(\tilde{\theta},\theta)\leq\varepsilon$. Then, the menu that the seller
designs for the misspecified distributions can be modified so that it
guarantees only a negligible revenue loss when it is evaluated in the true
setting. Lemma 5.1 formalizes this claim.

######  Lemma 5.1.

Let $\tilde{F},F$ be the distributions of the types that the seller has access
to and the true distribution of the types, respectively. Let also
$\\{\tilde{\theta}_{i}\\}_{i\in[k]},\\{\theta_{i}\\}_{i\in[k]}$ be the types
that the seller has access to and the true types, respectively. Assume that
$d_{TV}(\tilde{F},F)\leq\varepsilon_{1},d_{TV}(\tilde{\theta_{i}},\theta_{i})\leq\varepsilon_{2},\forall
i\in[k]$. We also let
$\widetilde{\mathcal{M}}=\\{\tilde{E}(\tilde{\theta}_{i}),\tilde{t}(\tilde{\theta}_{i})\\}_{i\in[k]}$
be an IC, IR menu that has revenue $\textsc{Rev}(\widetilde{\mathcal{M}})$
under the misspecified distributions and uses at most $|S|$ signals. Then, we
can compute a set of prices $\\{t(\tilde{\theta}_{i})\\}_{i\in[k]}$ so that
$\mathcal{M}=\\{\tilde{E}(\theta_{i}),t(\theta_{i})\\}_{i\in[k]}$ is IR, IC
and has
$\textsc{Rev}(\mathcal{M})\geq\textsc{Rev}(\widetilde{\mathcal{M}})-O\left(\varepsilon_{1}+\sqrt{|\Omega|\varepsilon_{2}}\right)$
under the true distributions.

Proof of Lemma 5.1: We first show that $\widetilde{\mathcal{M}}$ violates the
IC, IR constraints by at most $2|\Omega|\varepsilon_{2}$. Consider a type
$\tilde{\theta}$ who buys $E$, but the true type $\theta$ prefers $E^{\prime}$
over $E$. Then, by Lemma 3.9, $V_{\theta}(E)-\tilde{t}(E)\geq
V_{\theta}(E^{\prime})-\tilde{t}(E^{\prime})-2|\Omega|\varepsilon_{2}$. Hence,
by Lemma 3.7 we know that we can compute a new set of prices in time
$O(|\widetilde{\mathcal{M}}|)$ losing at most
$O(\sqrt{|\Omega|\varepsilon_{2}})$ revenue. Moreover, since the seller’s
distribution over the types is also misspecified we have

$\displaystyle\sum_{\theta}\left(\tilde{F}(\theta)-F(\theta)\right)t(\theta)\leq
2\varepsilon_{1}\implies\sum_{\theta}F(\theta)t(\theta)\geq\sum_{\theta}\tilde{F}(\theta)t(\theta)-2\varepsilon_{1}\geq$
$\displaystyle\sum_{\tilde{\theta}}\tilde{F}(\tilde{\theta})\tilde{t}(\tilde{\theta})-2\varepsilon_{1}-O(\sqrt{|\Omega|\varepsilon_{2}})$

$\Box$

Note that Lemma 5.1 allows us to generalize our results and obtain
approximately-optimal menus when we only have black-box access to the
distribution of the types. That is, we take enough samples to learn the
distribution within Total Variation distance $\varepsilon$ and then apply
Lemma 5.1.

###  5.2 Future Directions

We believe that the design of Information Markets is a very important problem
that has not received sufficient attention by the Theory of Computation
community. There are many interesting questions waiting be addressed.

  1. 1.

In the single-buyer setting where we only have access to the action space via
a BR oracle the running time of our algorithms is exponential in the number of
states. An immediate question to ask is whether we can get an FPTAS or even a
PTAS that has a better dependence on the number of states.

  2. 2.

In the multi-agent setting, we consider the case in which the seller does not
reveal the signaling scheme that she uses to send a signal to the winner. An
interesting question is whether we can have efficient algorithms in the
setting where the seller reveals the signaling scheme to the buyer.

  3. 3.

Currently, in the multi-agent setting we assume that the ex-post utility of
each buyer depends only on the state of the world and the action he takes. Is
the problem of designing the optimal mechanism when the ex-post utilities also
depend on the actions of the other buyers tractable?

## References

  * [1] Saeed Alaei, Hu Fu, Nima Haghpanah, Jason Hartline, and Azarakhsh Malekian.  Bayesian Optimal Auctions via Multi- to Single-agent Reduction.  In the 13th ACM Conference on Electronic Commerce (EC), 2012.
  * [2] Moshe Babaioff, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg.  A Simple and Approximately Optimal Mechanism for an Additive Buyer.  In the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014.
  * [3] Moshe Babaioff, Robert Kleinberg, and Renato Paes Leme.  Optimal mechanisms for selling information.  In Proceedings of the 13th ACM Conference on Electronic Commerce, pages 92–109, 2012.
  * [4] Dirk Bergemann, Alessandro Bonatti, and Alex Smolin.  The design and price of information.  American economic review, 108(1):1–48, 2018.
  * [5] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  An Algorithmic Characterization of Multi-Dimensional Mechanisms.  In the 44th Annual ACM Symposium on Theory of Computing (STOC), 2012\.
  * [6] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization.  In the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2012.
  * [7] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  Reducing Revenue to Welfare Maximization : Approximation Algorithms and other Generalizations.  In the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.
  * [8] Yang Cai, Constantinos Daskalakis, and S. Matthew Weinberg.  Understanding Incentives: Mechanism Design becomes Algorithm Design.  In the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2013.
  * [9] Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg.  A duality based unified approach to bayesian mechanism design.  In the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016\.
  * [10] Yang Cai, Federico Echenique, Hu Fu, Katrina Ligett, Adam Wierman, and Juba Ziani.  Third-party data providers ruin simple mechanisms.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 4(1):1–31, 2020.
  * [11] Yang Cai, Argyris Oikonomou, Grigoris Velegkas, and Mingfei Zhao.  An efficient epsilon-bic to bic transformation and its application to black-box reduction in revenue maximization.  In the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.  URL: https://arxiv.org/abs/1911.10172.
  * [12] Yang Cai and Mingfei Zhao.  Simple mechanisms for subadditive buyers via duality.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 170–183, 2017.  URL: http://doi.acm.org/10.1145/3055399.3055465, doi:10.1145/3055399.3055465.
  * [13] Shuchi Chawla, Jason D. Hartline, and Robert D. Kleinberg.  Algorithmic Pricing via Virtual Valuations.  In the 8th ACM Conference on Electronic Commerce (EC), 2007.
  * [14] Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan.  Multi-Parameter Mechanism Design and Sequential Posted Pricing.  In the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
  * [15] Yiling Chen, Haifeng Xu, and Shuran Zheng.  Selling information through consulting.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2412–2431. SIAM, 2020.
  * [16] Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, and Shang-Hua Teng.  Mixture selection, mechanism design, and signaling.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1426–1445. IEEE, 2015.
  * [17] Jacques Cremer and Richard P. McLean.  Full extraction of the surplus in bayesian and dominant strategy auctions.  Econometrica, 56(6):1247–1257, 1988.
  * [18] Constantinos Daskalakis, Alan Deckelbaum, and Christos Tzamos.  Strong duality for a multiple-good monopolist.  Econometrica, 85(3):735–767, 2017.
  * [19] Constantinos Daskalakis, Christos Papadimitriou, and Christos Tzamos.  Does information revelation improve revenue?  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 233–250. ACM, 2016.
  * [20] Constantinos Daskalakis and S. Matthew Weinberg.  Symmetries and Optimal Multi-Dimensional Mechanism Design.  In the 13th ACM Conference on Electronic Commerce (EC), 2012.
  * [21] Nikhil Devanur, Kira Goldner, Raghuvansh Saxena, Ariel Schvartzman, and S Matthew Weinberg.  Optimal mechanism design for single-minded agents.  arXiv preprint arXiv:2002.06329, 2020.
  * [22] Nikhil R Devanur and S Matthew Weinberg.  The optimal mechanism for selling to a budget constrained buyer: The general case.  In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 39–40, 2017.
  * [23] Shaddin Dughmi.  On the hardness of signaling.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 354–363. IEEE, 2014.
  * [24] Shaddin Dughmi, Nicole Immorlica, and Aaron Roth.  Constrained signaling in auction design.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1341–1357. Society for Industrial and Applied Mathematics, 2014.
  * [25] Shaddin Dughmi and Haifeng Xu.  Algorithmic bayesian persuasion.  In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 412–425. ACM, 2016.
  * [26] Amos Fiat, Kira Goldner, Anna R Karlin, and Elias Koutsoupias.  The fedex problem.  In Proceedings of the 2016 ACM Conference on Economics and Computation, pages 21–22, 2016.
  * [27] Yiannis Giannakopoulos and Elias Koutsoupias.  Duality and optimality of auctions for uniform distributions.  In ACM Conference on Economics and Computation, EC ’14, Stanford , CA, USA, June 8-12, 2014, pages 259–276, 2014.  URL: http://doi.acm.org/10.1145/2600057.2602883, doi:10.1145/2600057.2602883.
  * [28] Yiannis Giannakopoulos and Elias Koutsoupias.  Selling two goods optimally.  In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, pages 650–662, 2015.  URL: http://dx.doi.org/10.1007/978-3-662-47666-6_52, doi:10.1007/978-3-662-47666-6_52.
  * [29] Martin Grötschel, László Lovász, and Alexander Schrijver.  The Ellipsoid Method and its Consequences in Combinatorial Optimization.  Combinatorica, 1(2):169–197, 1981.
  * [30] Nima Haghpanah and Jason D. Hartline.  Reverse mechanism design.  CoRR, abs/1404.1341, 2014.  URL: http://arxiv.org/abs/1404.1341.
  * [31] Sergiu Hart and Noam Nisan.  Approximate Revenue Maximization with Multiple Items.  In the 13th ACM Conference on Electronic Commerce (EC), 2012.
  * [32] Emir Kamenica and Matthew Gentzkow.  Bayesian persuasion.  American Economic Review, 101(6):2590–2615, 2011.
  * [33] Richard M. Karp and Christos H. Papadimitriou.  On linear characterizations of combinatorial optimization problems.  SIAM J. Comput., 11(4):620–632, 1982.  URL: http://dx.doi.org/10.1137/0211053, doi:10.1137/0211053.
  * [34] Xinye Li and Andrew Chi-Chih Yao.  On revenue maximization for selling multiple independently distributed items.  Proceedings of the National Academy of Sciences, 110(28):11232–11237, 2013.
  * [35] Roger B. Myerson.  Optimal Auction Design.  Mathematics of Operations Research, 6(1):58–73, 1981.
  * [36] John Riley and Richard Zeckhauser.  Optimal selling strategies: When to haggle, when to hold firm.  The Quarterly Journal of Economics, 98(2):267–289, 1983.
  * [37] Andrew Chi-Chih Yao.  An n-to-1 bidder reduction for multi-item auctions and its applications.  In SODA, 2015.  URL: http://arxiv.org/abs/1406.3278.