Stéphane Gauthier

Guy Laroque

On the value of randomization *

Keywords: JEL classification numbers: H21, H23, H26 random taxation, adverse selection, incentive constraints

An optimal contract may involve randomization when the agents differ in their attitudes towards risk, so that randomization enables the principal to relax the incentive constraints. The paper provides a necessary and sufficient condition for local random deviations to be welfare improving in a neighborhood of a nonrandom optimum.

Introduction

In most economic models, concave objectives on convex sets lead to nonrandom choices. But asymmetric information and self-selection in principal agent models introduce nonconvexities. Randomization may then be useful when agents' risk attitudes are correlated with other private individual characteristics that are important to the principal. For instance a random conscription draft with exemptions may select young men with the lowest opportunity costs [START_REF] Sabin | Conscription tax[END_REF]), a fairy tale king evaluates how much a young prince loves his daughter by putting forward a risky fight against a dragoon, and Solomon could assess entrepreneurship in the light of a choice involving some exposure to risk [START_REF] Miller | Solomonic separation: gauging preference intensity through risk taking[END_REF]).

The paper relies on a technical result. Consider an abstract optimization program, with a finite number of constraints which define a nonconvex set of admissible choices in a finite dimension Euclidean space. When choices are restricted to be deterministic, a condition satisfied by a local optimum is that the second derivative of the Lagrangian be negative definite on the tangent space to the active constraints. Consider an associated random problem, where choices may be random and the functions defining the objective and constraints are the mathematical expectations of those of the deterministic program. The main technical result of the paper is that the deterministic optimum can locally be improved upon through a random deviation if and only if the second derivative of the Lagrangian has a positive eigenvalue. We give a constructive method to build the improving deviation. The result is applied to a number of economic models with asymmetric information.

Our first application is random taxation. In general the actual tax base is not fully known by the tax authority. When auditing all fiscal reports without error is extremely costly, some taxpayers will pay random taxes, due to administrative errors or successful tax evasion, as in [START_REF] Cremer | Tax evasion and optimal commodity taxation[END_REF], Cremer and Gahvari (1996), [START_REF] Slemrod | Cheating ourselves: the economics of tax evasion[END_REF] and [START_REF] Slemrod | Optimal observability in a linear income tax[END_REF]. However random taxation is not necessarily driven by the cost of monitoring. A random tax system may be optimal even if exact auditing can be implemented at no cost. Indeed, when taxpayers differ in their attitudes towards risk, tax randomization enables the government to separate agents who otherwise would have been treated equally. In [START_REF] Pestieau | Cheating ourselves: the economics of tax evasion[END_REF] agents differ both in their earning abilities and in their attitudes towards risks. A nonrandom income tax then pools agents with the same taxable income, while randomization within income classes may allow to treat differently the taxpayers depending on their self-revealed risk aversions (see the examples of 1991 and 1994 Italian tax amnesties for an application of this kind of argument in [START_REF] Marchese | Tax amnesties and the selfselection of risk-averse taxpayers[END_REF]). The most general results on the usefulness of random taxation appear in [START_REF] Brito | Randomization in optimal income tax schedules[END_REF]. These authors examine whether a small random redistribution can locally improve social welfare at a nonrandom second-best allocation in a standard two good (consumption and labor) Mirrlees economy. They obtain a necessary and sufficient condition (their Theorem III) for the existence of a local random improvement. However, their constructive tax reform methodology does not provide a description of the mechanism at work, so that it is unclear how it could be extended to more general economies. The condition, which bears on a weighted difference of the second derivatives of the agents' utility functions, appears quite intricate [START_REF] Hellwig | The undesirability of randomized income taxation under decreasing risk aversion[END_REF]). Our technique provides a simple way of deriving this condition and allows for a transparent economic interpretation.

We apply the analysis to the early principal-agent model by [START_REF] Weiss | The desirability of cheating incentives and randomness in the optimal income tax[END_REF] and [START_REF] Stiglitz | Self-selection and Pareto Efficient Taxation[END_REF], where randomization alleviates the incentive constraints faced by the regulator. Consider an economy with two types of agents: the first ones are skilled and display a high level of risk aversion, whereas the second ones are unskilled and have a lower level of risk aversion. Assume that the government would like to redistribute welfare from the skilled (rich) agents towards the unskilled (poor) agents. If neither skills nor risk aversions are publicly observed, the available information puts strong limits on the scope of redistribution: the skilled agents would pretend to be unskilled if they faced too high a tax. A random tax on the unskilled workers may then be part of the optimal second-best tax policy: the risk averse skilled types are discouraged to pretend being unskilled, which yields a social gain possibly overcoming the efficiency loss due to the government creating risk bearing on the unskilled. In this example, random taxation can be optimal when skill and risk aversion are positively correlated. Indeed randomized redistribution can only be useful when the agents that the government wants to favor have the lowest risk aversion [START_REF] Hellwig | The undesirability of randomized income taxation under decreasing risk aversion[END_REF]).

Our second application concerns discrimination strategies through differential risk exposure. Customers often buy goods and services whose quality and/or price depend on future contingencies. Quality of a journey is random when strikes, equipment malfunction or unavailable aircrafts make airline not fully reliable. Online travel intermediaries offer non-refundable 'opaque' low price hotel rooms in which buyers specify some characteristics such as dates or city, but other hotel properties are revealed after payment has been made. Both quality and price may be random when firms use overselling or overbooking combined with consolation rewards. Risk averse customers facing such alternatives will usually seek some form of insurance. Firms can exploit differences in the risk aversion of their customers by a suitable design of risk exposure. Airline companies thus offer high price tickets ensuring against delays business men who want to be on time.

