Int J Game Theory DOI 10.1007/s00182-013-0403-9

Mechanism design to the budget constrained buyer: a canonical mechanism approach Naoki Kojima

Accepted: 26 December 2013 © Springer-Verlag Berlin Heidelberg 2014

Abstract The present paper studies the problem on multi-dimensional mechanisms in which the buyer’s taste and budget are his private information. The paper investigates the problem by way of a canonical mechanism in the traditional one-dimensional setting: function of one variable, the buyer’s taste. In our multi-dimensional context, this is an indirect mechanism. The paper characterizes the optimal canonical mechanism and shows that this approach loses no generality with respect to the direct (multi-dimensional) mechanism. Keywords Multi-dimensional mechanism · Indirect mechanism · Budget constraint · Revelation principle · Taxation principle JEL Classification

D82 · D86

1 Introduction The present paper considers the optimal revenue-maximizing mechanism by the seller of a variety of different qualities of a commodity faced with the budget-constrained buyers1 who have taste and budget as their private information. This is an adverse selection problem in two dimensions. It is widely known that the multi-dimensional problem involves quite a few technical complications (see Armstrong 1996; Rochet and Chone 1998). One method for circumventing the difficulties is to reduce the dimension of private information (Rochet and Stole 2003).

1 In the author’s view, it is natural that agents are more or less constrained in their budgets. See discussion in Che and Gale (1998) for the possible sources of the constraint.

N. Kojima (B) Otaru University of Commerce, 3-5-21 Midori, Otaru 047-8501, Japan e-mail: [email protected]

123

N. Kojima

Recall that the revelation principle asserts that any outcome implemented by an indirect mechanism can be effectuated by a direct incentive compatible mechanism. Now, the reduction of dimension necessarily involves the use of an indirect mechanism and thus, in general, the principal may obtain a lower value for his objective function.2 Rochet and Stole (2003) give some examples in which the principal loses nothing by resorting to an indirect mechanism. Monteiro and Page (1998) dealt with the problem of the setting of this paper with the approach of a direct mechanism of full dimension with a very general principal’s and an agent’s utility. They focused upon the existence of the optimal solution and thus came short of characterizing the optimal solution.3 In our multi-dimensional setting, the direct mechanism is rather complicated to analyze and does not allow easy characterization of an optimal solution. Che and Gale (2000), therefore, resorted to the reduction of dimension as in Rochet and Stole (2003) by means of a non-linear price scheme—an indirect mechanism. They also showed that by using a non-linear price scheme, the principal could achieve the same level of revenue as the optimal direct mechanism. Thus far, the non-liner price scheme is the only indirect mechanism ever considered. This article investigates the effectiveness of another indirect mechanism very familiar by now, i.e., the canonical one-dimensional mechanism—a map from the taste space to the quality and price space—in the multi-dimensional setting.4 Research on mechanism design started with the case of one taste parameter (one-dimensional private information) and focused on this canonical mechanism5 and the facts and results obtained are numerous. One advantage of the approach of this paper is that it enables us to directly compare the structures of an optimal canonical mechanism in the standard one-dimensional setting without the budget constraint and those in the multi-dimensional context. Thus, one can highlight modifications to be brought about to a canonical mechanism by the very existence of the budget constraint and put them in contrast with a good many properties which have been accumulated in the past literature on mechanism design. The delicate question to arise, in turn, is: being indirect, does our mechanism lose any generality? It is shown in the last section that the optimal canonical mechanism does not lose any generality and realizes the same expected profit as the twodimensional optimal direct mechanism. In our two-dimensional context, since our canonical mechanism does not include the buyer’s budget, it may well happen that the buyer does not have a sufficient budget to buy a quality destined for his taste. Then, he is obliged to buy another quality within

2 In other words, the contrapositive of the revelation principle is not generally true. 3 There are quite a few papers on budget-constrained bidders in the auction setting. This article, however,

only focus on works in the setting of a principal-seller and agent-buyers. 4 While being a direct mechanism if taste is the only private information, the canonical mechanism is an indirect mechanism in the context where there is another private information, or budget. 5 The canonical mechanism here has naturally nothing to do with Maskin’s canonical mechanism in implementation theory. The author uses the same term in this paper because there is no concern for confusion due to the contextual difference.

123

Mechanism design to the budget constrained buyer

his budget. The paper scrutinizes how the agent makes a decision of purchase and characterizes the seller’s optimal canonical mechanism. It is found that if not well-off enough to pay the price of a quality assigned to him, the agent buys the highest quality, the price of which is also the highest within his budget. A finding on the side of the seller is as follows. If there is no budget constraint, he simply can focus upon how to extract rent from agents without considering their affordability for designated qualities for them. By contrast, when the agents have budget constraints, the seller has to take account of what quality an unwealthy agent purchases and designs a mechanism which induces that agent to spend as much money as possible. The way to do it is to provide a wider range of price than in the case with no budget constraint and this, in turn, implies proffering a wider variety of quality. By offering more qualities and prices, the seller manages to get a buyer to purchase the quality the price of which is the closest possible to his budget. At the optimum, the principal offers a continuous mechanism (continuous quality and price), whereby he induces an agent to spend his entire budget even though the latter is not well-off enough. The equation characterizing the optimal non-linear price scheme in Che and Gale (2000) is a second order integro-differential equation and its complex form does not allow intuitive interpretation of the equation. By contrast, the approach of this paper enables us to visualize a classic trade-off well known in the literature, faced by the principal, between rent extraction and concession of informational rent (see Laffont and Martimort 2001 for instance). This important trade-off—in the multi-dimensional context as well as in the traditional uni-dimensional one—can be brought to light by virtue of the use of the canonical mechanism. In spirit, one could possibly see the approach of this paper similar to the ones of Rochet and Stole (1997) and Rochet and Stole (2002). They studied the optimal selling mechanism of duopolistic sellers in Hotelling’s environment where buyers have private information of their taste and distance from the sellers. Since the private information is two-dimensional, as a direct mechanism approach it will be natural to consider the scenario that the sellers design an incentive scheme as a map from the taste and distance to the quality-price pair. Instead, Rochet and Stole (1997) took an alternative approach, in which the sellers make a price mechanism which associates only the buyers’ taste with a quality-price pair while regarding the distance as a random variable. The canonical mechanism of the present paper, in the similar manner, takes in only the buyer’s taste. If the budget is simply viewed to be a random variable, our approach is identical to that by Rochet and Stole (2002). This paper, however, takes a step further by examining how robust our approach is in comparison with direct mechanisms when the budget is the agent’s private information. In addition to the papers aforementioned, Richter (2011) also resorted to a nonlinear price scheme in order to deal with the same problem as ours on the assumption that taste and budget are independently distributed. With additional assumptions, he shows that the profit-maximizing price scheme is realized with a uniform price and this price scheme does not lose generality with respect to the optimal direct mechanism, i.e., achieves the same revenue. In a slightly different context with a multi-product firm and buyers of multi-dimensional taste (but no budget constraint), Armstrong

123

N. Kojima

(1999) shows that the profit-maximizing mechanism is closely approximated with an affine price scheme if the number of products is very large. In the context similar to Armstrong (1999), Manelli and Vincent (2006) consider a multi-product monopolist’s price scheme with bundling. They derive a necessary condition for such an optimal price scheme and shows in what environment the optimal price scheme does not lose generality in respect of the optimal direct mechanism. What distinguishes the present paper from the others is that the latter examine the question via a non-linear price scheme whereas this article analyzes it with a canonical mechanism in order to highlight differences between structures of optimal canonical mechanisms in the classic one-dimensional and the present two-dimensional contexts. In the next section, the model is presented. Section 3 formally describes the seller’s mechanism. Section 4 treats, as a reference case, the selling mechanism with no budget constraint. The case of the budget-constrained buyer is dealt with in Sect. 5. In Section 6, we make comparison between the approach of canonical mechanisms and the one of direct mechanisms. 2 The model There is a seller and a continuum of buyers who are both risk-neutral. The seller has one unit of an indivisible commodity to sell of quality q such that q ∈ Q := [0, 1] for normalization. Alternatively, it can be interpreted so 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 and budget w, both of which take values in R+ . The couple (t, w) is distributed according to the density g(t, w) continuous and positive on its non-empty support, which is T × W where T := [0, t] and W := [0, w]. (t, w) is the buyer’s private information. The seller only knows the density g(t, w). Name the pair (t, w) the buyer’s type from now onwards. Let us denote the function derived from g(t, w) by G(t, w): w G(t, w) :=

