The monopolist’s free boundary problem in the plane

The Monopolist’s problem is a principal-agent model for making decisions facing asymmetric information; it has fundamental importance in microeconomic theory. A simple form from [50] capturing multiple dimensions of heterogeneity that we rederive below is to

We always take $\Omega\subset\mathbf{R}^{n}$ to be open and convex with compact closure $\overline{\Omega}$. Our goal in this paper is to elucidate the properties of solutions to this minimization problem, with an eventual focus on the two-dimensional setting. Because the minimization takes place over the set of convex functions the problem has a free boundary structure. The free boundary separates the region where the function is convex, but not strictly convex, from the region where the function is strictly convex. In this paper we refine our understanding of the free boundary structure in all dimensions by showing regions where $u$ is not strictly convex always extend to the fixed boundary $\partial\Omega$. We show the regularity known for $u$ often extends from the interior to the fixed boundary. In two-dimensions, we show in a neighbourhood of a certain class of free boundary points (that we call tame), the minimizer solves the classical obstacle problem. From this we obtain the tame free boundary is locally piecewise Lipschitz except at accumulation points of its local maxima; it has Hausdorff dimension strictly less than two and is the graph of a function continuous $\mathcal{H}^{1}$-almost everywhere. We also establish a boot strapping procedure: if the free boundary is suitably Lipschitz, it is $C^{\infty}$. As an application of our techniques we completely describe the solution on the square domains $\Omega=(a,a+1)^{2}\subset\mathbf{R}^{2}$ with $a\geq 0$. Despite significant numerical [7, 17, 18, 19, 25, 42, 44, 48], and analytic attempts [50, 35, 41] the description of the solution on the square has previously remained incomplete, and has come to be regarded as analytically intractable [7, 19, 34]. At least on the plane, we rebut this view by confirming for $a\geq\frac{7}{2}-\sqrt{2}$ the solution recently hypothesized by McCann and Zhang [41]. We show how their solution can also be modified to accommodate smaller values of $a$ and other convex, planar domains. We show that the nature of the bunching undergoes unanticipated changes — from absent to targeted to blunt — as $a\geq 0$ is increased. We rigorously prove the support $Du(\overline{\Omega})$ of the unknown distribution of products consumed has a lower boundary which is concave nondecreasing — as the above-mentioned numerics and stingray description suggest — and that all products selected by more than one type of consumer lie on this boundary or its reflection through the diagonal.

The problem (1) arises from the question of how a monopolist should price goods for optimal profit in the face of information asymmetry. Here is a simple derivation of (1). We assume a closed set of products $\Omega^{*}\subset\mathbf{R}^{n}$ where each coordinate represents some attribute of the product, and an open set of consumers $\Omega\subset\mathbf{R}^{n}$ where each coordinate represents some attribute of the consumer. Consumers are distributed according to a Borel probability measure $\mu\in\mathcal{P}(\Omega)$. The monopolist’s goal is to determine a price $v(y)$ at which to sell product $y$ in a way which maximizes their profit. If consumer $x\in\Omega$ attains benefit $b(x,y)$ from product $y\in\Omega^{*}$ then the consumer will choose the product $y$ which maximizes their utility

Provided it exists, we denote the $y$ which realizes this supremum by $Yu(x)$. Assuming the monopolist pays cost $c(y)$ for product $y$, then the monopolist’s goal is to maximize their profit, the integral of price they sell for minus cost they pay,

The problem has been considered in this generality in e.g. [3] [12] [30] [38], and for even more general (non quasilinear) utility functions in [47], [39]. For this paper, to highlight the mathematical properties of most interest, we adopt several standard simplifying assumptions proposed by Rochet and Choné [50]: that products lie in the nonnegative orthant $\Omega^{*}=[0,\infty)^{n}$ and the monopolist’s direct cost to produce them is quadratic $c(y)=|y|^{2}/2$, furthermore, that consumers are uniformly distributed on their domain $\Omega\subset{\mathbf{R}}^{n}$ and their product preferences are bilinear $b(x,y)=x\cdot y$. In this case (2) implies $u$ is the Legendre transform of $v$ (and thus a convex function), $Yu(x)=\partial u(x)$, and when $\Omega\subset[0,\infty)^{n}$ the Monopolist’s goal becomes to maximize

