Learning to Price with Persuasion

Learning to Price with Persuasion Maria-Florina Balcan1 , Tejas Pagare1 , and Karan Singh1 1

Carnegie Mellon University, Pittsburgh, USA ninamf@cs.cmu.edu, tpagare@andrew.cmu.edu, karansingh@cmu.edu

arXiv:2608.16699v1 [cs.GT] 17 Aug 2026

Abstract Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al. (2022), where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer’s taste via a signaling scheme. We relax the assumption that the seller knows the buyers’ belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers’ behaviors to seller’s schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was left open by Bergemann et al. (2022). Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.

1

Introduction

A cornerstone of microeconomic theory is information asymmetry. Economic agents participating in a market might have latent preferences (or motives) invisible to the market maker. The foundational works of Spence (1973); Akerlof (1970) detail signaling mechanisms by which participants can partially overcome this information asymmetry, and market failures that result from the unmitigated presence of these circumstances. However, in recent years, the presence of monolithic algorithmic marketplaces has altered this picture. Such marketplaces routinely gather detailed user profiles, consisting of both demographic data and the history of past purchases. For example, recently, a shopper was surprised to discover that Kroger, a not particularly tech-savy retail giant in the US, had a 62-page shopping profile on them, including details like pet ownership and travel history (Kravitz, 2025). As a result, such digital platforms can forecast the personalized value a product or service holds for a given buyer much more accurately than individual buyers themselves. As another example, Google, as an advertising marketplace serving a trillion impressions every month, can arguably estimate the conversion rate associated with displaying a specific advertisement in a specific spot far more accurately than individual publishers. We consider one of the most foundational problems, namely, monopolistic screening (Mussa and Rosen, 1978; Maskin and Riley, 1984), albeit in the presence of such an informationally advantaged seller. In the classical problem, a monopolist aims to maximize the revenue gathered from a pool of buyers who have a certain distribution of latent tastes, by offering a menu of quality-price pairs. Products of higher quality also cost the monopolist more. By offering a menu of varied qualities at different price points, the seller can simultaneously appeal to disparate buyers whose utility for a given product is a function of both their latent taste and the product’s quality. In the new-age model, proposed by Bergemann et al. (2022) (also see Bergemann et al. (2026b)), the key distinction is that the seller can forecast the utility that a buyer with a certain taste associates with different product qualities, far better than the buyers themselves. A notable constraint on the seller is that in spite of knowing the buyer’s utility precisely she can not engage in perfect 1

Model

Value distribution

Sample Complexity / Regret

Value samples Demand queries

Arbitrary Discrete Bounded pdf Lipschitz pdf Analytic pdf

Joint learning

Arbitrary