g(t, x)d x. 0

G(t, w) is the probability that the buyer of taste t has a budget smaller than w. The buyer’s utility function is assumed to be of quasi-linear form. Thus, buying quality q and paying price p, taste t buyer obtains utility, tq − p.6 We assume that t ≤ w. (1) The buyer of the highest taste t obtains the utility t − p for the highest quality q = 1 and the price p. The assumption indicates that with the highest budget, he can pay the 6 This form of utility function, i.e., linear in taste is assumed in all studies cited thus far except Monteiro

and Page (1998) and Armstrong (1999).

123

Mechanism design to the budget constrained buyer

highest price t, for which he obtains zero utility (for the price higher than that, buyer t simply chooses not to purchase). 3 The mechanism In adverse selection literature, there are two approaches, one of which is a direct mechanism approach and the other a non-linear pricing (indirect mechanism) approach.7 By extending Wilson (1993), let us sketch the latter approach first. The non-linear price scheme τ (q) is defined as a map of the space Q to the price space R. Suppose that τ (q) is lower semi-continuous and almost everywhere differentiable. The buyer of type (t, w) purchases a quality which satisfies8 max

q∈{x|τ (x)≤w}

tq − τ (q).

(2)

One can write the measure of the buyers of tastes who purchase a quality higher than q: M(τ (q), q) := Prob {(t, w)|(∃x ≥ q)(∀y < q s.t. τ (y) ≤ w) t y − τ (y) ≤ t x − τ (x), τ (x) ≤ w} . If the programme (2) is quasi-concave, one obtains   M(τ (q), q) = Prob (t, w)|t ≥ τ  (q), τ (q) ≤ w =: M(τ (q), τ  (q), q). It follows immediately that



w  t

M(τ (q), τ (q), q) =

g(t, w)dwdt. τ (q) τ  (q)

The seller maximizes the following expected profits 1

τ  (q)M(τ (q), τ  (q), q)dq.

0

This depends on τ as well as τ  . Therefore, contrary to the case where there is no budget constraint, one cannot perform pointwise maximization (see Wilson 1993) and 7 Wilson (1993) refers to the second as a demand profile approach. 8 In what follows, the prime to a function stands for a derivative of the function and the double prime a second derivative and so forth. Thus, τ  (q) is a derivative of τ (q).

123

N. Kojima

calculation involves quite a few complications. Che and Gale (2000) resorted to this formalization to reduce the dimension in our two-dimensional problem. The standard mechanism design approach consists in parameterizing the buyer with his type (t, w) and assigns a quality-price pair to each type, what is called a direct mechanism. In this section, we take a weaker approach, in which an indirect mechanism associates the quality and price only with the buyer’s taste. In other words, we construct a mechanism as in the standard setting of a one-dimensional preference parameter. Formally, the canonical mechanism is defined as a map (q, p) : T → Q × R. This is an indirect mechanism; for the domain of a canonical mechanism is T while the type space is T × W . In order to induce the buyer of taste t to choose the pair (q(t), p(t)) and divulge his real taste, the mechanism has to satisfy the incentive compatibility constraint. Definition 1 The canonical mechanism (q(t), p(t)) is weakly implementable9 if and only if tq(t) − p(t) ≥ tq(t˜) − p(t˜) for any t, t˜ ∈ T.

(WIC)

Moreover, in order to induce the buyer to actually purchase, the seller has to assure him of minimum utility as the participation (or individual rationality) constraint. Normalizing reservation utility to zero, we set the participation constraint:10 u(t) := tq(t) − p(t) ≥ 0

on T.

(WIR)

Facing a weakly implementable canonical mechanism which ignores the budget constraint, the buyer of taste t may not be able to purchase (q(t), p(t)) if he is not well off enough. The next Sect. 4 addresses this issue. Remark 1 Notice that the usage of qualifications “weak” and “strong” (in Sect. 5) for a mechanism in this paper are different from that in Che and Gale (2000). In this paper, “weak” is used for a canonical—thus, indirect-mechanism and “strong” is used for a direct mechanism. By contrast, Che and Gale (2000) use both the qualifications for a direct mechanism. Specifically, they consider two cases, in one of which the seller can demand a deposit from buyers in advance so that the latter cannot lie about their budgets upwards and in the other the seller cannot demand a deposit. The authors qualify the incentive compatibly constraint of the former as weak and the latter as strong. The present paper deals with the latter case of theirs. Also, the regularity condition on the type distribution in this paper, Assumption 1 is different from that in Che and Gale (2000). It reflects the fact that this paper examines 9 The qualification of weak is used so as not to be confused with the implementability of a direct mechanism

to follow. 10 W in WIR stands for weak.

123

Mechanism design to the budget constrained buyer

the case of no budget constraint as a benchmark—canonical context—at the beginning of the next section whereas they do the case of the principal knowing the budget. Parallel to it, Assumption 3 in this article is different from that in their paper since the present paper resorts to a canonical mechanism while they a non-linear price scheme. As is standard, instead of the quality-price pair (q(t), p(t)), one sets up the problem with the quality-utility pair (q(t), u(t)), which is the advantage of the approach of this paper. Lemma 1 If the weak mechanism (q(t), p(t)) is weakly implementable, the following conditions are satisfied;11 u(t) is absolutely continuous, q(t) is non-decreasing,

(3) (4)

q(t) = u(t) ˙ a.e.

(5)

Conversely, given q(t) and u(t) which satisfies (3), (4) and (5), the weakly implementable mechanism (q(t), p(t)) can be constructed, by putting p(t) = tq(t) − u(t).

(6)



Proof See Rochet (1985).

In the perfect information case where t is observable and there is no budget constraint, the seller maximizes his profit, subject to the participation constraint tq− p ≥ 0, which leads to the first best efficient allocation, q = 1, p = t and u = 0. 4 Budget constraint As a reference case, consider first the standard setting in which there is no budget constraint and thus only taste is private information. Due to the Assumption (1), it is t equivalent to the support of g(t, w) being T × {w}: 0 g(t, w)dt = 1. In this case, the buyer can indeed purchase a quality designated for him by a canonical mechanism satisfying (WIC). The seller, thus, maximizes with respect to q and u his expected profit t

t p(t)g(t, w)dt =

0

(tq − u)g(t, w)dt, 0

subject to 0 ≤ q ≤ 1 and the implementability constraints (3), (4), (5) and the participation constraint 0 ≤ u(0).12 11 a.e. stands for almost everywhere. 12 (WIR) can be replaced by 0 ≤ u(0) due to (5).

123

N. Kojima

As usual, one ignores the monotonicity of q and verifies that it is satisfied at the end. Writing the optimal solution (q ∗ , u ∗ ), one easily obtains that u ∗ (0) = 0 from the transversality condition and also that the Hamiltonian is written as H (t, q, u, λ) = (tq − u)g + λq. where λ is an absolutely continuous adjoint variable. Let us introduce an assumption. t Assumption 1 g(t, w)t + 0 g(t, w)dt − 1 is strictly increasing. Proposition 1 Suppose that Assumption 1 is satisfied. Then, there exists the unique tˆ ∈ (0, t) such that g(tˆ, w)tˆ +

 tˆ

