PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Price with Persuasion

Maria-Florina Balcan, Tejas Pagare, Karan Singh

arXiv:2608.16699v1cs.GTcs.LGecon.TH

TL;DR

The paper asks how to learn revenue-maximizing menus and signaling schemes when sellers do not know buyers’ value distribution. It develops batch, demand-query, and online learning approaches, together with an efficient approximation algorithm for the non-convex joint-design problem. The results provide sample, computational, and regret guarantees for this asymmetric information setting.

  • Problem

    The paper addresses the gap created by assuming sellers know the precise distribution of buyers’ tastes, an assumption considered implausible for diverse modern marketplaces.

  • Method

    The paper combines value-sample learning, demand-query learning, online joint-learning analysis, and an algorithm for computing monotone partitional menus and signaling schemes.

  • Results

    The paper gives learning guarantees for batch and interactive settings, regret upper bounds for online joint learning, and the first polynomial-time FPTAS for the non-convex joint-design problem.

  • Takeaways & Limitations

    The work brings a learning-theoretic perspective to the interface between information design and traditional mechanism design.

  • Takeaways & Limitations

    In the joint-learning setting, buyers’ beliefs are incompletely specified, so the seller must design schemes robust to a set of possible beliefs.

Abstract

from arXiv · show

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

The paper studies learning revenue-maximizing menus and signaling schemes when sellers do not know buyers’ taste distribution, motivated by information-rich marketplaces. It provides sample-based and interactive learning guarantees, an efficient approximation algorithm despite non-convexity, and online regret bounds.

  • Motivation: Modern algorithmic marketplaces collect detailed user profiles, creating settings where sellers possess information about buyers’ latent preferences.The motivation includes demographic data and purchase histories.
  • Model motivation: The model extends monopolistic screening by allowing sellers to provide partial match-value information through signaling alongside a quality-price menu.Signals can act as personalized product recommendations or search rankings, enabling indirect price discrimination.
  • Learning problem: The paper relaxes the assumption that sellers know the precise distribution of buyers’ tastes and studies how samples and past interactions can provide that knowledge.The goal is to characterize explicit sample and computational requirements for learning a revenue-maximizing scheme.
  • Contributions: O(1/ε^3) i.i.d. value samples suffice to produce a menu and signaling scheme whose revenue is within ε of maximum.This is the batch value-sample guarantee.
  • Contributions: The first FPTAS computes a menu and signaling scheme in polynomial time with arbitrarily small additive revenue loss despite joint-design non-convexity.This computational result addresses an open problem identified in the prior work.
  • Contributions: Demand queries yield constant sample complexity for discrete values and O(1/ε^2) samples for bounded-density continuous values, with polylogarithmic requirements for analytic densities.The paper also gives regret upper bounds when sellers and buyer populations jointly learn online.

2 Problem Setup and Preliminaries

The setup has a monopolist selling quality-price options while committing to a signaling scheme that shapes buyers’ posterior beliefs and choices. The optimal joint design can be represented using finitely many menu items and monotone quantile partitions.

  • Economic environment: A monopolist manufactures qualities in Q at convex, non-decreasing cost c(q), while a buyer of value v receives utility v · q − p.Values lie on a common prior over V = [0, 1].
  • Mechanism: The seller commits to a public menu of quality-price pairs and a signaling scheme, also called an information structure or Blackwell experiment.The signal space can be put in one-to-one correspondence with menu items through an obedience argument.
  • Mechanism: For each value v, the signaling scheme specifies a conditional distribution over signals; after observing a signal, the buyer forms a posterior mean and selects a menu item.The seller samples the signal according to π(·|v), and each signal can label the buyer’s best-response menu item.
  • Optimization: The seller maximizes expected profit p(s) − c(q(s)) subject to individual rationality and incentive compatibility for every signal.Individual rationality requires nonnegative utility, while incentive compatibility requires the assigned item to maximize signal-conditioned utility.
  • Structural result: With information provision, the number of optimal menu items is finite even for continuous value distributions, unlike the potentially unbounded number without information provision.This finite structure supports the paper’s computational treatment of the joint design problem.
  • Structural result: The optimal menu has at most K items, and its optimal information structure is monotone partitional with at most K distinct signals.Monotone partitional structures divide value quantiles into intervals, with each signal revealing the corresponding quantile interval.

