Discussion Paper No. 672

FULL-TRUTHFUL IMPLEMENTATION
IN NASH EQUILIBRIA

Hideki Mizukami
andTakuma Wakayama

September 2006

The Institute of Social and Economic Research
Osaka University
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, Japan

Full-Truthful Implementation in Nash Equilibria∗
H IDEKI M IZUKAMI †Faculty of Economics, University of Toyama

mizukamie o.u-toyama.a .jp
andTAKUMA WAKAYAMA
Institute of Social and Economic Research, Osaka University

wakayamaiser.osaka-u.a .jp
September 29, 2006

∗ We are grateful to Yoshikatsu Tatamitani for his invaluable comments and suggestions. We
also thank seminar participants at the 2005 Autumn Meeting of the Japanese Economic Association for their comments.
† Corresponding author. Faculty of Economics, University of Toyama, 3190 Gofuku, Toyama
930-8555, JAPAN.

1

Abstract
We consider full-truthful Nash implementation, which requires that truth
telling by each agent should be a Nash equilibrium of a direct revelation
mechanism, and that the set of Nash equilibrium outcomes of the mechanism should coincide with the f -optimal outcome. We show that restrictedmonotonicity together with an auxiliary condition called boundedness isboth necessary and sufficient for full-truthful Nash implementation. We
also prove that full-truthful Nash implementation is equivalent to secure
implementation (Saijo et al. (2005)). This gives us an alternative characterization of securely implementable social choice functions.
Keywords: Restricted Monotonicity, Direct Revelation Mechanisms, Nash
Implementation, Truthful Implementation, Secure Implementation.

2

1 Introduction
The implementation problem is that a mechanism designer, who cannot observe the true preferences of each agent, devises a mechanism whose equilibrium outcomes always coincide with the social goal given by a social choice correspondence. The Nash equilibrium concept has often been used as an equilibrium concept in the complete information case, where each agent knows not
only own true preferences but also the true preferences of every other agent,
while the mechanism designer cannot observe agents’ true preferences. In theseminal paper on Nash implementation, Maskin (1999) showed that monotonicity is necessary for Nash implementation, and that monotonicity plus no vetopower is sufficient for Nash implementation when there are three or more agents.
The gap between necessity and sufficiency for Nash implementation has subsequently been closed by Moore and Repullo (1990), Dutta and Sen (1991), Sjöström(1991), etc.
However, positive results listed above rely on complicated mechanisms usedin the constructive proofs, where agents are often forced to announce an outcome, an integer, etc. in addition to a preference profile. Such mechanisms havebeen criticized not only for practicability but also for a theoretical reason. Jackson (1992) criticized such mechanisms for employing an integer game, because
mechanisms involving the integer game fail to satisfy the best response property regardless of the use of the Nash equilibrium concept. So, it is important toinvestigate what kinds of social choice functions can be Nash implemented by“simple” mechanisms which rule out integer games.
For the simplicity of mechanisms, we consider implementation by direct revelation mechanisms, i.e., mechanisms where agents are required to report own
preferences only. Much attention has recently focused on the mechanisms froma practical perspective as well as a theoretical viewpoint. For example, Roth(1984) analyzed a direct revelation mechanism used for the National Resident
Matching Program, Abdulkadiroğlu and Sönmez (2003) studied direct revelation
mechanisms for school choice, and Roth et al. (2004) proposed direct revelation
mechanisms for kidney exchange. Besides, direct revelation mechanisms satisfy self-relevancy (see Hurwicz (1960)), the requirement that each agent should
be asked to reveal information about only herself.1 So, the mechanisms seem
attractive from the viewpoint of informational decentralization. However, few
would study Nash implementation by direct revelation mechanisms. This would
be partly because the revelation principle for Nash implementation does nothold in general.
Nevertheless, in this paper, we restrict attention to Nash implementation
by a direct revelation mechanism where truth telling by each agent is a Nashequilibrium of the mechanism, which we call full-truthful Nash implementa1 Tatamitani (2001) considered Nash implementation by self-relevant mechanisms, where eachagent is required to announce own preferences, an outcome, and an agent index.

