CENTRAL CmCUUTtON BRACKS
The «S"T ' HsTnl * oT.rfreturn to sponsible for its re»rr . borrowed
,L library tar *** ££ stamped °Kn, °r Ye.u moV be Sfd . minimum
tee OT .? ,..„_,_„ „« books ore
tMtf
fcitfl.
When sewing bypbc^wnte new due da,eWo»
previous due date.
Digitized by the Internet Archive
in 2011 with funding from
University of Illinois Urbana-Champaign
http://www.archive.org/details/asymmetricinform1437chak
BEBR
FACULTY WORKING PAPER NO. 1437
Asymmetric Information, "Interim" Equilibrium and Mechanism Design
Bhaskar Chakravorti
WORKING PAPER SERIES ON THE POLITICAL ECONOMY OF INSTITUTIONS NO. 9
College of Commerce and Business Administration Bureau of Economic and Business Research University of Illinois, Urbana-Champaign
BEBR
FACULTY WORKING PAPER NO. 1437
College of Commerce and Business Administration
University of Illinois at Urbana- Champaign
March 1988
WORKING PAPER SERIES ON THE POLITICAL ECONOMY OF INSTITUTION NO. 9
Asymmetric Information, "Interim" Equilibrium and Mechanism Design
Bhaskar Chakravorti, Assistant Professor Department of Economics
ASYMMETRIC INFORMATION, "INTERIM" EQUILIBRIUM AND MECHANISM DESIGN
by
Bhaskar Chakravorti
Department of Economics
University of Illinois
330 Commerce West
1206 S. Sixth Street
Champaign, IL 61820
August 1987
Abstract
In this paper, we present a new equilibrium concept— "Interim" equilibrium—for games played by agents who have observed noisy private information and can, conceivably, acquire new information through communication and other means. We demonstrate its application in pro- viding a complete characterization of "interim"-implementability of performance standards by an uninformed social planner in economies with asymmetrically informed agents. We highlight the shortcomings of the concept of Bayesian equilibrium and its application to the mechanism design problem. It is shown that an analogous Revelation Principle does not hold and self- selection need not be a necessary condition for interim-implementability. Instead of the usual direct revelation mechanisms, wc. suggest that mechanisms should be of a "Tweed ring" variety.
I am grateful to Jeff Banks and William Thomson for their guidance and support and to Dimitrios Diamantaras, Laurence Kranich, Larry Samuelson, Sanjay Srivastava and Steve Turnbull for their comments. I have also benefited greatly from comments and discussions at seminars where an early version of this paper was presented. I thank all the participants. I am solely responsible for any errors.
ASYMMETRIC INFORMATION, "INTERIM" EQUILIBRIUM AND
MECHANISM DESIGN
1. Motivation
This paper presents an alternative theory of games and mechanism design for economies with informational asymmetries. We provide a critique of the available models and present a new equilibrium concept for games played by agents who have observed noisy private information and can, conceivably, acquire new information through communication and other means. We demonstrate its application in com- pletely characterizing the implementability of performance standards by an uninformed social planner in economies with asymmetrically informed agents. Thus far, all avail- able characterizations of implementability have been partial and extremely restrictive. A performance standard embodies the aspirations and objectives of a social planner or of the economy as a whole. Analytically, it is a mapping, say ip, that specifies the set of feasible "(^-optimal" allocations for every state of the world. By implementation of if, we mean that there exists a game (or mechanism) such that, for every state of the world, the set of equilibrium allocations of the game exactly coincides with the set of (^-optimal allocations.
The literature on implementation, or the "theory of mechanism design," has branched in two directions. One direction is exemplified by the work of Hurwicz C I I i '2. J, Maskin £ / &}, Groves and Ledyard ([ "7 } and Schmeidler (_ 23~). This school of thought implicitly interprets Nash equilibrium as a solution concept for games played by agents with incomplete information. This is the "privacy-preserving"
property of Nash-implementation mechanisms (see Hurwicz (_ I 4-3)- A Nash equilib- rium is modelled as a stationary point in an iterative process of strategy proposals. Do justify Nash-type behavior, it is assumed that the agents are somewhat myopic: they do not learn from the past and each one of them believes that the others will not deviate from their components of the current round of strategy proposals (see Laffont and Maskin £ 1 5 ~} and Maskin Q \ 7~) for a discussion of these assumptions).
The two principal shortcomings of this paradigm are: (i) the uncertainty in the environment and the asymmetry of information is not explicitly modelled, and (ii) since we assume myopic behavior on the part of the agents, this interpretation is not entirely satisfactory from a game-theoretic viewpoint. The strength of this paradigm is that it gives us a complete characterization of Nash-implementable performance standards by isolating a single property of standards - that of monotonicity, due to Maskin ^ \ to J - which is both necessary and sufficient for Nash-implementation in economic environments with at least three agents.
The alternative school takes a Bayesian approach a la Savage C^J Based on the contributions of Harsanyi £ <3 J, it interprets Nash equilibrium as a solution concept only for games of complete information. To take account of incompleteness of information, the agents are endowed with prior probability distributions on the set of states of the world. This school (exemplified by the work of Myerson (jXCQ, D'Aspremont and Gerard- Varet £ /\ J, Harris and Townsend [ <g ], Holmstrom and Myerson £ \0 ], Postlcwaite and Schmeidler [l5], Palfrey and Srivastava (_1~3^ and others) invokes Harsanyi's extension of Nash equilibrium for asymmetric infor- mation games - Bayesian equilibrium. The rationale underlying such an equilibrium concept (see Myerson £1t j) is that before playing the game, and before observing
any private information, each agent utilizes the common knowledge elements of the environment to predict the strategy that the other agents would play at an equilib- rium. Given that all agents make accurate calculations, each one of them arrives at an equilibrium in one shot. Alternatively, an unbiased and uninformed outsider, who has access to the same common knowledge elements, could perform the same calculations and suggest an equilibrium to the agents.
Despite the appeal and elegance of this paradigm, we shall argue that this paradigm has two major shortcomings: (i) the Bayesian equilibrium concept (or any of its refine- ments) does not always adequately predict the strategic behavior when play of a game begins after private information is observed, and (ii) it has very restricted use in one of its most fundamental applications - mechanism design and implementation. Our arguments for (i) are given with the help of Example 1 in Section III below and may be summarized as follows. We shall argue that a Bayesian equilibrium has several implicit assumptions which are unrealistic, given that our objective is to model decentralized decision-making: (a) agents cannot communicate, (b) it is the one-shot outcome of a calculation made from the perspective of an uninformed outsider, i.e. decisions are made ex ante (corresponding to the stage when no agent has received any private information), and (c) from a practical viewpoint, to attain a Bayesian equilibrium, typically, the aid of an unbiased, uninformed outsider is required. A Bayesian equi- librium may be unanimously renegotiated by agents at the interim stage (i.e. when all agents have received some noisy private information). This can occur either in a situation of open communication with recontracting and strategy revision permitted at the interim stage, or when the play of the game begins only when agents have re- ceived private information. There are many situations where there is a clear incentive
for some form of communication and, therefore, a "zero-communication" assumption is somewhat artificial. Moreover, since we wish to model agents who already have pri vate information when they make their economic plans and decisions, a "no revision of strategies in the interim stage" assumption is equally artificial. Finally, we need a gen- eral model for a vaxiety of realistic situations of decentralized decision-making, where play of a game begins iteratively after private information is observed and attains an equilibrium without the aid of an outsider. Such a model must take into account infor- mation acquisition during play of the game, either through communication or through other means.
This points to a lack of stability of Bayesian equilibria, with respect to the ob- servation and acquisition of information by the agents in the interim stage. Similar issues have been raised in Holmstrom and Myerson's ( 1 0 J discussion of the design of efficient decision rules under asymmetric information. We shall argue that the prob- lem that they refer to as lack of durability - i.e. the lack of coincidence between the recommendations from an outsider's perspective and the decisions taken by privately informed agents - has much more general implications; it is as much of an issue in the primary task of defining an equilibrium concept itself.
The second limitation with the Bayesian approach, i.e. (ii) above, relates to the application of Bayesian equilibrium to implementation. A necessary condition for Bayesian-implementation is that a performance standard must satisfy a self-selection property. This means that, for a given (/?, there is a direct game, i.e. one where each agent reports his/her information, which has a Bayesian equilibrium satisfying the following: (a) the equilibrium allocation rule picks a (^-optimal allocation in each state, and (b) truthful reporting by all agents is an equilibrium strategy. This severely
restricts the scope of Bayesian-implementability since many performance standards would not satisfy this property unless we impose strong restrictions on the structure of private information. Furthermore, such a restriction ("non-exclusivity of information", i.e. if all agents but one pool their information, they should be able to deduce the information of the remaining agent) has been used to isolate sufficient conditions on standards for Bayesian-implementability (see Postlewaite and Schmeidler £ 15 )). This restriction excludes most of the situations with asymmetric information that are of interest to economists. Typically, private information is truly exclusive and relates to preferences, reservation wages, "insider" information etc. Ideally, we would like to have a characterization of implementability independent of such restrictions.
To summarize, there are several difficulties with implementation theory as it stands. On the one hand, the theory based on the Nash equilibrium concept does not explicitly model informational asymmetry and assumes that agents are myopic. Yet we have a complete characterization of Nash-implementability in terms of a single property of monotonicity which is satisfied by several familiar economic performance standards. On the other hand, the theory based on Bayesian equilibrium provides an explicit model of asymmetric information. However, as we shall argue, the Bayesian equilibrium model is not representative of decision-making in the interim stage. More- over, since we cannot Bayesian-implement any performance standard that does not satisfy self-selection, this rules out many desirable standards. Since we do not have a complete characterization of implementability in general asymmetric information environments we know of no way to implement standards without making strong in- formational restrictions.
Our objective, in this paper, will be to propose a new paradigm which does away
with the shortcomings discussed above. A new equilibrium concept is presented - rim equilibrium. The basic model is still Bayesian; thus, the informational asym- metry is explicitly modelled. A game is played through an iterative process of strategy adjustments that begins after private information is observed. An equilibrium is de- fined for each state and is durable in the sense that it is stable with respect to any information acquisition (through communication or by other means) in the given state and to any mistakes or "trembles" in the agents' learning process while acquiring the information. The objective is to develop a model which is broad enough to tackle the complicated nature of the problem at hand.
Though existence of Interim equilibria is not guaranteed for a general class of games, for the purposes of its application to mechanism design, Interim equilibria can be shown to exist. A counterpart ©}. the Revelation Principle . which is a cornerstone of the mechanism design literature, breaks down. We present a complete characteri- zation of the mechanism design problem in terms of interim-implementability using a single property of performance standards. It is shown that it is possible to interim- implement standards without the restraint of a self-selection property or some restric- tion on the structure of private information such as non-exclusivity of information. We demonstrate an algorithm with which mechanisms for interim-implementation can be generated. This uses the concept of a "Tweed ring" (see McKelvey ^ 18 J) and requires each agent to report his/her own information and the information of one other person. Given the inadequacy of direct mechanisms, due to the failure of the Revela- tion Principle, the presence of such an alternative has important applications to the ign of optimal contracts and other mechanisms. A related set of issues is studied in Green and Laffont £ £ j. They analyze the
behavior of agents who communicate with no binding commitments in a preliminary stage and make binding commitments in a final stage. A much more specialized ques- tion is addressed in their paper. Though our framework and motivation is different, the implications of our study are more general.
The following section introduces the basic environment - a general equilibrium model of pure exchange with privately held assets, in the footsteps of Postlewaite and Schmeidler £25}. Given the nature of the problem, we anticipate an abundance of notation. The term "asset" is used to denote any commodity whose value to an agent is uncertain. The initial endowments of assets is common knowledge; to this extent, informational decentralization is partial. Each agent has access to exogenously spec- ified signals which help him/her to partition the set of possible states in a particular manner. Each event in an agent's partition contains a collection of states among which the agent cannot distinguish. Once a particular state of the world is realized, each agent observes a particular event in his/her partition which defines his/her initial in- formation set. This is the interim stage of decision-making. It is conceivable that more information can be acquired during the play of the game which leads to a refinement of this initial information set. Following the next section are the three main sections which present our findings. The final section provides a brief conclusion.
2. Preliminaries
We consider a class of exchange economies with £ privately consumable assets and n asymmetrically informed agents with n > 1. TV is the set of agents and $ is the set of states of the world, with i and xp denoting the respective generic elements. \I> is assumed to be non-empty and finite.
s
For any set X , p(X) is the set of subsets of X. Each agent i £ N is characterized by a list {C, Ui,u>i, IT,, 7*} where C, = R+ is agent i's consumption set, u, : C, x *I' — > R is agent i's von Neumann- M org enstern utility function, cot £ R+ is agent i's initial endowment of assets, II,- C p(^) is agent i's partition of the set of states and q* : $ — ► (0, 1] is agent i's prior probability distribution on the set of states. Let 2, denote a generic element of C, and let 7Tj denote a generic element of II, . Also, let C = Xi£wd, II = x,e/vn,- and £1 = YlitN^*- Unless specified otherwise, let x = (x{)i£N and x_,- = (xj)jeN\{i)- For all i E iST, C,-,u,-, u;,-,nt- and 9* are assumed to be given exogenously, independent of the element of ^ that is realized, and are common knowledge in the sense of Aumann (I J.
To summarize, an economy is completely characterized by the realization of a state of the world xp and the class of economies under consideration is correspondingly characterized by ty. We are interested in economies in a class where the following condition is met: for all i £ N and xp £ ^,it,(., .) is strictly increasing in z,\
The aggregate endowment of the entire population of agents determines the set of attainable allocations, A = {z £ C : YliGN Zi — ^)- ^n a^oca^lon TU^e is a function / : ^ — > A with F as the set of all such rules. A performance standard is a mapping <p : ^ — ► p(A)\0. We are interested in performance standards that satisfy the following weak condition: for all xp £ ^ for all z £ <p(xp), z /0. By a slight abuse of notation, we shall use / £ </? to denote the case where for all xp £ ^,f{xp) £ <p(xp).
A <7<i7tte /orm or simply game or mechanism, F, is a triple {TV, M,£}. Given that M, is agent i's message (or action) space, M = x,G/vA/,- £ : A-/ — ► C is an outcome function. Agent i's strategy, is a function .s, : FI, — ► M,, with Si denoting agent i's strategy space and S = X.^/vS,.
0
Let the function /,- : # -* Hi be defined by U(yb) = {</>' E * : 3", E 11; such that ip,yj' E 7Tt} E IIj. /,(?/>) is agent i's initial information set given xp. Note that the set Ii{4>) specifies the largest collection of states of the world which agent i cannot distinguish from the realized state, xp. If information were complete, then for all i E N and all t/> E ^, we would have U(xp) = {ip}- We shall need to consider any new information that the agents can acquire during play of the game. This corresponds to refinements of the initial information set. R{(xp)) = p(/,(i/>))\0 is the set of all non- empty refinements of agent i's initial information set given xp, whose generic element is denoted />,-. Note that this allows for the possibility of acquisition of misleading information, i.e. there exist pi E Ri(xJ>) with xp £ p{. Agent i's posterior probability distribution is the function g, : \I> x £>($)\0 —> [0, 1] defined by Bayes' Law, i.e. for all xp 6 #, for all H E p(*)\0,
{ 0, otherwise.
Agent i's expected utility from f E F, given pi is given by
J2xp'epi 3*(V,')P*)ui(/i(V'')>V'') and is written more compactly as EUx(f | /?,); agent i's expected pi-lower contour set at /is denoted ELt(f | p,) = {g E F : EU,(f | /?,) > EUi(g | Pl)}.
We shall maintain an important assumption in the rest of the paper. It is generally maintained in the existing literature on asymmetric information and implies that all sources of uncertainty are within the given economy. To see how this assumption can be relaxed, see (iii) in the concluding section of this paper.
Non- Redundancy of States Assumption (NRS): \/xp E <£, nteNIl(xp) — {xp}.
3. "Interim" Game Theory
10
In this section, we shall introduce and motivate a new concept of equilibrium for games with asymmetric information. For the purposes of this paper we shall simply consider games with pure strategies. We shall first define Harsanyi's £ 9 ) notion of an equilibrium.
Given a game T = { N, M, £} and given / = (oso/, the pair (5, /) G S x F is a Dayesian equilibrium, of F if
W> G tf,Vi G iV,V5;. G S„£ o (5; o Ii,s-i o /_,•) G ££,(/ 1 /.(</>))■
Let ^(T) C S x F denote the set of Bayesian equilibria of T and let Es(F) C S and £f(T) denote, respectively, the projections of the set E(F) on S and F.
This definition is a little different from the standard definition. It saves on notation in the sequel. To illustrate the shortcomings of Bayesian equilibrium and to motivate the alternative equilibrium concept that we shall subsequently introduce, consider the following example.
Example 1: Two thieves are arrested and the following day they are simulta- neously asked to plead either "guilty" or "not guilty" or sign an agreement to leave town. A few hours before they decide, one of the two lawyers in town is supposed to walk into prisoner 2's cell and inform her that he will handling their case. One of the lawyers (the good lawyer) has an excellent reputation for representing his clients and the other (the bad lawyer) has lost all the cases he has ever handled. Prisoner 2 finds out which one of the lawyers will be representing them at the time of making her decision and is, therefore, completely informed. Prisoner 1 is completely uninformed about the quality of the lawyer. Given the payoffs associated with the decisions of the prisoners, we have a game with asymmetric information.
Supp<>:-<- that the set of prisoners is iV = {1,2} and the set of states is $ — {G,B}
11
where G is the state where prisoner 2 meets the good lawyer and B is the state where she meets the bad lawyer. The information structure is as follows: 111 == {(G,B)} and n2 = {(G), (B)}. For i = 1,2, suppose that q*(G) = 0.25 and q*(B) = 0.75 are prisoner z's prior probabilities on {G, B}. Let m; correspond to pleading "guilty", let mj correspond to pleading "not guilty" and let m" correspond to signing the agreement to leave town. Finally, let £ be such that the final payoffs to the prisoners in terms of VNM utilities are given by the bi-matrices in Figure 1. This defines the game, denoted Ti . All of this information is common knowledge among the prisoners and is a description of the ex ante stage, when no private information has been observed. At the interim stage each prisoner observes an event in his/her partition.
[Insert Figure 1 here]
There are two (pure strategy) Bayesian equilibria of this game, i.e. Es(Ti) = {5,5'} which are given by:
*i((G, J3)) = ml-s2((G)) = m2,s2((B)) = m2
and
5i((G,£)) = m";s'2({G)) = m'i,s'2{(B)) = m".
Two crucial asumptions are implicit in the concept of Bayesian equilibrium: (i) there is no possibility of communication among the agents and (ii) that the equilib- rium is reached in a one-shot calculation made from the perspective of an uninformed outsider. The common knowledge elements of the game are sufficient to calculate a Bayesian equilibrium. Hence, an equilibrium can be predicted by each one of the pris- oners before playing the game and before observing any private information. There is
12
a danger with the prisoners independently making these predictions. One of them may predict s and the other may predict s' and the resulting outcome would be disastrous - (0, 0). Therefore, to actually attain an equilibrium in one shot, the help ot an unbiased and uninformed third-person may be required. Such a person can perform the same calculations using the common knowledge elements and suggest an equilibrium to the prisoners. Thus, from a practical viewpoint, there is a third assumption underlying Bayesian equilibrium: (iii) an unbiased and uninformed outsider exists.
Our objective is to develop models of decentralized decision-making (i) is a rather artificial restriction when there is a clear gain from communication, (ii) fails to account for several realistic situations where an iterative process of strategy adjustments begins after private information is observed, (iii) is not a desirable assumption in models where decision-making is decentralized. When these conditions are relaxed, a Bayesian equilibrium is, in general, not durable in the sense that it is not stable with respect to the private information that agents can independently observe and acquire during play of the game in the interim stage.
To see this in our example, suppose that (sj,^) is the chosen Bayesian equilib- rium. Recall that 5 is an "equilibrium" list because it has a self-enforcing property. However, it is self-enforcing at the ex ante stage. In the interim stage, i.e. once a state of the world occurs, and the prisoners observe an information set, the self-enforcing nature of 5 is jeopardized by the fact that at least one of the prisoners has an incentive to communicate with the other. Regardless of whether prisoner 2 observes state G or state B, she will always prefer to convey her information to prisoner 1 in some credible way. By conveying her information, 2 ensures that 1 is completely informed too. Thus, the prisoners would end up playing a complete information Nash equilibrium message
13
(m\,m'2) in state G or {mum2) or (m",m2) in state B. The corresponding outcomes Pareto-dominate the Bayesian equilibrium outcomes. The outcome in state G would not have been possible if the prisoners were committed to their strategies decided ex ante.
As Holmstrom and Myerson (1^1 have pointed out "we are assuming that the individuals already have their private information... when they meet to make their economic plans and decisions. That is, we are studying economies in which the ex ante stage... has already passed (if it ever indeed existed) so that 'ex ante' commitments are impossible." (pp. 1810) Ideally, we would like to have predictions from a general model, where the play of the game begins at the interim stage, where the equilibrium concept is stable with respect to any information acquisition (through communication or otherwise) and which does not require the aid of an outsider to attain an equilibrium.
Though there can be several ways of modelling this complex situation, we shall adopt the following one, which, we believe, is fairly general. A strategy will still be interpreted as a plan for an agent which specifies a message for every initial informa- tion set. A state of the world occurs, initial information is observed and play begins. Strategies are proposed by agents and subsequently revised if they feel they can do better. We shall suppress the dynamics of the iterative process of proposals and con- centrate on characterizing the equilibrium itself. An equilibrium is reached when there is a strategy list such that no player wishes to unilaterally revise his/her component of
the list. Once an equilibrium is reached, messages are computed using the equilibrium
1
strategies.
When an agent checks if his/her component of a given strategy list is a best response to the remaining components, he/she must keep in mind the information
14
that is publicly and privately available, and any information that can be acquired.. Suppose tp is the realized state of the world. Agent i observes the event Ii(xp) and knows that any state which is not in /,-(r/>) could not have occurred. At any given point in the process of strategy proposals, i must take into account a number of factors: (i) the history of past proposals and revisions conveys information; (ii) the currently proposed strategy list would convey information if i were to believe that the remaining agents do not deviate from it; (hi) information could be communicated by other agents in the past, present and in future and some of that information could be misleading; (iv) exceptionally clever agents would propose and revise strategies in a manner such that other agents are misled; (v) i could make small mistakes in acquiring information since it may require complex calculations and a precise knowledge of all the common knowledge elements; (vi) i may have imperfect recall of past play; (vii) i may not want to have any regrets in case there is some information that may be released in future; (viii) i may have to program a computer to play a best response strategy at the start of the game and he/she may not be able to revise the program once the game is in progress. To summarize, for every state rft, we are looking for a definition of an equilibrium of a game played in tp which is stable no matter what information agents may acquire in xp.
In other words, given a proposal s, every agent i must check that 5, is a best response to 5_t for every non-empty subset of i's initial information set in state, xp. Our interest in such a strong definition can be likened to the widespread interest in studying dominant strategy equilibria. The conceptual difference here is that instead of checking for dominance over the entire strategy space S, for each i, we check for dominance over the subspace of strategies that are z's best responses for alternative
15
refinements of the initial information /,(t/>), to a given s_,. This intuition is formalized in the concept of equilibrium defined below.
Given that a game T = {TV, M, £} is played in an economy rp G ^ and given z = £(s(I(ift))), the pair (s, z) G 5 x A is an Interim equilibrium of T in 0 if
Vi G iV,Vp, G fliW0,V4 G S,-,£ o (5', o /,,5_t o /_,) G ELi(£ osoI\ Pi).
Let jE(r, ip) C SxA denote the set of Interim equilibria ofT inxj) and let Es(T, xp) C S and -E^r,^) C A denote, respectively, the projections of the set £,(r,t/>) on 5 and A. To see the kind of predictions this equilibrium concept yields, consider the situa- tion in Example 1. For instance, suppose the state G had occurred. Then no prisoner would change strategy if they are confronted with a list 5* such that for i = l,2,s* is a best response to s*_{ for any refinement of i's initial information in state G. This property is met if s* is defined by:
s\({G,B)) = mi;s£((C7)) = m'2,s*2{(B)) = m'2.
Thus, s* G Es(Fi,G). Observe that s* £ ^s(Ti) because S2 is not a best response to s^ in case agent 2 had observed the state B. The payoff pair (2,6), which would have eluded the prisoners had they played Bayesian equilibrium strategies, are available as Interim equilibrium outcomes in the state G. Also, check that s £ Es(Fi,G).
The agents could behave naively and check that a strategy is a best response, for their respective initial information sets, to the other's strategy. In this particular case, however, there are at least two possible ways in which the uninformed agent can refine his initial information {G,B} upon observing s*. Prisoner 2 may try to communicate her information that G has occurred by telling prisoner 1, "the good lawyer will be representing us and I am willing to sign a contract which says that if you play 5J then
16
I will play 5o" . The credibility of this communication depends on which one of the two rationales prisoner 1 believes.
Rationale 1: Prisoner 1 checks that the message m^, specified by S2, is dominated in state B. Thus, he could use the following argument: prisoner 2 will not deviate from 5* only if it is the case that state G has occurred. Thus, prisoner 1 could conceivably refine his information set {G,B} to {G}.
Rationale 2: Prisoner 1 knows that prisoner 2 realizes that in state J3, she cannot achieve the outcome that is the best one for her - (0,4) - since prisoner 1 will never play m\ if prisoner 2 plays vn-i in state B. However, prisoner 2 can hope to achieve the outcome which is second-best for her - (1,3) - by playing m'2 and hoping that prisoner 1 plays m\ . So it is conceivable that state B has occurred and prisoner 2 is a sophisticated player who will not deviate from s* . Using such an argument, prisoner 1 could refine his initial information {G,B} to {B}.
Thus, even if 2 communicates her information to 1, her credibility depends on the kind of player that 1 thinks 2 is. If prisoner 1 is not sure, he will not gain any information. To make sure that s \ is a best response to s% no matter what prisoner 1 may have deduced, every conceivable information set must be considered - {G,B}, {G} and {B}. On the other hand, prisoner 2 takes advantage of the fact that her observed information helps to eliminate one of the states of the world. She does not care that Sj is not a best response to s* in state B. Given that the good lawyer appears, both prisoners plead "not guilty" and achieve the best possible outcome (2,6). Moreover, no matter how information is refined, in the state G,s* Pareto-dominates both 5 and
s'.
This, of course, does not imply that Interim equilibria always Pareto-dominate
17
Bayesian equilibria. Given the impossibility of ex ante commitments, and the tendency of real-world agents to communicate, and the fact that we assume that iterative play begins at the interim stage, the former concept seems more natural than the latter. There is no logical relationship between Bayesian equilibria and Interim equilibria. An Interim equilibrium allocation of a game in a given state is a complete information (Bayesian) Nash equilibrium allocation of the game in that state. This follows from the definitions.
It may appear that in our zeal to define a stable equilibrium concept, we may have gone too far. The set of Interim equilibria may be empty for a large class of games. However, the equilibrium concept is still a meaningful one because it has several useful applications. In this paper, our objective is to apply this concept to the general problem of mechanism design in asymmetric information economies. For any game we consider in this application, we shall demonstrate existence of Interim equilibria.
The problem of mechanism design can be motivated as follows. Unfortunately, the Pareto-dominant outcome (2, 6) in Example 1 is not the only Interim equilibrium outcome in state G. In general, given some set of desired social objectives (specified by a performance standard), we would like to have a game or mechanism so that for every state of the world all its equilibrium outcomes are thus "desirable". Thus, our objective is to design a game or mechanism for the implementation of a given performance standard using the equilibrium notion that we have just motivated. This subject is addressed in the following sections.
4. Further Revelations on the Revelation Principle
IS
In this section, we shall give an appropriate definition of the notion of "imple- mentability" of a performance standard. We shall argue that a self-selection property is not necessary for a standard to be implementable in our sense. We begin with a few definitions.
A direct game is a game Td = {N, M, £} such that Vt G N,Mi = Hi. Let Qd denote the class of all direct games.
Revelation Principle (Rosenthal 02-1% Myerson (.2.CTJ, Dasgupta, Hammond and Maskin £3 3? Harris and Townsend C £ 3): ^ with / G Ef(T) ^=> 3 Td G Qd and s G S such that (sj) G E(Td) with Vi G ^Vtt,- g Hi, «,•(«-,-) = tt,.
A performance standard </? satisfies self -selection (SS) if V/ G </>> 3Td G ^ and s G 5 such that (5,/) € E(rd) with Vt € iV,V7rt- G Ilf, 5t(7rf) = tt,.
The Revelation Principle has been the fundamental result which has been used to characterize the choice of a mechanism in both the theoretical and the applied liter- ature on auctions, optimal contracts, optimal taxation, principal-agent conflicts, etc. However, the principle simply says that any allocation rule that can be realized in a Bayesian equilibrium of any arbitrary game can be realized in a Bayesian equilibrium of a direct game, whose corresponding equilibrium strategy induces truthful revelation. This places no restriction on the remaining portion of the equilibrium set of the direct game. It is possible that there are other equilibrium strategies which involve untruthful reporting. Thus, if a particular direct game is the chosen mechanism simply on the ba- sis of the properties it satisfies in case the "truthful" equilibrium occurs, it may not be sufficient to ensure that the same properties are met in case the "untruthful" ones are realized. In fact the "untruthful" equilibria may Pareto-dominate the "truthful" one. This loophole with the reliance on "truthful implementability" has been pointed out
19
by several authors recently (Milgrom £ | 9 J, Repullo £Z6j), Demski and Sappington £ 5 "J, and Postlewaite and Schmeidler £X5"J). Postlewaite and Schmeidler present an argument for approaching the mechanism design problem from the viewpoint of Maskin Q f (y^. A game is said to (fully) implement a given performance standard, </?, if for every state, its set of equilibrium allocations coincides with the set of (^-optimal allocations. This ensures that all equilibria have the desirable properties. The crucial implication of the Revelation Principle is that even though SS is not sufficient for Bayesian-implementability of a standard, it is a necessary condition.
In this section, we shall replace the Bayesian equilibrium concept with that of In- terim equilibrium. The concept of implementation underlying our approach to mech- anism design is given by the following definition:
A performance standard </? is interim-implementable if 3r such that Vt/> 6 *, EA(T, tp) = ip{xp).
An analogous re-definition of the SS condition would be:
A performance standard tp satisfies interim self-selection (SS') if V/ G ip, 3Td G Qd
+*; e 71},
and 5 G S such that Vt/> G $,(s, /(</>)) G E(Td,ip) with Vi € iV,st-(7rf-) = tt,.
A
The following theorem shows that an analogous Revelation Principle does not hold if the equilibrium concept is changed from Bayesian to Interim. The result is proved using an example where we show interim-implementability of a performance standard which does not satisfy either SS or SS'.
Theorem 1: There exists T and f £ F with the following properties: (i)forallrpe *,/ty) € EA(T^) (n) there exists no Td G Qd that satisfies for all xp G $,/(» G EA(Td,xp).
Proof: The proof is by way of the following example.
20
Example 2: Consider the problem of a giant firm which markets two products from two divisions. Division 2 has a better market research department and is fully informed about the demand characteristics for the two products. Since the divisions compete for the firm's limited resources, the manager of Division 2 may not have the incentive to let either the manager of Division 1 or the firm's general manager know about the information gathered by the market survey. The job of the general manager of the firm is to allocate resources such that the firm's total profits are maximized. Let N = {1,2} be the set of managers of the divisions, let ^ = {r/>',i/>*} be the set of demand characteristics, let III = {(;/>', t/>*)}, II2 = {{ip'), (0*)} De the information partitions of the two managers, let ql(ip') = 0.75, ql(xp*) == 0.25 be the prior probabilities of Division l's manager and let {a, 6, c, d, e,r} — A be the set of feasible allocations of the available resources. Consider a game 1^2 = {N,M,£} where the manager of Division 1 has two possible messages and the manager of Division 2 has three possible messages, i.e. Mi = {mi^Tn^} and M2 = {m2,m2,m2}. The bi- matrices in Figure 2 give the information relating to the resource allocation rule used by the general manager, i.e. the function £ : M — » C and the profit functions for the two divisions, i.e. for i = 1,2, u, : C, x $ — ► R+. The letters in parentheses represent the allocation, £(m) and the pair of numbers represent the profits to the two divisions, Ui(&(m),V>),*-=l,2.
[Insert Figure 2 here]
It (;,ii be checked that
{(5,e),(s',C)} =£(r2,r//)
21
where5l((^^TA*)) = m;;62((V''))=m^52((^*))-m^and6'1((V'^tA,<))-m'1;4((V',)) m2,s2((V'*)) = rn'2 Also, it can be checked that
where *i(Wi#*)) = mi;s2((^')) = m2, s2((</>*)) = m2. Let / : # — A defined by /(*/>') = e and f(tp*) = a. /is realized as an Interim equilibrium of T2. To prove the theorem, we need to show that there cannot exist any direct game which realizes / as either Interim or Bayesian equilibria. To see this, we shall try constructing a direct game and show that no such construction will succeed.
For the problem at hand, a direct game, say Fd = {N, Md,£d}, must be such that Md = {(t/>',t/>*)} and Md = {(*/>'), (V'*)}- In addition, for / to be realized as Interim equilibria of this direct game, we must have {e, a} C [z £ t,d(jnd) '■ "^ G Md). Moreover, since | Md |= 2, we have {e,a} = {z G £d(md) ' rnd G Md}. Thus, we can have only two possible direct games satisfying these requirements. These are given in Figures 3 and 4. As in Figure 2, the letters in parentheses denote allocations and the pairs of numbers denote the associated profits to the divisions. Let these games be denoted Td and Td.
[Insert Figures 3 and 4 here]
It can be checked that
{e} = EA(rd3, t//) u EA(rd, r) u EA{vt v') u EA(ri,i>*).
Thus, we have shown that there is no Fd G Qd satisfying either (a) for all ^ € {*/>', 0* }, fW G EA{Td,il>) or (b) / G EF{Td). Q.E.D.
22
The divisional managers' private interests do not coincide with the firm's over- all objective, and the role of the general manager is that of a social planner. 'I he performance standard for this firm is the profit-maximizing allocation rule /. By con- struction, T2 interim-implements /. In the games T^ and T^, since truth-telling is not a best response in both states for Manager 2, / does not satisfy either SS or SS\
This raises a broader question: how can we tell whether or not a performance standard is interim-implementable in general? A complete characterization of interim- implementability is given in the following section.
5. Interim-Implementation
This section is divided into three sub-sections. In the first one, a crucial property of performance standards is introduced. The second sub-section presents an algorithm for generating mechanisms. The third sub-section presents a general characterization of interim-implementability.
Manipulation and Monotonicity
Consider a state of the world tft. We can derive another state t/>' which has a special relationship with ifr, in the sense that by manipulating their private information observed in stale r/>, agents can credibly pretend to an uninformed coordinator that the state is rp' . In other words, consider some mechanism in which each agent i is asked to report his/her information set as part of a message. Suppose agent i observes /,(t/>). The individual reports can be manipulated in a manner consistent with the common knowledge information, i.e. the given information structure II and the NRS assumption. These ideas can be formalized in a manner similar to Postlewaitc and Schmeidler {25} and Palfrey and Srivastava C 2-2. ]
23
A collection of compatible manipulation operators for U (CCMO), denoted a = (at)l€/v, is defined by
(i)Vi€N,ai : Hi -* n,-,
(«')v?r g n, {nteN7rt ^ 0} ==> {ntGNa,(7rt) ^ 0}.
By NRS, if Cii€N^i ^ $> tnen I ^ieN^i(^i) \= 1- Therefore, for any CCMO a, we have a well-defined function t/,a : ^ — ► ^ which is defined by ipa(tp) = rWe/va^/.-^)).
Next, we define an important property of monotonicity of performance standards. It is a generalization of a property devised by Maskin (| £> ) in the context of Nash- implementation. In the Bayesian-implementation context, alternative generalizations have been given by Postlewaite and Schmeidler ( 2*5) and Palfrey and Srivastava
( MO-
A performance standard cp satisfies Interim Monotonicity (I-MON) if V/ £ F,Vxp £ #,V CCMO's a, given t/>' = r/>a(», the following holds: If
(0/W) ^W'),
(u)Vi£ Ar,Vy £ F, {V/>; £ Ri(tl>'),9 £ ££»(/ | />;■)} ==» {V/>, £ ^),?o 0" £ EL,-(/ o ^° I /?.)},
then
/(0')€^).
The importance of this, rather complicated and yet crucial, property will become clearer later on.
For the special case of complete information, for all i £ N, for all xp £ $, It(ip) = {tA}. If each agent manipulates his/her report of the true information set, then each
24
agent i reports /,(t//) = a,(/,(^)). Thus, ntG/vW) = W)- Next, pick /(*//) G <p{tp'). Complete information among the agents ensures that the state agreed upon will be xf>'. Part (ii) of the definition of I-MON ensures that for all g 6 F, if g satisfies the following for all i € iV,
then the following is true for all z E iV:
«.-(/«WaW)),^)>«ibiWttW),^).
For </? to satisfy I-MON, we must have f{ip') G <£>(V0- Given that tjja(ip) — tp' , it can be seen that this simply corresponds to Maskin's ( ' £ ) monotonicity condition when interpreted in a complete information context. The definitions do not suggest a logical relationship between I-MON and the properties developed in Postlewaite and Schmeidler £.2-5] and Palfrey and Srivastava ('2.'2. ., 2~\ ).
A "Tweed Ring" Algorithm
Since we are unable to solve the implementation problem by simply construct- ing direct revelation mechanisms, we need to devise a method by which alternative mechanisms for interim-implementation can be constructed. In this sub-section, we introduce a "Tweed ring" algorithm, Q. When a particular performance standard, </? is inserted in the definition below, we have a game or mechanism, G(y>)- Observe that the rules of a game Q{<p) is not dependent on t/>, so it can be operated by an uninformed planner. This algorithm will be used to prove the results in the following sub-section. In the description below, all indices used to denote agents are to be read "modulo n". Q is defined as follows:
(I) | N |>3.
25
(II) Vz G N,Mi = {mi = (7r;(0,7ri+1(0,/(0^(0) € 11; xILi+1xFx (5,10]} Remark 1: The index in parentheses denotes the name of the agent who is transmitting the message. 7r,(z) should read, "agent z's announcement of an event in his/her own partition" and 7^4.1 (z) should read, "agent i's announcement of an event in his/her neighbor i + l's partition", f(i) should read, "agent i's announcement of an allocation rule" and 6(i) should read, "agent z's announcement of a number in the interval (5, 10]" .
The following notation will be used: (Dl) Vi G N, define 6t : M_, -> p(¥) by 0f(m_.) = {r^e/vu^O')} n {ir,-(t - 1)}. (D2) Define 6* : M -* p($) by 0*(m) = nieNXi(i). Remark 2: Note that by the NRS assumption, (i) Vz G 7V,Vm_t G M_,-,
{ni€2v\{,-}*j(j)} n{T,<i - 1)} ^ 0 =» I {n;GN\{t}^0')} n {x,-(i - i)} |= 1 and (ii)
nzG/vTr^z) 7^ 0 =^ I ntG/V7rt(z) |= 1.
(D3) Vz G N,m-i satisfies Property 7 | z if the following conditions hold:
(i) 0i(m-i) ? 0.
(ii) 3/ € if such that Vj G N\{i}J(j) = /.
(iii) Vj G A^\{z},<5(j) = 10. (D4) Vm G M,/v(m) = {i 6 N : <5(z) G (5,10] with 6(i) < 6(j),Vj G N\{i}}.
(III) £ : M — ► C, is given by the schematic diagram in Figure 5.
[Insert Figure 5 here]
Remark 3: The term "Tweed ring" comes from a political cartoon by Thomas Nast
in Harper's Weekly in the 1870's, which exposed the corruption and misappropriation
of public funds by William Marcy Tweed, an infamous New York politician and his
ring". The cartoon depicts Tweed and his cronies arranged in a circle with each
26
person pointing to the person to the right of him when asked who had stolen the public funds. Likewise, the games derived from Q are not direct revelation mechanisms. The players are arranged in a circle and each one of them transmits a message regarding both himself and a neighbor (to the right perhaps). Moreover, they are also asked to suggest an allocation rule and a number in the interval (5, 10]. The choice of these particular end-points, i.e. 5 and 10 is purely arbitrary. (5, 10] could be interpreted as a time-interval, with an agent's announcement of a number being interpreted as a point in time when the agent intends to join the queue.
Characterization of Interim-Implemeriability
In this sub-section, we shall show that in economies with more than two agents, the I-MON condition is both necessary and sufficient for interim-implementability. We shall first prove a series of lemmata using the Tweed ring method introduced earlier. The proofs of these lemmata are relegated to the appendix.
Lemma 1: Let <p be a performance standard. Vtf€*,pWCJ5A(0fo>),tf).
Lemma 2: Let </?, ip and s(/(?/>)) = m be given. If s £ Es{G{^p)-> V0> then m must be such that Case 1 is applicable.
Lemma3: Let <p be a performance standard satisfying I-MON.Vip E ^, £,4 (£(</>), t/>) C ip(ip).
Given the assumption that for all xp £ ^^(ip) ^ 0, Lemma 1 gurantees existence of Interim equilibria for any game G(ip)- Now we can provide a complete characteriza- tion of interim-implementation in asymmetric information environments with privately held assets.
Theorem 2: Let <p be a performance standard.
27
If <p is interun-implementable, then (p satisfies I-MON.
Proof: Choose rp,xp' G # such that there exists a CCMO, a with xp' = ipa(ip). By definition of interim-implementation, there exists a game T = {TV, M, £} such that for
By definition of interim-implementation, there exist s' G S and f = £o s' o I such that (s',f(if>')) G E(r,i/>') and /(i/>') G ¥>(V>')- Thus, for all i G TV, for all pj € Ri(ip'), for all 5" G Si, the following is true:
£o(5>/t,y_to/_0e£L,(/|p;). [1]
Next, suppose that for all i G TV, for all pi G Ri(ip), for all </ G EL,(f | It(ip')), the following holds:
^o^G^L,(/o^a|^)- [2]
Given [1] and [2], for all z G TV, for all />; G Ri{tp) and all 5" G 5,, the following holds: € ° W o /„5'_, o /_,-) o 0° G BL,-(/ o rpQ I Pi). [3]
By definition of a, for all i G TV, for all ip* G 7,(0), It{ipQ{*P*)) = a,-(/,-(V>*)). For all i G TV, let 5{ = 5'j o cti. By definition of Interim equilibrium, we conclude from [3] that (s,f(4>a(ip)) G E(T,tp). By definition of interim-implementation, f(ipa(ip) G ^(V7)- By construction, f(tp°(tp)) = /(*/>'). This proves that y> satisfies I-MON. Q.E.D.
Theorem 3: Let ip be a performance standard and let | TV |> 3. If ip satisfies I-MON, then cp is interun-implementable.
Proof: The conclusions of this theorem follow from Lemma 1 and Lemma 3. Q.E.D.
Corollary to Theorems 2 and 3: Let ip be a performance standard and let I TV |> 3. <p is interun-implementable if and only if <p satisfies I-MON.
28 6. Concluding Remarks
(i) In this paper, we have concentrated on an application of Interim equilibria to the problem of implementation of economic performance standards by an uninformed social planner. The class of games we have studied are such that existence of Interim equilibria is ensured. The question of whether there is a general list of conditions under which the set of Interim equilibria is non-empty is open. An investigation of this question will shed light on the other applications of this concept.
(ii) I-MON is clearly a fairly complicated condition. The catch is that not only is it sufficient for interim-implementability, it is also necessary. In Chakravorti Q 2_ }, I discuss the limits of implementability using this condition. An interesting question would be to study circumstances under which there are standards which do satisfy this condition.
(iii) To a certain extent, the NRS assumption can be relaxed. Instead of using t/> to denote a single state, let it be a class of states such that a social planner who has access to everybody's private information cannot distinguish between any of the states in xp. A performance standard 9 would then specify a non-empty subset of A for every xp 6 *£ such that every allocation in <p{xp) is (/'-optimal no matter which state in xp is realized. Given this formulation, the rest of our analysis would follow. Obviously, this makes the assumption of non-emptiness of f(xp) an even stronger one. The strength of this formulation is that it provides us with a model of mechanism design for environments with external sources of uncertainty.
(iv) A significant strength of our results is that they do not use the restrictive as- sumption of Non-exclusivity of Information: for all 0 e *£, for all 1 € N, r\}<=N\{i) Ij(7P) = \ip}. This makes the previous attempts at characterizing implementability inapplica-
29
ble to most situations that are of interest to economists. (Palfrey and Srivastava ( 2-4 ) have weakened this assumption to some extent.) Thus, by using this new concept of equilibrium, together with the formulation suggested in (ii) above, the issue of mecha- nism design can be discussed in a truly general framework of asymmetric information.
Appendix (Proofs of Lemmata)
The following notational convention will be used: Vi G N,\/si G .S,-,V7r, G II,-, let s*(7r,), sf(7rt), s?(7r,), s*(7Tt) denote, respectively, the projection of 5, (x;) on II,-, II,-+i, F and (5, 10]. Also, Vi G JV, let a, = s, o /,.
Proof of Lemma 1: Choose ip G $ and f £ <p. To show that f{xp) G EA(Q((f),fp), we need to show that there exists 5 such that (s,f(tp)) G E(Q((p),ip). Construct s as follows (see Remark 4 below): For all i G TV, for all tt; G II;,
(a)-si(7rf) = JT,-.
(&)*?(*,■) = JI+1(^),5J(7r,) = /,*}(*,) = 10.
For all i G JV, let m, = cr ,(*/>)). It may be checked that for all i G N,m-t satisfies Property 7 | t. Also, for all i G iV, f(i) = f and 0*(m) = 0,(m_,) = {V'}. Therefore, Case 1 applies and £(m) = f(tp). Next, we shall establish that for all i G iV, for all </>' G /,(</>), ^-.('/'') satisfies Property 7 | i and 0t(a_t(r/;')) = 0*(<r(^')) = {xp'}.
Given that agent i — l's strategy is 5,_i, agent z knows that for all 7T,-! G IIt-i, agent i - l's message contains s^^n^i) = /<(*/>)• Choose rp' G /,(0). Agent 1 knows that for all ; G iV\{z}, aJ-OW)) = Ij(tj)'). Thus, given (a) and (b) above, agent i can conclude that for all xp' G lt{ip),0-t{tp') satisfies Property 7 | i with 0,(<7_,(t/>')) = 0*(a(i>')) = {0'}. Given that s]{It(xP)) = / and sJ(/i(t/>)) = 10, for
30
all xp' E Ii(xp),s(I(xp')) is such that Case 1 is applicable. Thus, for all i E N, for all
Consider unilateral deviation by some z £ iV, to an arbitrary m\ E M, with s\{Ii{xp)) = ra(- = (7!"!(z),7rj-+1(i),/'(z),6'(z)). We shall consider the possible outcomes that agent i can expect given that for all xp' E Ii(xp),a-i(xp') satisfies Property 7 | t. Choose xp1 E Ii{xp). We need to consider the following possibilities:
(i) f'(i) = f, in which case either Case 1 applies or Case 2 applies and £,-(mj-, cr_j(0')) E {fi(xp'), 0}- Note that Case 4 does not apply since <7_,(t/>') satisfies Property 7 | z.
(ii) f'(i) ^ f- Then Case 3 applies and &(m{,<r_t-(^')) E {/-(O(^')i 0}.
To check whether (s,f(xp)) E E(Q(ip),xp), we would need to show that for all P« E Ri(ip), f°r all s(- E S,, the following holds:
to(s,ioIu<T-i)eELi(f\pi). [4]
Given the construction of s, for all xp' E /l(V,)5 f°r aU J € 7V\{z}, ^(/y^')) = /• Therefore, given that z knows that all j E iV\{z} are playing strategy s_;, i knows that (i) and (ii) are mutually exclusive.
Let g : $ — ► A be a function defined such that for all xp' E Ix(xp),g(xp') = 0. Given strict monotonicity of preferences, any linear combination of utilities obtainable from the rules / and g is weakly dominated by the expected utility to agent i from the rule /. Thus, in the case of possibility (i), regardless of his/her probability distribution on *£, agent i is no better off.
By definition of /;, for all xp' E U{xp), Rt{ip) — -^i(V,/)- Agent i can determine with certainty whether Case 3A or 3B is applicable in the case of possibility (ii) by choosing /'(*) and S'(i) appropriately. If agent 1 chooses Case 3B, by strict monotonicity of preferences he/she is no better off. If 1 chooses 3A, by definition, for all xp' E U{xp),
31
for all pi £ Ri(tp) = Ri(rj>'), f'(i) G ELt{f | pt). Again i is no better off.
Since this argument holds for all i £ N, we have f(ip) £ E A{Q {<p) , xp) . Q.E.D.
Remark J,: It should be noted that the when the strategy 5 is played it does not mean that agents know the "true" information sets of their neighbors. In the equilibrium constructed in the proof above, each agent picks an event from his/her neighbor's partition at some point in the iterative process. The event that each agent picks happens to be the true information set for the neighbor. Secondly, note that s,- is II,- measurable for all i. Corresponding to each state xp we have a different Interim equilibrium list of strategies. The construction of 5 in Lemma 1 clearly requires that for all xp' £ xp, if s G Es(Q{ip),xp) then s £ Es(G(<p),rp'). Observe that such a construction was possible since our equilibrium concept is Interim equilibrium and not Bayesian equilibrium. A Bayesian equilibrium strategy list is state-independent since it is the result of an ex ante calculation.
Proof of Lemma 2: By Lemma 1, given that for all xp £ ty,(p(xp) ^ 0, there exists m £ M satisfying the hypotheses of Lemma 2 such that Case 1 is applicable. We need to show, therefore, that there cannot be an m satisfying the hypotheses of Lemma 2 such that either of the Cases 2, 3 or 4 are applicable.
For all i £ N, let m, = (7rt(i),7Ti+1(i),/(i),^(z)). Consider an alternative strategy for agent i, *J(^W) = ™>\ such that m\ = «(t), 7rJ+1(t), /'^), S'(i)) with (x{(0, *'t + l(t), /'(0) (7rt(i),7rt+1(z), /(;)). S'(i) is such that for all j <= N\{i}, for all*,- G ttj,S'(i) < *j(*j)- This choice of strategy guarantees that for all xp' £ Ix(xp),K{m'i,a-l(xl)')) = {{}.
We shall establish that if Case 1 is not met by m, then for at least one i G N, the following strict inequality holds:
£,('»>_,(</•)) >6KV0) [5].
32
Consider the different possibilities in case there is m is such that either Case 2 or 3 or •1 applies:
(i) m is such that Case 2 is applicable for j . Consider the two possibilities:
(i)a. If Case 2A is applicable, then there exists j £ N such that A'(rn) = {]}. Therefore, for all i £ N\{j},m-i does not satisfy Property 7 | i. Choose i £ N\{j}. By construction of mj, Property 7 | j is not satisfied either by replacing m; with m^- in the list m_7. By Rule 4A, £;(m[-,<7_,(i/>)) = Q.. Since | N\{j] |> 2, there exists i £ N\{j} such that £,(m) < ft. Thus, [5] holds.
(i)b. If Case 2B is applicable, £(m) = 0. There exists i £ N with (m(-,m_t) such that Case 2A applies. By assumption, for all /£(/?, for all xj)' £ ty,f(xp') ^ 0. Thus, we conclude that [5] holds.
(ii) m is such that Case 3 is applicable. Then for some A: £ N,f(k) ^ f(k — 1). Therefore, for all i £ N\{k}, m_{ does not satisfy Property 7 | z. The arguments given in part (ii)a. would then apply.
(iii) m is such that Case 4 is applicable. Consider the two possibilities:
(iii)a. If Case 4A is applicable, then there exists j £ A^ such that K(m) = {j}. Therefore, for all i £ N\{j},m-i does not satisfy Property 7 | i. Choose i £ N\{j}. By construction of m\, Property 7 | j is not satisfied either by replacing m, with m[ in the list m_;. By Rule 4A, £,(m;,<7_,(0)) = SI. Given that K{m) / {i} we have Zi(m) < ft. Thus, [5] holds.
(iii)b. If Case 4B is applicable, £(m) = 0, and given that K{m'i,0-l{\l))) = {j}, [5] would hold.
Thus, we have shown that if there is m such that Case 1 does not apply, then, given strict monotonicity of preferences, for at least one 1 £ N , there exists s't £ 5,
33
such that for pt = {0} G Ri{xl>), EUt{i o {s\ o /t,s_, o /_,-) | Pl) > EU{{i osoI\ pt). This contradicts the hypothesis that s G Es(Q{^>),^)- Q.E.D.
Proof of Lemma 3: Choose ip G $ . Let s G Es{Q{^>)^) with s(I(ip)) = m = (irt(i),7Ti+l(i),f(i),6(i)). For all i £ N, let a; = st-. By Lemma 2, m is such that Case 1 is applicable. Thus, d*(m) ^ 0 and a is a CCMO with 0m(m) = ^{rp). Since Case 1 applies, there exists f £ <p such that for all i G N,f(i) = f and f(m) = f(xpa(xp)). We need to show that /(^(VO) € vKVO-
Let V' = </>a(V0- We shall show that for all i G N, if for all pj- G iW), 2 G £Li(/ | p\), then for all p{ G #,(</>), $r o ^a G ££,-(/ o V>Q | /?,)• Choose i G N and let <7 G EL{(f | p^) for all p\ G Ri(tp') such that g ^ f. Suppose agent i were to switch to m'i = (irt(i),Trt+1(i),g,8'(i)), where £'(i) is such that for all j G N\{i}, for allTr, G II,-,£'(i) <^(ttj).
By the definition of Case 1, 6*(rn) — 0,(m_;) = {tp1}. By Case 3A, given that for all xp" G #,tf(m'.,<7_,-(V>")) = {i} and g G ££,-(/ | ^J) for all p\ G fl^'UK,™-.') = g(ip'). Agent i's initial information set is Ii(ip). By definition of a, for all xp" G UW,ELx{f | Ii(il>a(rl>")))=ELi(f | /.(</>')). Thus, for all tf" G /,(</>), 6(m„a_t(^")) fi(rpa(ip")) and ^roj, a_f(</>")) - gi(1>a(ip")). Given that s G Es{G{s>\rl>), we con- clude that for all pt G R,{ip), g o t/>a G ££,(/ o z/>a | />,)• This holds for all i G Ar. By I-MON, we conclude that f{xpa{xp)) G <p(xp). Q.E.D.
34
REFERENCES
1 AUMANN, R.: "Agreeing to Disagree," Annals of Statistics,* (1976), 1236-1239.
CHAKRAVORT1, B.: "On the Impossibility of Efficiency and Equity in Economics with Asymmetric Information," mimeo University of Rochester, 1987.
3 DASGUPTA, P., P. HAMMOND AND E. MASKIN: "The Implementation of Social Choice Rules: Some General Results on Incentive Compatibility," Review of Economic Studies, 46(1979), 185-216.
4 D'ASPREMONT, C. AND L.-A. GERARD-VARET: "Incentives and Incomplete Information," Journal of Public Economics 11 (1979), 25-45.
5. DEMSKI, J. AND D. SAPPINGTON: "Optimal Incentive Contracts with Multiple Agents," Journal of Economic Theory, 33 (1984), 152-171.
6. GREEN, J. and J.-J. LAFFONT: "Posterior Implementability in a Two-Person Decision Problem," Econometrica 55 (1987), 69-94.
7. GROVES T. AND J. LEDYARD: "Optimal Allocation of Public Goods: A Solution to the Free-Rider Problem," Econometrica, 45 (1977), 783-810.
8. HARRIS, M. AND R. TOWNSEND: "Resource Allocation under Asymmetric Informa- tion," Econometrica, 49 (1981), 231-259.
9. HARSANYI, J.: "Games with Incomplete Information Played by 'Bayesian' Players," Management Science, 14 (1967-68), 159-189, 320-334, 486-502.
10. HOLMSTROM B. AND R. MYERSON: "Efficient and Durable Decision Rules with Incomplete Information," Econometrica, 51 (1983), 1799-1820.
1 I. HURWICZ, L.: "On Informational^ Decentralized Systems," in Decision and Organiza- tion, T. McGuirc and R. Radncr (cds.). North-Holland, Amsterdam, 1972.
12. HURWICZ, L. (1979a): "Outcome Functions Yielding Walrasian and Lindahl Alloca- tions at Nash Equilibrium Points," Review of Economic Studies, 46 (1979a), 217-225.
35
13. HURWICZ, L.: "On Allocations Attainable through Nash Equilibria," Journal of Economic TJieory, 21 (1979b), 140-165.
14. HURWICZ, L.: "Incentive Aspects of Decentralization," in Handbook of Mathematical Economics vol. Ill, K. Arrow and M Intrillgator (eds.) North-Holland, Amsterdam, 1986.
15. LAFFONT, J.-J. AND E. MASKIN: "The Theory of Incentives: An Overview," in Advances in Economic Theory, W. Hildenbrand (ed.), Cambridge University Press, Cam- bridge, 1982.
16. MASKIN, E.: "Nash Equilibrium and Welfare Optimality," mimeo M.I.T., 1977.
17. MASKIN, E.: "Theory of Implementation in Nash Equilibrium: A Survey" in Social Goals and Organization, L. Hurwicz, D. Schmeidler and H. Sonnenschein (eds.) Cam- bridge University Press, Cambridge 1985.
18. McKELVEY, R.: "Game Forms for Nash Implementation of General Social Choice Correspondences," mimeo California Instututc of Technology, 1986.
19. MILGROM P- "Rational Expectations, Information Acquisition and Competitive Bid- ding," Econometrica, 49 (1981), 921-943.
20. MYERSON, R.: "Incentive Compatibility and the Bargaining Problem," Econometrica, 47(1979), 61-74.
21. MYERSON, R.: "Bayesian Equilibrium and Incentive Compatibility: An Introduction," in Social Goals and Organization, L. Hurwicz, D. Schmeidler and H. Sonnenschein, Cam- bridge University Press, Cambridge, 1985.
22. PALFREY, T. AND S. SRIVASTAVA: "Implementation and Incomplete Information," mimeo Carnegie-Mellon University, 1985a.
23. PALFREY, T. AND S. SRIVASTAVA: "On Bayesian Implementable Allocations," mimeo Carnegie-Mellon University, 1985b. forthcoming in Review of Economic Studies.
36
24. PALFREY, T. AND S. SRIVASTAVA: "Implementation with Incomplete Information in Exchange Economics," mimco Carncgic-McIIon University, 1986.
25. POSTLEWAITE, A. AND D. SCHMEIDLER: "Implementation in Differential Infor- mation Economics," Journal of Economic TJieory 39 (1986), 14-33.
26. REPULLO, R.: "Implementation by Direct Mechanisms under Incomplete Information," mimco London School of Economics, 1983.
27. ROSENTHAL, R.: "Arbitration of Two-Party Disputes under Uncertainty," Review of Economic Studies, 45 (1978), 595-604.
28. SAVAGE., L.: The Foundations of Statistics, Wiley, New York, 1954.
29. SCHMEIDLER, D.: "Walrasian Analysis via Strategic Outcome Functions," Econome- trica 48 (1980), 1585-1594.
FOOTNOTES
1. It is common knowledge that once an equilibrium is reached, every agent is committed to computing a message using his/her component of the equilibrium list of strategies. It is assumed that such a commitment can be enforced.
State G (0.25)
State B (0 75)
rri2 m? m2
rri2 nri2
rri2
™1 mi
|
0, 4 |
0, 2 |
0, 0 |
|
1, 4 |
2, 6 |
0, 0 |
|
0, 0 |
0, 0 |
1. 2 |
m1
|
1, 2 |
0, 1 |
0, 0 |
|
0, 4 |
1, 3 |
0, 0 |
|
0, C |
0, 0 |
1. 2 |
Figure 1
F
F .7-
|
State 4>' (0.75) |
State i>* (0.25) |
||||||
|
m1 |
m2 t»2' rri2" |
m1 ml' |
m2 m2 1T12" |
||||
|
1. 1 (a) |
0, 3 (b) |
0, 4 (c) |
8, 3 (a) |
0, 2 (b) |
0, 0 (c) |
||
|
0, 2 (d) |
2, 3 (e) |
3, 0 (0 |
0, 10 (d) |
1. 4 (e) |
0, 0 (0 |
||
|
F |
gure |
2 |
F
|
State \p' (0. |
75) State ty* (0.25) |
|||||
|
(V. i>*) |
1, 1 (a) |
2, 3 (e) |
w. r) |
8, 3 (a) |
1, 4 (e) |
|
|
Figure 3 |
F-4-
|
State V (0.75) |
State i)* (0.25) |
||||||
|
m (**) |
(40 (**) |
||||||
|
W. i>*) |
2. 3 (e) |
1, 1 (a) |
(*'. **) |
1. 4 (e) |
8, 3 (a) |
||
|
Figure |
4 |
FIGURE 5
Let m = (TTj(i), TT( + 1(i), f(i). 6(i)),eN
Case 1:
Vi 6 N, (i) 3f 6 <|> f(i) = f, (ii) 6(i) = 10 and (iii) 0j(m_j) = 0*(m) * 0.
C(m) = f(6*(m))
F-5
Case 2:
(i) 3f 6 4> such that Vj 6 N, f(j) = f, (ii) 3i 6 N such that m_j satisfies Property y\\ and (iii) the conditions for Case 1 are not all met
Case 2A
K(m) = {i}
Case 2B
Otherwise
t
5(m) = f(ei(m_i))
C(m) = 0
Case 3:
3i 6 N such that (i) f(i) f f(i-l) 6 4> and (ii) m_j satisfies Property y|i.
Case 3A
(i) VPi 6 RjOjtm-j)), f(i) 6 ELj(f(i-1) I Pi) and (ii) K(m) = {i}
V
5(m) = f(i)(91(m_i))
Case 3B
Otherwise
V £(m) = 0
Case 4:
Otherwise,
Case 4A
3i 6 N with K(m) = {i}
(Cj(m), £_j(m)) = (fl. 0)
Case 4B
Otherwise
£(m) = 0.
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
HECKMAN
BINDERY INC.
JUN95
r N. MANCHESTER.' Bound -To -l'l«-v ,NDIANA46962_