over nonnegative convex functions which, up to an irrelevant constant, is the problem (1). Since convex functions are differentiable almost everywhere the integrand is well-defined. The nonnegativity constraint on $u$ represents the additional requirement that $v(0)=0$, meaning consumers need not consume if the monopolist raises prices too high, or equivalently, are always free to pay nothing by choosing the zero product as an outside option.

This problem was first considered by Mussa and Rosen in the one-dimensional setting [46], (after related models of taxation [45], matching [4], and signaling [53] were introduced and analyzed by Mirrlees, Becker and Spence). The multidimensional problem was considered by Wilson [55] and Armstrong [2], while our formulation above is essentially that of Rochet and Choné [50]. Although this model is of significant importance to economists it presents serious mathematical difficulties. Indeed, were there only the nonnegativity constraint in (1) we would have a variant of the obstacle problem [8, 29]; with the nonnegativity and convexity constraint we have a free boundary problem for three different regions. In the region where the function is positive but not strictly convex, the fundamental tool of two-sided perturbation by an arbitrary test function is no longer applicable. As a result, until recent work of the first and third authors [41] it has not even been possible to write down the Euler–Lagrange equation in the region of nonstrict convexity. Despite this, other aspects of the problem have been studied, notably by Rochet and Choné [50], who derived a necessary and sufficient condition for optimality in terms of convex-ordering between the positive and negative parts of the variational derivative of the objective functional, Basov [3] who advanced a control theoretic approach to such problems, Carlier [12, 13] who considered existence and first-order conditions for the minimizer, and Carlier and Lachand-Robert [14, 20, 16] who studied regularity and gave a description of the polar cone.

In this paper we prove results of mathematical and economic interest. We invoke tools from diverse areas of mathematics: the theory of sweeping and convex orders of measures, Monge–Ampére equations, regularity theory for the obstacle problem, and the theory of optimal transport (which has deep links to the Monopolist’s problem). We also indicate a striking connection to the classical obstacle problem: Locally the minimizer $u$ solves an obstacle problem where the obstacle is the minimal convex extension of $u$ from its region of nonstrict convexity. We now outline our results.

If $u$ solves (1) and $\Omega$ is a convex open subset of $\mathbf{R}^{n}$ it is known from the work of Rochet–Choné and Carlier–Lachand-Robert that $u\in C^{1}(\overline{\Omega})$ and from the work of Caffarelli and Lions [9] (see [38]) that $u\in C^{1,1}_{\text{loc}}(\Omega)$. Any convex function $u\in C^{1}(\overline{\Omega})$ partitions $\Omega$ according to its sets of contact with supporting hyperplanes; these sets are convex. Namely for each $x_{0}\in\overline{\Omega}$ set

Here $\tilde{x}$ is the equivalence class of $x$ under the equivalence relation $x_{0}\sim x_{1}$ if and only if $Du(x_{0})=Du(x_{1})$. We call an equivalence class trivial if $\tilde{x}=\{x\}$, in which case we say $u$ is strictly convex at $x$. We call equivalence classes leaves, since they foliate the interior of $\Omega_{i}$. They are also called isochoice sets [23] or bunches if nontrivial [50]. We also call one-dimensional leaves rays. We set

Thus, for example, $\Omega_{n}$ consists of all points at which $u$ is strictly convex and $\Omega_{0}$ consists of all points $x$ lying in the closure of some open set on which $u$ is affine. These disjoint sets partition $\overline{\Omega}$ and our first result describes the qualitative behavior in each set.