Following [START_REF] Maskin | Monopoly with incomplete information[END_REF], in a [START_REF] Mussa | Monopoly and Product Quality[END_REF] setup, our mathematical result yields the conditions under which a monopolist facing customers with different risk tolerances can relax some of the incentive constraints by randomizing the quality of service. In the airline case, exposure to risk discourages business men to buy second class tickets, and thus allows to extract more surplus.

The paper is organized as follows. Section 2 presents the mathematical properties that underlie the paper. Then Section 3 applies the results to a general framework with adverse selection, showing the role of the agents risk aversions. In Section 4 a simple taxation example with two-type of agents, disabled vs. able agents, serves to give a full illustration of the argument. Finally Section 5 shows how the optimal contracts set by a discriminating monopolist may involve randomization.

A mathematical result

Consider the following constrained optimization problem:

   max x f (x) g n (x) ≥ 0, n = 1, . . . , N
where x is in R M . The functions f (•) and g n (•), n = 1, . . . , N , are twice continuously differentiable. We do not impose convexity restrictions on the objective f (•), nor on the constraints g n (•). Although the above problem only involves inequality constraints, all our results would apply if there were also equality constraints. In second-best problems the objective is typically concave in x, while the incentive constraints may define a set which is not convex. We shall refer to the above program as the deterministic problem.

The associated Lagrangian L(x, λ) is the function f (x) + λ g(x), where λ is a vector of R N + .

Some of the results that follow require that the constraints be qualified at the point we consider. The nth constraint is active at some point x of the domain when g n (x) = 0. The constraints are qualified at x when the gradient vectors ∇g n (x) of the active constraints at x are linearly independent.

The following property is drawn from Simon and Blume (1994), Th. 18.4 and 19.8. Theorem 1. Let x * be an interior local maximum of the deterministic problem where the constraints are qualified.

1. There exists λ * ≥ 0 such that ∇ x L(x * , λ * ) = 0, and the complementary slackness conditions λ * n g n (x * ) = 0 hold for all n.

2. The Hessian ∇ 2 x L(x * , λ * ) is negative semi-definite on the tangent space to the active constraints at x * , i.e., x ∇ 2

x L(x * , λ * )x ≤ 0 for all x such that ∇g n (x * ) x = 0 for all constraints n with g n (x * ) = 0. Let x * in R M be a point that satisfies the first order conditions given in part 1 of Theorem 1. We prove a converse to Theorem 1. Suppose that the condition given in part 2 of Theorem 1 is not satisfied in the following sense: there is a direction x + in the tangent space to the active constraints such that x + ∇ 2

x L(x * , λ * )x + > 0. We are interested in the feasible deviations which improve the objective in this circumstance. A deterministic deviation from x * is a continuous function h(t) from [0, 1] into R M such that h(0) = 0 and

g n (x * + h(t)) = g n (x * ) = 0 (1)
for all n such that g n (x * ) = 0.

Theorem 2. Let x * be a point where the constraints are qualified and the first order conditions of Theorem 1.1 are satisfied. Suppose that there is a direction x + in the tangent space to the active constraints such that

x + ∇ 2 x L(x * , λ * )x + > 0.
Then there exists a deterministic deviation h(t) = tx + + β(t) satisfying

∇g n (x * ) β(t) + 1 2 t 2 x + ∇ 2 g n (x * ) x + = o(t 2 ),
for all the active constraints n with g n (x * ) = 0, such that f (x * +h(t)) > f (x * ) for small enough t different from 0. Consider now the following maximization problem:

   max x Ef (x) Eg n (x) ≥ 0, n = 1, . . . , N
where x is a random variable with values in R M , such that the mathematical expectations of f (x) and the g n (x), n = 1, . . . , n are well defined. We shall refer to this program as the random problem. Let x * be a point in R M which satisfies the constraints. A random deviation h(t) from x * is an application from [0, 1] into the random variables in R M which satisfies

Eg n (x * + h(t)) = g n (x * ) = 0, (2)
for all active constraints, such that h(0) = 0 and the diameter of the support of h(t) is a continuous function of t. For simplicity we limit our attention to the generic case where the Hessian ∇ 2 x L(x * , λ * ) evaluated at x * is of full rank.1 Then we have: Theorem 3. Let x * be a point where the constraints are qualified and the first order conditions of Theorem 1.1 are satisfied.

1. If ∇ 2 x L(x * , λ * ) is negative definite, x * is a local maximum of the random problem: there exists an open neighborhood V (x * ) of x * in R M such that f (x * ) > Ef (x)
for all random variables x, x = x * , with support contained in V (x * ) such that Eg n (x) = g n (x * ) = 0 for the active constraints.

Suppose that ∇ 2

x L(x * , λ * ) has a positive eigenvalue. To any vector x + such that x + ∇ 2

x L(x * , λ * )x + > 0, one can associate a random deviation h(t) equal to tx + + β(t) and to -tx + + β(t) with equal probabilities satisfying

∇g n (x * ) β(t) + 1 2 t 2 x + ∇ 2 g n (x * )x + = o(t 2 ),
for all the active constraints, such that Ef (x * + h(t)) > f (x * ) for small enough t different from 0.

