# signaling_in_posted_price_auctions__5916bba6.pdf

Signaling in Posted Price Auctions

Matteo Castiglioni, Giulia Romano, Alberto Marchesi, Nicola Gatti

Politecnico di Milano, Piazza Leonardo da Vinci 32, I-20133, Milan, Italy {matteo.castiglioni, giulia.romano, alberto.marchesi, nicola.gatti}@polimi.it

We study single-item single-unit Bayesian posted price auctions, where buyers arrive sequentially and their valuations for the item being sold depend on a random, unknown state of nature. The seller has complete knowledge of the actual state and can send signals to the buyers so as to disclose information about it. For instance, the state of nature may reﬂect the condition and/or some particular features of the item, which are known to the seller only. The problem faced by the seller is about how to partially disclose information about the state so as to maximize revenue. Unlike classical signaling problems, in this setting, the seller must also correlate the signals being sent to the buyers with some price proposals for them. This introduces additional challenges compared to standard settings. We consider two cases: the one where the seller can only send signals publicly visible to all buyers, and the case in which the seller can privately send a different signal to each buyer. As a ﬁrst step, we prove that, in both settings, the problem of maximizing the seller s revenue does not admit an FPTAS unless P = NP, even for basic instances with a single buyer. As a result, in the rest of the paper, we focus on designing PTASs. In order to do so, we ﬁrst introduce a unifying framework encompassing both public and private signaling, whose core result is a decomposition lemma that allows focusing on a ﬁnite set of possible buyers posteriors. This forms the basis on which our PTASs are developed. In particular, in the public signaling setting, our PTAS employs some ad hoc techniques based on linear programming, while our PTAS for the private setting relies on the ellipsoid method to solve an exponentially-sized LP in polynomial time. In the latter case, we need a custom approximate separation oracle, which we implement with a dynamic programming approach.

1 Introduction In posted price auctions, the seller tries to sell an item by proposing take-it-or-leave-it prices to buyers arriving sequentially. Each buyer has to choose between declining the offer without having the possibility of coming back or accepting it, thus ending the auction. Nowadays, posted pricing is the most used selling format in e-commerce (Einav et al. 2018), whose sales reach over $4 trillion in 2020 (e Marketer 2021). Posted price auctions are ubiquitous in settings such as, for example, online travel agencies (e.g., Expedia), accommodation websites (e.g., Booking.com), and retail platforms (e.g.,

Copyright c 2022, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

Amazon and e Bay). As a result, growing attention has been devoted to their analysis, both in economics (Seifert 2006) and in computer science (Chawla et al. 2010; Babaioff et al. 2015, 2017; Adamczyk et al. 2017; Correa et al. 2017), within AI and machine learning in particular (Kleinberg and Leighton 2003; Shah, Johari, and Blanchet 2019; Romano et al. 2021). We study Bayesian posted price auctions, where the buyers valuations for the item depend on a random state of nature, which is known to the seller only. By applying the Bayesian persuasion framework (Kamenica and Gentzkow 2011), we consider the case in which the seller (sender) can send signals to the buyers (receivers) so as to disclose information about the state. Thus, in a Bayesian auction, the seller does not only have to decide price proposals for the buyers, but also how to partially disclose information about the state so as to maximize revenue. Our model ﬁnds application in several realworld scenarios. For instance, in an e-commerce platform, the state of nature may reﬂect the condition (or quality) of the item being sold and/or some of its features. These are known to the seller only since the buyers cannot see the item given that the auction is carried out on the web.

Original Contributions. We study the problem of maximizing seller s revenue in single-item single-unit Bayesian posted price auctions, focusing on two different settings: public signaling, where the signals are publicly visible to all buyers, and private signaling, in which the seller can send a different signal to each buyer through private communication channels. As a ﬁrst negative result, we prove that, in both settings, the problem does not admit an FPTAS unless P = NP, even for basic instances with a single buyer. Then, we provide tight positive results by designing a PTAS for each setting. In order to do so, we ﬁrst introduce a unifying framework encompassing both public and private signaling. Its core result is a decomposition lemma that allows us to focus on a ﬁnite set of buyers posterior beliefs over states of nature called q-uniform posteriors , rather than reasoning about signaling schemes with a (potentially) inﬁnite number of signals. Compared to previous works on signaling, our framework has to deal with some additional challenges. The main one is that, in our model, the seller (sender) is not only required to choose how to send signals, but they also have to take some actions in the form of price proposals. This requires signiﬁcant extensions to standard approaches based on decomposition

The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22)

lemmas (Cheng et al. 2015; Xu 2020; Castiglioni and Gatti 2021). The framework forms the basis on which we design our PTASs. In the public setting, it establishes a connection between signaling schemes and probability distributions over q-uniform posteriors. This allows us to formulate the seller s revenue-maximizing problem as an LP of polynomial size, whose objective coefﬁcients are not readily available. However, they can be approximately computed in polynomial time by an algorithm for ﬁnding approximately-optimal prices in (non-Bayesian) posted price auctions, which may also be of independent interest.Solving the LP with approximate coefﬁcients then gives the desired PTAS. As for the private setting, our framework provides a connection between marginal signaling schemes of each buyer and probability distributions over q-uniform posteriors, which, to the best of our knowledge, is the ﬁrst of its kind, since previous works are limited to public settings (Cheng et al. 2015; Castiglioni, Celli, and Gatti 2020b).1 Such connection allows us to formulate an LP correlating marginal signaling schemes together and with price proposals. Although the LP has an exponential number of variables, we show that it can still be approximately solved in polynomial time by means of the ellipsoid method. This requires the implementation of a problem-speciﬁc approximate separation oracle that can be implemented in polynomial time by means of a dynamic programming algorithm.

