# public_signaling_in_bayesian_ad_auctions__63522058.pdf

Public Signaling in Bayesian Ad Auctions

Francesco Bacchiocchi , Matteo Castiglioni , Alberto Marchesi , Giulia Romano and Nicola Gatti Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133, Milan, Italy francesco.bacchiocchi@mail.polimi.it {matteo.castiglioni, alberto.marchesi, giulia.romano, nicola.gatti}@polimi.it

We study signaling in Bayesian ad auctions, in which 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. For instance, a state may collectively encode some features of the user 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 how the mechanism should send signals to bidders in order to maximize revenue. While this problem has already been addressed in the easier setting of second-price auctions, to the best of our knowledge, our work is the ﬁrst to explore ad auctions with more than one slot. In this paper, we focus on public signaling and VCG mechanisms, under which bidders truthfully report their valuations. We start with a negative result, showing that, in general, the problem does not admit a PTAS unless P = NP, even when bidders valuations are known to the mechanism. The rest of the paper is devoted to settings in which such negative result can be circumvented. First, we prove that, with known valuations, the problem can indeed be solved in polynomial time when either the number of states d or the number of slots m is ﬁxed. Moreover, in the same setting, we provide an FPTAS for the case in which bidders are single minded, but d and m can be arbitrary. Then, we switch to the random valuations setting, in which these are randomly drawn according to some probability distribution. In this case, we show that the problem admits an FPTAS, a PTAS, and a QPTAS, when, respectively, d is ﬁxed, m is ﬁxed, and bidders valuations are bounded away from zero.

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 e Marketer [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], trafﬁc 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 deﬁned as a randomized mapping from states of nature to signals being sent to the bidders. Our model ﬁts 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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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 ﬁrst 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 ﬁxed. The proposed algorithms work by solving suitably-deﬁned linear programs (LPs) of polynomial size, thanks to the crucial property that, when either m or d is ﬁxed, 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 speciﬁc (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 ﬁrst 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-deﬁned ﬁnite sets of posterior distributions. These sets are deﬁned 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 ﬁnite 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 ﬁxed, m is ﬁxed, and bidders valuations are bounded away from zero.1

1.2 Related Works To the best of our knowledge, the algorithmic study of signaling in auctions is limited to the second-price auction, which

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

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). [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 ﬁxed. [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 ﬁrst 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 ﬁxed 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: ﬁrst, 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 deﬁnes 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 deﬁned 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 ﬁrst m bidders in decreasing value of bi to the ﬁrst 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 deﬁnes an expected payment pi := Pm+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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Auctioneer )

choose φ observe µ draw s φ

observe φ observe s compute s bid > s vi

allocation payments

Figure 1: Time-line of a Bayesian ad auction.

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 deﬁned 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

ξs(θ) := µθφθ(s) P θ Θ µθ φθ (s). (1)

Finally, each bidder i N truthfully reports to the mechanism their expected valuation given the posterior ξs, namely ξ s vi = P θ Θ vi(θ) ξs(θ), and the mechanism allocates slots and deﬁnes 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 ξ Θ, deﬁned as

θ Θ µθφθ(s).

2Given a ﬁnite set X, we denote with X the (|X| 1)- dimensional simplex deﬁned over the elements of X. 3Given 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 X

ξ supp(γ) γ(ξ) ξ(θ) = µθ θ Θ. (2)

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 in which the matrix 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, ξ) := Pm j=1 j ξ vj+1(λj λj+1). Then, given a signaling scheme γ, the expected revenue of the mechanism is P ξ supp(γ) γ(ξ) REV(V, ξ). When the valuations are unknown, we let REV(V, ξ) := EV VREV(V, ξ) and deﬁne 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 ﬁnite set Ξ Θ of posteriors, it is possible to formulate the problem of computing an optimal signaling scheme as an LP, as follows:4

ξ Ξ γ(ξ) REV(V, ξ) s.t. (3a)

ξ Ξ γ(ξ) ξ(θ) = µθ θ Θ. (3b)

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 A General 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.

4LP 3 is written for the RV setting, its analogous for the KV setting can be obtained by substituting REV(V, ξ) with REV(V, ξ). 5The dependence of OPTΞ and OPT from either V or V is omitted, as it will be clear from context.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

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 ﬁxing some parameters of the problem (see Sections 4 and 6.1) or considering instances with a speciﬁc 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 ﬁxed. 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, ξ) := Pm j=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 ﬁxed π Π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 deﬁne a new signaling scheme that replaces ξ and ξ with a suitably-deﬁned 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 P π Π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 deﬁne 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 ﬁxing 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 ﬁxed, then an optimal signaling scheme can be computed in polynomial time.