g(t, w)dt − 1 = g(tˆ, w)tˆ −

t g(t, w)dt = 0,

(7)

tˆ

0

and the optimal solution and price are as follows,    ∗ (0, 0, 0) if t ∈ [0, tˆ], ∗ ∗ q (t), u (t), p (t) = ˆ ˆ (1, t − t , t ) if t ∈ [tˆ, t].   (0, q, u ∗ , λ) < 0 and ∂∂qH t, q, u ∗ , λ > 0. Therefore, by Assumption 1, there is a unique tˆ satisfying ∂∂qH (tˆ, q, u ∗ , λ) = 0. Since the Hamiltonian is equal to   t

(tq − u)g + 0 g(t, w)dt − 1 q, the proposition is obvious.

Proof

∂H ∂q

In comparison with the first best allocation, one makes the standard observation in the problem on asymmetric information: inefficient quality allocation and full rent extraction at the lowest taste, and no quality distortion at the highest taste. Now, we turn to the optimal canonical mechanism with budget-constrained buyers. Let us introduce a new assumption: Assumption 2 g(t, w) is continuously differentiable on T × W . Except in Sect. 5, this is assumed throughout the paper whereas Assumption 1 is unnecessary. A main question to be asked is what quality the buyer chooses if he cannot afford one assigned for his taste on account of his limited budget. Given a weakly implementable mechanism, the buyer of type (t, w) actually purchases the quality-price pair (q(t), p(t)) if p(t) ≤ w. On the contrary, if the price is too high, p(t) > w, the buyer is bound to choose another quality within his budget. Type (t, w) buyer’s decision upon purchase is determined by: max

t  s.t. p(t  )≤w

123

tq(t  ) − p(t  ).

Mechanism design to the budget constrained buyer

To express the seller’s maximization programme, one has to spell out what quality a buyer purchases when he has an insufficient budget. Let us begin with a straightforward observation, the proof of which is in the Appendix. Lemma 2 If a mechanism (q(t), p(t)) is weakly implementable, p(t) is nondecreasing. Along with (4), the lemma implies that a higher quality is coupled with a higher price. Thus, taste t buyer unable to afford the assigned quality is obliged to choose a lower quality designated for a lower taste. If the price is continuous, the buyer’s quality choice can be expressed in a simple manner as will be seen. The discontinuous price involves a little complication. Notice, however, that given a weakly implementable mechanism, the price p(t) is almost everywhere differentiable by Lemma 2. With a tiny condition on p(t), one obtains the following proposition. Proposition 2 Let (q(t), p(t))t∈T be a weakly implementable mechanism with p leftcontinuous. Suppose that the buyer of a given type (t, w) cannot afford the quality intended for him, namely p(t) > w. If w < p(0), the buyer cannot purchase any quality; that is, w < p(t  ) for all t  ∈ T. If p(0) ≤ w, there exists μ(w) := max{t  | p(t  ) ≤ w} and the buyer purchases the quality-price pair (q(μ(w)), p(μ(w))); i.e. μ(w) solves max

t  s.t. p(t  )≤w

tq(t  ) − p(t  ).

Moreover, {t  | p(t  ) ≤ w} = [0, μ(w)] and p(μ(w)) = max{ p(t  )| p(t  ) ≤ w}. Proof See the Appendix.



The proposition states that if the buyer is not wealthy enough to buy a quality assigned for him, he buys the highest quality within his budget and its price is also the highest that his budget allows. Provided that the price is continuous, a simpler statement can be made. Later on, we resort to the following result. Proposition 3 Let all the assumptions of the preceding proposition be satisfied except left continuity of p. Instead, assume that p is continuous. If p(0) ≤ w, μ(w) in Proposition 2 satisfies p(μ(w)) = w. Proof There exists t  such that p(t  ) = w because p is continuous and p(0) ≤ w < p(t). There also exists m := max{t  | p(t  ) = w} by continuity. Then one has μ(w) ≤ m by the monotonicity of p and m ≤ μ(w) from the definition of μ(w).



123

N. Kojima

The proposition indicates that when the price is continuous, taste t buyer with an insufficient budget purchases quality q(μ(w)), spending up to his budget. Let us next turn to the participation constraint. Given a weakly implementable mechanism, taste t buyer wealthy enough purchases (q(t), p(t)) and thus it suffices to have 0 ≤ u(t) as the participation constraint. However, if he is limited in the budget, he has to choose another quality-price pair. We need, therefore, the participation constraint which ensures that the buyer participates even if bound to choose another quality-price pair. Since taste t buyer, in that case, chooses a pair (q(t  ), p(t  )) such that t  < t, the participation constraint must guarantee that for all t and t  such that t  ≤ t, 0 ≤ tq(t  ) − p(t  ). It turns out that the standard participation constraint 0 ≤ u(t) assures this. Lemma 3 Let (q(t), p(t)) be weakly implementable. Then 0 ≤ u(t) for all t if and only if for all t and t  such that t  ≤ t, 0 ≤ tq(t  ) − p(t  ). Proof Suppose that 0 ≤ u(t) on T . Then it follows that for t and t  such that t  ≤ t, 0 ≤ u(t  ) = t  q(t  ) − p(t  ) ≤ tq(t  ) − p(t  ).



The converse is obvious.

Let us express the seller’s profit by means of Proposition 2. Suppose that a weakly implementable mechanism (q(t), p(t)) is given such that p(t) is left-continuous. It follows from the proposition that ⎧ ⎪ if w < p(0), ⎨(0, 0) tq(s)− p(s) = (q(μ(w)), p(μ(w))) if p(0) ≤ w < p(t), (8) arg max ⎪ (q(s), p(s)) s.t. p(s)≤w ⎩ (q(t), p(t)) if p(t) ≤ w, where we adopt a convention that if {s| p(s) ≤ w} is empty, the right side of (8) is equal to (0, 0). The seller obtains the following profit from taste t buyer, ⎧ ⎪ ⎨0 ( p(t), w) = p(μ(w)) ⎪ ⎩ p(t)

if w < p(0), if p(0) ≤ w ≤ p(t), if w ≥ p(t).

(9)

The formal definition of the optimal mechanism can be given now: Definition 2 The optimal canonical mechanism is a canonical mechanism which maximizes the seller’s expected profit of (9) and satisfies (WIC) and (WIR).

123

Mechanism design to the budget constrained buyer

Let us proceed, now, to express the seller’s profit by assuming that p(t) is continuous and making use of Proposition 3. Note, however, that here, we are not narrowing candidates of an optimal mechanism to continuous ones. On the contrary, it will be shown later that the optimal mechanism turns out to be actually continuous. t w By replacing p(t), we write 0 0 ( p(t), w)g(t, w)dtdw as t

⎛ ⎜ dt ⎝

tq(t)−u(t) 

⎞

w

⎟ g(t, w)(tq(t) − u(t))dw ⎠ .

g(t, w)wdw + −u(0)

0

tq(t)−u(t)

By partial integration in the first term, it turns into t

tq(t)−u(t) 



dt G(t, tq(t) − u(t))(tq(t) − u(t)) − 0

G(t, w)dw 0

+ (G(t, w) − G(t, tq(t) − u(t))) (tq(t) − u(t)) t

tq(t)−u(t) 



 G(t, w)dw .

dt G(t, w)(tq(t) − u(t)) −

=



0

(10)

0

The seller maximizes this expected profit subject to (3)–(5) and 0 ≤ u(0). The assumption of p(t) being continuous can be replaced by that of q(t) owing to (3). Let us now differentiate the objective function (10) with respect to u, which gives −G(t, w) + G(t, tq − u) ≤ 0. It follows that given an admissible pair (q, u), it will increase the value of the objective function to modify u by adding a constant in such a way that 0 ≤ u(0) binds. Note that doing so does not modify q due to (5). In consequence, one can replace 0 ≤ u(0) with u(0) = 0. The seller’s maximization programme for the optimal canonical mechanism can now be stated as follows: t max q,u