Theorems 1 to 3 provide a detailed picture of the local properties of a solution x * to the first order conditions of the deterministic constrained optimization problem. From Theorem 1, if x * cannot be improved upon by deterministic moves in the constrained set, the second derivative of the Lagrangian is semi negative definite on the tangent plan to the active constraints. Conversely, from Theorem 2, if there exists a direction in the tangent plan along which the Hessian of the Lagrangian is strictly positive, x * is not a local optimum of the deterministic problem, and there are local deterministic deviations in the constrained set which yield a higher value of the objective. Theorems 1 and 2 do not tell us anything on the behavior of the second derivative of the Lagrangian out of the tangent plan to the active constraints, indeed a region which is forbidden territory to the deterministic problem. Our contribution in this respect is Theorem 3. The argument is constructive. It shows that any direction along which the Hessian of the Lagrangian is positive, belonging or not to the tangent plan to the active constraints, allows to build an improving random deviation. If the number of active constraints is N a , the tangent plan to the active constraints has dimension M -N a and its complement of dimension N a is the size of the space in which the second derivative of the Lagrangian at a local deterministic optimum may be positive and generate improving random deviations.

Corollary 1. A necessary condition for a deterministic x * to be a local optimum of the random problem is that the second derivative of the Lagrangian at x * be negative semi definite.

Remark 1. All the above theorems assume qualified constraints. This allows to compute the deterministic component β(t) of the deviation through the implicit function theorem so that all the active constraints are exactly satisfied. In some economic problems, the constraints are not qualified. This for instance happens in the Lerner redistribution problem studied by [START_REF] Pestieau | Cheating ourselves: the economics of tax evasion[END_REF], where a fixed quantity of a single good must be shared between a finite number of agents whose characteristics are not publicly observed. Appendix B shows how our arguments can be adapted to the case where the constraints are not qualified. When the number of active constraints is greater than the number M of components of β(t), one can sometimes consider a subset of constraints and proceed as in the qualified case, making sure ex post that all the constraints are satisfied.

A general adverse selection problem

We apply the results of the previous section to a general principal agent setup. The principal faces a continuum of agents of different types i, i = 1, . . . , I, with whom she contracts. A deterministic contract is a K dimensional vector z. When a type i agent chooses contract z, he gets utility v i (z) while the principal receives u i (z). The functions u i and v i are increasing and concave von Neumann Morgenstern utility indices, and we allow for ex ante random contracts. The ex ante utility of a type i agent receiving a random contract z is Ev i (z), while that of the principal is Eu i (z). His type is private information to the agent. The principal knows the distribution of types in the population but does not observe individual types.

Under the revelation principle, the principal chooses a menu of random contracts (z i ), i = 1, . . . , I, solution to the program P max

I i=1 n i Eu i (z i )
subject to individual rationality constraints

Ev i (z i ) ≥ vi for all i, (p i )
and incentive constraints

Ev i (z i ) ≥ Ev i (z j )
for all i and all j.

(λ ij )

The incentive constraints (λ ij ) make sure that when the principal announces a menu of contracts (z i ) type i agents voluntarily choose the transfer zi designed for them.

In the examples that we analyze below, they are crucial in generating nonconvexities, through the presence of the utility of the other agents choices on the right hand side of the constraints. On the other hand the individual rationality constraints are not essential and could be replaced with other sorts of constraints, such as feasibility requirements.

Example 1. Monopoly regulation. The principal is a regulator observing the production q of a type i firm whose cost function C i (q) is private information. A contract z specifies a transfer t and a production level q. When a type i firm chooses a contract z = (t, q), its profit is v i (z) = t -C i (q) while the utility of the regulator is the social surplus u i (z) = S(q) -C i (q) -λt, where S(q) represents consumers surplus and λ is the (given) social cost of public funds. A random contract zi designed for firm i consists of a random transfer ti and/or a random production qi . The regulator's problem is P , where vi is the profit of a type i firm which receives zero transfer and does not produce, vi = v i (0, 0).

Example 2. Insurer as a monopolist. The probability p i of having an accident for type i agents is private information. In case of accident the wealth w of the agent is reduced by an amount . The insurance company offers a set of contracts z consisting of a premium q and a reimbursement r in case of accident. The expected profit realized by the insurer from a type i agent is u i (z) = q -p i r when this agent chooses contract z. The expected utility of such an agent is v i (z) = (1 -p i )ϕ(w -q) + p i ϕ(w -+ r -q), where the utility index ϕ is increasing and concave. A random contract zi designed for type i agents specifies a random premium qi and/or a random coverage ri in case of accident. The most realistic case may be the one where agents pay a deterministic premium but additional clauses actually restrict circumstances in which reimbursement is made in case of accident, implying random coverage. The insurer problem is P with vi being the expected utility of an uninsured type i agent v i (0, 0). Example 3. Optimal taxation. Type i agents are consumers-workers whose preferences are represented by the utility function v i (c, y) when they consume c units of a consumption good and they earn before tax income y. There is a linear technology which transforms labor into goods. A type i agent who works hours earns y = θ i , where θ i is her labor productivity. Both preferences and productivity are private information to the agent. The government observes individual income and consumption, but not separately labor supply and productivity. A weighted utilitarian government redistributes income across agents by offering a menu of contracts z i = (c i , y i ) for all types i. Let a i be the social weight of a type i agent. The contribution of type i agents to social welfare is u i (z i ) = a i v i (c i , y i ). A random contract zi specifies a random before tax income ỹi and/or a random after tax income ci (which coincides with consumption). It seems more plausible that the before-tax income remains deterministic, while after-tax income is random because there are random administration errors, tax evasion with non comprehensive audits, or voluntary random perturbations in the spirit of ordeal mechanisms. In this setup, individual rationality constraints are irrelevant, but there is a feasibility condition making sure that all that is consumed has been produced.

