f ENTRAl CIRCUIATION BOOKSTACKS

on or before the :L«H»» ■ » minimom

fee OT ^/S.ww ^ rea»on»

^H, -,,.1..!.-. -* -*£?%£. in dismissal .rem

Jor disciplinary action and may

the University. „,.„»« CENTER, 333-8400

TO RENEW CALL «"»■« "S^, u^NA-CHAMPA^

Htf*

-21397

w„««ta.i»*--.«1»—he**bSS

previous due date.

Digitized by the Internet Archive

in 2011 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/mechanismswithno1438chak

s~

BEBR

FACULTY WORKING PAPER NO. 1438

THE LiBR^v OF THE

|f .LLlNOIS

Mechanisms with No Regret:

Welfare Economics and Informaiton Reconsidered

Bhaskar Chakravorti

WORKING PAPER SERIES ON THE POLITICAL ECONOMY OF INSTITUTIONS NO. 10

College of Commerce and Business Administration Bureau of Economic and Business Research University of Illinois, Urbana-Champaign

BEBR

FACULTY WORKING PAPER NO. 1438

College of Commerce and Business Administration

University of Illinois at Urb ana -Champaign

March 1988

WORKING PAPER SERIES ON THE POLITICAL ECONOMY OF INSTITUTION NO. 10

Mechanisms with No Regret: Welfare Economics and Information Reconsidered

Bhaskar Chakravorti , Assistant Professor Department of Economics

MECHANISMS WITH NO REGRET: He I fare Economics and I nf or mat ion Reconsidered

by

Bhaskar Chakravorti

Department of Economics

University of Illinois at Urbana-Champai gn

Champaign, IL 61820

February 1988

Abstract

This paper achieves five objectives relating to the design of efficient mechanisms in "Post 1 ewai te-Schmei dl er" economies with asymmetric information. First, it is argued that the various notions of implementation used in the literature are either too strong or too weak; an appropriate notion is defined. Second, it is shown that it is impossible to design an individually rational and efficient mechanism using Bayesian equilibrium as the solution concept. Third, a complete characterization is given of "No regret-implementation" using mechanisms with communication and no binding commitments, introduced by Green and Laffont (1987). We propose a further refinement of their posterior optimal refinement of Bayesian equilibria. Fourth, it is shown that though such mechanisms cannot implement interim individually rational and efficient performance standards, they can implement ex post individually rational and efficient standards. Finally, it is shown that even under asymmetric information such mechanisms implement any performance standard that is Nash-i mpl ementabl e, such as the core or the Walrasian correspondence. Thus far, this is the only result that demonstrates the possibility of designing efficient mechanisms in general asymmetric information economies.

1 . Introduction

Imagine an economy with asymmetric information. A performance standard is a non-empty set of socially "desirable" state-contingent allocations. Given the incompleteness of information about the realized state of the world, a mechanism is required to implement a given performance standard. An implementing mechanism is a game of incomplete information such that its set of equilibrium outcomes is non-empty and is contained within the standard. Most economies aspire towards the two basic objectives of individual rationality and efficiency. This paper reports a fundamental difficulty with any attempt to design mechanisms for implementing individually rational -efficient performance standards, and then proposes a solution to this crucial problem. In light of the difficulties that were just alluded to, this is the only result that demonstrates the possibility of designing individually rat i onal -ef f i c i ent mechanisms in general asymmetric information economies. Moreover, we show that even in asymmetric information environments it is possible to implement any standard that is Nash-i mpl ementabl e, such as the core or the Walrasian correspondence.

Broadly, our strategy will be to proceed in five steps. First, we shall argue that arriving at the appropriate definition of "implementation" is a rather subtle issue and that the bulk, of the vast literature on the subject of mechanism design has appealed to definitions that are either too strong or too weak. Second, we show that we can never hope to design a mechanism such that all of its Bayesian equilibrium outcomes are individually rational and efficient (in either an interim or an ex post sense, as defined in Holmstrom and Myerson (1983)). In other words, there exist no individually rat i onal -effi ci ent performance standards that are

also Bayes ian- implement able. Third, we explore the implementation

