Platforms can learn to combine personalized signals with menu pricing to nearly maximize revenue: the paper proves polynomial-time algorithms with explicit sample-complexity bounds and delivers the first additive FPTAS for the joint pricing-and-signaling design problem.

Main Finding

The paper studies a monopolist seller that simultaneously designs a public menu of quality-price pairs and a signaling (persuasion) scheme to influence buyers’ posterior beliefs about their match value. Removing the usual assumption that the seller knows the buyers’ value distribution, the authors give sample-efficient learning algorithms and the first additive FPTAS for the joint menu+signaling optimization. Concretely: - From n = Õ(K^3 q^3 / ε^3) i.i.d. value samples the seller can (with high probability) learn a menu+signaling scheme whose expected revenue is within ε of optimum. - They give an additive FPTAS (polynomial time) to compute an ε-additive optimal menu+signaling scheme for discrete (empirical) distributions. - In an interactive demand-query model the sample complexity can be dramatically smaller (constant for discrete supports; O(1/ε^2) for bounded pdfs; better under smoothness). - They also provide online/joint-learning regret bounds (e.g., O(T^{3/4}) regret in a T-horizon game).

(K is the maximum menu size bound coming from model structure; q denotes quality-range parameters used in their bounds.)

Key Points

• Model:
  • Buyers have latent value V ∈ [0,1] drawn from unknown prior F. Buyers are ex ante unaware of their own value; when they receive a signal s the buyer uses posterior mean to choose a menu item.
  • Seller can produce qualities q ∈ Q and must commit to a public menu M = {(q_i,p_i)} and a signaling scheme π(s|v). Seller cannot perform explicit price discrimination but can use information (signals/recommendations) to indirectly segment buyers.
  • Production cost c(q) is convex, non-decreasing. Tie-breaking favors seller.
  • A structural result (from Bergemann et al.): the seller-optimal information structure is a monotone partitional scheme and the optimal menu has at most K items.
• Learning results:
  • ERM algorithm (Algorithm 1): fit an empirical distribution bF, compute a near-optimal monotone-partitional signaling scheme and menu on bF, translate quantile-based signals to value-space, modify prices with a carefully chosen linear-additive discount and bundle rare signals into a null signal. With n = Õ(K^3 q^3 / ε^3) samples this yields ε-additive optimal revenue with high probability.
  • Single-item menu special case: sample complexity improves to Õ(q^2/ε^2).
  • Demand-query / interactive model: much smaller sample requirements — constant for discrete supports; O(1/ε^2) for continuous distributions with bounded pdf; O(1/ε) with Lipschitz pdf; polylog(1/ε) for analytic pdfs.
  • Online/joint learning: seller and buyer population both learning leads to regret bounds (e.g., O(T^{3/4})).
• Algorithmic contributions:
  • Translation from quantile-space (monotone partitions) to value-space signaling descriptions (handles continuous and discrete/mixed distributions via randomized signaling).
  • Price-repair technique: linear-additive discounts across menu items (not simple multiplicative discounts) to restore IC/IR when empirical posteriors differ from true ones; bundling rare (low-probability) signals into a null signal to limit worst-case deviations.
  • A variance-aware uniform deviation bound (relative-deviation style) for conditional means that improves sample complexity analysis versus naive uniform bounds.
  • Additive FPTAS via dynamic programming on discretized quantile and quality grids exploiting IC structure and bounded menu size.
• Why the problem is hard: joint menu+signaling design is non-convex (IC constraints couple signals and prices); posterior means under empirical and true priors can differ arbitrarily for rare signals, which can violate IC unless handled carefully.

Data & Methods

• Data access modes considered:
  • Value-sample model: i.i.d. samples from the unknown value distribution F.
  • Demand-query / interactive model: the seller can present schemes and observe buyer item choices (feedback-rich).
  • Online/joint learning: repeated interaction where both seller and buyer population update from realized values.