The Lagrangian functions associated with the general programs are respectively

L = I i=1 n i u i (z i ) + p i (v i (z i ) -vi ) + j =i λ ij (v i (z i ) -v i (z j )) (3)
for the deterministic program denoted P , and

L = I i=1 n i Eu i (z i ) + p i (Ev i (z i ) -vi ) + j =i λ ij (Ev i (z i ) -Ev i (z j )) (4)
for P .

A deterministic optimum satisfies the necessary first-order conditions given in Theorem 1.1. The second-order conditions in Theorem 1.2 involve the Hessian H of the Lagrangian evaluated at this point, which must be semi negative definite on the tangent plan to the active constraints. In the current class of models the Hessian takes a specific form. Indeed H is a IK × IK symmetric matrix whose ith diagonal block is the K × K matrix

H i = n i ∇ 2 u i (z i ) + j =i λ ij + p i ∇ 2 v i (z i ) - j =i λ ji ∇ 2 v j (z i ) (5)
while all off diagonal blocks are zero.

The matrix H i is negative definite when the sum of the first two terms, a negative definite matrix from the concavity of utilities, dominates the last sum which is positive definite. This happens in a first-best optimum, i.e., the profile (z i ) satisfies the first-order conditions and generates no envy is a local optimum. When a type i agent is not envied, the multipliers λ ji are 0 for all j = i, so that the matrix H i defined in ( 5) is negative definite by concavity of the utility function. Therefore the Hessian H is negative definite when no type of agents is envied.

The Hessian H is likely to remain negative definite when the optimum is not far from the first-best, so that the incentive constraints are not strongly binding (the Lagrangian multipliers associated with these constraints are small). Conversely, for H i to have a positive eigenvalue, at least one of the incentive constraint must have a large multiplier λ ji and it helps if the corresponding agent j is more risk averse (that is, have a larger in absolute value second derivative of her utility) than i. Of course all these quantities are determined endogenously and must be compatible with optimality of the deterministic program. We shall relate them to the fundamental parameters of the economy in some of the examples below.

A nonconcave Lagrangian does not necessarily prevent from local optimality: from Theorem 1.2, H must be negative definite on the tangent space to the active constraints. This space has dimension IK -N a when there are N a binding incentive constraints. Hence the IK dimensional square matrix H has at least IK -N a negative eigenvalues at a local maximum. It may consequently have at most N a positive eigenvalues. Of course, for Theorem 1.2 to hold when H has N a positive eigenvalues, the N a dimensional positive eigenspace of H and the IK -N a dimensional tangent space to the active constraints must have no intersection. The second-order conditions leave room for positive eigenvalues in the N a directions that do not belong to the tangent plane to the active constraints at this optimum. This property can be exploited to yield a welfare improvement through random transfers.

The intuition of the argument is as follows. Consider a local maximum (z i ) among the nonrandom contracts, and small deviations (dz i ) such that all the active constraints at the nonrandom optimum remain binding at the new point (z i + dz i ). The change in the objective is therefore

I i=1 n i (Eu i (z i + dz i ) -u i (z i )) = L -L, (6)
where L is the Lagrangian defined by ( 4) and evaluated at the final random contract, while L is the Lagrangian defined by (3) and evaluated at the initial deterministic optimum. Since the initial deterministic optimum satisfies the first-order conditions in Theorem 1.1, the reform yields at most a second-order change to the objective,

L -L = 1 2 E I i=1 (dz i ) H i (dz i ) + o(||dz i || 2 ). ( 7
)
It turns out that one can build deviations dz that increase the objective of the principal when one of the matrices (H i ), say H j , has a positive eigenvalue.

The deviation involves two parts: a deterministic part β(t) chosen so that the binding constraints of the program at the reference point stay binding along the deviation, and for type j agents a lottery with zero expected value in the direction of some K dimensional eigenvector x + j associated with the positive eigenvalue of H j . The deviation is parameterized with a small positive scalar t which measures the scale of the change along the direction x + j . For type j the deviation takes two values

dz 1 j = tx + j + β j (t), dz 2 j = -tx + j + β j (t),
drawn independently with equal probability. The proof of Theorem 3 shows that β(t) is of the order of t 2 at most. For t close enough to 0, it therefore is negligible in ( 7). Thus ( 6) and (7) yield

I i=1 n i (Eu i (z i + dz i ) -u i (z i )) = 1 2 t 2 x + j H j x + j + o(t 2 ) > 0.
This yields the following result:

Proposition 1. Consider a nonrandom optimum among the nonrandom contracts, which satisfies the conditions laid down in Theorem 1. Then social welfare can be improved upon through local random contracts if the Hessian H of the nonrandom Lagrangian has at least one positive eigenvalue.

By Theorem 3.1, local randomization deteriorates the objective of the principal when all the eigenvalues of the Hessian H are negative. The condition for the existence of valuable randomizations given in Proposition 1 is necessary and sufficient when H is regular, i.e., all the eigenvalues of H differ from 0.

A taxation example

We particularize the abstract model of the previous section to a simple version of the taxation example described in section 3. There are two types of agents in the economy, n 1 agents of type 1 and n 2 agents of type 2, n 1 + n 2 = 1. Type 1 agents are 'disabled' and do not supply any labor. They consume c 1 units of the consumption good, yielding a utility level u 1 (c 1 ), where u 1 is increasing and concave. Type 2 agents consume c 2 and produce y 2 units of good. Their preferences are represented by u 2 (c 2 )-v 2 (y 2 ), with u 2 increasing and concave, v 2 (y 2 ) increasing, convex, and v 2 (0) = 0.