Related Works. The computational study of Bayesian persuasion has received terriﬁc attention (Vasserman, Feldman, and Hassidim 2015; Castiglioni, Celli, and Gatti 2020a; Rabinovich et al. 2015; Candogan 2019; Castiglioni, Marchesi, and Gatti 2022; Castiglioni et al. 2021a). The works most related to ours are those addressing second-price auctions. Emek et al. (2014) provide an LP to compute an optimal public signaling scheme in the known-valuation setting, and they show that the problem is NP-hard in the Bayesian setting. Cheng et al. (2015) provide a PTAS for this latter case. Bacchiocchi et al. (2022) extend the framework to study ad auctions with Vickrey Clarke Groves payments. Finally, Badanidiyuru, Bhawalkar, and Xu (2018) focus on the design of algorithms whose running time is independent from the number of states of nature. They initiate the study of private signaling, showing that, in second-price auctions, it may introduce non-trivial equilibrium selection issues.

2 Preliminaries 2.1 Bayesian Posted Price Auctions and Signaling In a posted price auction, the seller tries to sell an item to a ﬁnite set N := {1, . . . , n} of buyers arriving sequentially according to a ﬁxed ordering. W.l.o.g., we let buyer i N be the i-th buyer according to such ordering. The seller chooses a price proposal pi [0, 1] for each buyer i N. Then, each buyer in turn has to decide whether to buy the item for the proposed price or not. Buyer i N buys only if their item valuation is at least the proposed price pi.2 In that case, the

1A notable exception is (Castiglioni and Gatti 2021), which studies a speciﬁc case in between private and public signaling schemes. 2As customary in the literature, we assume that buyers always buy when they are offered a price that is equal to their valuation.

auction ends and the seller gets revenue pi for selling the item, otherwise the auction continues with the next buyer. We study Bayesian posted price auctions, characterized by a ﬁnite set of d states of nature, namely Θ := {θ1, . . . , θd}. Each buyer i N has a valuation vector vi [0, 1]d, with vi(θ) representing buyer i s valuation when the state is θ Θ. Each valuation vi is independently drawn from a probability distribution Vi supported on [0, 1]d. For the ease of presentation, we let V [0, 1]n d be the matrix of buyers valuations, whose entries are V (i, θ) := vi(θ) for all i N and θ Θ.3 Moreover, by letting V := {Vi}i N be the collection of all distributions of buyers valuations, we write V V to denote that V is built by drawing each vi independently from Vi. We model signaling with the Bayesian persuasion framework by Kamenica and Gentzkow (2011). We consider the case in which the seller having knowledge of the state of nature acts as a sender by issuing signals to the buyers (the receivers), so as to partially disclose information about the state and increase revenue. As customary in the literature, we assume that the state is drawn from a common prior distribution µ Θ, explicitly known to both the seller and the buyers.4 We denote by µθ the probability of state θ Θ. The seller commits to a signaling scheme φ, which is a randomized mapping from states of nature to signals for the receivers. Letting Si be the set of signals for buyer i N, a signaling scheme is a function φ : Θ S, where S := i N Si. An element s S called signal proﬁle is a tuple specifying a signal for each buyer. We use si to refer to the i-th component of any s S (i.e., the signal for buyer i), so that s = (s1, . . . , sn). We let φθ(s) be the probability of drawing signal proﬁle s S when the state is θ Θ. Furthermore, we let φi : Θ Si be the marginal signaling scheme of buyer i N, with φi(θ) being the marginalization of φ(θ) with respect to buyer i s signals. As for general signaling schemes, φi,θ(si) := P s S:s i=si φθ(s ) denotes the probability of drawing signal si Si when the state is θ Θ. Price proposals may depend on the signals being sent to the buyers. Formally, the seller commits to a price function f : S [0, 1]n, with f(s) [0, 1]n being the price vector when the signal proﬁle is s S. We assume that prices proposed to buyer i only depend on the signals sent to them, and not on the signals sent to other buyers. Thus, w.l.o.g., we can work with functions fi : Si [0, 1] deﬁning prices for each buyer i N independently, with fi(si) denoting the i-th component of f(s) for all s S and i N.5

The interaction involving the seller and the buyers goes on as follows (Figure 1): (i) the seller commits to a signaling scheme φ : Θ S and a price function f : S [0, 1]n, and the buyers observe such commitments; (ii) the seller observes the state of nature θ µ; (iii) the seller draws a signal

3Sometimes, we also write Vi := v i to denote the i-th row of matrix V , which is the valuation of buyer i N. 4In this work, given a ﬁnite set X, we denote with X the (|X| 1)-dimensional simplex deﬁned over the elements of X. 5Let us remark that our assumption on the seller s price function ensures that a buyer does not get additional information about the state of nature by observing the proposed price, since the latter only depends on the signal which is revealed to them anyway.

Seller (Sender)

Buyer i (Receiver)

commits (φ, f) observes θ µ draws s φθ

observes (φ, f) observes (si, fi(si)) infers prosterior ξi,si

if i buys buyer s utility: vi(θ) fi(si)

seller s revenue: fi(si)

next buyer i+1 if i leaves

Figure 1: Interaction between the seller and the buyers.

proﬁle s φ(θ); and (iv) the buyers arrive sequentially, with each buyer i N observing their signal si and being proposed price fi(si). Then, each buyer rationally updates their prior belief over states according to Bayes rule, and buys the item only if their expected valuation for the item is greater than or equal to the offered price. The interaction terminates whenever a buyer decides to buy the item or there are no more buyers arriving. The following paragraph formally deﬁnes the elements involved in step (iv).