⎛ ⎝G(t, w)(tq − u) −

0

tq−u 

⎞

G(t, w)dw ⎠ dt

(11)

0

s. t. 0 ≤ q ≤ 1,

(12)

u˙ = q a.e, q is non-decreasing and continuous,

(13) (14)

0 = u(0).

(15)

123

N. Kojima

As is standard, one searches for the solution among measurable control variable q’s and absolutely continuous state variable u’s while first ignoring (14). However, if we incorporate (14) from the beginning, i.e., two conditions q˙ = z a.e. and 0 ≤ z and replace (12) with 0 ≤ q(0) and q(t) ≤ 1, the problem amounts to that of control variable z and state variables u and q. Since standard optimal control takes a state variable as absolutely continuous, the second condition in (14) is automatically satisfied. And yet this approach does not get any closer to obtaining an explicit result. Let us call the above maximization problem without (14) the relaxed problem. It will be ascertained below that the solution of the relaxed problem is indeed that of the original problem. It implies that among all the canonical mechanisms, the optimal one is continuous. First, the existence of a solution is asserted by an elementary existence theorem. Proposition 4 There exists an optimal solution for the relaxed problem. Proof Let us resort to Filippov’s existence theorem [see p. 314 of Cesari (1983)]. From (13) and (15), it follows that t u(t) =

q(s)ds ≤ t. 0

From q being non-negative, it is obtained that u is non-decreasing. One sees that u(t) ∈ [0, t], which is compact. Likewise, it is easily verified that all the conditions for the existence theorem are satisfied.

Let (q ∗ , u ∗ ) be an optimal pair of the relaxed problem and then with an absolutely continuous variable λ, one can write the Hamiltonian tq−u 

H (t, q, u, λ) = G(t, w)(tq − u) −

G(t, w)dw + λq, 0

which is concave and differentiable in q. As the necessary conditions for optimality, one obtains the following:13 

H (t, q ∗ , u ∗ (t), λ(t)) = maxq∈[0,1] H (t, q, u ∗ (t), λ(t)) λ˙ = G(t, w) − G(t, tq ∗ − u ∗ ) and λ(t) = 0 (transversality condition).

Differentiation of the Hamiltonian with respect to q gives:     ∂H  t, q, u ∗ (t), λ(t) = t G(t, w) − G t, tq − u ∗ (t) + λ(t). ∂q Let us assume the following condition throughout the section. 13 The qualification of “almost everywhere” is omitted throughout.

123

Mechanism design to the budget constrained buyer

Assumption 3 For all (t, w) ∈ T × W , ∂ t ∂t

w g(t, w)dw = G(t, w) − G(t, w) + t (G 1 (t, w) − G 1 (t, w)) ≥ 0. w

where G 1 (t, w) is the partial derivative with respect to the first variable. The assumption is satisfied, for instance, if t and w are independent and t is uniformly distributed. They ensure that the ignored conditions of the original problem, monotonicity and continuity of q(t), are satisfied for the solution of the relaxed problem. Then, one can obtain the following main result, the proof of which is relegated to the Appendix. Theorem 1 The solution of the relaxed problem satisfies (14) and thus it is the optimal canonical mechanism. There exist unique t  and t  such that 0 < t  < t  < t which are defined respectively by t  G(t  , w) −

t

⎛

dt ⎝G(t, w) − G ⎝t, tq ∗ (t) −

t

⎛

⎛

⎛

⎜ ⎜ t  ⎝G(t  , w) − G ⎝t  , t  − t −

⎛

⎛

t 

⎞⎞ q ∗ (t)dt ⎠⎠ = 0,

(16)

0

⎞⎞ ⎟⎟ q ∗ (t)dt ⎠⎠

0

dt ⎝G(t, w) − G ⎝t, t −

t 

t

t

⎞⎞ q (t)dt ⎠⎠ = 0 ∗

(17)

0

q ∗ is uniquely determined such that on (t  , t  ) ⎛

⎛

t ⎝G(t, w) − G ⎝t, tq ∗ (t) − t −

⎛

⎛

⎞⎞ q ∗ (t)dt ⎠⎠

0

dt ⎝G(t, w) − G ⎝t, tq ∗ (t) −

t

and otherwise,

t

t

⎞⎞ q ∗ (t)dt ⎠⎠ = 0

(18)

0

 0 if t ∈ [0, t  ], q (t) = 1 if t ∈ [t  , t]. ∗

Furthermore, q ∗ (t) is strictly increasing, differentiable and 0 < q ∗ (t) < 1 on

(t  , t  ).

123

N. Kojima

The standard characteristics of the one-dimensional screening contract are inherited here: inefficient quality allocation and full rent extraction at the lowest, and no quality distortion at the highest taste. The canonical mechanism allows us to put the features of an optimal mechanism in line with those in the standard setting of a onedimensional type. In other words, one can highlight the well known basic trade-off faced by the principal between rent extraction and informational rent in literature (see Mussa and Rosen 1978; Laffont and Martimort 2001 for instance). This is an advantage of our approach over that of a non-linear price scheme. Equation (16) can be rewritten as



t



t G(t , w) −

   dt G(t, w) − G t, p ∗ (t) = 0

(19)

t

The first term in (16) indicates an amount of profit increase brought by a tiny left displacement of t  (tantamount to an infinitesimal increase of quality around t  ). The reservation price of agents of taste t  is t  . Note that at t  , quality and price are zero. Thus, all the agents of type close to t  can pay a risen price corresponding to an increase of quality whatever their budgets are; hence the seller gains t  G(t  , w). The second term represents increase in informational rent borne by the seller. As well known, the buyer of higher taste gains higher informational rent. Therefore, the seller has to concede risen informational rent for all the types [t  , t] whom he serves with positive qualities. One cannot make a direct comparison between t  and tˆ in (7) since optimal control used in this section requires that the objective function be at least continuous. Note, however, that if t < w (see (1)), due to G(t, p ∗ (t)) = 0, equation (19) is reduced to 

t



t G(t , w) −

G(t, w)dt = 0 t

As a result, using the notation of the present theorem, one can rewrite (7) in the same form as the above equation. Thus, if the shape of g(t, w) here approaches that in the previous section, one can say, albeit informally, that t  goes close to tˆ. The same argument applies to the cut-off type t  in (17). Note that it can be rewritten (recall that q(t) = 1 on [t  , t]) as

t











∗



G(t , w) − G t , p (t )



t −

   dt G(t, w) − G t, p ∗ (t) = 0.

(20)

t 

The first term indicate a profit gain by a tiny left displacement of t  , which signifies increasing quality up to 1 for the agents of that marginal taste. The gain comes only from those who have budgets above p ∗ (t  ). Otherwise, they cannot afford the quality increased. The second term is a concession of additional informational rent which

123

Mechanism design to the budget constrained buyer

the principal is obliged to give up to the agents of all tastes above t  . On the interval (t  , t  ), one can make the same argument since (18) can be rewritten similarly to (20). It transpires that q ∗ is strictly increasing, thus separating tastes on (t  , t  ). However, it may not separate the tastes in actuality. It implies that q ∗ is separating only if the buyers of the tastes are wealthy enough to purchase qualities assigned to them. Otherwise, they are obliged to choose qualities within their budgets. As seen in Proposition 3, the unwealthy buyers of two different tastes and the same budget, (t, w) and (t˜, w), purchase the same quality and pay the same price w; hence bunching. At the beginning of the section, it is seen that without budget constraint, the principal proposes the highest quality or none. Here, faced with budget-constrained buyers, the seller offers a wide range of quality. By so doing, he tries to sell the buyers the highest qualities within their budgets and make them pay the highest affordable prices. Continuity of the optimal weak mechanism is sensible. By assumption, the density of type is strictly positive. If there is a jump in the price, the seller loses money by letting buyers of a positive measure pay less than their budgets. Comparison between the results with and without budget constraints underlines the role of the constraints in quality provision and discrimination by the principal. The budget constraint is yet another factor besides the classic one in adverse selection which pushes the principal towards discrimination of agents. Example 1 Suppose that (t, w) follows uniform distribution. Let us consider first the benchmark case with no budget constraint considered at the beginning of the section and assume that T × W = T × {w} = [0, 1] × {1}. It follows, then, from Proposition 1 that the optimal contract q ∗ is  ∗