3

tion. This restricts the class of implementable social choice functions, since therevelation principle for Nash implementation cannot hold. Indeed, the classof fully-truthfully Nash implementable social choice functions is limited to theclass smaller than that of truthfully Nash implementable social choice functions,which is equivalent to that of truthfully dominant strategy implementable social choice functions, as shown by Dasgupta et al. (1979). However, the requirement that truthful revelation by each agent should be a Nash equilibrium of themechanism would be attractive from a practical standpoint. If there are multiple equilibria of a direct revelation mechanism violating the requirement, thenagents could be hard to predict each other’s actions, which could lead to miscoordination. But, if truthful reporting by each agent is a Nash equilibrium of
the mechanism, then it would be a focal point, and so agents would be able tocoordinate their actions.
This paper relates to one by Saijo et al. (2005), who identified conditions
necessary and sufficient for secure implementation,2 i.e., double implementation in dominant strategy equilibria and Nash equilibria. We show in Section
4 that full-truthful Nash implementation is equivalent to secure implementation, which gives us an alternative characterization of securely implementablesocial choice functions (see Corollary 3). The equivalence derives mostly fromthe result of Dasgupta et al. (1979) stating that truth telling by each agent is aNash equilibrium of a direct revelation mechanism if and only if it is a dominant
strategy equilibrium of the mechanism. So, the requirement of truthful revelation by each agent being a Nash equilibrium could be agreeable, because directrevelation mechanisms violating the requirement cannot securely implement
any social choice function.
This paper is organized as follows. Section 2 provides notation and definitions. We identify necessary and sufficient conditions for full-truthful Nash implementation in Section 3. In Section 4, we examine the relationship of fulltruthful Nash implementation to secure implementation. Section 5 contains
some concluding remarks.

2 Notation and Definitions
Let N := {1, 2, . . . , n} be the set of agents, where 2 ≤ n < +∞. Let A be the set of
feasible outcomes.
Each agent i ∈ N has preferences over A, which are represented by a complete
and transitive binary relation R i . The strict preference relation and indifference
relation associated with R i are denoted by P i and I i , respectively. Let R i denote the set of possible preferences for agent i ∈ N . A domain is denoted by
R := R 1 × R 2 × · · · × R n . A preference profile is a list R = (R 1 , R 2 , . . . , R n ) ∈ R . It is
2 Cason et al. (2006) ran experiments to compare the performance of secure and non-secure

mechanisms. They reported experimental results which suggest that the notion of secure implementation is important in terms of practical applications.

4