Given its redistributive tastes, parameterized by the positive numbers (a 1 , a 2 ), a government knowing the agents types chooses a deterministic allocation (c 1 , c 2 , y 2 ) which maximizes

a 1 n 1 u 1 (c 1 ) + a 2 n 2 [u 2 (c 2 ) -v 2 (y 2 )] subject to n 1 c 1 + n 2 c 2 ≤ n 2 y 2 . ( 8
)
The first-best allocation solution to this problem satisfies the two first order conditions a 1 u 1 (c 1 ) = a 2 u 2 (c 2 ) and u 2 (c 2 ) = v 2 (y 2 ). It varies continuously with the ratio a 2 /a 1 and a simple manipulation of the the first order and feasibility conditions shows that when a 2 /a 1 increases, type 2 benefits both through a higher consumption c 2 and a lower labor supply y 2 , while type 1 looses with a smaller c 1 .

Disabled agents cannot work, and therefore cannot imitate the workers. To study the second best optimum, there is a single incentive constraint to consider: the type 2 workers must not want to fake type 1 disability, i.e.

u 2 (c 2 ) -v 2 (y 2 ) -u 2 (c 1 ) ≥ 0.
Note that the left hand side of the above inequality, evaluated at the first best allocation is increasing in a 2 /a 1 : there is a threshold a such that for all a 2 /a 1 > a, the incentive constraint does not bind and the first and second best coincide. On the other hand, for a 2 /a 1 < a the second-best allocation differs from the first-best. It is solution of the system formed by ( 8), the binding incentive constraint

u 2 (c 2 ) -v 2 (y 2 ) = u 2 (c 1 ), ( 9
)
and the first-order condition u 2 (c 2 ) = v 2 (y 2 ). 2 Remark that in this specific example the second-best allocation (c * 1 , c * 2 , y * 2 ) does not depend on the social weights (a 1 , a 2 ), whenever it differs from the first-best.

2 One can check that the solution to this system is local maximum, using Theorem 1.2. The tangent plane to the active constraints is

-n 1 -n 2 n 2 -u 2 (c 1 ) u 2 (c 2 ) -v 2 (y 2 )   dc 1 dc 2 dy 2   = 0 0 .
13 Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

We can now apply the techniques developed earlier in the paper to find the cases where a small random deviation from the deterministic second-best may increase the government objective. The Lagrangian of the deterministic problem is

L = a 1 n 1 u 1 (c 1 ) + a 2 n 2 [u 2 (c 2 ) -v 2 (y 2 )] + ρ [n 2 y 2 -n 1 c 1 -n 2 c 2 ] + λ [u 2 (c 2 ) -v 2 (y 2 ) -u 2 (c 1 )] ,
with Hessian

H =   a 1 n 1 u 1 (c 1 ) -λu 2 (c 1 ) 0 0 0 (a 2 n 2 + λ) u 2 (c 2 ) 0 0 0 -(a 2 n 2 + λ) v 2 (y 2 )   .
It follows from Proposition 1 that there is a profitable local random deviation if and only if the Hessian has a positive eigenvalue, that is a

1 n 1 u 1 (c 1 ) - λu 2 (c 1 ) > 0.
Proposition 2. A necessary and sufficient condition for the existence of an open interval of values of social weights where the deterministic second-best optimum is locally dominated by a random allocation is

r A 1 (c * 1 ) r A 2 (c * 2 ) 1 + n 1 n 2 u 2 (c * 2 ) u 2 (c * 1 ) < 1. ( 10
)
where r A i (c) = -u i (c)/u i (c) is the coefficient of absolute risk aversion of type i when consuming c.

Proof. Eliminating the multiplier ρ between the two first order conditions

∂L ∂c 1 = ∂L ∂c 2 = 0
For all such deviations, it must be that

dc 1 dc 2 dy 2 H   dc 1 dc 2 dy 2   ≤ 0.
From the first-order conditions, there is no distortion at the top for type 2 agents, u 2 (c 2 ) = v 2 (y 2 ). Therefore the only deviations (dc 1 , dc 2 , dy 2 ) from the deterministic extremum in the tangent plan to the constraints are proportional to (0, 1, 1). Since the sub-Hessian H 2 corresponding to c 2 and y 2 is negative definite, any local extremum of the Lagrangian is a local maximum.

yields the multiplier λ associated with the incentive constraint (9)

u 2 (c * 1 ) n 1 + u 2 (c * 2 ) n 2 λ = a 1 u 1 (c * 1 ) -a 2 u 2 (c * 2 ).
The positivity of the eigenvalue is equivalent to

a 2 a 1 u 2 (c * 2 ) u 1 (c * 1 ) < 1 - r A 1 (c * 1 ) r A 2 (c * 2 ) 1 + n 1 n 2 u 2 (c * 2 ) u 2 (c * 1 )
, which gives the desired result.

Since the positive eigenvalue is associated with the eigenvector with all weight on c 1 , the deviation can put randomness on the disability allowance c 1 . For randomness to be worthwhile, (10) requires that type 2 be substantially more risk averse than type 1. The domain of parameters a 2 /a 1 with improving local random deviation is larger all other things equal when the proportion of type 1 agents is smaller, or when c * 2 is large relative to c * 1 . Since by ( 9

) c * 2 is larger than c * 1 , u 2 (c * 2 ) ≤ u 2 (c * 1 )
, and a sufficient condition for (10) to hold is

