Public Signaling in Bayesian Ad Auctions

1 Introduction

Nowadays, worldwide spending in digital advertising is skyrocketing, and this growth is primarily driven by ad auctions. These account for almost all market share, since they are at the core of popular advertising platforms, such as, e.g., those by Google, Amazon, and Facebook. According to a recent report by eMarketer [2021], digital ad spending will reach over $490 billion in 2021 and zoom past half a trillion in 2022.

We study signaling in ad auction settings by means of the Bayesian persuasion framework [Kamenica and Gentzkow, 2011]. Over the last years, this framework has received considerable attention from the computer science community, due to its applicability to many real-world scenarios, such as, e.g., online advertising [Bro Miltersen and Sheffet, 2012], voting [Alonso and Cˆamara, 2016; Cheng et al., 2015; Castiglioni et al., 2020a; Castiglioni and Gatti, 2021], traffic routing [Vasserman et al., 2015; Bhaskar et al., 2016; Castiglioni et al., 2021a], recommendation systems [Mansour et al., 2016], security [Rabinovich et al., 2015; Xu et al., 2016], and product marketing [Babichenko and Barman, 2017; Candogan, 2019]. Some recent works also addressed the problem of dealing with uncertain parameters in Bayesian persuasion, boosting its applicability [Castiglioni et al., 2020c; Castiglioni et al., 2021b; Zu et al., 2021; Babichenko et al., 2021; Castiglioni et al., 2022a].

In a standard ad auction, the advertisers (also called bidders) compete for displaying their ads on a limited number of slots, and each bidder has their own private valuation representing how much they value a click on their ad. In this work, we study Bayesian ad auctions, which are characterized by the fact that bidders' valuations depend on a random, unknown state of nature. The auction mechanism has complete knowledge of the actual state of nature, and it can send signals to bidders so as to disclose information about the state and increase revenue. In particular, the auction mechanism commits to a signaling scheme, which is defined as a randomized mapping from states of nature to signals being sent to the bidders. Our model fits many real-world applications that are not captured by classical ad auctions. For instance, a state of nature may collectively encode some features of the user visualizing the ads-such as, e.g., age, gender, or geographical region-that are known to the mechanism only, since the latter has access to data sources unaccessible to the bidders.

We study the problem of computing a revenue-maximizing signaling scheme for the mechanism. In particular, we focus on public signaling, in which the mechanism can only send a single signal that is observed by all the bidders. Moreover, we restrict our attention to VCG mechanisms, which are widely used in practice and have the appealing property of inducing bidders to truthfully report their valuations. While the signaling problem studied in this paper has already been addressed in the easier setting of second-price auctions, to the best of our knowledge, our work is the first to explore algorithmic signaling in general ad auctions with more than one slot.

1.1 Original Contributions

We start with a negative result, showing that, in general, the revenue-maximizing problem with public signaling does not admit a PTAS unless P = NP, even when bidders' valuations are known to the mechanism. Thus, we address settings in which such a negative result can be circumvented.

First, we show that, in the known valuations setting, the problem admits a polynomial-time algorithm when either the number of slots m or the number of states d is fixed. The proposed algorithms work by solving suitably-defined linear programs (LPs) of polynomial size, thanks to the crucial property that, when either m or d is fixed, there always exists an optimal signaling scheme using a polynomial number of different signals. Moreover, we also study special instances in which the bidders are single minded, but m and d can be arbitrary. In this case, each bidder positively values a click on their ad only when the actual state of nature is a specific (single) state, and all the bidders interested in the same state value a click on their ad for the same amount. By exploiting a particular combinatorial structure of the set of bidders' posterior distributions induced by signaling schemes, we are able to provide an FPTAS in such setting. The algorithm works by applying the ellipsoid method in a non-trivial way, with only access to an approximate polynomial-time separation oracle. The latter is implemented by a rather involved dynamic programming algorithm, which works thanks to the particular structure of the set of bidders' posteriors.

