Existence in Multidimensional Screening with General Nonlinear Preferences

Existence in Multidimensional Screening with General Nonlinear Preferences

Introduction

This paper provides a general existence for a multidimensional nonlinear pricing model, which is a natural extension of the models studied by Mussa-Rosen MussaRosen78, Spence Spence74, Spence80, Myerson Myerson81, Baron-Myerson BaronMyerson82, Maskin-Riley MaskinRiley84, Wilson Wilson93, Rochet-Chon\'e RochetChone98, Monteiro-Page MonteiroPage98 and Carlier Carlier01. A significant distinction lies in whether the agents' private type is one-dimensional (such as MussaRosen78, MaskinRiley84), or multidimensional (such as RochetChone98,MonteiroPage98, Carlier01). Another distinction is whether preferences are quasilinear on price (such as Armstrong96, Carlier01) or fully nonlinear (such as NoldekeSamuelson15p, McCannZhang17), especially for multidimensional models.

This paper proves the existence of a (price menu) solution to a multidimensional multiproduct monopolist problem, by extending Carlier Carlier01 to fully nonlinear preferences. $G$-convex analysis, which is strongly tied to Trudinger's theory on the regularity of nonlinear PDEs Trudinger14 developed for vastly different purposes, is employed to deal with the difficulty of non-quasilinear preferences. This method is potentially applicable to other problems under the same principal-agent framework, such as the study of tax policy (Mirrlees71) and other regulatory policies (BaronMyerson82).

Consider the problem for a multiproduct monopolist (the principal) who sells indivisible products to a population of consumers (agents), who each buy at most one unit. Assume the monopolist is able to produce enough of each product such that there are neither product supply shortages {nor economies of scale}. Taking into account participation constraints and incentive compatibility, the monopolist would like to find the optimal menu of prices to maximize her total profit.

In this paper, we first identify incentive compatibility with a $G$-convexity constraint, before rewriting the maximization problem by converting the optimization variables from a product-price pair of mappings to a product-value pair. It can then be shown that the product-value pair converges under the $G$-convexity constraint. The existence result follows.

Starting from Mirrlees Mirrlees71 and Spence Spence74, there are two main types of generalizations. One generalization is regarding dimension, from one-dimensional to multi-dimensional. The other generalization is in the form of utility functions, to beyond quasilinear.

For the quasilinear case, where the utility function depends linearly on price, theories of existence Basov05,RochetStole03,Carlier01,MonteiroPage98, uniqueness CarlierLachand-Robert01,FigalliKimMcCann11,MussaRosen78,RochetChone98 and robustness Basov05,FigalliKimMcCann11 have been well studied, among which the equivalence of function space convexity to the non-negative cross-curvature condition revealed by Figalli-Kim-McCann FigalliKimMcCann11 serves as a major milestone orienting our work.

When parameterization of preferences is linear in agent types and price, Rochet and Chon\'e (1998, RochetChone98) not only obtain existence results but also partially characterize optimal solutions and expound their economic interpretations, given that the monopolist profit can be characterized by {the aggregate difference between selling prices and quadratic manufacturing costs.}

More generally, Carlier Carlier01 has proved existence results for general quasilinear utilities, where agent type and product type are not necessarily of the same dimension and the monopolist profit equals selling price minus some linear manufacturing cost.

This paper generalizes the quasilinear case to the non-quasilinear case, which has many potential applications. For example, some fully nonlinear utilities include scenarios where agents are more sensitive to higher prices and where different agents might have different sensitivities to the same price. See Wilson Wilson93 for the importance of taking income effects into account. The generalized existence problem also appears as a conjecture by Basov Basov05. However, only a few results are known for the multidimensional non-quasilinear case, and the impact of price on utility could be much more complicated.

Recently, N\"oldeke-Samuelson NoldekeSamuelson15p provided a general existence result assuming that the agent and product space are compact, by implementing a duality argument based on Galois connections. McCann-Zhang McCannZhang17 not only showed a general existence result assuming the single-crossing type condition and boundedness of the agent-type and product-type spaces, but generalized uniqueness and convexity results of Figalli-Kim-McCann FigalliKimMcCann11 to the non-quasilinear case, by using $G$-convexity arguments. In this paper, we also explore existence using $G$-convex analysis, which will be introduced in Subsection (ref), but with less restriction on boundedness of the product domain and without assuming the generalized single-crossing condition McAfeeMcMillan88. As a result of the lack of natural compactness, the proof of the existence result in this paper is entirely different from that in either of the earlier papers. It should be mentioned here that the existence results from this paper and the earlier two require no restrictions on the monopolist profit to take on a particular form, which is a generalization from much of the literature.