q (t) =

0 if t ∈ [0, 21 ], 1 if t ∈ [ 21 , 1].

Let us turn to the case in the presence of budget constraints. Suppose that (t, w) follows uniform distribution on [0, 1]2 . Then, the optimal canonical mechanism is found by Theorem 1. Equation (18) is a fairly convoluted integro-differential equation and thus let us obtain a simple differential equation by differentiating it twice in t. As a result, one obtains the second order equation: 4 q ∗ + q ∗ = 0. t As is standard, transform it into simultaneous equations by introducing a new function q1 :  q ∗ = q1 q1 = − 4t q1 . Although the solution entails constants, it follows from q ∗ (t  ) = 0 and q ∗ (t  ) = 1 that the constants can be replaced. As a result, one obtains:

123

N. Kojima

⎧ ⎪ ⎨0 ∗ t 3 t 3 −3 q (t) = − t 3 t + −t 3 ⎪ ⎩ 1

t 3 t 3 −t 3

if t ∈ [0, t  ], if t ∈ (t  , t  ), if t ∈ [t  , 1],

t  and t  are to be numerically calculated by the two equations, (16) and (17), which are simultaneous polynomial equations in two variables. 5 Comparison with the approach of a direct mechanism In this section, we turn to comparison between the approach of a canonical mechanism and that of a direct mechanism. It should be emphasized that the results of this section do not rely on any regularity assumptions on g. They hold whether or not g is continuous not to mention all the other assumptions upon g and G. Nor do they rely on condition (1). Let us define the two-dimensional mechanism in taste and budget; namely, the direct mechanism is a map: (q(t, w), p(t, w)) : T × W → Q × R. Truthful revelation on the part of buyers requires that the direct mechanism should satisfy the following condition. Definition 3 The direct mechanism (q(t, w), p(t, w)) is strongly implementable14 if and only if p(t, w) ≤ w for any (t, w) ∈ T × W,

(SBC)

tq(t, w) − p(t, w) ≥ tq(t˜, w) ˜ − p(t˜, w) ˜ ˜ for any (t, w) and (t , w) ˜ ∈ T × W such that p(t˜, w) ˜ ≤ w.

(SIC)

The direct mechanism assigns a quality and a price to a buyer of each taste and budget. The requirement (SBC) is necessary for the buyer to actually purchase the designated quality: the corresponding price should be within his budget. The participation constraint is also needed in order that the buyer honestly announcing his taste and budget will purchase the quality assigned by the strongly implementable mechanism. tq(t, w) − p(t, w) ≥ 0

on T × W.

(SIR)

Definition 4 The optimal direct mechanism is (q(t, w), p(t, w))(t,w)∈T ×W which maximizes 14 “S” in the tags SBC and SIC stands for strong.

123

Mechanism design to the budget constrained buyer

  p(t, w)g(t, w)dtdw T W

s.t. (SBC), (SIC) and (SIR). Recall that a mechanism (see Myerson 1979) is defined as a map from a message set to an allocation set. Here, the allocation set is the product of the quality and price spaces Q × R. Only buyers have variable types in our setting: taste and budget. The type set, therefore, consists of T × W . A generic direct mechanism is defined as a mechanism with the message set coincident with the type set; otherwise, a mechanism is indirect. Clearly, the direct mechanism in our definition conforms to this general definition in Myerson (1979) and the canonical mechanism is an indirect mechanism with the message set T . By the same token, the non-linear price scheme is an indirect mechanism with the message set Q. The revelation principle states that the equilibrium outcome of an indirect mechanism is realized by a direct mechanism. This is the justification, whereby most of mechanism design literature concentrates upon the direct mechanism. It follows from the contrapositive of the revelation principle that some quality-price pairs realized by a strongly implementable mechanism may not possibly be put into effect by a weakly implementable mechanism. We now show that the weakly implementable mechanism preserves the same generality as the strongly implementable mechanism. The conditions in Definition 3 make it quite cumbersome to directly compare the strongly and the weakly implementable mechanisms. We proceed, thus, by way of a non-linear price scheme. First, we show that given a direct mechanism, there exists a non-linear price scheme which brings the seller a weakly greater profit. Then, we show that there exists a canonical mechanism which achieves the same outcome as the non-linear price scheme. Recall that the outcome of any indirect mechanism can be realized by a direct mechanism. The following proposition demonstrates the first step. Proposition 5 Given any direct mechanism (q(t, w), p(t, w)) satisfying (SBC), (SIC) and (SIR), there exists a non-linear price scheme τ : Q → R such that it is continuous, strictly increasing, convex and τ (0) = 0, and further that for all (t, w),

τ (y) ≥ p(t, w)

(21)

(22)

where y ∈ arg max t x − τ (x). x s.t. τ (x)≤w

Proof See the Appendix.



It is clear from the remark made just before the proposition that the optimal direct mechanism attains the same outcome as the corresponding non-linear price scheme. Let us turn to showing that a weakly implementable mechanism can replicate the quality-price allocation that the non-linear price scheme (superior to the direct mechanism in profit) puts into effect.

123

N. Kojima

Let us define the maximizer of utility: given the continuous price schedule τ (x), Q(t) := arg max t x − τ (x).

(23)

x∈Q

Note that Q(t) is not necessarily single-valued and thus it is a set-valued map, in general. One obtains: Lemma 4 Given the continuous price scheme τ , Q(t) is upper semicontinuous.15 Proof See Theorem 6, p. 53 in Aubin and Cellina (1984).



Recall that a selection of Q(t) is a function constructed such that q(t) ∈ Q(t). First, the following fact is easy to show but very useful, the proof of which is in the Appendix. Lemma 5 Any selection q(t) of Q(t) is non-decreasing. The nub of our demonstration is the following proposition, the proof of which is relegated to the Appendix. Proposition 6 Given the continuous price scheme τ , there exists a continuous selection of Q(t) If Q(t) reduces to a single-valued map, upper semicontinuity amounts to the usual continuity of a single-valued map. It arises, for instance, when the maximand in (23) is strictly concave. The difficulty of the proof of Proposition 6 consists in the fact that contrary to a lower semicontinuous map, an upper semicontinuous map has no general criterion for the existence of a continuous selection. One, however, has the result that an upper semicontinuous map is lower semicontinuous on a dense set, which, coupled with Lemma 5, leads to the above proposition. Finally, we show that the outcome of τ is achievable by a weakly implementable mechanism. Proposition 7 Given a non-linear price scheme τ satisfying (21), let q(t) be a continuous selection of Q(t). Then, it holds good that arg max

x s.t. τ (x)≤w,x∈Q

t x − τ (x)

is identical to arg max

q(t  ) s.t. τ (q(t  ))≤w,q(t  )∈q(T )

tq(t  ) − τ (q(t  )).

(24)

(25)

Proof Let us show that q(T ) = [0, q(t)]. First, one obtains that q(T ) ⊂ [0, q(t)] because q(t) is non-decreasing by Lemma 5 and q(0) = 0 by the definition of Q(t). Then, the result is obvious since q(T ) is connected. 15 Refer to a section in the Appendix for all the definitions as regards set-valued functions.

123

Mechanism design to the budget constrained buyer

Then, even if {x|τ (x) ≤ w, x ∈ Q} is strictly larger than {x|τ (x) ≤ w, x ∈ q(T )}, arg max in (24) does not contain an element outside q(T ) by the definition and Lemma 5. Now the proposition is obvious.

