Data-based price discrimination: information theoretic limitations and a
  minimax optimal strategy
  This paper studies the gap between the classical pricing theory and the
data-based pricing theory. We focus on the problem of price discrimination with
a continuum of buyer types based on a finite sample of observations. Our first
set of results provides sharp lower bounds in the worst-case scenario for the
discrepancy between any data-based pricing strategies and the theoretical
optimal third-degree price discrimination (3PD) strategy (respectively, uniform
pricing strategy) derived from the distribution (where the sample is drawn)
ranging over a large class of distributions. Consequently, there is an
inevitable gap between revenues based on any data-based pricing strategy and
the revenue based on the theoretical optimal 3PD (respectively, uniform
pricing) strategy. We then propose easy-to-implement data-based 3PD and uniform
pricing strategies and show each strategy is minimax optimal in the sense that
the gap between their respective revenue and the revenue based on the
theoretical optimal 3PD (respectively, uniform pricing) strategy matches our
worst-case lower bounds up to constant factors (that are independent of the
sample size $n$). We show that 3PD strategies are revenue superior to uniform
pricing strategies if and only if the sample size $n$ is large enough. In other
words, if $n$ is below a threshold, uniform pricing strategies are revenue
superior to 3PD strategies. We further provide upper bounds for the gaps
between the welfare generated by our minimax optimal 3PD (respectively, uniform
pricing) strategy and the welfare based on the theoretical optimal 3PD
(respectively, uniform pricing) strategy.