The remainder of this paper is organized as follows. Section (ref) states the mathematical model and assumptions. It also introduces preliminaries, including $G$-convexity and $G$-subdifferentiability, and reformulates the monopolist's problem. In Section (ref), we state the existence theorem (Theorem (ref)) as well as the convergence results for sequences of $G$-convex functions (Proposition (ref)). Section (ref) proposes some directions for future work. We leave all the proofs of lemmas, propositions and the existence theorem in Section (ref).

Model

Our model of the principal-agent problem is a bilevel optimization. After a monopolist publishes her price menu, each agent maximizes his utility through the purchase of at most one product. Knowing only the distribution of agent types, the monopolist maximizes aggregate profit based on agents' choices, which are based on the price menus.

Suppose the agents' preferences are given by some parametrized utility function $G(x, y, z)$, where $x$ is an $M$-dimensional vector of agent characteristics, $y$ is an $N$-dimensional vector of attributes of each product, and $z$ represents the price of each product. Denote {by} $X$ the space of agent types, by $Y$ the space of products, by $cl(Y)$ the closure of $Y$, by $Z$ the space of prices, and by $cl(Z)$ the closure of $Z$. In this paper, we only consider the case where both agent types and product attributes are continuous.

The monopolist sells indivisible products to agents, i.e., she will sell neither a part/percentage of one product nor a product with some probability. Each agent buys at most one unit of product. For any given price menu $p: cl(Y) \rightarrow cl(Z)$, an agent $x \in X$ knows his utility $G(x,y,p(y))$ for purchasing each product $y$ at price $p(y)$. It follows that each agent solves the following maximization problem

where $u(x)$ represents the maximal utility agent $x$ can obtain, and $u: X \rightarrow \mathbf{R}$ is also called the value function or indirect utility function. At this point, it is assumed that the maximum in (ref) is attained for each agent $x$.

If agent $x$ purchases product $y$ at price $p(y)$, the monopolist would earn from this transaction a profit of $\pi(x,y,p(y))$. For example, the monopolist profit can take the form $\pi(x,y,p(y)) = p(y)-c(y)$, where $c(y)$ is a variable manufacturing cost function. Summing over all agents in the distribution $d\mu(x)$, the monopolist's total profit is characterized by

which depends on her price menu $p: cl(Y) \rightarrow cl(Z)$ and agents' choices $y: X \rightarrow cl(Y)$.\footnote{It is worth mentioning that in some literature, the monopolist's objective is to design a product line $\tilde{Y}$ (i.e., a subset of $cl(Y)$) and a price menu $\tilde{p}: \tilde{Y} \rightarrow \mathbf{R}$ that jointly maximize the overall monopolist profit. Then, given $\tilde{Y}$ and $\tilde{p}$, an agent of type $x$ chooses the product $y(x)$ that solves

Allowing the price to take value $\bar{z}$ (which may be $+\infty$), and assuming Assumption (ref) below, the effect of designing a product line $\tilde{Y}$ and price menu $\tilde{p}: \tilde{Y}\rightarrow \mathbf{R}$ is equivalent to that of designing a price menu $p : cl(Y)\rightarrow (-\infty, +\infty]$, which equals $\tilde{p}$ on $\tilde{Y}$ and maps $cl(Y) \setminus \tilde{Y}$ to $\bar{z}$, such that no agents choose to purchase any product from $cl(Y) \setminus \tilde{Y}$, which is less attractive than the outside option $y_{\emptyset}$ according to Assumption (ref). In this paper, we use the latter as the monopolist's objective.

For any given price menu $p: cl(Y)\rightarrow (-\infty, +\infty]$, one can construct a mapping $y: X \rightarrow cl(Y)$ such that each $y(x)$ solves the maximization problem in (ref). But such mapping is not necessarily unique, without the single-crossing type assumptions. Therefore, we adopt in (ref) the total profit as a functional of both price menu $p$ and its corresponding mapping $y$.}

An incentive-compatible product-price pair $(y, p(y))$ ensures that no agent has the incentive to pretend to be another agent type.

In addition, we adopt a participation constraint in order to rule out the possibility of the monopolist charging exorbitant prices and the agents still having to make transactions despite this: each agent $x\in X$ will refuse to participate to the market if the maximum utility he can obtain is less than his reservation value $u_{\emptyset}(x)$, where the function $u_{\emptyset}: X \rightarrow \mathbf{R}$ is given in the form $u_{\emptyset}(x): = G(x, y_{\emptyset}, z_{\emptyset})$ for some $(y_{\emptyset}, z_{\emptyset}) \in cl(Y \times Z)$, where $y_{\emptyset}$ represents the outside option, whose price equals to some fixed value $z_{\emptyset} \in \mathbf{R}$ beyond the monopolist's control.