assumed that each agent can observe not only her own preferences but also allother agents’ preferences.
An environment is a collection (N , A, R ).
Let LC i (a; R i ) := {b ∈ A | aRi b } be agent i ’s lower¯ contour set of a ª∈ A at R i ∈©
R i . For each agent i ∈ N , let arg max Ā R i := a ∈ Ā ¯ aRi b for all b ∈ Ā be the setof maximal elements in Ā ⊆ A at R i ∈ R i .3
A social choice function is a single-valued function f : R → A that assigns a
feasible outcome a ∈ A to eacha social choice¯ preference profile R ∈ R . Givenª©
function f , let O i (R) := a ∈ A ¯ a = f (R i′ , R −i ) for some R i′ ∈ R i be agent i ’s option set at R ∈ R . Note that O i (R) = O i (R i′ , R −i ) for all R ∈ R , all i ∈ N , and all
R i′ ∈ R i .
Let M i denote a message space of agent i ∈ N . We call m i ∈ M i a message ofagent i ∈ N . A mechanism is a pair Γ = (M , g ), where M := M 1 × M 2 × · · · × M n
and g : M → A is an outcome function. A mechanism (M , g ) is called a directrevelation mechanism if M i = R i for all i ∈ N . Given a social choice function f ,a mechanism (M , g ) is called the associated direct revelation mechanism if M i =R i for all i ∈ N and g = f . A message profile is denoted by m = (m 1 , m 2 , . . . , m n ) ∈M.
A message profile m ∗ = (m 1∗ , m 2∗ , . . . , m n∗ ) ∈ M is a Nash equilibrium of (M , g )∗∗at R ∈ R if, for any i ∈ N , g (m i∗ , m −i
)R i g (m i′ , m −i
) for any m i′ ∈ M i . Let NE Γ (R) ⊆M denotethe set of Nash equilibria of Γ = (M , g ) at R ∈ R . Let g (NE Γ (R)) :=¯ª©
¯a ∈ A a = g (m) for some m ∈ NE Γ (R) be the set of Nash equilibrium outcomesof Γ = (M , g ) at R ∈ R .
A message profile m ∗ = (m 1∗ , m 2∗ , . . . , m n∗ ) ∈ M is a dominant strategy equilib′′
rium of (M , g ) at R ∈ R if, for any i ∈ N , g (m i∗ , m −i
)R i g (m i′ , m −i
) for any m i′ ∈ M i′
and any m −i
∈ M −i . Let DSE Γ (R) ⊆ M be the set¯ of dominant strategy equilibria©
ªof Γ = (M , g ) at R ∈ R . Let g (DSE Γ (R)) := a ∈ A ¯ a = g (m) for some m ∈ DSE Γ (R)be the set of dominant strategy equilibrium outcomes of Γ = (M , g ) at R ∈ R .
A mechanism Γ = (M , g ) Nash implements a social choice function f if g (NE Γ (R)) =f (R) for any R ∈ R .4 A social choice function is Nash implementable if there exists a mechanism that Nash implements it. A social choice function is directly
implementable in Nash equilibria if there exists a direct revelation mechanism
which Nash implements it.
A direct revelation mechanism Γ = (R , g ) truthfully Nash implements a social choice function f if R ∈ NE Γ (R) and g (R) = f (R) for any R ∈ R .5 A social
choice function is truthfully implementable in Nash equilibria if there exists a
direct revelation mechanism which truthfully Nash implements it.
A direct revelation mechanism Γ = (R , g ) fully-truthfully Nash implements
a social choice function f if R ∈ NE Γ (R) and g (NE Γ (R)) = f (R) for any R ∈ R .
A social choice function is fully-truthfully implementable in Nash equilibria if
3 Note that argmax R may be empty.
Ā i©
ª
4 To simplify notation, we write f (R) instead of f (R) .

5 As we focus on social choice functions, truthful Nash implementation can be defined as R ∈NE Γ (R) and g (R) = f (R) for any R ∈ R , instead of as R ∈ NE Γ (R) and g (R) ∈ f (R) for any R ∈ R .

5there exists a direct revelation mechanism which fully-truthfully implements it
in Nash equilibria.
A mechanism Γ = (M , g ) dominant strategy implements a social choice function f if g (DSE Γ (R)) = f (R) for any R ∈ R . A social choice function is dominant
strategy implementable if there exists a mechanism that dominant strategy implements it. A direct revelation mechanism Γ = (R , g ) truthfully dominant strategy implements a social choice function f if R ∈ DSE Γ (R) and g (R) = f (R) for any
R ∈ R.

3 Characterizations
In this section, we seek to characterize social choice functions which are fullytruthfully implementable in Nash equilibria.
We begin by proving the associated direct revelation principle, which saysthat when attention is restricted to truthfully implementable social choice functions, the class of social choice functions that are directly implementable in
Nash equilibria is equivalent to that of social choice functions which can be
Nash implemented by the associated direct revelation mechanisms.
Theorem 1 (The Associated Direct Revelation Principle). A social choice function f is fully-truthfully implementable in Nash equilibria if and only if it isfully-truthfully implemented in Nash equilibria by the associated direct revelation mechanism.
Proof. The if part. This part follows straight from the definition of full-truthful
Nash implementation.
The only if part. Let Γ = (R , f ) denote the associated direct revelation mechanism. Since f is fully-truthfully implementable in Nash equilibria, there is adirect revelation mechanism Γ̄ = (R , g ) such that R ∈ NE Γ̄ (R) and g (NE Γ̄ (R)) =f (R) for all R ∈ R . Since Γ̄ truthfully implements f in Nash equilibria, we haveg = f by definition, which implies Γ̄ = Γ. Hence, R ∈ NE Γ (R) and g (NE Γ (R)) =f (R) for all R ∈ R .
The following example demonstrates that if we give up truthful implementation in Nash equilibria, then there is a social choice function that cannot be
Nash implemented by the associated direct revelation mechanism, but which is
directly Nash implementable.
Example 1. Consider an environment (N , A, R ) such that #N = 2, A = {a, b, c},
R = {R 1 , R̄ 1 } × {R 2 , R̄ 2 }, and aP i bP i c and c P̄ i a P̄ i b for all i ∈ N . A social choicefunction f is given as follows.

