Implementability by a Canonical Indirect Mechanism of an Optimal Two-Dimensional Direct Mechanism

Show more

1. Introduction

In standard literature on adverse selection, an agent-buyer has his taste as private information. If the agent has, in addition, a budget constraint as his private information, the problem becomes one of two-dimensional mechanism design. It is well known that multi-dimensional mechanism design entails quite a few technical difficulties (see [1] , [2] ). One way to get around them is to reduce the dimension of private information [3] and thus to resort to an indirect mechanism.

In the setting of budget-constrained buyers, [4] invoked a non-linear price scheme while showing that this indirect mechanism realizes the equilibrium outcome of the optimal two-dimensional direct mechanism. [5] , by only focusing on the agent’s taste, reduced the whole setting to the well known one of a canonical one-dimensional mechanism, i.e., a map from the taste space to the quality-price space and showed that the optimal canonical mechanism achieves the same outcome as an optimal direct mechanism.^{1} The proof of equivalence, however, involved fancy theory of set-valued mappings not necessarily familiar to an audience in economics.

The above two works differ in perspective and motivation so that they are based on different assumptions as regards the distribution of agents’ type. By adopting the assumptions of [4] , this paper provides an elementary proof that their optimal non-linear price scheme is implemented by a canonical one-dimen- sional mechanism a la Kojima, while resorting to their structure of the optimal non-linear price scheme given by an integro-differential equation.

It turns out that a two-dimensional direct mechanism in general is not so straightforward to implement by a canonical mechanism. This article shows where this difficulty lies, which was not visible in the approach by theory of set- valued functions in [5] . In one word, it consists in the lack of strict concavity of a non-linear price scheme implementing a direct mechanism.

2. The Model

A risk-neutral seller has one unit of an indivisible commodity to sell of quality $q\in Q:=\left[0,1\right]$ . A continuum of buyers purchase one unit of the commodity of quality $q$ or none. The seller values the commodity at zero. A buyer has taste $t$ for the commodity and a budget $w$ . The couple $\left(t,w\right)$ is distributed according to the density $f\left(t,w\right)$ continuously differentiable and positive on its non-empty support, $T\times W$ where $T:=\left[0,\stackrel{\xaf}{t}\right]$ and $W:=\left[0,\stackrel{\xaf}{w}\right]$ . $\left(t,w\right)$ is the buyers’ private information and the seller only knows the density $f\left(t,w\right)$ . The pair $\left(t,w\right)$ is referred to as the buyers’ type from now onwards. The marginal distribution of $w$ is $G\left(w\right)$ and the conditional distribution of $t$ given $w$ is $F\left(t|w\right)$ with the corresponding densities $g\left(w\right)$ and $f\left(t|w\right)$ .

The buyer of taste $t$ obtains utility $tq-p$ when buying quality $q$ and paying price $p$ . Suppose as in [4] that the seller incurs zero cost. The following is assumed, the reason for which is merely to assure that in Lemma 2, Equation (5) is always valid (see Th.1 in [4] ).

$\stackrel{\xaf}{t}\le \stackrel{\xaf}{w}.$ (1)

The buyer of the highest taste $\stackrel{\xaf}{t}$ obtains utility $\stackrel{\xaf}{t}-p$ for the highest quality $q=1$ , the highest acceptable price of which, reservation price, is $\stackrel{\xaf}{t}$ . The assumption ensures that the buyer with the highest budget can pay the price.

3. The Mechanism

The non-linear price scheme $\tau \left(q\right)$ is defined as a mapping of the space $Q$ to the price space $R$ . Note that it is an indirect mechanism since the type space here is $T\times W$ .

The canonical mechanism is defined so that it associates the quality and price only with the buyer’s taste as in the standard setting while ignoring the budget constraint:

$\left(q,p\right):T\to Q\times R.$

It is yet another indirect mechanism but very familiar to us in literature for decades. Let us define as usual:

Definition 1. The canonical mechanism
$\left(q\left(t\right),p\left(t\right)\right)$ is weakly feasible^{2} if and only if