r A 1 (c * 1 ) < n 2 r A 2 (c * 2 ).

Discrimination through risk exposure

The general framework used in section 3 also applies to monopoly pricing analyzed in [START_REF] Mussa | Monopoly and Product Quality[END_REF] and [START_REF] Maskin | Monopoly with incomplete information[END_REF]. The principal is a monopolist producing a commodity in different qualities. The unit cost c(q) of one good of quality q is increasing and convex, with c(0) = 0. Each agent buys at most one good. A type i agent buying a quality q good at price p has utility v i (θ i q -p), with v i increasing and concave. Tastes represented by v i and the valuation θ i for the quality are private information. By convention valuations increase with i, θ i < θ i+1 for all i ≤ I -1.

Prices and/or quality may be random. The problem of the seller is to choose a profile (p i , qi ), i = 1, . . . , I, which maximizes her expected revenue

I i=1 n i E[p i -c(q i )]
subject to participation constraints, Ev i (θ i qi -pi ) ≥ 0 for all i = 1, . . . , I, and self-selection constraints, Ev i (θ i qi -pi ) ≥ Ev i (θ i qj -pj ) for all i, j = 1, . . . , I.

Deterministic optimum

The study of the deterministic optimum builds on the results of [START_REF] Maskin | Monopoly with incomplete information[END_REF] (see their Proposition 2) and ?. The specification of the utility functions is different here, but the argument can be easily transposed. Indeed the single crossing condition, v qθ > 0, is satisfied. Then, provided that quality increases with valuation, q i increases with i, the individual rationality constraint of type 1 consumers (associated with Lagrange multiplier λ 1 ) and the local neighboring downward incentive constraints are the only relevant constraints in the nonrandom problem. Let λ i be the Lagrange multiplier associated with the nonrandom self-selection constraints

v i (θ i q i -p i ) ≥ v i (θ i q i-1 -p i-1 ) for all i > 1.
The Lagrangian is

L = I i=1 n i [p i -c(q i )] + λ 1 v 1 (θ 1 q 1 -p 1 ) + I i=2 λ i [v i (θ i q i -p i ) -v i (θ i q i-1 -p i-1 )] .
Differentiating the Lagrangian with respect to q i gives the first-order condition

∂L ∂q i = -n i c (q i ) + λ i θ i v i -λ i+1 θ i+1 v i+1 = 0, (11)
where we use the convention λ I+1 = 0. The first-order conditions with respect to prices yield λ i v i = N i for all i, where N i is the fraction of the population with valuation θ at least equal to θ i (this number is decreasing in i), N i = I j=i n j for i ≤ I and N I+1 has been set to zero. Therefore, (11) rewrites

n i c (q i ) = N i θ i -N i+1 θ i+1 . ( 12
)
We have neglected the non negativity and the monotonicity of q i in the above program. For the solution obtained from (12) to be economically meaningful, these properties have to be satisfied, which turns out to hold provided the following Assumption is met.

Assumption 1. The following properties hold:

1. N i θ i > N i+1 θ i+1 for all i;

2. the sequence (N i θ i -N i+1 θ i+1 ) /n i is increasing with i;

3. the marginal cost of quality c (q) is zero at the origin and goes to infinity when q goes to infinity.

Random deviations

Under Assumption 1, the deterministic optimum is defined by a profile of qualities satisfying (12) while prices are given by the I binding constraints.

To see whether random deviations from this deterministic optimum can be profitable, we study the second derivative of the Lagrangian. Since λ i v i = N i for all i, the Hessian of the Lagrangian is a diagonal matrix whose ith diagonal entry is

∂ 2 L ∂q 2 i = -n i c (q i ) + λ i θ 2 i v i -λ i+1 θ 2 i+1 v i+1 = -n i c (q i ) -N i θ 2 i r A i + N i+1 θ 2 i+1 r A i+1 ,
where r A i is the coefficient of absolute risk aversion of type i at the deterministic optimum. Theorem 3 implies: Proposition 3. Suppose that the Hessian is of full rank at the deterministic optimum. Under Assumption 1, it is worthwhile to locally randomize the quality designed for type i consumers if and only if

N i+1 θ 2 i+1 r A i+1 > N i θ 2 i r A i + n i c (q i ). (13)
Condition ( 13) confirms some of the intuitions seen earlier in the taxation example. From N I+1 = 0, it follows that it is never optimal to randomize the quality offered to the highest type: this comes from the fact that no other agents envy people at the top. The more convex the cost function, the higher the right hand side of (13), and the more reluctant the seller will be to randomize quality. The risk aversions of the consumers matter as expected. It is never worthwhile to randomize the quality offered to risk neutral agents.

Remark 2. In the specification used by [START_REF] Mussa | Monopoly and Product Quality[END_REF] or [START_REF] Maskin | Monopoly with incomplete information[END_REF], the utility of type i consumers is separable and quasi-linear in the price, v(q i , θ i ) -p i . Then the monopolist cannot increase its expected profit with a local random deviation. To see this, recall that, by Theorem 1.2, second-order conditions for a local maximum only involve deviations in the tangent space to the I binding constraints. Since the consumers' preferences are separable, these constraints allow to derive all the I expected prices as functions of the I qualities and to substitute them in the expression giving the monopolist profit. One gets an unconstrained optimization problem with respect to the qualities. It follows that at the deterministic optimum the Hessian is negative definite for all quality deviations, and by Theorem 3 local randomness cannot be profitable. 3where x is a point on the segment [x * , x]. From part 1 of Theorem 1, the second term on the right hand side is equal to zero. The third one is strictly negative in the chosen neighborhood since ∇ 2

