(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "The theory of implementation in Nash equilibrium : a survey"

Digitized by the Internet Archive 

in 2011 with funding from 

Boston Library Consortium IVIember Libraries 



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



working paper 
department 
of economics 



The 


Theory of 


Imp lementation 


in 


Nash 


Equilibrium: 






A 


Survey 














Eric 


S. Maskin 










Number 333 










October 


1983 



massachusetts 
institute of 

technology 

50 memorial drive 
Cambridge, mass. 02139 



The Theory of Implementation in Nash Equilibrium: 
A Survey 

Eric S. Maskin 
Number 333 October 1983 



D11 



The Theory of Implementation in Nash Equilibrium:/ 

A Survey- 



Eric S. ^skin 
MIT 



To appear in Social Goals and Social Organization: Volume in Memory of 
Elishe Pazner, Cambridge University Press. 



June, 1985 



Revised October, 1983 



Financial support from the KSF and the A. P. Sloan Foundation is gratefully 
acknowledged. I wish to thank David Schmeidler and Hugo Sonnenschein for 
helpful comments. 



The Theory of Implementation in Nash Equilibrium: A Survey 

The theory of implementation concerns the problem of designing game 
forms (sometimes called "mechanisms" or "outcome functions") the equilibria 
of which have properties that are desirable according to a specified 
criterion of social welfare called a social choice rule . A game form, in 
effect, decentralizes decision-making. The social alternative is selected 
by the joint actions of all individuals in society rather than by a central 
planner. 

Formally, a social choice rule assigns a set of alternatives to each 
profile of preferences (or other characteristics) that individuals in 
society might have; the set consists of the "welfare optima" relative to the 
preference profile. A game form is a rule that specifies an alternative (or 
outcome ) for each configuration of actions that individuals take. A game 
form implements (technically, fully implements) a social choice rule if, for 
each possible profile of preferences, the equilibrium outcomes of the game 
form coincide with the welfare optima of the social choice rule. Of course, 
the equilibrium set depends on the particular solution concept being used. 
Implementation theory has considered a variety of solution concepts, 
including equilibrium in dominant strategies, Bayesian equilibrium, and Hash 
equilibrium. Other chapters of this volume treat the first two equilibrium 
concepts. In the .main, this article is confined to implementation in Nash 
equilibrium, although it relates this theory to those of other solution 
concepts, dominant strategies in particular. 

Nash equilibrium is the noncooperative solution concept par excellence , 
and so it is not surprising that implementation theory should have employed 
it extensively. Nonetheless, one reason often advanced for the desirability 



of decentralization is that information is incomplexe, and so it may seem 
strange to use a solution concept of complete information (I am 
distinguishing here between Mash equilibrium in its original sense, c.f. 
Nash (1950), and the incomplete information extension due to Harsanyi 
(1967), commonly called "Bayesian equilibrium"). There are at least three 
alternative justifications for so doing. 

First, as the work of Hurwicz (1972) and Groves and Ledyard (1977) at 
least implicitly assumes , a Nash equilibrium can be viewed as a stationary 
point of an iterative adjustment process. In such a process, players may 
have incomplete information but continually revise their actions imtil a 
point is reached where unilateral deviation no longer pays. Such a point is 
a Nash equilibrium- 
There are several difficulties with this interpretation. If an 
individual believes that others play "naively" in the sense of always 
adjusting their actions optimally, assuming that the distribution of current 
actions will continue to prevail, then it will, in general, pay him to act 
as a Stackelberg leader and allow others to adapt to an action that he does 
not adjust. But if one or more players attempt to behave as Stackelberg 
leaders, there is no longer any reason to suppose that a stationary point of 
the process is a Nash equilibrium. 

There are two cases where we might be able to rule out such Stackelberg 
behavior. One is where society is sufficiently large so that one 
individual's effect on others is slight enough as to have no appreciable 
effect on their actions. In that case, the individual would best play in 
"Hash-like" fashion (see, for example, Roberts and Postlewaite (1976)). The 
other is where the individual believes that any given iteration is the last 
(at least with very high probability), in which event, from his perspective. 



there is no opportunity for influencing future behavior. 

Clearly, though, these cases are highly restrictive. When they do not 
apply, we cannot expect naive behavior. But if all individuals are 
"sophisticated" then each must realize that, when adjusting his action, he 
may affect others' (probabilistic) beliefs about his preferences. Since 
these beliefs, in turn, may affect their behavior, individuals may, again, 
be induced to behave in a non-Nash-like way. 

The second reason for using Nash equilibrium is more satisfactory game 
theoretically. There are many circumstances where the planner (game form - 
designer) can be thought of as having highly incomplete information, whereas 
individuals themselves are well-informed. For example, the individuals may 
be firms that are experts in research and development and know a great deal 
about each other, whereas the planner may be the government, who knows next 
to nothing about R&D but wants to influence firms' behavior. Alternatively, 
the planner might be a "constitution-designer," who must devise the 
procedural rules (the game form) by which committee members make decisions 
long in advance of any particular application. Indeed, the planner may not 
literally exist as a physical entity; rather he may simply stand for the 
committee as a whole. But, by the time, any particular decision has to be 
made, committee members may be well aware of each other's preferences. 

In either of these two examples, Hash equilibrium is the appropriate 
solution concept. • It is important in the examples that individuals have 
good information about each other; otherwise, Bayesian rather than Hash 
equilibrium pertains. It is equally necessary that the planner have poor 
information; otherwise, he could simply impose a welfare optimal social 
alternative by fiat. 



Finally, implementation in Nash equilibrium may be thought of as a 
positive theory. To the extent that the theory can characterize the set of 
implementable social choice rules, it can predict the kinds of outcomes that 
can rise as equilibria of already existing (complete information) games. 

This article is divided into nine sections. The first introduces 
notation and the basic concepts. The second presents the fundamental 
theorem characterizing the set of implementable social choice rules. This 
theorem is cast in terms of two properties, monotonicity and weak no veto 
power. Section 3 discusses the so-called "revelation principle" with 
respect to implementation in Nash equilibrium and several other equilibrium 
concepts. We clarify the relevance for Nash implementation of the 
principle, as usually stated, and propose an alternative formulation. 
Section 4 discusses the connection between implementability and several 
common properties of social choice rules, viz., weak no veto power, 
neutrality, and individual rationality. Section 5 exposits the relationship 
between Nash and dominant strategy implementation. Section 6 treats 
implementation in a much-studied special case, where preferences are of a 
"quasilinear" form. 

Through Section 6, all analysis assumes noncooperative behavior on the 
part of individuals. Section 7, however, allows for collusion and studies 
implementation in strong equilibrium. Section 8 considers an implementation 
concept, double implementation, that accommodates both noncooperative and 
cooperative behavior simultaneously. Finally, Section 9 briefly discusses 
two concepts related to Nash implementation. 
1 . Notation and Basic Concepts 

Let A be a set of social alternatives (A can be either finite or 
infinite). A utility function, u, on A is a real-valued function 



u: A -^ R, 
where R denotes the real numbers. Let U. be the set of all utility- 
functions. For each i ■= 1,...,n, let U. be a subset of U . . Then, an n- 
person social choice rule (SCR) on (U,,...,U ) is a correspondence 

f : U,x. ..xU ■»■ A.^ 

1 n 

For any profile (u,,...,u ) of utility functions, one interprets 
f(u. ,...,u ) (sometimes called the choice set and which we assume to be 
nonempty) as the set of welfare otpimal alternatives. Common examples of 
social choice rules include the Pareto correspondence, which selects all 
Pareto optima corresponding to a given profile, and the Condorcet 
correspondence, which selects all alternatives for which a majority does not 
prefer some other alternative. Notice that, in principle, we allow the SCR 
to select two different choice sets for two utility profiles that correspond 
to the same preference orderings. That is, the choice set may depend on 
cardinal properties of utility functions. This flexibility will be 
eliminated below when we discuss implementation. However, our formulation 
enables the ordinal nature of an implementable SCR to be proved (albeit 
trivially) rather than postulated. 

Given action spaces S. ,...,S for each individual, an n-person game 
form g is a mapping 

g: S.X.. .xs ->■ A. 

^ 1 n 

If individuals 1 through n play the action configuration (s.,...,s ), the 
outcome is alternative g(s,,...,E ). 

For a game form g, let NE (u. ,...,u ) be the set of Nash equilibrium 

& I 11 



■'■ In this chapter we shall suppose throughout that preferences alone 
constitute the relevant data about individuals. See the chapter by 
Postlewaite in this volume for a treatment that allows for other information 
(e.g., endowments) as well. 



outcomes corresponding to the profile (u , ...,u ). Slightly diverging from 
the terminology of Dasgupta, Hammond, and Maskin (1979), we shall say that 
the game form g weakly implements the SCR f in Nash equilibrium if, for 
every (u^,...,u^) e U^x..,xU^ 

(1) NE (u,,...,u ) is nonempty 

(2) NE (u.,...,u )Cf(u.,...,u ). 

g 1 n — 1 n 

Thus, if g weakly implements f, an equilibrium always exists, and all 

equilibria lie in the social choice set. 

Requirements (l) and (2) are, by now, the standard requirements in 

Nash-implemenxation theory. We shall see below, however, that the analogue 

of (2) is not always imposed in the corresponding theories for other 

solution concepts. 

If for all (u. ....jU ) c U.X...XU and all a c f(u<,...,u ) there 
1 ' n 1 n ^ 1 ' ' n 

exists a game form g that weakly implements f and for which 

a e NE (u, ,...,u ), then we say that f is implementable (in Nash 

equilibrium). The difference between weak and ordinary implementability is 

that the latter requires every element of every choice set to arise as a 

Hash equilibrium of some implementing game form. An ostensibly still 

stronger requirement is that a single game form yield all these equilibria.' 

We shall say that the game form g fully implements the SCR f if for all 

(u^,.-.,u^) E U^x...xu^, 

(3) NE(u^,...,u^)' = f(u^,...,u^). 

We shall see below (Section 4) that, in fact, implementability and full 

implementability are equivalent. 

2. The Fundamental Characterization Theorem 

To characterize those SCR's that are implementable, we must first 

define two properties of SCR's. We shall argue that the first of these is 
in many circumstances extremely weak. 



7 
Weak No Veto Pover : An SCR f sat^-sfies weak no veto power if, for all 

(u u ) e U,x...xU and a e A, a e f(u. ,...,u ) whenever there exists i 

^ 1 n 1 n I n 

such that for all i * ± and all b e A u.(a) _> u (b). 

In words, an SCR satisfies weak no veto power if whenever all 
individuals except possibly one agree that an alternative is top-ranked - 
i.e., no other alternative is higher in their preference orderings - then 
that alternative is in the social choice set; the remaining individual 
cannot veto it. The hypothesis that the alternative be top-ranked is what 
distinguishes this property from other no veto conditions and what makes it 
so weak. Indeed, in many circumstances the hypothesis cannot be satisfied 
at all. Suppose, for example, that we equate a social alternative with an 
allocation of goods across consumers. Assume also that at least one of 
these goods is a divisible private good that all individuals find desirable. 
Then no two individuals will agree that any given alternative is top-ranked, 
since each would like all the private good to himself. Thus if there are at 
.least three individuals, our weak no veto power condition is satisfied 
vacuously. 

Our other condition is considerably stronger, although quite standard. 
It sometimes goes under the name "strong positive association" (see Muller 
and Satterthwaite (l977) and Moulin and Peleg (1982)). 

Monotonicity : An SCR f is monotonic if, for all (u. , . . . ,u ), (u. ,...,u ) e 
U. X...XU and a z ^, a z f (u. , — ,u ) whenever (i) a e f (u. , . . . ,u ) and, 
(ii) for all b e A and i, u.(a) >_ u.(b) implies u.(a) >_ u.(b). 

In words, an SCR is monotonic if, whenever an alternative a is in the 
choice set for a profile of preferences, and then those preferences are 



8 

altered in a way such that a does not fall in anyone's preference ordering 

relative to any other alternative, it remains in the choice set. 

Clearly, monotonicity is a purely ordinal property, and an SCR that 

satisfies it will reflect only ordinal properties of utility functions. 

That is, if, for all i, u. = h. o u. , where h. : R ->■ R is strictly 

increasing, then a monotonic f satisfies f(u,,...,u ) «= f(u,...,u ). Thus 

1 n n 

monotonicity rules out the interpersonal comparisons inherent in, say, 

utilitarianism or the Rawlsian difference principle. Moreover, as we shall 

see below (see section 5), it amounts to something very close to 

independence of irrelevant alternatives in the sense of Arrow (1951 )• 

Nonetheless it is satisfied by such common SCR's as the Pareto and Condorcet 

correspondences and, in economic contexts, by the correspondence that 

selects core allocations. 

Monotonicity does not require that all Pareto optimal alternatives be 

in the choice set (the Condorcet correspondence is a covmterexample) , but, 

if f is onto A, it does imply that a subset of Pareto optimal alternatives 

is in the choice set, namely, those that are top-ranked by all individuals: 

LeTTiTTip 1 : Suppose that f is monotonic and onto A. For any (u, ,...u ) e 

U.>'...xU and a e A if, for all b and i, u.(a) > u.(b), then a e 
1 n '2.-2. 

f(u^ ,...,u^). 

Proof : Because, by assumption, f is onto A, there exists (u-,...,u ) e 

Ux.-.xU such that a c f(u, ,...,u ). If, for all i and b, u.(a) > u.(b), 
1 n 1 n 1—1 

then, from monotonicity, a t f(u', ,...,u ). 

Q.E.D. 



We can now state the fundamental characterization result. 
Theorem 1 : (Maskin (1977)): Suppose that f is an n-person SCR. If f is 
implementable in Nash equilibrium, then it is monotonic. Furthermore, if 
n > 3 and f satisfies weak no veto power and monotonicity, then it is fully 
implementable . 
Proof : To see that implementability implies monotonicity, suppose that f is 

not monotonic. Then there exist (u.,...,u ) and (u,,...,u ) e U, x. . . xU and 

in 1 n 1 n 

a E A such that a c f(u,,...,u ) and, for all b e A and all i, 

In 

(4) u^(a) >_ u^(b) implies u^(a) >_ u^(b) 
but 

(5) a / f(u^ , .. -fU^) . 

Now, if f is implementable, there exists a game form g: S, >«...xS ->• A and a 
configuration of strategies (s*,...,s*) such that g(s*, . . . ,s*) = a and 
(s*,...,s*) is a Nash equilibrium for profile (u.,...,u ). But from (4), 
(Et,...,s*) is also E Hash equilibrium for (u>,...,u ), which, in view of 
(5), contradicts (2). Hence, f is not implementable. 

Ve only sketch the proof that weak no veto power and monotonicity imply 
that f is fully implementable. For the omitted details see Maskin (1977). 
For any a e A and u. e U. let 

L(a,u.) = {b E A|u.(a) >_ u.(b)}. 

L(a,u. ) is the lower contour set of u. at a, i.e., the set of alternatives 
1 1 

that someone with 'utility fxinction u. does not prefer to a. For each i, let 

(6) S^ = {(u^ , . . . ,u^,a) I (u^ , .. . ,u^) E U^x.,.xU^ and a e f(u^ , .. . ,u^) } . 



10 



That is, each player's action consists of announcing a profile of utility- 
functions and an alternative that is in the choice set with respect to that 
profile. Define g: S.x...xS -^ A so that: 

(7) if s^ ■= ... = s^ = (u^ ,.. .,Uj^,a), then g(s^,...,s^) = a; 

(8) if B . = (u.,...,u ,a) for all 2*1, then 
{b c A|b = g(s^,7_^), s^ e S^} «= L(a,u^)2 

and 

(9) if, for given i, there exist j and k, with j ^ i * k, such that "b .t "b , 
then 

{b z A|b = g(s^,B_^), 8^ E S^} = A. 

That there exist game forms satisfying conditions (6)-(9) is demonstrated in 

Maskin (1977). ¥e claim that any such game form fully implements f. 

To see this, first choose (u<,...,u ) e U, >^. . . xU and a e f(u<,...,u ). 
' 1 n 1 n 1 n 

From (7), if all individuals take the action (u, ,...,u ,a), the outcome is 

1 n 

a. Furthermore if (u,,...,u ), in fact, are individuals' utility functions, 

then, from (8), each individual cannot obtain an alternative he prefers to a 

by varying his action unilaterally. Hence, all individuals' 

taking the action (u, ,...,u ,a) is a Hash equilibirum for the profile 

(u. , . . . ,u ). This establishes that for all (u. , . . . ,u ), f(u, ,...,u )^ 

NE^(u. ,...,u ). 
g 1 n 

To establish the opposite inclusion, suppose that (s,,...,e ) is a Nash 
equilibirum of g for the profile (u, ,...,u ) and that a = g(B>,...,E ). We 



■The notation "g(s.,s .)" is shorthand for g(E>,...,E. . ,s. ,e. _^. , • . . ,e ) . 



11 



must establish that a e f(u^,...,u ). There are three cases to consider: 

(a) s, " ... " s ; (p) there exist i and action s such that for all j ^ i 
s^. = s but B. * s; and (y) all other configurations. 

Consider case (a) first. Suppose that b. " (u.,...,u ,a) for all i. 
We have already observed that, from (7) and (8), g(s,,...,B ) *= a and that 
(s. ,...,B ) is a Nash equilibrium for the profile (u, ,...,u ). For any i 
consider b such that u.(a) _>. u.(b), i.e., such that b e L(a,u.). Prom (8) 
there exists s. e S. such that g(B.,E .) " b. Hence u.(a) >_u.(b); 
otherwise, s. could not be an equilibrium action for utility function u. , 
contrary to our assumption. Therefore, the hypotheses of the monotonicity 
condition are satisfied, and we conclude that a t f(u,,...,u ), as required. 

Kext, consider case (p). Suppose that, for all j * i, s. «= 

(u^,...,u ,a) and that s. t (u^,...,u ,a). Since, for each k * i, s, ^ b. 

and n >_ 5i (9) implies that, for all j * i and all b e A, there exists 

s. E S. such that g(s.,s .) = b. Hence, because (s.,...,s ) was assumed to 

be a Hash equilibrium for (u. ,...,u ), we can conclude that u.(a) _> u.(b) 

for all j '' i and all b e A. Our weak no veto power condition then implies 

that a E f(u, ,...,u ), as reauired. 
In 

Finally, in case (y), for all i, there exist j. and k, with j ;' i i^ k, 



12 



such that B. t s, . Hence, as in case (p), weak no veto power implies that 
a e f(u.,...,u ), completing the proof. 

Q.E.S. 

The proof of Theorem 1 is constructive. Given an SCR satisfying weak 
no veto power and monotonicity, we produce a game form that fully implements 
it. It may be helpful to summarize the construction in words. An action 
consists of announcing a profile of utility functions and an alternative 
that is in the choice set for that profile. Condition (7) says that if all 
individuals announce the same profile (u. ,...,u ) and alternative a, then a 
is the outcomme. Condition (8) says that if all individuals but one play 
the same action (u^,...,u ,a), then, by varying his action, the remaining 
individual can "trace out" the entire lower contour set corresponding to the 
utility function the others announce for him and to the alternative that 
they announce. Condition (9) stipulates that if, in a configuration of 
actions, two individuals' actions differ, then any third individual can 
trace out the entire set A by varying his action. 

As we have noted, the Pareto correspondence is monotonic Also, it 

obviously satisfies weak no veto power. Theorem 1 implies, therefore, that 

the Pareto correspondence is implementable for n 2. 3, even when the U.'s are 

unrestricted (i.e., equal to U.)- This result, however, does not obtain 

when n = 2, as Theorem 2 demonstrates. 

Pareto Optimality : An SCR f: U. x — xU ->• A is Pareto optimal if for all 

(u. ,...,u ) E UX...XU and all a c f (u, , — ,u ) , a is weakly Pareto optimal 
1 n 1 n In 

with respect to (u.,...,u ), i.e., there does not exist b e A such that, for 

all i, u. (b) > u. (a) . 

Dictatorship: An SCR f: U x...xU -*■ A is dictatorial if there exists an 
*- 1 n 



13 

individual i such that, for all (u. ,...,u ) e U. x.,.xU and all a e A, u.(a) 

I n 1 n 1 

>_u.(b) for all b e A if a e f(u.,...,u ). That is, an SCR is dictatorial 
if there exists an individual (the dictator) who always gets his way. 
Theorem 2 ; Let f: U. x U. -*• A be a two-person, Pareto optimal SCR. Then f 
is implementable in Nash equilibrium if and only- if f is dictatorial. 
Proof : See Maskin (1977) and Hurwicz and Schmeidler (1978). 

The hypothesis that the U. 's are equal to U is crucial to the validity 
of Theorem 2. As we shall see in Section 7, many two-person, Pareto 
optimal, and nondictatorial SCR's on restricted domains are implementable. 

Given a set of SCR's satisfying the hjrpotheses of Theorem 1, we can 
generate new implementable SCR's: 

Corollary to Theorem 1 : For n >_ 3, suppose that {f^jfj,-..} is a sequence 
of n-person monotonic SCR's. Then, if one of the f.'s satisfies no veto 

CD 

power (_/ f. is fully implementable in Nash eauilibrium, and if each of f.'s 
i=1 ^ * ^ 



satisfies weak no veto power (1 f. is fully implementable (assuming /O 

i=1 ^ 

f.(u. ,...,u ) is nonempty for all profiles) 



i=1 ^ i=1 



Proof: The proof simDly consists of verifying that [^ f. and /^ f. both 

i=1 ^ i=1 ^ 



satisfy monotonicity, that [^ f . satisfies weak no veto power if one of 

i=1 ^ 

CD 

f.'s does, and that^ .'_!. f. satisfies weak no veto power if all the f.'s do. 



14 



3. The Revelation Principle 

Let us temporarily broaden the idea of an SCR. Rather than limiting 
its domain to sets of utility functions, we shall define it to be a 

correspondence on 9, x...x0 where 0. is individual i's space of possible 

1 n 1 

"characteristics." A characteristic 9. not only describes i's preferences, 

but perhaps also his endowment, information about others, and whatever else 

might be relevant. 

Suppose that the SCR f: Q>x...x0 ->■ A is weakly implemented by a game 

form g: S.x...xS -*■ A according to some noncooperative solution concept. 

Thus we require the analogues of (l) and (2) to hold for the solution 

concept under consideration. Because the solution concept is 

noncooperative, we can write each individual's equilibrium action as a 

function st(e.) of his characteristic. Hence, for all profiles (9. ,...,9 ), 

(s*(9, ) , . . . ,s*(9 ) ) is an equilibrium. Now, define the induced game form 
linn 

g*: 0,x...xe -*■ A 
I n 

so that, for all (9,,..., 9 ), 

1 n 

e*(e^,...,9^) = g(s*(e^),...,s*(9^)). 

Notice , that for all (9.,..., 6 ), the actions (9,,..., 9 ) constitute an 

1 n 1 n 

equilibrium^ for the profile (9.,..., 9 ) and that, furthermore, 
g*(9,,...,9 ) E f(9,,...,9 ). This is the revelation principle (see Gibbard 
(1973), Dasgupta, Hammond, and Maskin (1979), Myerson (1979), (1982), and 
(1983) and the references cited in this last paper): the observation that 



^Actually this assertion is a bit too strong. It is true only for solution 
concepts that have the property that an individual's best action does not 
change when one deletes from the action spaces of other individuals all 
actions that are never equilibirum actions for any possible characteristic 
they might have. This property holds for dominant strategy, Bayesian, and 
Nash equilibrium, but not for, say, maximin equilibrium. However it does 
hold for a modified version of maximin equilibrium (see Dasgupta, Hammond, 
and Maskin (1979)). 



15 
if a game form implements an SCR, then there exists a "direct revelation" 
game form whose action spaces coincide with the characteristic spaces and 
which has the properties that (1 ) playing one's true characteristic is 
always an equilibrium action and (2) such a "truth-telling" equilibrium is 
in the choice set. 

Although the revelation principle is a useful technical device, we must 
stress that g* does not necessarily implement f. That is because, although 
g*(9,,...,9 ) is in the choice set for (G, ,...,G ), there may be other 
equilibrivim outcomes that are not, even if g (the original game form) does 
implement f. . 

Thus, we cannot conclude from the revelation principle that all one 
ever need consider are direct revelation game forms. Unfortunately, one may 
draw that incorrect conclusion from reading much of the literature on 
implementation in dominant and Bayesian equilibria. For the most part, this 
literature has implicitly used an implementation concept different from (the 
analogue of) (l) and (2), viz., namely "truthful implementation"** which 
requires only that the truthful equilibrium of a direct revelation game form 
be in the choice set. Although the connection between truthful and ordinary 
implementation has been (partially) elucidated for the case of dominant 
strategy equilibrium, almost nothing is known about it for Bayesian 
equilibrium. In any case, the Nash implementation theory is the sole 
implementation literature where much attention has been given to the issue 
of multiple equilibria.. Indeed that is the aspect that lends the literature 
interest, since for any SCR, it is extremely easy to contruct a direct 
revelation game form for which, for each profile, the truthful equilibrium 



^See Dasgupta, Hammond, and Maskin (1979), Laffont and Maskin ( 1982a), and 
Sections 5 and 6 below. ' 



16 



IS in the choice set. All we have to do is satisfy (7), which is possible 
for anj;; SCR. 

There _is, nonetheless, a version of the revelation principle that is 
consistent with our definition of Nash implementation. When Nash 
equilibrium is the solution concept, an individual needs to know not just 
his own preferences but the preferences of everyone else in order to 
determine his equilibrium action. Therefore, in the framework of Sections 1 
and 2, a characteristic of an individual is an entire profile of utility 
functions. Indeed, if instead we interpreted individual i's characteristic 
to be u. alone, we would, in effect, be requiring dominant strategies (see 
Theorem 7.1.1 of Dasgupta, Hammond, and Maskin (1979))- 

Notice that having individuals announce utility profiles is, 
essentially, what the game forms in the proof of Theorem 1 do (individuals 
also announce alternatives, but that is only because f may be multivalued; 
if f were single- valued, the strategy spaces could be taken to be 

U^x...xU ). Thus these game forms may be thought of as ones of direct 

I n 

revelation. Now, as we shall see in Section 4, not all implementable SCE's 

satisfy weak no veto power. Therefore, Theorem 1 does not quite completely 

characterize the set of implementable SCE's. Nevertheless, the kind of game 

form constructed in the proof, only slightly modified, is capable of fully 

implementing any SCE that can be implemented at all. Thus, in this sense, 

we need consider only a "canonical" class of SCE's. 

Suppose that f is an implementable SCR. For each i and u. e U. let 

N.(u.) = {a e A| there exists u . such that, for all j * i and all b e A, 

u.(a) > u.(b) but a i f (u, , . . . ,u )}. That is, the set K.(u.) consists of 
2—2 ' \ n 11 



17 



all the alternatives a that individual i can veto if he has utility function 

u. even if a is a top-ranked alternative for everyone else. Clearly, N.Cu.) 

is empty if f satisfies weak: no veto power. As in the proof of Theorem 1, 

let 

(6). S^ = {.(.U|,^. ..„,Uj^,a) |(u^ , .. .,Uj^) e U^x...xU^ and a e f (u^ , . . . ,u^) } . 

Define g: S x,..xs -»• A to satisfy (7), 

(8*) if s . = (u.,...,u ,a) for all i * 1, then 

{b E A|b = g(s^,B_^), s^ e S^} ■= L(a,u^) - K^(a,u^), 

where M.(a,u.) = {b e aI there exists u. e U. such that b e N.(u.) and u.(b) 
11 11 111 

>^u.(c) for all c e L(a,u.)}, and 

(9*) if, for given i, there exist j and k, with j ^ i ^^^ k, such that S. t 

S, , then 
k 

{b E A| b = g(s^,B_^), B^ E S^} = A - ?, 

where P = {a e aI there exists (u>,...,u ) such that u.(a) > u.(b) for all i 
' in 1—1 

and b but a / f(u. ,...,u )}. From Lemma 1, if a e P, then a is not in the 
/ ' n 

range of f. Therefore P is empty if f is onto A. To see that such a 
construction is possible, see Maskin (1977)- 

Condition (8*) says that if all individuals but i take the same action 
(u.,...,u ,a), then, by varying his action, i can trace out the lower 
contour set corresponding to u. and a except for those alternatives b for 
which there exists a profile (u^,...,u ) such that (a) b is top-ranked by 
all individuals other than i, (p) individual i (with utility funciton u. ) 



18 
prefers b to all alternatives in the lower contour set corresponding to 

L(a,u.), and (y) t is not in the choice set corresponding to (u, , . . , iT ). 

1 in 

Condition (9*) requires that if, in a configuration of actions, two 
individuals' actions differ, then any third individual, by varying his 
action, can trace out the entire set A except for those alternatives a for 
which there exists a profile in which a is top-ranked by everyone but not in 
the choice set. 

Theorem 3 : The Revelation Principle: Suppose that, for n >_ 5. f is an n- 
person SCR that is implementable in Nash equilibrium. Then a game form 
satisfying (6), (7), (8*), and (9*) exists. Furthermore, f is fully 
implementable by any such game form. 

For the details of the proof, see Maskin (1977). Here we give only an 
indication of the idea behind the proof by way of an example. 

The construction in Theorem 1 will not serve to implement all 
implementable SCE's. This is because an implementable SCR may fail to 
satisfy weak no veto power (however some implementable SCE's that violate 
weak no veto power can be implemented by the Theorem 1 construction, e.g., 
the individual rationality correspondence of Section 4 below). For example, 
consider the SCR f that chooses alternative c as optimal unless c is Pareto 
dominated. If b Pareto dominates c, b is chosen, unless a, in turn, Pareto 
dominates b, in which case a is chosen. This SCR is clearly monotonic, but 
it does not satisfy weak no veto power because if individuals 2 and 3 (in a 
three-person society) both prefer a to b and b to c, and individual 1 
prefers b to a and a to c, then b is chosen, even though two out of three 
individuals top-rank a. Moreover, the construction of Theorem 1 does not 
implement the SCR. 



19 



To see this, suppose, for instance, that individuals' preferences are 
as just described. However, suppose, in the Theorem 1 construction, that 
individuals 2 and 3 both play the strategy consisting of announcing the 
profile 

'"-^^ -_1_ -2 5 " - 

b c c 
(*) c a a 

abb 

and the alternative c If individual 1 does the same, then the outcome is 
c, since this is the f-optimal alternative. By playing some alternative 
strategy s', furthermore, individual 1 can obtain alternative a, since a 
lies in the lower contour set of 1 's preference ordering as specified by 
(*). Individual 1 cannot, however, obtain alternative b. Therefore, a 
strategy triple where individual 1 plays s' and individuals 2 and 3 each 
play (*) is a Nash equilibrium with respect to individuals' (true) 
preferences. Because the corresponding outcome, a, is not optimal for those 
preferences, we conclude that the game form does not implement f. 

However, f _is_ implementable by a game form satisfying (6), (7), (8*), 
and (9*)' Specifically, (8*) guarantees that a non-optimal equilibrium as 
above cannot arise because, starting from a configuration where all 
individuals play the same strategy, an individual cannot trace out the whole 
lower contour set and, in particular, cannot obtain, for any profile of 
preference, any alternative that is top-ranked by all others and, within his 
lower contous set, top-ranked for him. Thus, in the example, if individuals 
2 and 3 play (*), individual 1 cannot obtain a (in this example, we did not 
have to invoke (9*), which applies only to SCE's that permit non-Pareto 
optimal outcomes). 



20 

Notice that Theorem 3 establishes that implementability implies full 
implementability, as we claimed earlier. The theorem can be used to extend 
the corollary to Theorem 1 to the case of SCR's that do not necessarily 
satisfy weak no veto power. 

Corollary 1 : Suppose that, for n 2i 3, f]^,f2f-»' is a sequence of monotonic 
SCE's. Suppose one of the f.'s is implementable in Nash equilibrium. Then 

CD 

(^ f. is implementable also. 

<^ 

It remains an open question whether (^ f . is necessarily 

i=1 ^ 

implementable. However, a case in which the intersection of two 

implementable SCR's ±s_ implementable is where one of the f. 's is the Pareto 

correspondence . 

Corollary 2 : Por n 2. 3, i^ ^i is an implementable SCR and ^2 i^ ''-^^ Pareto 

correspondence, then f, /if, is implementable if it is nonempty for all 

profiles. 

Closely related to Corollary 2 is the observation that the "Pareto 
frontier" of an implementable SCE is implementable. 

Pareto Frontier of an SCR ; The Pareto frontier of an SCR f is the SCR 
PF(f)(u^ ,...,-u^) = {a e f(u^ ,...,u^)lfor all b e f(u^ ,---,u^), u^(a) >_ u^(b) 
for some i} . 

Corollary 3 '- For n 2. 3, if f is an implementable SCR, then the Pareto 
frontier PF(f) is .also implementable. 

The proofs of Corollaries 1-3 are straightforward applications of 
Theorem 3 (see Maskin (l977)). 



21 



4. No Veto Power, Individual Rationality, and Neutrality 

We have already mentioned that weak no veto power is not necessary for 
implementability. One prominent example of an implementable SCR that 
violates this property is the individual rationality correspondence. Let Bq 
be an element of A. We interpret &q to be the "status quo • " The individual 
rationality correspondence, ■f-r-Tji selects all alternatives that weakly Pareto 
dominate a^, i.e. 

fjp(u^ , ...,u^) ■= {a E A|u^(a) >_ u^C^q) for all i). 
Clearly, f-T, does not satisfy weak no veto power on all domains of utility 

IK 
functions, because every individual must be guaranteed at least the utility 

he derives from a^ . Nonetheless it is a simple matter to fully implement 

f^Tj. For instance, the construction of Theorem 1 will do the trick. For a 

simpler example, let S. = A for all i. Define the game form g: S.x...xS ->■ 

A so that 



s, if E^ = ... = s^ 



(10) g(s^,...,s^) = < 



a.Q, otherwise 

That is, each individual chooses an alternative as an action. If the 
alternatives agree, the common alternative is the outcome; otherwise, Bq is 
the outcome. It is immediate that g fully implements f-pn- Notice that this 
is true even for n = 2. 

The SCR f jTj iB implementable not only by itself but in conjunction with 
other implementable SCR's. 

Corollary 4 to Theorem 3 : Suppose that, for n >_ 5, f is an n-person SCR 
that is implementable. Then f I IfTu ^s implementable too. 

The individual rationality correspondence is highly "non-neutral"; it 

treats the alternative ap very differently from all others. But, just as it 
is imDlementable , so is anv neutral and monotonic SCR. 



22 



Neutrality : An SCR f: U x...xU ♦ A is neutral if for any permutation u: 



A -* A and any profile (u. ,...,u ) 



f(u, n,...,u Ti) = 11 f(u,,...,u ). 

in In 

Neutrality simply says that an alternative's labelling is irrelevant. 
Notice that in the formal statement, we have defined f on the unrestricted 
domain. This is to ensure that f is defined on the permutation profile 
(u. ii,...,u on). The following result is another simple application of 
Theorem 3- 

Theorem 4 (Maskin (1977)): For n >^ 3, an n-person SCR that is monotonic and 
neutral is implementable in Nash equilibrium. 

Theorem 4 and Corollary 4 raise the question of whether weak no veto 
power is a redundant condition for implementability when n >_ 3» In fact, 
the following example demonstrates that it is not, by exhibiting a three- 
person monotonic SCR that is not implementable. 

Example 1 (Maskin (1977)) A nonimplementable, monotonic SCR: Let n = 3 and 
A = {a,b,c}. For each i, let U. consist of all utility functions 
corresponding to strict preference orderings (i.e., u. (a) = u. (b) implies a 
= b). Define the SCR f: U^ x U2 x U3 -^ A so that for all (u^Uj^Ug) e U^^ x 
U2 X U3 and all x, y e A, x e f(u2,U2,U3) if and only if 

(11) X is Pareto optimal 

(12) if X E {a,b} u^(x) > u^(y) for all y * x 

(13) if X = c, there exists y c A such that u^(x) > u,(y). 

It is easy to see that f is monotonic. Choose (u*,Up,;i^), (uf*,U2*»u¥*) , 
and ( u*** , u^** , u?** ) e U^ x U2 x Ug so that 

u*(b) > u*(c) > u*(a) 

u*(c) > u*(a) > u|(b) 

u*(c) > u*(a) > u*(b) 
3 3 3 



23 



u**(a) > u^(b) > u|»(c) 
u**(c) > u^(b) > u**(a) 
u**(c) > u»*(a) > u|*(b) 



U***^^?)"^ u***(a) > uf**(c) 
u^(a) > u***(b) > u^(c) 
u?**(a) > u?**(b) > u***(c). 



Then 

(U) f(u»,u*,u*) - {b,c} 

(15) f(u^,u|*,u^) = {a} 

(16) f(u***,u***,u*^) •= {b}. 

If f is implement able, there erists a weakly implementing game form g: Sj^ ^ 
S2 >< S3 •*• A and a vector of actions (sj^jSjrSj) such that g(B2,B2,B3) •= c and 
(s^.SjtSg) is a Nash equilibrium for the profile (utjuS.u?) • Because u1^(b) 
> ut(c), there does not exist sV t S. such that g(B'',B_,s_) = b. If there 
exists s' E S, such that g(s',Sp,s_) = a, then (s',s„,s_) is a Nash 
equilibrium for (u"?**,ut**,u?**) , contradicting (16). If there does not 
exist s[ E S, with g(s',Sp,s_) = a, then (s.,Sp,s_) is an equilibirum for 
(u**,u**,u?*) , contradicting (15)« Hence f is not implementable . 
5- Nash versus DoTninnnt Strategy Implementation 

A dominant strategy ie an action that an individual is willing to take 
regardless of the actions of others. Formally, we have 
Dominant Strategy : In a game form g: S>x...xS -»- A, an action s. is a 
dominant strategy for individual i with utility function u. if for all s. e 
S . and s . E n S . 



24 



The definition of implementability in dominant strategies is analogous 
to that for Nash equilibrium. The game form g: S. x. . . xS -►A weakly- 
implements the SCR f if for all profiles (u,,...,u ) 

(17) DSE (u.,...,u ) is nonempty. 
and 

(18) DSE (u^ ,.. .,u^) C f(u^ ,...,u^), 

where DSE (u. ,...,u ) consists of all dominant strategy equilibium outcomes 

corresponding to (u,,...,u ). If ( 18) is an equality, g fully implements f. 

As we suggested in Section 3. however, the literature on dominant 

strategies has emphasized not this definition but rather the concept of 

truthful implementation. For dominant strategies, a direct revelation game 

form is a mapping 

g: U X. . .xU -^ A. 
''In 

The game form g truthfully implements f in dominant strategies if, for all 

(u. ,...,u ), the actions (u. ,...,u ) constitute a dominant strategy 

in. In 

equilibrium with respect to the utility functions (u. ,...,u ) and 

g(u^,...,u^) t f(u^ , ...,u^). 

Clearly, if f is weakly implemenxable in dominant strategies, it is 
truthfully implementable. However, it is eas/ to give examples where the 
converse does not hold (e.g.. Example 4-. 1.2 in Dasgupta, Hammond, and Maskin 
(1979))' Nonetheless, there is an important case in which we can deduce the 
converse; viz., where the U. 's contain only strict preferences. 
Lemma_2: Suppose the U. 's contain only strict preferences. If the SCE f : 
U.X...XU ->■ A is truthfully implementable, then it is weakly implementable 
in dominant strategies. 



25 



Proof ; See Daegupta, Hammond and Maskin (1979)' 

?or much of the rest of this section, we vlll concentrate on SCH'e that 
are single-valued, i.e., whose choice sets contain only a single element. 
For such sen's (denoted "SSCR's" for Bingl»-valued social choice rules) we 
can characterize tinithful implementabillty in terms independent person-by- 
person monotonicity. 

Independent Person-by-Person Honotonicity (IPM) ; An SSCR f satisfies IPM if 
for all (u^,...,u ) E U.X...XU , all i, all u, e U. and all a, b e A such 

that a E f(u.,>*.,u ) and u. (b) > u. (a), it must be the case that b / 

I n 1 1 ' 

f(u^fU_^). 

Lemma 3 : An SSCR f: U, X...U •♦■ A is truthfully implementable if and only if 

it satisfies IPM. 

Proof ; See Dasgupta, Hammond, and Maskin (1979)» 

We should point out that IPM does not, in general, imply monotonicity. 
That is, truthful implementability (even full implementability) in dominant 
strategies does not imply Nash implementability. 

Example 2 ; Let A ■ {a,b,o,d} and n - 3« Suppose that each U. consists of 4 
utility functions: u^, u^ , u , u°, where 

u^a) > u^(b) > u^(d) > u^(o) 

u^^(a) - u^^b) > u^^o) > u^^(d) 

u^(b) > u^a) > u^(d) > u^o) 

u°(o) > u°(d)'> u°(a) > u°(b). 
Define the SSCR f : Uj_ >« Uj x U3 ■► A so that 



26 



{c}, if u. •= u for some i and 
1 

a majority prefers c to d. 



{d}, if u. = u for some i and 

a majority prefers d to c. 



f(u^ rUjtUg) = < 



{b}, if at least two individuals have 
utility function u and no one 
has u . 

{a} , otherwise 

One can verify straightforwardly that f is truthfully implementable in 
dominant strategies. In fact, the direct revelation game form corresponding 
to f fully implements f (and has the strong property that, truth-telling is 
dominant even for coalitions). However, f is not monotonic because, for 
example, f(u ,u ,u ) = {b} but f(u ,u ,u ) = {a} even though, for all x e 
A, u (b) >_ u (x) implies u (b) >_ u (x). Thus f is not implementable in 
Kash equilibrium. This may seem odd, because the concept of dominant 
strategy equilibrium is much more demanding than that of Nash equilibrium. 
The apparent paradox is resolved by remembering that, to implement an SCR, 
one not only has to ensure that the elements of the choice set can arise as 
equilibrium outcomes , one has to prevent the existence of equilibrium 
outcomes outside the choice set. It is easier to meet this second 
requirement when dominant strategies are the solution concept, since by the 
very stringency of a dominant strategy equilibrium, a nonoptimal equilibrixun 
is less like to arise. 



27 
Nonetheless, when preferences are strict, dominant strategy 
implementability does imply Hash implementability: 

Theorem 5 (Dasgupta, Hammond, and Maskin (1979)): If the U. 's contain only 
strict preferences, then an SSCR f that is truthfully implementable in 
dominant strategies is also monotonia. 

Proof : Prom Lemma 3, an SSCR that is truthfully implementable satisfies 
IPM. Consider (u2^,...,u ), (u^,...,u ), and a e A such that 
a e f(u^,...,u ) and, for all b e A and i, u (a) > u.(b) implies u.(a) > 
u. (b). Suppose that c t f(u. ,u_ , . . . ,u ) for some c e A. If c ^ a, then IPM 
implies that U2^(c) > u^(a) and u^(a) > u^Cc). But u^(a) > Uj^(c) implies 
u^Ca) > Uj^Cc), by hypothesis. Therefore a"c, and so a e f (u^jUj, • • • rU ). 
Continuing iteratively, a e f(u,,...,u ). 