$tq\left(t\right)-p\left(t\right)\ge tq\left(\stackrel{\u02dc}{t}\right)-p\left(\stackrel{\u02dc}{t}\right)\text{forany}t,\stackrel{\u02dc}{t}\in T$ (WIC)

$tq\left(t\right)-p\left(t\right)\ge 0\text{on}T.$ (WIR)

Let us turn to the direct mechanism in the two-dimensional setting, which is a mapping:

$\left(q\left(t,w\right),p\left(t,w\right)\right):T\times W\to Q\times R.$

Feasibility in this multi-dimensional mechanism is expressed as follows:

Definition 2. The direct mechanism $\left(q\left(t,w\right),p\left(t,w\right)\right)$ is strongly feasible if and only if

$p\left(t,w\right)\le w\text{forany}\left(t,w\right)\in T\times W,$ (SBC)

$\begin{array}{l}tq\left(t,w\right)-p\left(t,w\right)\ge tq\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)-p\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)\\ \text{forany}\left(t,w\right)\text{and}\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)\in T\times W\text{suchthat}p\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)\le w.\end{array}$ (SIC)

$tq\left(t,w\right)-p\left(t,w\right)\ge 0\text{on}T\times W.$ (SIR)

(SIC) induces truth-telling and (SIR) participation whereas (SBC) ensures that the buyer can actually purchase the quality assigned.

The seller’s aim is to construct a strongly feasible mechanism which maximizes the expected revenue $Ep\left(t,w\right)$ .

The revelation principle asserts that the outcome of an indirect mechanism is realized by a direct mechanism. Said contrariwise, an indirect mechanism might suffer sub-optimality compared to a direct mechanism [4] , nonetheless, showed the following result and resorted to a non-linear price scheme instead of a direct mechanism to maximize the seller’s revenue (see also [5] for the proof^{3}).

Lemma 1. Given any strongly feasible direct mechanism
$\left(q\left(t,w\right),p\left(t,w\right)\right)$ there exists a non-linear price scheme
$\tau :Q\to R$ such that^{4}

$\text{itiscontinuous,strictlyincreasing,convexand}\tau \left(0\right)=0\text{aswellas}0\le {{\tau}^{\prime}}_{+}\le \stackrel{\xaf}{t},$ (2)

and further that for all $\left(t,w\right)$

$\tau \left(y\right))\ge p\left(t,w\right)$ (3)

where

$y\in \underset{xs.t.\text{\hspace{0.05em}}\tau \left(x\right)\le w}{\mathrm{arg}\mathrm{max}}tx-\tau \left(x\right).$ (4)

Note that the outcome of a non-linear price scheme given in the lemma is realized by a strongly feasible mechanism due to the revelation principle. The lemma, therefore, asserts that the revenue of an optimal^{5} strongly feasible me- chanism is attained by a non-linear price scheme.

It shows that a weakly feasible mechanism can replicate the quality-price allocation of a strongly feasible mechanism, which basically amounts to proving that the former offers at least the same variety of qualities by the latter. In general, it is not such an easy task for a strongly feasible mechanism-which [5] deal with-but in the case of an optimal strongly feasible mechanism, one can construct a canonical mechanism which replicates the quality-price allocation of the former by way of the corresponding optimal non-linear price scheme. Due to $T=\left[0,\stackrel{\xaf}{t}\right]$ and (1), one obtains:

Lemma 2. (Che and Gale). Assume that for each $w$ , $H\left(t|w\right):=1-F\left(t|w\right)-tf\left(t|w\right)$ is strictly decreasing in $t$ . Then, the optimal strong mechanism is implemented by the non-linear price scheme $\tau \left(x\right)$ which satisfies (2) and

$-{\tau}^{\u2033}\left(x\right)\left\{{\displaystyle {\int}_{\tau \left(x\right)}^{\stackrel{\xaf}{w}}}\frac{\partial H\left({\tau}^{\prime}\left(x\right)|w\right)}{\partial {\tau}^{\prime}\left(x\right)}g\left(w\right)\text{d}w\right\}={\tau}^{\prime}{\left(x\right)}^{2}f\left({\tau}^{\prime}\left(x\right)|\tau \left(x\right)\right)g\left(\tau \left(x\right)\right)$ (5)