For the monopolist profit, some literature assumes $\pi(x, y_{\emptyset}, z_{\emptyset}) \ge 0$ for all $x\in X$ to ensure that the outside option is harmless to the monopolist. Here, it is not necessary to adopt such an assumption for the sake of generality.

The monopolist's problem can be described as follows:

We assume that $p$ is lower semicontinuous, without which the maximum in (ref) may not be attained. We also rewrite the monopolist's problem in Proposition (ref), which is an equivalent form of (ref).

The purpose of the following subsections is to fix terminology and prepare the preliminaries for the main results in the next section. The proofs can be found in Section (ref).

$G$-Convex and $G$-Subdifferentiability

In this subsection, we introduce some tools from convex analysis and the notion of $G$-convexity (c.f. Trudinger14,Balder77,Singer97), which is a generalization of ordinary convexity. Several results in this subsection echo those from Section 3 of McCann-Zhang McCannZhang17 but extend to unbounded domains.

The following assumptions are made to the agents' direct utility $G$. We use $C^0(X)$ to denote the space of all continuous functions on $X$ and use $C^1(X)$ to denote the space of all differentiable functions on $X$ whose derivatives are continuous.

Here we do not necessarily assume $X$, $Y$, and $Z$ are compact spaces; in particular, $Y$ and $Z$ are potentially unbounded (i.e.,\ we do not set a priori bounds for product attributes or an a priori upper bound for prices). However, we do specify a lower bound for the price range, since the monopolist has no incentive to set price close to negative infinity. The last inequality shows the highest price $\bar{z}$ is less preferred than the outside option.

This is to say that, for any given product, the higher the price paid to the monopolist, the lower the utility that will be left for the agent. For each $(x, y) \in X\times cl(Y)$ and $u\in G(x,y, cl(Z))$, define $H(x,y,u) := z$ whenever $G(x,y,z) = u$, i.e., $H(x, y, \cdot)= G^{-1}(x,y,\cdot)$. Therefore, $H(x,y,u)$ represents the price paid by agent $x$ for product $y$ when receiving value $u$.

Proposition (ref) shows that the inverse function of $G$ is also continuous because $G$ is continuous and monotonic on the price variable.

Recall that the subdifferential of a function $u$ at $x_0$ is defined as the set:

Here we use $ \langle , \rangle$ to denote the Euclidean inner product. This set is nonempty for every $x_0$ if and only if $u$ is convex. Then for any convex function $u$ on $X$ and any fixed point $x_0 \in X$, there exists $y_0 \in \partial u(x_0)$, satisfying

where equality holds at $x = x_0$. On the other hand, if for any $x_0\in X$, there exists $y_0$ such that (ref) holds for all $x\in X$, then $u$ is convex. The following definition is analogous to this property, which is a special case of $G$-convexity, when $G(x,y,z) = \langle x, y \rangle -z$.

Similarly, one can also generalize the definition of subdifferential from (ref).

In particular, if $G(x,y,z) = \langle x, y \rangle - z$, then the $G$-subdifferential coincides with the subdifferential. There are other generalizations of convexity and subdifferentiability. For instance, $h$-convexity in Carlier Carlier01, or equivalently, $b$-convexity in Figalli-Kim-McCann FigalliKimMcCann11, or $c$-convexity in Gangbo-McCann GangboMcCann96, is a special form of $G$-convexity, where $G(x,y,z)= h(x,y) -z$, which plays an important role in the quasilinear case. For more references of convexity generalizations, see Kutateladze-Rubinov KutateladzeRubinov72, Elster-Nehse ElsterNehse74, Balder Balder77, Dolecki-Kurcyusz DoleckiKurcyusz78, Singer Singer97, Rubinov Rubinov00a, and Martínez-Legaz MartinezLegaz05.

As mentioned above, a well-known result in convex analysis is that a function is convex if and only if it is subdifferentiable everywhere. The following lemma adapts this to $G$-convexity.

Using Lemma (ref), one can show the following result, which connects incentive compatibility in the economic context with $G$-convexity and $G$-subdifferentiability in mathematical analysis, generalizing the results of Rochet Rochet87 and Carlier Carlier01.

Implementability

We introduce implementability here, which is closely related to incentive-compatibility and can also be exhibited by $G$-convexity and $G$-subdifferential.

As a corollary of Lemma (ref), implementable functions can be characterized as $G$-subdifferential of $G$-convex functions.