Q.E.D. 
Not surprisingly, monotonicity does not in general imply IPM. Still, 
there is a large class of oases where the implication holds. To discuss 
this class, we need the following definition. 

Monotonically Closed Domain ^: A class U of utility functions is a 
monotonically closed domain if, for all pairs {u,u'} C U and {a,b} ^A such 
that (i) u(a) >_ u(b) implies u'(a) _> u' (b) and (ii) u(a) > u(b) implies 
u'(a) > u-'(b), there exists u" t U such that for all c e A (iii) u(a) >_ u(c) 
implies u"(a) >_u"(c), and (iv) u'(b) ^ u'(c) implies u"(b) _> u"(c). 

One way of generating a u" satisfying the requirements of the 
definition is by taking minimums: if u(a) = u'(a) and u(b) ■= u'(b), then u" 
= min(u,u') will suffice. 



^A monotonically closed domain is called a "rich domain" in Dasgupta, 
Hammond, and Maskin (1979). 



28 

Clearly, the iinrestricted domain U. is monotonically closed. 

Trivially, any domain consisting of a single utility function is also 

monotonically closed. Suppose that A is the set of allocations across 

individuals of fixed stocks of m divisible commodities. If U consists of 

all utility functions corresponding to continuous, strictly, monotone, 

strictly convex, selfish (i.e., no externalities) preferences over A, then, 

as shown by Dasgupta, Hammond, and Maskin (1979), U is monotonically closed 

as well. 

Theorem 6 (Dasgupta, Hammond, and Maskin (1979)): If U. is monotonically 

closed for all i, then if the SSCR f is implementable in Nash equilibrium, 

it is truthfully implementable in dominant strategies. 

Proof : If f is implementable in Nash equilibrium, then it is monotonic. If 

f violated IPM, there would exist (u^j.-.fU ), u., a, and, b such that a t 

f(u,,...,u ) and u.(a) > u.(b) but b e f(u.,u .). From the monotonic 
in 1 1 1 -1 

closure of U. , however, there exis-cs u. e U. such that for all c 
1 11 



and 



u.(a) > u.(c) implies u.(a) > u.(c) 
1—1 ^ 1—1 



u. (b) 2. ii- (c) implies u. (b) _> u. (c) . 



Prom monotonicity applied to (u. ,u .) and (u.,u .), we have a z f (u. ,u .). 
But from monotonicity applied to (u. ,u .) and (u. ,u .), b e f(u. ,u .), a 



29 

contradiction of f's single- valuedness. Therefore, f satisfies IPM and so 
is truthfully implementable in dominant strategies. 

Q.E.D. 
Theorem 6 implies that if a planner wishes to implement a single-valued 
SCR , he"wriirget no extra mileage from using the ostensibly weaker concept 
of Nash implementation if the domain of utility functions is monotonically 
closed. In particular, we have the following negative result. 
Corollary 1 (Dasgupta, Hammond, and Maskin (1979), Roberts (1979): Suppose 
that A contains at least three elements and that f : U -^ A is an n-person 
SSCR that is onto A. If f is implementable in Nash equilibrium, it is 
dictatorial. 

Proof : Because U is monotonically closed, Theorem 6 implies that f is 
truthfully implementable in dominant strategies. But then, from the Gibbard 
(1973)/Satterthwaite (1975) theorem on dominant strategies, f is 
dictatorial . 

Q.E.L. 
Roberts (1979) extends Corollary 1 to the case of "conjectural" 

equilibria, where, rather than taking other players' strategies as given, an 

individual conjectures that others will respond to his strategy choice. 

This result is, in turn, closely related to one of Pattanaik (1976). 

Another implications we can draw "from Theorem 6 is a set of conditions 

under which an implementable f can be thought of as maximizing a social 

aggregation function. 

Social Aggregation Function : Let B. be the class of all complete, 

reflexive, binary relations on A. A social aggregation function (SAF) is a 

mapping 

F: U X...XU -i- B. . 
1 n A 



30 

If the range of F consists of acyclic relations, F is called a social 

decision function, and if these relations are also transitive, F is a social 

welfare function. F satisfies the Pareto property if whenever all 

individuals strictly prefer a to b (i.e., u.(a) > u.(b) for all i) then 

F(u. ,...,u ) ranks a above b. F satisfies nonnegative response if, for all 

{a,b} and { (u. , . . . ,u ) , (u. , . . . ,u )} , if, for all i, u.(a) >_ u.(b) implies 

u. (a) >^ u. (b) and u. (a) > u. (b) implies u. (a) > u.(b), then that a is ranked 

weakly (strictly) above b by F(u. ,...,u ) implies that a is ranked weakly 

(strictly) above b by F(u. , . . . ,u ). 

The SSCR f maximizes F if, for all (u, ,...,u ), a e f(u. ,...,u ) 

In In 

implies that, for all b ^ a, a is striclty preferred to b by F(u, ,...,u ). 

Corollary 2 : Suppose that the U! s are monotonically closed and consist only 

of strict preferences , the SSCR f is implementable in Nash equilibrium if 

and only if there exists an SAF F satisfying nonnegative response such that 

f maximizes F. Furthermore, if f is onto A, F satisfies the Pareto 

property. 

Proof : See Dasgupta, Hammond, and Maskin (1979) 

Nonnegative response implies independence of irrelevant alternatives 
(IIA) in the sense of Arrow (l95l)- Corollary 2, therefore, illustrates the 
close relationship among monotonicity, IPM, and IIA. 
6. Quasilinear Preferences 

So far, the only particular domain of utility functions that we have 
discussed in any detail is the unrestricted domain U,. We next consider an 
important restricted domain: the class of quasilinear preferences. 

Suppose that a social alternative consists of a public decision d 

(which is an element of some set D) and a vector (t,,...,t ) of transfers of 

1 ' n 



51 



some private good (the t. 's are real numbers). Individual i's preferences 

are quasilinear if his utility function u takes the form 

(20) v(d) + t^. 

Let U. be the class of all preferences of form (20). This class has been 

the object of much study in the dominant strategy implementation literature 

(see, for example, Clarke (1971), Groves (1973), Green and Laffont (1979))- 

Rather less has been done with it in the Nash implementation literature 

(see, however, Laffont and Maskin ( 1982a) and (1982b) and Roberts (1979))- 

QL 
It is readily verified that the domain U. is not monotonically closed. 

Therefore, Theorem 10 does not apply, and we cannot conclude that the sets 

of Nash- and dominant strategy-implementable SSCR's are the same. 

Nevertheless, as Roberts (1979) has shown, the public decision parts of the 

SSCR's are identical. 

In view of (20) we can express an SSCR as a function of the public 

parts of individuals' utility functions. Write 

f(v.,...,v ) = (d(v. , ... ,v ), t(v. ,... ,v ), . .. ,t (v. , ... ,v )), 
in 1 n 1 n n i n 

where u. = v. + t. . 

Ill 

Theorem 7 : Suppose that D, the public decision space is finite. Let f: 

OL OL / \ 

U; x...xu^ ->■ A be an SSCR such that d( ) is onto B. Then if f is either 
1 n 

Hash-implementable or truthfully implementable in dominant strategies, there 

n 

exist VfiiD ->• R and numbers a. , . . . , a such that c. > for all i and I a. = 
" ^ 1 ' ' n 1 — . , 1 

1=1 



1 such that d(v. ,...,v ) = arg max(vQ(d) + Z a^. v^. (d)) 



d i=1 



n 

01- . . , 

1 1 



32 

Proo f: See Roberts (1979). 

Laffont and Maskin ( 1982a) place more structure on the problem by- 
assuming that 

D = [0,1] 
and that the individuals' v. functions are concave and differentiable and 
take their maxima in the interior of D. Let V be the class of such 
functions. They also assume that the public decision function d( ) is 

weaklv efficient (if v, =...= v , then d(v, ,...,v ) = arg mar v.), and 

' 1 n 1 n ^ 1 ' 

neutral (d(v , ...,v ) = d(v , ...,v ) + c, where for all i, v.(d) ■= v.(d-c)). 

Theorem 8 : Let f be an SSCE oe Vx..,xV that is either Nash-implementable or 
truthfully implementable in dominant strategies. If d is weakly efficient 
and neutral then 

(i) there exists a continuous and semi-strictly increasing^ function h: 
R -*• R such that h(0,...,0) = and d(v, ,...,v ) solves h(v' (d) , • . . ,v' (d)) = 
0, where primes denote derivatives; 

(ii) if f is Nash implementable, t. is a function of the numbers 
d(v^,...,v^) and v^ (d(v^ , . . . ,v^)) , . . . ,v^(d(v^ , . . . ,v^) ) ; 

(iii) if f is truthfully implementable in dominant strategies, then 

d(v^ ,' ••.\) 

t = - / h (v:(t))dt + H (v ), 
1 1-1 

where h.: IR •* IE satisfies 



^By "semi-strictly increasing" we mean that if x is bigger in evry component 
than y, then h(x) > h(y) . 



33 

h(h (a ), B. ) "0, if there exists a. with h(a. ,a . ) ■= 
h.(a .) •= 0, otherwise. 
Proof: See Laffont and Maskin ( 1982a). 



Notice that the set of implementahle public decisions is defined by- 
varying h, whether it be Nash or dominant strategy implementation. When, 

n 
for example, h = Z ^^v.' . 
i=1 

the public decision becomes 

n 

d(v.,...,v ) = arg max Z \.v.(d). 
1 n "^ , .,11 
d i'=1 

The form of the transfers, however, depends on the type of implementation. 
Nash implementation demands that the transfers be a function of the optimal 
public decision and the derivatives of individuals' utility functions 
evaluated at the optimum. Dominant strategy implementation requires that an 
individual's transfer be the sum of two terms: a term depending on the 
derivitives of the utility functions and the public decision, and a term 
depending only on the utility functions of the other individuals . 
7. Strong Equilibrium 

Hash equilibrium is a noncooperative concept; it implicitly assumes 
that individuals do not act in concert. When individuals can collude, 
strong equilibrium may be a more appropriate solution concept. 
Strong Equilibium : A strong equilibrium for the game form g: S.x. ..xS -»- A 
with respect to the profile (u. ,...,u ) is a configuration (s^,...,e ) such 
that for all coalitions CC {1,...,n} and all s„ z U S. there exists i e C 

such that u^(g(s)) >_ u^(g(sp,s"_p)) . 



34 



By analogy with Nash equilibrium, a game form g fully implements the f 

in strong equilibrium if for all profiles (u.,...,u ) 

SE„(u, , .. . ,u ) = f(u ,...,u ), 
g 1 n 1 n 

where SE (u, ,...,u ) consists of the strong equilibrium outcomes of g for 

the profile (u, ,...,u ). 
1 n 

We should note that if g fully implements f in strong equilibrium, it 
does not necessarily implement f in Nash equilibrium. The reason for this 
apparent anomaly is that g may possess Nash equilibria that are not strong 
and which, futhermore, do not lead to outcomes in the choice set. For 
example, consider the following two- person game form, where individual 1 
chooses rows as actions, and individual 2, columns: 



a 


a 


a 


b 



This game form fully implements the SSCR f*: U2^xU2-^{a,b}in strong 
equilibria, where the U. 's contain the strict preferences on {a,b} and 

b, if both individuals prefer b to a 



•f* 



(u2,U2) = < 



a, otherwise. 

However, the game form does not implement f* in Hash equilibrium, because 
(3^,82) is a non-f*-optimal Nash equilibrium when both individuals prefer b 
to a. 

We have seen that monotonicity is a necessary condition for 
implementability in Nash equilibirum. The same is true for strong 



35 



Theorem 9 : (Maskin ( 1979b): If an SCR f is implementable in strong 
equilibrium, it is monotonic 

On the other hand, weak no veto power, which played an important role 
in establishing positive results for Nash implementation, prevents 
implementation in strong equilibrixim when the number of individuals does not 
exceed the number of alternatives and the domain is unrestricted. 
Theorem 10 : If the n- person SCR f: U x...xU -► A is onto A, n is less than 
or equal the cardinality of A but greater than or equal to three, and f is 
implementable in strong equilibrium, f does not satisfy weak no veto power. 
Proof : The proof consists of considering a "cyclic" profile of preferences 
(u^ , . . . ,u ) , where 

u^(a^) > u^(a2) >...> u^(a^) 

U2(a2) > U2(a3) >...> U2(a^) 

u (a ) > u (ai) >...> u (a ,). 
n n n -^ n n-1 

Such a profile exists because there are at least as many alternatives as 
individuals. But then it is a straightforward to show that no alternative 
can be a strong equilibrium, since no single individual has veto power. For 
the details, see Maskin ( 1979b). 

Q.E.I. 
Theorem 10 is false if the number of individuals exceeds the number of 
alternatives, as the following example shows. 

Example 3 : Let n = 3, A = {a,b}, and U. consist of the strict preferences 
on A. Let f be majority rule, i.e., an alternative is in the choice set if 
and only if it is top-ranked by two or more individuals. The following game 
form implements f: 



36 



a 


a 


a 


b 



a 


b 


b 


b 



where individual 1 chooses rows, 2 columns, and 3 matrices. A large class 

of other examples has been constructed by Moulin and Peleg (1982). 

Clearly if an SCR f is onto its range and fully implementable , it must 

be Pareto optimal. In Section 4 we demonstrated that the SCR that selects 

all Pareto optimal and individually rational alternatives is implementable 

in Nash equilibirum. In fact, this is the only individually rational SCR on 

the unrestricted domain that is fully implementable in strong equilibrium. 

Individually Rational SCR: If an e A is the status quo, an SCR f: U, x...xU 
1 - ' 1 n 

•^ A is individually rational if for all (u. ,...,u ) and all a t f(u. ,...,u ) 

u.(a) > u.(an) for all i. 

Theorem 11 (Maskin (l979b)): Let f „ : U x...xU. ^- A be the SCC such that 
Q A A 

for all (u. , . . . ,u ) 

I n 

f-(u, ,...,u ) = {a E Alfor all j u.(a) > u.(an) and, for all i, and for 
all b E A, there exists i such that u.(a) >_u.(b)}. 
Then f^^ is the iinique individually rational SCC on U.x...xU, that is 
implementable in strong equilibrium. 

Proof : It is immediate to verify that f^ is fully implemented by the game 
form (10) (which, interestingly, also implements the individual rationality 

correspondence in Nash equilibrium) . That f-^ is the only implementable 
individually rational SCR on the unrestricted domain follows from an 
argument in Maskin ( 1979b). 



37 



8. Double Implementation 

Whereas implementation in Nash equilibrium ignores the possibility of 
collusion, implementation in strong equilibrium may, in effect, require 
coalitions to form. To see this, consider the game form (10). In order to 
obtain any alternative other than Bq, all individuals have to take the same 
action. Clearly, there are many (non-strong) Nash equilibria in which 
different individuals take different actions, and to avoid ending up in one 
of these presumably involves some coordination. That is, collusion is 
necessary. 

Because the game form designer may not know the extent to which 
collusion can or will take place, it is desirable to have an implementation 
concept that does not posit any particular degree of collusion. One 
possibility is to require a game form to fully implement simultaneously in 
both strong and Nash equilibrium. This game form would yield optimal 
outcomes regardless of collusion. We shall say that such a game form 
(fully) doubly implements the SCR. 

Of course, double implementation is a very demanding requirement. Hot 
very surprisingly, when the number of alternatives is at least three and the 
domain of utility functions is unrestricted, the only SCE's that are onto A 
and doubly implementable are dictatorial. 

Theorem 1 2 (Maskin 1979a): Suppose A contains at least three elements and 
f: U.><...>«U. -*■ A is an n-person SCE that is onto A. If f is doubly 
implementable, then it is dictatorial. 

The results are more encouraging, however, when preferences are 
restricted. Suppose, in particular, that there exists (at least) one 
divisible and transferable private good that all individuals find desirable 
and that does not create externalities (i.e., one individual's allotment of 



38 

this good does not affect any other's utility). Let us express a social 

alternative a as (b,t, , . . . ,t ) , where t. is the transfer of this private 

good to individual i, and b represents all other social decisions inherent 

in a. We shall call b the "public decision," although it may itself entail 

the allocation of private goods. Denote the status quo, blq, by 

(bg ,0, . . . ,0) . Suppose that the private good is sufficiently desirable (and 

that consumers have enough of it in the status quo so that, for all i and 

all public decisions b, there exist (t.,...,t ) such that 

(21) (b,^, ,... ,"t ) E A and, for all t. < "t. and all u., u.(an) > 
In 1 1 iiO 

u. (b,t . ,t . ) . 
1 1 -1 

Condition (21) provides for the existence of "punishments." It says that 
regardless of the public decision, it is always possible to take away enough 
of the private good from individual i to make him worse off than under the 
status quo. ¥e have the following result. 

Theorem 13 : Assum.e the existence of a desirable and divisible private good . 
If (21) is satisfied, then any individually rational and Pareto optimal SCR 
is fully doubly implementable. 
Proof ; See Maskin (1979a). 
9. Related Concepts 

This paper has discussed Hash, strong Nash, and "double" 
implementation. We should, however, mention two related lines of work. 

Farquharson (1969) proposed the concept of a "sophisticated" 
equilibrium. This is a refinement of Hash equilibrium in which weakly 
dominated strategies are successively eliminated. For example, consider the 
following two player game: 



59 



2,2 


1,1 


1,1 


0,G 


1,1 


2,1 


0,0 


1,2 


0,0 



The strategy configurations (a,d), (b,e), (c,e), and (b,f) are all Nash 
equilibria. However, strategies c and f are weakly dominated for players I 
and II. If we delete them, the game becomes 

d e 



2,2 


1,1 


0,0 


1,1 



notice that here strategies b and e are weakly dominated. Once these are 
deleted, the players have one strategy each. Hence (a,d) forms a 
sophisticated or dominance solvable equilibrium. 

The theory of implementation in dominance solvable equilibrium has been 
developed largely by Moulin (see Moulin (l979a), (l979b), (1979c), (1980), 
(1981 )). Although a full characterization of the implementable SCR's is not 
available, there are by now many examples of Pareto optimal, neutral, and 



40 

anonymous SCR'b that can be implemented, including some that are not Nash 
implementable . 

An SSCR can itself be thought of a a game form; a player's strategy is 
the announcement of a utility function (not necessarily his true one) and 
the outcome is the alternative optimal with respect to the announced 
preferences. An SSCR is said to be consistent if for any profile of (true) 
preferences there exists a strong equilibrium of the SSCR (when viewed as a 
game form) whose outcome is optimal with respect to those (true) 
preferences. Notice that the qualification about optimality is not 
superfluous since the strategies played in equilibrium may themselves be 
untruthful. The concept of consistency is due to Peleg (1977). Besides 
Peleg, contributors to the subject include Butta and Pattanaik (1978). 



41 



REFERENCES 



Arrow, K. (1951). Social Choice and Individual Values , Cowles Foundation 
Monograph 12. 

Clarke, E. (1971 ), "Multipart Pricing of Public Goods," Public Choice , 8:19- 
35. 

Dasgupta, P., P. Hammond, and E. Maskin (1979), "The Implementation of 
Social Choice Rules," Review of Economic Studies , 46:185-216. 

Dutta, B. and P. Pattanaik (1978), "On Nicely Consistent Voting Systems," 
Econometrica , 46:165-170. 

Farquharson, R. (1969), The Theory of Voting , New Haven: Yale University 
Press. 

Gibbard, A (1975), "Manipulation of Voting Schemes: A General Result," 
Econometrica , 41:587-602. 

Green, J. and J.J. Laffont (1979), Incentives in Public Decision-Making , 
Amsterdam: North-Holland . 

Groves, T. (1975), "Incentives in Teams," Econometrica , 41:617-51* 

Groves, T. and J. Ledyard (1977), "Optimal Allocation of Public Goods: A 
Solution to the Free Rider Problem," Econometrica , 45:785-810. 

Harsanyi, J. (1967), "Games with Incomplete Information Played by 'Bayesian' 
Flayers," Management Science , 14:159-32, 520-54, 485-502. 

Hurwicz, L. (1972), "On Informationally Decentralized Systems," in Decision 
and Organization , edited by C.B. McGuire and R. Radner, 
Amsterdam: North-Holland . 

Hurwicz, L. and D. Schmeidler (1978), "Outcome Functins which Guarantee the 
Existence and Pareto Optimality of Nash Equilibria," Econometrica , 
46:144-74. .. 

Laffont, J.J. and E. Maskin (l982a), "Nash and Dominant Strategy 

Implementation, in Economic Environments," Journal of Mathematical 
Economics , 10:17-47- 

Laffont, J.J. and E. Maskin (l982b), "The Theory of Incentives: An 

Overview," in Advances in Economic Theory , edited by W. Hildenbrand, 
Cambridge: Cambridge University Press. 

Maskin, E. (1977), "Nash Equilibrium and Welfare Optimality," to appear in 
MasthematicE of Onerations Research. 



42 



Maskin, E. ( 1979a), "Incentive Schemes Immune to Group Manipulation," mimeo. 

Maskin, E. (1979b), "Implementation and Strong Nash Equilibrium," in 
Aggregate and Revelation of Preferences , edited by J.J. Laffont, 
Amsterdam : North-Holland . 

Moulin, K. (1979a), "Dominance-Solvable Voting Schemes," Econometrica , 
47:1357-51. 

Moulin, H. (1979b), "Implementing Just and Efficient Decision Making," 
forthcoming in the Journal of Public Economics . 

Moulin, H. ( 1979c), "Prudence versus Sophistication in Voting Strategy," 
forthcoming in the Journal of Economic Theory . 

Moulin, H. (1980), "Implementing Efficient, Anonjnnous, and Neutral Social 
Choice Functions," Journal of Mathematical Economics , 7:249-269- 

Moulin, H. (I98l), The Strategy of Social Choice , Paris: Laboratoire 
d 'Econometrie de 1 Ecole Polyxechnique. 

Moulin, H. and B. Peleg (1982), "Cores of Effectivity Functions and 

Implementation Theory," Journal of Mathematical Economics , 10: 11 5-45 • 

Muller, E. and M. Satterthwaite (1977), "The Equivalence of Strong Positive 
Association and Strategy-Proofness , " Journal of Economic Theory , 
14:412-18. 

Myerson, E. (1979), "Incentive Compatibility and the Bargaining Problem," 
Econometrica , 47: 61 -73' 

Myerson, E. (1982), "Optimal Coordination Mechanisms in Principal-Agent 
Problems," Journal of Mathematical Economics , 10. 

Ryerson, E. (1983), "Implementation via Bayesian Equilibria," in Social 
Coals and Social Organization: VolTime in Memory of Elisha Pazner , 
CambriQge University Press, forthcoming. 

Sash, J. (1950), "Equilibrium Points in n-person Games," Proceedings of the 
National Academy of Sciences , 36:48-50. 

Pattanaik, P. (1976), "Counter-threats and Strategic Manipulation under 
Voting Schemes," Review of Economic Studies , 43:11-18. 

Peleg, B. (1977), "Consistent Voting Systems," Econometrica , 46:155-162. 

Roberts, J. and A. Postlewaite (1976), "The Incentives for Price-taking 
Behavior in Large Exchagne Economies," Econometrica , 44:115-28. 

Roberts, K. (1979), "The Characterization of Implementable Choice Rules," in 
Aggregation and Revelation of Preferences , edited by J.J. Laffont, 
Amsterdam: North-Holland . 



43 



Satterthwaite, M. (1975), "Strategy-Proof ness and Arrow's Conditions: 

Existence and Correspondence Theorems for Voting Procedures and Social 
Welfare Functions," Journal of Economic Theory , 10:187-217. 



9632 



2i]^^ 



3 TDflD DD3 D 



,2M 



Date Due 




Lib-26-67