A recent paper by Bergeman, Brooks and Morris (BBM) supposes a monopolist free to segment the market in any way she can (without worrying about arbitrage), and asks what is the achievable set of pairs of producer and consumer surplus? BBM gives a simple and satisfying answer to this question. This post attempts a short proof of their characterization.

A monopolist faces a market consisting of buyers with valuations ${\{v_1, v_2, \ldots, v_n\}}$. Order them so that ${v_1 < v_2 < \ldots < v_n}$. The number of buyers with valuation ${v_i}$ is ${d_i}$ and assume the buyers are divisble. A segmentation of the market is a partition of the buyers into upto ${n}$ markets with the property that the profit maximizing price in market ${j = 1, \ldots, n}$ is ${v_j}$. If we let ${x_{ij}}$ be the number of buyers with valuation ${v_i}$ in market ${j}$, then any segmentation is characterized by the following:

$\displaystyle \sum_{j=1}^{n}x_{ij} = d_i\,\, \forall i = 1, \ldots, n$

$\displaystyle v_j\sum_{r \geq j}x_{rj} \geq v_t \sum_{r \geq t}x_{rj}\,\, \forall j = 1, \ldots, n, \,\, \forall t \neq j$

$\displaystyle x_{ij} \geq 0\,\, \forall i,j$

Denote by ${X(d)}$ the set of feasible segmentations. Let ${P = \sum_{j=1}^{n}v_j\sum_{r= j}^nx_{rj}}$ be the profit earned by the monopolist under the segmentation ${x \in X(d)}$. The consumer surplus of buyers under the segmentation ${x \in X(d)}$ is ${C = \sum_{j=1}^{n}\sum_{r = j}^n[v_r-v_j]x_{rj}.}$

It is easy to see that ${P \leq \sum_{j=1}^nv_jd_j = \Pi_1(d)}$. The upper bound follows from the segmentation that assigns all buyers with valuation ${v_j}$ to the ${j^{th}}$ market and no others. This corresponds to first degree price discrimination. It is also easy to see that ${P \geq \max_{1 \leq j \leq n} v_j\sum_{r \geq j}d_j = \Pi_0(d)}$. The lower bound comes from the segmentation that assigns all customers to market ${k}$, where ${v_k}$ is the profit maximizing monopoly price without discrimination. BBM show the following:

Theorem ${(P,C)}$ is feasible iff ${\Pi_0(d) \leq P \leq \Pi_1(d)}$ and ${P + C \leq \sum_jv_jd_j}$.

That ${\Pi_0(d) \leq P \leq \Pi_1(d)}$, is straightforward. The hard part is to show two things.

1) For any ${P}$ such that ${\Pi_0(d) \leq P \leq \Pi_1(d)}$ there is a ${C}$ such that ${P + C = \sum_{j=1}^nv_jd_j}$.

2)There exists an ${x \in X(d)}$ such that ${P = \Pi_0(d)}$ and ${C = 0}$.

To prove the first item (which BBM note in the paper is easy) on this list, call a segmentation ${x \in X(d)}$ upper triangular if ${x_{ij} = 0}$ for all ${i < j}$. Note ${v_k > v_t}$.

Let ${r = \arg \max_{1 \leq q \leq t}v_q\sum_{i=q}^tx_{ik}}$. We construct a new segmentation ${y \in X(d)}$ from ${x}$ by shifting the buyers in market ${k}$ with values below ${v_k}$ into market ${r}$. As the profit maximizing price just to this portion of buyers is ${v_r}$, moving them into market ${r}$ leaves the profit maximizing price in market ${r}$ unchanged. Formally:

${y_{ij} = x_{ij}}$ for all ${i}$ and ${j \neq k, r}$.
${y_{ik} = x_{ik}}$ for all ${i \geq k}$.
${y_{ik} = 0}$ for all ${i t}$.
${y_{ir} = x_{ir} +x_{ik}}$ for all ${i \leq t}$.

Under segmentation ${y}$, both ${P}$ and ${C}$ increased in value, contradicting the initial choice of ${x}$.