When parameterization of preferences is linear in agent types and price, Corollary (ref) says that a function is implementable if and only if it is monotone increasing. In general quasilinear cases, this coincides with Proposition 1 of Carlier Carlier01.

Reformulation of the Monopolist's Problem

From the original monopolist's problem (ref), we replace product-price pair $(p,y)$ by the value-product pair $(u,y)$, using $u(\cdot) = G(\cdot, y(\cdot), p(y(\cdot)))$. Combining this with Lemma (ref), the incentive-compatibility constraint $(y,p(y))$ is equivalent to $G$-convexity of $u(\cdot)$ and $y(x) \in \partial^G u(x)$ for all $x\in X$. Therefore, one can rewrite the monopolist's problem as follows.

Other Assumptions

In the next section, we will show the existence result of the rewritten monopolist's problem $(P)$ given in (ref). For the preparation of the main result, we introduce the following assumptions. Note that, even in the one-dimensional case, we assume no single-crossing type condition. We also include two propositions here, which will be employed in the proofs of Proposition (ref) and the existence theorem.

In Assumption (ref), we assume that agent utility increases along each agent attribute coordinate. Given coordinate monotonicity of $G$ in the first variable, one can show that all the $G$-convex functions are nondecreasing. Therefore, the value functions are also monotonic with respect to the agent attributes.

In the following, we use $D_x G(x,y,z) := \left(\frac{\partial G}{\partial x_1}, \frac{\partial G}{\partial x_2}, \dots, \frac{\partial G}{\partial x_M}\right)(x,y,z)$ to denote derivative with respect to $x$. For any vector in $\mathbf{R}^M$ or $\mathbf{R}^N$, we use $\left\lVert\cdot\right\rVert$ and $\left\lVert\cdot\right\rVert_{\alpha}$ to denote its Euclidean $2$-norm and $\alpha$-norm ($\alpha \ge 1$), respectively. For example, for $x\in \mathbf{R}^M$, we have $\left\lVertx\right\rVert = \sqrt{\sum_{i=1}^{M} x_i^2}$ and $\left\lVertx\right\rVert_{\alpha} = \left(\sum_{i=1}^{M} |x_i|^{\alpha}\right)^{\frac{1}{\alpha}}$. We say a function $f: X \times Y \times Z \rightarrow \mathbf{R}$ is asymptotically decreasing super-linearly (respectively, linearly) with respect to the variable $y\in Y$ if and only if $\frac{f(x,y,z)}{\left\lVerty\right\rVert} \rightarrow -\infty ~(\text{respectively, }C(x,z))$ as $\left\lVerty\right\rVert\rightarrow +\infty$, where $C(x,z)$ is a negative variable depending only on $x$ and $z$. We say a function $f: Y\rightarrow \mathbf{R}$ is asymptotically super-linear if and only if $\frac{f(y)}{\left\lVerty\right\rVert} \rightarrow +\infty$ as $\left\lVerty\right\rVert\rightarrow +\infty$.

In Rochet-Chon\'e's model, $H(x,y,u) = x\cdot y -u$ and $\pi(x,y,z) = z-c(y)$ with a quadratic cost function $c$. In this case, $\pi(x,y,H(x,y,u)) = x\cdot y -u -c(y)$. Since $c$ is asymptotically super-linear and the space $X$ is bounded, it is reasonable to assume the following:

As shown in the alternative formulation, Assumption (ref) requires the existence of some weighted surplus which is asymptotically decreasing super-linearly with respect to the product (when $\alpha >1$). In the case where $Y$ is bounded, Assumption (ref) is equivalent to the existence of some weighted surplus bounded from above.

Assumptions (ref) - (ref) are some technical assumptions on $D_xG$, which are automatically satisfied for $X$, $Y$, and $Z$ being bounded.

Allowing Assumption (ref), {the derivatives $D_{x_i}G$ are always nonnegative; therefore,} we no longer need to take absolute values of $D_{x_i}G$ in the inequality of Assumption (ref). Then Assumption (ref) says that the marginal utility of agents who select the same product $y$ will increase to infinity as $\left\lVerty\right\rVert$ approaches infinity, uniformly for all agents and prices. For instance, when $M = N$, utility $G(x,y,z) = \sum_{i=1}^{M} x_iy_i^2 -f(y,z) $, with $f \in C^1(Y \times Z)$ strictly increasing with respect to $z$, satisfies Assumption (ref), because $$\sum_{i=1}^{M} \left|D_{x_i}G(x,y,z)\right| = \sum_{i=1}^{M} D_{x_i}G(x,y,z) = \sum_{i=1}^{M} y_i^2 \rightarrow +\infty$$ as $\left\lVerty\right\rVert \rightarrow + \infty$. In addition, with appropriate $\pi$, this $G$ could satisfy all the other assumptions. For instance, if we take $\bar{z} = +\infty$, then profit $\pi(x,y,z) = z - \sum_{i=1}^{M} y_i^4$ and agents' utility $G(x,y,z)= \sum_{i=1}^{M} x_iy_i^2 - z^2 $ together satisfy Assumption (ref) - (ref).