To construct a weakly implementable mechanism which achieves the outcome by τ , posit simply: (q(t), p(t)) := (q(t), τ (q(t))). (26) By construction, this canonical mechanism satisfies (WIC) and (WIR). Faced with the price scheme τ (x) and the weakly implementable mechanism in (26), the buyer makes the same quality choice and pays the same price. In consequence, one has proved: Theorem 2 Given a direct mechanism satisfying (SBC), (SIC) and (SIR), there exists a canonical mechanism satisfying (WIC) and (WIR) which yields a greater expected profit. The revelation principle asserts that the expected profit achieved by a canonical mechanism is attained by a direct mechanism. The above theorem assures, thus, along with the revelation principle, that in particular, the expected profit by the optimal direct mechanism is realized by a canonical mechanism. Discussion 1 One natural question for the equivalence result in Theorem 2 is to what extent it can be extensible. In other words, is it valid with other objective functions of the seller’s such as welfare maximization? Also, is it valid when the taste space T and allocation space Q are multidimensional? To consider the question, let us recall the following fact. On the one hand, the revelation principle ensures that the outcome of any indirect mechanism—thus of a non-linear price scheme, too—is implemented by an incentive compatible direct mechanism. On the other hand, the taxation principle (Rochet 1985, 1987) asserts to the contrary, i.e., that the outcome of any incentive compatible direct mechanism is implemented by a non-linear price scheme. Some readers might wonder, then, why one needs to underscore Proposition 5; for after all, the above two principles assure equivalence between the two approaches: that of a direct mechanism and that of a non-linear price scheme. If one takes this equivalence result at face value, it amounts to the same thing whether one starts with a non-linear price scheme or a direct mechanism. The significance of the proposition is, however, that it shows the existence of a nonlinear price scheme with some “regularity conditions” (21). Whatever the problem is, when one seeks for an optimal—revenue maximization, welfare maximization and so forth—solution, one must resort to a technique of maximization, be it optimal control, calculus of variations or else. In the process, one is bound to assume some regularity conditions on control and/or state variables.16 Literature has until now failed to pay attention to this issue of regularity. The seminal work by Wilson (1993) on the non-linear pricing approach assumes as regularity that 16 For instance, in optimal control, a control variable is measurable and a state variable absolutely contin-

uous.

123

N. Kojima

the non-linear price scheme has a marginal price. By a direct mechanism of what regularity condition is the outcome of an optimal price scheme with that regularity condition—whatever the seller’s objective function is—realized? On the contrary, what regularity condition does a non-linear price scheme possess which implements the outcome of an optimal direct mechanism with regularity conditions required by the maximization technique? One needs to scrutinize this question so as to give the equivalence result a decisive meaning. Let us turn back to our context with budget constraints. The taxation principle is very general and valid no matter what the type space and the commodity space are (i.e., whether the dimension of the type space is larger or smaller than the dimension of the commodity space) and regardless of the seller’s objective function. While Proposition 5 merely deals with the case of one taste parameter and a budget parameter, the proof of Theorem 2 has no bearing on the dimensionality of type but most crucially hinges upon the continuity of a non-linear price scheme. Therefore, the question posed at the beginning of the discussion as to possibility of extention of the result of no loss of generality is reduced to whether a particular direct mechanism to be considered can be implemented by a continuous non-linear price scheme. It is a very interesting question but largely out of scope of this paper. 6 Conclusion This article has analyzed the optimal selling mechanism of the monopolist faced with a continuum of budget-constrained buyers with one-dimensional heterogeneous taste. Multi-dimensional mechanism design involves technical difficulties. One way to circumvent them is the reduction of the dimension; in other words, use of an indirect mechanism. In the setting of budget-constrained buyers (and also multi-product and multi-dimensional taste), the non-linear price scheme was the only indirect mechanism thus far investigated. This paper studied a canonical mechanism in the standard setting of buyers in one-dimension taste as another possibility. It characterized the optimal canonical mechanism in existence of budget constraints and showed no loss of generality of its approach as regards an optimal direct mechanism. Another indirect mechanism possible to consider is a map from the budget space to the quality-price space. It is worth further investigation in future research as well as the question of the extent of no loss of generality raised at the end of the preceeding section. Acknowledgments The author is very grateful to Jean-Charles Rochet for his valuable comments. The author acknowledges the two reviewers’ very careful reading of the paper. The final version has benefited considerably from their comments and suggestions.

Appendix Proof of Lemma 2 Suppose that (q(t), p(t)) satisfies (WIC). In addition, let us assume, as opposed to the proposition, that p(t) > p(t  ) for t ≤ t  . Then, one has

123

Mechanism design to the budget constrained buyer

