Chapter 4

Nash Implementation

We start with a motivating example called the King Solomon’s problem. Two
females and a child appear in the court of King Solomon. Both females claim
to be the mother of the child and want the king to allocate the custody of
the child to the true mother. The king who has no prior information on the
problem tells them that if they both agree on the true mother, the custody
will be given to her, but if they disagree, the child would be cut into halves
and both will get a half each. One of the females immediately gives up her
claim, and the king decides to give her the custody.
In this problem, we observe two possible states of the world : where one
of the females is the true mother. In either state, both females prefer getting
custody over not getting it. Both females know the true state, but the
king does not. The king’s problem is to assign the custody to the mother
corresponding to the true state. In order to know the true state, the king
designs what we call a mechanism: he wants each claimant to report her
preference over (a) getting the child herself, (b) the other claimant getting
the child and (c) getting a half of the child. He interprets giving up the claim
as a sign of the true mother. This problem has all the features of a complete
information implementation problem as described below.
Like in Chapter 3, let N be a set of agents and A a finite set of alternatives.
Further, we introduce a set of states of the world: ⇥ = {✓, , , . . .}. In the
context of voting, these may represent di↵erent preference profiles, e.g., in
a two person two alternative case with strict preferences, there can be four
states, each representing a di↵erent preference profile. Let Ri (✓) represent the
strict preferences of agent i 2 N at state ✓ 2 ⇥. In Chapter 3, we introduced
the notion of a social choice correspondence assigning a non-empty subset of
alternatives to each preference profile, or state. We will now use the notation
F to denote this correspondence, and F (✓) to denote the set of alternatives
assigned to state ✓. A social choice correspondence specifies the objectives of

51
52 CHAPTER 4. NASH IMPLEMENTATION

the planner or mechanism designer. The mechanism designer does not know
the true state, but it is common knowledge for the agents. Such a setting is
referred to as a complete information mechanism design problem.
Definition 4.1 (Mechanism). A mechanism G is an n+1-tuple (M1 , . . . , Mn ; g)
where Mi refers to a set of messages for agent i and g is a mapping g :
M1 ⇥ . . . ⇥ Mn ! A.
For every ✓, the pair (G, ✓) induces a normal form game where Mi is the
strategy set of agent i and g is an outcome function. The payo↵s of the agents
from each outcome can be derived from their preferences in the current state.
Let NE(G, ✓) be the set of Nash equilibria of this game:

NE(G, ✓) = {m̄ 2 M1 ⇥ . . . ⇥ Mn : g(m̄)Ri (✓)g(mi , m̄ i )8i, 8mi 6= m̄i }

Definition 4.2 (Nash Implementation). A mechanism G implements the

social choice correspondence F in Nash equilibrium if g(N E(G, ✓)) = F (✓)
for all ✓.
The primary question in implementation theory is to identify the set of
social choice correspondences that can be implemented in an equilibrium.
King Solomon’s problem is to implement the social choice rule f : {✓, } !
{a, b, c} where f (✓) = a and f ( ) = b. Does his mechanism implement it?
Unfortunately, in either state, announcing the wrong mother is a dominant
strategy for both females.
Maskin (1999) provided the necessary and sufficient conditions for imple-
mentation in Nash equilibrium. We first present these conditions.
Let L(a, i, ✓) be set of alternatives agent i prefers less than a at ✓:

L(a, i, ✓) = {b 2 A : aRi (✓)b}.

With this notation, the monotonicity condition of last Chapter 3.15 can
be restated as follows.
Definition 4.3 (Maskin monotonicity). A social choice correspondence F
satisfies Maskin monotonicity if for any a 2 A, ✓, 2 ⇥,

[a 2 F (✓), L(a, i, ✓) ⇢ L(a, i, )8i] ) a 2 F ( ). (4.1)

Alternatively, F satisfies Maskin monotonicity if for any a 2 A, ✓, 2 ⇥,

[a 2 F (✓) F ( )] ) 9i 2 N and b 2 A : aRi (✓)b and bPi ( )a (4.2)

 53

Condition (4.1) says that a social choice correspondence is Maskin-monotonic

if for every chosen alternative in a given state the lower contour sets of every
agent are subsets of respective lower contour sets in another state, then the
alternative chosen in the former state must belong to the set of potential
alternative in the latter state. Alternatively, (4.2) says that a a social choice
correspondence is Maskin-monotonic if for every alternative chosen in a state
but not chosen in another, there exists an agent and another distinct alter-
native such that the agent prefers the former alternative to the latter in the
former state but strictly prefers the latter alternative to the former in the
latter state.

Exercise 4.0.1. Check that the following social choice correspondences are
Maskin-monotonic:

• A dictatorial social choice correspondence;

• The Pareto efficient social choice correspondence;

• Walrasian correspondence in exchange economies when all Walrasian

allocations are interior;

• Individually rational correspondence in exchange economies;

• Pareto efficient and individually rational social choice correspondence

in exchange economies.

Exercise 4.0.2. Show that if two social choice correspondences F and G