f =

R2
a
a
6

R̄ 2
a
c

R1
R̄ 1

Then, f cannot be Nash implemented by the associated direct revelation
mechanism Γ = (R , f ). This is because f (NE Γ (R̄ 1 , R̄ 2 )) = {a, c} 6= {c} = f (R̄ 1 , R̄ 2 ),©
ªsince NE Γ (R̄ 1 , R̄ 2 ) = (R 1 , R 2 ), (R̄ 1 , R̄ 2 ) .
However, another direct revelation mechanism Γ̄ = (R , g ) can Nash implement f , where g is defined below.

g=

R2
c
a

R̄ 2
a
b

R1
R̄ 1

©
ª
©
ª
Since NE Γ̄ (R 1 , R 2 ) = (R 1 , R̄ 2 ), (R̄ 1 , R 2 ) , NE Γ̄ (R 1 , R̄ 2 ) = (R̄ 1 , R 2 ) , NE Γ̄ (R̄ 1 , R 2 ) =©
ª(R 1 , R̄ 2 ) , and NE Γ̄ (R̄ 1 , R̄ 2 ) = {(R 1 , R 2 )}, we have g (NE Γ̄ (R 1 , R 2 )) = {a} = f (R 1 , R 2 ),g (NE Γ̄ (R 1 , R̄ 2 )) = {a} = f (R 1 , R̄ 2 ), g (NE Γ̄ (R̄ 1 , R 2 )) = {a} = f (R̄ 1 , R 2 ), and g (NE Γ̄ (R̄ 1 , R̄ 2 )) ={c} = f (R̄ 1 , R̄ 2 ), respectively. Thus, f can be Nash implemented by the directrevelation mechanism Γ̄, although it cannot be Nash implemented by the associated direct revelation mechanism Γ. Note that f cannot be truthfully implemented in Nash equilibria by Γ̄, although it can be truthfully implemented in
Nash equilibria by Γ.
äInvoking the associated direct revelation principle, we restrict attention to
the associated direct revelation mechanisms hereafter. We next identify a condition which is necessary for full-truthful Nash implementation by the associateddirect revelation mechanisms.
Restricted monotonicity is a version of monotonicity 6 (Maskin (1999)), which
requires the following. Suppose a change from R to R ′ . Then, for each agenti ∈ N , if any outcome that was weakly worse for her than f (R) in her option set
at R when her preference relation was R i remains weakly worse for her than f (R)when her preference relation is R i′ , then f (R) must still be f -optimal at R ′ .
Definition 1 (Restricted Monotonicity). A social choice function f satisfies restricted monotonicity if, for all R, R ′ ∈ R , if LC i ( f (R); R i ) ∩ O i (R) ⊆ LC i ( f (R); R i′ )for all i ∈ N , then f (R ′ ) = f (R).
Remark 1. Restricted monotonicity is stronger than monotonicity by definition.
Remark 2. The definition of restricted monotonicity can be rewritten as follows.
A social choice function f satisfies restricted monotonicity if, for all R ∈ R and alli ∈ N , there is a set C i ( f (R); R) ⊆ O i (R) with f (R) ∈ arg maxC i ( f (R);R) R i such thatfor all R ′ ∈ R , if f (R) ∈ arg maxC i ( f (R);R) R i′ for all i ∈ N , then f (R ′ ) = f (R). Thisway of defining restricted monotonicity is analogous to that of defining Condition µ (Moore and Repullo (1990)).
6 A social choice function f satisfies monotonicity if, for all R,R ′ ∈R , if LC i ( f (R);R i ) ⊆LC i ( f (R);Ri′ ) for all i ∈ N , then f (R ′ ) = f (R). Note that monotonicity is a necessary condition
for Nash implementation and is part of the sufficient condition for Nash implementation when
there are three or more agents.