3 Sample Complexity with Value Samples

The section develops an empirical-revenue-maximization approach that transfers a menu-signaling scheme learned from samples to the unknown value distribution while repairing incentive constraints. It establishes approximation guarantees, improved single-item complexity, and a variance-aware analysis that sharpens standard uniform-deviation bounds.

  • Algorithmic framework: The algorithm learns a near-optimal menu and signaling scheme from i.i.d. samples, then translates empirical quantile signals into a value-space description for the unknown distribution.The procedure optimizes on the empirical distribution, converts quantile partitions into value-space signals, designates rare signals as bad, and discounts prices.
  • Algorithmic framework: The distribution affects revenue both through signal-generation probabilities and through the posterior beliefs buyers use to choose menu items.Thus, applying an empirically optimized scheme directly can change buyer behavior on the true distribution.
  • Value-space translation: Discrete or mixed distributions require randomized signaling so quantile intervals sharing an atom are assigned only portions of that atom’s probability mass.This preserves the intended signal marginals and posterior means under the empirical distribution.
  • Constraint repair: Price discounting repairs incentive and participation constraints caused by differences between empirical and true posterior means, but multi-item menus require discounts to propagate across higher prices.Because rare signals can have unstable conditional means and a discount at one signal affects other types, the revenue impact can scale as O(K∆).

4 Additive FPTAS for Revenue Maximization

The paper formulates revenue maximization as a dynamic program over quantile intervals and quality levels, yielding an additive FPTAS for jointly designing menus and signaling schemes.

  • Guarantee: For any εOPT > 0, Algorithm 2 runs in poly(K, N, q, 1/εOPT) time and outputs a menu with revenue within εOPT of the optimum.The guarantee is stated for discrete distributions with support size N and extends to arbitrary distributions through the empirical distribution when sampling access is available.
  • Problem reduction: The payment formula reduces the optimization problem by making the lowest type’s participation constraint and adjacent-type incentive constraints binding.This also implies monotonicity of qualities with respect to buyer values.
  • Discretization: The algorithm discretizes qualities and quantiles into grids and scans quantile intervals from left to right.The construction includes an outside-option quality and grid resolutions controlled by ε.
  • Dynamic programming: The FPTAS uses a dynamic program whose state stores the number of pools, the final quantile boundary, and the last assigned quality.The transition utility captures revenue from assigning a quality to an interval given the preceding interval’s quality, while preserving quality monotonicity.

5 Sample Complexity with Demand Queries

Demand queries let the seller recover distributional moments from buyer responses and use them to construct revenue-maximizing or approximately optimal menu-signaling pairs. The resulting query complexity is constant for discrete distributions and improves with smoothness for continuous ones.

  • Continuous distributions: For continuous distributions, the method estimates the CDF using polynomial approximation and converts the estimate into a nonnegative nondecreasing CDF envelope.The construction uses de la Vallée Poussin means after moment recovery and then derives a quantile-based signaling scheme.
  • Demand-query model: A demand query returns both the signal shown to a randomly drawn buyer and the menu item selected in response.The seller chooses the signaling scheme and menu before observing the buyer’s response.
  • Discrete distributions: For discrete distributions with support size n + 1, n queries recover a revenue-maximizing menu-signaling pair exactly.Theorem 5 states that the resulting revenue equals Rev∗(F).
  • Discrete distributions: The queries recover moments exactly, and Vandermonde inversion then recovers the underlying probability mass function without revenue loss.Distinct support points ensure that the Vandermonde matrix is invertible.
  • Continuous distributions: 1/ε2 queries suffice for bounded pdfs, 1/ε queries for Lipschitz pdfs, and polylogarithmic queries for analytic functions.These rates follow from the stated continuous-distribution approximation results.

6 Regret under Joint Learning