are Maskin-monotonic and F (✓) \ G(✓) 6= ; for every ✓ 2 ⇥, then F \ G is
Maskin-monotonic.

Exercise 4.0.3. Check that no scoring rule ( e.g., plurality rule) is Maskin-
monotonic.

The following condition requires that if at least n 1 agents prefer any

alternative over all others at any state, the alternative must be one of the
potential selections.

Definition 4.4 (No veto power). A social choice correspondence F satisfies

no veto power if for all a 2 A and all ✓ 2 ⇥,

[|{i 2 N : aRi (✓)b for all b 2 A}| n 1] ) a 2 F (✓) (4.3)

Maskin’s result is now presented below.

54 CHAPTER 4. NASH IMPLEMENTATION

Theorem 4.1 (Maskin (1999)). If a social choice correspondence is imple-

mentable in Nash equilibrium, then it must satisfy Maskin monotonicity.
Conversely, if n 3, every social choice correspondence satisfying Maskin
monotonicity and no veto power must be implementable in Nash equilibrium.

Proof. Suppose mechanism (M, g) implements F in Nash equilibrium, a 2

F (✓), and L(a, i, ✓) ⇢ L(a, i, ). Then there must exist m̄ 2 M such that
g(m̄) = a and m̄ is a Nash equilibrium of g at ✓. Therefore, g(mi , m̄ i ) ⇢
L(a, i, ✓) for all mi 2 Mi . By our hypothesis, g(mi , m̄ i ) ⇢ L(a, i, ) for all
mi 2 Mi . This implies m̄ is also a Nash equilibrium at and produces a
as an outcome. Since (M, g) implements F , a 2 F ( ). Hence the necessary
part.
Suppose n 3 and F is a social choice correspondence satisfying Maskin
monotonicity and no veto power. We construct a mechanism which imple-
ments F in Nash equilibrium. Let

Mi = {(ai , ✓i , ni , bi , ci ) 2 A ⇥ ⇥ ⇥ N ⇥ A ⇥ A | ai 2 F (✓i )},

where N is the set of all integers.

The game form g : M ! A is described as follows:

1. if mi = (a, ✓, . . .) for all i 2 N , then g(m) = a;

2. if mi = (a, ✓, . . .) for all i 2 N {j}, and mj = (aj , , nj , bj , cj ) then

⇢
bj if bj 2 L(a, j, ✓),
g(m) =
a otherwise.

Notice that this specification is well-defined only if n 3.

3. Otherwise, g(m) = ck where k is the lowest index of the agents an-

nouncing the highest integer: k = arg min{i 2 N | ni nj 8j =
6 i}.

Let ✓ 2 ⇥ be the true state and let a 2 F (✓). We prove F (✓) =

g(N E(G, ✓)) using two claims.
Claim 1. F (✓) ⇢ g(N E(G, ✓)).

Proof. Consider m̄i = (a, ✓, . . .) for all i 2 N . Then g(m̄) = a. If j deviates,

g results in bj 2 L(a, j, ✓). Therefore, m̄ 2 N E(G, ✓). Hence the claim.

Claim 2. g(N E(G, ✓)) ⇢ F (✓).

 55

Proof. Let m̄ 2 N E(G, ✓). We will show that g(m̄) 2 F (✓). Consider the
two cases:
Case 1: m̄i = (a, , . . .) for all i 2 N . Then g(m̄) = a. By construction,
{g(mi , m̄ i ) | mi 2 Mi } = L(a, i, ) for all i 2 N . Since m̄ is a Nash
equilibrium of G at ✓, we must have L(a, i, ) ⇢ L(a, i, ✓) for all i 2 N . Since
a 2 F ( ), by Maskin monotonicity, a 2 F (✓).
Case 2: Case 1 does not hold. Let g(m̄) = a. By making an arbitrarily
high integer announcement, any agent can influence selection of any arbitrary
b 2 A: {g(mi , m̄ i ) | mi 2 Mi } = A for all i except possibly some j when
all agents other than j announce (a, , . . .). Since m̄ is a Nash equilibrium
under G at , it must be that aRi (✓)b for all b 2 A for all i 2 N j. Since
F satisfies no veto power, a 2 F (✓).

Remark. Notice that Maskin’s result is applicable with three or more agents.
Additional conditions are required for Nash implementation when there are
only two agents. Suppose agent 1 sends the message (a, ✓) and agent 2 sends
(b, ). It could be that 1 is deviating from the Nash equilibrium resulting in
b at ; alternatively, 2 may be deviating from the Nash equilibrium outcome
a at ✓. Hence the resulting outcome must be in both L(b, 1, ) and L(a, 2, ✓).
A necessary condition for Nash implementation in two-person case is the
following:

For all ✓, 2 ⇥ and a, b 2 A such that a 2 F (✓) and b 2 F ( ),

L(b, 1, ) \ L(a, 2, ✓) 6= ;.

The notion of implementation can be extended beyond Nash equilibrium

to many of its refinements and other equilibrium notions. Interestingly, the
range of social choice correspondences that can be implemented in many
of these equilibria is larger than the set of Maskin monotonic social choice
correspondences. See Jackson (2001) for a survey.