Then, we switch the attention to the random valuations setting, where bidders' valuations are unknown to the mechanism, but randomly drawn according to some probability distribution. In this case, we first provide some preliminary results that establish useful connections between the optimal value of the revenue-maximizing problem and that of optimal signaling schemes restricted to suitably-defined finite sets of posterior distributions. These sets are defined so that the expected revenue of the mechanism is "stable", meaning that it does not decrease too much when restricting signaling schemes to use posteriors in such sets. In particular, for our results we use sets of q-uniform posteriors, for suitable values of q. As a preliminary step, we also show that it is possible to compute an approximately-optimal signaling scheme having only access to a finite number of samples from the distribution of bidders' valuations. In conclusion, all the preliminary results described so far allow us to prove that, in the random valuations setting, the problem admits an FPTAS, a PTAS, and a QPTAS, when, respectively, d is fixed, m is fixed, and bidders' valuations are bounded away from zero. 1

1.2 RelatedWorks

To the best of our knowledge, the algorithmic study of signaling in auctions is limited to the second-price auction, which can be seen as a special ad auction with a single slot (with the only exception of [Castiglioni et al., 2022b], which studies signaling in posted price auctions).

1 All the proofs are in [Bacchiocchi et al., 2022].

[Emek et al. 2014] study second-price auctions in the known valuations setting. They provide an LP to compute an optimal public signaling scheme. Moreover, they show that it is NP-hard to compute an optimal signaling scheme in the random valuations setting. In our work, we generalize their positive result, in order to provide our polynomial-time algorithm working when the number of slots m is fixed.

[Cheng et al. 2015] complement the hardness result of [Emek et al., 2014] by providing a PTAS for the random valuations setting. This result cannot be extended to ad auctions, as we show in our first negative result. However, we provide two generalizations of the result by [Cheng et al. 2015]: we provide a PTAS for the random valuations setting with a fixed number of slots m, and a QPTAS when the bidder's valuations are bounded away from zero.

Finally, [Badanidiyuru et al. 2018] study algorithms whose running time does not depend on the number of states of nature. Moreover, they initiate the study of private signaling schemes, showing that, in second-price auctions, private signaling introduces non-trivial equilibrium selection problems.

In conclusion, there are some works that, while addressing problems different from our problem, are strictly related to it. In particular, [Daskalakis et al., 2016] studies how to jointly optimize the auction mechanism and the signaling scheme, while [Fu et al., 2012; Li and Das, 2019] provide a quantitative analysis on how revealing information increases revenue.

2 Preliminaries

In a standard ad auction [Nisan and Ronen, 2001], there is a set N := {1, . . . , n} of advertisers (or bidders) who compete for displaying their ads on a set M := {1, . . . ,m} of slots, with m ≤ n. Each bidder i ∈ N is characterized by a private valuation vi ∈ [0, 1], which represents how much they value a click on their ad. Moreover, each slot j ∈ M is associated with a click through rate parameter λj ∈ [0, 1], which is the probability with which the slot is clicked by a user. W.l.o.g., we assume that the slots are ordered so that λ1 ≥ . . . ≥ λm. The auction goes on as follows: first, each bidder i ∈ N separately reports a bid bi ∈ [0, 1] to the auction mechanism; then, based on the bids, the latter allocates an ad to each slot and defines how much each bidder has to pay the mechanism for a click on their ad. We focus on truthful mechanisms, and the VCG mechanism in particular. In truthful mechanisms, allocation and payments are defined so that it is a dominant strategy for each bidder to report their true valuation to the mechanism, namely bi = vi for every i ∈ N. In particular, the allocation implemented by the VCG mechanism orderly assigns the first m bidders in decreasing value of bi to the first m slots (those with the highest click through rates). At the same time, assuming w.l.o.g. that bidder i is assigned to slot i, the mechanism defines an expected payment pi := ∑m+1 j=i+1 bj(λj-1-λj) for each bidder i ∈ {1, . . . ,m}, where, for the ease of notation, we let λm+1 = 0. The payment is zero for all the other bidders. In practice, each bidder i ∈ {1, . . . ,m} has to pay pi λi whenever a user clicks on their ad, so that their utility is λivi - pi in expectation over the clicks. The expected utility of all the other bidders is zero. We study Bayesian ad auctions, which are characterized by a set Θ := {θ1, . . . , θd} of d states of nature. Each bidder i ∈ N has a valuation vector vi ∈ [0, 1]d , with vi(θ) being bidder i's valuation in state θ ∈ Θ, and all such vectors are arranged in a matrix of bidders' valuations V ∈ [0, 1]n×d , whose entries are defined as V (i, θ) := vi(θ) for all i ∈ N and θ ∈ Θ. We model signaling by means of the Bayesian persuasion framework [Kamenica and Gentzkow, 2011]. We consider the case in which the auction mechanism knows the state of nature and acts as a sender by issuing signals to the bidders (the receivers), so as to partially disclose information about the state and increase revenue. As customary, we assume that the state is drawn from a common prior distribution µ ∈ ∆Θ, with µθ being the probability of θ ∈ Θ. 2 The mechanism publicly commits to a signaling scheme φ, which is a randomized mapping from states of nature to signals for the bidders. We focus on the public signaling case, where all the bidders receive the same signal. Formally, a signaling scheme is a function φ : Θ → ∆S, where S is a set of available signals. For the ease of notation, we let φθ(s) be the probability of sending signal s ∈ S when the state is θ ∈ Θ.