7

Since restricted monotonicity is stronger than monotonicity by Remark 1, it
is not clear whether restricted monotonicity is a necessary condition for Nash
implementation. The following lemma states that restricted monotonicity isnecessary for full-truthful implementation in Nash equilibria by the associateddirect revelation mechanisms.
Lemma 1. If a social choice function f is fully-truthfully implemented in Nashequilibria by the associated direct revelation mechanism, then it satisfies restrictedmonotonicity.
Proof. Pick any R, R̄ ∈ R such that LC i ( f (R); R i ) ∩ O i (R) ⊆ LC i ( f (R); R̄ i ) for alli ∈ N . Let Γ = (R , f ) denote the associated direct revelation mechanism. Since
f is truthfully implemented in Nash equilibria by Γ, we have R ∈ NE Γ (R).
Since R ∈ NE Γ (R), it holds that for all i ∈ N , f (R)R i f (R i′ , R −i ) for all R i′ ∈ R i .
This implies f (R) ∈ arg maxO i (R) R i for all i ∈ N . So, LC i ( f (R); R i )∩O i (R) = O i (R)for all i ∈ N .
Thus, since LC i ( f (R); R i )∩O i (R) ⊆ LC i ( f (R); R̄ i ) for all i ∈ N , we have O i (R) ⊆LC i ( f (R); R̄ i ) for all i ∈ N . So, R ∈ NE Γ (R̄). Since f is Nash implemented by Γ,f (R) ∈ f (NE Γ (R̄)) = f (R̄). This implies f (R̄) = f (R), because f is a single-valued
function.
We are now ready to characterize fully-truthfully implementable social choicefunctions in Nash equilibria. Theorem 2 below says that restricted monotonicity
together with an auxiliary condition called boundedness is both necessary andsufficient for full-truthful Nash implementation. It should be noted that Theorem 2 holds even when n = 2.
Definition 2 (Boundedness). A social choice function f satisfies boundedness if
arg maxO i (R) R i 6= ; for all R ∈ R and all i ∈ N .
Remark 3. As we focus on implementation by the associated direct revelation
mechanisms, imposing boundedness on a social choice function is equivalent
to requiring the associated direct revelation mechanism to satisfy the best response property 7 (Jackson et al. (1994)). As mentioned by Jackson et al. (1994),
the best response property would be an appropriate restriction in order for the
Nash equilibrium concept to make sense. Theorem 2 shows that the restriction
is not only sufficient but also necessary for a social choice function to be fullytruthfully implementable in Nash equilibria.
Theorem 2. A social choice function f is fully-truthfully implementable in Nashequilibria if and only if it satisfies restricted monotonicity and boundedness.
Proof. Let Γ = (R , f ) denote the associated direct revelation mechanism.
The if part. Step 1: f (R) ∈ arg maxO i (R) R i for all R ∈ R and all i ∈ N .
7 A mechanism (M, g ) satisfies the best response property if, for all R ∈R , all i ∈ N , and allm −i ∈ M−i , there exists m i ∈ Mi such that g (m i ,m −i )Ri g (m i′ ,m −i ) for all m i′ ∈ Mi .