To prove the second item on the list, among all feasible segmentations such that ${P = \Pi_0(d)}$, choose one that minimizes ${C}$, say ${x}$. Call ${x}$ lower triangular if ${x_{ij} = 0}$ for all ${i > j}$. I show that ${x}$ must be lower triangular from which it follows that ${C = 0}$. The proof will be by induction on ${n}$ the number of distinct valuations.

The case ${n=2}$ is straightforward. Suppose first that ${\Pi_0(d) = v_1(d_1 + d_2)}$. The following segmentation, as can be verified, does the trick:

${x_{22} = d_2}$
${ x_{12} = \alpha}$ where ${v_1[\alpha + d_2] = v_2d_2}$
${x_{21} = 0}$
${x_{11} = d_1 - \alpha}$

If ${\Pi_0(d) = v_2d_2}$, the segmentation that assigns all buyers to market 2 will have the requiste property.

Now consider the case of arbitrary ${n}$ and suppose first that ${\Pi_0(d) > v_1\sum_{i=1}^nd_i}$. Given an instance ${d}$ on ${n}$ valuations construct an instance ${d'}$ on ${n-1}$ valuations ${\{v'_2, \ldots, v'_{n}\}}$ by setting ${d'_i = d_i}$ for all ${i \geq 2}$. It is easy to see that ${\Pi_0(d') = \Pi_0(d)}$, i.e., the optimal monopoly profit with no discrimination remains unchanged. By the induction hypothesis there is a segmentation ${y \in X(d')}$ that is lower triangular. To conclude the argument we must show how to convert ${y}$ into a legitimate segmentation for ${d}$.

${x_{ij} = y_{ij}}$ for ${i,j \geq 2}$.
${x_{1i} = \mu_i}$ where ${v_1[\mu_i + \sum_{r=2}^nx_{ri}] \leq v_{ii}x_{ii}}$ for all ${i \geq 1}$ and ${\sum_{i=1}^n\mu_i = d_1}$.
If the ${\mu_i}$‘s can indeed be chosen as specified, then, ${x \in X(d)}$ is lower triangular and the corresponding ${P = \Pi_0(d)}$ and ${C = 0}$. To verify that appropriate ${\mu_i}$‘s exist, it is enough to check that
$\displaystyle d_1 \leq \sum_{i=1}^n\frac{v_{ii}}{v_1}x_{ii} - \sum_{i=1}^n \sum_{r=2}^nx_{ri} = \frac{1}{v_1}\Pi_0(d') - \sum_{r=2}^nd_r$

which follows from the hypothesis that ${v_1\sum_{r=1}^nd_r \leq \Pi_0(d)}$.

To conclude, suppose now that ${\Pi_0(d) = v_1\sum_{i=1}^nd_i}$. Construct a new instance ${d'}$ on ${n-1}$ valuations ${\{v'_1, v'_3 \ldots, v'_{n}\}}$ by setting ${d'_i = d_i}$ for all ${i \geq 3}$ and ${d'_1 = d_1 + d_2}$. Notice, ${\Pi_0(d') = \Pi_0(d)}$. By the induction hypothesis there is a segmentation ${y \in X(d')}$ that is lower triangular. To conclude the argument we must show how to convert ${y}$ into a legitimate segmentation for ${d}$.

${x_{ij} = y_{ij}}$ for ${i,j \geq 3}$.
${x_{2i} = \mu_i}$ for all ${i \geq 1}$ where ${v_2[\mu_i + \sum_{r \geq 3}x_{ri}] \leq v_{ii}x_{ii}}$, ${\mu_i \leq y_{1i}}$ and ${\sum_{r=1}^n\mu_i = d_2}$.
${x_{1i} = y_{1i} - \mu_i}$ for all ${i \geq 1}$.

If the ${\mu_i}$‘s can be chosen as specified then, ${x}$ is lower triangular, in ${X(d)}$ and the corresponding ${P = \Pi_0}$ and ${C = 0}$. Verifying that the appropriate ${\mu_i}$‘s exist, can be done in the same way as the previous case.