In the joint-learning setting, the seller repeatedly updates an empirical value distribution while buyers’ beliefs may also evolve. Robust revenue efficiency is defined through belief-set coverage and worst-case revenue loss over possible histories.

  • Online setting: The online model lets the seller observe each buyer’s value and purchase decision after deploying a menu and signaling scheme.The seller and buyer population jointly learn from past value realizations, while buyers may also update beliefs externally.
  • Robustness: Robust revenue efficiency requires high-probability coverage of buyers’ beliefs and a bounded revenue gap for every possible history.The gap is evaluated against the best scheme under the seller’s empirical distribution.
  • Belief sets: The seller uses statistically achievable belief sets centered at the empirical distribution, with radius εt in the Kolmogorov metric.Algorithm 4 selects parameters based on these sets and updates the empirical distribution over time.
  • Guarantees: The analysis establishes parameter choices and discount sequences under which the online algorithm is robustly revenue efficient.One stated choice uses ρt = 4q̄εt/τt for the sets Ct(εt).
  • Guarantees: The paper also gives a ˜O(T 2/3) cumulative-regret upper bound for more intricate statistically plausible belief sets.Regret compares the seller’s cumulative revenue with the benchmark defined over rounds.

7 Conclusion

The paper develops learning algorithms for personalized menu and recommendation design using samples, demand queries, and online interactions. It also provides an efficient near-optimal solver despite the underlying non-convexity.

  • Conclusion: The motivation is that algorithmic platforms can use user trails to forecast personalized value for niche products.The paper frames this as a learning problem at the interface of information and mechanism design.
  • Conclusion: 1/ε3-order value samples suffice for learning a menu-signaling scheme with near-optimal revenue.The conclusion summarizes the sample-based guarantee as order 1/ε3.
  • Conclusion: Demand-query feedback can substantially reduce sample requirements, in some circumstances making them near-constant.This improvement comes from observing buyer behavior under selected menus and recommendations.
  • Conclusion: An efficient algorithm computes a near-optimal menu and signaling scheme even though the joint optimization problem is non-convex.The paper’s proofs cover both the joint-learning regret setting and the FPTAS.

A.1 Proof of Theorem 2

The proof controls revenue loss between the true and empirical taste distributions using uniform convergence and modified signaling schemes. It then combines these bounds with an empirical-optimality argument to establish the sample guarantee.

  • The proof decomposes the revenue gap into terms comparing optimal revenues and modified schemes under true and empirical distributions.Term 1 is explicitly defined as the difference between optimal revenue under F and the empirical distribution.
  • With high probability, Lemma 2 provides simultaneous bounds for signal probabilities under the true and empirical distributions.The bound applies to all monotone partitional signaling schemes with K signals.
  • Small-probability signals are mapped to a null signal and prices are discounted linearly to preserve participation-related guarantees under distribution changes.The modification removes signals with marginal probability below τ and uses prices ˜pk = pk − kρ.
  • Lemma 3 bounds the loss from this modification by qK(τ + 2(ε1/τ + ε2/√τ) + ε0).The bound is applied after choosing ρ and τ according to the sampling error scale.
  • Uniform convergence is obtained by applying variance-sensitive bounds to function classes with bounded pseudo-dimension.The relevant signal probabilities and conditional-value expressions are represented using classes whose pseudo-dimension is bounded by a constant.

A.5 Proof of Theorem 3

This proof analyzes a two-signal setting by expressing signal probability and posterior means explicitly, then transfers feasibility and revenue guarantees between the true and empirical distributions.

  • The two-signal information structure is parameterized by a threshold w1 and endpoint weight ξ1.The high and low signals correspond to a partition of the value space.
  • The high-signal posterior mean is computed as the expected value weighted by the threshold and endpoint randomization.The expression uses (1 − ξ1)v1{v = w1} + v1{v > w1}.
  • The optimization objective multiplies the probability of realizing the high signal by an indicator that the buyer participates.Participation occurs when the posterior-mean quality value covers the menu price.
  • Empirical and true-distribution individual-rationality constraints are related by reducing prices according to estimated signal probabilities.The adjusted prices preserve feasibility across the two distributions.
  • Revenue under the true distribution is at least the empirical revenue minus 2εq.The comparison applies to the transformed menu and signaling parameters.
  • The proof solves for the sample size needed to make the net revenue loss ε.The resulting sample requirement is stated with probability at least 1 − δ.