8Suppose to the contrary that f (R) 6∈ arg maxO i (R) R i for some R ∈ R and some i ∈N . Let b ∈ A be such that b ∈ arg maxO i (R) R i .8 Then, b 6= f (R). Since b ∈ O i (R),b = f (R̄ i , R −i ) for some R̄ i ∈ R i .
Since f (R̄ i , R −i ) = b ∈ arg maxO i (R) R i , it holds that LC i ( f (R̄ i , R −i ); R̄ i )∩O i (R) ⊆LC i ( f (R̄ i , R −i ); R i )∩O i (R). So, it follows from O i (R) = O i (R̄ i , R −i ) that LC i ( f (R̄ i , R −i ); R̄ i )∩O i (R̄ i , R −i ) ⊆ LC i ( f (R̄ i , R −i ); R i ) ∩ O i (R̄ i , R −i ). This implies LC i ( f (R̄ i , R −i ); R̄ i ) ∩O i (R̄ i , R −i ) ⊆ LC i ( f (R̄ i , R −i ); R i ), because LC i ( f (R̄ i , R −i ); R i )∩O i (R̄ i , R −i ) ⊆ LC i ( f (R̄ i , R −i ); R i ).
Thus, since LC j ( f (R̄ i , R −i ); R j ) ∩O j (R̄ i , R −i ) ⊆ LC j ( f (R̄ i , R −i ); R j ) for all j 6= i , restricted monotonicity implies f (R) = f (R̄ i , R −i ), which contradicts f (R) 6= b =f (R̄ i , R −i ).
Step 2: f satisfies strategy-proofness.9
Since f (R) ∈ arg maxO i (R) R i for all R ∈ R and all i ∈ N by Step 1, it follows fromthe definition of the option set that f (R)R i f (R i′ , R −i ) for all R ∈ R , all i ∈ N , and
all R i′ ∈ R i . Thus, f satisfies strategy-proofness.
Step 3: f is fully-truthfully Nash implementable.
Pick any R ∈ R . Since f satisfies strategy-proofness by Step 2, it is truthfully
implemented in dominant strategy equilibria by Γ, i.e., R ∈ DSE Γ (R) for all R ∈R . So, R ∈ NE Γ (R) for all R ∈ R .
Suppose R̄ ∈ NE Γ (R). Then, for any i ∈ N , f (R̄)R i f (R i′ , R̄ −i ) for any R i′ ∈ R i .
This implies f (R̄) ∈ arg maxO i (R̄) R i for all i ∈ N , implying LC i ( f (R̄); R i ) ∩O i (R̄) =O i (R̄) for all i ∈ N . So, since LC i ( f (R̄); R̄ i ) ∩ O i (R̄) ⊆ O i (R̄) for all i ∈ N , wehave LC i ( f (R̄); R̄ i ) ∩ O i (R̄) ⊆ LC i ( f (R̄); R i ) ∩ O i (R̄) for all i ∈ N . This implies
LC i ( f (R̄); R̄ i ) ∩ O i (R̄) ⊆ LC i ( f (R̄); R i ) for all i ∈ N , since LC i ( f (R̄); R i ) ∩ O i (R̄) ⊆LC i ( f (R̄); R i ) for all i ∈ N . Therefore, restricted monotonicity implies f (R) =f (R̄). So, f (R) = f (R̄) for any R̄ ∈ NE Γ (R). This implies f (NE Γ (R)) = f (R). Thus,
f (NE Γ (R)) = f (R) for all R ∈ R .
The only if part. By Theorem 1, if f is fully-truthfully Nash implementable,
then it is fully-truthfully Nash implemented by Γ. So, Lemma 1 implies that fsatisfies restricted monotonicity.
Since f is fully-truthfylly Nash implemented by Γ, it holds that R ∈ NE Γ (R)for all R ∈ R , i.e., f (R)Ri f (R i′ , R −i ) for all R ∈ R , all i ∈ N , and all R i′ ∈ R i . Thisimplies f (R) ∈ arg maxO i (R) R i for all R ∈ R and all i ∈ N . Thus, f satisfies boundedness.
We end this section by briefly discussing the redundancy of boundedness
in characterizing fully-truthfully implementable social choice functions in Nashequilibria. The following is due to Dasgupta et al. (1979).

8 It should be noted that arg max
O i (R) R i 6= ; by boundedness.
9 A social choice function f satisfies strategy-proofness if, for all R ∈Ri′ ∈ R i such that f (Ri′ ,R−i )P i f (R).

9

