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.
Figures & tables
Model
Value distribution
Sample Complexity / Regret
Value samples
Arbitrary
O(1/ε3)
Demand queries
Discrete
O(1)
Bounded pdf
O(1/ε2)
Lipschitz pdf
O(1/ε)
Analytic pdf
O(polylog 1/ε)
Joint learning
Arbitrary
O(T3/4)
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.
π~(s∣v)={π(s∣v)∑k∈zτπ(k∣v) if s∈/zτ, if s=null
Algorithm 1 Empirical Revenue Maximization (ERM) via Samples
π~(s∣v)={πk(s∣v)∑k∈zτπk(k∣v) if s∈/zτ, if s=null
Algorithm 3 Empirical Revenue Maximization via Demand Queries
The data market design problem is a problem in economic theory to find a set of signaling schemes (statistical experiments) to maximize expected revenue to the information seller, where each experiment reveals some of the information known to a seller and has a corresponding price [Bergemann et al., 2018]. Each buyer has their own decision to make in a world environment, and their subjective expected value for the information associated with a particular experiment comes from the improvement in this decision and depends on their prior and value for different outcomes. In a setting with multiple buyers, a buyer's expected value for an experiment may also depend on the information sold to others [Bonatti et al., 2022]. We introduce the application of deep learning for the design of revenue-optimal data markets, looking to expand the frontiers of what can be understood and achieved. Relative to earlier work on deep learning for auction design [Dütting et al., 2023], we must learn signaling schemes rather than allocation rules and handle obedience constraints − these arising from modeling the downstream actions of buyers − in addition to incentive constraints on bids. Our experiments demonstrate that this new deep learning framework can almost precisely replicate all known solutions from theory, expand to more complex settings, and be used to establish the optimality of new designs for data markets and make conjectures in regard to the structure of optimal designs.
Sai Srivatsa Ravindranath, Yanchen Jiang, David C. Parkes
Harvard John A. Paulson School of Engineering and Applied Sciences
We study the pricing behavior of third-party platforms facing strategic agents. Assuming the platform is a revenue maximizer, it observes market features that generally affect demand. Since only transacted quantities and prices can be observed, this presents a general demand learning problem under confounding. Mathematically, we develop an algorithm with optimal regret of \TildeO(T∧σS−2). Our results reveal that supply-side noise fundamentally affects the learnability of demand, leading to a phase transition in regret. Technically, we show that non-i.i.d. actions can serve as instrumental variables for learning demand. We also propose a novel homeomorphic construction that allows us to establish estimation bounds without assuming star-shapedness, providing the first efficiency guarantee for learning demand with deep neural networks. Finally, we use simulations and offline counterfactuals from Talabat and Lyft data to illustrate the potential revenue implications of our approach.
Bayesian persuasion studies how an informed sender can influence the behavior of a receiver through strategic information disclosure. Standard models assume the sender is the receiver's only source of information, yet in many applications receivers also consult external sources the sender can neither observe nor control. We study an online Bayesian persuasion problem in which a binary-action receiver has access to a fixed signaling scheme that is unknown to the sender. Over T rounds, the sender commits to a signaling scheme and sends a signal; the receiver combines it with its private signal and acts, while the sender observes only the action. We design a learning algorithm that achieves regret O(T3/4) relative to the optimal scheme of a sender who knows the private signaling scheme of the receiver, with polynomial dependence on the sizes of the state space and the receiver's signal alphabet. Our key insight is reducing the problem of learning the exponentially large belief-space partitioning induced by the private scheme to a one-dimensional change-point detection problem.