x L(x * , λ) is negative definite by assumption. Therefore, for x = x * , L(x * , λ * ) > EL(x, λ * ).

The active constraints at x * are satisfied at equality, while the inactive constraints stay inactive in a suitable neighborhood of x * . It follows that λ * g(x * ) = λ * g(x) = 0, and consequently

f (x * ) > Ef (x).
We now prove part 2. By assumption ∇ 2

x L(x * , λ) has one positive eigenvalue and the associated eigenvector is a suitable x + . From part 2 of Theorem 1, note that x + cannot belong to the tangent space to the active constraints, i.e., g n (x * ) x + = 0 for some n such that g n (x * ) = 0.

By (2) the deviations h(t) are such that Eg n (x * + h(t)) = g n (x * ) for the active constraints, i.e.

1 2 g n (x * + tx + + β(t)) + 1 2 g n (x * -tx + + β(t)) = g n (x * ). ( 14
)
We are going to show that there is a β(t) satisfying ( 14) which is at most O(t z ) for some z ≥ 2. If there are N a active constraints, (14) is a system of N a equations in the unknown β(t). A Taylor expansion of ( 14) yields, for all active constraints n,

∇g n (x * ) β(t) + 1 4 (tx + + β(t)) ∇ 2 g n (x * )(tx + + β(t)) + 1 4 (-tx + + β(t)) ∇ 2 g n (x * )(-tx + + β(t)) = o(t 2 ).
Since the constraints are qualified, the N a × M matrix of derivatives ∇g n (x * ) of the active constraints is of full rank.

Since by assumption the constraints are qualified, the rank of this matrix is N a . We fix M -N a components of β(t) at zero, so that the N a non zero components of β(t) form a vector β(t) which can be solved for locally by applying the implicit function theorem to the system made of the N a active constraints. For each active constraint, let G n be the 1 × N a subvector of 20 Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée) ∇g n (x * ) associated with the components of β(t). From the implicit function theorem, the function β(t), with β(0) = 0, is well defined and continuously differentiable in a neighborhood of the origin. Since ∇g n (x * ) β(t) = G n β(t), the Taylor expansion of ( 14) can be rewritten as

G n β(t) + 1 2 t 2 x + ∇ 2 g n (x * )x + + 1 2 β(t) ∇ 2 g n (x * )β(t) = o(t 2 ),
for every n in N a . The expression in the left hand side of this equation is of smaller order than t 2 when t is in a neighborhood of the origin since β(t)±tx + is at most O(t). Stacking up these N a equalities gives

G β(t) + 1 2 t 2 a + 1 2 b = o(t 2 ), (15)
where a and b are two

N a × 1 vectors, a =    . . . x + ∇ 2 g n (x * )x + . . .    , b =    . . . β(t) ∇ 2 g n (x * )β(t) . . .    ,
and G is the (N a × N a ) matrix obtained by stacking up the N a subvectors G n of the active constraints. From the qualification of the active constraints G is of full rank and invertible. Multiplying through by the inverse of G shows that b can be neglected in (15). Indeed, t 2 a is O(t z ) for some z ≥ 2, so that β(t) is at most O(t z ), and thus b is at most O(t 2z ). As a result, one gets

G β(t) + 1 2 t 2 a = o(t 2 ), (16)
or equivalently, for all active constraint n,

∇g n (x * ) β(t) + 1 2 t 2 x + ∇ 2 g n (x * )x + = o(t 2 ),
where the M -N a components of β(t) associated with inactive constraints at x * are zero, and the N a remaining components of this vector are obtained from ( 16). This is the expression given in the statement of Theorem 3 that is satisfied by the deterministic component β(t) of the deviation. Now, by the property ( 14) of the random deviation, From the qualification of constraints, we know that stacking up the vectors ∇g n (x * ) for the active constraints n gives a matrix of rank N a . As in the proof of Theorem 3, we fix M -N a components of β(t) at zero, and denote β(t) the N a non zero components, chosen so that the extracted matrix is of full rank. For each active constraint, let G n be the 1 × N a subvector of ∇g n (x * ) associated with the components of β(t) and J n the 1 × N a subvector of x + ∇ 2 g n (x * ) also associated with the non zero components of β. The Taylor expansion becomes