R and all i ∈ N, there is noProposition 1 (Dasgupta et al. (1979)). Suppose that R is rich.10 Then, if a social
choice function satisfies monotonicity, then it satisfies strategy-proofness.
Proposition 1 together with Remark 1 implies that restricted monotonicity implies strategy-proofness if R is rich. So, restricted monotonicity implies
boundedness if R is rich. Moreover, if A is finite, then boundednes is automatically satisfied by the completeness and transitivity of preferences regardless ofwhether or not R is rich. Thus, we have the following corollary.
Corollary 1. Suppose that either (i) A is finite or (ii) R is rich. Then, a social
choice function is fully-truthfully implementable in Nash equilibria if and only if
it satisfies restricted monotonicity.

4 The Relationship to Secure Implementation
In this section, we explore the relationship of full-truthful Nash implementation
to secure implementation11 (Saijo et al. (2005)), which is identical with double
implementation in dominant strategy equilibria and Nash equilibria.
We begin by showing a limitation of full-truthful Nash implementation, whichstems mainly from Proposition 2 (Dasgupta et al. (1979)).
Proposition 2 (Dasgupta et al. (1979)). A social choice function is truthfully implemented in Nash equilibria by a direct revelation mechanism if and only if it istruthfully implemented in dominant strategy equilibria by the same direct revelation mechanism.
Theorem 3. If a social choice function f is fully-truthfully Nash implemented by
the associated direct revelation mechanism, then it is dominant strategy implemented by the associated direct revelation mechanism.
Proof. Let Γ = (R , f ) denote the associated direct revelation mechanism. Since
f is truthfully implemented in Nash equilibria by Γ, Proposition 2 implies that itis truthfully implemented in dominant strategy equilibria by Γ. So, R ∈ DSE Γ (R)for all R ∈ R , implying R ∈ DSE Γ (R) ⊆ NE Γ (R) for all R ∈ R . This implies f (DSE Γ (R)) ⊆f (NE Γ (R)) for all R ∈ R . Thus, f (DSE Γ (R)) = f (NE Γ (R)) = f (R) for all R ∈ R ,because f (NE Γ (R)) = f (R) for all R ∈ R , and because f is a single-valued function.
The following example demonstrates that the converse to Theorem 3 does
not hold in general, which is in contrast to Proposition 2.
10 A domain

R is rich (Dasgupta et al. (1979)) if, for any R,R ′ ∈ R , any a, a ′ ∈ A, and any i ∈ N,

if aRi a ′ implies aRi′ a ′ and aP i a ′ implies aP i′ a ′ , then there exists R ′′ ∈ R such that LC i (a;Ri ) ⊆LC i (a;Ri′′ ) and LC i (a ′ ;Ri′ ) ⊆ LC i (a ′ ;Ri′′ ). Examples of rich domains are found in Dasgupta et al.

(1979).
11 A mechanism Γ = (M, g ) securely implements a social choice function f if g (DSE Γ (R)) =g (NE Γ (R)) = f (R) for any R ∈ R . A social choice function f is securely implementable if there
exists a mechanism which securely implements it.

10

Example 2. Consider an environment (N , A, R ) for which #N = 2, A = {a, b, c},and R = {R 1 , R̄ 1 } × {R 2 , R̄ 2 }, where aP 1 cP 1 b, b P̄ 1 c P̄ a, aI 2 bP 2 c, and a P̄ 2 b I¯2c. A
social choice function f is defined below.

f =

R2
b
b

R̄ 2
a
c

R1
R̄ 1

Then, it is easy to check that f can be dominant strategy implemented by the
associated direct revelation mechanism, but cannot be fully-truthfully Nash implemented by the associated direct revelation mechanism.
ä
Theorem 3 together with the revelation principle leads to the following corollary, which indicates the relationship of full-truthful Nash implementation tosecure implementation.
Corollary 2. A social choice function is securely implemented by the associateddirect revelation mechanism if and only if it is fully-truthfully Nash implemented
by the associated direct revelation mechanism.
Corollary 3 below follows directly from Theorems 1 and 2, Corollary 2, andresults of Saijo et al. (2005) for secure implementation.
Corollary 3. The following statements are equivalent:(i) f is fully-truthfully implementable in Nash equilibria,(ii) f is securely implementable,(iii) f is robustly implemented in Bayesian Nash equilibria by the associated direct revelation mechanism,(iv) f satisfies restricted monotonicity and boundedness,(v) f satisfies the rectangular property12 (Saijo et al. (2005)) and strategy-proofness.
Corollary 3 tells us that full-truthful Nash implementation is equivalent tosecure implementation, which sheds light on the structure of secure implementation. Corollary 3 also provides an alternative characterization of securely implementable social choice functions. In contrast to the characterization by Saijoet al. (2005), our characterization has an advantage of using a version of monotonicity, which is familiar to literature on implementation theory.