B.1 Proof of Theorem 6

The proof extends the empirical-distribution analysis by approximating continuous distributions and transferring CDF approximation guarantees to signal probabilities and posterior means.

  • The continuous-distribution analysis decomposes the revenue error into terms comparing true and empirical optimal revenues.The same modified-scheme strategy is then applied to both terms.
  • CDF approximation in L∞ transfers to approximation of signal occurrence probabilities and corresponding posterior means.Signals are value-space intervals for continuous distributions.
  • The proof modifies schemes by nulling signals with interval mass below τ and discounting prices.This transformation is used to control feasibility and revenue loss under distributional changes.
  • The sample size is chosen by solving for n so that the combined revenue loss is ε.This closes the proof after bounding both error terms.

C Regret under Joint Learning

The joint-learning analysis studies robust revenue efficiency when empirical distributions are updated online. It combines confidence-set guarantees, scheme transformations, and concentration bounds to control cumulative regret.

  • Robust revenue efficiency: A transformed scheme nulls sufficiently small signal intervals and discounts menu prices to remain robust over a CDF confidence set.For distributions in C(F), the transformation gap is bounded by K(ρ + q̄τ).
  • Robust revenue efficiency: For C(ˆFt) defined by supv |G(v) − ˆFt(v)| ≤ εt, Algorithm 4 uses ρt = 4q̄εt/τt and incurs κt = Kq̄(4εt/τt + τt).These parameters provide the stated robust-efficiency guarantee.
  • Regret under joint learning: Choosing τt = √εt and the prescribed εt yields robust efficiency with probability at least 1 − 3T^-1/2.The resulting per-round loss is κt = 5Kq̄√εt.
  • Regret under joint learning: The regret proof decomposes each round’s loss into confidence-set, transformation, decision, and martingale terms.Azuma-Hoeffding controls the martingale contribution.
  • Alternative confidence sets: A second robust-efficiency result uses ρt = q̄(εt/√τt + εt^2/τt) for the sets C′(ˆFt).The theorem gives κ bounds for any sequences of confidence radii and cutoffs.
  • Alternative confidence sets: For the alternative confidence sets, the resulting high-probability event holds with probability at least 1 − O(T^-1/2).The regret decomposition again uses the robust-efficiency and concentration bounds.

D Proofs for the FPTAS

The proofs establish that dynamic programming optimally solves the discretized menu-and-signaling problem, while grid rounding controls the resulting revenue loss and yields an additive FPTAS.

  • Rounding analysis: Rounding quantile boundaries and qualities to grids preserves monotonicity and incurs a bounded additive revenue loss.The analysis modifies thresholds, qualities, and prices while bounding the loss through interval-width and rounding arguments.
  • Dynamic-program correctness: The dynamic program’s value function equals the maximum revenue over feasible monotone partitions and quality assignments.The proof establishes both inequalities by induction over the number of intervals.
  • Dynamic-program correctness: The backward pass recovers optimal partitions and quality assignments, while the payment formula ensures an optimal incentive-compatible menu.These properties follow from the DP construction and the payment formula.
  • Rounding analysis: Setting the grid parameter to √ε yields the optimization error εOPT = I(6q + 1 + q)√ε.The bound follows after accounting for the rounding and DP approximation errors.
  • Complexity and FPTAS: For discrete distributions, Algorithm 2 runs in polynomial time and uses O(K · m · nq) memory, with O(K/ε4) time when m = O(1/ε).The runtime is dominated by the forward DP pass; the backward pass, price computation, and signaling construction are lower-order terms.
  • Complexity and FPTAS: The additive FPTAS outputs a monotone partition signaling scheme and menu with revenue exceeding Rev⋆(F) − εOPT.The grid resolution is chosen as ε = (εOPT)2/(K(6q + 1 + q))2.
Loading 2608.16699v1…