Buyers Posteriors. In step (iv), a buyer i N receiving a signal si Si infers a posterior belief over states (also called posterior), which we denote by ξi,si Θ, with ξi,si(θ) being the posterior probability of state θ Θ. Formally,

ξi,si(θ) := µθφi,θ(si) P θ Θ µθ φi,θ (si). (1)

Thus, after receiving signal si Si, buyer i s expected valuation for the item is P θ Θ vi(θ) ξi,si(θ), and the buyer buys it only if such value is at least as large as the price fi(si). In the following, given a signal proﬁle s S, we denote by ξs a tuple deﬁning all buyers posteriors resulting from observing signals in s; formally, ξs := (ξ1,s1, . . . , ξn,sn).

Distributions on Posteriors. In single-receiver Bayesian persuasion models, it is oftentimes useful to represent signaling schemes as convex combinations of the posteriors they can induce. In our setting, a marginal signaling scheme φi : Θ Si of buyer i N induces a probability distribution γi over posteriors in Θ, with γi(ξi) denoting the probability of posterior ξi Θ. Formally, it holds that

γi(ξi) := X

si Si:ξi,si=ξi

θ Θ µθφi,θ(si).

Intuitively, γi(ξi) denotes the probability that buyer i has posterior ξi. Indeed, it is possible to directly reason about distributions γi rather than marginal signaling schemes, provided that such distributions are consistent with the prior. Formally, by letting supp(γi) := {ξi Θ | γi(ξi) > 0} be the support of γi, it must be required that X

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

2.2 Computational Problems We focus on the problem of computing a signaling scheme φ : Θ S and a price function f : S [0, 1]n that maximize the seller s expected revenue, considering both public and private signaling settings.6

6Formally, a signaling scheme φ : Θ S is public if: (i) Si = Sj for all i, j N; and (ii) for every θ Θ, φθ(s) > 0 only for

We denote by REV(V, p, ξ) the expected revenue of the seller when the distributions of buyers valuations are given by V = {Vi}i N , the proposed prices are deﬁned by the vector p [0, 1]n, and the buyers posteriors are those speciﬁed by the tuple ξ = (ξ1, . . . , ξn) containing a posterior ξi Θ for each buyer i N. Then, the seller s expected revenue is: X

s S φθ(s)REV (V, f(s), ξs) .

In the following, we denote by OPT the value of the seller s expected revenue for a revenue-maximizing (φ, f) pair. In this work, we assume that algorithms have access to a black-box oracle to sample buyers valuations according to the probability distributions speciﬁed by V (rather than actually knowing such distributions). Thus, we look for algorithms that output pairs (φ, f) such that

s S φθ(s)REV(V, f(s), ξs)

where λ 0 is an additive error. Notice that the expectation above is with respect to the randomness of the algorithm, which originates from using the black-box sampling oracle.

3 Hardness of Signaling with a Single Buyer We start with a negative result: there is no FPTAS for the problem of computing a revenue-maximizing (φ, f) pair unless P = NP, in both public and private signaling settings. Our result holds even in the basic case with only one buyer, where public and private signaling are equivalent. Notice that, in the reduction that we use to prove our result, we assume that the support of the distribution of valuations of the (single) buyer is ﬁnite and that such distribution is perfectly known to the seller. This represents an even simpler setting than that in which the seller has only access to a black-box oracle returning samples drawn from the buyer s distribution of valuations. The result formally reads as follows:7

Theorem 1. There is no additive FPTAS for the problem of computing a revenue-maximizing (φ, f) pair unless P = NP, even when there is a single buyer.

4 Unifying Public and Private Signaling In this section, we introduce a general mathematical framework related to buyers posteriors and distributions over them, proving some results that will be crucial in the rest of this work, both in public and private signaling scenarios. One of the main difﬁculties in computing sender-optimal signaling schemes is that they might need a (potentially) inﬁnite number of signals, resulting in inﬁnitely-many receiver s

signal proﬁles s S such that si = sj for i, j N . Since, given a signal proﬁle s S, under a public signaling scheme all the buyers always share the same posterior (i.e., ξi,si = ξj,sj for all i, j N ), we overload notation and sometimes use ξs Θ to denote the unique posterior appearing in ξs = (ξ1,s1,, . . . , ξn,sn). Similarly, in the public setting, given a posterior ξ Θ we sometimes write ξ in place of a tuple of n copies of ξ. 7The proofs of all the results are in (Castiglioni et al. 2022).

posteriors. The trick commonly used to circumvent this issue in settings with a ﬁnite number of valuations is to use direct signals, which explicitly specify action recommendations for each receiver s valuation (Castiglioni et al. 2020, 2021b). However, in our auction setting, this solution is not viable, since a direct signal for a buyer i N should represent a recommendation for every possible vi [0, 1]d, and these are inﬁnitely many. An alternative technique, which can be employed in our setting, is to restrict the number of possible posteriors. Our core idea is to focus on a small set of posteriors, which are those encoded as particular q-uniform probability distributions, as formally stated in the following deﬁnition.8

Deﬁnition 1 (q-uniform posterior). A posterior ξ Θ is q-uniform if it can be obtained by averaging the elements of a multiset deﬁned by q N>0 canonical basis vectors of Rd.

We denote the set of all q-uniform posteriors as Ξq Θ. Notice that the set Ξq has size |Ξq| = O (dq). The existence of an approximately-optimal signaling scheme that only uses q-uniform posteriors is usually proved by means of so-called decomposition lemmas (see (Cheng et al. 2015; Xu 2020; Castiglioni and Gatti 2021)). The goal of these lemmas is to show that, given some signaling scheme encoded as a distribution over posteriors, it is possible to obtain a new signaling scheme whose corresponding distribution is supported only on q-uniform posteriors, and such that the sender s utility only decreases by a small amount. At the same time, these lemmas must also ensure that the distribution over posteriors corresponding to the new signaling scheme is still consistent (according to Equation (2)). The main result of our framework (Theorem 2) is a decomposition lemma that is suitable for our setting. Before stating the result, we need to introduce some preliminary deﬁnitions. Deﬁnition 2 ((α, ϵ)-decreasing distribution). Let α, ϵ > 0. A probability distribution γ over Θ is (α, ϵ)-decreasing around a given posterior ξ Θ if the following condition holds for every matrix V [0, 1]n d of buyers valuations:

Pr ξ γ n Vi ξ Viξ ϵ o 1 α i N.

Intuitively, a probability distribution γ as in Deﬁnition 2 can be interpreted as a perturbation of the given posterior ξ such that, with high probability, buyers expected valuations in γ are at most ϵ less than those in posterior ξ.9 The second deﬁnition we need is about functions mapping vectors in [0, 1]n deﬁning a valuation for each buyer to seller s revenues. For instance, one such function could be the seller s revenue given price vector p [0, 1]n. In particular, we deﬁne the stability of a function g compared to another function h. Intuitively, g is stable compared to h if

8In all the deﬁnitions and results of this section (Section 4), we denote by ξ Θ a generic posterior common to all the buyers and with γ a probability distribution over Θ (i.e, over posteriors). 9Deﬁnition 2 is similar to analogous ones in the literature (Xu 2020; Castiglioni and Gatti 2021), where the distance is usually measured in both directions, as |Vi ξ Viξ| ϵ. We look only at the direction of decreasing values, since in a our setting, if a buyer s valuation increases, then the seller s revenue also increases.

the value of g, in expectation over buyers valuations and posteriors drawn from a probability distribution γ that is (α, ϵ)-decreasing around ξ, is close to the the value of h given ξ, in expectation over buyers valuations.10 Formally: Deﬁnition 3 ((δ, α, ϵ)-stability). Let α, ϵ, δ > 0. Given a posterior ξ Θ, some distributions V = {Vi}i N , and two functions g, h : [0, 1]n [0, 1], g is (δ, α, ϵ)-stable compared to h for (ξ, V) if, for every probability distribution γ over Θ that is (α, ϵ)-decreasing around ξ, it holds:

E ξ γ,V V h g(V ξ) i (1 α)EV V h h(V ξ) i δϵ.

Now, we are ready to state our main result. We show that, for any buyer s posterior ξ Θ, if a function g is stable compare to h, then there exists a suitable probability distribution over q-uniform posteriors such that the expected value of g given such distribution is close to that of h given ξ. Theorem 2. Let α, ϵ, δ > 0, and set q := 32

α. Given a posterior ξ Θ, some distributions V = {Vi}i N , and two functions g, h : [0, 1]n [0, 1], if g is (δ, α, ϵ)-stable compared to h for (ξ, V), then there exists γ Ξq such that, for every θ Θ, P ξ supp(γ) γ( ξ) ξ(θ) = ξ(θ) and

h ξ(θ)g(V ξ) i ξ(θ) h (1 α)EV V h h(V ξ) i δϵ i . (3)

The crucial feature of Theorem 2 is that Equation (3) holds for every state. This is fundamental for proving our results in the private signaling scenario. On the other hand, with public signaling, we will make use of the following (weaker) corollary, obtained by summing Equation (3) over all θ Θ. Corollary 1. Let α, ϵ, δ > 0, and set q := 32

α. Given a posterior ξ Θ, some distributions V = {Vi}i N , and two functions g, h : [0, 1]n [0, 1], if g is (δ, α, ϵ)-stable compared to h for (ξ, V), then there exists γ Ξq such that, for every θ Θ, P ξ supp(γ) γ( ξ) ξ(θ) = ξ(θ) and

E ξ γ,V V h g(V ξ) i (1 α)EV V h h(V ξ) i δϵ. (4)

5 Warming Up: Non-Bayesian Auctions In this section, we focus on non-Bayesian posted price auctions, proving some results that will be useful in the rest of the paper.11 In particular, we study what happens to the seller s

10The notion of compared stability has been already used (Cheng et al. 2015; Castiglioni and Gatti 2021). However, previous works consider the case in which g is a relaxation of h. Instead, our deﬁnition is conceptually different, as g and h represent two different functions corresponding to different price vectors of the seller. 11When we study non-Bayesian posted price auctions, we stick to our notation, with the following differences: valuations are scalars rather than vectors, namely vi [0, 1]; distributions Vi are supported on [0, 1] rather than [0, 1]d; the matrix V is indeed a column vector whose components are buyers valuations; and the price function f is replaced by a single price vector p [0, 1]n, with its i-th component pi being the price for buyer i N. Moreover, we continue to use the notation REV to denote seller s revenues, dropping the dependence on the tuple of posteriors. Thus, in a non Bayesian auction in which the distributions of buyers valuations are V = {Vi}i N , the notation REV(V, p) simply denotes the seller s expected revenue by selecting a price vector p [0, 1]n.