tq(t) − p(t) ≤ tq(t  ) − p(t) < tq(t  ) − p(t  ). The first inequality follows from (4) of Lemma 1. It is obvious that tq(t) − p(t) < tq(t  ) − p(t  ) contradicts (WIC). Proof of Proposition 2 From Lemma 2, if w < p(0), it follows that w < p(t) for all t. Therefore, the buyer can afford no quality. Now suppose that p(0) ≤ w. Then {t  | p(t  ) ≤ w} = ∅. Since p is non-decreasing and left continuous, there exists μ(w) := max{t  | p(t  ) ≤ w} and one has [0, μ(w)] = {t  | p(t  ) ≤ w}. Again, from the monotonicity of p, it follows that p(μ(w)) ≥ p(t  ) for t  ∈ [0, μ(w)]. Let us show that taste t buyer chooses (q(μ(w)), p(μ(w))). Suppose t  < μ(w). Then it suffices to show that tq(t  ) − p(t  ) ≤ tq(μ(w)) − p(μ(w)). It is seen from above that t  ∈ {t| p(t) ≤ w} and so that taste t buyer can purchase quality t  . Now let us suppose that tq(t  ) − p(t  ) > tq(μ(w)) − p(μ(w)) and deduce the contradiction. Recall that q is non-decreasing by (4) and that t  < μ(w) < t since p is non-decreasing. Then, it follows that     0 > t q(μ(w)) − q(t  ) − p(μ(w)) − p(t  )   > μ(w) q(μ(w)) − q(t  )) − ( p(μ(w)) − p(t  ) . It is equivalent to μ(w)q(t  ) − p(t  ) > μ(w)q(μ(w)) − p(μ(w)), which is contradictory to the definition of (WIC). Proof of Theorem 1 First we search for the solution of the relaxed problem and then verify the satisfaction of (14). Let (q ∗ , u ∗ ) be an optimal pair of the relaxed problem. Then we have the necessary conditions in Sect. 4 at our disposal. The Hamiltonian is concave and differentiable in q and we have     ∂H  t, q, u ∗ (t), λ(t) = t G(t, w) − G t, tq − u ∗ (t) + λ(t). ∂q Since H (t, q, u ∗ (t), λ(t)) is concave in q, it follows that  ∂H   ∂H   ∂H  t, 0, u ∗ (t), λ(t) ≥ t, q, u ∗ (t), λ(t) ≥ t, 1, u ∗ (t), λ(t) . ∂q ∂q ∂q First, we obtain

123

N. Kojima

Lemma 6 λ is strictly increasing and λ(t) ≤ λ(t) = 0. Proof Noticethat λ˙ = G(t, w)− G(t, tq ∗ (t)−u ∗ (t)) > 0 a.e; for we have 0 ≤ q ≤ 1 t and u ∗ (t) = 0 q ∗ (s)ds so that tq ∗ (t) − u ∗ (t) < w except at t = t. Therefore λ is strictly increasing. From the transversality condition, the lemma is obvious.

Let us consider the maximization of the Hamiltonian. Since the Hamiltonian is concave, if ∂∂qH (t, 0, u ∗ (t), λ(t)) ≤ 0, the Hamiltonian is maximized at q = 0 and if ∂H ∗ ∂q (t, 1, u (t), λ(t))

≥ 0, it is maximized at q = 1.

We have

 ∂H  t, 0, u ∗ (t), λ(t) = t G(t, w) + λ(t). ∂q

η(t) :=

This is continuous and strictly increasing, which follows from Lemma 6 and the fact that t G(t, w) is non-decreasing (one obtains this by putting w = 0 in Assumption 3). We have η(t) > 0 and also η(0) = λ(0) < 0 from Lemma 6. Thus, there is the unique t  such that 0 < t  < t and η(t  ) = 0. Besides, η(t) < 0 on the interval [0, t  ). It follows that q ∗ is zero on [0, t  ] and that the optimal q ∗ is unique on [0, t  ). It turns out that at t  likewise, q ∗ is uniquely determined to be zero. This is evident because, from u ∗ (t  ) = 0 (due to absolute continuity) and η(t  ) = 0, we obtain that  ∂H   t , q, u ∗ (t  ), λ(t  ) = −t  G(t  , t  q) < 0. ∂q Now, we can define t  by η(t  ) = t  G(t  , w) +

t 

⎛

⎛

dt ⎝G(t, w) − G ⎝t, tq ∗ (t) −

t

t

⎞⎞ q ∗ (t)dt ⎠⎠ = 0. (27)

0

Let us turn to the latter half part. We define θ (t) :=

    ∂H  t, 1, u ∗ (t), λ(t) = t G(t, w) − G t, t − u ∗ (t) + λ(t). ∂q

θ (t) is continuous and it follows from t − u ∗ (t) < t < w and g(t, w) > 0 that    θ (t) = t G(t, w) − G t, t − u ∗ (t) > 0, Likewise, θ (0) < 0 from Lemma 6. There exists, thus, t  < t such that θ (t  ) = 0. Let us show that t  is unique. There exists θ˙ (t) almost everywhere and     θ˙ (t) = G(t, w) − G t, t − u ∗ (t) + t G 1 (t, w) − t G 1 t, t − u ∗ (t) + λ˙ (t); for we have 1 − u˙ ∗ (t) = 0 since u(t) ˙ = q a.e. and q = 1 by the definition of θ (t).

123

Mechanism design to the budget constrained buyer

˙ − λ˙ (t) ≥ 0 and we also know that λ˙ = G(t, w) − Assumption 3 assures that θ(t) G(t, tq ∗ − u ∗ ) > 0 a.e. because g(t, w) > 0 and w > tq ∗ − u ∗ except at t = t. As a result, θ is strictly increasing and t  is unique. It follows that q ∗ = 1 on [t  , t] and the optimal q ∗ is unique on (t  , t]. Let us show that q ∗ is unique at t  . Note that the left derivative with respect to q of ∂ H  ∗      ∂q (t , q, u (t ), λ(t )), estimated at the point q = 1, is lim q→1− −t g(t , t q − u ∗ (t  )).17 It suffices to show that it is strictly negative. For this, it is, in turn, enough to show that t  q − u ∗ (t  ) is non-negative around q = 1. It is assured since we have u ∗ (t) < t from the fact that u˙ = q a.e., 0 ≤ q ≤ 1 and q ∗ = 0 on [0, t  ]. We can formally define t  by (recall that q ∗ = 1 on [t  , t]): ⎛ ⎞ t  ⎜ ⎟ t  ⎝G(t  , w) − G(t  , t  − q ∗ (t)dt)⎠ t  +

⎛

⎛

0

dt ⎝G(t, w) − G ⎝t, t −

t

⎞⎞ q ∗ (t)dt ⎠⎠ = 0

0

t

In view of the above argument, we see that for t ∈ (t  , t  ),   ∂H  t G(t, w) + λ(t) > 0 if q = 0, t, q, u ∗ (t), λ(t) = ∗ ∂q t (G(t, w) − G (t, t − u (t))) + λ(t) < 0 if q = 1. (28) Since ∂∂qH (t, q, u ∗ (t), λ(t)) is continuous and non-increasing in q ∈ Q, there exists ∂H ∗ ∗ ∂q (t, q (t), u (t), λ(t))

an optimal q ∗ (t) ∈ (0, 1) such that for all t ∈ (t  , t  ), By substituting u ∗ (t) and λ(t), we obtain (18): ⎛

⎛

t ⎝G(t, w) − G ⎝t, tq ∗ (t) − t +

⎛

⎛

t

⎞⎞ q ∗ (t)dt ⎠⎠

0

dt ⎝G(t, w) − G ⎝t, tq ∗ (t) −

t

= 0.

t

⎞⎞ q ∗ (t)dt ⎠⎠ = 0

0

q ∗ (t) is unique on (t  , t  ). Note that tq ∗ (t) − u ∗ (t) > 0 on (t  , t  ); for otherwise ∂H ∗ ∗ ∂q (t, q (t), u (t), λ(t)) = t G(t, w) + λ(t) > 0 from (28). We obtain that    ∂2 H  ∗ t, q (t), u ∗ (t), λ(t) = −tg t, tq ∗ (t) − u ∗ (t) < 0. ∂q 2 Uniqueness has been proved. 17 q → 1− means q converges to 1 from below.

123

N. Kojima

Now we set to verifying that the solution of the relaxed problem satisfies the condition ignored of the original problem. Proposition 8 q ∗ (t) is continuous and non-decreasing on [0, t]. Further, it is strictly increasing and differentiable on (t  , t  ). Proof As for continuity, we have seen that q ∗ (t) uniquely maximizes the Hamiltonian on (t  , t  ). Thus, we can apply Theorem 6.1 of Fleming and Richel (1975) (see p. 75). We will show that q ∗ is differentiable and q˙ ∗ > 0 on (t  , t  ). Let us look upon J (t, q) = t (G(t, w) − G(t, tq − u ∗ (t))) + λ(t) as a function on (t  , t  ) × (0, 1). Now let us show that J (t, q) is differentiable at (t, q ∗ (t)) for t ∈ (t  , t  ). We know J (t, q ∗ (t)) = 0 on (t  , t  ). First, note that tq ∗ (t) − u ∗ (t) > 0 on t ∈ (t  , t  ); for otherwise, J (t, q ∗ (t)) = t G(t, w) + λ(t) > 0 from (28), which, however, is a contradiction to the definition of q ∗ (t). Thus, J (t, q) is continuously differentiable in q at the point (t, q ∗ (t)) when t ∈ (t  , t  ). Let us turn to the differentiability of J (t, q) with respect to t at (t, q(t)). ˆ Since λ˙ = G(t, w) − G(t, tq ∗ − u ∗ ) almost everywhere and q ∗ is continuous, λ is continuously differentiable on (t  , t  ) (recall also that 0 < tq ∗ (t) − u ∗ (t) on (t  , t  ) above). Therefore, J (t, q) is continuously differentiable with respect to t at (t, q ∗ (t)) when t ∈ (t  , t  ). Combining the two results, we obtain that J (t, q) is differentiable at (t, q ∗ (t)) for t ∈ (t  , t  ). In addition, ∂ J˜ ∗   ∂q (t, q (t)) = 0 when t ∈ (t , t ). Now we can apply an implicit function theorem (see Theorem in 3.8.2 Schwartz 1997) and conclude that q ∗ is differentiable on (t  , t  ). q˙ ∗ is expressed as ∂J (t, q ∗ ) ∂t ∗ q˙ (t) = − ∂J (t, q ∗ ) ∂q As was seen,

u ∗ (t) t

for t ∈ (t  , t  ).

< q ∗ < 1 on (t  , t  ) so that for t ∈ (t  , t  ), ∂J (t, q ∗ ) = −t 2 g(t, tq ∗ − u ∗ (t)) < 0. ∂q

On the other hand, for t ∈ (t  , t  ),   ∂ J  ∗ t, q = G(t, w) − g t, tq ∗ − u ∗ (t) + t G 1 (t, w) ∂t      − tg t, tq ∗ − u ∗ (t) q ∗ − u˙ ∗ (t) − t G 1 t, tq ∗ − u ∗ (t) + λ˙ (t). Notice that u is everywhere differentiable because q is continuous and therefore λ˙ (t) always exists on (t  , t  ). From (13), it follows that    g t, tq ∗ − u ∗ (t) q ∗ − u˙ ∗ (t) = 0.

123

Mechanism design to the budget constrained buyer

From Assumption 3, we have for t ∈ (t  , t  )     G(t, w) − g t, tq ∗ − u ∗ (t) + t G 1 (t, w) − t G 1 t, tq ∗ − u ∗ (t) ≥ 0. We also know from Lemma 6 that λ˙ > 0 on (t  , t  ). We have deduced that ∂ J  ∗ t, q > 0. ∂t It is established that q˙ ∗ is strictly increasing on (t  , t  ).



Proof of Proposition 5 Proof We follow the proof of Lemma 1 in Che and Gale (2000). Let us suppose that there is given a strong mechanism (q(t, w), p(t, w)) satisfying (SBC), (SIC) and (SIR). We posit the following price schedule τ :     t x − t  q(t  , w) − p(t  , w) + tq(t, w) − p(t, w) . τ (x) := max  t ∈T

Let us show that it satisfies (21). First, t  q(t  , w) − p(t  , w) is both continuous and non-decreasing in t  ; for from (SIC) it follows that for t  , t such that t  ≥ t, t  q(t  , w) − p(t  , w) ≥ t  q(t, w) − p(t, w) ≥ tq(t, w) − p(t, w) ≥ tq(t  , w) − p(t  , w). Thus max in the definition exists and obviously τ (0) = 0. It is also clear that τ is strictly increasing. The so-called maximum theorem obtains that τ is continuous. It is convex as the superior envelope of the linear function. We have proved (21). Now we turn to (22). It can be shown that type (t, w) buyer likes best q(t, w), faced to the price schedule τ (x) (note that we are concerned about preference but not affordability): for x ∈ Q, τ (x) ≥ t x − (tq(t, w) − p(t, w)) + tq(t, w) − p(t, w) ⇐⇒ t x − τ (x) ≤ tq(t, w) − p(t, w) − (tq(t, w) − p(t, w)) = tq(t, w) − τ (q(t, w)). (29) The equality follows from the definition of τ . Let us show (22). Suppose that (t, w) is given. (1) If τ (q(t, w)) ≤ w, put q(t, w) into x in (29), which gives p(t, w) ≤ τ (q(t, w)) − (tq(t, w) − p(t, w)). This shows that faced with τ , type (t, w) can afford and chooses q(t, w) and brings the seller more money than the direct mechanism. (22) is proved.

123

N. Kojima

(2) If τ (q(t, w)) > w, there is x ∗ such that τ (x ∗ ) = w since τ is continuous and Q is connected. In addition, we know that t x − τ (x) is concave. Accordingly, we obtain that max

x s.t. τ (x)≤w

t x − τ (x) = t x ∗ − w.

The price scheme τ brings the seller w, which is greater than p(t, w).



Facts on a set-valued map First, let us put together definitions and facts concerning a set-valued map.18 Suppose that X and Y are topological spaces and let F be a set-valued map from X to Y , i.e. with the value F(x) being a non-empty subset of Y for each x ∈ X . Definition 5 F is upper semicontinuous at x if for any neighbourhood V of F(x), there exists a neighbourhood U of x such that F(U ) ⊂ V . F is upper semicontinuous if it is upper semicontinuous at every point. Definition 6 F is lower semicontinuous at x if for any y ∈ F(x) and any neighbourhood V (y) of y, there exists a neighbourhood N (x) of x such that ∀x  ∈ N (x),

F(x  ) ∩ V (y) = ∅.

F is lower semicontinuous if it is lower semicontinuous at every point. Definition 7 F is continuous at x if it is both upper and lower semicontinuous at x. F is continuous if it is both upper and lower semicontinuous at every point. If F is single-valued, the three definitions above are identical to the definition of a continuous function. Proposition 9 Suppose that X is a complete metric space and Y a complete separable metric space. Then, if F is upper semicontinuous, it is continuous on a countable intersection of some dense open subsets An ⊂ X . Proof Refer to Theorem 1.4.13 in Aubin and Frankowska (1990)



Theorem 3 (Michael’s Selection Theorem) Suppose that X is a metric space and Y a Banach space. Let F be lower semicontinuous with each value F(x) being a closed convex subset of Y . Then, there exists a continuous selection f of F. 18 Refer to Aubin and Cellina (1984).

123

Mechanism design to the budget constrained buyer

Proof of Lemma 5 By definition, one has t  q(t  ) − τ (q(t  )) ≥ t  q(t) − τ (q(t)), tq(t) − τ (q(t)) ≥ tq(t  ) − τ (q(t  )). Adding side by side, one obtains that q(t) is non-decreasing. Proof of Proposition 6 Given the continuous non-linear price scheme τ , Q(t) is lower semicontinuous on a countable intersection of dense open subsets of T due to Lemma 4 and Proposition 9. Baire’s theorem, then, asserts that Q(t) is lower semicontinuous on a dense subset of T . It follows from Theorem 3, now, that there is a continuous selection q(t) on the dense subset of T . Finally, Lemma 5 ensures that one can obtain a continuous selection on the whole of T . References Armstrong M (1996) Multiproduct nonlinear pricing. Econometrica 64:51–75 Armstrong M (1999) Price discrimination by a many-product firm. Rev Econ Stud 66:151–168 Aubin J, Cellina A (1984) Differential inclusion. Springer Verlag, Berlin Aubin J, Frankowska H (1990) Set-valued analysis. Birkhäuser, Boston Cesari L (1983) Optimization—theory and applications. Springer Verlag, New York Che Y, Gale I (1998) Standard auctions with financially constrained bidders. Rev Econ Stud 65:1–21 Che Y, Gale I (2000) The optimal mechanism for selling to a budget-constrained buyer. J Econ Theory 92:198–233 Fleming W, Richel R (1975) Deterministic and stochastic optimal control. Springer Verlag, New York Laffont J, Martimort D (2001) The theory of incentives: the principal-agent model. Princeton University Press, Princeton Manelli A, Vincent R (2006) Bundling as an optimal mechanism by a multiple-good monopolist. J Econ Theory 127:1–35 Monteiro PK, Page FH Jr (1998) Optimal selling mechanism for multiproduct monopolists: incentive compatibility in the presence of budget constraints. J Math Econ 30(4):473–502 Mussa M, Rosen S (1978) Monopoly and product quality. J Econ Theory 18:301–317 Myerson R (1979) Incentive compatibility and the bargaining problem. Econometrica 47:61–73 Richter M (2011) Mechanism design with budget constraints and a continuum of agents. New York University, discussion paper Rochet J (1985) The taxation principle and the multi-time Hamiltonian–Jacobi equations. J Math Econ 14:113–128 Rochet J (1987) A necessary and sufficient condition for rationalizability in a quasilinear context. J Math Econ 16:191–200 Rochet J, Chone P (1998) Ironing, sweeping, and multidimensional screening. Econometrica 66:783–826 Rochet J, Stole L (1997) Competitive nonlinear pricing. University of Chicago, discussion paper Rochet J, Stole L (2002) Nonlinear pricing with random participation. Rev Econ Stud 69(1):277–311 Rochet J, Stole L (2003) The economics of multidimensional screening. In: Dewatripont M, Hansen L, Turnovski S (eds) Advances in economics and econometrics: theory and applications, eighth World Congress, vol 1. Cambridge University Press, New York Schwartz L (1997) Analyse, vol 2. Hermann, Paris Wilson R (1993) Nonlinear pricing. Oxford University Press, New York

123