properties of "mechanisms with no regret": where the agents do not make binding commitments during the play of the game and an equilibrium is a voluntary signing of a contract representing a binding agreement. We further sharpen a criterion for refinement of Bayes ian equilibria due to Green and Laffont (1987) which requires that the components of the equilibrium strategy profile retain their mutual best-response properties even if the players are permitted to revise their strategies after observing the actions of others. A complete characterization of No Regret -implementabi I ity (which is very different from Green and Laffont's characterization of posterior implementabi I ity) is provided using our refinement of Green and Laffont's equilibrium as the solution concept. Fourth, we show that there exists a mechanism with no regret that implements the ex post individually rat i onal -ef f i c i ent standard in the class of problems analyzed here. Interim individually rat i ona 1 -ef f i c i ent standards still remain non-i mpl ementabl e. Finally, we show that such mechanisms implement any Nash- i mpl ementabl e standard.

Juxtaposed with recent literature on the subject, our findings have several interesting implications: (i) We prove some pessimistic conjectures made by Palfrey and Srivastava (1987a) regarding Bayes i an- i mpl ementat i on. (ii) We show that the negative conclusions of Green and Laffont (1987) on implementation using mechanisms with no regret can be reversed for the class of problems that we study. (iii) The most widely studied concept of implementation is Nash-i mpl ementat i on whose origins lie in the classic work of Maskin (1977). Maskin's characterization of Nash- i mpl ementab 1 e standards (also see Saijo (1988)) has been criticized on the grounds that it applies only to complete information settings. Our results show that the class of standards that Maskin had identified as being i mpl ementabl e

can be implemented (by mechanisms with no regret) even when information is asymmetric. (iv) Finally, we find that appropriate refinements of Bayesian equilibria broadens the scope mechanism design — a fact discovered by Palfrey and Srivastava (1987b) for economies with private values and by Moore and Repu 1 1 o (1988) for economies with complete information.

1.1 "Full", "Weak" and Just Plain I mp I ement at i on

At the heart of some of the differences between the findings of this paper and those of Palfrey and Srivastava (1987a) and Green and Laffont (1987) lies the definition of implementation itself. Our notion of implementation is as defined in the first paragraph of the paper. This is distinct from the stronger notion of full implementation (Mask in (1977), Dasgupta, Hammond and Mask in (1979), Postlewaite and Schmeidler (1986)), which requires that the set of equilibrium outcomes of a mechanism and the performance standard must coinci de. On the other hand, there is a notion of weak implementation, which simply requires that the set of equilibrium outcomes should contai n the standard. (A special case of weak implementation is truthful implement at ion (Myerson (1979), Harris and Townsend (1981)), which is widely used in theoretical and applied models that appeal to the Revelation Principle). As Postlewaite and Schmeidler (1986), Repullo (1986) and others have argued, rather convincingly, weak implementation ignores the possibility that the mechanism could have equilibrium outcomes that lie outside the standard which could, in addition, be more salient (Pareto-super i or, for example) than those contained in the standard.

In other words, weak implementation is too weak. We argue that full implementation is, for some purposes, too strong. The latter may be an

appropriate concept if one is interested in possibility results since a standard that is fully i mpl ementabl e is also i mpl ementabl e. However, if one is interested in impossibility results, implementation (as defined in the first paragraph of the paper) is the notion that one should focus on: a standard that is not fully i mpl ementabl e may still be i mpl ementabl e, whereas one that is not i mpl ementabl e can never be fully i mpl ementab 1 e. To summarize, given that both i mpl ementabi 1 i ty and full i mpl ementab i 1 i ty are satisfactory from the viewpoint of a mechanism designer, in any study of the limits and possibilities of mechanism design, both the notions deserve our attention.

1.2 Efficient Mechanisms

An efficient mechanism is a game such that all of its equilibrium outcomes are efficient. Palfrey and Srivastava (1987a) have shown that neither the interim efficient set nor the ex post efficient set is fully Ba yes i an-i mpl ementabl e. Disappointing as this may be, this does not imply that we cannot hope to design an efficient mechanism since there still remains the possibility of Bayes i an-i mpl ement i ng either the interim or ex post efficient set (and their subsets).

A crucial condition called "Bayesian Monotoni ci ty" is necessary for full Bayesi an-i mpl ementabi 1 i ty. It can be checked that a standard that does not satisfy Bayesian monotonicity can still have subsets that do satisfy the condition. Consider a performance standard <p defined such that <p - <p' u </>" where <p' is Bayesian monotonic and <p" is not. By construction, <p is not Bayesian monotonic. If <p' is fully i mpl ementabl e, and under certain conditions it is, then <p is Bayes i an-i mpl ementab 1 e even though it is not fully Bayes i an- i mpl ementabl e. To prove a stronger statement which

says that neither one of the efficient sets can be Bayes i an-i mpl emented, it needs to shown that an even weaker condition, (given in this paper) which is necessary for Bayes i an-i mpl ementati on, is violated. In the paper, we prove such a proposition by imposing an additional restriction of individual rationality. The latter rules out uninteresting outcomes which assign all resources to one individual and yet are efficient and trivially i mpl ementabl e.

2.3 Efficient Mechanisms with No Regret

The next step in the agenda is to address the problem of non-existence of individually rat i onal -ef f i ci ent mechanisms by exploring the possibilities with mechanisms where agents can communicate but make no binding agreements during the play of the game. To model such mechanisms, we follow the lead of Green and Laffont (1987). Their approach is to pose the following question: which one of the Bayesian equilibria of a normal form game will survive if the agents were not committed to their Bayesian equilibrium actions? An equilibrium that survives is interpreted as a voluntary signing of a contract representing a binding agreement.

Consider a normal form Bayesian game where every player takes into consideration the fact that the equilibrium actions of other players will be observable. Hence, a Bayesian equilibrium strategy profile will survive only if the mutual best response property of its components is not destroyed even after new information is acquired through the observation of the actions of others. Any Bayesian equilibrium that passes this test is a posterior optimal agreement in the sense of Green and Laffont.

In this paper, we shall be interested in those agreements that are robust in the following sense. We refine the set of equilibria even

further by imposing the following consistency condition: two posterior optimal equilibria s and s' must not destroy each other, i.e. the information revealed when s is played does not invalidate the optimal i ty of s' and vice versa. Any equilibrium that survives is a common knowledge

potential endogenous source of information. A robust agreement/equilibrium

* is a list of strategies s such that it is common knowledge that there is

* no other potential source of information that would destroy s . The fact

that agents are not committed a priori to any agreement and that we do not

expect agents to ignore common knowledge information sources motivates our

consistency requirement. The set of posterior optimal equilibria that

satisfies this consistency requirement is referred to as the set of

Bayesian equi I ibria with no regret in the sequel. The argument behind this

can be seen most easily by way of a simple example.

Example I: Consider a game with two players and three states of the

world: "Rain", "Shine" and "Cloudy". Player 1 chooses T or B and is

completely uninformed. Her prior beliefs are that there is an equal chance

of any one of the states occurring. Player 2 chooses L, M or R and is

completely informed. Their payoffs are given in Figure 1. Four Bayesian

equilibria of this game are given in Figure 2: s = (s , s ) , s' = (s', s'),

a » a 12 12

* * *

s" = (s", s") and s - {s , s ) . 12 12

[Insert Figures 1 and 2 here. ] Each player can revise his/her strategy after observing the other player's action. A Bayesian equilibrium will survive Green and Laffont's test if and only if such observation does not lead to a revision of either player's strategy in equilibrium. Since an equilibrium is a pair of strategies that are common knowledge functions, Player 1 could conceivably acquire some information if Player 2's action were associated with a unique state. Observe that the equilibrium s is non-revealing. Given no revision

of information, s survives. In the equilibrium s' Player 1 can distinguish "Shine" from the other states. However, s' continues to remain a best response to s' even though Player 1 can partition the state space in the following way: {{Rain, Cloudy}, {Shine}}. Thus, s' also survives. Next, check that in the equilibrium s" Player 1 can distinguish "Cloudy" from the other states. Given this new information, s" is no longer a best response to s" since in the "Cloudy" state, Player 1 would do better by switching to 7. Thus, the Bayesian equilibrium s" is not posterior optimal. Finally,

check that s is fully revealing and even under complete information s is

* *

a best response to s . Therefore s survives too.

* Thus, we are left with three equilibria s, s' and s that are

posterior optimal and are, therefore, three potential agreements according

to Green and Laffont. We shall argue that s and s' may not be expected to

survive. Suppose that s is being considered as a potential agreement

between the players. Check that s cannot be destroyed by any new

information and, therefore, represents an agreement that is a Bayesian

equilibrium with no regret. Thus, it is common knowledge that there is an

* agreement s which is fully revealing. Since there is no binding

* commitment, Player 1 could wait for s to be played and then withdraw her

* commitment to s and evaluate s in light of the complete information

revealed by the play of s . s is no longer a best response to s since in

the "Cloudy" state Player 1 would do better by switching to B. s' is also

destroyed by the same argument. In a normal form game, the players make

all these calculations before playing the game as j_f the sequence of play

described above were possible, and in one shot arrive at an equilibrium.

This formulation and the consistency condition appears to be a natural

consequence of Green and Laf font's model of games with no binding

commi tments.

For arbitrary games, in general, the set of Bayesian equilibria with no regret may be empty. However, we shall prove existence of such a set for any mechanism that we use for our implementation results.

Green and Laffont's notion of poster i or-i mpl ementabi 1 i ty is a form of weak implementation with their refinement of equilibrium as the solution concept. They argue that mechanisms for posterior implementation have two limitations in general: (a) such mechanisms cannot posterior implement any performance standard that cannot be weakly Bayes i an-i mpl emented; and (b) in two-person economies, such mechanisms can posterior implement only those standards that can take on essentially two values throughout the range of observations of the players. We hope to show that neither (a) nor (b) is any cause for alarm. Green and Laffont's mechanisms can actually do better than Bayes i an-i mpl ementati on mechanisms. This apparent contradiction can be resolved by keeping in mind the fact that while Green and Laffont's analysis relates to weak implementation, we focus on i mpl ementabi 1 i ty itself. As the Postlewaite and Schmeidler (1986), Repu 1 1 o (1986) examples demonstrate, the latter approach is the more compelling one.

There are other differences between our framework and that of Green and Laffont: while they analyze a two-person abstract choice problem, we focus on a "Post 1 ewai te-Schmei dl er" economy (Postlewaite and Schmeidler (1986)), i.e. an n-person (n > 2) Arrow-Debreu-McKenz i e pure exchange economy with asymmetric and non-exclusive information about individual preferences; they consider only singleton-valued performance standards while we analyze the more general case; in Green and Laffont's model, private information can take on uncountable values ranging from the "best news" to the "worst news", while we consider private information about a finite set of states of the world with no explicit ranking of the states.

As noted earlier, Palfrey and Srivastava's (1987b) results imply that,

given non-exclusive information, it is possible to fully implement efficient performance in economies with private values by considering undominated Bayesian equilibrium as the solution concept. The more general situation, i.e. economies with common values still suffered from the non-existence of efficient mechanisms. Our findings offer a solution to this problem.

2. Prel iminaries

An asymmetric informat ion economy, e, is a triple {L, N, 0} . L is a set of goods, N is a set of agents and 0 is a set of states of the world. All of these sets are assumed to be non-empty and finite and the cardinalities of L and N are given by I and n, respectively. J? is the domain of all asymmetric information economies. In the definitions that follow, we focus on a given e € E\ An explicit reference to e is dropped to minimize notational burden.

Let e = {L, N, 0} be given. Every agent i e N i s completely

* I

characterized by a list (u , cj , TT , q ), where u : R x 0 -> R i s agent i's

i i i i i +

I von Neumann-Morgenstern utility function; u (# 0) € R is agent i's

i +

initial endowment of goods; IT is agent i's natural informat ion part it ion

i * of 0 and q_: 6 -> (0, 1) is agent i's prior probability distribution on 0.

Each constituent of this list is assumed to be given exogenously, and is

common knowledge in the sense of Aumann (1976). Let the function / : 0 ->

i

TI be defined by I°{6) = {9' e 0: there exists n e TI such that 9, 9' € i i i i

n.}. The latter is agent i's natural informat ion set in state 9. By "natural" information we refer to the information structure that the agent is exogenously endowed with. This distinguishes it from the information that can be acquired endogenous 1 y. In the sequel, let IT = xIT and Q =

i € H i

V u . In addition, unless specified otherwise, x = (x ) and x =

i€N i i i€N -i

(x )

Let P(X) denote the set of non-empty subsets of X. Agent i's posterior probability distribution is the function q.: 0 x P(0) -» [0, 1] defined by Bayes ' Law, i.e. for all 0 € 0 and for all 3 e P(0),

if Be J;

q (0, 3 ) = i

q*(e)

1

V«jV6'»

o,

otherwi se.

/Igent i's expected utility from f e F, given J € P(/.(0)) is £ q.(0' .

1 9'€j'

J)u (/ (0'), 0'), and is written more compactly as EU (/ .7). /Igenf i's i i i ' '

3-expected lower contour set at f is given by EL (f 3) = {g e F: EU (f

i ' i '

3) > Ft7.(g I 3)}.

The domain under consideration, 6" is defined as the collection of all

economies e ={L, N, 0} 6 6", that satisfy the following:

[A1] (strict monotonicity of preferences) Vie/V, V0e0, u(., .) is

i

I strictly increasing in ze (R , and

[A2] (non-exciusiui ty o/ informat ion) Vi e A/, V0 € 0, f] /°(0) = {0>.

[A3] \N\ > 2.

The assumption A2 implies that once n - 1 agents pool their private information, they can tell exactly what information the last agent has. Such an assumption is clearly restrictive. However, as discussed in Postlewaite and Schmeidler (1986), Palfrey and Srivastava (1987a) and Blume and Easley (1987) some such restriction is required to analyze i mpl ementabi 1 i ty using Bayesian equilibrium or one of its refinements. This is a consequence of the Revelation Principle (for a full discussion, see the references given). Presumably, the A2 restriction can be mildly

10

weakened. However, given that it is still descriptive of a large class of interesting problems with asymmetric information, as in these earlier papers, our focus will not be on weakening this restriction.

/I = {z € R : £ z < Q) is the set of feasible allocations. A

+ i€N i -

state-cont ingent allocat ion is a random variable /: 0 -> A. F is the domain

of such functions. A performance standard <p is a non-empty subset of F

such that for all 9 6 8, 0 <&. <p(0). $ is the class of all performance

standards.

A mechanism is a game T = {A/, M, £} , where, given that M. is agent i's

message (or action) space, M = .xM.; and £.- tl -> A is an outcome fund ion.

Agent i's strategy is a random variable s : 0 -> M such that s is

i i i

IT -measurabl e. Let S be the domain of such functions. Let S = XS . i i i€N i

3. Bayesian Equilibria with No Regret

The fundamental solution concept for games with asymmetric information is that of Bayesian equilibrium due to Harsanyi (1967). This concept is defined as follows:

s e S is a Bayesian equil ibrium of T = {N, M, £,} if Vi e JV, V6 e 0,

Vs' € S , i i

£°(s\ s ) € EL (C«s I /°(6)). 1-1 i ' i

Let E (D denote the set of Bayesian equi I ibria of V and £°(D = {^s e F: s e E°(D, T = {A/, M, 0>-

An implicit assumption underlying the Bayesian equilibrium concept is that the agents are committed to their equilibrium strategies. In this paper, we shall drop this assumption and attempt to identify the set of Bayesian equilibria that survive when the agents are not committed to their

11

messages and can revise their strategies after having observed the

actions/messages of others.

Let / (0, s) = {G' € /°(6): Vj e H\{i), s (0) = s (G')}. Green and i i J J

Laffont (1987) propose the following refinement of Bayesian equilibrium for

games with no binding commitments:

s € S is a posterior optimal Bayesian equi I ibrium of T - {N, M, £} if

Vi € N, VG € 0, Vs' € S ,

i i

£«(s' s ) 6 EL C£»s I I°(Q)) fl EL (£°s I / (G, s)). i -i i ' i ■ ' l ' i * Let E (D denote the set of posterior optimal Bayesian equi I ibria of r.

The set of Bayesian equilibria with no regret, denoted E(D, is a

subset of E (D that satisfies the following condition:

Vs, s' € f(D, Vi € N, VG 6 9, Vs" € S ,

i i

£°(s", s .) € EL (£oS I / (G, s' ))

i-i i ■ i

Let £ (D = {^s e F: s € E(D, T = {N, M, £,} } . We interpret f(D as the set of binding agreements which each agent will voluntarily endorse. A game with no commitment which has a non-empty set of such agreements is a mechanism with no regret.

4. Bayesian-Impl ementat i on and Welfare Implications

The classical approach to welfare economics has been to identify the subset of allocations that are Pareto-ef f i c i ent within the set of all physically and technologically feasible allocations. Among these efficient allocations, attention is generally focused on ones that are individually rational. However, in asymmetric information economies, these welfare evaluations must also take account of informational constraints -- an uninformed social planner or the group of agents as a whole cannot identify

12

the set of individually rat i onal -ef f i c i ent allocations in the absence of complete information about the state of the world which affects the agents' preferences. The notion of an individually rat i ona 1 -ef f i c i ent allocation would vary depending on the extent of insurance that the allocation provides each agent. Individual rationality and Pareto-ef f i c i ency are thus extended to take account of different levels of insurance and the appropriate notion depends on the timing of the welfare analysis (see Holmstrom and Myerson (1983) for a detailed discussion). The two primary concepts of efficiency are:

Interim-efficiency-. A state-contingent allocation / is

interim-efficient if there is no g e F such that Vi € N, VG € 0, f € EL (g

i

7°(8)) and / e int(£L {g /°(8)) for some i € N and some 8 e 0. 1 i i ' i

Ex post -efficiency: A state-contingent allocation / is ex

post-efficient if there i s no g € F such that Vi € N, V6 € 0, f e EL {g

i '

{8}) and / € int(EL (g {8}) for some i € N and some 8 € 0.

i '

Given w € F defined by a/(8) = u for all 8 € 0, let ?' a {f € F: f is interim efficient and Vi € A/, V8 € 0, u € EL (f I /°(8))> and fe = {f e F:

i ' i

f is ex post efficient and Vi € A/, V8 € 0, u € EL (f {8>> denote,

i

respectively, the sets of interim individually rat ional-efficient and ex post individual I y rat ional-efficient performance standards.

Once a social planner decides on the appropriate notion of efficiency, the question of implementing an efficient performance standard arises. Once again, the informational asymmetry poses a constraint. A naive mechanism in which each agent is asked to report his/her private information to the planner will generally not ensure truth-telling as the unique equilibrium strategy profile. Thus, we need to be guaranteed the existence of a mechanism that implements the given standard. This is defined (for the case where Bayesian equilibrium is the solution concept)

13

as f ol 1 ows :

A performance standard <p is Bayesian- implement able by T in e = {L, A/, 0} if 0 * E°(D c ip.

F

A performance standard (p is Bayesian implement able (in a global sense) if Ve € E\ 3T such that <p is Bayes i an-i mpl ementabl e by T in e. Remark: FuJ / Bayes i an-i mpl ementat i on of </> by T requires that £ (D = </>, whereas weak Bayes i an-i mpl ementat i on of <p by T requires that <p c £ (r).

Next, we present a condition that is both necessary and, in economies

in E, sufficient for a performance standard to be Bayes i an-i mpl ementabl e.

Before we present the condition, some additional definitions are needed.

We shall use the approach of Postlewaite and Schme idler (1986) and Palfrey

and Srivastava (1987) to define a "collection of compatible manipulation

operators". The intuition behind these operators is simple. Consider a

mechanism in which each agent is asked to report his/her initial

information set to the game designer as part of a message. If the realized

state of the world is 0, then agent i observes / (9). The game designer

i

cannot observe this set. By the common knowledge assumption, agent i's

natural information partition IT is observable. Second, the assumption A2

i

is common knowledge. These two facts constrain the extent to which agent i

can manipulate his/her report of his/her private information. An n-tuple

of manipulated reports will fool the game designer only if the manipulation

is "compatible" with the common knowledge structure. This is formalized in

the definitions below.

A collection of compatible manipulation operators for IT (CCMO),

denoted a = (a ) , is defined by

(i) V i € N , a: TT -> IT , i i i

( i i ) Vrc e IT, { H " * 0> ■* < fl a (n ) * 0} .

oc oc

Let 0 : 0 -> 0 be the decept ion induced by a and defined by 0 (0) s

14

.a

na (/ (8)). By assumption A2, 9 is a well-defined function. i€N i i

A performance standard <p satisfies Property M if the following is true:

3<p'e * such that <p' Q <p and V/ € F, VCCMO's a, if ( i ) / •€ <p' and

(i i ) vi € A/, v g € f, ve € e, ve' = ea(e), (g e EL.(f I 7°(9'))> =>

(goe" e EL.(f°o /(e))},

then fo0 e <p .

Remark: <p satisfies Bayesian monotonicity if the Property M is modified as

follows: Vf 6 F, VCCMO's a, if (i)' and (ii)' imply f°Qa e <p, where (i)' /

e ^) and (ii)' is the same as (ii) in the definition above.

Fact 1: There exists <p € $ such that <p sat isfies Property M and violates

Bayesian monotonicity.

To check that this true, simply choose <p such that it is the union of a Bayesian monotonic set <p' e <f> and a set <p" e <t> which is not Bayesian monotonic. For examples of such sets, see Palfrey and Srivastava (1987a). Fact 2: Let e = (L, N, 0} be an economy in IS. A performance standard </> is fully Bayesian- implement able by a game in e if and only if it sat isfies Bayesian monotonicity. Proof: See Palfrey and Srivastava (1985). ■

The following proposition provides a parallel characterization of Bayesian-implementabi 1 i ty.

Proposition 1: Let e = (L, N, 0} be an economy in S. A performance standard <p is Bayesian- implement able by a game in e if and only if it sat isfies Property M.

Proof: <p is Bayes i an-i mpl ementabl e if and only if there exists <// € <t> such that <p' Q (p and <p' is fully Bayes i an-i mpl ementabl e. Given Fact 2, the

15

proposition follows from the definitions. ■

In conjunction with the facts given above, the proposition has an interesting implication: a performance standard may be Bayes i an-i mpl ementabl e even though it violates Bayesian monoton i c i ty.

Palfrey and Srivastava's (1987a) examples suggest that the f and f sets are not fully Bayesi an-i mpl ementabl e. However, disappointing as this may be, we are interested in a more crucial question: can we ever hope to design a mechanism so that all of its Bayesian equilibrium outcomes are individually rat i onal -ef f i c i ent (in either an interim or an ex post sense)? In other words, is it possible to Bayesi an-i mpl ement (i.e. to fully

i c

Bayesi an-i mpl ement some subset of) f or ¥ in the domain of economies that Palfrey and Srivastava have examined? It must be noted that their result does not answer this latter question. The following results confirm that the answer to the question is, indeed, negative.

The theorems are proved by way of counterexamples. We shall present simple ones using linear economies. The negative results do not depend on the assumption of linearity and hold for other utility specifications too.

Theorem 1: If <p £ f , then <p is not Bayesian- implement able.

Proof : Consider the following example:

Example 2: We define e = {L, N, 0} as follows. Let L = {X, V'} with the

quantities of the two goods being denoted by the corresponding lower case

letters. Let N = {1, 2, 3, 4} and let 0 = {a, b, c} . IT = IT - {(a), (6),

(c)} and TT = TI = {(a), (b, c)}, i.e. agents 1 and 2 are fully informed 3 4

and agents 3 and 4 cannot distinguish between states b and c when one of

them occurs. An allocation z is written as (x , y ) . u = ((0, 1), (0,

i i i€N

* *

1), (1, 0), (1, 0)). Each state is equally likely, i.e. q.{a) = q.(b) =

i

• 1 I

q.(c) = - for all t € N. u : (R x 0 -> K i s given as follows: i 3 i +

16

Vi € {1 , 2} , V0 e 0, u.(z., e) =

1 1

x. + 1. 1y., i i

u (z , e) =

(x3 + y3),

if 9 = a

0.25(x + y ) if 9 = b

0.75(x + y ) if 6 = c. 3 JZ

u.(z G) =

4 4

(X4+ V'

if 9 = a

0.75(x + y ) if 8 = b 0.25(x + y ) if 9 = c.

4 4

It can be checked that f *■ 0. Consider the following state-contingent

* allocation, denoted / :

a		b		c
(0,	1)	(0,	1)	(0,	1)
(0,	1)	(0,	1)	(0,	1)
d,	0)	(0,	0)	<§■	0)
(1,	0)	(2,	0)	<;■	0)

2 =

1

Z = 3

Z =

* i It can be checked that f € f . Also check that assumptions A1 and A2

are satisfied.

Choose any y> € $ such that <p Q f . We shall show that the hypothesis

of Property M is satisfied. Consider the function a : IT -» TT for all i e

i i i

N defined by a (ji ) = {a} for all i € N and all n € TT . Thus, a is a CCM0 i i i i

and for all 9 € 0, 0a(9) = a. Pick f € <p and g € F. Write /(a) as (x, y) and g(a) as (x', y'). By construction, the utility functions of agents 1 and 2 are state- i ndependent . Therefore, given that they are completely informed, the relevant portion of the hypothesis of Property M is trivially satisfied for these two agents. The following relationships imply that the

17

relevant portion of the hypothesis of Property M is met for the remaining agents:

x + y > x' + y' => 0.5[0.25(x + y ) + 0.75(x + y )] 2 O.S[0.25(x' +

3 JZ 3 ^3 3 ^3 3 ^3 3

y^) + 0.75(x^ + y3)].

x + y > x' + y' => 0.5[0.75(x + y ) + 0.25(x + y )] > 0.5[0.75(x' +

4 J 1* 4 J C U J 1. 4 4 4

y') + 0.25(x' + y')]. 4 44

For ? to satisfy Property M, we must have f°Q e <p. The following

a allocation is recommended by f°Q :

Agent 3 [x , y ) (x , y )

Agent 4 (x y ) (x y )

4 4 4 4

By interim individual rationality of /, (x , y ) * (0, 0). By the

construction of this example and given that / e <p Q ? , x > 0 and x > 0.

Given min{x , x } > c > 0, consider an alternative rule h <= F defined by 3 4 J

Ma) = fia),

Vi € {1, 2}, V9 € {b, c>, h (G) = / (a),

i i

h3(b) = (x3-c, y3), h3(c) = (x^, y3), h (b) = (x+c, y ), h(c) = (x-|, y )-

4 4 4 4 4 3 4

Thus, £b (h | {b, c>) = 0.5[0.25(x - c + y) + 0.75(x + - + y)] =

0.5[0.25(x + y ) + 0.75(x + y )] = EU (/°9a | {b, c) ) . Trivially, for i

€ {1, 2} and all 9 € 0, £(/ (h I {9}) = EU (/°9a I {9}). Also, trivially,

i ' i '

for i € {3, 4>, EU (h I {a}) = EU (f°9a I {a}). However, EU (h I {b, c} ) =

0.5[0.75(x + c + y ) + 0.25(x - - + y )] > 0.5[0.25(x + y ) + 0.75(x + 4 Jt, 4 3 4 4 4 4

y )] = EU (f°9a I {b, c}). Thus, f°ea « ?'. 4 4

For any <p c f with f e <p, we find that /»G £ <p. Thus, ? violates Property M. By Proposition 1, it is not Bayes i an- i mp 1 ementabl e in e. ■

Theorem 2: / f <p Q f , then </> is not Bayes i an- implement able.

18

Proof: The proof is by a counter-example. Consider an economy e' which retains all the specifications of e from Example 2 above with one exception: agent 3's utility function is altered as follows:

if 0 = a

u (z , 0) =

(x3 + y3).

(x +1.5y) if e = b

(x + 0.5y ) if 9 = c. 3 JZ

Given these specifications, f t 0. Choose a : IT -> TT as in the previous

i i i

proof, i.e. for all i € N, for all n € TT, a (tt ) = {a}. Thus, a i s a

i i i i

CCMO and for all 9 € 0, 9a(e) = a. Choose any <p € $ such that <p Q ?e and pick f e <p. Next, we establish that the hypothesis of Property M is met. From the relationships derived in the proof of Theorem 1, we know that the relevant relationships for agents 1, 2 and 4 hold. To check that the relevant relationship holds for agent 3, consider the following observations:

Pick f e (p and g € F. Write f{a) as (x, y), and gia) as ix' , y'). Thus, we have

x + y > x' + y' => 0.5[(x + 1.5y ) + (x + 0.5y )] > 0.5[(x' + 1.5y3) + (x3 + 0.5y3)].

Thus, the hypothesis of Property M is satisfied. For f to satisfy Property M, we must have /°6 € <p. The following allocation is recommended by foea:

Agent 1 Agent 3

<*,. y,) (,5. y,J

t*,. y,)

(x3, y )

By ex post individual rationality of /, (x , y ) # (0, 0).

By the

construction of this example and given that f & <p Q ? , x >0 and y > 0.

Given min{— x y } > c > 0, consider an alternative rule h € F defined by:

h (b) = (x +1 . 1c, y -c) 1 1 1

19

h (b) = (x -1. 1e, y +c)

Vi e {1, 3}, VG € {a, c}, h.(0) = / (a)

i i

Vi € {2, 4}, h = / oGa. i i

Thus, £f (h I {b}) = x - 1.1c + 1.5c + 1 . 5y = x + 0.4c + 1 . 5y > x + 3 ' 3 ^3 3 ^3 3

1 . 5y = EU (f°Ga | {5} ) and EU (h | {6} ) = x + 1. 1c + 1. 1y - 1.1c = x +

1 . 1 y = EU lf°Oa I {5}). For all i <= N and all G € 9, f°6a e EL (h I {G}).

11' i '

Thus, /oGa <£ <p Q ?*. Given that this holds for all p S ?°, J*6 does not satisfy Property M. By Proposition 1, it is not Bayes i an-i mpl ementabl e in

5. No Regret Implementation

In this section, we discuss the i mpl ementabi 1 i ty properties of mechanisms with no regret and provide necessary and sufficient conditions for this method of implementation.

A performance standard <p is No regret- implement able ( NR- impl ement abl e) by V in e = {L, N, 8} if 0 * E (D S <p.

A performance standard <p is NR- imp I ement able (in a global sense) if Ve € E, 3T such that <p is NR-i mpl ementabl e by T in e. Remark: (p is fully NR- implement able by T if £ (D - <p.

Next, we shall define some properties that shall be used to characterize NR- i mpl ementabl e standards.

A performance standard <p satisfies Property Ml with respect to T =(N, tl, £;} if the following is true: 3<p' € <t> such that <p' Q <p and V/ e F, VCCMO's a,

if u) / € <p'

(ii) Vi e N. Vg e F, VG e 0, VG' = Ga(G), {Vs 6 E(D, g e EL (f I

i '

20

i°(e')) fl EL (f I l (Q' > s^> * <*s' € s> s°eCC e EL.(f°ea I J°(e)) fl

EL C/o9a I f.fe, s'))>,

i ' i

a then f°Q € <p .

A performance standard <p satisfies Property M2 with respect to T if V/

oc

€ <p, VCCMO's a, (i)' and (ii)' imply f°Q € <p, where (i)' / e <p and (ii)'

is the same as (ii) in the definition above.

Green and Laffont (1987) present a characterization of "posterior i mplementabl e" performance standards in two-person economies and show that a posterior i mpl ementabl e standard can take essentially only two values throughout the range of observations of the two agents. We shall attempt a parallel characterization of NR-i mplementabl e performance standards.

Theorem 3: Let e = (L, N, Q) be an economy in 6\ and let <p be a performance

standard. If <p is NR- implement able by T in e, then <p sat isfies Property Ml

with respect to r.

Proof: By definition of NR-i mpl ementat i on by a game T = {N, M, £;} , there

exists <p' Q <p such that <p' is fully NR- i mpl emented by T. Thus, for all / e

<p' there exists s € E(D that / = £;°s. This means that the following holds

for all i € N, for all 9 e 0, for all s' e S , for all s" € E(D:

i i

£°(s'., s .) € EL.if I /°(0)) [) EL (f \ I (9, s")) (1)

Choose a CCMO a. Next, suppose that for all i e N, for all 9 € 0, for all

9' = 9a(9), for all s" € E(D, for all g € EL ( f I /°(9')) fl EL(f I

* 7.(9', s")), the following holds for all s € S:

i

goG* 6 ELXfoQ* I J°(e)) fl EL (foQ* I 1.(6, S )) (2)

Given (1) and (2), for all i € Af, for all 9 e 0, for all s' € S, for all

i i * s € S, the following holds:

€°(s'.f s )o9a € EL C/°9a I 7°(9)) fl EL (/o0a I / (e, s*')) (3)

l-i i ' i ' ■ i ' i

By definition of a, s 09 is TT -measurabl e for all i e IV. By definition of

i i

21

Bayesian equilibrium with no regret, (3) implies that s°0 € E(D and f°B e E (D. By definition of full NR- i mpl ementat i on of <p' , E (D Q <p' . Thus, /°9 e <p' and <p satisfies Property M1 . ■

Theorem 4: Let e = (L, N, Q) be an economy in I' and let <p be a performance

standard. There exists T such that if <p sat isfies Property M2 with respect

to T, then <p is NR- implement able by T in e.

Proof: The proof of this statement derives from the following lemmata.

Lemma 1: There exist T and s e £(D such that for all i e N, for all Q € 0,

7.(0, s) = (Q). i

Lemma 2: There exists T that sat isfies Lemma 1 such that if <p sat isfies Property M2 with respect to T, then E (D Q <p.

The proofs of these results are given in the appendix. ■

Corollary to Theorem 4: Let e = (L, N, 0} be an economy in E, and let <p be a performance standard. If <p is fully NR- implement able by T in e, then <p sat isfies Property M2 with respect to T. Conversely, there exists T such that if <p sat isfies Property M2 with respect to T, then <p is fully NR- implement able by T in e.

6. No Regret Implementation and Welfare Implications

This section explores whether or not the individually rational- efficient performance standards are i mpl ementabl e by no regret mechanisms. We have bad news and good news. The bad news is that the interim standard is not NR- i mpl ementabl e. The good news is that the ex post standard is. Often we are not interested in implementing the entire ex post individually

22

rat ional -ef f i ci ent set. Instead, we would like to find out which subsets of this set are i mpl ementabl e. This brings us to the most significant result: any performance standard that is Nash-i mpl ementabl e is NR-i mpl ementabl e. Hence, extremely important sets like the core or the Ualrasian correspondence are i mpl ementabl e by mechanisms with no regret even in asymmetric information economies.

Theorem 5: f is not NR- implement able.

Proof: Suppose that the theorem were not true, i.e. for all e e E, there

exists a game T such that f is NR-i mpl ementabl e by T in e. Consider the

economy e defined in Example 2 (see proof of Theorem 1 above). By

definition of NR-i mpl ementat i on by T = {N, M, £;} in e, there exists <p Q ?

such that for all /€</>, there exists s 6 f(D with £°s = f. In addition,

check that in the economy e in Example 2, the hypotheses of Property Ml are

satisfied with respect to T. Choose a CCMO a as in Example 2. Pick f e <p

and g e F. Write f{a) as (x, y) and g{a) as (x' , y' ) . By construction,

the utility functions of agents 1 and 2 are state-independent. Therefore,

given that they are completely informed, the relevant portion of the

hypothesis of Property M1 is trivially satisfied for these two agents. The

following relationships imply that the relevant portion of the hypothesis

of Property M1 is met for the remaining agents:

x + y 2: x' + y' =* 0.5[0.25(x + y ) + 0.75(x + y )] > 0.5[0.25(x' +

y^) + 0.7S(x^ + y^)].

x + y > x' + y' => 0.5[0.75(x + y ) + 0.25(x + y )] > 0.5[0.75(x' + 4 4 4 4 44 44 4

y') + 0.25(x' + y')] and

4 4 4

X3 + y3 " X3 + y3 °* °-25(x3 + yz] ~ 0.25(x^ + y^)

x3 + y3 " x3 + y3 "* °-75(x3 + y3} - °-75(*3 + y3)

x, + y > x' + y' =* 0.75(x + y ) > 0.75(x' + y' ) 44 44 4 4 44

23

x + y > x' + y' =* 0.25(x + y ) > 0.25(x' + y' ) 4 Jb 4 4 4 4 4 4

Given these observations, the hypothesis of Property M1 is met for any game V. The rest of the proof of Theorem 5 follows the proof of Theorem 1 and it is established that /°6 € <p. Thus, f does not satisfy Property Ml with respect to V. Given Theorem 3 and the assumption that f is

NR-impl ementable by T, we have a contradiction. ■

Theorem 6: f is NR- implement able.

This result follows from Lemma 3 and a more general result given in Theorem 7. The lemma is proved in the appendix. We shall use the following definition:

A performance standard <p satisfies Property M if the following is

true:

3</>'€ * such that <p' Q <p and V/ e F, VCCMO's a,

i f ( i ) / € <p' and

( i i ) Vi € N, V g € F, V0 € 0, V9' = 0a(G), (g € EL (f I {6'})) =>

i '

(goea € el. (/°0a I {e})>,

then /o9 € <p' .

e *

Lemma 3: f sat isfies Property M .

Theorem 7: Let <p be a performance standard. Iff is Bayesi an- implement able

(Nash- implement able) in economies with complete information, i.e. when for

all i € N and al I 8 € 0, / (G) = (6>, then <p is NR- implement able .

i

Proof : By Proposition 1, i f <p i s Bayes i an-i mpl ementabl e in economies with

* complete information, it must satisfy Property M . By definition, if </>

satisfies Property M , then there exists <p' Q <p which satisfies Property M2

with respect to any game f such that for all i e N and all G e 0, there

24

exists s e E(D with J (9, s) = {0}. By Lemma 1 and Lemma 2 and the

i

Corollary to Theorem 4, <p' is fully NR-i mpl ementabl e. Thus, <p is NR-i mpl ementabl e. ■

7. Extensions

In many economic problems of interest, initial endowments are not specified (for example, when resources are owned collectively) or a social planner may wish to efficiently allocate resources in an "equitable" manner. In such situations, we may want to replace the individual rationality condition with some equity requirement, such as freedom from, envy (Foley (1967). The results reported in this paper, both and positive ones, hold for the corresponding problem of implementing the interim and ex post envy-free-efficient performance standards.

To summarize, we have shown that it is impossible to design "interesting" efficient mechanisms using Bayesian equilibrium as the solution concept. By employing mechanisms with no regret, introduced in the literature by Green and Laffont (1987), we have a solution to the problem. In fact, any success that has been achieved by Nash- i mpl ementat i on theory for complete information economies can be mimicked in situations where information is non-exclusive and incomplete.

25

References

AUMANN, R. (1976): "Agreeing to Disagree," Annals of Stat ist ics, 4,

1236-1239.

BLUME, L. AND D. EASLEY (1987): "Implementation of Rxpectations

Equilibria," mimeo Cornell University.

DASGUPTA, P., P. HAMMNOND AND E. MASKIN (1979): "The Implementation of

Social Choice Rules: Some General Results on Incentive Compatibility,"

Review of Economic Studies, 46, 185-216.

EOLEY, D. (1967): "Resource Allocation and the Public Sector," Yale

Economic Essays, 7, 45-98.

GREEN, J. AND J. -J. LAFFONT (1987): "Posterior Impl ementabi 1 i ty in a

Two-Person Decision Problem," Econometrica, 55, 69-94.

HARRIS, M. AND R. TOWNSEND (1981): "Resource Allocation under Asymmetric

Information," Econometrica, 49, 231-259.

HARSANYI , J. (1967): " Games with Incomplete Information Played by

'Bayesian' Players," Management Science, 14, 159-189, 320-334, 486-502.

H0LMSTR0M, B. AND R. MYERSON (1983): "Efficient and Durable Decision Rules

with Incomplete Information," Econometrica, 51, 1799-1820.

MASKIN, E. (1977): "Nash Equilibrium and Welfare Optimal i ty, " mimeo,

M.I.T..

MOORE, J. AND R. REPULLO (1988): "Subgame Perfect Implementation,"

Econometrica (forthcoming).

MYERSON, R. (1979): "Incentive Compatibility and the Bargaining Problem,"

Econometrica, 47, 61-74.

PALFREY, T. AND S. SRIVASTAVA (1985): "Implementation and Incomplete

Information," mimeo, Carnegie-Mellon University.

PALFREY, T. AND S. SRIVASTAVA (1987a): "On Bayesian Imp 1 ementabi e

26

Allocations," Review of Economic Studies, 54, 193-208.

PALFREY, T. AND S. SRIVASTAVA (1987b): "Mechanism Design with Incomplete

Information: A Solution to the Implementation Problem," mimeo California

Institute of Technology and Carnegie-Mellon University.

POSTLEWAITE, A. AND D. SCHMIEDLER (1986): "Implementation in Differential

Information Economies," Journal of Economic Theory, 39, 14-33.

REPULLO, R. (1986): "On the Revelation Principle under Complete and

Incomplete Information," in Economic Organizations as Games edited by P.

Dasgupta and K. Binmore, Basil Blackwell, Oxford.

SAIJO, T. (1988): "Strategy Space Reduction in Maskin's Theorem: Sufficient

Conditions for Nash-impl ementati on, " Econometrica, (forthcoming).

27

Append i x

In this appendix, we shall prove the lemmata presented in the main body of the paper. For this purpose, we shall devise an algorithm which generates a game for every performance standard. Let £ denote the algorithm and let £(</>) denote the game that is generated when a particular (p is applied to the algorithm given below. For all <p e <I>, £(</?) = {N, M, *;} is defined as follows:

(I) Vi € N, M = {m. = (n.ii), /( i ) , S(i)) € II. x F X R }.

111 i +

Definition: Vi € N, m satisfies Property y\i if the following conditions hold:

1 ' j€N\(i) j

(ii) 3f e <p such that Vj e N\{i}, f(j) = f.

(i i i ) Vj € AM i}, 5(j) = 0.

* *

Definition-. Vm € M, 9 (m) is defined such that D n ( i ) = {8 (m)}.

1 ' i€N i

Definit ion-. Vi e N, Vm € M , 0 (m ) is defined such that (~| " (j)

-i -i i -i ' ' j€N\(i) j

= {9 (m )}. 1 - 1

Definition: Vm € M, K(m) s {i e /V: Vj € N\{i), 8{i) ^ 5(j)}.

(II) £: M -> i4 i s given by the schematic diagram in Figure 3.

A1

Proof of Lemma 1 : Choose / € <p. We shall show that there exists s €

E(g(<p)) such that £°s = / and for all i e N and all 0 e 0, 7.(0, s) = {0}.

Construct a strategy list s € S as follows: for all i e N , for all 0 € 0,

s (0) = (J (0), /, 0). It may be checked that for all i e N, for all 0 e i i

0, s (0) satisfies Property y 1 i . By construction, Case 1 applies and £<>s - i

= /-

Consider a unilateral deviation to s' € S by agent i. We write s' =

i 1 i

(s' , s' , s' ). Note that by assumption A2, for all 0 € 0, 0 (s (0)) = i 1 i 2 i 3 l-i

0. For all 0e0, there are two possibilities:

(a) s' (0) = /, in which case either Case 1 or Case 2 applies and

i 2

€(s'.(e), s .(0)) e {/(g), 0}. 1 -1

(b) s' (0) * /. Case 3 applies and £(s'(0), s (0)) e {/'(i)(0), 0}.

i 2 i - 1

By strict monotonicity of preferences, u.(/, 0) ^ u.(0, 0) for all 0 € 0.

By construction for all j e N, s (0) = / (0). In conjunction with

J1 j

assumption A2, this implies that for all 0 € 0, for all 0' € /.(0)\{0),

there exists j € N\{i) such that s (0) * s (0'). Thus, for all i € N,

for all 0 € 0, / (0, s) = {0}. If possibility (b) occurs, by Case 3, we i

have £°(s', s ) e EL (/ {0}) which implies that for all s" € S, £,°(s', i - i i ' i

s ) € EL (/ I J°(0)) f] EL (f \ I (0, s")). Thus, we conclude that s e - i i ' i ■ ' i ' i

£(£(</>)). Given ^«s = / € <p, we have £(£(<?)) * 0. ■

Proof of Lemma 2\_ By Lemma 1, £(£(<p)) * 0. We need to show that f (£(</))) £ tp.

Step 1 : The proof of this lemma makes use of the following result:

Lemma 2.1: Let s e £(£(>)). For all 0 e 0, s(0) satisfies Case I.

Proof of Lemma 2. 1 : We shall establish that there cannot be a state 0 € 0

such that s(0) = (rr (j), /( i ) , 5(i)) satisfies either of the cases 2, 3

i i€N

or 4. We write s as (s , s , s ) where the components of this list

i i1 i2 i3

A2

denote the functions induced by restricting the range of s to IT , F and R

i i +

respect i ve 1 y.

Suppose that for some 0 € 8, siQ) satisfies one of the following: Case

2, Case 3 or Case 4. A contradiction will be established. Consider a

unilateral deviation by agent i 6 N to s' e S such that s' = (s , s ,

i i i i 1 i 2

s' ). s' is such that for all j € AM i }, for all 0' e 0, s.(G') < i 3 i3 J3

s' (6'). Let m = s(G) and m' = (s'(0), s (6)). We shall show that i 3 i i

there exists i € N such that the following hold:

S.(m') > £.(m) (*)

i i

V9' € 0, £ (s'(G'), s (G')) ^ £ (s(G')) (**)

ii -l i

There are two possibilities:

(i) Possibility 1: There exists j € N such that Kim) = ij).

Therefore, for all i e N\{j}, m does not satisfy Property y I i . Choose i

-i '

e M\{j}. By definition, Property yli is not met even if j deviates to s'.

1 i

By the outcome rule associated with Case 4A, we have £ (m') = Q. Since

i

|AMj> | > 1, there exists i € N\{j} such that £.(m) * fi. Thus, (*) holds.

(ii) Possibility 2: There does not exist any j e N such that Kim) = {j}. In this case, by construction, £(m) = 0. By the outcome rules

associated with Cases 2A, 3A and 4A, and given that for all 0' € 0, for all

/€</>, fiQ') * 0, there exists i e N such that £ (m') > 0. Thus, (*)

i

hol ds.

To check that (**) is true for the agent i for whom (*) holds, choose 6" € 0 with G" * G. There are, again, two possibilities:

(a) Possibi I i ty 1 ■. There exists j € N such that K(s(G")) = {j}. The arguments given in (i) above apply. Thus, for all k e N\{j}, £, (s'(G"),

k k

s (G")) = Q. Also, £(s'(9"), s (G")) = FisiO")). Thus, (**) holds for - k j - j

(b) Possibi I ity 2: There does not exist j e N such that KisiO")) =

{j}. By construction, for some f e tp, F,isi0")) € {/, 0}. By the outcome

A3

rules associated with Cases 2A, 3A and 4A, we conclude that £[(s'(9"),

i

s (8")) 6 {/, 0.}. Thus, (**) holds for i.

Given that (*) and (**) are true, and given strict monotonicity of preferences, we conclude that if s(0) does not satisfy Case 1, for some 9 e 0, then s £ £(£(</>)). This contradicts the assumption that s <= E(g(</?)). ■

Step 2j_ Choose s e £(£(<p)). By Lemma 2.1, for all 9 € 0, s(9) must

satisfy Case 1. We write s as (s , s , s ). Thus, for all 9 e 0,

i i1 i"2 i3

*

fl s (9) * 0 and 9 (s(9)) is well-defined. By IT -measurabi 1 i ty of s , 1 * i € N i 1 i i

(s ) defines a CCMO and we shall write it as a, where for all i e N, i1 i€N

*

for all 9 € 0, a (/ (9)) ■ s (9). Observe that for all 9 € 0, 9 (s(9)) = i i i 1

a *

9 (9). By construction, for all 9 € 0, there exists f <= <p such that

*

s (9) = / . This implies that there exists f e <p such that for all 9 € 0, i2

€Js(9)) = fie (s(9)), i.e. £°s = /o9a. We need to show that foQa e <p.

We shall first show that for all i e N, for all 9 e 0, for all 0' =

9a(9), if g € EL.if | /.(9\ s )) for all s € £(£(<*>)), then goQa e

EL (foGCC I J°(9)) fl ^ (/°6a I / (0, s)) for all s e S. In the case where i ' l ■ ■ i ' i

f = g, this is trivially true. To show that this is true even when f * g,

choose i € N and g e F such that g * f and for all 0 e 0 and for all 0' =

0a(0), for all s € E(eU)), g € EL (/ I / (G' , s ) ) . By Lemma 1, there

i ' i

* *

exists s € E(£(y>)) such that for al 1 0 € 0, / (0, s ) = {0}. Thus, g e

i * ♦

EL.Cf M0\ s )) for all s € £(£(</>)) implies that g e EL . ( / {0'}).

Suppose i unilaterally deviates to s' e S where for all 0 € 0, s'(0) =

i i i

(s. (e), g, 5'(i)). <5'(j) is such that for all j € ^\{ J } , for all 0 e 0, 1 1

*

5'(i) > s.,(0). By construction, for all 0 e 0, 0 (s (0)) = 0 (s(0)). j3 i -i

Thus, for all 0 € 0, (s'(0), s (0)) satisfies Case 3A and £((s'(0),

i - i i

* a

s .(0)) = g(0.(s .(0))) = g(e (s(0)) = g(6 (0)). Observe that s € E(£(y>))

implies that for all 0 e 0, for all s e E(C(y>)), go©" e EL (/°9a /°(9))

i ' i

a * *

f] EL. (/o9 /.(9, s )). By Lemma 1, there exists s e E(£(<p)) such that

A4

•

.a r-. , „ „oc

/ (9, s ) = {9} for all 9 e 0. Thus, g°9 e EZ. (f°9 {9}) for all 9 e 0 i i '

and we conclude that for all s e S, g°9tt € EL (foOa I 7°(G)) fl EL (/°9a I

i ' i ' ' i

/ (9, s)). i

Given that the last conclusion holds for all i e N, by the fact that <p

(X

satisfies Property M2 with respect to £(</>) , we have f°Q e <p. ■

Proof of Lemma 3: Choose f e f and a CCMO a. Suppose that for all i e N,

for all 9 € 0, for all 9' = 9tt(9), if f € EL (/ I {9'}), then /' o0a e

i '

EL (/°9a I {9}).

i ■

OC e

Next, suppose that /<>9 <t. f . We shall prove that this yields a

oc e

contradiction. f°Q £ f implies either one or both of the following

poss i bi 1 i t i es:

oc Possibility A: f°6 is not individually rational, i.e. given u e F defined

by w(9) = cj for all 9 6 0, there exists j € N and 9 e 0 such that u <£

EL.(f°ea I {e}).

j

cc Possibility B: /°9 is not ex post efficient, i.e. there exists g, h € F

such that h = goe with h tf EL (foe {e }) for some k e N and some 9 e 0

k '

and foQa e EL (h I {9'}) for all i € N and all 9' e 0. i '

By assumption, for all i e N, for all 9 € 0, for all 9" = 9 (9), for

all /' e E if /' € EL (f I {9">), then foe" e EL(/oea I {9}). This

i ' i ' *

implies that for u, g, 9, 9 j and k given above, Possibility A implies (+)

and Possibility B implies (++) and (+++), where

w i EL.(f | {9"}) for 9" = 9a(9) (+)

g <£ EL (/ {9"}) for 9" = 9a(9 ) (++)

k '

and for all i € N, for all 9' e 0,

f € EL (g I {9'} ) (+++)

(+) contradicts the fact that f € f implies ex post individual rationality

of f. (++) and (+ + +) contradict the fact that / € Tc implies ex post

efficiency of f. Thus Possibilities A and B cannot occur and we conclude

A5

that /oe € f

A6

Rain

l n

R

Shi ne L M

CI oudy

L M

t 10, 10 5, 5 0, 0;

5, 5 10, 10 0, 0

I i

T	10,	10	5,	5 10, 10
B	5,	5	10,	10| 0, 0

r	5,	10 j	5,	10	10, 0
B	10,	10	5,	5 I	5, 10 !

F i gure 1

F1

s (Rain) = 7; s (Rain) = L 1 2

s (Shine) = 7; s (Shine) = L

s (Cloudy) = 7; s (Cloudy) = L

s'(Rain) = T: s' (Rain) = L

s' (Shine) = 7; s' (Shine) = K

s^ (Cloudy) = 7; s' (Cloudy) = L

s'^Rain) = B; s"(Rain) = M

s'' (Shine) = B; s" (Shine) = M

sj (Cloudy) = B; s"(Cloudy) = R

s^Rain) = 7: s (Rain) = L

* •

s (Shine) = 7; s (Shine) = R

*

s^Cloudy) =7; s (Cloudy) = M

Figure 2

F2

Let m = (w.(i), f(i) S(i))

Case 1 :

Vi e N, ( i ) 38 e G such that G (m) {0} , (ii) 3/ € <p such that /( i ) f, and ( i i i ) 5( i ) = 0.

£(m) = /(G

Case 2:

(i) 3/ € <p such that Vj e N, /(j) = /, (ii) 3i € A/ such that m satisfies

- i

Property ^ I i and (iii) the conditions of Case 1 are not all met.

Case 2A

Kim) = {i}

£(m) = /(G (m i - 1

Case 2B

Otherwi se

£(m) = 0

Figure 3

F3

Case 3:

3i € N such that (i) Vj e N\{i}, /( i ) * f(j) and (ii) m . satisfies Property y I i .

(i) K(m) = { i}

(ii) /(i) € ELAf(j) I {e.(m .)}), j * i

i 1-1

€(m) = /(i)(e (m ))

i - 1

£(m) = 0

3i € A/ with Kim) = { i>

(C.(m), £ .(m)) = (n, 0) i -i

Otherwi se

C(m) = 0

Figure 3 (Contd. )

F4

Papers in the Political Economy of Institutions Series

No. 1 Susan I. Cohen. "Pareto Optimality and Bidding for Contracts." Working Paper # 1411

No. 2 Jan K. Brueckner and Kangoh Lee. "Spatially-Limited Altruism, Mixed Clubs, and Local Income Redistribution." Working Paper #1406

No. 3 George E. Monahan and Vijay K. Vemuri. "Monotonicity of Second-Best Optimal Contracts." Working Paper #1417

No. 4 Charles D. Kolstad, Gary V. Johnson, and Thomas S. Ulen. "Ex Post Liability for Harm vs. Ex Ante Safety Regulation: Substitutes or Complements?" Working Paper #1419

No. 5 Lanny Arvan and Hadi S. Esfahani. "A Model of Efficiency Wages as a Signal of Firm Value." Working Paper #1424

No. 6 Kalyan Chatterjee and Larry Samuelson. "Perfect Equilibria in Simultaneous-Offers Bargaining." Working Paper #1425

No. 7 Jan K. Brueckner and Kangoh Lee. "Economies of Scope and Multiproduct Clubs." Working Paper #1428

No. 8 Pablo T. Spiller. "Politicians, Interest Groups, and

Regulators: A Multiple-Principals Agency Theory of Regulation (or "Let Them Be Bribed." Working Paper #1436

No. 9 Bhaskar Chakravorti . "Asymmetric Information, 'Interim' Equilibrium and Mechanism Design." Working Paper #1437

No. 10 Bhaskar Chakravorti. "Mechanisms with No Regret: Welfare

Economics and Information Reconsidered." Working Paper #1438

No. 11 Bhaskar Chakravorti. "Communication Requirements and Strategic Mechanisms for Market Organization." Working Paper #1439

jlNDERY INC.

JUN95