This condition ensures that $\tau $ has a second derivative: hence we actually have a derivative ${{\tau}^{\prime}}_{+}={\tau}^{\prime}$ for the optimal strong mechanism. A second observa- tion is that $\tau $ is strictly convex since otherwise ${\tau}^{\u2033}\left(x\right)=0$ at some $x$ and Equation (5) leads to ${\tau}^{\prime}\left(x\right)=0$ , which is contradictory to (2).

Let us now turn to the construction of a canonical mechanism which repli- cates the agent’s quality (thus price) choice faced to the optimal direct me- chanism. Suppose that the optimal direct mechanism is given as well as the corresponding non-linear price scheme as in lemma 2. Let us define the maxi- mizer of utility:

$\underset{x\in Q}{\mathrm{max}}tx-\tau \left(x\right).$ (6)

There are three possible cases for this maximization.

(1) First case: If $t<{\tau}^{\prime}\left(0\right)$ ,

then, the utility maximizer is $x=0$ and one defines ${q}^{\ast}\left(t\right):=0$ .

(2) Second case: If there exists $x$ such that $0=t-{\tau}^{\prime}\left(x\right)$ , it is unique due to strict convexity. Then, one defines ${q}^{\ast}\left(t\right):=x$ .

(3) Third case: If $t>{\tau}^{\prime}\left(1\right)$ ,

the maximizer is $x=1$ . Then, define ${q}^{\ast}\left(t\right):=1$ .

Define now a canonical mechanism by $\left({q}^{\ast}\left(t\right),{p}^{\ast}\left(t\right)\right):=\left({q}^{\ast}\left(t\right),\tau \left({q}^{\ast}\left(t\right)\right)\right)$ . Then, it satisfies (WIC) just by construction of ${q}^{\ast}\left(t\right)$ ―through (6)―and also

(WIR) due to $\tau \left(0\right)=0$ . It is, thus, weakly feasible. Due to $0\le {{\tau}^{\prime}}_{+}\left(x\right)\le \stackrel{\xaf}{t}$ on $\left[0,1\right]$ , one can always find $t\in T$ such that $t={\tau}^{\prime}\left(x\right)$ for any $x\in Q$ . In other words, for any $x$ , there is a buyer of taste $t$ for whom $x$ was a utility maximizer and an inner solution (Second case above). Thus, one obtains that $q\left(T\right)=\left[0,1\right]$ : the canonical mechanism constructed covers the whole quality range.

Now consider a buyer of $\left(t,w\right)$ . If $p\left(t\right)\le w$ , he will indeed buy $q\left(t\right)$ . Otherwise, while willing to do so, he cannot afford that quality and will choose $q\left({t}^{\prime}\right)$ such that ${t}^{\prime}<t$ and pays his whole budget $p\left({t}^{\prime}\right)=w$ because his utility function in (6) is strictly concave. These choices are identical to those when the buyer faces the non-linear scheme.

Due to Lemma 1, therefore, one obtains:

Proposition 1. A weakly feasible canonical mechanism implements the quality- price allocation of an optimal strongly feasible direct mechanism.

Let us turn to the case of a direct mechanism in general―not revenue-maxi- mizing optimal. Given a strongly feasible mechanism, consider an outperform- ing non-linear price scheme, the existence of which is assured by Lemma 1. Existence is, however, no longer assured of the derivative ${\tau}^{\prime}$ let alone strict convexity of $\tau $ (see the remark just after Lemma 2). The quality-price choice by any agent facing this non-linear price scheme is in turn realized by some strongly feasible mechanism by virtue of the revelation principle. Let us try to replicate this quality-price choice with a canonical mechanism according to (6).