expected revenue when buyers valuations are slightly decreased , proving that the revenue also decreases, but only by a small amount. This result will be crucial when dealing with public signaling, and it also allows to design a poly-time algorithm for ﬁnding approximately-optimal price vectors in non-Bayesian auctions, as we show at the end of this section. In the following, we extensively use distributions of buyers valuations as speciﬁed in the deﬁnition below. Deﬁnition 4. Given ϵ > 0, we denote by V = {Vi}i N and Vϵ = {Vϵ i }i N two collections of distributions of buyers valuations such that, for every price vector p [0, 1]n, Prvi Vϵ i {vi pi ϵ} Prvi Vi {vi pi} i N. Intuitively, valuations drawn from Vϵ are slightly decreased with respect to those drawn from V, since the probability with which any buyer i N buys the item at the (reduced) price [pi ϵ]+ when their valuation is drawn from Vϵ i is at least as large as the probability of buying at price pi when their valuation is drawn from Vi.12 Our main contribution in this section (Lemma 2) is to show that maxp [0,1]n REV(Vϵ, p) maxp [0,1]n REV(V, p) ϵ. By letting p arg maxp [0,1]n REV(V, p) be any revenuemaximizing price vector under distributions V, one may naïvely think that, since under distributions Vϵ and price vector [p ϵ]+ each buyer would buy the item at least with the same probability as with distributions V and price vector p , while paying a price that is only ϵ less, then REV(Vϵ, [p ϵ]+) REV(V, p ) ϵ, proving the result. However, this line of reasoning does not work, as shown by Example ?? in the Extended Version. The crucial feature of Example ?? is that there exists a p in which one buyer is offered a price that is too low, and, thus, the seller prefers not to sell the item to them, but rather to a following buyer. This prevents a direct application of the line of reasoning outlined above, as it shows that incrementing the probability with which a buyer buys is not always beneﬁcial. One could circumvent this issue by considering a p such that the seller is never upset if some buyer buys. In other words, it must be such that each buyer is proposed a price that is at least as large as the seller s expected revenue in the posted price auction restricted to the following buyers. Next, we show that there always exists a p with such desirable property. Letting REV>i(V, p) be the seller s revenue for price vector p [0, 1]n and distributions V = {Vi}i N in the auction restricted to buyers j N : j > i, we prove the following: Lemma 1. For any V = {Vi}i N , there exists a revenuemaximizing price vector p arg maxp [0,1]n REV(V, p) such that p i REV>i(V, p ) for every buyer i N. The proof of Lemma 2 builds upon the existence of a revenue-maximizing price vector p [0, 1]n as in Lemma 1 and the fact that, under distributions Vϵ, the probability with which each buyer buys the item given price vector [p ϵ]+ is greater than that with which they would buy given p . Since the seller s expected revenue is larger when a buyer buys compared to when they do not buy (as p i REV>i(V, p )), the seller s expected revenue decreases by at most ϵ.

12In this work, given x R, we let [x]+ := max{x, 0}. We extend the [ ]+ operator to vectors by applying it component-wise.

Algorithm 1: FIND-APX-PRICES Inputs: # of samples K N>0; # of discretization steps b N>0 1: for i N do 2: for k = 1, . . . , K do 3: vk i Sample buyer i s valuation using oracle for Vi 4: VK i Empirical distribution of the K i.i.d. samples v K i 5: VK {VK i }i N ; p 0n; r 0 6: for i = n, . . . , 1 (in reversed order) do 7: pi arg max p i P b p i Prvi VK i vi p i + 1 Prvi VK i vi p i r

8: r pi Prvi VK i {vi pi} + 1 Prvi VK i {vi pi} r

9: return (p, r)

Lemma 2. Given ϵ > 0, let V = {Vi}i N and Vϵ = {Vϵ i }i N satisfying the conditions of Deﬁnition 4. Then, maxp [0,1]n REV(Vϵ, p) maxp [0,1]n REV(V, p) ϵ.

Lemma 2 will be useful to prove Lemma 3 and to show the compared stability of a suitably-deﬁned function that is used to design a PTAS in the public signaling scenario.

Finding Approximately-Optimal Prices. Algorithm 1 computes (in polynomial time) an approximately-optimal price vector for any non-Bayesian posted price auction. It samples K N>0 matrices of buyers valuations, each one drawn according to the distributions V. Then, it ﬁnds an optimal price vector p in the discretized set Pb, assuming that buyers valuations are drawn according to the empirical distribution resulting from the sampled matrices.13 This last step can be done by backward induction, as it is well known in the literature (see, e.g., (Xiao, Liu, and Huang 2020)). The following Lemma 3 establishes the correctness of Algorithm 1, also providing a bound on its running time. The key ideas of its proof are: (i) the sampling procedure constructs a good estimation of the actual distributions of buyers valuations; and (ii) even if the algorithm only considers discretized prices, the components of the computed price vector are at most 1/b less than those of an optimal (unconstrained) price vector. As shown in the proof, this is strictly related to reducing buyer s valuations by 1

b. Thus, it follows by Lemma 2 that the seller s expected revenue is at most 1/b less than the optimal one.

Lemma 3. For any V = {Vi}i N and ϵ, τ > 0, there exist K poly n, 1

τ and b poly 1

ϵ such that, with probability at least 1 τ, Algorithm 1 returns (p, r) satisfying REV(V, p) maxp [0,1]n REV(V, p ) ϵ and r [REV(V, p) ϵ, REV(V, p) + ϵ] in time poly n, 1

6 Public Signaling In the following, we design a PTAS for computing a revenuemaximizing (φ, f) pair in the public signaling setting. Notice that this positive result is tight by Theorem 1. As a ﬁrst intermediate result, we prove the compared stability of suitably-deﬁned functions, which are intimately related to the seller s revenue. In particular, for every price vector

13In this work, for a discretization step b N>0, we let P b [0, 1] be the set of prices multiples of 1/b, while Pb := i N P b.

p [0, 1]n, we conveniently let gp : [0, 1]n [0, 1] be a function that takes a vector of buyers valuations and outputs the seller s expected revenue achieved by selecting p when the buyers valuations are those speciﬁed as input. The following Lemma 4 shows that, given some distributions of buyers valuations V and a posterior ξ Θ, there always exists a price vector p [0, 1]n such that gp is stable compared with gp for every other p [0, 1]n. This result crucially allows us to decompose any posterior ξ Θ by means of the decomposition lemma in Corollary 1, while guaranteeing a small loss in terms of seller s expected revenue.