It is immediate from the definition that $\Omega_{i}$ for $1\leq i\leq n-1$ are a union of nontrivial equivalence classes; the key conclusion is these extend to the boundary (i.e. if $x\in\Omega_{i}$ for $1\leq i\leq n-1$ then $\tilde{x}\cap\partial\Omega\neq\emptyset$). The PDE in point (3) has been considered in more generality by Rochet and Choné [50]. Note the economic interpretation of (1): no bunches of positive measure are sold apart from the null product; as we shall see during the proof of (2), any product sold to more than one consumer lies on the boundary of the set of products sold. Thus the entire interior of the set of products sold consists of individually customized products. Our proof of Theorem 1.1 and some subsequent results requires a new proposition asserting that a.e. on the boundary of a convex domain $\Omega$, the minimizer of (1) satisfies the boundary condition $(Du(x)-x)\cdot\mathbf{n}\geq 0$ where $\mathbf{n}$ is the outer unit normal to $\Omega$. Established in Proposition 2.3, it can be interpreted to mean that the normal component of any boundary distortion in product selected can never be inward. Moreover, in convex polyhedral domains and certain other situations, we are able to extend the interior regularity $u\in C^{1,1}_{\text{loc}}(\Omega)$ of Caffarelli and Lions [9] [38] to the smooth parts of the fixed boundary, Theorem 4.1.

The remainder of our results are restricted to the planar case $\Omega\subset\mathbf{R}^{2}$. Theorem 1.1 provides a complete description of the solution in $\Omega_{0}$ and $\Omega_{2}$: it remains to better understand the behavior of the solution in $\Omega_{1}$ as well as the properties of the domains $\Omega_{1}$ and $\Omega_{2}$, (noting $\Omega_{0}$ is, by Theorem 1.1, a closed convex set).

By Theorem 1.1, the free boundary $\Gamma:=\partial\Omega_{1}\cap\partial\Omega_{2}\cap\Omega$ between $\Omega_{1}$ and $\Omega_{2}$ consists only of points in rays which foliate $\Omega_{1}$ and extend to $\partial\Omega$. In §5 we prove that the Neumann condition

where $\mathbf{n}$ is the outer unit normal to the fixed boundary ${\partial}\Omega$, can be used to characterize the presence of these rays. Namely if (5) is not satisfied at $x_{0}\in\partial\Omega$ then $\tilde{x_{0}}\neq\{x_{0}\}$. Conversely, if $x\in\partial\Omega$ lies in a boundary neighbourhood $B_{\varepsilon}(x)\cap\partial\Omega$ on which the Neumann condition (5) is satisfied then $x$ is a point of strict convexity for $u$. The remaining case — rays $\tilde{x}_{0}\neq\{x_{0}\}$ which satisfy (5) — is subtle: we call such rays stray and conjecture the union $\mathcal{S}$ of stray rays has zero area in general, but are able to show it is empty only for the squares $\Omega=(a,a+1)^{2}$.

Let $x_{1}$ be a point in the free boundary $\Gamma$ which, necessarily, lies on the ray $\tilde{x_{1}}$. Let $x_{0}=\tilde{x_{1}}\cap\partial\Omega$ be the boundary endpoint of $\tilde{x_{1}}$. Note that provided $\partial\Omega$ is $C^{1}$ in a neighbourhood of $x_{0}$ and $(Du(x_{0})-x_{0})\cdot\mathbf{n}>0$, the same inequality holds for all $x\in B_{\varepsilon}(x_{0})\cap\partial\Omega$ and thus such $x$ are also the boundary endpoints of nontrivial rays. In this case we call $x_{1}$ a tame free boundary point (and $\tilde{x}_{1}$ a tame ray); we denote the set of tame free boundary points by $\mathcal{T}$.

Since we don’t know whether local maxima of $D(x)=\text{diam}(x)$ can be dense, we augment (2) by proving the function $\partial\Omega\ni x\mapsto D(x)$ is continuous $\mathcal{H}^{1}$-almost everywhere on the fixed boundary in Theorem 7.2. Establishing the Lipschitz regularity of $D$, which permits the above-mentioned bootstrapping to a $C^{\infty}$ free boundary, remains an interesting open problem.

Theorem 1.2 is proved using new coordinates for the problem, new Euler–Lagrange equations, and a new observation: That in a neighbourhood of a tame free boundary point the difference between the minimizer $u$ and the minimal convex extension of $u|_{\Omega_{1}}$ solves the classical obstacle problem. A priori, the obstacle is $C^{1,1}$, i.e. has a merely $L^{\infty}$ Laplacian, and thus, without first improving the regularity of $u|_{\partial\Omega_{1}}$, the above results are the best one can obtain from the theory of the obstacle problem.