A Bayesian ad auction goes on as follows (Figure 1): (i) the auction mechanism commits to a signaling scheme φ, and the bidders observe it; (ii) the mechanism gets to know the state of nature θ ∼ µ and draws signal s ∼ φ(θ); and (iv) the bidders observe the signal s and rationally update their prior belief over states according to Bayes rule. After observing s ∈ S, all the bidders infer a posterior distribution ξs ∈ ∆Θ over state such that the posterior probability of state θ ∈ Θ is

Finally, each bidder i ∈ N truthfully reports to the mechanism their expected valuation given the posterior ξs, namely ξ⊤ s vi = ∑θ∈Θ vi(θ) ξs(θ), and the mechanism allocates slots and defines payments as in a standard ad auction. 3

Representing Signaling Schemes. It is oftentimes useful to represent signaling schemes as convex combinations of the posteriors they can induce [Dughmi, 2014; Cheng et al., 2015]. Formally, a signaling scheme φ : Θ → ∆S induces a probability distribution γ over posteriors in ∆Θ, with γ(ξ) denoting the probability of posterior ξ ∈ ∆Θ, defined as

2 Given a finite set X, we denote with ∆X the (|X| - 1)- dimensional simplex defined over the elements of X.

3 Given that all the bidders share the same posterior, the induced auction is equivalent to a classical VCG ad auction. Thus, truthfully reporting expected valuations is a dominant strategy for the bidders.

Indeed, we can directly reason about distributions γ over ∆Θ rather than about signaling schemes, provided that they are consistent with the prior. By letting supp(γ) := {ξ ∈ ∆Θ | γ(ξ) > 0} be the support of γ, this requires that

In the rest of the paper, we will use the term signaling scheme to refer to a consistent distribution γ over ∆Θ.

Computational Problems. We focus on the problem of computing an optimal signaling scheme, i.e., one maximizing the revenue of the mechanism. We study two settings:

• the known valuations (KV) setting inwhich thematrix of bidders' valuations V is known to the mechanism; and
• the random valuations (RV) setting in which the matrix of bidders' valuations V is unknown, but randomly drawn according to a probability distribution V.

As it is customary in the literature (see, e.g., [Badanidiyuru et al., 2018]), in the RV setting we assume that algorithms have access to a black-box oracle returning i.i.d. samples drawn from V (rather than actually knowing such distribution). We denote by REV(V, ξ) the expected revenue of the mechanism when the bidders' valuations are given by V and the posterior induced by the mechanism is ξ ∈ ∆Θ. Formally, given that bidders truthfully report their expected valuations and assuming w.l.o.g. that bidder i is assigned by the mechanism to slot i, we can write REV(V, ξ) := ∑mj=1 j ξ⊤vj+1(λj - λj+1). Then, given a signaling scheme γ, the expected revenue of the mechanism is ∑ξ∈supp(γ) γ(ξ) REV(V, ξ). When the valuations are unknown, we let REV(V, ξ) := EV∼VREV(V, ξ) and define the expected revenue analogously. Notice that, given a distribution of valuations V (or, in the KV setting, a matrix of bidders' valuations V ) and a finite set Ξ ⊆ ∆Θ of posteriors, it is possible to formulate the problem of computing an optimal signaling scheme as an LP, as follows: 4

In the following, we let OPTΞ be the optimal value of LP 3, while we denote with OPT the optimal expected revenue of the mechanism over all the possible signaling schemes γ. 5

3 AGeneral Inapproximability Result

We start our analysis with the following negative result:

Theorem 1. The problem of computing an optimal signaling scheme does not admit a PTAS unless P = NP, even when it is restricted to the KV setting.

4 LP 3 is written for the RV setting, its analogous for the KV setting can be obtained by substituting REV(V, ξ) with REV(V, ξ).

