Two-Dimensional Mechanism Design and Implementability by an Indirect Mechanism

Author(s)
Naoki Kojima

ABSTRACT

This paper studies the problem on two-dimensional mechanism design where the buyer’s taste and budget are his private information. The paper investigates the problem by the method of dimension-reduction,*i.e.*, by
focusing only on the buyer’s budget and constructing an indirect mechanism:
function of one variable, the buyer’s budget. It is an approach quite antipodal
to that by Kojima [1] where he focused on the
buyer’s taste instead of his budget. It is shown that the seller does not lose any
money by adopting the indirect mechanism of this paper. In other words, the
seller’s revenue-maximizing direct mechanism is implemented by such an indirect
mechanism

This paper studies the problem on two-dimensional mechanism design where the buyer’s taste and budget are his private information. The paper investigates the problem by the method of dimension-reduction,

KEYWORDS

Multi-Dimensional Mechanism, Indirect Mechanism, Budget Constraint, Reduction of Dimension, Revelation Principle

Multi-Dimensional Mechanism, Indirect Mechanism, Budget Constraint, Reduction of Dimension, Revelation Principle

1. Introduction

The present paper studies the problem in which the principal sells a variety of qualities of a commodity to agent-buyers who have a two-dimensional type, taste (or valuation) and budget. Two-dimensional private information involves inevitable technical difficulties inherent in multi-dimensional mechanism design pointed out by Armstrong [2] and Rochet and Chone [3] . One way to get around the difficulties is to reduce the dimension of private information. Rochet and Stole [4] list up several contexts in which the reduction of dimension is feasible without loss of generality. Note that this approach is tantamount to resorting to an indirect mechanism, which raises a fundamental issue of suboptimality. Indeed, the revelation principle states that any outcome of an indirect mechanism is realized as the one of a direct mechanism; however, its contrapositive is not generally true; hence possible suboptimality of an optimal indirect mechanism.

In analysis of the two-dimensional mechanism of our context, Che and Gale [5] employ a non-linear price scheme as an indirect mechanism and show that given a two-dimensional direct mechanism, there exists a non-linear price scheme which brings the seller a greater revenue. Kojima [1] investigates the same question by a canonical uni-dimensional indirect mechanism, i.e., quality-price function of taste which has been studied for quite a long time since the birth of screening contracts. He shows that there is a canonical indirect mechanism which, given a direct mechanism, brings about a greater revenue. They, therefore, manage to defeat the curse of the revelation principle.

The present paper examines yet another indirect mechanism on the lines of Kojima [1] . By contrast, this paper focuses upon the agent’s budget instead of his taste and constructs a uni-dimensional mechanism, i.e., function from the budget space to the quality and price spaces^{1}.

Recall that Wilson [6] pointed out that one needed accumulated purchase data of a fairly large number of different quality-price pairs so as to be able to estimate the distribution of agents’ type. It implies that the firm must have been in business for quite some time and providing a variety of qualities. Even so, purchase data will get quickly outdated in the area where technological progress is rapid and new lines of products are regularly launched^{2}. In those contexts, past purchase or customer data are of little use and one can only resort to socio-demographic data such as age, sex, income, etc. and often they can be complemented through surveys or questionnaires. In such a situation, one is bound to resort to an indirect mechanism instead of a direct mechanism^{3} which refers to data available on hand as a message space.

Besides the advantage of data collection, our indirect mechanism is rather intuitive with only one of the two pieces of information being a variable of a mechanism. Suppose that some, say technological firm launches a new product. A marketing and sales team, and a tech team get together to decide on a product line. They discuss how much customers are ready to spend for the product― budget―and what qualities to provide. Most likely, they would not talk about consumers’ taste (valuation) for quality. They would just match consumers’ budgets to qualities and then decide prices. Agents’ budgets are quite easy to obtain as socio-demographic data or through questionnaires. It has, actually, been getting easier and easier through data collection by Internet companies such as social media and e-commerce business―Amazon, Google, Facebook, Alibaba, Baidu and so forth. By contrast, customers’ taste (valuation) is much harder to measure or evaluate, especially in monetary (numeric) terms―the utility function is quasi-linear in our context.

The seller’s ultimate objective is to earn the greatest revenue, in which respect its interest is how much the buyer can afford to pay. The buyer’s taste is not as important inasmuch as by ignoring it, the seller does not lose money.

This article shows that there exists a one-dimensional indirect mechanism described above that brings the seller as great a revenue as an optimal direct mechanism. Therefore, a technological firm launching a product range in our given example will not lose any money in their business planning.

2. The Model

