On the limitations of data-based price discrimination
Abstract
EconStor is a publication server for scholarly economic literature, provided as a non-commercial public service by the ZBW.
Full text
Xie, Haitian; Zhu, Ying; Shishkin, Denis Article On the limitations of data-based price discrimination Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Xie, Haitian; Zhu, Ying; Shishkin, Denis (2025) : On the limitations of data-based price discrimination, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 20, Iss. 1, pp. 303-351, https://doi.org/10.3982/TE5916 This Version is available at: https://hdl.handle.net/10419/320287 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/
Theoretical Economics 20 (2025), 303–351 1555-7561/20250303 On the limitations of data-based price discrimination Haitian Xie Department of Business Statistics and Econometrics, Guanghua School of Management, Peking University Ying Zhu Department of Economics, University of California San Diego Denis Shishkin Department of Economics, University of California San Diego The classic third degree price discrimination (3PD) model requires the knowledge of the distribution of buyer valuations and the covariate to set the price conditioned on the covariate. In terms of generating revenue, the classic result shows that 3PD is at least as good as uniform pricing. What if the seller has to set a price based only on a sample of observations from the underlying distribution? Is it still obvious that the seller should engage in 3PD? This paper sheds light on these fundamental questions. In particular, the comparison of the revenue performance between 3PD and uniform pricing is ambiguous overall when prices are set based on samples. This finding is in the nature of statistical learning under uncertainty: a curse of dimensionality, but also other small sample complications. Keywords. Price discrimination, empirical revenue maximization, information theory, prior-independent pricing, optimal rate of convergence. JEL classification. C14, C44, D42, D82. 1. Introduction In the past few decades, the advances in the theory of mechanism design have been followed by a tremendous interest in its practical applications. At the same time, classic Haitian Xie: [email protected] Ying Zhu: [email protected] Denis Shishkin: [email protected] Haitian Xie and Ying Zhu share the first authorship and are listed alphabetically. This paper supersedes a previously circulated draft by Xie and Zhu (https://arxiv.org/pdf/2204.12723v1.pdf). All three authors are grateful to the constructive comments from two anonymous reviewers at Theoretical Economics, and three anonymous reviewers and the meta reviewer at ACM Economics and Computation. The authors would also like to thank Dirk Bergemann, Songzi Du, Federico Echenique, Graham Elliott, Yannai Gonczarowski, Roger Gordon, Nima Haghpanah, Johannes Horner, Jonathan Libgober, Esfandiar Maasoumi, Maximilian Schaefer, Joel Sobel, Karl Schlag, Larry Samuelson, Yixiao Sun, J. Miguel Villas-Boas, and Joel Watson for valuable comments and discussions. Haitian Xie is grateful to the UC San Diego Department of Economics where this project was developed during his doctoral studies. Xie is supported by the Fundamental Research Funds for the Central Universities at Peking University. Ying Zhu is grateful to the Society of Hellman Fellows at University of California and the Cowles Foundation at Yale University, and also thanks participants at her seminars. ©2025 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5916
304 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) theoretical models typically make strong assumptions about the designer’s knowledge of the environment, which may lead the optimal mechanism to be sensitive to the details of the environment (which is sometimes referred to as the Wilson critique).1 Third degree price discrimination (3PD) requires an observable covariate value associated with the buyer valuation. To set the price conditioned on the covariate, the classic pricing model requires the knowledge of the distribution of buyer valuations and the covariate. In terms of generating revenue, the classic result shows that 3PD is at least as good as uniform pricing. What if the seller has only partial information about those distributions? Is it still obvious that the seller should engage in 3PD? On the one hand, setting the optimal price for each observed value of the covariate may not “extrapolate” well to the unobserved covariate values, and yield a lower expected revenue than a uniform price. But on the other hand, too little discrimination underutilizes the information contained in the covariate about buyer valuations. This paper is concerned with how much information the seller will need to make 3PD generate more revenue. Suppose a unit demand buyer with a privately-known valuation Yand a one-dimensional continuous covariate Xdrawn from a joint distribution FY,Xthat is unknown to the seller. The continuous covariate Xcan be a single index or score that summarizes the relevant characteristics for pricing and marketing. Hartmann, Nair, and Narayanan (2011)provide examples where marketing firms use a one-dimensional continuous score function of customer characteristics, past response histories, and features of the zip code, and casinos use a one-dimensional continuous score referred to as the average daily win. While our seller is ignorant of FY,X, he/she does have access to a random sample of i.i.d. {Yi,Xi}n i=1drawn from FY,X. A natural strategy is to choose prices that optimize against the empirical distribution of {Yi,Xi}n i=1.TheK-markets empirical revenue maximization (ERM) divides the covariate space into Kequal-length segments, and the optimal price based on the conditional empirical distribution for each segment is calculated. We show that when K=(n1/4),theK-markets ERM strategy generates an expected revenue converging to that of the true distribution 3PD optimum at the rate O(n−1/2). The 1-market ERM strategy is simply the (uniform) ERM strategy, which we show generates a revenue converging to that of the true-distribution uniform optimum at the rate O(n−2/3).TheK-markets ERM is just one possible strategy and one may wonder if a more sophisticated strategy might provide faster convergence rates. In a sense, the answer is no. We show that these rates are asymptotically unimprovable for the worst case distributions of (Y,X)subject to some mild smoothness conditions. In other words, to guarantee a revenue deficiency of δuniformly over a class of distributions, the necessary condition for the sample size is that n=(δ−2)in the 3PD problem and n=(δ−3/2)in the uniform pricing problem. For sufficiently small δ,theK-markets ERM and the uniform ERM strategies are optimal on the growth requirements of the sample size, respectively; that is, n=(δ−2) in the 3PD problem and n=(δ−3/2)in the uniform pricing problem. To show this optimality result, we establish a lower bound for the revenue deficiency in any databased pricing strategy relative to the true-distribution optimal strategy in the worst case 1In some cases, this leads to extreme or unrealistic results as in, for example, Crémer and McLean (1988). 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 305 (by considering the supremum over a class of joint distributions, FY,X, subject to some mild smoothness assumptions). In particular, data-based uniform pricing strategies are algorithms that depend on {Yi}n i=1only, and the true-distribution optimal strategy corresponds to the optimal uniform pricing strategy derived from FY. Similarly, data-based 3PD strategies are algorithms that depend on {Yi,Xi}n i=1, and the true-distribution optimal strategy corresponds to the optimal 3PD strategy derived from FY,X. We show that the minimax revenue deficiency is (n−2/3)and (n−1/2)in the uniform and 3PD cases, respectively. Our results highlight the following economic trade-off. When the seller has the access to a sample of i.i.d. {Yi,Xi}n i=1, she can choose the K-markets ERM strategy that exploits both {Xi}n i=1and {Yi}n i=1, or the uniform ERM strategy that ignores {Xi}n i=1and exploits only {Yi}n i=1. Inherently, the former is an algorithm trying to learn the FY,Xoptimal pricing function p(·)while the latter is an algorithm trying to learn the FYoptimal (constant) pricing function. As a result of the curse from the extra dimensionality, the former is more demanding in the sample size than the latter. However, in terms of generating revenue, the true-distribution optimal 3PD strategy is at least as good as the true-distribution optimal uniform pricing strategy. This trade-off suggests that, even if Xcontains useful information about Y,theK-markets ERM strategy based on a random sample can be revenue inferior to the uniform ERM strategy when the sample size nis not large enough, and vice versa. To verify these potential implications, we conduct several numerical studies. In particular, we calculate the revenues of the K-markets ERM and the uniform ERM strategies based on a real-world data set from eBay auctions and two simulated data sets. Our numerical results illustrate the aforementioned trade-off. When the sample size is small, the uniform ERM strategy can generate higher expected revenue than the K-markets ERM strategy. As the sample size grows, the K-markets ERM strategy (the uniform ERM strategy) gets closer to the true-distribution optimal 3PD strategy (resp., the truedistribution optimal uniform pricing strategy). The slower rate of convergence in the revenue from the K-markets ERM strategy (in contrast to the faster rate of convergence in the revenue from the uniform ERM strategy) is dominated by the benefit of price discrimination (based on FY,X) over uniform pricing (based on FY). Consequently, the revenue of the K-markets ERM strategy overtakes that of the uniform ERM strategy when the sample size becomes sufficiently large and Xcontains sufficient information about Y. The key takeaways from this paper are summarized here. First, no sample-based 3PD strategy is able to escape from the curse of dimensionality, shown by our information theoretic lower bounds. Second, absent uncertainty regarding the underlying probability laws, third-degree price discrimination is at least as good as uniform pricing in generating revenue. In contrast, the comparison of the revenue performance between the K-markets ERM and the uniform ERM strategies is ambiguous overall. This finding is in the nature of statistical learning under uncertainty: a curse of dimensionality, but also other small sample complications.2Empirical revenue maximization is not free of 2Specifically, there exists a distribution FYwhere the revenue of the uniform ERM strategy is worse with two observations than with one; see Babaioff, Gonczarowski, Mansour, and Moran (2018). We illustrate in 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
306 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) these issues. Ultimately, this paper poses a challenging open question of whether there exist some n<¯ n<∞such that for any n∈[n,¯ n]and distribution in the class defined in this paper, the K-markets ERM strategy (for any K>1) is always revenue-inferior to the uniform ERM strategy. 1.1 Related literature Complexity measures and information theoretic lower bounds Information theoretic lower bounds and sample complexity are important notions in machine learning. Both aim to characterize learnability, i.e., how easy it is to learn an unknown object of interest (in our context, the true-distribution optimal 3PD strategy) from data where the uncertainty arises. Sample complexity derives the rate at which the sample size needs to grow to guarantee a desired learning accuracy. Information theoretic lower bound derives a lower bound as a function of the sample size on the learning error (in our context, the revenue deficiency) in the worst case. Sample complexity and information theoretic lower bounds are intrinsically tied to the complexity or size of the underlying function class of interest. Vapnik–Chervonenkis (VC) dimensions, shattering dimensions, and metric entropy (such as the cardinality of packing sets) are popular measures of complexity in machine learning. There have been a number of innovative applications of VC dimensions or shattering dimensions in economic theory and algorithmic economics. Together with the Probably Approximately Correct (PAC) framework, they are used to study the complexity of the classes of demand and utility functions (Beigman and Vohra (2006), Balcan, Daniely, Mehta, Urner, and Vazirani (2014)), k-demand buyer’s valuation (Zhang and Conitzer (2020)), theories of choices (Basu and Echenique (2020)), preference functions (Chambers, Echenique, and Lambert (2021,2023)), as well as the resulting learnability from data. VC dimension is useful for deriving sample complexity bounds concerning discrete function sets and finite-dimensional vector spaces, and shattering dimension is useful for certain real functions. From the theory of machine learning, when a class has infinite VC or shattering dimensions, this class is not PAC learnable. For example, a collection of sinusoids have subgraphs with infinite VC dimension. The max-min expected utility model with at least three states of the world has infinite VC dimension (Basu and Echenique (2020)). The class of demand functions has infinite shattering dimension (Beigman and Vohra (2006)). Nonetheless, the notion of “learnability” can be generalized using a different type of complexity analysis that gives rise to our information theoretic lower bound in the 3PD problem. This type of analysis is built upon the notion of packing sets, along with tools from information theory. In particular, packing sets are useful for studying classes with an infinite number of elements (see Kolmogorov and Tikhomirov (1959) and Wainwright (2019)). This is the case for our 3PD problem as we try to learn an optimal pricing function of the covariate (an infinitely-dimensional parameter) and bound the deficiency in the expected revenue, which concerns the entire pricing function at all covariate values. Section 6that this seemingly counter-intuitive result highlights the difficulty of establishing general comparative results with very small sample size and sheds some light on the comparison of the revenue performance of the K-markets ERM strategy with K=1vs.K=2inthecaseofn=2. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 307 Prior-independent mechanism design Most of the classic monopoly pricing literature assumes a known distribution of valuations (and covariates).3More recently, some papers (e.g., those surveyed in Carroll (2019)) studied “prior”-independent mechanism design.4The main focus of that literature is on deriving a robustly optimal mechanism in the absence of both “prior” and data. In particular, Bergemann and Schlag (2008,2011) derive the minimax-regret uniform pricing strategy in closed form; that is, the strategy that guarantees the smallest deficiency in revenue relative to the known distribution case. Like Bergemann and Schlag (2008,2011), we study the revenue deficiencies, but in contrast, we assume the availability of data and focus on the (inevitable) informationtheoretic limitations of any data-based pricing strategies and the achievability of the limitation. This paper is inspired by the literature that studies approximately optimal “prior”- independent mechanism design, in particular monopoly pricing with a single buyer.5 This literature assumes that the seller has access to a random sample of i.i.d. {Yi}n i=1 drawn from FYand proposes variants of the uniform ERM strategy to derive the revenue guarantee in relation to that from the true-distribution optimal uniform pricing strategy. There are two types of analyses in this literature. The first one focuses on the guarantees for the specific case of n=1orn=2(Babaioff et al. (2018), Allouah, Bahamou, and Besbes (2023)). The second one (e.g., Huang, Mansour, and Roughgarden (2018)) establishes “sample complexity bounds” such that the uniform ERM variants achieve a (1−)fraction guarantee when the sample size grows at a rate depending on , and also derives the rate at which the sample size needs to grow (as a function of )for any data-based uniform pricing strategies to obtain a given (1−)fraction guarantee. Allouah, Bahamou, and Besbes (2022) involve both types of analyses. In this paper, we ask the related question, how fast the revenue deficiency decays as afunctionofn, and provide an answer using information-theoretic lower bounds (independent of algorithms) and upper bounds with respect to specific algorithms in the worst case scenarios.6The main difference with the majority of the data-based literature is that, we study third-degree price discrimination (3PD) with a continuous covariate and compare the revenue performance of data-based 3PD and uniform pricing strategies. To understand why the 3PD problem in our context is more challenging than the uniform pricing problem, note that fundamentally the latter tries to learn the constant 3See also Segal (2003) for a study of optimal multiunit auctions where the seller has a probabilistic belief about the valuation distribution of the i.i.d. buyers. 4Here, “prior” distribution refers to the seller’s prior belief about buyers’ valuations and is often taken to be the true distribution. 5There is a less related literature that studies optimal auctions; see, e.g., Cole and Roughgarden (2014), Dhangwatnotai, Roughgarden, and Yan (2015), Fu, Immorlica, Lucier, and Strack (2015), Guo, Huang, and Zhang (2019), Fu, Haghpanah, Hartline, and Kleinberg (2021). 6A large literature studies data-based auctions by focusing on guarantees for revenue deficiencies (instead of fractions), such as how the revenues from the data-based strategies converge in probability to the true-distribution benchmark, e.g., Baliga and Vohra (2003), Goldberg, Hartline, Karlin, Saks, and Wright (2006), Gonçalves and Furtado (2024). This line of work does not consider the optimal rates of convergence or optimal sample size requirements. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
308 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) optimal pricing function (a scalar parameter) while the former tries to learn an optimal pricing function of the covariate (an infinitely-dimensional parameter), where the deficiency in the expected revenue concerns the entire pricing function at all covariate values. Our framework allows us to tackle several challenging aspects of the 3PD problem, which might be difficult to analyze with the toolkit in the existing pricing literature. We describe one example below. Somewhat related, Devanur, Huang, and Psomas (2016) study sample complexity of optimal pricing with “side information.” In their “signals model” (Sections 5.1 and 5.3), there is a covariate (signal) X∈[0, 1], and the seller can condition the data-based reserve price on the covariate. For the single-buyer case (which would correspond to our 3PD problem), they derive upper and lower sample complexity bounds. Importantly, they assume that the true joint distribution FY,Xhas the following property: larger values of Xare associated with larger values of Yin the sense of first-order stochastic dominance of conditional distributions. In contrast, our 3PD setup imposes no assumptions about the relationship between the covariate Xand the valuation Y; meanwhile, our proposed K-markets ERM strategy learns the relationship from the data. Moreover, our K-markets ERM strategy attains the optimal rate of convergence in revenue deficiency (as described before), while the upper and lower bounds in Devanur, Huang, and Psomas (2016)have different rates, and hence, the optimal sample size requirement is unclear. 2. Setup The seller is selling an item to a buyer. Let Y∈[0, 1]be the valuation (i.e., willingness to pay) of the buyer, and Xthe covariate (such as a characteristic) associated with the buyer. The joint distribution of (Y,X)is denoted by FY,X. We assume that Xis supported on a bounded interval, and without loss of generality, we take the interval to be [0, 1].7 Given a covariate value, the seller wants to set a price according to a mapping from the covariate to a set of prices. We use Dto denote the set of all pricing functions: D≡p:[0, 1]→[0, 1], measurable. For a generic pricing strategy p∈D, the price depends on the covariate value x.This scheme falls in the realm of third-degree price discrimination (3PD). Uniform pricing can be viewed as a special case where the price is the same for all covariate values. We use Uto denote the set of all uniform pricing functions: U≡{p∈D:pis a constant function}. 7The assumption that Y,X∈[0, 1]is made merely for simplicity. First of all, our results in Sections 3and 4hold for general bounded supports. Second, the precise knowledge of the support boundaries is unnecessary because they can be readily estimated using extremum order statistics. The estimator converges at a superconsistent rate of n−1(see, e.g., Hirano and Porter (2003)), significantly faster than the convergence of revenue deficiency that we show in Section 3. Therefore, in our analysis, the estimation error resulting from the unknown support is negligible. We are grateful to a referee for raising this discussion. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 309 To lighten the notation, we express p∈Uas a scalar rather than a function for the uniform pricing problem. Let FY|Xbe the conditional CDF and fXthe marginal density function. Given a price y∈[0, 1]and a covariate value x∈[0, 1],thereare1−FY|X(p|x)buyers whose valuation is above the price. The revenue generated from these buyers is r(y,x,FY,X)≡1−FY|X(y|x)y,(1) and the expected revenue for a pricing function pis R(p,FY,X)≡1 0 rp(x),x,FY,XfX(x)dx. In various places of the rest of the paper, we will slightly abuse the notation and denote r(p,x)≡r(p(x),x)when pis a pricing function and also write r(y,x)=r(y,x,FY,X) for brevity when FY,Xis clear from the context. In the special case where the pricing strategy is uniform (i.e., p∈U), the revenue only depends on the marginal distribution FY: R(p,FY,X)=pP(Y≥p)=p1−FY(p),p∈U. The true-distribution optimal 3PD strategy p∗ Dis the one that maximizes the revenue: Rp∗ D,FY,X=sup p∈D1 0 rp(x),x,FY,XfX(x)dx. In a similar fashion, we denote p∗ Uas the true-distribution optimal uniform pricing strategy such that Rp∗ U,FY=Rp∗ U,FY,X=sup p∈U p1−FY(p). Note that p∗ Ddepends on FY,Xand p∗ Udepends on FY. In terms of generating revenue, the classic pricing theory shows that 3PD is at least as good as uniform pricing when the joint distribution FY,Xis known to the seller. In this case, we can solve analytically or numerically for the optimal pricing strategies p∗ D and p∗ U. Since Uis contained in D,p∗ Dmust achieve a (weakly) better revenue than p∗ U. Intuitively, when Yis correlated with X,p∗ Dutilizes the information in X. Now suppose that the seller knows neither FY,Xnor FY, but instead observes a random sample of data ≡{(Yi,Xi),1≤i≤n}drawn from FY,X,ordataY≡{Yi,1≤i≤n} from FY, and wants to construct a pricing strategy based on the sample. The following assumption is used throughout this paper. Assumption 1. data and dataYconsist of i.i.d. draws from FY,Xand FY, respectively. The following assumption is used to establish the results concerning our 3PD problem. Instead of a single known joint distribution FY,X, there is a class Fof unknown distributions, which are deemed possible and our data-based pricing strategies can be evaluated within this class. The functions in Fsatisfy several smoothness and regularity conditions stated below. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
310 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Assumption 2. Any distribution function in the set Fsatisfies the following conditions: (i) (Lipschitz continuity) There exists C0∈(0, ∞)such that, for any y,y,x∈[0, 1],the conditional density fY|Xsatisfies fY|X(y|x)−fY|Xy|x≤C0y−y. (ii) (Strong concavity) There exists C∗>0such that the revenue function r(y,x)≡ y(1−FY|X(y|x)) is strictly concave with the second-order derivative −2fY|X(y|x)−y∂ ∂y fY|X(y|x)≤−C∗,a.e. (2) (iii) (Interior solution) For each x∈[0, 1], the optimal price is an interior solution; that is, p∗ D(x;FY,X)∈(0, 1). (iv) (Differentiability) The conditional distribution function fY|X(y|x)is continuously differentiable in (x,y)in a neighborhood of the curve {(x,p∗ D(x;FY,X)) :x∈ [0, 1]}. (v) (Boundedness) The functions 2fY|X(y|x)+y∂ ∂y fY|X(y|x)and (3) ∂ ∂xFY|X(y|x)+y∂ ∂xfY|X(y|x)(4) are bounded from above by C∈(0, ∞)a.e. (vi) (Marginal density) The marginal density fXis bounded from above by C∈(0, ∞) and bounded away from zero; that is, fX≥C > 0. Part (i) requires the conditional density function to be sufficiently smooth. The partial derivative ∂ ∂y fY|X(y|x)is well-defined almost everywhere because fY|Xis Lipschitz continuous, and hence, absolutely continuous. Part (iii) ensures that the first-order condition holds for the optimal price. Part (iv) ensures that the optimal pricing function p∗ D(x;FY,X)is sufficiently smooth in x. Part (v) requires the partial derivatives of the revenue to be bounded. Part (vi) ensures that the covariate does not take vanishing or dominating values. Under part (ii), the optimal price is well-defined. Part (ii) is a standard assumption in the optimal auctions/pricing literature also known as regularity (Myerson (1981)), which is a so-called “strong concavity” condition from machine learning theory. It is well known that any distribution Fwith the monotone hazard rate satisfies regularity. Analogously, the following assumption is used to establish the results for the uniform pricing problem, which concerns a class FUof unknown marginal distributions that are deemed possible. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 317 the covariate (an infinitely-dimensional parameter) and the deficiency in the expected revenue concerns the entire pricing function at all covariate values. The notion of packing sets in Kolmogorov and Tikhomirov (1959) and the Gilbert–Varshamov bound from coding theory are useful ingredients for proving Theorem 4. The most intricate part of the proof involves carefully constructing Mconditional densities (where Mgrows with n) and bounding the separation between the optimal prices associated with these densities. The desired set of optimal prices in our proof is a packing set where the separation between elements is (n−1/4)with respect to the unweighted L2norm, and the cardinality of this set is (2n1/4). 4.2 Uniform pricing We have the following theorem for uniform pricing. Theorem 5. Let Assumption 1hold. For any FUsatisfying the conditions in Assumption 3with C∗∈(0, 2)in (2), the minimax difference in the revenues is bounded from below as RU nFUn−2/3. Theorem 5states that there is an inevitable deficiency, (n−2/3),intherevenue from any data-based uniform pricing strategy relative to the revenue from the truedistribution optimal uniform pricing strategy by taking the supremum over FU. Recalling Corollary 1on the convergence rate O(n−2/3)of the 1-market ERM strategy, despite its simplicity, Theorem 5implies that the revenue from this algorithm achieves the optimal rate of convergence (as a function of n) to the revenue from the true-distribution optimal uniform pricing strategy uniformly over FU. 4.3 Sketches of the proofs To facilitate understanding, we start with a preliminary of the proof for Theorem 3before laying out the preliminaries for Theorems 4and 5. 4.3.1 Preliminary of the proof for Theorem 3For Theorem 3, we first show that the minimax difference in price at a given covariate value x0is bounded from below as follows: inf ˇ pD∈ˇ D sup FY,X∈F EFY,Xˇ pD(x0;data)−p∗ D(x0;FY,X)n−1/4,x0∈(0, 1).(6) Using Taylor expansion type of arguments and condition (2), we can relate the revenue difference to the minimax squared difference in price at x0: RD n(x0;F)inf ˇ pD∈ˇ D sup FY,X∈F EFY,Xˇ pD(x0;data)−p∗ D(x0;FY,X)2 ≥inf ˇ pD∈ˇ D sup FY,X∈FEFY,Xˇ pD(x0;data)−p∗ D(x0;FY,X)2 where the last line follows from the Jensen’s inequality. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
318 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) The derivation of the lower bound (6) can be reduced to a binary classification problem. In a binary classification problem, we have two distributions F1 Y,X,F2 Y,X∈Fwhose optimal prices are separated by some number 2ε;thatis, p∗ Dx0;Fj Y,X−p∗ Dx0;Fj Y,X≥2ε,j,j∈{1, 2}.(7) A binary classification rule uses the data to decide whether the true distribution is F1 Y,X or F2 Y,X. To relate the binary classification problem to the pricing problem, note that, given any pricing function ˇ pD, we can use it to distinguish between F1 Y,Xand F2 Y,Xin the following way. Define the binary classification rule ψ(data)=argmin j∈{1,2}p∗ Dx0;Fj Y,X−ˇ pD(x0;data). We claim that when the underlying distribution is Fj Y,Xthe decision rule ψis correct if p∗ Dx0;Fj Y,X−ˇ pD(x0;data)<ε.(8) To see this, note that by the triangle inequality, (7)and(8) guarantee that p∗ Dx0;Fj Y,X−ˇ pD(x0;data) ≥p∗ Dx0;Fj Y,X−p∗ Dx0;Fj Y,X−p∗ Dx0;Fj Y,X−ˇ pD(x0;data) >2ε−ε=ε,wherej=j,j,j∈{1, 2}. This implies that PFj Y,Xψ(data)=j≤PFj Y,Xp∗ Dx0;Fj Y,X−ˇ pD(x0;data)≥ε,j=1, 2. Therefore, we can upper bound the average probability of mistakes in the binary classification problem as 1 2PF1 Y,Xψ(data)=1+1 2PF2 Y,Xψ(data)=2 ≤1 2PF1 Y,Xp∗ Dx0;F1 Y,X−ˇ pD(x0;data)≥ε +1 2PF2 Y,Xp∗ Dx0;F2 Y,X−ˇ pD(x0;data)≥ε ≤sup FY,X∈F PFY,Xp∗ D(x0;FY,X)−ˇ pD(x0;data)≥ε. By the Markov inequality, we have sup FY,X∈F Eˇ pD(x0;data)−p∗ D(x0;FY,X) ≥εsup FY,X∈F Pˇ pD(x0;data)−p∗ D(x0;FY,X)≥ε 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 319 ≥ε1 2PF1 Y,Xψ(data)=1+1 2PF2 Y,Xψ(data)=2. Finally, we take the infimum over all pricing strategies on the left-hand side (LHS), and the infimum over the induced set of binary decisions on the right-hand side (RHS). This leads to inf ˇ pD∈ˇ D sup FY,X∈F Eˇ pD(x0;data)−p∗ D(x0;FY,X) ≥εinf ψ1 2PF1 Y,Xψ(data)=1+1 2PF2 Y,Xψ(data)=2.(9) The RHS of the above inequality consists of two parts: (1) ε, related to the separation between two optimal prices, and (2) the average probability of making a mistake in distinguishing the two distributions. To obtain a meaningful bound, we want to find two distributions F1 Y,Xand F2 Y,Xthat are close to each other (hard to distinguish) but their optimal prices are sufficiently separated. We leave the details of the construction of such distributions to the proof of Theorem 3giveninAppendixB. 4.3.2 Preliminary of the proof for Theorem 4For Theorem 4, we first show that the minimax (unweighted) L2-distance in price is bounded from below as follows: inf ˇ pD∈ˇ D sup FY,X∈F E ˇ pD(data)−p∗ D(FY,X) 2 2n−1/2 where ˇ pD(data)−p∗ D(FY,X) 2 2=1 0ˇ pD(x;data)−p∗ D(x;FY,X)2dx. Using Taylor expansion type of arguments and condition (2), we can relate the difference in the expected revenues to the minimax (unweighted) L2-distance in price: RD n(F)inf ˇ pD∈ˇ D sup FY,X∈F EFY,X ˇ pD(data)−p∗ D(FY,X) 2 2 where the expectation EFY,Xis taken with respect to data ∼FY,X. The object above concerns the entire pricing function p∗ D(·;FY,X).Asaresult, bounding the RHS of the above inequality is more complicated than the previous one (6). In particular, we consider a multiple classification problem that tries to distinguish among Mdistributions, where Mis a function of the sample size n. Similar as before, we want the optimal prices of these Mdistributions to be sufficiently separated. Similar derivations show that the lower bound of the revenue problem can be reduced to that of a multiple classification problem: inf ˇ pD∈ˇ D sup FY,X∈F EFY,X ˇ pD(data)−p∗ D(FY,X) 2 2≥ε2inf ψ 1 M M j=1 PFj Y,Xψ(data)=j, (10) 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
320 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) where the infimum infψis taken over the set of all multiple decisions (with Mchoices). To proceed, we apply the Fano’s inequality from information theory (Cover and Thomas (2005)). Fano’s inequality gives a lower bound on the average probability of mistakes:9 1 M M j=1 PFj Y,Xψ(data)=j≥1− M j,j=1 KLFj Y,XFj Y,X/M2+log2 logM, (11) where KL(··)denotes the Kullback–Leibler (KL) divergence between two distributions: KL(F1F2)≡f1(y,x)log f1(y,x) f2(y,x)dy dx. To obtain a sharp bound based on the multiple classification problem, we want to find a set of distributions (where the cardinality Mofthesetislargeenough)thatareclose enough to each other (small enough pairwise KL divergence) but their optimal prices are sufficiently separated. We leave the detailed proof to Appendix B. Our proof is based on a delicate construction of conditional densities along with an application of the Gilbert–Varshamov lemma from coding theory. Specifically, we use the distribution Y,X∼U[0, 1]with Xindependent of Yas the benchmark distribution and construct its perturbed versions with some correlation. 4.3.3 Preliminary of the proof for Theorem 5Relative to the proofs in the case of 3PD, the proofs for the priceand revenue-deficiency lower bounds in uniform pricing are simpler. We first show that the minimax difference in price is bounded from below as follows: inf ˇ pU∈ˇ U sup FY∈FU EFYˇ pU(dataY)−p∗ Un−1/3. (12) As previously, we can relate the revenue difference to the minimax squared difference in price: RU nFUinf ˇ pU∈ˇ U sup FY∈FU EFYˇ pU(dataY)−p∗ U2 ≥inf ˇ pU∈ˇ U sup FY∈FUEFYˇ pU(dataY)−p∗ U2 where the last line follows from the Jensen’s inequlity. The derivation of (12)onlyrequires constructing two distributions, similar to the approach discussed in Section 4.3.1. 5. Numerical evidence Sections 3and 4establish that the K-markets ERM strategy achieves the optimal rates of convergence in revenue uniformly over a class of distributions. In this section, we 9We do not present the Fano’s inequality in its standard form as in Cover and Thomas (2005). Instead, we use a version from Wainwright (2019) that is more convenient for our purposes. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 321 turn to specific distributions and study the revenue performance of our K-markets ERM strategies in these cases. We present numerical evidence that supports the implications of our theoretical results. Specifically, we calculate the revenues of the pricing strategies proposed in Section 3using real-world and simulated data. We describe the data in detail below. Data For the empirical study, we use an eBay auction data set (Jank and Shmueli (2010)). Because eBay uses a sealed-bid second-price auction format, the bid of each participant can serve as a proxy for an individual valuation of the object. In particular, we use the data on 194 7-day auctions for the new Palm Pilot M515 PDAs.10 The data has 3832 observations at the bid level, and each observation includes an auction id, a bid amount, a bidder id, and a bidder rating. Some bidders appear in the data set several times because either they revised their bid during an auction or participated in several auctions. To be consistent with our assumption of independent sampling, we analyze the data at the bidder level and use the highest bid of each bidder across all auctions she participated in as the one representing her valuation. This leaves 1203 observations from which we draw samples of various sizes. For Yi, we use the bid (as described above) of bidder inormalized to [0, 1].ForXiin the 3PD case, we use bidder i’s rating on eBay, which indicates the number of times sellers left feedback after a transaction with i. For the simulation study, we let the marginal distribution of Xbe uniform on [0, 1] and the CDF of Yconditional on X=xbe FY|X(y|x)=yx+1. (13) Implementation For each type of data, we calculate (a Monte-Carlo approximation of) the expected revenue generated by the uniform ERM and the K-markets ERM strategies for various sample sizes as follows. First, fix nand K. Then draw a sample {Yi,Xi}n i=1 and, for each k=1, ,K,let marketk≡{Yi:Xi∈Ik},ˆ Fk(t)≡|Yi∈marketk:Yi≤t| |marketk|. Then the empirical optimal price in the kth market is given by ˆ pD,k≡argmax y∈[0,1] y1−ˆ Fk(y)=argmax y∈marketk y1−ˆ Fk(y), where the second equality holds because ˆ Fkis a step function. Note that the uniform ERM strategy simply corresponds to the 1-market ERM strategy. When K>1anda drawn sample results in empty markets that contain no observations, we set the prices in those markets to one. Finally, we compute the revenue deficiency for the uniform ERM and K-markets ERM strategies (under Kn1/4). 10Jank and Shmueli (2010) also provide data on Cartier wristwatches, Swarovski beads, and Xbox game consoles, but each of these data sets may pool various configurations or models of these products categories. Thus, we choose the data on the Palm Pilot M515 to minimize such variations. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
322 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Figure 1. Revenue under uniform and K-markets ERM strategies. Numerical findings Figure 1plots the expected revenue generated by the K-markets ERM strategy for K∈{1, ,5 }as a function of the sample size n(with K=1 corresponding to the uniform ERM strategy). To facilitate the exposition, we use a logarithmic scale for the n-axis. For both types of data, one can see that for sufficiently small n,theKmarkets revenue is decreasing in K.Asngrows, the performance of higher Kimproves faster than that of lower K, and for sufficiently large n,theK-markets revenue overtakes that with any lower K. This finding can be explained by the bound (K/n)2/3+1/K2 in Theorem 1(ii), which implies that higher K(more discrimination) approximates the revenue generated by the FY,X-optimum better but incurs a larger “variance.” When the sample size is small, a lower Kcan indeed be more beneficial. Figure 1also suggests that, even if Xcontains useful information about Y, the uniform ERM strategy may be revenue superior to any K(>1)-markets ERM strategy when nis sufficiently small. Recall from Theorem 1that the bound (K/n)2/3+1/K2is minimized at K=n1/4,whichgivesn−1/2, the optimal rate of convergence to the revenue generated by the FY,X-optimal 3PD strategy. This convergence rate is slower than n−2/3, the optimal rate of convergence to the revenue generated by the FY-optimal uniform pricing strategy (cf. Corollary 1). The slower convergence of the rate-optimal K-markets ERM strategy can potentially dominate the revenue gain from price discrimination over without discrimination for small n. Figure 2illustrates the difference in the convergence rates of the uniform ERM and the K-markets ERM strategies to their respective theoretical benchmarks. In particular, we set K=1 5n1/4for the simulation study and K=max{1, 2n1/4−7}for the empirical study. As predicted by the rate n−1/2in Theorem 1and the rate n−2/3in Corollary 1, the revenue from the uniform ERM strategy is converging to the revenue from the FY-optimal uniform pricing strategy faster than the K-markets revenue to the revenue from the FY,X-optimal 3PD strategy. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 323 Figure 2. Data-based revenue deficiency under uniform and K-markets ERM strategies (with Kn1/4). Figure 3exhibits the revenue under the K-markets ERM strategy for K=1, ,5and n=2, ,10 5,inthecasewhereXand Yare uniform on [0, 1]and independent of each other. Not surprisingly, there is no benefit from price discrimination for revenue. Figure 3. Uniform and K-marketsrevenueforthecaseofXand Yuniform on [0, 1]and independent of each other. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
324 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) 6. Discussions Recall that p∗ Dis the true-distribution optimal 3PD strategy and ˆ pDis the K-markets ERM strategy with K=(n1/4)giving the best trade-off between the “variance” and approximation error as shown in Theorem 1;p∗ Uis the true-distribution optimal uniform pricing strategy and ˆ pUis the uniform ERM strategy. We can decompose the difference between the expected revenues generated respectively from ˆ pDand ˆ pUas follows: ER(ˆ pD)−ER(ˆ pU)=−Rp∗ D−ER(ˆ pD) A1 +Rp∗ D−Rp∗ U A2 +Rp∗ U−ER(ˆ pU) A3 . The first term A1=(n−1/2)under a worst-case distribution FY,X∈F,andthethird term A3=O(n−2/3)under FY, the marginal of FY,X.ThesecondtermA2=(1)when Xcontains sufficient information about the valuation Y. Then a sufficient condition for ˆ pDto be revenue superior to ˆ pUis that n→∞. In theory, this claim can be proved with the upper bounds in Section 3and a different construction in the derivations of the lower bounds. Particularly, this new construction would first find a density fY,Xsuch that the revenue generated by the corresponding fY,X-optimal 3PD strategy is well separated from the revenue generated by the optimal uniform pricing strategy associated with fY, and then build a large enough class of perturbed versions of fY,X; finally, we would bound the separation between the optimal prices associated with these densities, in a similar fashion as what is done in Appendix B. In the paper, to make the analysis tractable, we choose the distribution Y,X∼U[0, 1]with Xindependent of Yas the benchmark distribution and construct its perturbed versions with some correlation. A challenging open question is, can the condition on nbe weakened to some finite number and if so, when? To answer this question, we would have to derive the universal constants in our bounds in meaningful forms. Unfortunately, due to the complexity of our problem, this exercise is infeasible under the existing techniques from mathematical statistics, probability theory, and information theory. Our results suggest that it is more beneficial to engage in sample-based uniform pricing when Xis independent of Y.11 The fundamental reason lies in the proofs for Theorems 3and 4:unlessn=∞, no strategies that exploit {(Yi,Xi),1≤i≤n}are able to distinguish with certainty the distribution Y,X∼U[0, 1]with Xindependent of Y from its perturbed versions with some correlation (see the detailed constructions in Appendix B). The curse of dimensionality from exploiting the covariate Xmakes the convergence of 3PD strategies based on {(Yi,Xi),1≤i≤n}slower than that of the uniform pricing strategies based on {Yi,1≤i≤n}. Our upper and lower bounds together suggest the following possibility: even when the covariate Xcontains useful information about the valuation Y,theK-markets ERM strategy can be revenue inferior to the uniform ERM strategy in finite samples, due to the curse of dimensionality and slower convergence of the K-markets ERM strategy to its true-distribution optimal counterpart (and hence, a more stringent growth requirement of the sample size). Indeed, the numerical evidence in Section 5confirms this possibility. But such an implication should be taken with caution in small samples. 11The information of independence is unknown to the seller. She can statistically test for the independence of Yand Xfrom the data but any such tests would suffer from Type I and Type II errors. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 325 Small sample complication Given the pattern observed in our numerical studies, one might conjecture the following: there exists some ¯ n>1 such that when n< ¯ n, the uniform ERM is always revenue-superior to the K-markets ERM (with K>1). In what follows, we explain why this conjecture may not hold. Specifically, in our language, Babaioff et al. (2018) construct a distribution FYsuch that the uniform ERM revenue under n=2 is strictly smaller than the uniform ERM revenue under n=1. This seemingly counterintuitive result highlights the difficulty of establishing general comparative results with very small sample size. We now argue that this construction also sheds some light on the comparison of the revenue performance of the K-markets ERM strategy with K=1vs.K=2inthecaseofn=2. To make this connection, we take Xto be uniform on [0, 1]and independent of Y, and assume that in the case K=2, when one of the markets is empty, the price for this market is set at the same level as for the other market. Then, if K=2 and both markets are nonempty, the revenue in each market equals the 1-market ERM revenue under n=1. Otherwise, if both observations are in the same market, then the revenue equals the 1-market ERM revenue under n=2. Therefore, the expected 2-markets ERM revenue with n=2 is the average of the 1-market ERM revenue under n=1andn=2, and hence, strictly higher than the 1-market ERM revenue with n=2 for a distribution FY exhibiting the property discussed in Babaioff et al. (2018). More formally, let RK,ndenote the expected revenue of the K-markets ERM strategy with a sample of size n.Then R2,2 =Edatan=2∼FY,XRˆ pD(data),FY,X =1 2Edatan=2∼FY,X|I1=∅or I2=∅Rˆ pD(data),FY,X +1 2Edatan=2∼FY,X|I1=∅and I2=∅Rˆ pD(data),FY,X =1 2R1,2 +1 2R1,1. Therefore, R1,1 >R 1,2 implies R2,2 >R 1,2. Finally, we add the caveat that the construction in Babaioff et al. (2018) is based on an atomless approximation of the censored equal-revenue distribution FY(y)=1−1/y, y∈[1, ∞), which has a discontinuous density. However, it is straightforward to verify that the same property holds for the equal-revenue distribution truncated at any y>4, which has a Lipschitz continuous and differentiable density. Moreover, the equal revenue distribution truncated at yand translated to the left by t>1/y (so that the support is [1−t,y−t]) also has a Lipschitz continuous and differentiable density, the interior optimal price (in line with our assumptions), and satisfies the Babaioff et al. (2018)property, e.g., for y=4, t=1/2. An open problem To conclude, we would like to propose a challenging open problem: Do there exist some 3 ≤n<¯ n<∞such that for any n∈[n,¯ n]and distribution in F,the K-markets ERM strategy (for any K>1) is always revenue-inferior to the uniform ERM strategy? 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
326 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Appendix A: Proofs for upper bounds To facilitate the presentation, we first give the proof for Corollary 1. Proof of Corollary 1.Denoteκ≡infp∈[0,1]|R(p)|/2>0. By Taylor expansion, for any p, Rp∗ U−R(p)≥κp−p∗ U2. Denote ˆ R(p)≡p(1−ˆ F(p)). Combining the inequality above with the basic inequality (i.e., ˆ R(ˆ pU)≥ˆ R(p∗ U)), we have κˆ pU−p∗ U2≤Rp∗ U−R(ˆ pU)≤Rp∗ U−ˆ Rp∗ U−R(ˆ pU)−ˆ R(ˆ pU). (14) For δ∈(0, p∗ U], define Gδ≡y→p1{y≥p}−p∗ U1y≥p∗:p∈p∗ U−δ,p∗ U+δ and Gδ(y)≡⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 0, if y<p ∗ U−δ, p∗ U,ifp∗ U−δ≤y≤p∗ U+δ, δ,ify>p ∗ U+δ. Then Gδis an envelope function of the class Gδ.TheL2(P)-norm of Gδis bounded by GδL2(P)=p∗ U2PY∈p∗ U−δ,p∗ U+δ+δ2PY>p ∗ U+δ1/2≤C√δ. As we argue in the proof of Lemma 6,Gδis a VC-subgraph class, so we have Esup g∈Gδ 1 n n i=1 g(Yi)−Eg(Yi)≤Cδ/n. (15) We derive the convergence rate of ˆ p−p∗via a peeling argument. Consider the following decomposition: Pn1/3ˆ pU−p∗ U>M=∞ j=M+1 P(n1/3ˆ pU−p∗ U∈(j−1, j]). For any j≥M+1, we have ˆ pU−p∗ U∈((j−1)n−1/3,jn−1/3] =ˆ pU−p∗ U>(j−1)n−1/3,ˆ pU−p∗ U≤jn−1/3 ⊂Rp∗ U−ˆ Rp∗ U−R(ˆ pU)−ˆ R(ˆ pU)≥κ(j−1)2n−2/3,ˆ pU−p∗ U≤jn−1/3 ⊂j,n≥κ(j−1)2n−2/3, 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 333 The integral on the last line can be decomposed based on the Kmarkets: E1 0ˆ pD(x;data)−p∗ D(x)fX(x)dx ≤ K k=1IkEˆ pD(x;data)−˜ pk+˜ pk−p∗ D(x)fX(x)dx = K k=1 E|ˆ pk−˜ pk|/K + K k=1Ik˜ pk−p∗ D(x)fX(x)dx (K/n)1/3+1/K +exp−nc2 1 8K2+logKn−1/4, where the last line follows from the proof of Theorem 1. For part (ii), since p∗ Uis a scalar, the welfare can be simplified to Wp∗ U,FY=p∗ U 0 yfY(y)dy. Then we have EWˆ pU(dataY),FY−Wp∗ U,FY=Eˆ pU(dataY) p∗ U yfY(y)dy ≤sup yyfY(y)Eˆ pU(dataY)−p∗ U n−1/3, wherewehaveusedCorollary1along with the fact that yfY(y)is nonnegative and bounded for y∈[0, 1]. Appendix B: Proofs for lower bounds Proof of Theorem 3.ForTheorem3, we use Lemma 4to prove the lower bound. Define ωD()≡sup F1,F2∈Fp∗ D(x0;F1)−p∗ D(x0;F2):H(F1F2)≤. By Lemma 4,wehave inf ˇ pD∈ˇ D sup FY,X∈F EFY,Xˇ pD(x0;data)−p∗ D(x0)≥1 8ωD1/(2√n). Therefore, we only need to find a lower bound for ωD. Based on the explanation in Section 4.3.1, we want to construct two distributions that are hard to distinguish but their optimal prices are well separated. We start by defining two perturbation functions. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
334 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Figure 4. Perturbation functions φYand φX. Let φYbe defined as φY(t)≡ ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ t+1, t∈[−1, 0], −t+1, t∈[0, 2], t−3, t∈[2, 3], 0, otherwise. (27) Notice that φYis Lipschitz continuous on R.LetφXbe defined as φX(t)≡⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ e−(4t−1)2/(1−(4t−1)2),t∈(0, 1/2), −e−(4t−3)2/(1−(4t−3)2),t∈(1/2, 1), 0, otherwise. Notice that φXis infinitely differentiable on R. We plot the two perturbation functions in Figure 4. Now we construct the two distributions. Let δ∈(0, 1/4)be a small number (that depends on n) to be specified later. Let abe any number in the interval (0, 4 −2C∗). Define the two conditional density functions of Ygiven Xas f1(y|x)≡1, f2(y|x)≡1+aδφYy−1/2 δφXx−x0 δ+1/4. (28) We let the marginal distribution fX(x)of Xbe the uniform distribution on [0, 1].Note that f1(y|x),f2(y|x),f1(y,x)=f1(y|x)fX(x),andf2(y,x)=f2(y|x)fX(x)are nonnegative everywhere, with integrals over their respective entire spaces all equaling to 1. The first task is to verify that the two distributions are indeed in the class Fκ.For C∗∈(0, 2), the first distribution is in Fby Lemma 2and the fact that Yis independent of X. Given any x∈[0, 1], we can treat the whole term aφX((x−x0)/δ +1/4)as the coefficient bin Lemma 3. Then the results of Lemma 3applies since |φX|≤1. In particular, the revenue function at xis twice-differentiable a.e., the absolute value of the 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 335 second-order partial derivative with respect to yis bounded, and is also bounded from below by C∗. The optimal price is an interior solution and is in the interior of a region on which the revenue function is twice differentiable. Lastly, the absolute value of the partial derivative of f2(y|x)with respect to xis bounded. This ensures that the quantity |∂ ∂x FY|X(y|x)+y∂ ∂x fY|X(y|x)|is bounded. Next, we want to derive the Hellinger distance between the two joint densities f1(y,x)=1, f2(y,x)=1+aδφYy−1/2 δφXx−x0 δ+1/4. Let (t)≡√1+t. Its second-order derivate is bounded when |t|<1/2; that is, sup |t|<1/2(t)<C. We use Hto denote the Hellinger distance: H(f1f2)2≡1 0f1(y)−f2(y)2dy. The Hellinger distance can be bounded as H2(f1f2)/2=1−1 01 0 aδφYy−1/2 δφXx−x0 δ+1/4dy dx =1 01 0 (0)−aδφYy−1/2 δφXx−x0 δ+1/4dy dx ≤−a(0)δ1 01 0 φYy−1/2 δφXx−x0 δ+1/4dy dx +a2Cδ21 01 0 φ2 Yy−1/2 δφ2 Xx−x0 δ+1/4dy dx, where we have applied the second-order Taylor expansion to obtain the last inequality. By the change of variables u=(y−1/2)/δ and v=(x−x0)/δ +1/4, for sufficiently small δ∈(0, 1/2], 1 01 0 φYy−1/2 δφXx−x0 δ+1/4dy dx =δ21 −1 φY(u)du1 0 φX(v)dv =0, (29) and 1 01 0 φ2 Yy−1/2 δφ2 Xx−x0 δ+1/4dy dx =δ21 −1 φ2 Y(u)du1 0 φ2 X(v)dv ≤Cδ2. Therefore, the Hellinger distance is bounded as H2(f1f2)δ4. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
336 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Now we take δsuch that δ41/n.Notethat(29)holdswhenδ>0 is small enough such that δ∈(0, 1/2],1/4−x0/δ ≤0, and (1−x0)/δ +1/4≥1; that is, when x0n1/4≥cand (1−x0)n1/4≥c for positive universal constants cand c (independent of nand x0). This ensures that H2(f1f2)1/n. Then from Lemma 4, we know that inf ˇ pD∈ˇ D sup FY,X∈F EFY,Xˇ pD(x0;data)−p∗ D(x0)n−1/4,x0∈(0, 1). For bounding the revenue, recall that the revenue achieved at the price pand covariate value x0is r(p,x0)=maxpp(1−FY|X(p|x0)). By Lemma 1,wehave rp∗ D(x0)−rˇ pD(x0;data)≥C∗ 2p∗ D(x0)−ˇ pD(x0;data)2. As a result, we have inf ˇ pD∈ˇ D sup FY,X∈F Erp∗ D,x0−rˇ pD(data),x0 ≥inf ˇ pD∈ˇ D sup FY,X∈F EC∗ 2p∗ D(x0)−ˇ pD(x0;data)2 ≥inf ˇ pD∈ˇ D sup FY,X∈F C∗ 2Ep∗ D(x0)−ˇ pD(x0;data)2n−1/2. This proves Theorem 3. Proof of Theorem 4.ToproveTheorem4, we follow the explanation in Section 4.3.2 and use the Fano’s inequality to bound the probability of mistakes in the multiple classification problem. Before solving the revenue problem, we first study the lower bound for the L2-distance of pricing functions. For two pricing functions p1and p2, we define the (unweighted) L2-distance as p1−p22≡1 0p1(x)−p2(x)2dx1/2 . In part (i), we defined the perturbation on the Xdimension at a fixed point x0.Nowwe want to define a large set of perturbed distributions. Each of these distributions is perturbed in a small interval on the Xdimension. Let m≥8 be a large number (depending on n) that we specify later. Let α∈{0, 1}mbe a vector of length m;thatis, α≡(α1,,αm),whereαj∈{0, 1},j=1, ,m. We construct a set of conditional density functions indexed by α: fα Y|X(y|x)≡1+a m m j=1 αjφYm(y−1/2)φXmx −(j−1). The marginal distribution of Xis taken to be the uniform distribution on [0, 1], i.e., fX≡ 1[0,1]. We denote the joint distribution by fα Y,X≡fα Y|XfX. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 337 We briefly describe this construction of the conditional density. The unit interval [0, 1]is divided equally into msubintervals: Ij≡(j−1)/m,j/m,j=1, ,m. For x∈Ij,ifαj=0, then the conditional density is 1. If αj=1, then the conditional density fα Y|X(y|x)≡1+a mφYm(y−1/2)φXmx −(j−1),x∈Ij. By treating 1/m as the scalar δin part (i), we can see that, for mlarge enough, each fα Y,X belongs to the set Fκ. From the set {fα Y,X:α∈{0, 1}m}, we want to pick out a large enough subset of distributions whose optimal price functions are well separated. For this purpose, we use the Gilbert–Varshamov bound (Lemma 2.9, Chapter 2, Tsybakov (2009)). The Gilbert– Varshamov bound states that for m≥8, there exists a subset A⊂{0, 1}mwith cardinality M≡|A|≥2m/8, and the pairwise rescaled Hamming distance between elements in this set is greater than 1/8. That is, 1 m m j=1 1αj=α j≥1 8,foranyα,α∈A. Applying the Gilbert–Varshamov bound, we can show that for α,α∈A, the optimal pricing functions of fα Y,Xand fα Y,Xare well separated. Let pαbe the pricing function associated with fα Y,X;thatis, pα(x)≡argmax p∈[0,1] p1−Fα Y|X(p|x), where Fα Y|X(y|x)is the corresponding conditional cumulative distribution function. Note that α,α∈Adiffer in at least m/8 positions. This means that fα Y|Xand fα Y|Xdiffer in m/8 intervals. Suppose that Ijis such an interval, where αj=0andα j=1. We restrict our attention to a subset of this interval: ˜ Ij≡1 6m+j−1 m,1 3m+j−1 m⊂Ij. When x∈˜ Ij,wehave mx −(j−1)∈[1/6, 1/3]=⇒ φXmx −(j−1)∈φX(0),φX(1/2). (30) By Lemma 3(where b=aφX(mx −(j−1)) >0, δ=1/m), the choice a∈(0, 4 −2κ),and the fact (30), if we fix x∈˜ Ij,thenpα(x)=1/2 while pα(x)≤1/2−c mφXmx −(j−1)≤1/2−cφX(1/6) m,x∈˜ Ij, 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
338 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) where c>0 is a universal constant that does not depend on n.12 This implies that pα(x)−pα(x)1 m,x∈˜ Ij. Therefore, on the interval Ij, the separation between pαand pαis lower bounded as Ijpα(x)−pα(x)2dx ˜ Ij 1/m2dx =1 6m×1 m21/m3. By the Gilbert–Varshamov bound, there are at least m/8 such intervals. Therefore, we can lower bound the total separation by p1−p22m/8×1/m31/21/m. Next, we want to compute the KL divergence between fα Y,Xand fα Y,X. Note that the term φX(mx −(j−1)) is nonzero only when x∈Ij. The KL divergence can therefore be treated as a sum of mintegrals: KLfα Y,Xfα Y,X=1 01 0 fα Y,X(y,x)log fα Y,X fα Y,X dy dx = m j=1 Ej, where Ej≡Ij1 01+a mαjφYm(y−1/2)φXmx −(j−1) ×log 1+a mαjφYm(y−1/2)φXmx −(j−1) 1+a mα jφYm(y−1/2)φXmx −(j−1)dy dx. Notice that when αj=αj,Ej=0. Therefore, we only need to consider the j’s where αj=α j.Denote1(t)=−log(1+t)and 2(t)=(1+t)log(1+t).ThenwecanwriteEj as Ej=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ Ij1 0 1a mφYm(y−1/2)φXmx −(j−1)dy dx,ifαj=0, α j=1, Ij1 0 2a mφYm(y−1/2)φXmx −(j−1)dy dx,ifαj=1, α j=0. By the second-order Taylor expansion at zero, we have 1(t)=−t+1 21+t2t2, 12For example, ccan be equal to a/8 according to Lemma 3. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 339 for some tbetween 0 and t.When|t|≤1/4,13 we have 1(t)≤−t+Ct2, for some universal constant C>0. Similarly, we can show that 2(t)≤t+Ct2. Applying these inequalities to Ej,wehave Ej≤±Ij1 0 a mφYm(y−1/2)φXmx −(j−1)dy dx +CIj1 0 a2 m2φ2 Ym(y−1/2)φ2 Xmx −(j−1)dy dx. Similar to the derivation in part (i), we know that the first term on the RHS is zero. For the second term, we can apply change of variables u=m(y−1/2)and v=mx −(j−1) and obtain that Ij1 0 φ2 Ym(y−1/2)φ2 Xmx −(j−1)dy dx =1 m21 0 φ2 X(v)dv3 −1 φ2 Y(u)du ≤C m2 for some universal constant C>0. Putting the results results together, we know that Ej≤C m4for all j. Since there are mintervals, we can bound the KL divergence by KLfα Y,Xfα Y,X= m j=1 Ej1 m3. This is the KL distance for a single observation. For the entire data set with ni.i.d. observations, the KL divergence is upper bounded by Cn/m3. Lastly, we can summarize our results into the Fano inequality presented in Lemma 5. We have inf ˇ pD∈ˇ D sup FY,X∈F E ˇ pD(data)−p∗ D 2 2≥C1 m21−C2n/m3+log2 log2m/8 ≥C1 m21−C2n/m3+log2 C3m. By choosing m=c0n1/4for a sufficiently large universal constant c0>0, we can make the factor (1−C2n/m3+log2 C3m)stay above, say, 1/2. Then we have inf ˇ pD∈ˇ D sup FY,X∈F E ˇ pD(data)−p∗ D 2 21 m2n−1/2. 13Later we show that mis chosen to be c0n1/4where c0>0 is a universal constant. As a result, |t|≤1/4is guaranteed as long as c0is sufficiently large. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
340 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) So far we have derived the lower bound for the L2-distance of pricing. Moving onto the revenue problem, recall that the revenue achieved at the price pand covariate value xis r(p,x)=maxpp(1−FY|X(p|x)). By Lemma 1,wehave rp∗ D,x−rˇ pD(data),x≥C∗ 2p∗ D(x)−ˇ pD(x;data)2. Since fXis bounded away from zero, we have inf ˇ pD∈ˇ D sup FY,X∈F ERp∗ D−R(ˇ pD) =inf ˇ pD∈ˇ D sup FY,X∈F E1 0rp∗ D,x−r(ˇ pD,x)fX(x)dx ≥inf ˇ pD∈ˇ D sup FY,X∈F EC∗ 2inf x∈[0,1]fX(x)1 0p∗ D(x)−ˇ pD(x;data)2dxn−1/2. Proof of Theorem 5. We use Lemma 4to prove the lower bound for Theorem 5.Define ωU()≡sup F1,F2∈FUp∗ U(F1)−p∗ U(F2):H(F1F2)≤. Then by Lemma 4,wehave inf ˇ pU∈ˇ U sup FY∈FU EFYˇ pU(dataY)−p∗ U≥1 8ωU1/(2√n). Therefore, we only need to find a lower bound for ωU. The proof proceeds in three steps. In the first step, we construct two distributions and compute the separation between their optimal prices. The second step bounds the Hellinger distance between these two distributions. The third step summarizes. Step 1. We construct two distribution functions. The first distribution is the uniform distribution on the unit interval [0, 1]. We denote this density function as f1(y)=1[0,1](y). The distribution function is F1(y)=yon the support [0, 1]. The revenue function under this distribution is R1(p)=p(1−p). The optimal price is p1=argmax p∈[0,1] R1(p)=argmax p∈[0,1] p−p2=1/2. The second distribution function is a small twist of the uniform distribution. We use the same perturbation function φYdefined in (27). 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 341 Figure 5. Density functions f1and f2. We apply a small perturbation to the uniform density. Let δ>0beasmallnumber (that depends on n) specified later. Let a∈(0, 4 −2C∗). The formula of the density f2is given by f2(y)≡1+aδφYy−1/2 δ= ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 1, if y∈[0, 1/2−δ), ay +1−a 2+aδ,ify∈[1/2−δ,1/2), −ay +1+a 2+aδ,ify∈[1/2, 1/2+2δ), ay +1−a 2−3aδ,ify∈[1/2+2δ,1/2+3δ), 1, if y∈[1/2+3δ,1 ]. We compare the two densities f1and f2in Figure 5. Denote the optimal price under f2by p2. By Lemma 3(ii), we have |p2−p1|≥aδ/8 when δis sufficiently small. Step 2. We want to bound the Hellinger distance H(F1F2). Define the function (t)=√1+t. Its second-order derivative is bounded when |t|<1/2; that is, sup |t|<1/2(t)≤√2 2. Since f1(y)=1, we have H(F1F2)2/2=1−1 0 aδφYy−1/2 δdy =1 0 (0)−aδφYy−1/2 δdy. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
342 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) By the second-order Taylor expansion, we have (0)−aδφYy−1/2 δ ≤−(0)aδφYy−1/2 δ+√2 4a2δ2φ2 Yy−1/2 δ. By the construction of φY,wehave 1 0 φYy−1/2 δdy =0. Bythechangeofvariablesu=(y−1/2)/δ,wehave 1 0 φ2 Yy−1/2 δdy =δR φ2 Y(u)du ≤4δ0 −1 (x+1)2dx =4 3δ. Combining these results together, we obtain a bound on the Hellinger distance H(F1F2)2≤2√2 3a2δ3. Step 3. By setting δ=c 0(3/8√2)1/3a−2/3n−1/3for c 0∈(0, 1), we can ensure that H(F1F2)≤1/(2√n). Previously, we assumed that aδ ≤1/2 for the second-order Taylor expansion. This is true if c 0is chosen to be sufficiently small. In this case, the separation between p1and p2is lower bounded as below: |p1−p2|≥aδ/8=c 0 163 √21/3a n1/3 . By Lemma 4,wehave inf ˇ pU∈ˇ U sup FY∈FU Eˇ pU(dataY)−p∗ U≥c 0 163 √21/3a n1/3 . Lastly,wewanttolowerboundtherevenue.ByLemma1,wehave RU nFU=inf ˇ pU∈ˇ U sup FY∈FU ERˇ pU(dataY),FY−Rp∗ U,FY ≥inf ˇ pU∈ˇ U sup FY∈FU EC∗ 2ˇ pU(dataY)−p∗ U2 ≥inf ˇ pU∈ˇ U sup FY∈FU C∗ 2Eˇ pU(dataY)−p∗ U2 1 n2/3 . 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 349 References Alexander, Kenneth S. (1987), “Rates of growth and sample moduli for weighted empirical processes indexed by sets.” Probability Theory and Related Fields, 75, 379–423. [0313] Allouah, Amine, Achraf Bahamou, and Omar Besbes (2022), “Pricing with samples.” Operations Research, 70, 1088–1104. [0307] Allouah, Amine, Achraf Bahamou, and Omar Besbes (2023), “Optimal pricing with a single point.” Management Science.[0307] Babaioff, Moshe, Yannai A. Gonczarowski, Yishay Mansour, and Shay Moran (2018), “Are two (samples) really better than one?” In Proceedings of the 2018 ACM Conference on Economics and Computation, 175. [0305,0307,0325] Balcan, Maria-Florina, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V. Vazirani (2014), “Learning economic parameters from revealed preferences.” In Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14–17, 2014. Proceedings 10, 338–353, Springer. [0306] Baliga, Sandeep and Rakesh Vohra (2003), “Market research and market design.” Advances in Theoretical Economics,3.[0307] Basu, Pathikrit and Federico Echenique (2020), “On the falsifiability and learnability of decision theories.” Theoretical Economics, 15, 1279–1305. [0306] Beigman, Eyal and Rakesh Vohra (2006), “Learning from revealed preference.” In Proceedings of the 7th ACM Conference on Electronic Commerce, 36–42. [0306] Bergemann, Dirk and Karl H. Schlag (2008), “Pricing without priors.” Journal of the European Economic Association, 6, 560–569. [0307] Bergemann, Dirk and Karl H. Schlag (2011), “Robust monopoly pricing.” Journal of Economic Theory, 146, 2527–2543. [0307] Bousquet, Olivier (2003), “Concentration inequalities for sub-additive functions using the entropy method.” In Stochastic Inequalities and Applications, 213–247, Springer. [0327] Carroll, Gabriel (2019), “Robustness in mechanism design and contracting.” Annual Review of Economics, 11, 139–166. [0307] Chambers, Christopher P., Federico Echenique, and Nicolas S. Lambert (2021), “Recovering preferences from finite data.” Econometrica, 89, 1633–1664. [0306] Chambers, Christopher P., Federico Echenique, and Nicolas S. Lambert (2023), “Recovering utility.” arXiv preprint arXiv:2301.11492.[0306] Cole, Richard and Tim Roughgarden (2014), “The sample complexity of revenue maximization.” In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, 243–252. [0307] 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
350 Xie, Zhu, and Shishkin Theoretical Economics 20 (2025) Cover, Thomas M. and Joy A. Thomas (2005), Elements of Information Theory.JohnWiley & Sons, Ltd. [0320] Crémer, Jacques and Richard P. McLean (1988), “Full extraction of the surplus in Bayesian and dominant strategy auctions.” Econometrica: Journal of the Econometric Society, 1247–1257. [0304] Devanur, Nikhil R., Zhiyi Huang, and Christos-Alexandros Psomas (2016), “The sample complexity of auctions with side information.” In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, 426–439. [0308] Dhangwatnotai, Peerapong, Tim Roughgarden, and Qiqi Yan (2015), “Revenue maximization with a single sample.” Games and Economic Behavior, 91, 318–333. [0307] Folland, Gerald B. (1999), Real Analysis: Modern Techniques and Their Applications,second edition, volume 40. John Wiley & Sons, New York, NY. [0343] Fu, Hu, Nima Haghpanah, Jason Hartline, and Robert Kleinberg (2021), “Full surplus extraction from samples.” Journal of Economic Theory, 193, 105230. [0307] Fu, Hu, Nicole Immorlica, Brendan Lucier, and Philipp Strack (2015), “Randomization beats second price as a prior-independent auction.” In Proceedings of the Sixteenth ACM Conference on Economics and Computation, 323. [0307] Giné, Evarist and Richard Nickl (2015), Mathematical Foundations of InfiniteDimensional Statistical Models. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press. [0348] Goldberg, V. Andrew, Jason D. Hartline, Anna R. Karlin, Michael Saks, and Andrew Wright (2006), “Competitive auctions.” Games and Economic Behavior, 55, 242–269. [0307] Gonçalves, Duarte and Bruno A. Furtado (2024), “Statistical mechanism design: Robust pricing, estimation, and inference.” arXiv preprint arXiv:2405.17178.[0307] Guo, Chenghao, Zhiyi Huang, and Xinzhi Zhang (2019), “Settling the sample complexity of single-parameter revenue maximization.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 662–673. [0307] Hartmann, Wesley, Harikesh S. Nair, and Sridhar Narayanan (2011), “Identifying causal marketing mix effects using a regression discontinuity design.” Marketing Science, 30, 1079–1097. [0304] Hirano, Keisuke and Jack R. Porter (2003), “Asymptotic efficiency in parametric structural models with parameter-dependent support.” Econometrica, 71, 1307–1338. [0308] Huang, Zhiyi, Yishay Mansour, and Tim Roughgarden (2018), “Making the most of your samples.” SIAM Journal on Computing, 47, 651–674. [0307,0316] Jank, Wolfgang and Galit Shmueli (2010), Modeling Online Auctions. John Wiley & Sons. [0321] 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License
Theoretical Economics 20 (2025) Limitations of data-based price discrimination 351 Kolmogorov, Andrei Nikolaevich, and Vladimir Mikhailovich Tikhomirov (1959), “εentropy and ε-capacity of sets in function spaces.” Uspekhi Matematicheskikh Nauk, 14, 3–86. [0306,0317] Myerson, Roger B. (1981), “Optimal auction design.” Mathematics of Operations Research, 6, 58–73. [0310] Segal, Ilya (2003), “Optimal pricing mechanisms with unknown demand.” American Economic Review, 93, 509–529. [0307] Talagrand, Michel (1996), “New concentration inequalities in product spaces.” Inventiones Mathematicae, 126, 505–563. [0327] Tsybakov, Alexandre B. (2009), Introduction to Nonparametric Estimation, first edition, Springer Series in Statistics. Springer, New York, NY. [0337] van de Geer, Sara A. (2000), Empirical Processes in M-Estimation, volume 6. Cambridge University Press. [0313] van der Vaart, Aad W. and Jon A. Wellner (1996), Weak Convergence and Empirical Processes. Springer, New York, NY. [0313,0348] Wainwright, Martin J. (2019), High-Dimensional Statistics: A Non-Asymptotic Viewpoint, volume 48. Cambridge University Press. [0306,0320,0347] Zhang, Hanrui and Vincent Conitzer (2020), “Learning the valuations of a k-demand agent.” In International Conference on Machine Learning, PMLR, 11066–11075. [0306] Co-editor Rakesh Vohra handled this manuscript. Manuscript received 18 October, 2023; final version accepted 12 July, 2024; available online 30 July, 2024. 15557561, 2025, 1, Downloaded from https://onlinelibrary.wiley.com/doi/10.3982/TE5916 by ZBW Kiel - Hamburg (German National Library of Economics), Wiley Online Library on [04/07/2025]. See the Terms and Conditions (https://onlinelibrary.wiley.com/terms-and-conditions) on Wiley Online Library for rules of use; OA articles are governed by the applicable Creative Commons License