5 The dependence of OPTΞ and OPT from either V or V is omitted, as it will be clear from context.

Theorem 1 is proved by a reduction from the VERTEX COVER problem in cubic graphs [Alimonti and Kann, 2000]. In the rest of this work, we study several settings in which the negative result in Theorem 1 can be circumvented, by either fixing some parameters of the problem (see Sections 4 and 6.1) or considering instances with a specific structure (see Sections 5 and 6.2).

4 KV Setting: Parametrized Complexity

In this section, we study the parametrized complexity of the problem of computing an optimal signaling scheme, showing that it admits a polynomial-time algorithm when either the number of slots m or the number of states of nature d is fixed.

In the following, we let Πl ⊆ 2N be the set of all the the possible permutations of l ≤ n bidders taken from N, with π = (i1, ..., il) ∈ Πl denoting a tuple made by bidders i1, . . . , il ∈ N, in that order. We also let Ξπ ⊆ ∆Θ be the (possibly empty) polytope of posteriors in which the expected valuations of bidders in π ∈ Πl are ordered (from the highest to the lowest) according to π; formally, it holds Ξπ := {ξ ∈ ∆Θ | ξ⊤vi1 ≥ ξ⊤vi2 ≥ . . . ≥ ξ⊤vil }. Notice that, given a permutation π ∈ Πl of l ≥ m+1 bidders, the expected revenue of the mechanism in any posterior ξ ∈ Ξπ is REV(V, ξ) := ∑mj=1 j ξ⊤vj+1(λj -λj+1), since the bidders truthfully report their expected valuations to the mechanism, and, thus, the latter allocates slots to bidders in π according to their order in the permutation. Thus, for any fixed π ∈ Πl with l ≥ m+ 1, the term REV(V, ξ) is linear in ξ over Ξπ.

4.1 Fixing the Number of Slots m

In this case, the problem can be solved in polynomial time by formulating it as an LP, thanks to the following lemma:

Lemma 1. There always exists an optimal signaling scheme γ such that |Ξπ ∩ supp(γ)| ≤ 1 for every π ∈ Πm+1.

Intuitively, the lemma follows from the fact that, given any signaling scheme γ and two posteriors ξ, ξ ′ ∈ supp(γ) such that ξ, ξ ′ ∈ Ξπ for some π ∈ Πm+1, it is always possible to define a new signaling scheme that replaces ξ and ξ ′ with a suitably-defined convex combination of them, without decreasing the expected revenue (since it is linear over Ξπ).

By Lemma 1, we can re-write the revenue maximization problem as max ∑π∈Πm+1 γ(ξπ)REV(V, ξπ) subject to constraints ensuring that each ξπ belongs to Ξπ (for π ∈ Πm+1) and that γ is a consistent probability distribution over such posteriors (see Equation (2)). This problem can be formulated as an LP by introducing a variable for each π ∈ Πm+1 and θ ∈ Θ, encoding the products γ(ξπ)ξπ(θ) that define the expected revenue. Overall, the resulting LP (see LP 8 in [Bacchiocchi et al., 2022]) has a number of variables and constraints that is O(nm), which, after fixing m, is polynomial in the size of the input. 6 Thus, we conclude that:

Theorem 2. In the KV setting, if the number of slots m is fixed, then an optimal signaling scheme can be computed in polynomial time.

6 We remark that LP 8 in [Bacchiocchi et al., 2022] is a generalization of the LP presented by Emek et al. [2014] for the easier case of second price auctions.

4.2 Fixing the Number of States d

Our polynomial-time algorithm exploits the fact that an optimal signaling scheme can be computed by restricting the attention to distributions supported on a finite set of posteriors whose cardinality is polynomial in all the parameters, except from d. In particular, it is sufficient to focus on the set Ξ∗ := ⋃π∈Πn V (Ξπ), where V (·) denotes the set of vertices of the polytope given as input. Formally:

The lemma follows from the fact that, given any signaling scheme γ and posterior ξ ∈ supp(γ) such that ξ ∈ Ξπ for some π ∈ Πn, by Carath´eodory's theorem it is always possible (since Ξπ is a polytope) to decompose ξ into a convex combination of the vertices of Ξπ, obtaining a new signaling scheme that provides the mechanism with an expected revenue at least as large as that of γ (since REV(V, ξ) is linear over Ξπ). By observing that |Ξ∗ | = O((n2 + d)d-1 ), it is easy to show that an optimal signaling scheme can be computed by means of LP 3 instantiated for the set Ξ∗ , which has a number of variables and constraints that is polynomial once d is fixed. This proves the following:

Theorem 3. In the KV setting, if the number of states d is fixed, then an optimal signaling scheme can be computed in polynomial time.

5 KV Setting: Single-Minded Bidders

In this section, we focus on particular Bayesian ad auctions where the bidders are single minded. Intuitively, in our setting, by single mindedness we mean that each bidder is interested in displaying their ad only when the realized state of nature is a specific (single) state, and that all the bidders interested in the same state value a click on their ad for the same amount. We introduce the following formal definition:

Definition 1 (Single-minded bidders). In a Bayesian ad auction, we say that bidders are single minded if there exist Nθ ⊆ N and δθ ∈ [0, 1] for all θ ∈ Θ such that:

• (i) N = ⋃θ∈Θ Nθ and Nθ ∩Nθ′ = ∅ for all θ ̸= θ′ ∈ Θ;
• (ii) for every θ ∈ Θ and i ∈ Nθ, it holds vi(θ) = δθ and vi(θ′ ) = 0 for all θ′ ∈ Θ : θ′ ̸= θ.

Notice that, given a posterior ξ ∈ ∆Θ induced by the mechanism, all the bidders i belonging to the same set Nθ have the same expected valuation, namely ξ⊤vi = δθξ(θ) for all θ ∈ Θ and i ∈ Nθ. As a result, given that bidders truthfully report their expected valuations, the mechanismwill always receive at most d different bids, one per set Nθ.

The last observation implies that, given ξ ∈ ∆Θ, in order to unequivocally define an allocation of bidders to slots (and, thus, also define the expected payments) it is sufficient to know the relative ordering of the (at most) d different expected valuations associated to sets Nθ. This allows us to tackle the problem with an approach analogous to the one of Section 4, with the only difference that, in this case, we will reason about permutations of the groups of bidders Nθ, rather than about permutations of all the individual bidders.

In the following, we let Π ⊆ 2Θ be the set of all the permutations of the sates of nature Θ = {θ1, . . . , θd}, while we let

π = (θk1 , . . . , θkd ) ∈ Π be an ordered tuple made by states θk1 , . . . , θkd ∈ Θ, where k1, . . . , kd ∈ {1, . . . , d}. Moreover, Ξπ := {ξ ∈ ∆Θ | δθk1 ξ(θk1 ) ≥ . . . ≥ δθkd ξ(θkd )} is the polytope of posteriors in which the expected valuations associated to sets Nθ are ordered according to π.

The first preliminary result that we need in order to derive our approximation algorithm is a characterization of the vertices of the sets Ξπ for π ∈ Π, as follows.

Lemma 3. Given π ∈ Π and ξ ∈ Ξπ, it holds that ξ ∈ V (Ξπ) if and only if there exists ℓ ∈ {1, . . . , d} such that:

Intuitively, Lemma 3 states that the vertices of a set Ξπ are all the posteriors ξ ∈ ∆Θ such that, for some ℓ ∈ {1, . . . , d}, only the first ℓ states according to the ordering defined by π are assigned a positive probability, while all the remaining states have zero probability. Moreover, the positive probabilities of the posterior ξ are defined so that all the bidders belonging to the first ℓ sets Nθ, according to the ordering defined by π, are the same. Notice that, in the special case in which all the values δθ are equal to one, the vertices of all the sets Ξπ are all the uniform probability distributions over subsets of ℓ states of nature, for any ℓ ∈ {1, . . . , d}.

By letting Ξ∗ = ⋃π∈Π V (Ξπ), since the term REV(V, ξ) is linear in ξ over Ξπ for every permutation π ∈ Π, we can conclude that OPTΞ∗ = OPT (the proof is analogous to that of Lemma 2). Thus, Lemma 3 allows us to find an optimal signaling scheme by solving LP 3 for the set Ξ∗ and the matrix of bidders' valuations V . However, notice that, since the size of Ξ∗ is exponential in d, the resulting LP has exponentiallymany variables. Nevertheless, since the LP has polynomiallymany constraints, we can still solve it in polynomial time by applying the ellipsoid algorithm to its dual, provided that a polynomial-time separation oracle is available.