There are a seller and a continuum of buyers both risk-neutral. The seller has one unit of an indivisible commodity to sell of quality $q\in Q:=\left[0,1\right]$ for normalization. Alternatively, one can interpret that the seller has one unit of a divisible commodity and q is a quantity. The buyer purchases either one unit of the commodity of quality q or none. The seller values the commodity at zero. The buyer has taste t for the commodity as well as a budget w. The couple $\left(t\mathrm{,}w\right)$ takes a value in the non-empty space $T\times W$ with $T:=\left[0,\stackrel{\xaf}{t}\right]$ and $W\mathrm{:}=\left[\mathrm{0,}\stackrel{\xaf}{w}\right]$ , which is the buyer’s private information unknown to the seller. The pair $\left(t\mathrm{,}w\right)$ is referred to the buyer’s type from now onwards.

The buyer’s utility function is of quasi-linear form: taste t buyer obtains utility $tq-p$ when buying quality q and paying price p.

3. Construction of a Uni-Dimensional Mechanism

In the two-dimensional context of the present paper, the direct mechanism is defined by:

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

The direct mechanism has to satisfy the following condition so that it induces the agent’s truthful revelation.

Definition 1 (Strong implementability). The direct mechanism
$\left(q\left(t\mathrm{,}w\right)\mathrm{,}p\left(t\mathrm{,}w\right)\right)$ is strongly implementable^{4} if and only if

$p\left(t\mathrm{,}w\right)\le w\text{\hspace{1em}}\text{for}\text{\hspace{0.17em}}\text{any}\text{\hspace{0.17em}}\left(t\mathrm{,}w\right)\in T\times W,$ (SBC)

$\begin{array}{l}tq\left(t\mathrm{,}w\right)-p\left(t\mathrm{,}w\right)\ge tq\left(\stackrel{\u02dc}{t}\mathrm{,}\stackrel{\u02dc}{w}\right)-p\left(\stackrel{\u02dc}{t}\mathrm{,}\stackrel{\u02dc}{w}\right)\\ \text{for}\text{\hspace{0.17em}}\text{any}\text{\hspace{0.17em}}\left(t,w\right)\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)\in T\times W\text{\hspace{0.17em}}\text{such}\text{\hspace{0.17em}}\text{that}\text{\hspace{0.17em}}p\left(\stackrel{\u02dc}{t},\stackrel{\u02dc}{w}\right)\le w\mathrm{.}\end{array}$ (SIC)

The direct mechanism assigns a quality-price pair to a buyer of each taste and budget. The condition (SBC) ensures that the agent can indeed afford the quality assigned to him. The condition (SIC) ensures that among pairs affordable to him, $\left(t,w\right)$ buyer will indeed choose a pair assigned to his type.

The participation constraint assures that the agent will actually purchase the quality assigned.

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

The revelation principle ensures that the outcome of an indirect mechanism is brought into effect by a direct mechanism; hence justification that most of mechanism design literature focuses on a direct mechanism. The opposite to this fact, however, is not true in general. From the point of view of revenue earning, it implies that resorting to an indirect mechanism, the seller might as well make less revenue.

This paper aims to show that there does exist an indirect mechanism which does the seller as well as a direct mechanism. In particular, the optimal direct mechanism-direct mechanism bringing in the greatest revenue-is implemented by an indirect mechanism. The indirect mechanism to be examined to that end is the following: the weak mechanism is defined as a map

$\left(q\mathrm{,}p\right)\mathrm{:}W\to Q\times R\mathrm{.}$

That is, the principal constructs an indirect mechanism by only taking account of the agents’ budgets while ignoring differences in taste. Later below, we will construct a concrete weak mechanism to realize our objective. It is, however, clear that direct comparison between a direct and a weak mechanism is rather cumbersome considering that a strongly implementable mechanism carries conditions, (SBC) and (SIC). The paper gets around the difficulty via a non-linear price scheme. It is shown first―Che and Gale [5] ―that given a strong mechanism, there exists a non-linear price scheme which brings the seller a weakly greater revenue. Next, one goes ahead to show the existence of a weak mechanism which achieves the same outcome as the non-linear price scheme. The following is the first step.

Lemma 1. Given the direct mechanism $\left(q\left(t\mathrm{,}w\right)\mathrm{,}p\left(t\mathrm{,}w\right)\right)$ satisfying (SBC), (SIC) and (SIR), there exists a non-linear price scheme, i.e. $\tau \mathrm{:}Q\to R$ such that

$\text{it}\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\text{continuous,}\text{\hspace{0.17em}}\text{strictly}\text{\hspace{0.17em}}\text{increasing,}\text{\hspace{0.17em}}\text{convex}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}\tau \left(0\right)=0\text{,}$ (1)

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

$\tau \left(y\right)\ge p\left(t\mathrm{,}w\right)$ (2)

where

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

Proof. See Lemma 1 in Che and Gale [5] or Kojima [1] for strict increase.

,

The revelation principle asserts that the outcome of a non-linear price scheme is realized by a direct mechanism since a non-linear price scheme is an indirect mechanism.