• Core algorithms:
  • Algorithm 1 (ERM via samples): build empirical CDF bF, compute near-optimal monotone partitional scheme on bF, map quantile-partition to value-space π(·|v), mark signals with tiny marginal mass as “bad” and bundle them, apply linear-additive discounts to prices (˜p_k = p_k − kρ) to maintain IC/IR in the true distribution.
  • Algorithm 2 (DP FPTAS): discretize quantiles and qualities; dynamic program that scans quantiles left-to-right, remembering only last assigned quality (uses incentive-compatibility structure) to achieve polynomial-time additive ε-approximation on discrete distributions.
• Theoretical tools:
  • Use Bergemann et al. structural result: optimal information design can be taken monotone partitional and menu size is bounded by K.
  • Variance-aware uniform convergence (relative-deviation / VC-class tools) to bound errors of conditional means with dependence on signal frequency ν: error scales like 1/√(ν n) rather than 1/(ν √n).
  • Careful IC/IR repair analysis showing that naive discount schemes cause spillover across types; linear-additive discount + bundling localizes fixes and yields the sample bounds.
• Main quantitative guarantees (selected):
  • Value-samples, arbitrary F: n = Õ(K^3 q^3 / ε^3) samples suffice for ε-additive optimal revenue (Theorem 2).
  • Single-item menu: n = Õ(q^2 / ε^2) suffices (Theorem 3).
  • Demand-query sample complexity table (from paper summary):
    • Discrete: O(1)
    • Bounded pdf: Õ(1/ε^2)
    • Lipschitz pdf: Õ(1/ε)
    • Analytic pdf: polylog(1/ε)
  • Additive FPTAS: polynomial-time algorithm producing an ε-additive optimal menu+scheme on an empirical (discrete) distribution.
  • Regret in T-horizon joint learning: O(T^{3/4}) (paper gives this as one of the results).

Implications for AI Economics

• Practical relevance: modern platforms that collect rich user data can implement revenue-improving indirect price discrimination by combining menus and personalized signals (recommendations). This paper quantifies how much data those platforms need to learn near-optimal joint menu+signal policies.
• Learning + mechanism design interaction: demonstrates that even in a non-convex joint information-mechanism design problem, sample-efficient learning and polynomial-time approximation are possible using structural economic properties (bounded menu size, monotone partitions).
• Guidance for platform design:
  • Recommendation algorithms (signals) can be used strategically to segment demand and raise seller revenue while respecting public-menu constraints (no explicit personalized prices).
  • Price adjustments and robustness (bundling rare signals, conservative discounts) are necessary to ensure incentive-compatibility when the seller is learning the prior from data.
• Policy and regulatory considerations:
  • The results formalize how much data is needed to effectively implement indirect personalization; this is relevant to privacy and anti-discrimination debates because even without price discrimination, information design plus a public menu can achieve segmentation.
  • The importance of rare-signal handling suggests small groups may be more sensitive to misestimation and manipulation.
• Directions for further research:
  • Extend to multi-seller / competitive markets, richer buyer heterogeneity (contextual features), or strategic buyers who learn/respond over time.
  • Incorporate privacy constraints (DP learning for menu+signal design) or fairness constraints into the learning objectives.
  • Empirical validation on platform data to measure constants and practical performance of the proposed ERM + DP methods.
• Limitations to bear in mind:
  • The model assumes the seller can fully commit to both menu and signaling scheme and knows the mapping from qualities to buyer utility functional form (v · q − p). Real platforms may face commitment or model-misspecification issues.
  • Some bounds depend on model parameters (K, q) and discretization; constants hidden in Õ may matter in practice.

Summary: the paper builds a rigorous bridge between information design (persuasion) and learnable mechanism design: it gives sample- and compute-efficient procedures to learn revenue-maximizing menu+signaling policies from data, characterizes how data richness and smoothness affect sample complexity, and supplies an additive FPTAS for the inherently non-convex joint design problem.