For general convex domains it is difficult to study the structure of the stray set $\mathcal{S}=\Gamma\setminus\mathcal{T}$ which may include points in the relative interior of rays. We also have not ruled out, in general, that the relative boundary of

in ${\partial}\Omega$ might have positive $\mathcal{H}^{1}$-measure and the corresponding free boundary be nonsmooth. However, in specific cases, a more complete description is possible. For example, on the squares $\Omega=(a,a+1)^{2}$, we show $\partial\Omega_{\neq}$ is a single connected component of $\partial\Omega$. In fact, we are able to provide the first explicit and complete description of the solution on $\Omega=(a,a+1)^{2}$, including an unexpected trichotomy for $a=0$, $a$ sufficiently small, and $a$ sufficiently large. To describe the solution we label the edges of $\Omega$ by their compass direction and set

The minimizer is described by the following bifurcation theorem (visualized in Figure 1).

The following corollary may be of purely mathematical interest from the point of view of calculus of variations and partial differential equations; the smoothness asserted follows from the results of [10, 8].

Assuming $\Omega_{2}$ is Lipschitz (or at least has finite perimeter), we arrive at a characterization of the solution to (1) on $\Omega=(a,a+1)^{2}$ for every value of $a\geq 0$. Namely $u\in\mathcal{U}$ minimizes (1) if and only if (A) bunching is absent ($\Omega_{1}=\emptyset$, as for $a=0$), in which case $u$ solves $\frac{1}{3}\Delta u=1_{\{u>0\}}$, i.e the classical obstacle problem [49, 29, 27] and $(Du-x)\cdot\mathbf{n}=0$ on $\partial\Omega$ (Figure 1(a)), or (B) bunching is present but blunt bunching is absent, ($\Omega_{1}^{0}=\emptyset\neq\Omega_{1}$, as for $a\ll 1$) in which case we derive below necessary conditions, whose sufficiency can be confirmed as in [41] (Figure 1(b)), or (C) blunt bunching is present, ($\Omega_{1}^{0}\neq\emptyset$, as for $a\geq\frac{7}{2}-\sqrt{2}$) (Figure 1(c)), in which case the sufficient conditions for a minimum established by two of us [41] are also shown to be necessary below. (The only gap separating the necessary from the sufficient condition is the question of whether or not $\Omega_{2}$ must have finite perimeter.)

If instead (B) blunt bunching is absent but bunching is present, $\Omega_{1}^{0}=\emptyset\neq\Omega_{1}$, Theorem 1.4 asserts that $\Omega_{1}=\Omega_{1}^{+}\cap\Omega_{1}^{-}$ splits into two connected components

placed symmetrically below and above the diagonal. The region $\Omega_{1}^{-}$ and its reflection $\Omega_{1}^{+}$ below the diagonal are foliated by isochoice segments making continuously varying angles $\theta$ with the horizontal. The limit of these segments is a segment of length $R_{0}>0$ lying on the boundary of the convex set $\Omega_{0}$, having endpoint $(a,h_{0})$ and making angle $\theta_{0}\in[-\pi/4,0)$ with the horizontal.

Fix any closed convex neighbourhood $\Omega_{0}$ of $(a,a)$ in $\overline{\Omega}$ which is reflection symmetric around the diagonal and contains such a segment in its boundary. We describe the solution $u=u_{1}^{-}$ in $\Omega_{1}^{-}$ using an Euler-Lagrange equation (9) from [41], rederived more simply in Section 8 below. Index each isochoice segment in $\Omega_{1}^{-}$ by its angle $\theta\in(-\frac{\pi}{4},0)$; (angles which are less than $-\pi/4$ or non-negative are ruled out in the proof of Theorem 1.4). Let $(a,{h(\theta)})$ denote its left-hand endpoint and parameterize the segment by distance ${r}\in[0,R(\theta)]$ to this boundary point $(a,h(\theta))$. Along the hypothesized length $R(\theta)$ of this segment assume $u$ increases linearly with slope $m(\theta)$ and offset $b(\theta)$:

Given the initial (angle, height) pair $(\theta_{0},h_{0})\in[-\pi/4,0)\times(a,a+1)$, and ${R}:\left[\theta_{0},0\right]\to\left[0,\sqrt{2}/2\right)$ piecewise Lipschitz with $R(\theta_{0})=R_{0}$, solve

then set

Given $(\theta_{0},h_{0},R_{0})$ and $R(\cdot)$ as above, the triple $(m,b,h)$ satisfying (9)–(11) exists and is unique on the interval where $R(\cdot)>0$. Thus the shape of $\Omega_{1}^{-}$ and the value of $u_{1}^{-}$ on it will be uniquely determined by $\Omega_{0}$ and $R:\left[\theta_{0},0\right]\to\left[0,\sqrt{2}/2\right)$. We henceforth restrict our attention to choices of $\Omega_{0}$ and $R(\cdot)$ for which the resulting set $\Omega_{1}^{-}$ lies above the diagonal. In this case $\Omega_{1}^{+}$ and the value of $u=u_{1}^{+}$ on $\Omega_{1}^{+}$ are determined by reflection symmetry $x_{1}\leftrightarrow x_{2}$ across the diagonal. This defines $u=u_{1}$ on $\Omega_{1}$ and provides the boundary data on ${\partial}\Omega_{1}\cap{\partial}\Omega_{2}$ needed for the mixed Dirichlet / Neumann boundary value problem for Poisson’s equation,

which determines $u=u_{2}$ on $\Omega_{2}:=\Omega\setminus(\Omega_{0}\cup\Omega_{1})$. The duality discovered in [41], implies that for at most one choice of $\Omega_{0}$ and $R(\cdot)$ Lipschitz can convex $u$ (pieced together from $u_{1},u_{2}$ as above with $u_{0}:=0$ on $\Omega_{0}$) satisfy the supplemental Neumann conditions

required on the free boundaries (since $u\in C^{1}(\overline{\Omega})$ [15][50]); here $\hat{\mathbf{n}}$ denotes the outer unit normal to $\Omega_{2}$ at $x\in{\partial}\Omega_{2}$. In the course of proving Theorem 1.4 in Section 8 below we complete this circle of ideas — apart from the piecewise Lipschitz hypothesis which Theorem 1.2 falls just short of proving — by showing at least one such choice exists; this choice uniquely solves (1) on the square in case (B). In case (C), Theorem 1.4 shows at least (and therefore exactly [41]) one choice exists satisfying the free boundary problem from [40] in the analogous sense.

We conclude this introduction by outlining the structure of the paper. Section 2 contains preliminaries: the variational inequality associated to (1), some background on Alexandrov second derivatives, and localization results of Rochet–Choné. In Section 3 we prove Theorem 1.1 using perturbation techniques previously used to study the Monge–Ampère equation. In Sections 4 and 5 and we prove some technical results which facilitate our later work in Sections 6 and 7. First, in Section 4, a boundary $C^{1,1}$ result which is new for this problem and extends the interior regularity result of Caffarelli and Lions [9] [38]. Next, in Section 5, propositions quantifying how at points of nonstrict convexity the Neumann boundary condition fails to be satisfied. Section 6 and Section 7 establish Theorem 1.2 using techniques from the study of the obstacle problem. Here we indicate a new connection to the classical obstacle problem. Namely, that the Monopolist’s problem gives rise to an obstacle problem where the obstacle is the minimal convex extension of the function defined on $\Omega_{1}$. The proof of Theorem 1.4 is completed in Section 8 using a case by case analysis based on a careful choice of coordinates. It confirms the economic intuition that the degree to which product selection (hence bunching) is influenced by the market presence of competing consumers decreases as we move away from the exclusion region, i.e. from the lower left toward the upper right region of the square, while on the other hand, increasing as we move the entire square of consumer types away from the outside option by increasing $a\geq 0$. We conclude with appendices containing some relevant background results. Table 1 contains a list of notation.