3 e O(1/ε ) O(1) 2 e O(1/ε ) e O(1/ε) O(polylog 1/ε) e 3/4 ) O(T

Figure 1: Summary of our results. For value samples and demand queries, we list the sample requirements to produce an ε-optimal menu along with the associated signaling scheme. The last row lists the regret in a T -horizon game. price discrimination (driving the consumer surplus to zero), because existing regulations exclude explicit price discrimination in most markets (Mansoor, 2026). Thus, in addition to designing a public menu of quality-price pairs, the seller commits to releasing partial information about the value of buyer-quality matches via a signaling scheme of their choice allowing an indirect price discrimination. In practice, one can think of such a signal as a personalized recommendation to the buyer indicating what product (quality) she should purchase (or in a softer manner through search rankings). Recommendation algorithms in this context play the role of a commitment device. For example, Amazon labels certain products, which are neither the ones with the highest rating nor the highest number of reviews, as Amazon’s choice. Such personalized recommendations can be viewed as signals to the buyer. To design a revenue maximizing menu and signaling scheme in the above context, it is typically assumed that the seller knows the precise distribution of the buyer’s tastes. This is implausible given the diversity of products sold on modern marketplaces, and in this work, we relax this assumption. Instead, we consider explicit learning algorithms that dictate how such knowledge may be acquired via samples and past interactions, with explicit bounds on sample and compute requirements. Concretely, we make the following contributions (also partly summarized in Figure 1). 3 e ) i.i.d. samples from the buyers’ taste (or as we will 1. We give a learning algorithm that when given O(1/ε call it going forward, value) distribution, produces a signaling scheme and menu that achieves a revenue within ε of the maximum.

2. The problem of jointly designing a menu and a signaling scheme is non-convex, as noted in Bergemann et al. (2022). Despite this, we give the first FPTAS that computes a solution in polynomial time with revenue within an arbitrarily small additive loss of the optimum. 3. We also study a demand query model, where the seller can observe how the buyers behave in presence of the menus and signaling schemes she designs. In this interactive setting, we obtain a constant sample 2 e complexity for discrete value distributions and improve to O(1/ε ) samples for continuous distributions with bounded pdfs. Further smoothness assumptions result in smaller sample requirements; for example, polylogarithmic for analytic pdfs. 4. Finally, we give regret upper bounds for a model in which both the seller and the buyer population jointly learn in an online setting based on the past realizations of values. In this setting, the seller has to design schemes that are somewhat robust to the buyers’ beliefs, which are incompletely specified.

1.1

Related Work

In economics, the nonlinear pricing problem introduced in Mussa and Rosen (1978) and further studied in Maskin and Riley (1984) characterizes the optimal quality, price menus for a revenue maximizing monopolist seller facing privately informed random buyer or a population of buyer with known value distribution. See Wilson (1993) for a broader survey and Bolton and Dewatripont (2004) for the simplified analysis for

2

computing optimal menu.The information design literature in which a informationally advantaged sender influences receiver via communication was initially popularized by a cheap talk model Crawford and Sobel (1982). This was then formalized with a commitment power to the sender on distribution of messages as Bayesian Persuasion in Kamenica and Gentzkow (2011). See Bergemann and Morris (2019); Kamenica (2019) for a survey treatment. This was then translated to the linear bayesian persuasion setting Gentzkow and Kamenica (2016); Dworczak and Martini (2019) where the senders’ utility is solely characterized by the expected posterior value. We build on Bergemann et al. (2026b), who prove that the seller-optimal joint design always takes a monotone partitional form with finitely many signals and menu items. See also Bergemann et al. (2026a) for more developments on the joint mechanism and information design problem. The intersection of machine learning and economics is now a flourishing area of research. The use of sample complexity theory for mechanism design was initiated by Balcan et al. (2005, 2008). It was later studied by many others including Cole and Roughgarden (2014); Roughgarden and Schrijvers (2016) for single-item auction and Morgenstern and Roughgarden (2016); Balcan et al. (2016); Mohri and Medina (2016) for parametrized auction classes. Online learning with unknown demand distribution for posted pricing was studied in Kleinberg and Leighton (2003), see also Balcan and Beyhaghi (2024) and Balcan et al. (2025) for other pricing mechanisms. Online learning in Bayesian Persuasion, where the sender faces a receiver with unknown type, which characterizes the receiver’s utility function, was initiated in Castiglioni et al. (2020) and further developed in Babichenko et al. (2022); Zu et al. (2025); Castiglioni et al. (2021). Recent developments include Bacchiocchi et al. (2024) which further considers that the sender does not know the common prior, Zu et al. (2025) studies the sender interaction with a population of receivers who also does not know the common prior. See also Balcan et al. (2026a,b) who consider learning in the presence of additional side-information which is public to both the sender and receiver. A notable work on the learning-theoretic interface of the joint information design and pricing problem is Agrawal et al. (2023), which studies a variation of the posted pricing problem in which the seller reveals information about the uncertain quality of a good. However, the mechanism formats, the posted pricing in the former, and the menu pricing for us, are fundamentally incomparable. For instance, the ratio of optimal revenues for posted pricing for a single quality product vs. menu pricing can be vanishingly small. In addition, the former assumes that the seller knows the (exogenous) quality distribution but not the buyers’ demand distribution, whereas in our case, the seller can produce any quality and influence the demand/type of the buyer through carefully constructed signals.

2

Problem Setup and Preliminaries

We consider the setting from Bergemann et al. (2022), where a monopolist seller can manufacture goods of arbitrary (positive) quality q in the range Q = [q, q] at a cost c(q), which is assumed to be convex and non-decreasing. The buyer’s value V is distributed according to a common prior on V = [0, 1] with the CDF F (v) := P (V ≤ v). Following Mussa and Rosen (1978), a buyer with value v gains a utility of v · q − p upon purchasing a product of quality q at price p. Buyers in this setup are Bayesian utility-maximizing agents, who are ex ante unaware of their own value in contrast to Mussa and Rosen (1978). The seller commits to a public menu and a signaling scheme; the latter is sometimes termed an information structure or a Blackwell experiment (Blackwell, 1953). The public menu M = {(qi , pi ) : i ∈ I} is composed of a collection of quality-price tuples for some index set I, with qualities restricted to Q and prices at most q so that buyers still find the menu attractive. By an argument mirroring the revelation principle, sometimes termed an obedience argument, we can generically assume that the signal space S as being in a one-to-one correspondence with the menu and, therefore, just as numerous. Intuitively, each menu item can be labeled by the signal for which it is the best response – if there is no such signal, it can be removed altogether – and signals inducing the same menu item as the best response can be merged. Formally, the signaling scheme I := (S, {π(·|v)}v∈V ) encodes a signal space S ⊆ Q and a conditional distribution over signals for every possible value π(·|v) ∈ ∆(S). To fully specify the timeline, upon seeing a buyer with value v, the seller samples a signal s ∼ π(·|v), as promised upon commitment. The buyer, upon observing a signal R1 R1 s, forms a posterior mean v̄π,F (s) = [ 0 vπ(s|v)dF (v)]/[ 0 π(s|v)dF (v)], and rationally chooses a quality 3

(q(s), p(s)) ∈ arg max(q,p)∈M v̄π,F (s) · q − p, breaking ties in the favor of the seller. This gives the seller a revenue of p(s) − c(q(s)) which is the profit minus the production cost. The seller thus aims to find an incentive-compatible direct menu {(q(s), p(s)) : s ∈ S} and a signaling scheme I to maximize the expected revenue which corresponds to the following program where the first constraints enforce individual rationality (IR) and the second constraints enforce incentive compatibility (IC) which ensures that menu item (q(s), p(s)) is a best-response for the buyer upon receiving signal s. XZ 1 max (p(s) − c(q(s)))π(s|v)dF (v) (1) S⊆Q, {(q(s),p(s)):s∈S} {π(·|v)∈∆(S):v∈V} s∈S

0

subject to v̄π,F (s) · q(s) − p(s) ≥ 0 ∀s ∈ S

(IR) ′

and

v̄π,F (s) · q(s) − p(s) ≥ v̄π,F (s) · q(s ) − p(s′ ) ∀s, s′ ∈ S

(IC).

A key result from Bergemann et al. (2022) that we will use states that the resulting menu has only a finite number of items, even if the underlying value distribution is continuous. In contrast, in Mussa and Rosen (1978), where there is no information provision, this number can be unbounded. Definition 1. A signaling scheme I := (S, {π(·|v)}v∈V ) belongs to the set of monotone partitional information structures Ipart , if there exists an I ∈ Z>0 and 0 = t0 < t1 < · · · < tI = 1 such that upon receiving any signal i each buyer only knows that their value corresponds to the quantile in [ti−1 , ti ) with respect to the distribution of values. Theorem 1 (Bergemann et al. (2026b)). The optimal menu has as most K := q/q items. Furthermore, the optimal information structure is monotone partitional with at most K distinct signals.

3

Sample Complexity with Value Samples

In this section, we consider the setting in which the seller can draw i.i.d. samples from the value distribution F , and uses these in Algorithm 1 to compute a near-optimal menu and signaling scheme. We explain the Algorithm 1 with the four key ingredients that we use, the last three of which are novel in this setting. First, we solve the best monotone partitional signaling scheme and menu with empirical distribution, by solving the optimization program from Bergemann et al. (2022). In fact, in Section 4, we will give an algorithm to do this step in polynomial time. This gives the quantile partitions of values corresponding to different signals, as in Definition 1. Second, to actually implement such a signaling scheme on the true distribution, we translate this description into the value space. There is some subtlety to this and we describe this in detail in Section 3.1. Third, the buyer’s response, i.e., the item they pick from the menu, is dictated by their signal-conditioned posterior mean, which is different on the true and the empirical distributions. Posting the empirically determined menu as is can result in a constant revenue loss. To fix this, we discount the prices in a linear-additive manner in Line 5 so that a buyer does not defect to a menu item cheaper than what was intended for them in the empirical world, since a price corresponding to a higher signal also gets a larger discount. Multiplicative discounting of the form p̃k = (1 − ρ)pk is a common tool to repair incentive-compatibility constraints (e.g., see Lemma 9 in Cai and Velegkas (2021)), but this would lead to a 5 e sample complexity of O(1/ε ) in our setting. The linear-additive discount crucially relies on the menu being bounded in size (Li et al., 2025), which a multiplicative discount does not take advantage of. Finally, the signal-conditioned posterior means can be arbitrarily far off under F and Fb for signals with low marginal probability. So, in truth, we bundle all such signals, termed bad, into a null signal, and only attempt to repair incentive compatibility for good signals. The finitude of the menu once again means that the revenue loss due to this bundling of (individually) rare signals can not be too high. From now on, we will use Rev ∗ (F ) to denote the optimal revenue associated with a distribution F , and Rev(x; F ) to denote the revenue associated with a menu-signaling-scheme pair x on the same distribution. The distribution F in fact plays two roles in determining the revenue (see Equation (1)): it appears in the objective dictating the probability with which signals are generated, and it is used to update the buyer’s belief 4

Algorithm 1: Empirical Revenue Maximization (ERM) via Samples Input: value distribution F , sample budget n,P cutoff τ , discount ρ. b(v) = 1 n 1v ≤v by drawing n i.i.d. samples from F . 1 Construct the empirical distribution F i i=1 n 2 Let (tk : k ∈ [K]) be the quantile description of a near best monotone partitional signaling scheme for the distribution F̂ , with the direct menu (qk , pk : k ∈ [K]), up to εOPT error. 3 Optionally, if εOPT > 0, run the procedure in Section A.4 to obtain a direct menu with non-decreasing (pk − c(qk ) : k ∈ [K]) of equal or greater revenue. 4 Use the quantiles (tk : k ∈ [K]) to generate an explicit value-space description of the form (π(k | v) : ∀v ∈ V, k ∈ [K]) with respect to Fb, as detailed in Section 3.1. 5 Designate zτ = {k ∈ [K] : tk − tk−1 < τ } as the set of bad signals. 6 Modify the prices as p̃k = pk − kρ for all k ∈ [K]. 7 Design a modified signaling scheme that clumps all bad signals into a new null signal as ( π(s | v) π̃(s | v) = P k∈zτ π(k | v)

if s ∈ / zτ , if s = null

Output: x̃F̂ encoding ((qk , p̃k ) : k ∈ [K]) and (π̃(s | v) : v ∈ V, s ∈ [K] ∪ {null}).

to arrive at posterior means. In more elaborate tri-variate form, for the analysis, we will let Rev(x; G, F ) be the revenue when signals are generated according to F , yet buyers update their beliefs starting from the prior G. Thus, Rev(x; F ) = Rev(x; F, F ). e Theorem 2. For any ε, δ > 0, there exists a  setting of n, τ, ρ and εOP T = 0 satisfying τ = O(ε/qK) and 3 3 K q 1 e ρ = O(ε/K) such that upon observing n = Õ log i.i.d. samples from F , with probability at least 3 ε

δ

1 − δ, Algorithm 1 produces a menu-signaling-scheme pair x̃F̂ satisfying Rev(x̃F̂ ; F ) ≥ Rev ∗ (F ) − ε. Further, for optimization error εOP T > 0 in line 2, the revenue is reduced by an additive εOP T term. If we constrain our menu to a single item, we can improve the sample complexity to 1/ε2 . In fact, Bergemann et al. (2022) provide sufficient conditions under which such a menu may be optimal within the wider unrestricted class. We preview the key points in the analysis in Section 3.2, where we also highlight the difficulty of the multi-item case, while complete proofs are given in Section A.  2  Theorem 3. For any ε, δ > 0, there exists an algorithm that draws Õ qε2 log 1δ i.i.d. samples from F , and with probability at least 1 − δ, produces a signaling scheme and a menu containing a single item with revenue within ε of the optimal revenue generated by single-item menus.

3.1

Value-space Description of Quantile-based Signals

Recall that the buyer chooses a menu item using the prior F which is unknown to the seller. In this section, given a quantile description of a monotone partitional signaling scheme (tk : k ∈ [K]) associated with a distribution Fb, we give a recipe to convert this to a value-space description: given a specific v, what is the corresponding distribution over signals? This matters because we are transplanting a signaling scheme designed for Fb to F , and only a value-space description is invariant to changes in the prior distribution. For a continuous distribution Fb, this is straightforward as noted in Bergemann et al. (2022); namely, all values in the range [Fb−1 (tk−1 ), Fb−1 (tk )) are assigned the signal k deterministically, where Fb−1 (t) = inf{v : t ≤ Fb(v)} is the generalized inverse (or quantile) function. 1 1 As a convention, quantiles in (max F̂ −1 (t), 1] are assigned the signal corresponding to the previous quantile interval. t

5

The translation for discrete (or mixed) distributions is more delicate and requires randomized signaling. For all k such that Fb−1 (tk ) = Fb−1 (tk−1 ) = v0 (say), we choose the conditional law π(k|v) = (tk − tk−1 )/(Fb(v0 ) − Fb(v0− )) for v = v0 and 0 for all other v, where Fb(v0− ) is the left limit of Fb at v0 . Intuitively, only a part of the total mass Fb(v0 ) − Fb(v0− ) of v0 is assigned to the signal k. For all k such that Fb−1 (tk ) = v1 and Fb−1 (tk−1 ) = v0 with v0 ̸= v1 , the conditional probability of signal k is π(k|v) = 1{x = v0 }

Fb(v0 ) − tk−1 tk − Fb(v1− ) + 1{x ∈ (v , v )} + 1{x = v } . 0 1 1 Fb(v0 ) − Fb(v − ) Fb(v1 ) − Fb(v − ) 0

1

The key property of this translation is that the marginal probability of generating signal k under Fb R tk −1 b remains tk − tk−1 and EFb [v|k] = tk−1 F (x)dx/(tk − tk−1 ) by an immediate application of integration by parts, exactly as intended in the quantile space.

3.2

Key Ingredients in the Analysis

The main point of care is that for the same signaling scheme π, the posterior means conditioned on the same signal v π,F (k) and v π,Fb (k) can be different. This can break IC and IR constraints, resulting in a receiver of signal k buying a different item than intended or nothing at all, netting O(1) revenue loss. To fix this, we discount the prices. Naively, one might hope to discount the price by qk |v π,F (k) − v π,Fb (k)| for item k. Such conditional means can be arbitrarily far apart for rare signals; one way to see this is that the probability of signal’s occurrence appears in the denominator of these quantities. This by itself might not seem bad because the contribution to the net revenue for a signal k is also proportional to the probability of its occurrence. 2 e This reasoning indeed gets O(1/ε ) sample complexity against the benchmark of single-item menus (see Theorem 3). But for a multi-item menu, that is, the general case, this mode of analysis breaks down because discounting pk by itself can break incentive-compatibility for other types (recipients of other signals). So, any discount offered on pk must propagate through higher prices too, to ensure that other types do not defect to cheaper products (see Lemma 3). Thus, the impact of discounting the price by ∆ at some signal k is not localized, and affects the net revenue by O(K∆). This is why we designate rare signals as bad signals, and only hope to repair incentive-compatibility constraints on good signals, where the conditional means can be estimated well, and hence, where limited discounting is sufficient. 4 e The above framework gets us a sample complexity of O(1/ε ), when paired with standard uniform deviation arguments (e.g., the DKW inequality Dvoretzky et al. (1956); Massart (1990)). Such uniform arguments are needed because the boundaries of our signals are data-dependent, since we optimize over these. To improve upon this, we in fact that says the error in √ prove a variance-aware uniform deviation inequality √ conditional means scales as 1/ νn (upto lower order terms), instead of 1/ν n, where ν is the frequency of the signal’s occurrence (see Lemma 2). Our results imply a variance-aware DKW inequality whose existence has been posed as an open question in Guo et al. (2019), but in fact we show that such results can be derived with relative ease from known relative-deviation-style uniform convergence bounds for VC classes (Haussler, 1992; Li et al., 2001; Bartlett et al., 2005; Maurer and Pontil, 2009).

4

Additive FPTAS for Revenue Maximization

As usual for an FPTAS, the key is to formulate a dynamic program on suitably small state space. What makes this possible is the fact that while scanning values from left to right, or quantiles from bottom to top, with the intention of pooling these, it is enough to remember just the quality assigned to the last pool (instead of all qualities). This relies on the structure of incentive compatibility constraints in the setting of Mussa and Rosen (1978), as we detail next. The theorem as stated, and proved in Section D, only holds for discrete distributions. But the generalization to arbitrary distributions is free, given sampling access, because the empirical distribution is discrete, and we can plug this algorithm into line 2 of Algorithm 1.

6

Algorithm 2: Dynamic Programming (DP) for Optimal Menu and Signaling Scheme Input: CDF F on [0, 1]; quantile grid t = (t0 , t1 , . . . , tnt ) with t0 = 0, ti = iε; quality grid Eq = {q0 , q1 , . . . , qnq } with q0 = 0, qj = q + jε; max. menu size K and A(t) 1 Rev[0, 0, 0] := 0 and Rev[k, r, j] := −∞ for all (k, r, j) ̸= (0, 0, 0)// Initialization 2 for k = 1, . . . , K; r = 1, . . . , m; j = 1, . . . , nq do  3 Rev[k, r, j] := max0≤ℓ<r, 0≤j ′ ≤j Rev[k − 1, ℓ, j ′ ] + U [ℓ, r, j ′ , j] ;  4 ptr[k, r, j] := arg max0≤ℓ<r, 0≤j ′ ≤j Rev[k − 1, ℓ, j ′ ] + U [ℓ, r, j ′ , j] ; (k ⋆ , j ⋆ ) := arg max1≤k≤K, 1≤j≤nq Rev[k, m, j], rk⋆ := nt , jk⋆ := j ⋆ , r0 := 0; ⋆ 6 for k = k − 1 to 1 do 7 (rk , jk ) := ptr[k + 1, rk+1 , jk+1 ];

5

for k = 1 to k ⋆ do
Pk−1 9 pk := µF (rk−1 , rk ) qjk − ℓ=1 µF (rℓ , rℓ+1 ) − µF (rℓ−1 , rℓ ) qjℓ ;

8

⋆

Output: Menu {(pk , qjk )}kk=1 and signaling scheme I = (k ⋆ , (trk : k ∈ [k ⋆ ]))

Theorem 4 (Additive-FPTAS). For any εOPT > 0, given a discrete distribution with support size N , ⋆ Algorithm 2 runs in poly(K, N, q, 1/εOPT ) time and outputs a menu {(pk , qjk )}kk=1 and a monotone paritional signaling scheme I = (k ⋆ , (trk : k ∈ [k ⋆ ])) with revenue exceeding Rev ⋆ (F ) − εOPT by setting the resolution of grid as ε = (εOPT )2 /(K(6q + 1 + q))2 . We start by simplifying the optimization problem (Equation (1)). It is well known that the participation constraint for the lowest type binds and incentive compatibility constraints for all other types bind with the immediately lower type (Maskin and Riley, 1984). Moreover, the constraints imply monotonicity of the qualities with respect to the types (or values). That is v̄i · qi − pi = v̄i · qi−1 − pi−1 with q0 = p0 = 0 and Pi−1 qi ≥ qi−1 ∀i. This gives us the so called payment formula pi = v̄i qi − j=1 (v̄j+1 − v̄j )qj . Thus, we can write the optimization problem in the quantile space, which we use in the dynamic programming formulation, as LsF :

I X

max v̄i (1 − ti−1 )(qi − qi−1 ) − (ti − ti−1 )c(qi ) ((I,t),(qi )i∈[I] )) i=1 R ti

qi ≥ qi−1 ∀i ∈ {1, . . . , I} with q0 = 0,

t0 = 1 − tI = 0, and v̄i =

ti−1 F

−1

(t)dt

ti −ti−1

Let Eq = {q0 , q1 , . . . , qnq } with q0 = 0 be the quality grid, where q0 denotes the outside option and qj := q + jε q−q

for j ∈ {1, . . . , nq }, with nq = ⌈ ε ⌉, and Et = {t0 , . . . , tnt } with t0 = 1 − tnt = 0 be the quantile grid Rt with ti = iε and nt = 1/ε ∈ Z>0 . Define A(t) = 0 F −1 (s) ds ∀t ∈ [0, 1]. For indices 0 ≤ ℓ < r ≤ m, ℓ) define µF (ℓ, r) := A(trtr)−A(t the posterior mean of the quantile interval (tℓ , tr ] under F . For the dynamic −tℓ programming we store Rev[k, r, j] which denotes the maximum revenue from partitioning (0, tr ] into k nonempty quantile grid intervals with the last interval assigned quality qj ∈ Eq . Moreover, we store U[ℓ, r, j ′ , j] for quality indices 0 ≤ j ′ ≤ j ≤ nq which we define as the transition utility U[ℓ, r, j ′ , j] := µF (ℓ, r) (1 − tℓ ) (qj − qj ′ ) − c(qj )(tr − tℓ ), i.e. the revenue contribution from assigning quality qj to the interval (tℓ , tr ], given that the preceding interval was assigned quality qj ′ . The dynamic programming recursion immediately follows where one needs to maintain the monotonicity of quality being assigned.

5

Sample Complexity with Demand Queries

We consider a setting where the seller deploys signaling schemes and menus of their choice, and observes how a buyer with a randomly drawn value responds to it. Despite the stochasticity in values, we will see 7

Algorithm 3: Empirical Revenue Maximization via Demand Queries Input: query budget n, cutoff τ , discount ρ. 2 1 Fix a menu M = {(q, p(q) := (q − q) /2(q − q)) : q ∈ [q, q]}. 2 for j = 1, . . . n do 3 Choose a signaling scheme with two signals πj (0|v) = 1 − πj (1|v) = v j−1 . Observe the generated signal sj and the purchased quality qj when the menu M was coupled with 4 a signaling scheme πj . 5 Let qj′ = (qj − q)/(q − q) be the normalized quality. ( qj′ mj−1 if sj = 0, 6 With the convention that m0 = 1, set mj = ′ m1 − qj (1 − mj−1 ) if sj = 1. if the value distribution is discrete then For a discrete value distribution with support {x1 , . . . xn+1 } of size n + 1, calculate the pmf p ∈ ∆([n]) by solving the linear system V p = m, where m = [m0 , m1 , . . . mn ]⊤ and V ∈ R(n+1)×(n+1) is a Vandermonde matrix with Vi,j = xij . 9 Let Fb be the corresponding CDF.

7

8

else Pj Let Lj (x) = i=0 aji xi be the expansion of the j th Legendre polynomial shifted to [0, 1]. Pj Pj 12 Calculate αj = i=0 aji (1 − mi+1 /(i + 1)) and F̃j (x) = i=0 αi Li (x), which is the degree-j Legendre projection of the CDF. P2⌈n/2⌉−1 1 13 Compute the de la Vallee Poussin mean F̂⌈n/2⌉ (x) = ⌈n/2⌉ i=⌈n/2⌉ F̃i (x).

10

11

Let F̂ be the smallest non-negative non-decreasing upper envelope of F̂⌈n/2⌉ .

14

Let (tk : k ∈ [K]) be the quantile description of the best monotone partitional signaling scheme for the distribution F̂ , with the direct menu (qk , pk : k ∈ [K]). 16 Use the quantiles (tk : k ∈ [K]) to generate an explicit value-space description of the form (π(k | v) : ∀v ∈ V, k ∈ [K]) with respect to Fb, as detailed in Section 3.1. 17 Designate zτ = {i ∈ [I] : ti − ti−1 < τ } as the set of bad signals. 18 Modify the prices as p̃k = pk − kρ for all k ∈ [K]. 19 Design a modified signaling scheme that clumps all bad signals into a new null signal as 15

( πk (s | v) π̃(s | v) = P k∈zτ πk (k | v)

if s ∈ / zτ , if s = null

Output: x̃F̂ encoding ((qk , p̃k ) : k ∈ [K]) and (π̃(s | v) : v ∈ V, s ∈ [K] ∪ {null}).

that it is possible to extract the moments of the value distribution exactly in this setting, without any error. We couple this with results from approximation theory (Trefethen, 2019) to estimate the underlying value distribution. We define the setting first and then give the algorithm. Definition 2. A demand query accepts as input a signaling scheme (S, {π(·|v)}v∈V ) and a menu ((p(z), q(z))z∈Z ) for some index set Z and outputs the signal s ∼ π(·|v) made available to the buyer along with the item (q, p) selected by the buyer, where the value of the buyer v is drawn randomly from F .

5.1

Approximating Discrete Distributions

The main observation is that in this model we can exactly simulate bounded linear functionals of the pmf (or the pdf) corresponding to the common prior F . We specifically chose moments. Interestingly, this makes our queries non-adaptive.

8

Theorem 5. For any discrete distribution F with support size n + 1, when Algorithm 3 is run for n queries, with τ = ρ = 0, it returns a revenue-maximizing menu and signaling scheme pair x̃Fb that attains the optimal revenue, that is, Rev(x̃Fb ) = Rev ∗ (F ). We first begin with the following moment recovery lemma. Lemma 1. For any j ≤ n, mj = EF [v j ] as recovered on line 6 of Algorithm 3. Proof. Upon observing any signal s, the quality of the item chosen by the buyer is arg maxq∈[q,q] qv π,F (s)−p(q). First-order conditions dictate that qj′ = v π,F (s), thus we recover the posterior mean exactly. Now, in any round k

k

F [v]−EF [v ] j n, we have v π,F (0) = EEFF[v[vk−1] ] and v π,F (1) = E1−E k−1 ] . Thus, inductively, we have that mj = EF [v ]. F [v

Given a sufficient number of moments, Vandermonde inversion guarantees exact pmf recovery. Pn+1 Proof of Theorem 5. Using Lemma 1 we can see that EF [v j ] = i=1 pi xji = Vj⊤ p, where Vj is the j th row of the Vandermonde matrix defined on line 8 of Algorithm 3. Hence, the true pmf satisfies V p = m. Because the Vandermonde matrix is invertible as long as xi = ̸ xj for all i < j, the pmf reconstructed by the algorithm is exact, and no revenue is lost.

5.2

Approximating the CDF for Continuous Distributions

The continuous case is trickier. We would like to approximate the CDF F via orthogonal polynomial families in the L∞ sense, that is, in the Kolmogorov metric. We instead settle on the best L2 approximation, since those can be computed via inner products on the Lebesgue measure; the latter restriction rules out well-loved classes like the Chebyshev family (Cheney and Light, 2009). However, Legendre projections are known to have suboptimal L∞ approximation guarantees, so we use de la Vallee Poussin mean of Legendre projections which in effect stabilizes the latter, and uses twice the number of moments to give near-optimal guarantees matching the best L∞ approximation à la Jackon’s theorem (Mastroianni et al., 2008). A final hurdle is that moments of a distribution naturally correspond to inner products of the moment curve with the pdf, and we would like to compute inner products with the CDF. This gap can be bridged by an application of integration by parts. We supply the details in the Appendix B. R1 j R 1 j+1 1 x F (x)dx = 1 − j+1 x f (x)dx. 0 0 Theorem 6. For any r ∈ Z>0 and any continuous distribution F where the rth derivative of the CDF is 2/r 2/r B bounded as B r , for some constant B > 0, when Algorithm 3 is run for n = O( q εK ) queries and suitable 2/r τ, ρ, it produces a menu-signaling-scheme pair x̃F̂ satisfying Rev(x̃F̂ ; F ) ≥ Rev ∗ (F ) − ε. As an immediate corollary, for bounded and Lipschitz pdfs we need 1/ε2 and 1/ε queries, respectively. For analytic functions, we choose r = log(1/ε) to get polylogarithmic in 1/ε queries.

6

Regret under Joint Learning

Followed by Zu et al. (2025), we consider a more general setting where the seller interacts with a buyer on each day, commits to a menu and signaling scheme, and observes the purchase decision and the value of the buyer at the end of the day. More importantly, we allow the case when the population of buyers are learning, perhaps exogenously through reviews of the item on the platform. This setting thus subsumes the previous settings, however, the analysis closely mirrors the earlier one once we introduce the following relaxed behavioral assumption. Since the buyers are learning, the seller asks, what does the belief the buyer who arrives on that day hold? If the seller knew the belief of the buyer, he could solve the offline problem. Since he does not know the buyer’s belief precisely, he robustifies the menu and signaling scheme which performs 9

Algorithm 4: Online Empirical Menu & Information Design Input: τt , εt , h(τt , εt ) for t = 1, . . . , T 1 Initialize F̂1 ∈ B0 ; 2 for t = 1, . . . , T do 3 Call Algorithm 1 with the distribution F̂t , cutoff τt and discount ρt to obtain x̃F̂t ; Pt 4 Execute x̃F̂t and observe vt and update F̂t+1 (v) = 1t s=1 1{vs ≤v} ;

well for a set of beliefs, which the seller iteratively updates knowing that buyers are learning. This idea is captured in the following definition, where the seller confidently assumes that the arriving buyer’s belief on day t lies in the set C(F̂t ) which can simply be {F ⋆ }, the unknown common belief, B0 the sellers prior belief about buyers’ belief or simply F̂t , the empirical distribution on day t. Definition 3. We say that an algorithm which executes x̃t in each round is (β, κ)-robustly
revenue efficient, if there exists data-dependent sets Ct such that we have (i) coverage i.e. Pr ∩Tt=1 Ct ∋ F ⋆ ≥ 1 − β and (ii) robustness, i.e. for Ht the set of all possible histories up to time t, we need for all t ∈ [T ] and for all ht ∈ Ht , conditioned on the history ht that supG∈C(F̂t ) maxx Rev(x; F̂t , F̂t ) − Rev(x̃t ; G, F̂t ) ≤ κt . Assumption 1. For a (β, κ)-robustly revenue efficient algorithm w.r.t. sets Ct , the buyers’ prior Ftb at round t is such that Pr(Ct ∋ Ftb ) = 1 ∀ t ∈ [T ]. The seller knows the set B0 s.t. Pr(B0 ∋ F ⋆ ) = 1. Although the Definition 3 allows for arbitrary sets C, one is interested in sets which are statistically achievable by the buyer. We propose Algorithm 4, where the seller chooses parameter sequence based on the assumed sets C. Throughout the following results we take the sets Ct (εt ) := {G ∈ ∆(V) : supv |G(v) − F̂t (v)| ≤ εt } for all t ∈ [T ], which are εt > 0 sized balls centered at F̂t in the Kolmogorov metric. First, we show the space parameters β, κ for which the algorithm is robustly revenue efficient. Theorem 7. The Algorithm 4 with any cutoff sequence {τt }Tt=1 and for any sequence {εt }Tt=1 with εt ∈ (0, 1] and P discount sequence given by ρt = 4q̄εt /τt is (β, κ)-robustly revenue efficient for sets Ct (εt ) for all
β ≥ t∈[T ] 2 exp −tε2t /2 and κt = K q̄(4εt /τt + τt ). PT We measure the performance of the algorithm through cumulative regret defined as Reg := t=1 Rev⋆ (F ⋆ )− revt (xt ; Ftb ) where revt (xt ; Ftb ) denotes the revenue generated by seller on day t upon committing to xt when the arriving buyer hold belief Ftb . √ √ Theorem 8. Algorithm 4 with cutoff τt = εt and discount ρt = 4q̄ εt , for the sets Ct (εt ) with εt = p
3 log T /t gives the cumulative regret Reg ≤ O K q̄(log T )1/4 T 3/4 with probability at least 1 − 3T −1/2 . In Section C, we prove the above results and also show that there are (more intricate) statistically plausible sets Ct for which we obtain a Õ(T 2/3 ) regret upper bound.

7

Conclusion

We study a novel learning problem motivated by the fact that sellers and algorithmic platforms today have access to vast user trails that they can use to forecast the personalized value of niche products for a specific user. We give learning algorithms that reflect how a seller might use past experience to craft the best menu of products and prices, along with a recommendation for individual customers on what products to buy. With access to samples of values, we achieved a sample complexity of ordert 1/ε3 . We then showed that this can be improved significantly in a model where the seller can observe the buyers’ behaviors to carefully chosen menu and recommendations, under some circumstances making the sample complexity near-constant. Finally, we give an efficient algorithm to compute a near-optimal menu and signaling scheme, despite the underlying problem being non-convex. Our work brings a learning-theoretic perspective to the interface between information and (traditional) mechanism design. 10

Acknowledgements TP is supported by the Balas Fellowship Award and Ph.D. funding from the Tepper School of Business. We thank Rattana Pukdee, Kiriaki Fragkia and Andreas Kalavas for helpful comments.

References Agrawal, S., Feng, Y., and Tang, W. (2023). Dynamic pricing and learning with bayesian persuasion. In Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS ’23, Red Hook, NY, USA. Curran Associates Inc. Akerlof, G. A. (1970). The market for “lemons”: Quality uncertainty and the market mechanism. The Quarterly Journal of Economics, 84(3):488–500. Anthony, M. and Bartlett, P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge University Press. Babichenko, Y., Talgam-Cohen, I., Xu, H., and Zabarnyi, K. (2022). Regret-minimizing bayesian persuasion. Games and Economic Behavior, 136:226–248. Bacchiocchi, F., Bollini, M., Castiglioni, M., Marchesi, A., and Gatti, N. (2024). Online bayesian persuasion without a clue. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS ’24, Red Hook, NY, USA. Curran Associates Inc. Balcan, M. F., Bernasconi, M., Castiglioni, M., Celli, A., Harris, K., and Wu, S. (2026a). Nearly-optimal bandit learning in stackelberg games with side information. In The Fourteenth International Conference on Learning Representations. Balcan, M. F. and Beyhaghi, H. (2024). New guarantees for learning revenue maximizing menus of lotteries and two-part tariffs. Transactions on Machine Learning Research. Balcan, M.-F., Blum, A., Hartline, J., and Mansour, Y. (2005). Mechanism design via machine learning. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 605–614. Balcan, M.-F., Blum, A., Hartline, J. D., and Mansour, Y. (2008). Reducing mechanism design to algorithm design via machine learning. Journal of Computer and System Sciences, 74(8):1245–1270. Balcan, M. F., Fragkia, K., and Harris, K. (2026b). Learning in structured stackelberg games. In Forty-third International Conference on Machine Learning. Balcan, M.-F., Sandholm, T., and Vitercik, E. (2016). Sample complexity of automated mechanism design. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 2091–2099, Red Hook, NY, USA. Curran Associates Inc. Balcan, M.-F., Sandholm, T., and Vitercik, E. (2025). Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms. Operations Research, 73(2):648–663. Bartlett, P. L., Bousquet, O., and Mendelson, S. (2005). Local rademacher complexities. The Annals of Statistics, 33(4):1497–1537. Bergemann, D., Heumann, T., and Morris, S. (2022). arXiv:2212.03360v1.

Screening with persuasion.

arXiv preprint

Bergemann, D., Heumann, T., and Morris, S. (2026a). Information design and mechanism design: An integrated framework. arXiv preprint arXiv:2601.17267. Bergemann, D., Heumann, T., and Morris, S. (2026b). Screening with persuasion. Journal of Political Economy, 134(2):570–625. 11

Bergemann, D. and Morris, S. (2019). Information design: A unified perspective. Journal of Economic Literature, 57(1):44–95. Blackwell, D. (1953). Equivalent comparisons of experiments. The Annals of Mathematical Statistics, 24(2):265–272. Bolton, P. and Dewatripont, M. (2004). Contract Theory. Contract Theory. MIT Press. Cai, Y. and Velegkas, G. (2021). How to Sell Information Optimally: An Algorithmic Study. In Lee, J. R., editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 81:1–81:20, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. Castiglioni, M., Celli, A., Marchesi, A., and Gatti, N. (2020). Online bayesian persuasion. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS ’20, Red Hook, NY, USA. Curran Associates Inc. Castiglioni, M., Marchesi, A., Celli, A., and Gatti, N. (2021). Multi-receiver online bayesian persuasion. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1314–1323. PMLR. Cheney, E. and Light, W. (2009). A Course in Approximation Theory. Graduate studies in mathematics. American Mathematical Society. Cole, R. and Roughgarden, T. (2014). The sample complexity of revenue maximization. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 243–252, New York, NY, USA. Association for Computing Machinery. Crawford, V. P. and Sobel, J. (1982). Strategic information transmission. Econometrica, 50(6):1431–1451. Dvoretzky, A., Kiefer, J., and Wolfowitz, J. (1956). Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator. The Annals of Mathematical Statistics, 27(3):642–669. Dworczak, P. and Martini, G. (2019). The simple economics of optimal persuasion. Journal of Political Economy, 127(5):1993–2048. Gentzkow, M. and Kamenica, E. (2016). A rothschild-stiglitz approach to bayesian persuasion. American Economic Review, 106(5):597–601. Goldberg, P. and Jerrum, M. (1993). Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. In Proceedings of the Sixth Annual Conference on Computational Learning Theory, COLT ’93, page 361–369, New York, NY, USA. Association for Computing Machinery. Guo, C., Huang, Z., and Zhang, X. (2019). Settling the sample complexity of single-parameter revenue maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 662–673, New York, NY, USA. Association for Computing Machinery. Haussler, D. (1992). Decision theoretic generalizations of the pac model for neural net and other learning applications. Information and Computation, 100(1):78–150. Kamenica, E. (2019). Bayesian persuasion and information design. Annual Review of Economics, 11:pp. 249–272. 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 online posted-price auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pages 594–605. 12

Kravitz, D. (2025). Inside kroger’s secret shopper profiles: Why you may be paying more than your neighbors. Consumer Reports. Li, A., Ravi, R., Singh, K., Yi, Z., and Zhang, W. (2025). How to sell high-dimensional data optimally. arXiv preprint arXiv:2510.15214. Li, Y., Long, P. M., and Srinivasan, A. (2001). Improved bounds on the sample complexity of learning. Journal of Computer and System Sciences, 62(3):516–527. Mansoor, S. (2026). Maryland becomes first state to ban surveillance pricing in grocery stores. The Guardian. Maskin, E. and Riley, J. (1984). Monopoly with incomplete information. The RAND Journal of Economics, 15(2):171–196. Massart, P. (1990). The tight constant in the dvoretzky-kiefer-wolfowitz inequality. The Annals of Probability, 18(3):1269–1283. Mastroianni, G., Themistoclakis, W., et al. (2008). De la vallée poussin means and jackson’s theorem. Acta Scientiarum Mathematicarum, 74(1-2):147–170. Maurer, A. and Pontil, M. (2009). Empirical bernstein bounds and sample-variance penalization. In COLT 2009 - The 22nd Conference on Learning Theory, Montreal, Quebec, Canada, June 18-21, 2009. Mohri, M. and Medina, A. M. (2016). Learning algorithms for second-price auctions with reserve. Journal of Machine Learning Research, 17(74):1–25. Morgenstern, J. and Roughgarden, T. (2016). Learning simple auctions. In Feldman, V., Rakhlin, A., and Shamir, O., editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 1298–1318, Columbia University, New York, New York, USA. PMLR. Mussa, M. and Rosen, S. (1978). Monopoly and product quality. Journal of Economic Theory, 18(2):301–317. Roughgarden, T. and Schrijvers, O. (2016). Ironing in the dark. In Proceedings of the 2016 ACM Conference on Economics and Computation, EC ’16, page 1–18, New York, NY, USA. Association for Computing Machinery. Spence, M. (1973). Job market signaling. The Quarterly Journal of Economics, 87(3):355–374. Trefethen, L. N. (2019). Approximation Theory and Approximation Practice, Extended Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA. van der Vaart, A. and Wellner, J. (2023). Weak Convergence and Empirical Processes: With Applications to Statistics. Springer Series in Statistics. Springer. Wilson, R. (1993). Nonlinear Pricing. Oxford University Press. Zu, Y., Iyer, K., and Xu, H. (2025). Learning to persuade on the fly: Robustness against ignorance. Operations Research, 73(1):194–208.

13

Appendix In Section A, we complete the proof for sample complexity with value samples. Section B supplies the proofs for sample complexity of demand queries. In Section C and Section D, we complete the proofs for the joint-learning-based regret setting and prove the correctness of the FPTAS, respectively. Section E provides formal proofs for the signaling transformation discussed in Section 3.1.

A

Sample Complexity with Value Samples

A.1

Proof of Theorem 2

We decompose the error as Rev ∗ (F ) − Rev(x̃F̂ ; F ) = Rev ∗ (F ) − Rev ∗ (F̂ ) + Rev ∗ (F̂ ) − Rev(x̃F̂ ; F, F ) . {z } | | {z } Term1

Term2

Throughout the analysis, we condition on the event in Lemma 2, which holds with high probability. Lemma 2. There exists a universal constant C such that for any δ > 0, n > 1 and distribution F , with probability 1 − δ, for all monotone paritional signaling scheme π with K signals, we have that s ! log(n/δ) (log n/δ) min{ Pr (k), Pr (k)} + , (2) Pr (k) − Pr (k) ≤ C π◦F π◦F b b n n π◦F π◦F s ! log(n/δ) log(n/δ) EF [v|k] − EFb [v|k] ≤ C + , n max{Prπ◦F (k), Prπ◦Fb (k)} n max{Prπ◦F (k), Prπ◦Fb (k)} for all k ∈ [K], where Fb is a n-point empirical distribution sampled from F . First, we upper bound Term 1. Let xF be the optimal pair of menu ((qk , pk ) : k ∈ [K]) and monotone partitional signaling scheme (tk : k ∈ [K]) under F . Let zτ = {k ∈ [K] : tk − tk−1 < τ }. Define x̃F with signaling scheme π̃ modified so that all signals in zτ are mapped to a null signal: ( π(s | v) if s ∈ / zτ , π̃(s | v) = P π(k | v) if s = null, k∈zτ and the prices discounted as p̃k = pk − kρ. Then we have Term1 := Rev ∗ (F ) − Rev(x̃F ; F̂ , F̂ ) + Rev(x̃F ; F̂ , F̂ ) − Rev ∗ (F̂ ) ≤ Rev ∗ (F ) − Rev(x̃F ; F̂ , F̂ ) where we appeal to the fact that Rev ∗ (F̂ ) is the optimal revenue for the empirical distribution Fb. Now, 1/3 e we use Lemma 3, which places an upper bound of Õ(qK/n1/3 ) on Term 1, by choosing ρ = Θ(q/n ) and 1/3 e τ = Θ(1/n ). Lemma 3. Consider any two value distributions F, Fb such that for all monotone partitional signaling schemes π with K signals, we have for all k ∈ [K] that Pr (k) − Pr (k) ≤ ε0 , and EF [v|k] − EFb [v|k] ≤

π◦F

b π◦F

ε1 Prπ◦F (k)

+p

ε2 Prπ◦F (k)

.

Let xF be εOPT -suboptimal solution for distribution F comprising of an incentive-compatible menu and monotone partitional signaling scheme, for which pk − c(qk ) is in non-decreasing in k. Further, let x̃F be a 14

modification of xF with all signals with marginal probability smaller than √ τ (with respect to F ) mapped to a null signal and price modifications p̃k = pk − kρ, where ρ = 2q(ε1 /τ + ε2 / τ ), pk is the corresponding price for signal k in xF . Then, we have √ Rev(xF ; F, F ) − Rev(x̃F , Fb, Fb) ≤ qK(τ + 2(ε1 /τ + ε2 / τ ) + ε0 ). Similarly, for Term2, let xFb be an εOP T -suboptimal pair of menu ((qk , pk ) : k ∈ [K]) and monotone partitional signaling scheme (tk : k ∈ [K]) this time under Fb. Let z̃τ = {k ∈ [K] : tk − tk−1 < τ }. Let x̃Fb be the analogous modification where all signals in z̃τ are mapped to a null signal, and prices are linear-additively discounted by ρ at all indices. Now, applying Lemma 3, with the roles of F and Fb reversed, we get Term2 := Rev ∗ (Fb) − Rev ∗ (xFb ; Fb, Fb) + Rev(xFb ; Fb, Fb) − Rev ∗ (x̃Fb ; F, F ) ≤ εOPT + Rev(x b ; Fb, Fb) − Rev(x̃F ; F̂ , F̂ ) F

≤ εOPT + Õ(qK/n1/3 ).

A.2

Proof of Lemma 3

Since xF encodes an incentive-compatible menu ((qk , pk ) : k ∈ [K]) under the distribution F , we know that for all k ∈ [K] that ! ε2 ε1 qk · EF̂ [v|k] − pk ≥ qk · EF [v|k] − pk − q +p Prπ◦F (k) Prπ◦F (k) ! ε1 ε2 ≥ max{0, max{qj · EF [v|k] − pj }} − q +p j Prπ◦F (k) Prπ◦F (k) ! ε1 ε2 ≥ max{0, max{qj · EFb [v|k] − pj }} − 2q +p j Prπ◦F (k) Prπ◦F (k) Now by implementing the modified prices p̃k = pk − kρ, it is clear that participation constraints are upheld for Fb for all (good) signals in not zτ . We do not claim to uphold incentive compatibility under Fb, only that any buyer receiving signal k does not purchase an item indexed by a lower signal, as long as k ̸∈ zτ . To observe this, note for all j < k that qk · EF̂ [v|k] − pek = qk · EF̂ [v|k] − pk + kρ ≥ qj · EF̂ [v|k] − pj + kρ − ρ = qj · EF̂ [v|k] − p̃j + (k − j)ρ − ρ ≥ qj · EF̂ [v|k] − p̃j . Thus, each receipt of a good signal k ̸∈ zτ agrees to pay at least pk − Kρ and generates a margin at least pk − c(qk ) − Kρ for the buyer under the distribution Fb. Thus, we have Rev(xF ; F, F ) − Rev(x̃F , Fb, F ) ≤ K(ρ + qτ ), even assuming that in the worst case those assigned the null signal refuse to purchase anything. Finally, using the observations that the marginal probability of signals is similar under F and Fb: Rev(x̃F ; Fb, F ) − Rev(x̃F , Fb, Fb) ≤ qKε0 . Combining the last two inequalities concludes the proof.

15

A.3

Proof of Lemma 2

Our plan is to appeal to variance-sensitive versions of uniform convergence bounds for function classes with bounded pseudo-dimension. We start with a result of Maurer and Pontil (2009), which is stated in terms of L∞ covering number on n-sample distributions, a term we will quickly rid ourselves of. (See van der Vaart and Wellner (2023) for the definition.) Theorem 9 (Maurer and Pontil (2009)). Let X be a random variable with values in a set X with distribution F and let F be a class of hypotheses f : X → [0, 1]. Fix δ ∈ (0, 1), n ≥ 16 and set M(n) = 10N∞ (1/n, F, 2n). Then with probability at least 1 − δ in the random vector X = (X1 , . . . , Xn ) ∼ µn we have r 18Vn (f, X) ln(M(n)/δ) 15 ln(M(n)/δ) Ex∼F [f (x)] − Ex∼Fb [f (x)] ≤ + , ∀f ∈ F, n n−1 P where Vn (f, X) = i<j (f (xi ) − f (xj ))2 /n(n − 1) is the sample variance, and Fb is the empirical distribution on the dataset X. For real-valued function classes with bounded pseudo-dimension, the above statement can be stated in terms of pseudo-dimension. Definition 4. A function class F : X → R has pseudo-dimension d if d is the maximum number for which there is d-sized set S = {x1 , . . . , xd } ⊆ X and real numbers r1 , . . . , rd such that for each b ∈ {0, 1}d there is a function fb ∈ F with sign(fb (xi ) − ri ) = bi ∀i ∈ [d]. Theorem 10 (Anthony and Bartlett (1999)). Let F be a set of real functions from a domain X to the bounded interval [0, B]. Let ϵ > 0 and suppose that the pseudo-dimension of F is d. Then N∞ (ϵ, F, m) ≤

d    i X m B i=1

i

ϵ

,

which is less than (emB/(ϵd))d for m ≥ d. Now, we perform three steps at once: one, we compose the last two results; two, we apply the results to the class F ′ = {1 − f : f ∈ F } in addition to the original class; three, we note for any f : X → [0, 1] that n Vn (f, X) = n−1 (Ex∼Fb [f (x)2 ] − Ex∼Fb [f (x)]2 ) ≤ 2Ex∼Fb [f (x)]. As a result, we get that there is a universal constant C such that for any function class F : X → [0, 1] with pseudo-dimension d, with probability 1 − δ, we have for all f ∈ F that ! r EFb [f (x)]d log(n/δ) d log(n/δ) + . EF [f (x)] − EFb [f (x)] ≤ C n n claim can be restated as ∆ ≤ pLet ∆ := |EF̂ [f (x) − EF [f (x)]| and b := d log(n/δ)/n.√ The above √ √ C (EF [f (x)] + ∆) b + C ′ b for some constants C, C ′ . Using a + b ≤ a + b and then applying AM-GM p √ 2 as C ∆b ≤ 12 ∆ + C2 b gives us ∆ ≤ 2C EF [f (x)] · b + (C 2 + 2C ′ )b. Thus, whenever the above inequality holds, we also have for a different universal constant C ′ that ! r EF [f (x)]d log(n/δ) d log(n/δ) ′ + . EF [f (x)] − EFb [f (x)] ≤ C n n Let G be the class of function on [0, 1] of the form gu,v,ξu ,ξv (x) := ξu 1{x = u}+1{u < x < v}+ξv 1{x = v}, where 0 ≤ ξu , ξv ≤ 1, u ≤ v ∈ [0, 1]. Let F = {xg(x) : g ∈ G}. We wish to bound the pseudo-dimension 16

of these classes. Recall that for any class F, the pseudo-dimension is precisely the VC dimension of {(x, t) 7→ 1{f (x) ≥ t} : f ∈ F}. We use the following result from Goldberg and Jerrum (1993) on VC dimension of classes involving real numbers to conclude that the pseudo-dimension of both classes is at most a constant, by observing that membership for the subgraph sets of such function classes can be computed by a constant sized algebraic circuit that permits usual arithmetric operations and (in)equalities. Theorem 11 (Goldberg and Jerrum (1993)). Let {Ck,n : k, n ∈ Z>0 } be a family of concept classes where concepts in Ck,n and inputs are represented by k and n real values, respectively. Further, let the test for membership of an instance x in a concept C in Ck,n consist of an algorithm Ak,n taking k + n real inputs representing C and x, whose runtime is t = t(k, n), and which returns the truth value a ∈ C. The algorithm Ak,n is allowed to perform conditional jumps (conditioned on equality and inequality of real values) and execute the standard arithmetic operations on real numbers (+, −, ×, /) in constant time. Then the VC dimension of Ck,n is at most O(kt). Note that for any monotone partitional signaling scheme π, as detailed in Section 3.1, Prπ◦F [k] and Eπ◦F [v1{signal k is observed}] can be realized as expectations of specific members in G and F, respectively. Thus, we already have with high probability for a suitable universal constant C ′′ that   max Pr (k) − Pr (k) , Eπ◦F [v1{k is observed}] − Pr [v1{k is observed}] π◦F b b π◦F π◦F s ! log(n/δ) log(n/δ) ≤ C ′′ + . min{ Pr (k), Pr (k)} π◦F b n n π◦F To conclude the statement concerning the conditional means, we observe the following elementary inequality ′ ′ A A′ A′ |B −B| for positive reals: B ≤ |A B−A| + B and substitute the appropriate quantities from the last ′ − B ′ B inequality, while noting that the condition mean, i.e., A′ /B ′ , can at most be one.

A.4

Ensuring Monotonic Margins

Let us consider that we are given a monotone partitional scheme (tk : k ∈ [K]) and an associated incentive compatible direct menu ((qk , pk ) : k ∈ [K]) for a value distribution Fb, which might not be revenue maximizing pair. A key condition used in previous proofs are that the seller’s margins pk − c(qk ) are non-decreasing in k. This is true by default for optimal incentive-compatible direct menus with respect to Fb; our approach here will give an alternative proof of this. However, if we use the approximately optimal menu from Section 4, this may not be true. To placate this worry, we now provide an algorithm that given an incentive-compatible menu converts it into another incentive compatible menu where margins are non-decreasing in the index, while weakly increasing the revenue. Thus, this condition can always be ensured algorithmically. The modification works as follows: first, we calculate the margins πk = pk − c(qk ) for all signals. Next, we only retain menu items in the set S = {k : πk ≥ maxj<k πj } and delete the rest. This results in an indirect menu. So, we calculate what a buyer observing signal k purchases in this smaller menu (with respect to the prior Fb) and designate that as their quality-item pair in a new direct menu. Proposition 1. Given any incentive-compatible direct menu, the above procedure produces another incentive-compatible direct menu with non-decreasing margins. In addition, during this transformation, the revenue weakly increases. Proof. The incentive compatibility holds because of the relabeling in the last step. Notice that the item corresponding to smallest k is retained by definition, and hence participation for all (signal) types is upheld. Let σ(k) be the item a buyer observing signal k picks in this smaller menu S. It is well known incentive-compatibility for one-dimensional (signal) types ensures that qσ(k) is non-decreasing (Maskin and Riley, 1984), and hence, by construction, πσ(k) follows the same pattern. As for preserving the revenue, this is immediate for any signal k for which k belongs to S, because a buyer receiving this signal will still pick the same item, which in turn has not been deleted. If k is not in S, let k − be the largest index picked in S that is 17

smaller than k, and k + be the smallest index picked in S that is larger than k. Since incentive-compatibility constraints only enforce on neighboring types even for suboptimal menus (Maskin and Riley, 1984), σ(k) is either k − or k + . Because k is not S, we know πk− ≥ πk , and similarly, πk+ ≥ πk . So, without knowing the precise details of what signal k picks, we know that the margin (and hence the net revenue) is weakly greater.

A.5

Proof of Theorem 3

We consider Xs = {((I, w, ξ), (p, q)) with I = 2 and thus w = {0 = w0 ≤ w1 ≤ w2 = 1}}, ξ = {0 = ξ0 ≤ ξ1 ≤ ξ2 = 1}}. Thus we can equivalently write Xs = {(w1 , ξ1 , (p, q))}. Here the information structure simply consists of two signals sH and sL where ( ( 1 if v < w1 1 if v > w1 π(sL |v) = , π(sH |v) = ξ1 if v = w1 1 − ξ1 if v = w1 Let µF (w1 , ξ1 ) be the posterior mean under signal sH , which is explicitly given as µF (w1 , ξ1 ) =

EF [(1 − ξ1 )v1{v = w1 } + v1{v > w1 }] . EF [(1 − ξ1 )1{v = w1 } + 1{v > w1 }]

The optimization problem can be written as (1)

LF :

max EF [(1 − ξ1 )1{v = w1 } + 1{v > w1 }] · (p − c(q)) · I {µF (w1 , ξ1 ) · q − p ≥ 0} . {z } | {z } | {z } p∈R,q∈[q,q] | revenue participation of the buyer w1 ,ξ1 ∈[0,1] probability of realizing signal sH : PrF (sH |w1 ,ξ1 ) iid

Given N samples v1 , . . . , vN ∼ F , let F̂ (v) = |{vi : vi ≤ v}|/n = ˆ (p̂, q̂)) be the solution of L(1) and L(1) respectively. (ŵ, ξ, F F̂ Define

Pn

i=1 I{vi ≤ v}/n and let (w, ξ, (p, q)) and

G = {gw,ξ (v) = (1 − ξ)1{v = w} + 1{v > w} ∀ξ ∈ [0, 1], w, v ∈ [0, 1]} We have with probability at least 1 − δ, the following from the analysis of section A.3 sup ξ∈[0,1],w∈[0,1]

|Ev∼F [gw,ξ (v)] − Ev∼F̂ [gw,ξ (v)] ≤ ε

q
1 for ε = C 2n ln 1δ for some constant C > 0. Using this, a simple application of triangle inequality gives for all ξ ∈ [0, 1] and w ∈ [0, 1] with probability at least 1 − δ, the following |µF (w, ξ) − µF̂ (w, ξ)| ≤ min{ρw,ξ , ρ̂w,ξ }, where ρ̂w,ξ = ε/Ev∼F̂ [gw,ξ (v)] and ρw,ξ = ε/Ev∼F [gw,ξ (v)]. ˆ · q̂ − p̂ ≥ 0 implies µF (ŵ, ξ) ˆ · q̂ − p̂′ ≥ 0 where p̂′ = p̂ − ρ̂ q. Thus, µF̂ (ŵ, ξ) ŵ,ξ̂ Similarly, µF (w, ξ) · q − p ≥ 0 implies µF̂ (w, ξ) · q − p′ ≥ 0 for p′ = p − ρw,ξ q. ˆ (p̂′ , q̂)) satisfies This simply means that (w, ξ, (p′ , q)) satisfies the IR conditions under F̂ and similarly (ŵ, ξ, the IR conditions under F . Now, observe that ˆ (p̂′ , q̂); F ) = Ev∼F [g (v)] · (p̂′ − c(q̂)) Rev(ŵ, ξ, ŵ,ξ̂     ≥ Ev∼F̂ [gŵ,ξ̂ (v)] − ε · p̂ − ρŵ,ξ̂ q − c(q̂)   ≥ Ev∼F̂ [gŵ,ξ̂ (v)] · (p̂ − c(q̂)) − Ev∼F̂ [gŵ,ξ̂ (v)] · ρŵ,ξ̂ q − εq

18

ˆ (p̂, q̂); F̂ ) − 2εq = Rev(ŵ, ξ, Using the feasibility of (w, ξ, (p′ , q)) for LF̂ , we get ˆ (p̂′ , q̂); F ) ≥ Rev(ŵ, ξ, ˆ (p̂, q̂); F̂ ) − 2εq Rev(ŵ, ξ, ≥ Rev(w, ξ, (p′ , q); F̂ ) − 2εq = Ev∼F̂ [gw,ξ (v)] · (p′ − c(q)) − 2εq ≥ (Ev∼F [gw,ξ (v)] − ε) · (p − ρw,ξ q − c(q)) − 2εq ≥ Ev∼F [gw,ξ (v)] · (p − c(q)) − εq − Ev∼F [gw,ξ (v)] · ρw,ξ q − 2εq ≥ Rev(w, ξ, (p, q); F ) − 4εq 2

Thus with probability at least 1 − δ for ε additive error we need O( qε2 log 1δ ) samples.

B

Sample Compelxity with Demand Queries

B.1

Proof of Theorem 6

Pj We already know from Lemma 1 that mj captures the j th moment exactly. Let F̃j = i=0 αi Li (x) be the degree-j Legendre projection of F . Since Lj ’s are a family of orthogonal polynomials under the usual measure, we know Z 1 Z 1 j X αj = F (x)Lj (x)dx = aji F (x)xi dx 0

=

0

i=0

j X



Z 1

aji 1 − 0

i=0

 X   j xi+1 mi+1 f (x)dx = aji 1 − , (i + 1) i+1 i=0

as claimed. For the de la Vallee Poussin mean, which are suffix averages of higher-degree Legendre projections, using Theorem 2.1 from Mastroianni et al. (2008), with α = β = δ = γ = ν = 0 and p = ∞ substituted in their statement, for a constant C that changes neither with n nor F , we have max |F (v) − F̂⌈n/2⌉ (x)| ≤ ∆ :=

v∈[0,1]

CB r . (n/2)r

Now it follows that maxv∈[0,1] |F (v) − Fb(v)| ≤ ∆, because forcing the CDF estimate to be non-negative and non-decreasing can only (weakly) decrease the L∞ distance. Note that in this section, both F and Fb are continuous, the former by assumption, and the latter because it is a polynomial. For continuous distributions, signals are simple partitions of the value space, as explained in Section 3.1. Consider any generic signal k such that π(k|v) = 1{v ∈ [v0 , v1 )}. Now, we have that Pr [k] = F (v1 ) − F (v0 ), Z v1 Z v1 EF [v1{v ∈ [v0 , v1 )}] = vf (v)dv = v1 F (v1 ) − v0 F (v0 ) − F (v)dv. π◦F

v0

v0

Thus, we can transfer L∞ approximation guarantees from F to probability of occurrence of signals, and the corresponding posterior means. Concretely, we have Pr (k) − Pr (k) ≤ ∆, and EF [v|k] − EFb [v|k] ≤

π◦F

b π◦F

where the last display uses the inequality that

A′ A B′ − B

19

′

∆ , max{Prπ◦F (k), Prπ◦Fb (k)} ′

′

A |B −B| ≤ |A B−A| + B . ′ B

From here on, we essentially retrace the proof of Theorem 2. We decompose the error as Rev ∗ (F ) − Rev(x̃F̂ ; F ) = Rev ∗ (F ) − Rev ∗ (F̂ ) + Rev ∗ (F̂ ) − Rev(x̃F̂ ; F, F ) . | {z } | {z } Term1

Term2

To upper bound Term 1, let xF be the optimal pair of menu ((qk , pk ) : k ∈ [K]) and monotone partitional signaling scheme (tk : k ∈ [K]) under F . Let zτ = {k ∈ [K] : tk − tk−1 < τ }. Define x̃F with signaling scheme π̃ modified so that all signals in zτ are mapped to a null signal, and the prices discounted as p̃k = pk − kρ. Then, we have that Term1 := Rev ∗ (F ) − Rev(x̃F ; F̂ , F̂ ) + Rev(x̃F ; F̂ , F̂ ) − Rev ∗ (F̂ ) ≤ Rev ∗ (F ) − Rev(x̃F ; F̂ , F̂ ) where we once again appeal to the fact that Rev ∗ (F̂ ) is the optimal Fb. √ revenue for the empirical distribution √ Now,√we use Lemma 3, which places an upper bound of O(qK ∆) on Term 1, by choosing ρ = 4q ∆ and τ = ∆. Similarly, for Term2, let xFb be the optimal pair of menu ((qk , pk ) : k ∈ [K]) and monotone partitional signaling scheme (tk : k ∈ [K]) this time under Fb. Let z̃τ = {k ∈ [K] : tk − tk−1 < τ }. Let x̃Fb be the analogous modification where all signals in z̃τ are mapped to a null signal, and prices are linear-additively discounted by ρ at all indices. Now, applying Lemma 3, with the roles of F and Fb reversed, we get Term2 := Rev ∗ (Fb) − Rev ∗ (xFb ; Fb, Fb) + Rev(xFb ; Fb, Fb) − Rev ∗ (x̃Fb ; F, F ) √ ≤ Rev(x b ; Fb, Fb ) − Rev(x̃F ; F̂ , F̂ ) = O(qK ∆). F

Now, we solve for n that makes the net revenue loss ε.

C

Regret under Joint Learning

Define the following quantity,    GAP(x, F, C(F )) := sup  G∈C(F ) 

 Rev(x⋆F ; F, F ) | {z }

optimal revenue under the common prior of F

−

Rev(x; G, F ) | {z }

  . 

revenue under x when buyer holds prior G

K For any CDF F over [0, v] with v ≤ 1, let the solution of LF be denoted by xF = ((K, {ti }K i=0 ), (pi , qi )i=1 ) where 0 = t0 < . . . < tK = 1 is the quantile partition of the motonone partitional information structure, and (pi , qi ) is the direct menu item corresponding to the quantile interval (tk−1 , tk ]. For τ ∈ [0, 1] and ρ ≥ 0, define the transformation x̃F = Tr(xF ; τ, ρ) where x̃F consists of the following modified signaling scheme in the value-space for zτ = {k ∈ [K] : tk − tk−1 < τ }   if s = sk , k ∈ / zτ , ∀v ∈ [0, v] k | v) π(s P π̃(s | v) = k∈zτ π(sk | v) if s = null, ∀v ∈ [0, v]   1 if s = null, ∀v ∈ (v, 1]

where (π(k | v) : ∀v ∈ [0, v], k ∈ [K]) is the value-space description w.r.t F from Section 3.1 with a modified menu (p̃i , qi )K i=0 where p̃i = pi − iρ ∀i ∈ [K]. K Lemma 4. Let F be a CDF over V = [0, v] with v ≤ 1 and let xF = ((K, {ti }K i=0 ), (pi , qi )i=1 ) be the solution of LF . For each CDF G, define EG [v|k] the posterior mean of signal sk (which corresponds to the quantile interval (tk−1 , tk ] of F ) under G. Let C(F ) be the family of CDFs G on [0, 1] such that we have |EF [v|k] − EG [v|k]| ≤ ρ/q ∀ k ∈ [K]\zτ for zτ = {k ∈ [K] : tk − tk−1 < τ }. Then for x̃F = Tr(xF ; τ, ρ), we have GAP(x̃F , F, C(F )) ≤ K(ρ + q̄τ ).

20

Proof of Lemma 4. Since (pk , qk ) is a solution of LF , it satisfies individual rationality (IR) under F , i.e. EF [v|k] · qk − pk ≥ 0 for all k ∈ [K]. For any k ∈ [K]\zτ , since |EF [v|k] − EG [v|k]| ≤ ρ/q, we have under G that IR for all k ∈ [K]\zτ with the modified prices. Furthermore, the incentive compatibility constraint under F gives, for all k, j ∈ [K]: EF [v|k] · qk − pk ≥ EF [v|k] · qj − pj .

(3)

Observe that for all k ∈ [K] we have that qk · EG [v|k] − pk ≥ qk · EF [v|k] − pk − ρ ≥ max{0, max{qj · EF [v|k] − pj }} − ρ j

≥ max{0, max{qj · EG [v|k] − pj }} − 2ρ j

Now observe that for all j < k that qk · EG [v|k] − p̃k = qk · EG [v|k] − pk + kρ ≥ qj · EG [v|k] − pj + kρ − ρ = qj · EG [v|k] − p̃j + (k − j)ρ − ρ ≥ qj · EG [v|k] − p̃j . Thus GAP(x̃F , F, C(F )) ≤ K(ρ + q̄τ ) using the same argument as in Lemma A.2. Definition 5. Let G denote the class of functions gu,v,ξu ,ξv : [0, v] → [0, 1] of the form gu,v,ξu ,ξv (x) := ξu 1{x = u} + 1{u < x < v} + ξv 1{x = v},

u ≤ v ∈ [0, v],

ξu , ξv ∈ [0, 1].

Lemma 5. Let F, G ∈ ∆([0, 1]) be CDFs with supv |F (v) − G(v)| ≤ ε. For any g ∈ G such that EF [g], EG [g] > 0, we have   1 1 EF [xg] EG [xg] − ≤ 4ε min , . EF [g] EG [g] EF [g] EG [g] Proof. By triangle inequality EF [xg] EG [xg] |EF [xg] − EG [xg]| EG [xg] |EF [g] − EG [g]| − ≤ + · . EF [g] EG [g] EF [g] EF [g] EG [g] Since EG [xg]/EG [g] ≤ 1 as x ∈ [0, 1], it suffices to bound |EF [h] − EG [h]| for h ∈ {g, xg}. Observe that |EF [h] − EG [h]| ≤ dTV (h) sup |F (v) − G(v)| ≤ εdTV (h) v

where dTV (h) = supn sup0=x0 <x1 <...<xn =1 [0, 1], this is so since

Pn

i=1 |h(xi ) − h(xi−1 )| is the total variation of the function h on

Z 1 EF [h] − EG [h] =

Z 1 hd(F − G) = −

0

(F − G)dh. 0

Now g ∈ G has the total variation at most 2, and x · g has the total variation at most 2 since x ≤ 1. Hence |EF [g] − EG [g]| ≤ 2ε and |EF [xg] − EG [xg]| ≤ 2vε. Substituting gives us the bound. Swapping F and G yields the same bound as EG [g] in the denominator, and taking the minimum proves the claim. Theorem 12. Algorithm 4 with cutoff τt and discount ρt =P4q̄εt /τt is (β, κ)-robustly revenue efficient for
sets C(F̂t ) = {G ∈ ∆(V) : supv |G(v) − F̂t (v)| ≤ εt } for β ≥ t∈[T ] 2 exp −tε2t /2 and κt = K q̄(4εt /τt + τt ) where V = [0, 1] for any sequence {εt }t=T , {τt }Tt=1 with τt , εt ∈ (0, 1] ∀t ∈ [T ]. 21

Proof of Theorem 12. Consider G ∈ C(F̂t ), then we have by definition supv∈V |G(v) − F̂t (v)| ≤ εt . From Lemma 5, we have ∀G ∈ C(F̂t ) the following for all [u, v] ⊆ V   1 1 EF [xg] EG [xg] ≤ 4ε min − , . EF [g] EG [g] EF [g] EG [g]
Let xF̂ = (I, t), (pi , qi )i∈[I] ) be the solution of LF̂t and let zτt = {i ∈ [I] : ti − ti−1 < τt } ⊆ [I]. Then from above we have ∀G ∈ C(F̂t ) the following EG [v|k] − EF̂t [v|k] ≤ 4εt /τt =: ρt /q̄

∀ i ∈ [I]\zτ .

For x̃F̂t = Tr(xF̂t ; τt , ρt ) using Lemma 4, we get GAP(x̃F̂t , F̂t , C(F̂t )) ≤ K q̄(4εt /τt + τt ) =: κt . Finally,     PrF ⋆ ∩Tt=1 C(F̂t ) ̸∋ F ⋆ = PrF ⋆ ∪Tt=1 C(F̂t )c ∋ F ⋆   X ≤ PrF ⋆ C(F̂t )c ∋ F ⋆ t∈[T ]

=



X

PrF ⋆

≤



v

t∈[T ]

X

sup |F ⋆ (v) − F̂t (v)| > ϵt

2 exp −2tϵ2t ,

t∈[T ]

where the last inequality follows from the Dvoretzky–Kiefer–Wolfowitz (DKW) Dvoretzky et al. (1956); Massart (1990) inequality given as follows  
Pr sup |F (v) − F̂ (v)| > ϵn ≤ 2 exp −2nϵ2n . v∈R

√ √ Theorem 13. Algorithm 4 with cutoff τt = εt and discount ρt = 4q̄ εt , for C(F̂t ) = {G ∈ ∆(V) : p
supv |G(v)−F̂t (v)| ≤ εt } with εt = 3 log T /t gives the following cumulative regret Reg ≤ O K q̄(log T )1/4 T 3/4 with probability at least 1 − 3T −1/2 .
Proof of Theorem 13. Define the event E := ∩Tt=1 {F ⋆ ∈ C(F̂t )}. Let xF̂ = (I, t), (pi , qi )i∈[I] ) be the solution of LF̂t and let zτt = {i ∈ [I] : ti − ti−1 < τt } ⊆ [I]. Then recall that Algorithm 4 uses x̃F̂t = Tr(xF̂t ; τt , ρt ). p √ Then for εt = 3 log T /t and τt = εt ∀t ∈ [T ], Theorem 12 gives (β, κ)-robustly revenue efficiency for PT P √ T β = t=1 2 exp(−tε2t /2) = t=1 2T −3/2 = 2T −1/2 and κt = K q̄(4εt /τt + τt ) = 5K q̄ εt . This implies Pr(E) ≥ 1 − 2T −1/2 . Then ∀G ∈ C(F̂t ) we have the following from Lemma 5 EG [v|k] − EF̂t [v|k] ≤ 4εt /τt =: ρt /q̄

∀ i ∈ [I]\zτ ,

and using Lemma 4, we get GAP(x̃F̂t , F̂t , C(F̂t )) ≤ K q̄(4εt /τt + τt ) = κt .

22

Regret upper bound : On E, supv |F ⋆ (v) − F̂t (v)| ≤ εt ∀t ∈ [T ]. Also Ftb ∈ C(F̂t ) by Assumption 1. Decompose the tth -regret term as follows     OPT(F ⋆ ) − Rev(x̃F̂t ; Ftb , F ⋆ ) = OPT(F ⋆ ) − OPT(F̂t ) + OPT(F̂t ) − Rev(x̃F̂t ; Ftb , F̂t ) {z } | | {z } (A)

(B)

  + Rev(x̃F̂t ; Ftb , F̂t ) − Rev(x̃F̂t ; Ftb , F ⋆ ) . | {z } (C)

Since Ftb ∈ C(F̂t ) we get (B) ≤ GAP(x̃F̂t , F̂t , C(F̂t )) ≤ κt . PK For (C) the buyer’s decision is the same, so it can be upper bounded by q̄ supv |F ⋆ (v)− F̂t (v)| k=1 dTV (gk ) ≤ 2q̄εt K since g has 2 jumps of size at most 1, where dTV (·) is the total variation distance. ⋆ Define x̃F ⋆ = Tr(xF ⋆ ; τt , ρt ) for xF ⋆ = ((K ⋆ , t⋆ ), (p⋆i , qi⋆ )K i=1 ) solution of LF ⋆ . Then ∀G ∈ C(F ) we have the following from Lemma 5 |EG [v|k] − EF ⋆ [v|k]| ≤ 4εt /τt = ρt /q̄

∀ k ∈ [K ⋆ ] : t⋆k − t⋆k−1 ≥ τt ,

and using Lemma 4, we get GAP(x̃F ⋆ , F ⋆ , C(F ⋆ )) ≤ K q̄(4εt /τt + τt ) = κt . Recall that under E, we also have F̂t ∈ C(F ⋆ ) ∀t ∈ [T ]. For (A) we perform the following decomposition     (A) ≤ OPT(F ⋆ ) − Rev(x̃F ⋆ ; F̂t , F ⋆ ) + Rev(x̃F ⋆ ; F̂t , F ⋆ ) − Rev(x̃F ⋆ ; F̂t , F̂t ) | {z } | {z } ≤ GAP(x̃F ⋆ ,F ⋆ ,C(F ⋆ )) ≤ κt

≤2q̄εt K using same TV argument as (C)

  Rev(x̃F ⋆ ; F̂t , F̂t ) − OPT(F̂t ) | {z }

+

≤ 0 due to suboptimality of x̃F ⋆ under F̂t

≤ κt + 2q̄εt K. Combining we get overall OPT(F ⋆ ) − Rev(x̃F̂t ; Ftb , F ⋆ ) ≤ 2κt + 4q̄εt K. Finally, define Yt := revt (x̃F̂t ; Ftb ) − Rev(x̃F̂t ; Ftb , F ⋆ ). Since x̃F̂t and Ftb are Ht -measurable and vt |Ht ∼ F , we have E[Yt |Ht ] = 0 and |Yt | ≤ q̄ where Ht denotes the σ-algebra of all the histories upto time t. By Azuma-Hoeffding, we get !   T X z2 Pr (−Yt ) ≥ z q̄ ≤ exp − . 2T t=1 ⋆

√ Setting z = T log T gives T −1/2 P upper bound. Thus overall on the event E ∩ { t (−Yt ) ≤ z q̄}, which now holds with probability ≥ 1 − 2T −1/2 − T −1/2 = 1 − 3T −1/2 , we get Reg =

T X

T T
X
X OPT(F ⋆ ) − revt = OPT(F ⋆ ) − Rev(x̃F̂t ; Ftb , F ⋆ ) + (−Yt )

t=1

t=1

≤

t=1

T X

(2κt + 4q̄εt K) + q̄

t=1

23

p

T log T .

p √ √ Substituting τt = εt gives us κt = K q̄(4εt /τt + τt ) = 5K q̄ εt and since εt = 3 log T /t, we have PT PT √ εt = (3 log T )1/4 t−1/4 and εt = (3 log T )1/2 t−1/2 . Using t=1 t−1/4 ≤ 43 T 3/4 and t=1 t−1/2 ≤ 2T 1/2 we get the leading term as follows T X √

  εt ≤ 43 (3 log T )1/4 T 3/4 = O (log T )1/4 T 3/4

t=1

Finally we have   Reg ≤ O K q̄(log T )1/4 T 3/4 .

Consider the following set for which we show the O(T 2/3 ) regret guaranty. ) ( s EF̂t [xg] EG [xg] 1 1 ′ 2 ≤ εt . C (F̂t ) = G ∈ ∆(V) : − + εt EF̂t [g] EG [g] max{EF̂t [g], EG [g]} max{EF̂t [g], EG [g]} √ Theorem 14. Algorithm 4 with cutoff τt and discount ρt = q̄(εt / τt + ε2t /τt ) is (β, κ)-robustly revenue
P √ efficient for the sets C ′ (F̂t ) for β ≥ t∈[T ] t exp −tε2t /C and κt = K q̄(εt / τt + ε2t /τt + τt ) where V = [0, 1] for any sequence {εt }t=T , {τt }Tt=1 with τt , εt ∈ (0, 1] ∀t ∈ [T ].
Proof of Theorem 14. Consider G ∈ C ′ (F̂t ). Let xF̂ = (I, t), (pi , qi )i∈[I] ) be the solution of LF̂t . Then we have ∀G ∈ C ′ (F̂t ) the following by definition √ EG [v|k] − EF̂t [v|k] ≤ εt / τt + ε2t /τt =: ρt /q̄∀ i ∈ [I]\zτ . For x̃F̂t = Tr(xF̂t ; τt , ρt ) using Lemma 4, we get √ GAP(x̃F̂t , F̂t , C ′ (F̂t )) ≤ K q̄(εt / τt + ε2t /τt + τt ) =: κt . Finally,     PrF ⋆ ∩Tt=1 C ′ (F̂t ) ̸∋ F ⋆ = PrF ⋆ ∪Tt=1 C ′ (F̂t )c ∋ F ⋆   X ≤ PrF ⋆ C ′ (F̂t )c ∋ F ⋆ t∈[T ]

X

≤

t exp −tε2t /C ,

t∈[T ]

where the last inequality follows from Lemma 2 for some constant C. √ 1/3 Theorem 15. Algorithm 4 with cutoff τt = εt and discount ρt = q̄(εt / τt + ε2t /τt ), for C ′ (F̂t ) with p
εt = 5 log T /(2t) gives the following cumulative regret Reg ≤ O K q̄(log T )1/3 T 2/3 with probability at least 1 − O(T −1/2 ). Proof of Theorem 15. Define the event E := ∩Tt=1 {F ⋆ ∈ C(F̂t
) := {G ∈ ∆([0, 1]) : maxv |G(v) − F̂t (v)| ≤ ξt }} and E ′ := ∩Tt=1 {F ⋆ ∈ C ′ (F̂t )}. Let xF̂ = (I, t), (pi , qi )i∈[I] ) be the solution of LF̂t and let zτt = {i ∈ [I] : p ti − ti−1 < τt } ⊆ [I]. Then recall that Algorithm 4 uses x̃F̂t = Tr(xF̂t ; τt , ρt ). Then for εt = 5 log T /(2t) P 1/3 and τt = εt , Theorem 14 gives (β, κ)-robustly revenue efficiency for β = t∈[T ] t exp (−tεt /C) = O(T −1/2 ) √ 1/3 and κt = K q̄(εt / τt + ε2t /τt + τt ) = O(Kqεt ). This gives Pr(E ′ ) ≥ 1 − O(T −1/2 ). 24

Also, we have ∀G ∈ C ′ (F̂t ) the following by definition √ EG [v|k] − EF̂t [v|k] ≤ εt / τt + ε2t /τt = ρt /q̄∀ i ∈ [I]\zτ . For x̃F̂t using Lemma 4, we get √ GAP(x̃F̂t , F̂t , C ′ (F̂t )) ≤ K q̄(εt / τt + ε2t /τt + τt ) = κt . Using DKW we also have 1 − Pr(E) ≤

X

2 exp(−2tξt2 ).

t∈[T ]

q

log(2T 3/2 ) we get Pr(E) ≥ 1 − O(T −1/2 ) and therefore Pr(E ∩ E ′ ) ≥ 1 − O(T −1/2 ). 2t Regret upper bound : Ftb ∈ C(F̂t ) by Assumption 1. Under the event E ∩ E ′ decompose the tth -regret term

For ξt =

as follows     OPT(F ⋆ ) − Rev(x̃F̂t ; Ftb , F ⋆ ) = OPT(F ⋆ ) − OPT(F̂t ) + OPT(F̂t ) − Rev(x̃F̂t ; Ftb , F̂t ) {z } | | {z } (A)

(B)

  + Rev(x̃F̂t ; Ftb , F̂t ) − Rev(x̃F̂t ; Ftb , F ⋆ ) . | {z } (C)

Since Ftb ∈ C ′ (F̂t ), we get (B) ≤ GAP(x̃F̂t , F̂t , C ′ (F̂t )) ≤ κt PK For (C) the buyer’s decision is the same, so it can be upper bounded by q̄ supv |F ⋆ (v)− F̂t (v)| k=1 dTV (gk ) ≤ 2q̄ξt K since g has atmost 2 jumps. ′ ⋆ Define x̃F ⋆ = Tr(xF ⋆ ; τt , ρt ) for xF ⋆ = ((K ⋆ , t⋆ ), (p⋆i , qi⋆ )K i=1 ) solution of LF ⋆ . Then ∀G ∈ C (F ) we have the following by definition |EG [v|k] − EF ⋆ [v|k]| ≤ ρt /q̄

∀ k ∈ [K ⋆ ] : t⋆k − t⋆k−1 ≥ τt ,

and using Lemma 4, we get GAP(x̃F ⋆ , F ⋆ , C ′ (F ⋆ )) ≤ κt . Recall that under E ∩ E ′ , we also have F̂t ∈ C ′ (F ⋆ ) ∀t ∈ [T ]. For (A) we perform the following decomposition     (A) ≤ OPT(F ⋆ ) − Rev(x̃F ⋆ ; F̂t , F ⋆ ) + Rev(x̃F ⋆ ; F̂t , F ⋆ ) − Rev(x̃F ⋆ ; F̂t , F̂t ) | {z } | {z } ≤ GAP(x̃F ⋆ ,F ⋆ ,C ′ (F ⋆ )) ≤ κt

+



≤2q̄ξt K using same TV argument as (C)



Rev(x̃F ⋆ ; F̂t , F̂t ) − OPT(F̂t ) | {z }

≤ 0 due to suboptimality of x̃F ⋆ under F̂t

≤ κt + 2q̄ξt K. Combining we get overall OPT(F ⋆ ) − Rev(x̃F̂t ; Ftb , F ⋆ ) ≤ 2κt + 4q̄ξt K. Finally, define Yt := revt (x̃F̂t ; Ftb ) − Rev(x̃F̂t ; Ftb , F ⋆ ). Since x̃F̂t and Ftb are Ht -measurable and vt |Ht ∼ F , we have E[Yt |Ht ] = 0 and |Yt | ≤ q̄ where Ht denotes the σ-algebra of all the histories upto time t. By Azuma-Hoeffding, we get !   T X z2 Pr (−Yt ) ≥ z q̄ ≤ exp − . 2T t=1 ⋆

25

√ Setting z = T log T gives T −1/2 upperP bound. Thus overall on the event E ∩ E ′ ∩ { t (−Yt ) ≤ z q̄}, which now holds with probability ≥ 1 − O(T −1/2 ), we get Reg =

T X

⋆

OPT(F ) − revt =

t=1

T X

OPT(F

⋆

) − Rev(x̃F̂t ; Ftb , F ⋆ )

t=1

≤

T X + (−Yt ) t=1

T X

(2κt + 4q̄ξt K) + q̄

p

T log T .

t=1

p √ 1/3 1/3 Substituting τt = εt gives us κt = K q̄(εt / τt + ε2t /τt + τt ) = O(K q̄εt ) and since εt = 5C log T /(2t), √ PT 1/3 we have εt = (5C log T /(2t))2/3 and t=1 ξt = O( 3T log T ), which gives us   Reg ≤ O K q̄(log T )1/3 T 2/3

D

Proofs for the FPTAS

Lemma 6. Consider any quantile interval [t1 , t2 ] with 0 ≤ t1 < t2 ≤ 1, and define t̃1 := ε⌊ tε1 ⌋, t̃2 := ε⌊ tε2 ⌋. R t2 R t̃2 Q(u)du Q(u)du t1 Then |(t2 − t1 ) − (t̃2 − t̃1 )| ≤ ε. Moreover, let µ(t1 , t2 ) = and define µ(t̃1 , t̃2 ) = t̃1 and t2 − t 1 t̃2 − t̃1 as Q(t̃1 ) whenever t̃1 = t̃2 . Then |µ(t1 , t2 ) − µ(t̃1 , t̃2 )| ≤

3ε . t2 − t 1

Proof of Lemma 6. By definition, t̃1 ≤ t1 and t1 − ε ≤ t̃1 and similarly, t̃2 ≤ t2 and t2 − ε ≤ t̃2 . Thus t2 − t1 ≤ t̃2 + ε − t̃1 and t2 − t1 ≥ t̃2 − t̃1 − ε. Thus |t2 − t1 − (t̃2 − t̃1 )| ≤ ε. Thus if t̃2 − t̃1 = 0, then t2 − t1 < ε, then the inequality immediately follows |µ(t2 , t1 ) − Q(t̃1 )| ≤ 1 ≤ 3ε/(t2 − t1 ). Otherwise for t̃2 > t̃1 we have Z t2

Z t̃2 Q(u)du −

t1

Z t̃1 Q(u)du ≤

t̃1

Z t̃2 Q(u)du ≤ 2ε

Q(u)du + t2

t1

which gives R t2 |µ(t1 , t2 ) − µ(t̃1 , t̃1 )| ≤

t1

R t̃ Q(u)du − t̃12 Q(u)du t2 − t 1 Z t̃2 + Q(u)du

Z t̃2 +

Q(u)du t̃1

2ε 1 1 − t1 − t 2 t − t t̃ − t̃2 1 2 1 t̃1 2ε ε ≤ + (t̃2 − t̃1 ) t2 − t 1 (t2 − t1 )(t̃2 − t̃1 ) ≤

≤ 3ε/τ

26

1 1 − t2 − t 1 t̃2 − t̃1

Theorem 16 (Correctness of Algorithm 2). For LsF restricted to quantiles in Et and qualities in Eq , the ⋆ Algorithm 2 outputs an optimal menu {(pk , qjk )}kk=1 and a valid information structure I = (k ⋆ , t). Proof. For k ∈ [K], r ∈ [nt ] and j ∈ [nq ], define ( k ) X V (k, r, j) := max U[ℓi−1 , ℓi , ji−1 , ji ] 0 = ℓ0 < . . . < ℓk = r, 0 = j0 i=1

which denotes the maximum revenue that can be obtain from partitioning (0, tr ] into k nonempty quantile grid intervals with the last interval assigned quality qj . Define V (0, 0, 0) = 0 and V (0, r, j) = −∞ ∀(r, j) ̸= (0, 0). We claim Rev[k, r, j] = V (k, r, j) ∀ k, r, j. We will show this by an induction over k. Base case is when k = 0, by initialization we have equality. Inductive step assume that Rev[k − 1, ·, ·] = V (k − 1, ·, ·). The DP recursion gives us Rev[k, r, j] = max {Rev[k − 1, ℓ, j ′ ] + U [ℓ, r, j ′ , j]} = max {V (k − 1, ℓ, j ′ ) + U [ℓ, r, j ′ , j]} 0≤ℓ<r 0≤j ′ ≤j

0≤ℓ<r 0≤j ′ ≤j

We will first show that Rev[k, r, j] ≤ V (k, r, j) ∀r, j. To do this, fix any 0 ≤ ℓ < r and 0 ≤ j ′ ≤ j and let 0 = ℓ0 < . . . < ℓk−1 = ℓ be a partition of intervals (k − 1) with quality assignment 0 = j0 ≤ . . . ≤ jk−1 = j ′ where the quantile interval indexed by [ℓk−2 , ℓk−1 ] is assigned quality indexed jk−1 and so on. Appending (ℓ, r] at the end of the quantile interval gives us a valid valid partition as ℓ < r and assigning quality qj to this interval is valid since it maintains monotonicity, such a scheme gives us revenue of V (k − 1, ℓ, j ′ ) + U[ℓ, r, j ′ , j]. By feasibility we have V (k − 1, ℓ, j ′ ) + U[ℓ, r, j ′ , j] ≤ V (k, r, j) ∀0 ≤ ℓ < r, 0 ≤ j ′ ≤ j. Taking maximum on all such ℓ, j ′ gives us Rev[k, r, j] ≤ V (k, r, j)∀r, j. Now we show that V (k, r, j) ≤ Rev[k, r, j] ∀r, j. Consider the k partition 0 ≤ ℓ0 < . . . < ℓk = r and the quality assignment of 0 = j0 ≤ . . . ≤ jk = j that obtains the value V (k, r, j). Set ℓ = ℓk−1 and j ′ = jk−1 . Then the partition 0 = ℓ0 < . . . < ℓ is a valid (k − 1) partition with feasible quality assingment Pk−1 0 = j0 ≤ . . . ≤ j ′ giving us i=1 U[ℓi−1 , ℓi , ji−1 , ji ] ≤ V (k − 1, ℓ, j ′ ). Finally, by definition, we have V (k, r, j) =

k−1 X

U[ℓi−1 , ℓi , ji−1 , ji ] + U [ℓ, r, j ′ , j] ≤ V (k − 1, ℓ, j ′ ) + U [ℓ, r, j ′ , j] ≤ Rev[k, r, j]

i=1

where the last inequality follows from the DP update. Optimality of the partitions and quality assignment follows from the greedy backward pass, and optimality and IC of the menu follow from the payment formula.

Theorem 17. Let x = (I, t), (pi , qi )i∈[I] be the solution of LF . Then the DP output x′ = (I ′ , t′ ), (p′i , qi′ )i∈[I] √ is such that Rev(x′ ; F ) ≥ Rev(x; F ) − εOPT where the optimization error is given as εOPT = I(6q + 1 + q) ε. Proof of Theorem 17. We use the following decomposition Rev(x; F ) − Rev(x′ ; F ) = Rev(x; F ) − Rev(x̃; F ) + Rev(x̃; F ) − Rev(x′ ; F ) | {z } ≤0 (by correctness of DP)

where x̃ ← modification(x) such that for x̃ = ((I, t̃), (p̃i , q̃i )i∈[I] ) where each component of t̃ and each q̃i lie on the grid Et and Eq respectively, with p̃i defined later. In particular let q̃i = ε⌊ qεi ⌋ and t̃i = ε⌊ tεi ⌋. Thus the monotonicity of q̃i is preserved. Based on the modification, we have q̃i ≤ qi and qi − ε ≤ q̃i and similarly, t̃i ≤ ti and ti − ε ≤ t̃i . Let zτ = {i ∈ [I] : ti−1 − ti < τ }. Consider i ̸∈ zτ . Then using Lemma 6 we get q̃i · µ(t̃i−1 , t̃i ) − pi ≥ qi · µ(ti−1 , ti ) − pi − 3qε/(ti−1 − ti ) − ε 27

≥ qi · µ(ti−1 , ti ) − pi − 3qε/τ − ε ≥ max{0, max{qj · µ(ti−1 , ti ) − pj }} − 3qε/τ − ε j

≥ max{0, max{qj · µ(t̃i−1 , t̃i ) − pj }} − 6qε/τ − ε j

≥ max{0, max{q̃j · µ(t̃i−1 , t̃i ) − pj }} − 6qε/τ − ε j

Let p̃i = pi − iρ for ρ = 6qε/τ + ε. Then observe that for all j < i µ(t̃i−1 , t̃i ) · q̃i − p̃i = µ(t̃i−1 , t̃i ) · q̃i − pi + iρ ≥ µ(t̃i−1 , t̃i ) · q̃j − pj + iρ − ρ = µ(t̃i−1 , t̃i ) · q̃j − p̃j + (i − j)ρ − ρ ≥ µ(t̃i−1 , t̃i ) · q̃j − p̃j Therefore, buyer upon receiving signal i ̸∈ zτ agrees to pay at least pi −Iρ, generating a margin of pi −c(qi )−Iρ, therefore, Rev(x; F ) − Rev(x̃; F ) ≤ I(ρ + qτ ) where for upper √ bound we assume the worst case that buyers with signal i ∈ zτ do not purchase anything. Setting τ = ε, we get √ Rev(x; F ) − Rev(x′ ; F ) ≤ I(6q + 1 + q) ε

Theorem 18. For discrete F with O(m) atoms, Algorithm 2 has a runtime complexity of O K · m2 · n2q which is O(1/ε4 ) for m = O(1/ε), and has memory complexity O(K · m · nq ).

Proof of Thm 18. Complexity. Algorithm 2 preprocesses A(·) at all m + 1 grid points in O(m + N ) time, so that each µF (ℓ, r) is evaluated in O(1). The DP table has K · m · nq entries where filling each entry requires
maximizing over O(m · nq ) pairs (ℓ, j ′ ), giving a total forward-pass runtime complexity of O K · m2 · n2q . The backward pass runs in O(K) with price computation in O(K 2 ), and the signaling scheme in O(K · N ), all dominated by the forward pass. The grid {t0 , . . . , tm } can be chosen freely, choosing m points with maximum spacing ∆ := maxi (ti − ti−1 ) = O(ε) requires m = O(1/ε). With nq = O((q − q)/ε), the total time is thus O(K/ε4 ) which polynomial in 1/ε for fixed K, q, and q. Memory complexity is O(K · m · nq ) for the Rev and ptr tables. Theorem 19 (Additive-FPTAS). For any εOPT > 0, given a discrete distribution with support size N , ⋆ Algorithm 2 runs in poly(K, N, q, 1/εOPT ) time and outputs a menu {(pk , qjk )}kk=1 and a monotone paritional signaling scheme I = (k ⋆ , (trk : k ∈ [k ⋆ ])) with revenue exceeding Rev ⋆ (F ) − εOPT by setting the resolution of the grid as ε = (εOPT )2 /(K(6q + 1 + q))2 . Proof. The proof follows by a combination of earlier results, namely, Theorems 16, 17, and 18.

E

Equivalent Representations of Signaling Schemes

Lemma 7. Consider the following equivalent representation of the signaling scheme. [I]

1. Quantile space representation: S = {ri }i=1 with the signaling scheme as π(ri |u) = 1{u ∈ [ti−1 , ti ]} for all u ∼ Unif[0, 1] where t0 = 1 − tI = 0 with ti−1 ≤ ti and ti ∈ [0, 1] ∀ i ∈ [I].

28

[I]

2. Value space representation: S = {si }i=1 w0 ≤ w1 ≤ · · · ≤ wI , ξi ∈ [0, 1] with ξ0 = 0, ξI = 1, and ξi−1 ≤ ξi whenever wi−1 = wi , with the signaling scheme as ( (1 − ξi−1 )1{v = wi−1 } + 1{wi−1 < v < wi } + ξi 1{v = wi } if wi−1 < wi , π(si |v) = (ξi − ξi−1 )1{v = wi−1 } if wi−1 = wi . for all v ∼ F . Then for ti = (1 − ξi )F (wi− ) + ξi F (wi ), the posterior mean under signal si and signal ri is equal to R ti Q(t)dt/(ti − ti−1 ) where Q(t) = inf{v : F (v) ≥ t}. ti−1 Proof of Lemma 7. In the value space, it is a little messy and can be written as π(ri |v) = λ([F (v − ), F (v)] ∩ [ti−1 , ti ])/(F (v) − F (v − )), where λ(·) captures the length of the interval, concretely, a Lebesgue measure. The posterior expected value under ri is N/D where Z 1

Z ti Q(u)1{u ∈ [ti−1 , ti ]}du =

N= 0

Q(u)du ti−1

where we used v = Q(u) and Z 1 1{u ∈ [ti−1 , ti ]}du = ti − ti−1

D= 0

Consider first the case when wi−1 < wi , this implies F is continuous and strictly increasing on (wi−1 , wi ). Then the posterior expected value under si is N′ /D′ where N′ =

Z v

− vdF (v) = wi−1 (1 − ξi−1 )(F (wi−1 ) − F (wi−1 )) +

0

Z

vdF (v) + wi ξi (F (wi ) − F (wi− ))

(wi−1 ,wi )

Note by the definition of Q(·) we have Q(t) = wi−1 ∀t ∈ [ti−1 , F (wi−1 )] and Q(t) = wi ∀t ∈ [F (wi− ), ti ]. R R F (wi− ) Therefore (wi−1 ,wi ) vdF (v) = F (wi−1 Q(t)dt, substituting this in N′ and writing ξi in terms of ti gives us ) ′ N = N. Also, Z v̄ Z − D′ = dF (v) = (1 − ξi−1 )(F (wi−1 ) − F (wi−1 )) + dF (v) + ξi (F (wi ) − F (wi− )) 0

(wi−1 ,wi ) − = (1 − ξi−1 )(F (wi−1 ) − F (wi−1 )) + (F (wi− ) − F (wi−1 ) + ξi (F (wi ) − F (wi− ))

= ti − ti−1 = D R v̄ For the case when wi−1 = wi , ti−1 , ti ∈ [F (wi− ), F (w)] thus Q(t) = wi ∀t ∈ [ti−1 , ti ]. Thus 0 vdF (v) = R v̄ wi (ξi − ξi−1 )(F (wi ) − F (wi− )) and 0 dF (v) = (ξi − ξi−1 )(F (wi ) − F (wi− )), which writing ξi in terms of ti gives the desired result.

29

Related documents

• Learning to Price with Persuasion#625261
• Learning to Price with Persuasion#622988
• Fairness and the Strengths of Agents' Claims#767291
• Belief Elicitation from Agents with Competing Incentives#1115456
• Bargaining with Algorithms: An Experiment on Algorithmic Price Discrimination and Consumer and Data Protection Laws#1176847