Let a direct mechanism $\left(q\left(t\mathrm{,}w\right)\mathrm{,}p\left(t\mathrm{,}w\right)\right)$ satisfying (SBC), (SIC) and (SIR) be given as well as the corresponding non-linear price scheme $\tau \left(x\right)$ in the above lemma satisfying (1). One can construct a “weak” mechanism which implements quality-price choices by all types of agents faced with the corresponding non-linear price scheme in the following way.

Let us define the “weak mechanism” by

$q\left(w\right):={\tau}^{-1}\left(w\right),\text{\hspace{1em}}p\left(w\right):=\tau \left(q\left(w\right)\right)=w.$ (3)

$q\left(w\right)$ is obviously concave, strictly increasing and continuous due to (1) and thus it follows easily that

$q\left(W\right)={\tau}^{-1}\left(W\right)=\left[0,q\left(\stackrel{\xaf}{w}\right)\right]=\left\{x|\tau \left(x\right)\le \stackrel{\xaf}{w}\right\}$ (4)

Whatever t an agent is, the qualities that he can buy faced with the non-linear price scheme $\tau $ are of necessity in $\left\{x|\tau \left(x\right)\le \stackrel{\xaf}{w}\right\}=q\left(W\right)$ . Otherwise, they are beyond his budget. It is, thus, clear that the weak mechanism provides all the qualities that the agent can afford with the non-linear price scheme. In addition, the price which an agent pays for a quality with the weak mechanism is the same for that quality with the non-linear price scheme, by virtue of the definition (3).

One accordingly obtains that along with lemma 1 and the revelation principle:

Proposition 1. Given a direct mechanism $\left(q\left(t\mathrm{,}w\right)\mathrm{,}p\left(t\mathrm{,}w\right)\right)$ satisfying (SBC), (SIC) and (SIR), there exists a weak mechanism defined by (3) which provides a weakly greater revenue to the seller than a direct mechanism. In particular, there exists a weak mechanism which provides the same revenue as a profit-maximizing optimal direct mechanism.

One caution that one should bear in mind is that since the weak mechanism is an indirect mechanism, an agent-buyer with budget w will not necessarily select $\left(q\left(w\right)\mathrm{,}p\left(w\right)\right)$ because his taste t is totally left out of consideration in construction of the weak mechanism.

Let us see, then, what quality an agent of type $\left(t\mathrm{,}w\right)$ indeed chooses. Given some $\left(t\mathrm{,}w\right)$ , consider:

$K\left(w\right)\mathrm{:}=\underset{x\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\tau \left(x\right)\le w}{\mathrm{arg}\mathrm{max}}tx-\tau \left(x\right)=q\left(\stackrel{\u02dc}{w}\right)$

where $\stackrel{\u02dc}{w}:=\underset{{w}^{\prime}\le w}{\mathrm{arg}\mathrm{max}}tq\left({w}^{\prime}\right)-p\left({w}^{\prime}\right)=\underset{{w}^{\prime}\le w}{\mathrm{arg}\mathrm{max}}tq\left({w}^{\prime}\right)-{w}^{\prime}.$

There are three cases for this maximization^{5}.

The first two cases result from ^{6}

$\overline{)\exists}{w}^{\prime}\le w\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\in t\partial q\left({w}^{\prime}\right)-1$

In other words, the two cases are those of boundary solutions.

(1) Type
$\left(t\mathrm{,}w\right)$ chooses
$\left(q\left(0\right),0\right)=\left(0,0\right)$ ^{7}:

$\text{For}\text{\hspace{0.17em}}\forall {w}^{\prime}\le w\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0>t\partial q\left({w}^{\prime}\right)-\mathrm{1;}$

this leads, due to concavity, to

$0>t\partial q\left(0\right)-1.$

(2) Type $\left(t\mathrm{,}w\right)$ chooses $\left(q\left(w\right)\mathrm{,}w\right)$ :

$\text{For}\text{\hspace{0.17em}}\forall {w}^{\prime}\le w\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0<t\partial q\left({w}^{\prime}\right)-\mathrm{1;}$

once again, due to concavity, it follows that

$0<t\partial q\left(w\right)-1.$

The third case arises:

$\exists {w}^{\prime}\le w\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{s}\text{.t}\text{.}\text{\hspace{0.17em}}\text{\hspace{0.17em}}0\in t\partial q\left({w}^{\prime}\right)-1$

(3) This is the case in which the agent of
$\left(t\mathrm{,}w\right)$ might not choose
$\left(q\left(w\right)\mathrm{,}p\left(w\right)\right)$ . In other words, it is when the agent is well off enough to effectively buy a quality that his taste parameter t wishes, without the budget hampering such purchase^{8}. It leads to:

$\frac{1}{t}\in \partial q\left({w}^{\prime}\right)\text{\hspace{1em}}\text{if}\text{\hspace{0.17em}}{\stackrel{\dot{}}{q}}^{-1}\left(0\right)<t<{\stackrel{\dot{}}{q}}^{-1}\left(w\right)$ (5)

where $\partial q$ is written as derivative $\stackrel{\dot{}}{q}$ since q is almost everywhere differentiable and also ${q}^{-1}\left(0\right)$ and ${q}^{-1}\left(0\right)$ are each reciprocals.

In view of the preceding paragraph, the principal’s optimization problem is to find q maximizing the revenue:

${\int}_{{\stackrel{\dot{}}{q}}^{-1}\left(w\right)}^{\stackrel{\xaf}{t}}}\text{\hspace{0.05em}}\text{d}t{\displaystyle {\int}_{0}^{\stackrel{\xaf}{w}}}\text{d}w\text{\hspace{0.05em}}wf\left(t\mathrm{,}w\right)+{\displaystyle {\int}_{{\stackrel{\dot{}}{q}}^{-1}\left(0\right)}^{{\stackrel{\dot{}}{q}}^{-1}\left(w\right)}}\text{d}t{\displaystyle {\int}_{0}^{\stackrel{\xaf}{w}}}\text{d}w\text{\hspace{0.05em}}{\stackrel{\dot{}}{q}}^{inv}\left(\frac{1}{t}\right)f\left(t\mathrm{,}w\right)$

where ${\stackrel{\dot{}}{q}}^{inv}$ is an inverse function of $\stackrel{\dot{}}{q}$ .

Unfortunately, it is not straightforward to find such an optimal q analytically. In all liklihood, one needs a numerical procedure to approximate the optimal indirect mechanism.

4. Conclusion

The paper studied an indirect mechanism in the context where agent-buyers have a one-dimensional taste parameter and a budget as private information. In addition to two indirect mechanisms by Che and Gale [5] or Kojima [1] , it has shown that there is another one which weakly outperforms a given direct mechanism in terms of revenue; hence no loss of generality due to the revelation principle.

Fund

This work was supported by JSPS KAKENHI Grant Number JP16K03545.

NOTES

^{1}Both in Cheand Gale [5] and Kojima [1] , their outperforming optimal indirect mechanisms are implemented by way of direct mechanisms on the strength of the revelation principle.

^{2}The examples are numerous: cars, computers, mobile phones, or more generally, electronic goods and so forth.

^{3}In reality, not a few businesses offer tariffs only related to age such as students or senior person discount.

^{4}“S” in the tags SBC and SIC stands for strong.

^{5}For maximization, see Rockafellar [7] .

^{6
$\partial q\left(w\right)$ } denotes a subdifferential of q at w.

^{7
$\partial q\left({w}^{\prime}\right)$ } is generally a set. The notation that
$0>t\partial q\left({w}^{\prime}\right)-1$ signifies that
$0>tx-1$ for any
$x\in \partial q\left({w}^{\prime}\right)$ .

^{8}Such
${w}^{\prime}$ might not be unique.

Cite this paper

Kojima, N. (2017) Two-Dimensional Mechanism Design and Implementability by an Indirect Mechanism.*Theoretical Economics Letters*, **7**, 1595-1601. doi: 10.4236/tel.2017.76107.

Kojima, N. (2017) Two-Dimensional Mechanism Design and Implementability by an Indirect Mechanism.

References

[1] 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

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

https://doi.org/10.2307/2171924

[3] Rochet, J. and Chone, P. (1998) Ironing, Sweeping, and Multidimensional Screening.*Econometrica,* 66, 783-826.

https://doi.org/10.2307/2999574

[4] Rochet, J. 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,* Vol. 1, Cambridge University Press.

[5] Che, Y. 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

[6] Wilson, R. (1993) Nonlinear Pricing. Oxford University Press, New York.

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

https://doi.org/10.1515/9781400873173

[1] Kojima, N. (2014) Mechanism Design to the Budget Constrained Buyer: A Canonical Mechanism Approach.

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

[2] Armstrong, M. (1996) Multiproduct Nonlinear Pricing.

https://doi.org/10.2307/2171924

[3] Rochet, J. and Chone, P. (1998) Ironing, Sweeping, and Multidimensional Screening.

https://doi.org/10.2307/2999574

[4] Rochet, J. and Stole, L. (2003) The Economics of Multidimensional Screening. In: Dewatripont, M., Hansen, L. and Turnovski, S., Eds.,

[5] Che, Y. and Gale, I. (2000) The Optimal Mechanism for Selling to a Budget Constrained Buyer.

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

[6] Wilson, R. (1993) Nonlinear Pricing. Oxford University Press, New York.

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

https://doi.org/10.1515/9781400873173