Lemma 4. Given α, ϵ > 0, a posterior ξ Θ, and some distributions of buyers valuations V = {Vi}i N , there exists p [0, 1]n such that, for every other p [0, 1]n, the function gp is (1, α, ϵ)-stable compared with gp for (ξ, V).

Our PTAS leverages the fact that public signaling schemes can be represented as probability distributions over buyers posteriors (recall that, in the public signaling setting, all the buyers share the same posterior, as they all observe the same signal). In particular, the algorithm returns a pair (γ, f ), where γ is a probability distribution over Θ satisfying consistency constraints (see Equation (2)), while f : Θ [0, 1]n is a function mapping each posterior to a price vector. In single-receiver settings, it is well known (see Subsection 2.1) that using distributions over posteriors rather than signaling schemes φ is without loss of generality. The following lemma shows that the same holds in our case, i.e., given a pair (γ, f ), it is always possible to obtain a pair (φ, f) providing the seller with the same expected revenue.

Lemma 5. Given a pair (γ, f ), where γ is a probability distribution over Θ with P ξ supp(γ) γ(ξ)ξ(θ) = µθ for all θ Θ and f : Θ [0, 1]n, there is a pair (φ, f) s.t. X

s S φθ(s)REV(V, f(s), ξs)= X

ξ supp(γ) γ(ξ)REV(V, f (ξ), ξ).

Next, we show that, in order to ﬁnd an approximatelyoptimal pair (γ, f ), we can restrict the attention to q-uniform posteriors (with q suitably deﬁned). First, we introduce the following LP that computes an optimal probability distribution restricted over q-uniform posteriors.

ξ Ξq γ(ξ) max p [0,1]n REV(V, p, ξ) s.t. (5a)

ξ Ξq γ(ξ) ξ(θ) = µθ θ Θ. (5b)

The following Lemma 6 shows the optimal value of LP 5 is close to OPT. Its proof is based on the following core idea. Given the signaling scheme φ in a revenue-maximizing pair (φ, f), letting γ be the distribution over Θ induced by φ, we can decompose each posterior in the support of γ according to Corollary 1. Then, the obtained distributions over q-uniform posteriors are consistent according to Equation (2), and, thus, they satisfy Constraints (5b). Moreover, since such distributions are also decreasing around the decomposed posteriors, by Lemma 4 each time a posterior is decomposed there exists a price vector resulting in a small

revenue loss. These observations allow us to conclude that the seller s expected revenue provided by an optimal solution to LP 5 is within some small additive loss of OPT. Lemma 6. Given η > 0 and letting q = 1 η2 128 log 6

η, an optimal solution to LP 5 has value at least OPT η. Finally, we are ready to provide our PTAS. Its main idea is to solve LP 5 (of polynomial size) for the value of q in Lemma 6. This results in a small revenue loss. The last part missing for the algorithm is computing the terms appearing in the objective of LP 5, i.e., a revenue-maximizing price vector (together with its revenue) for every q-uniform posterior. In order to do so, we can use Algorithm 1 (see also Lemma 3), which allows us to obtain in polynomial time good approximations of such price vectors, with high probability. Theorem 3. There exists an additive PTAS for computing a revenue-maximizing (φ, f) pair with public signaling.

7 Private Signaling With private signaling, computing a (φ, f) pair amounts to specifying a pair (φi, fi) for each buyer i N composed by a marginal signaling scheme φi : Θ Si and a price function fi : Si [0, 1] for buyer i , and, then, correlating the φi so as to obtain a (non-marginal) signaling scheme φ : Θ S. We leverage this fact to design our PTAS. In Subsection 7.1, we ﬁrst show that it is possible to restrict the set of marginal signaling schemes of a given buyer i N to those encoded as distributions over q-uniform posteriors, as we did with public signaling. Then, we provide an LP formulation for computing an approximately-optimal (φ, f) pair, dealing with the challenge of correlating marginal signaling schemes in a non-trivial way. Finally, in Subsection 7.2, we show how to compute a solution to the LP in polynomial time, which requires the application of the ellipsoid method in a non-trivial way, due to the features of the formulation.

7.1 LP for Approximate Signaling Schemes Before providing the LP, we show that restricting marginal signaling schemes to q-uniform posteriors results in a buyer s behavior which is similar to the one with arbitrary posteriors. This amounts to showing that suitably-deﬁned functions related to the probability of buying are comparatively stable. For i N and pi [0, 1], let gi,pi : [0, 1]n {0, 1} be a function that takes as input a vector of buyers valuations and outputs 1 if and only if vi pi (otherwise it outputs 0). Lemma 7. Given α, ϵ > 0 and some distributions V = {Vi}i N , for every buyer i N, posterior ξi Θ, and price pi [0, 1], the function gi,[pi ϵ]+ is (0, α, ϵ)-stable compared with gi,pi for (ξi, V). The following remark will be crucial for proving Lemma 9. It shows that, if for every i N we decompose buyer i s posterior ξi Θ by means of a distribution over q-uniform posteriors (α, ϵ)-decreasing around ξi, then the probability with which buyer i buys only decreases by a small amount.14

14In this section, for the ease of presentation, we abuse notation and use Ξq i to denote the (all equal) sets of q-uniform posteriors (Deﬁnition 1), one per buyer i N, while Ξq := i N Ξq i is the set of tuples ξ = (ξ1, . . . , ξn) specifying a ξi Ξq i for each i N .

Remark 1. Lemma 7 and Theorem 2 imply that, given a tuple of posteriors ξ = (ξ1, . . . , ξn) i N θ and some distributions V = {Vi}i N , for every buyer i N and price pi [0, 1], there exists γi Ξq i with q = 32