In general, if $Y$ is bounded, any $G$ in the form of $G(x,y,z) = b(x,y) - f(y,z)$, with $b \in C^1(cl(X\times Y))$ and $f\in C^0(cl(Y \times Z))$, satisfies Assumption (ref) - (ref). This class of separable utility functions for the agent are also considered in Nöldeke-Samuelson NoldekeSamuelson15p, where they serve as the prime example for utility functions that are not necessarily quasilinear but yield strong implementability.

Proposition (ref) presents that uniform boundedness of the agents' value functions on some compact subset implies uniform boundedness of the corresponding agents' choices of their favorite products.

Assumptions (ref) states constraints on continuity of the principal's profit function $\pi$, integrability of participation constraint $u_{\emptyset}$. From now on, we assume $\mu$ to be equivalent to the Lebesgue measure. One might seek to extend the corresponding results to more general settings, e.g., assuming $\mu$ to be absolutely continuous with respect to the Lebesgue measure.

For $\alpha \ge 1$, denote $L^{\alpha}(X)$ as the space of measurable functions for which the $\alpha$-th power of the absolute value is Lebesgue integrable on $X$. That is, a function $f: X\rightarrow \mathbf{R}$ is in $L^{\alpha}(X)$ if and only if $$\left\lVertf\right\rVert_{L^{\alpha}(X)}:= \left(\int_{X} |f(x)|^{\alpha} dx \right)^{\frac{1}{\alpha}} <+\infty,$$ where $\left\lVertf\right\rVert_{L^{\alpha}(X)}$ is the associated $L^{\alpha}$ norm of $f$ on $X$. For instance, Assumption (ref) implies $u_{\emptyset}\in L^{1}(X)$. For any function $f$ on $X$, its {\em essential supremum} is defined as:

Denote by $L^{\infty}(X)$ the space of measurable functions on $X$ whose essential supremum is finite. Also, denote by $L_{loc}^{\infty}(X)$ the space of measurable functions on $X$ which belong to $L^{\infty}(K)$ for all compact subsets $K$ of $X$.

Main result

In this section, we state the existence theorem, the proof of which is provided in Section (ref).

Technically, in order to demonstrate existence, we start from a sequence of value-product pairs, whose total profits have a limit that is equal to the supremum of $(P)$. Then we need to show that this sequence converges, up to a subsequence, to a pair of limit mappings. Then we show this limit value-product pair satisfies the constraints of $(P)$, and its corresponding total payoff is no worse than those of any other admissible pairs.

Suppose the space of products $Y$ is bounded, then Assumption (ref) - (ref) could be simplified, and Proposition (ref) holds automatically. Besides, some steps in the proof of the main theorem would be simplified. If, in addition, both spaces $Y$ and $Z$ are bounded, Assumption (ref) - (ref) are automatically satisfied and the proofs will be much simpler.

In the following, we denote by $W^{1,1}(X)$ the Sobolev space of $L^1$ functions whose first derivatives exist in the weak sense and belong to $L^1(X)$. For any function $f: X \rightarrow \mathbf{R}$, define its $W^{1,1}(X)$ norm as

For more properties of Sobolev spaces and weak derivatives, see Evans Evans98. If $\omega$ is some open subset of $X$, the notation $\omega \subset \subset X$ means that the closure of $\omega$ is also included in $X$.

Lemma (ref) provides convergence results for sequences of convex functions, which are uniformly bounded in Sobolev spaces on open convex subsets. We state this classical result without proof, which can be found in Carlier Carlier01.

We extend the above convergence result to $G$-convex functions in the following proposition, which is required in the proof of the existence theorem, as it extracts a limit function from a converging sequence of value functions.

In the proof of Proposition (ref), we show that the sequence of $G$-convex functions is convergent by applying results from Lemma (ref), then prove that the limit function is also $G$-convex.

Future Work

We have strong interest in giving an explicit solution for the non-quasilinear example on the real line and in high dimension. We also would like to investigate, among other things, the conditions under which the matching map $y: X \rightarrow cl(Y)$ is continuous and/or differentiable. Given the technical arguments employed in this paper, it may be very fruitful to study possible generalizations of other known results for convex functions to $G$-convex functions.

Proofs