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_