In order to design a polynomial-time separation oracle, we apply the procedure described above to a relaxed version of LP 3, whose optimal value is sufficiently "close" to that of the original LP. Given β ∈ R+, the relaxed LP reads as follows:

The dual problem of LP 4 reads as follows:

where yθ for θ ∈ Θ are dual variables associated to Constraints (3b), while t is a dual variable for ∑ξ∈Ξ∗ γ(ξ) = 1. Notice that, by relaxing the LP, in the dual LP 5 we get the additional Constraint (5c) and that yθ ≤ 0 for all θ ∈ Θ. This is crucial to design a polynomial-time separation oracle.

The separation problem associated to Problem 5 reads as:

Definition 2 (Separation problem). Given values for the dual variables yθ ∈ [-β, 0] for all θ ∈ Θ, compute:

The following Lemma 4 shows that Problem 6 can be solved optimally up to any given additive loss λ > 0, by means of a dynamic programming algorithm that runs in time polynomial in the size of the input, in 1λ , and in β. Formally:

Lemma 4. Given λ > 0, there exists an algorithm that finds an additive λ-approximation to Problem 6, in time polynomial in the size of the input, in 1λ , and in β.

The crucial observation that allows us to solve Problem 6 by means of dynamic programming is that, in any posterior ξ ∈ Ξ∗ , bidders' expected valuations are either a positive, bidder-independent value or zero (see Lemma 3). This allows us to build a discretized range of possible bidders' valuation values, so that, for each discretized value, we can compute an optimal posterior ξ ∈ Ξ∗ inducing that value by adding states of nature incrementally in a dynamic programming fashion.

Since the algorithm in Lemma 4 only returns an approximate solution to Problem 6, we need to carefully apply the ellipsoid algorithm to solve LP 5, so that it correctly works even with an approximated oracle. Some non-trivial duality arguments allow us to prove that, indeed, this can be achieved by only incurring in a small additive loss on the quality of the returned solution, and without degrading the running time of the algorithm. Overall, this allows us to conclude that:

Theorem 4. In the KV setting, if the bidders are single minded, then the problem of computing an optimal signaling scheme admits an (additive) FPTAS.

6 RV Setting

In this setting, as stated in Section 2, we assume that the auction mechanism has access to the distribution of bidders' valuations V only through a black-box sampling oracle. In the following, given s ∈ N>0 i.i.d. samples of matrices of bidders' valuations, namely V1, . . . , Vs ∈ [0, 1]n×d , we let V s be their empirical distribution, which is such that PrV ∼V s {V = ˆ V } := ∑st=1 1{Vt=ˆ V } s for all ˆ V ∈ [0, 1]n×d .

In this section, we first study the parametrized complexity of the problem of computing an optimal signaling scheme in general auctions (Section 6.1), and, then, we address special auction settings in which the bidders' valuations are bounded away from zero, namely vi(θ) > δ for all i ∈ N and θ ∈ Θ, for some threshold δ > 0. In the latter case, we show that the problem admits a QPTAS and the result is tight (Section 6.2).

Before stating our main results (Theorems 5, 6, 7, and 8), we introduce some preliminary useful lemmas. The first one (Lemma 5) works under the true distribution of bidders' valuations V, and it establishes a connection between the optimal expected revenue (OPT) and the optimal value of LP 3 for suitably-defined finite sets Ξ ⊆ ∆Θ of posteriors (OPTΞ).

In particular, we look at sets Ξ ⊆ ∆Θ for which the function REV(V, ·) is "stable" according to the following definition: 7

Definition 3 ((α, ε)-stability). Given α, ε ≥ 0 and a finite set Ξ ⊆ ∆Θ, we say that REV(V, ·) is (α, ε)-stable for Ξ if, for every ξ ∈ ∆Θ, there exists a distribution γξ ∈ ∆Ξ such that:

For any finite set Ξ ⊆ ∆Θ such that REV(V, ·) is (α, ε)- stable for Ξ, starting from an optimal signaling scheme γ one can recover an optimal solution to LP 3, only incurring in "small" multiplicative and additive losses in the expected revenue, respectively of 1 - α and ε. This can be accomplished by decomposing each posterior ξ ∈ supp(γ) into γξ ∈ ∆Ξ and, then, putting such distributions together. These observations allow us to prove the following lemma:

The second lemma (Lemma 6) deals with the approximation error introduced by using an empirical distribution of bidders' valuations V s , rather than the actual distribution V. Given a finite set Ξ ⊆ ∆Θ of posteriors, let γV s ∈ ∆Ξ be an optimal solution to LP 3 for distribution V s and set Ξ. Moreover, let OPTΞ,s := E [∑ξ∈Ξ γV s(ξ)REV(V, ξ)] be the average expected revenue of signaling schemes γV s under the true distribution of valuations V, where the expectation is with respect to the sampling procedure that determines V s . Then, a concentration argument proves the following:

Finally, the last lemma (Lemma 7) exploits Lemma 5 to provide two useful bounds on the value of OPTΞq , where Ξq ⊆ ∆Θ (for a given q ∈ N>0) is the finite set of all the q-uniform posteriors, according to the following definition:

Definition 4 (q-uniform posterior). Given q ∈ N>0, a posterior ξ ∈ ∆Θ is q-uniform if each ξ(θ) is a multiple of 1q .

Notice that the set Ξq has size |Ξq | ≤ min{dq , qd }. The two points in the following lemma are readily proved by applying Lemma 5, after noticing that the sets Ξq in the statement are such that the function REV(V, ·) is (α, ε)-stable for them, with suitable values of α ≥ 0 and ε ≥ 0. Formally:

6.1 Parametrized Complexity

First, we study the computational complexity of the problem of computing an optimal signaling scheme when the number of states d is fixed. We provide an (additive) FPTAS that works by performing the following two steps: (i) it collects a suitable number s ∈ N>0 of matrices of bidders' valuations, by invoking the sampling oracle; and (ii) it solves LP 3 for the resulting empirical distribution V s and a suitably-defined set of q-uniform posteriors. In particular, given a desired (additive) error λ > 0, the algorithm works on the set Ξq for q = ⌈ md λ ⌉ and its approximation guarantees rely on the following Lemma 8, proved again by means of Lemma 5.

7 Notions of stability analogous to that in Definition 3 have already been used in the literature; see, e.g., [Cheng et al., 2015].

Thanks to Lemmas 6 and 8 (the former applied for suitable values ρ, τ > 0), we can prove that the procedure described in steps (i) and (ii) above gives a signaling scheme achieving an expected revenue at most a function of λ lower than OPT, provided that the number of samples s is defined as in Lemma 8. Moreover, let us notice that, since |Ξq| = O(qd ) = O(( 1λ md)d ), if d is fixed, then the overall procedure runs in time polynomial in the input size and in 1λ . Thus, we can conclude that:

Theorem 5. In the RV setting, if the number of states d is fixed, then the problem of computing an optimal signaling scheme admits and (additive) FPTAS.

Next, we switch the attention to the case in which the number of slots m is fixed. We provide an (additive) PTAS that works as the FPTAS in Theorem 5, but whose approximation guarantees follow from Lemma 6 and point (i) in Lemma 7 (rather than Lemma 8). Thus, the only difference with respect to the previous case is that the algorithm works on the set Ξq of q-uniform posteriors for q defined as in Lemma 7. As a result, since |Ξq| = O(dq ) and q depends on a parameter η > 0 that is related to the quality of the obtained approximation, the algorithm is only a PTAS rather than an FPTAS. Formally, we can prove the following:

Theorem 6. In the RV setting, if the number of slots m is fixed, then the problem of computing an optimal signaling scheme admits and (additive) PTAS.

6.2 Valuations Bounded Away FromZero

We conclude the section by studying the case in which the bidders' valuations are bounded away from zero. This case is dealt with an algorithm identical to the one in Theorem 6, but carrying on the approximation analysis by using Lemma 6 and point (ii) in Lemma 7 (rater than point (i)). Thus, since the value of q in Lemma 7 is related to the quality of the approximation thorough a parameter η > 0 and also depends logarithmically on the number of slots m, we obtain:

Theorem 7. In the RV setting, if vi(θ) ≥ δ for all i ∈ N and θ ∈ Θ for some δ > 0, then the problem of computing an optimal signaling scheme admits a (multiplicative) QPTAS.

The following theorem shows that the result is tight.

Theorem 8. Assuming the ETH, there exists a constant ω > 0 such that finding a signaling scheme that provides an expected revenue at least of (1-ω)OPT requires I ˜Ω(log I) time, where I is the size of the problem instance. This holds even when vi(θ) > 13 for all i ∈ N and θ ∈ Θ. 8

8 The ˜Ω notation hides poly-logarithmic factors.