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

## See other formats

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