1 2 f (x * + tx + + β(t)) + 1 2 f (x * -tx + + β(t)) -f (x * ) = 1 2 L(x * + tx + + β(t
[G n + tJ n ] β(t) + 1 2 t 2 x + ∇ 2 g n (x * )x + + 1 2 β(t) ∇ 2 g n (x * )β(t) = o(t 2 ).
Let G and J be the N a × N a matrices obtained by stacking up the G n and J n over the active constraints. By the qualification of constraints, G is of full rank, so that G + tJ is invertible for small enough t. The second and third terms on the left hand side are respectively O(t z ) and O(t 2z ) at most for all active constraints, where z ≥ 2. Therefore the terms β(t) ∇ 2 g n (x * )β(t) are negligible, β(t) is at most O(t z ), and the expression in the statement of the Theorem holds.

Finally the expansion of L(x * + tx + + β(t), λ * ) -L(x * , λ * ) = f (x * + tx + + β(t)) -f (x * ) yields

∇ x L(x * , λ * )(tx + + β(t)) + 1 2 t 2 x + ∇ 2 x L(x * , λ * )x + + o(t 2 ) = 1 2 t 2 x + ∇ 2 x L(x * , λ * )x + + o(t 2 ) > 0,
which completes the proof.

B The Lerner case

When the number N a of active constraints at the deterministic optimum is greater than the number M of nonzero components of the vector β(t), the implicit function theorem does not apply and the argument in the proof of Theorem 3 does not work. A possible way out however is to restrict attention to a subset of n qualified constraints, and hope that the N a -n remaining constraints are satisfied when one implements the random deviation exhibited in Theorem 3.

In order to illustrate this point, let us consider the example of the redistribution problem in a Lerner world studied by [START_REF] Pestieau | Cheating ourselves: the economics of tax evasion[END_REF]. In this example, there are two agents, i = 1, 2, and one consumption good. Utility of agent i when she consumes c units of the good is u i (c). Each agent is initially endowed with y units of the good. The type i is not publicly observed. Therefore, if the tax authority wants to allocate (nonrandomly) c i units of the good to agent i, the two incentive constraints u 1 (c 1 ) ≥ u 1 (c 2 ), u 2 (c 2 ) ≥ u 2 (c 1 ), must be met. In addition, feasibility requires c 1 + c 2 ≤ 2y.

5

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

22

  Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

  -tx + + β(t), λ * ) -L(x * , λ * ) = ∇ x L(x * , λ * ) β(t) + 1 2 t 2 x + ∇ 2 x L(x * , λ * )x + + 1 2 β(t) ∇ 2 x L(x * , λ * )β(t) + o(t 2 ). Since x * is a local deterministic maximum, ∇ x L(x * , λ * ) = 0. Moreover, by (16), β(t) = O(t z ) at most, so that β(t) ∇ 2 x L(x * , λ * )β(t) is at most O(t 2z). As a result,Ef (x * + h(t)) -f (x * ) =

	), λ * ) +	1 2	L(x 1 2 t 2 x + ∇ 2 x L(x

* * , λ * )x + + o(t 2 ) > 0,

(17)

by the choice of x + .

Proof of Theorem 2. The deviation is deterministic, h(t) = tx + + β(t), and a Taylor expansion of (1) gives

∇g n (x * ) β(t)+ 1 2 t 2 x + ∇ 2 g n (x * )x + +tx + ∇ 2 g n (x * )β(t)+ 1 2 β(t) ∇ 2 g n (x * )β(t) = o(t 2 ), or ∇g n (x * ) + tx + ∇ 2 g n (x * ) β(t)+ 1 2 t 2 x + ∇ 2 g n (x * )x + + 1 2 β(t) ∇ 2 g n (x * )β(t) = o(t 2 ).

Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

Dealing with the situation where the Hessian has a zero eigenvalue in some directions would involve looking at derivatives of higher order in these directions. 6 Documents de Travail du Centre d'Economie de la Sorbonne -2011.62 (Version révisée)

This is an instance of a more general phenomenon which is at work in[START_REF] Strausz | Deterministic versus stochastic mechanisms in principal-agent models[END_REF]. When some variables linearly enter the Lagrangian function, the corresponding entries of the Hessian of the Lagrangian are identically zero and the structure of the problem may simplify drastically. In the model studied by[START_REF] Strausz | Deterministic versus stochastic mechanisms in principal-agent models[END_REF], there are I known active constraints with I associated transfers entering linearly both the constraints and the objective. The procedure sketched in Remark 2 then implies that there is no scope for improvement through local random deviations.

We are most grateful to Bernard Salanié for his numerous comments.

Appendices

A Proofs of the mathematical statements of Section 2

Proof of Theorem 3. We start with part 1. The mathematical expectation of a Taylor expansion of L in a suitable neighborhood of x * is

In this example, the vector (c 1 , c 2 ) is two-dimensional, i.e., M = 2. Still, at the nonrandom optimum, the three constraints hold at equality: incentive compatibility actually requires c 1 = c 2 and feasibility implies c 1 = c 2 = y.

We can study the usefulness of randomization by adapting the argument in the proof of Theorem 3. Assume that the tax authority only cares about the welfare of agent 1. Random redistribution toward this agent, if possible, is likely to be limited by the fact that agent 2 will mimic agent 1, when she receives too much. Let us therefore restrict our attention to the following subset of the active constraints at the nonrandom optimum:

and

We shall verify ex post that the remaining constraint, u 1 (c 2 ) ≤= Eu 1 (c 1 ), is indeed satisfied, with a Lagrange multiplier equal to 0. The corresponding Lagrangian is

Its Hessian at the deterministic allocation c 1 = c 2 = y is

with from the first-order condition

The eigenvalue λu 2 (y) is always negative. The other one is positive if and only if

u 2 (y) u 2 (y) .

Let x + = (1, 0) stand for the eigenvector associated with this eigenvalue. Consider the lottery with the two outcomes tx + + β(t) and -tx + + β(t), each one occurring with the same probability, and β(t) = (β 1 (t), β 2 (t)) . The first component of the two-dimensional vectors ±tx + +β(t) gives the consumption of agent 1, and the second the consumption of agent 2. For t close enough to 0, the vector β(t) is characterized by the active constraints as in Theorem 3:

This yields

When the Hessian has a positive eigenvalue, this randomization increases the welfare of agent 1:

There remains to check that type 1 incentive constraint is satisfied. But we have just seen that Eu 1 (c 1 ) > u 1 (y) and since β 2 (t) is negative, c 2 is smaller than y. This completes the analysis of this variant of the Lerner model.