The difficulty in constructing a canonical mechanism implementing a direct mechanism in this case―or the corresponding price scheme alike―consists in the fact that one may not be able to provide the whole quality range offered by the non-linear price scheme (i.e., $q\left(T\right)\ne Q=\left[0,1\right]$ ). Then, the canonical mecha- nism might not provide the qualities which some buyers would pick with the non-linear price scheme: hence failure of implementation.

Lemma 1 does not guarantee the existence of the first or second derivative of
$\tau $ but their existence is not an essential point here. If they do not exist, the same argument applies by replacement of
${\tau}^{\prime}$ with its subdifferential.^{6}

For Cases (1) and (3) of corner solutions, there is no problem. We repeat the same process. The problem is Case (2) of inner solutions. Suppose
$\tau $ is not strictly convex but just convex by Lemma 1. Then, there might be an interval of maximizers
$\left[x,y\right]$ for some
$t$ ’s due to convexity. Now, our maximizer for
$t$ is a multi-valued function
$K\left(t\right)$ but a canonical mechanism is a single-valued function. One has to assign one quality to each
$t$ . If we assign some quality
$z\in \left[x,y\right]$ to each type who has multiple utility maximizers and build
$q\left(t\right)$ , it is quite probable that
$q\left(T\right)$ has some holes in
$Q$ , i.e.,
$q\left(T\right)\ne Q$ . Technically speaking, the maximizer of Equation (6),
$K\left(t\right)$ , is a multi-valued (set-valued) function and there does not always exist a single-valued continuous canonical mechanism^{7} such that
$q\left(t\right)\in K\left(t\right)$ .^{8}

Supported

This work was supported by JSPS KAKENHI Grant Number JP16K03545.

NOTES

^{1}As a matter of course, a canonical mechanism here has no bearing on Maskin’s one in literature.

^{2}We use the qualification of “weak” in order to avoid confusion with feasibility of a direct mechanism.

^{3}Although [4] states the result with a weakly increasing
$\tau $ , strict increase is evident by its definition. In fact, it is crucial to our purpose. See [5] .

^{4}
${{\tau}^{\prime}}_{+}$ stands for the largest subgradient or equivalently the right derivative (see [6] ).

^{5}Throughout the paper, an optimal mechanism stands for the seller's expected revenue-maximizing mechanism.

^{6}See [6] .

^{7}See [7] or [8] for instance.

^{8}If there exists,
$q\left(T\right)=Q$ is obvious since
$T$ is connected.

References

[1] Armstrong, M. (1996) Multiproduct Nonlinear Pricing. Econometrica, 64, 51-75.

https://doi.org/10.2307/2171924

[2] Rochet, J.C. and Chone, P. (1998) Ironing, Sweeping, and Multidimensional Screening. Econometrica, 66, 783-8268.

https://doi.org/10.2307/2999574

[3] Rochet, J.C. and Stole, L. (2003) The Economics of Multidimensional Screening. In: Dewatripont, M., Hansen, L. and Turnovski, S., Eds., Advances in Economics and Econometrics: Theory and Applications, Eighth World Congress, Volume 1, Chapter 5, Cambridge University Press.

https://doi.org/10.1017/cbo9780511610240.006

[4] Che, Y.K. and Gale, I. (2000) The Optimal Mechanism for Selling to a Budget-Constrained Buyer. Journal of Economic Theory, 92, 198-233.

https://doi.org/10.1006/jeth.1999.2639

[5] Kojima, N. (2014) Mechanism Design to the Budget Constrained Buyer: A Canonical Mechanism Approach. International Journal of Game Theory, 43, 693-719.

https://doi.org/10.1007/s00182-013-0403-9

[6] Rockafellar, T. (1970) Convex Analysis. Princeton University Press, Princeton.

https://doi.org/10.1515/9781400873173

[7] Aubin, J.P. and Frankowska, H. (1990) Set-Valued Analysis. Birkhaauser, Boston.

[8] Aubin, J.P. and Cellina, A. (1984) Deferential Inclusion. Springer Verlag, Berlin Heidelberg.

https://doi.org/10.1007/978-3-642-69512-4