12 A social choice function f satisfies the rectangular property if, for all R,R ′ ∈R , if′ ) for all i ∈ N, then f (R ′ ) = f (R).
f (R ′ )I i f (Ri ,R−i

11

5 Conclusion
In this paper, we have shown that restricted monotonicity together with boundedness is both necessary and sufficient for full-truthful Nash implementation.
Moreover, by proving the equivalence of full-truthful Nash implementation andsecure implementation, we have provided an alternative characterization of securely implementable social choice functions. Our characterization sheds newlight on the structure of securely implementable social choice functions in termsof monotonicity, a well-known property in implementation theory.
It is true that the requirement of truth telling by each agent being a Nashequilibrium is appealing. But, as demonstrated in Example 1, the requirement
restricts the class of Nash implementable social choice functions by direct revelation mechanisms. Direct revelation mechanisms have been recently received
a great deal of attention from both theoretical and practical viewpoints. So, aninteresting topic for further research is to identify necessary and sufficient conditions for Nash implementation by direct revelation mechanisms.

12

References
A BDULKADIRO ĞLU , A. AND T. S ÖNMEZ (2003): “School Choice: A Mechanism
Design Approach,” American Economic Review, 93, 729–747.
C ASON , T. N., T. S AIJO, T. S JÖSTRÖM , AND T. YAMATO (2006): “Secure Implementation Experiments: Do Strategy-Proof Mechanisms Really Work?” forthcoming in Games and Economic Behavior.
D ASGUPTA , P., P. J. H AMMOND, AND E. M ASKIN (1979): “The Implementation ofSocial Choice Rules: Some General Results on Incentive Compatibility,” Review of Economic Studies, 46, 185–216.
D UTTA , B. AND A. S EN (1991): “A Necessary and Sufficient Condition for TwoPerson Nash Implementation,” Review of Economic Studies, 58, 121–128.
H URWICZ , L. (1960): “Optimality and Informational Efficiency in Resource Allocation Processes,” in Mathematical Methods in the Social Sciences, ed. by K. J.
Arrow, S. Karlin, and P. Suppes, Stanford University Press, 27–46.
J ACKSON , M. O. (1992): “Implementation in Undominated Strategies: A Look at
Bounded Mechanisms,” Review of Economic Studies, 59, 757–775.
J ACKSON , M. O., T. R. PALFREY, AND S. S RIVASTAVA (1994): “Undominated Nash
Implementation in Bounded Mechanisms,” Games and Economic Behavior,
6, 474–501.
M ASKIN , E. (1999): “Nash Equilibrium and Welfare Optimality,” Review of Economic Studies, 66, 23–38.
M OORE , J. AND R. R EPULLO (1990): “Nash Implementation: A Full Characterization,” Econometrica, 58, 1083–1099.
ROTH , A. E. (1984): “The Evolution of the Labor Market for Medical Interns andResidents: A Case Study in Game Theory,” Journal of Political Economy, 92,
991–1016.
ROTH , A. E., T. S ÖNMEZ , AND M. U. Ü NVER (2004): “Kidney Exchange,” Quarterly Journal of Economics, 119, 457–488.
S AIJO, T., T. S JÖSTRÖM , AND T. YAMATO (2005): “Secure Implementation,”
mimeo., Osaka University.
S JÖSTRÖM , T. (1991): “On the Necessary and Sufficient Conditions for Nash Implementation,” Social Choice and Welfare, 8, 333–340.
TATAMITANI , Y. (2001): “Implementation by Self-Relevant Mechanisms,” Journalof Mathematical Economics, 35, 427–444.

13