h ξi(θ) Pr V V

n Vi ξi [pi ϵ]+ oi ξi(θ)(1 α) Pr V V{Viξi pi}

and P ξi Ξq i γi( ξi) ξi(θ) = ξi(θ) for all θ Θ.

Next, we show that an approximately-optimal pair (φ, f) can be found by solving LP 6 instantiated with suitablydeﬁned q N>0 and b N>0. LP 6 employs: Variables γi,ξi (for i N and ξi Ξq i ), which encode the distributions over posteriors representing the marginal signaling schemes φi : Θ Si of the buyers. Variables ti,ξi,pi (for i N, ξi Ξq i , and pi P b), with ti,ξi,pi encoding the probability that the seller offers price pi to buyer i and buyer i s posterior is ξi. Variables yθ,ξ,p (for θ Θ, ξ Ξq, and p Pb), with yθ,ξ,p encoding the probability that the state is θ, the buyers posteriors are those speciﬁed by ξ, and the prices that the seller offers to the buyers are those given by p.

max γ,t,y 0

p Pb yθ,ξ,p REV(V, p, ξ) s.t. (6a)

ξi(θ)ti,ξi,pi = X

ξ Ξq:ξ i=ξi

p Pb:p i=pi yθ,ξ ,p

θ Θ, i N, ξi Ξq i , pi P b (6b) X

pi P b ti,ξi,pi = γi,ξi i N, ξi Ξq i (6c)

ξi Ξq i γi,ξi ξi(θ) = µθ i N, θ Θ. (6d)

Variables ti,ξi,pi represent marginal signaling schemes, allowing for multiple signals inducing the same posterior. This is needed since signals may correspond to different price proposals.15 One may think of marginal signaling schemes in LP 6 as if they were using signals deﬁned as pairs si = (ξi, pi), with the convention that fi(si) = pi. Variables yθ,ξ,p and Constraints (6b) ensure that marginal signaling schemes are correctly correlated together, by directly working in the domain of the distributions over posteriors. To show that an optimal solution to LP 6 provides an approximately-optimal (φ, f) pair, we need the following two lemmas. Lemma 8 proves that, given a feasible solution to LP 6, we can recover a pair (φ, f) providing the seller with an expected revenue equal to the value of the LP solution. Lemma 9 shows that the optimal value of LP 6 is close to OPT. These two lemmas imply that an approximatelyoptimal (φ, f) pair can be computed by solving LP 6.

15Notice that, in a classical setting in which the sender does not have to propose a price (or, in general, select some action after sending signals), there always exists a signaling scheme with no pair of signals inducing the same posterior. Indeed, two signals that induce the same posterior can always be joined into a single signal. This is not the case in our setting, where we can only join signals that induce the same posterior and correspond to the same price.

Lemma 8. Given a feasible solution to LP 6, it is possible to recover a pair (φ, f) that provides the seller with an expected revenue equal to the value of the solution.

Lemma 9. For every η > 0, there exist b(η), q(η) N>0 such that LP 6 has optimal value at least OPT η.

7.2 PTAS We provide an algorithm that approximately solves LP 6 in polynomial time, which completes our PTAS for computing a revenue-maximizing pair (φ, f) in the private setting. The core idea of our algorithm is to apply the ellipsoid method on the dual of LP 6.16 In particular, our implementation of the ellipsoid algorithm uses an approximate separation oracle that needs to solve the following optimization problem. Deﬁnition 5 (MAX-LINREV). Given some distributions of buyers valuations V = {Vi}i N such that each Vi has ﬁnite support and a vector w [0, 1]n |Ξq i | |P b|, solve

max ξ Ξq,p Pb REV(V, p, ξ) + X

i N wi,ξi,pi.

As a ﬁrst step, we provide an FPTAS for MAX-LINREV using a dynamic programming approach. This will be the main building block of our approximate separation oracle.17 The FPTAS works as follows. Given an error tolerance δ > 0, it ﬁrst deﬁnes a step size 1

c, with c = n

δ , and builds a set A = {0, 1

c, . . . , n} of possible discretized values for the linear term appearing in the MAX-LINREV objective. Then, for every buyer i N (in reversed order) and value a A, the algorithm computes M(i, a), which is an approximation of the largest seller s revenue provided by a pair (ξ, p) when considering buyers i, . . . , n only, and restricted to pairs (ξ, p) such that the inequality P j N :j i wj,ξj,pj a is satisﬁed. By letting zi := Prvi Vi v i ξi pi , the value M(i, a) can be deﬁned by the following recursive formula:18

M(i, a) := max ξi Ξq i ,pi P b

a A:wi,ξi,pi+a a

zipi + (1 zi) M(i + 1, a ).

Finally, the algorithm returns maxa A {M(1, a) + a}. Thus: Lemma 10. For any δ > 0, there exists a dynamic programming algorithm that provides a δ-approximation (in the additive sense) to MAX-LINREV. Moreover, the algorithm runs in time polynomial in the size of the input and 1

δ . Now, we are ready to prove the main result of this section. Theorem 4. There exists an additive PTAS for computing a revenue-maximizing (φ, f) pair with private signaling.

16To be precise, we apply the ellipsoid method to the dual of a relaxed version of LP 6, since we need an over-constrained dual. More details on these technicalities are in the Extended Version. 17Notice that, since MAX-LINREV takes as input distributions with a ﬁnite support, we can safely assume that such distributions can be explicitly represented in memory. In our PTAS, the inputs to the dynamic programming algorithm are obtained by building empirical distributions through samples from the actual distributions of buyers valuations, thus ensuring ﬁniteness of the supports. 18Notice that, given a pair (ξ, p) with ξ Ξq and p Pb, it is possible to compute in polynomial time the probability with which a buyer i N buys the item.