6We 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 ﬁnite set of posteriors whose cardinality is polynomial in all the parameters, except from d. In particular, it is sufﬁcient to focus on the set Ξ := S π Πn V (Ξπ), where V ( ) denotes the set of vertices of the polytope given as input. Formally: Lemma 2. It holds that OPTΞ = OPT. 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 ﬁxed. This proves the following: Theorem 3. In the KV setting, if the number of states d is ﬁxed, 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 speciﬁc (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 deﬁnition: Deﬁnition 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 = S θ Θ 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 mechanism will always receive at most d different bids, one per set Nθ. The last observation implies that, given ξ Θ, in order to unequivocally deﬁne an allocation of bidders to slots (and, thus, also deﬁne the expected payments) it is sufﬁcient 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

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

π = (θk1, . . . , θkd) Π be an ordered tuple made by states θk1, . . . , θkd Θ, where k1, . . . , kd {1, . . . , d}. More-

over, Ξπ := n ξ Θ | δθk1 ξ(θk1) . . . δθkd ξ(θkd) o is the polytope of posteriors in which the expected valuations associated to sets Nθ are ordered according to π. The ﬁrst 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: (i) δθk1 ξ(θk1) = . . . = δθkℓξ(θkℓ) > 0; and

(ii) δθkℓ+1 ξ(θkℓ+1) = . . . = δθkd ξ(θkd) = 0.

Intuitively, Lemma 3 states that the vertices of a set Ξπ are all the posteriors ξ Θ such that, for some ℓ {1, . . . , d}, only the ﬁrst ℓstates according to the ordering deﬁned by π are assigned a positive probability, while all the remaining states have zero probability. Moreover, the positive probabilities of the posterior ξ are deﬁned so that all the bidders belonging to the ﬁrst ℓsets Nθ, according to the ordering deﬁned 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 Ξ = S π Π 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 ﬁnd 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 sufﬁciently close to that of the original LP. Given β R+, the relaxed LP reads as follows:

max γ Ξ ,z 0

ξ Ξ γ(ξ) REV(V, ξ) + βz s.t. (4a)

ξ Ξ γ(ξ) ξ(θ) z µθ θ Θ. (4b)

The dual problem of LP 4 reads as follows:

θ Θ yθµθ + t s.t. (5a)

θ Θ yθ ξ(θ) + t REV(V, ξ) ξ Ξ (5b)

θ Θ yθ β, (5c)

where yθ for θ Θ are dual variables associated to Constraints (3b), while t is a dual variable for P ξ Ξ γ(ξ) = 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:

Deﬁnition 2 (Separation problem). Given values for the dual variables yθ [ β, 0] for all θ Θ, compute:

max ξ Ξ REV(V, ξ) X

θ Θ yθ ξ(θ). (6)

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 ﬁnds 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 Vs be their empirical distribution, which is such that

Pr V Vs n V = ˆV o :=

Ps t=1 1{Vt= ˆV }

s for all ˆV [0, 1]n d. In this section, we ﬁrst 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 ﬁrst 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-deﬁned ﬁnite sets Ξ Θ of posteriors (OPTΞ).

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

In particular, we look at sets Ξ Θ for which the function REV(V, ) is stable according to the following deﬁnition:7

Deﬁnition 3 ((α, ε)-stability). Given α, ε 0 and a ﬁnite set Ξ Θ, we say that REV(V, ) is (α, ε)-stable for Ξ if, for every ξ Θ, there exists a distribution γξ Ξ such that: X

ξ Ξ γξ(ξ )REV(V, ξ ) (1 α)REV(V, ξ) ε. (7)

For any ﬁnite 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:

Lemma 5. Given α, ε 0 and Ξ Θ such that REV(V, ) is (α, ε)-stable for Ξ, it holds OPTΞ (1 α)OPT ε.

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

Lemma 6. Given ρ, τ > 0, let Ξ Θ be ﬁnite and s := l 2(λ1m)2

ρ m , OPTΞ,s (1 ρ|Ξ|) OPTΞ τ.

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 ﬁnite set of all the q-uniform posteriors, according to the following deﬁnition:

Deﬁnition 4 (q-uniform posterior). Given q N>0, a posterior ξ Θ is q-uniform if each ξ(θ) is a multiple of 1

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:

Lemma 7. Given η > 0 and q := l 1 2η2 log m+1

η m , it holds:

(i) OPTΞq OPT 2ηm;

(ii) if, for some δ > 0, it is the case that vi(θ) > δ for all i N and θ Θ, then OPTΞq (1 η

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 ﬁxed. We provide an (additive) FPTAS that

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

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 Vs and a suitably-deﬁned 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.

Lemma 8. For λ > 0 and q = md

λ , OPTΞq OPT λ.

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 deﬁned as in Lemma 8. Moreover, let us notice that, since |Ξq| = O(qd) = O(( 1

λmd)d), if d is ﬁxed, 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 ﬁxed, 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 ﬁxed. 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 deﬁned 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 ﬁxed, then the problem of computing an optimal signaling scheme admits and (additive) PTAS.

6.2 Valuations Bounded Away From Zero 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 ﬁnding 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(θ) > 1

3 for all i N and θ Θ.8

8The Ωnotation hides poly-logarithmic factors.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

References [Alimonti and Kann, 2000] Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237:123 134, 04 2000. [Alonso and Cˆamara, 2016] Ricardo Alonso and Odilon Cˆamara. Persuading voters. American Economic Review, 106(11):3590 3605, 2016. [Babichenko and Barman, 2017] Yakov Babichenko and Siddharth Barman. Algorithmic aspects of private Bayesian persuasion. In ITCS, 2017. [Babichenko et al., 2021] Yakov Babichenko, Inbal Talgam Cohen, Haifeng Xu, and Konstantin Zabarnyi. Regretminimizing bayesian persuasion. In EC, page 128, 2021. [Bacchiocchi et al., 2022] Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, Giulia Romano, and Nicola Gatti. Public signaling in bayesian ad auctions. Co RR, abs/2201.09728, 2022. [Badanidiyuru et al., 2018] Ashwinkumar Badanidiyuru, Kshipra Bhawalkar, and Haifeng Xu. Targeting and signaling in ad auctions. In SODA, pages 2545 2563, 2018. [Bhaskar et al., 2016] Umang Bhaskar, Yu Cheng, Young Kun Ko, and Chaitanya Swamy. Hardness results for signaling in bayesian zero-sum and network routing games. In EC, pages 479 496, 2016. [Bro Miltersen and Sheffet, 2012] Peter Bro Miltersen and Or Sheffet. Send mixed signals: earn more, work less. In EC, pages 234 247, 2012. [Candogan, 2019] Ozan Candogan. Persuasion in networks: Public signals and k-cores. In EC, pages 133 134, 2019. [Castiglioni and Gatti, 2021] Matteo Castiglioni and Nicola Gatti. Persuading voters in district-based elections. In AAAI, pages 5244 5251, 2021. [Castiglioni et al., 2020a] Matteo Castiglioni, Andrea Celli, and Nicola Gatti. Persuading voters: It s easy to whisper, it s hard to speak loud. In AAAI, pages 1870 1877, 2020. [Castiglioni et al., 2020b] Matteo Castiglioni, Andrea Celli, and Nicola Gatti. Public bayesian persuasion: Being almost optimal and almost persuasive. Co RR, abs/2002.05156, 2020. [Castiglioni et al., 2020c] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. In Neur IPS, pages 16188 16198, 2020. [Castiglioni et al., 2021a] Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Signaling in Bayesian network congestion games: the subtle power of symmetry. In AAAI, pages 5252 5259, 2021. [Castiglioni et al., 2021b] Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online Bayesian persuasion. In ICML, pages 1314 1323, 2021. [Castiglioni et al., 2022a] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian persuasion meets

mechanism design: Going beyond intractability with type reporting. In AAMAS, 2022. [Castiglioni et al., 2022b] Matteo Castiglioni, Giulia Romano, Alberto Marchesi, and Nicola Gatti. Signaling in posted price auctions. In AAAI, 2022. [Cheng et al., 2015] Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, and Shang Hua Teng. Mixture selection, mechanism design, and signaling. In FOCS, pages 1426 1445, 2015. [Daskalakis et al., 2016] Constantinos Daskalakis, Christos H. Papadimitriou, and Christos Tzamos. Does information revelation improve revenue? In EC, pages 233 250, 2016. [Dughmi, 2014] Shaddin Dughmi. On the hardness of signaling. In FOCS, pages 354 363. IEEE, 2014. [e Marketer, 2021] e Marketer. Worldwide digital ad spending year-end update. https://www.emarketer.com/content/ worldwide-digital-ad-spending-year-end-update, 2021. Accessed: 2022-01-09. [Emek et al., 2014] Yuval Emek, Michal Feldman, Iftah Gamzu, Renato Paes Leme, and Moshe Tennenholtz. Signaling schemes for revenue maximization. TEAC, 2(2):1 19, 2014. [Fu et al., 2012] Hu Fu, Patrick R. Jordan, Mohammad Mahdian, Uri Nadav, Inbal Talgam-Cohen, and Sergei Vassilvitskii. Ad auctions with data. In SAGT, pages 168 179, 2012. [Kamenica and Gentzkow, 2011] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590 2615, 2011. [Li and Das, 2019] Zhuoshu Li and Sanmay Das. Revenue enhancement via asymmetric signaling in interdependentvalue auctions. In AAAI, pages 2093 2100, 2019. [Mansour et al., 2016] Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. Bayesian exploration: Incentivizing exploration in Bayesian games. In EC, pages 661 661, 2016. [Nisan and Ronen, 2001] Noam Nisan and Amir Ronen. Algorithmic mechanism design. Games and Economic behavior, 35(1-2):166 196, 2001. [Rabinovich et al., 2015] Zinovi Rabinovich, Albert Xin Jiang, Manish Jain, and Haifeng Xu. Information disclosure as a means to security. In AAMAS, pages 645 653, 2015. [Vasserman et al., 2015] Shoshana Vasserman, Michal Feldman, and Avinatan Hassidim. Implementing the wisdom of waze. In IJCAI, pages 660 666, 2015. [Xu et al., 2016] Haifeng Xu, Rupert Freeman, Vincent Conitzer, Shaddin Dughmi, and Milind Tambe. Signaling in Bayesian Stackelberg games. In AAMAS, pages 150 158, 2016. [Zu et al., 2021] You Zu, Krishnamurthy Iyer, and Haifeng Xu. Learning to persuade on the ﬂy: Robustness against ignorance. In EC, pages 927 928, 2021.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)