Acknowledgments

This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR Algorithms, Games, and Digital Market .

References Adamczyk, M.; Borodin, A.; Ferraioli, D.; Keijzer, B. D.; and Leonardi, S. 2017. Sequential posted-price mechanisms with correlated valuations. ACM Transactions on Economics and Computation (TEAC), 5(4): 1 39. Babaioff, M.; Blumrosen, L.; Dughmi, S.; and Singer, Y. 2017. Posting prices with unknown distributions. ACM Transactions on Economics and Computation (TEAC), 5(2): 1 20. Babaioff, M.; Dughmi, S.; Kleinberg, R.; and Slivkins, A. 2015. Dynamic pricing with limited supply. ACM Transactions on Economics and Computation (TEAC), 3(1): 1 26. Bacchiocchi, F.; Castiglioni, M.; Marchesi, A.; Romano, G.; and Gatti, N. 2022. Public Signaling in Bayesian Ad Auctions. Co RR, abs/2201.09728. Badanidiyuru, A.; Bhawalkar, K.; and Xu, H. 2018. Targeting and Signaling in Ad Auctions. In Proceedings of the Twenty Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2545 2563. Candogan, O. 2019. Persuasion in networks: Public signals and k-cores. In Proceedings of the 2019 ACM Conference on Economics and Computation, 133 134. Castiglioni, M.; Celli, A.; and Gatti, N. 2020a. Persuading Voters: It s Easy to Whisper, It s Hard to Speak Loud. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 34, 1870 1877. Castiglioni, M.; Celli, A.; and Gatti, N. 2020b. Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive. Co RR, abs/2002.05156. Castiglioni, M.; Celli, A.; Marchesi, A.; and Gatti, N. 2020. Online Bayesian Persuasion. In Advances in Neural Information Processing Systems, volume 33, 16188 16198. Castiglioni, M.; Celli, A.; Marchesi, A.; and Gatti, N. 2021a. Signaling in Bayesian Network Congestion Games: the Subtle Power of Symmetry. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 35, 5252 5259. Castiglioni, M.; and Gatti, N. 2021. Persuading Voters in District-based Elections. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 35, 5244 5251. Castiglioni, M.; Marchesi, A.; Celli, A.; and Gatti, N. 2021b. Multi-Receiver Online Bayesian Persuasion. In Proceedings of the 38th International Conference on Machine Learning, 1314 1323. Castiglioni, M.; Marchesi, A.; and Gatti, N. 2022. Bayesian Persuasion Meets Mechanism Design: Going Beyond Intractability with Type Reporting. ar Xiv:2202.00605. Castiglioni, M.; Romano, G.; Marchesi, A.; and Gatti, N. 2022. Signaling in Posted Price Auctions. ar Xiv preprint ar Xiv:2201.12183.

Chawla, S.; Hartline, J. D.; Malec, D. L.; and Sivan, B. 2010. Multi-parameter mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM symposium on Theory of computing, 311 320. Cheng, Y.; Cheung, H. Y.; Dughmi, S.; Emamjomeh-Zadeh, E.; Han, L.; and Teng, S. 2015. Mixture Selection, Mechanism Design, and Signaling. In 56th Symposium on Foundations of Computer Science, 1426 1445. Correa, J.; Foncea, P.; Hoeksma, R.; Oosterwijk, T.; and Vredeveld, T. 2017. Posted price mechanisms for a random stream of customers. In Proceedings of the 2017 ACM Conference on Economics and Computation, 169 186. Einav, L.; Farronato, C.; Levin, J.; and Sundaresan, N. 2018. Auctions versus posted prices in online markets. Journal of Political Economy, 126(1): 178 215. e Marketer. 2021. Worldwide ecommerce will approach $5 trillion this year. https://www.emarketer.com/content/ worldwide-ecommerce-will-approach-5-trillion-this-year. Accessed: 2021-09-02. Emek, Y.; Feldman, M.; Gamzu, I.; Paes Leme, R.; and Tennenholtz, M. 2014. Signaling schemes for revenue maximization. ACM Transactions on Economics and Computation (TEAC), 2(2): 1 19. Kamenica, E.; and Gentzkow, M. 2011. Bayesian persuasion. American Economic Review, 101(6): 2590 2615. Kleinberg, R.; and Leighton, T. 2003. The value of knowing a demand curve: Bounds on regret for pricing-price auctions. In 44th Symposium on Foundations of Computer Science, 594 605. Rabinovich, Z.; Jiang, A. X.; Jain, M.; and Xu, H. 2015. Information disclosure as a means to security. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, 645 653. Romano, G.; Tartaglia, G.; Marchesi, A.; and Gatti, N. 2021. Online Posted Pricing with Unknown Time-Discounted Valuations. In Proceedings of the AAAI Conference on Artiﬁcial Intelligence, volume 35, 5682 5689. Seifert, S. 2006. Posted price offers in internet auction markets, volume 580. Springer Science & Business Media. Shah, V.; Johari, R.; and Blanchet, J. 2019. Semi-Parametric Dynamic Contextual Pricing. In Advances in Neural Information Processing Systems, volume 32, 2363 2373. Vasserman, S.; Feldman, M.; and Hassidim, A. 2015. Implementing the wisdom of waze. In Proceedings of the Twenty Fourth International Joint Conference on Artiﬁcial Intelligence, 660 666. Xiao, T.; Liu, Z.; and Huang, W. 2020. On the Complexity of Sequential Posted Pricing. In Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 1521 1529. Xu, H. 2020. On the Tractability of Public Persuasion with No Externalities. In Chawla, S., ed., Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2708 2727.