Discussion Papers In Economics
And Business

Dominant Strategy Implementationin Pure Exchange Economies
Hideki Mizukami
Takuma Wakayama

Discussion Paper 04-03-Rev.

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANDominant Strategy Implementationin Pure Exchange Economies
Hideki Mizukami
Takuma Wakayama

Discussion Paper 04-03-Rev.

March 2005

この研究は「大学院経済学研究科・経済学部記念事業」
基金より援助を受けた、記して感謝する。

Graduate School of Economics andOsaka School of International Public Policy (OSIPP)
Osaka University, Toyonaka, Osaka 560-0043, JAPANDominant Strategy Implementationin Pure Exchange Economies∗
Hideki Mizukami†‡
Faculty of Economics, Toyama University
E-mail: mizukami@eco.toyama-u.ac.jp

andTakuma Wakayama
Graduate School of Economics, Osaka University
E-mail: wakayama@iser.osaka-u.ac.jp

March 1, 2005∗

We are especially grateful to Tomas Sjöström, whose note led to improvements of thecontents. We are also grateful to Masaki Aoyagi, Atsushi Kajii, Tatsuyoshi Saijo, Toyotaka
Sakai, James Schummer, Koji Takamiya, Yoshikatsu Tatamitani, Naoki Yoshihara, and seminar participants at the 10th Decentralization Conference in Japan, the 2004 Spring Meetingof the Japanese Economic Association, and the 7th International Meeting of the Society forSocial Choice and Welfare for their valuable and helpful comments and suggestions.
†
The author gratefully acknowledges financial support from the Ministry of Education,
Culture, Sports, Science and Technology, Grant-in-Aid for 21st Century COE Program “Interfaces for Advanced Economic Analysis.”‡
Correspondent: Faculty of Economics, Toyama University, 3190 Gofuku, Toyama 9308555, JAPAN. Fax: 81-(0)76-445-6419.

1

Abstract
In this paper, we consider dominant strategy implementation inclassical pure exchange economies with free disposal. We show thatquasi-strong-non-bossiness and strategy-proofness together are necessary and sufficient for dominant strategy implementation via the directrevelation mechanism. Moreover, we prove that strategy-proofness issufficient for dominant strategy implementation, by using an augmented revelation mechanism similar to the one devised by Jackson
et al. (1994). This implies that, in classical pure exchange economies,
dominant strategy implementability by a certain indirect mechanism
is equivalent to truthful implementability in dominant strategy equilibria.
Keywords: Quasi-strong-non-bossiness, Strategy-proofness, Augmented
Revelation Mechanism, The Revelation Principle.
JEL Classification Numbers: D51, C72, D71, D78.

2

1 Introduction
The revelation principle asserts that if a social choice function is implementable in dominant strategy equilibria, then it is truthfully implementable
in dominant strategy equilibria (i.e., truthful revelation by each agent is adominant strategy equilibrium of the direct revelation mechanism). However, the direct revelation mechanism might have untruthful dominant strategy equilibria, so it might fail to fully implement the social choice function(e.g., see Dasgupta et al. (1979) for dominant strategy implementation, andPostlewaite and Schmeidler (1986), Repullo (1986), and Palfrey and Srivastava (1989) for Bayesian implementation). Since, as is well-known, thismultiple equilibrium problem depends on the possibility of indifference inpreferences, the problem can arise in a classical pure exchange economy.
Example 1 (A Multiple Equilibrium Problem in an Exchange Economy).
Consider a two-agent, two-good exchange economy with initial endowment point ω = ((6, 4), (4, 6)). Each agent i ∈ {1, 2} has two possible types
θi , θ0i . Agent 1 has preferences represented by 2u1 ((x11 , x21 ); θ1 ) = x11 x21

and

 2
u1 ((x11 , x21 ); θ01 ) = x11 x21 ;and agent 2 has preferences represented byu2 ((x12 , x22 ); θ2 ) = x12 x22

andu2 ((x12 , x22 ); θ02 ) = 1/2  1/2 2
x12
+ x22
.

Consider an individually rational social choice function f defined by

f =

θ2
z
ω

θ02
ω
ω

θ1
θ01

where z = ((4, 6), (6, 4)). The social choice function can be fully implemented in dominant
strategyequilibria by an indirect mechanism Γ =
o n
o 
n
0 , 1 such that
m1 , m01 , m00
×
m
,
m
2
2
1

1=

m2
z
ω
ω

m02
ω
ω
y

m1
m01
m00
1

where y = ((7.5, 1.5), (2.5, 8.5)).1 In the mechanism Γ, agent 1’s dominant
strategy is m1 if her type is θ1 , and m01 if θ01 ; and agent 2’s dominant strategy
1This type of indirect mechanism is called an augmented revelation mechanism (seeMookherjee and Reichelstein (1990)).

3

θ01

θ1

O2

z

ω
y
O1

θ2

θ02

Figure 1: A Two-agent, Two-good Exchange Economy
is m2 if her type is θ2 , and m02 if θ02 . Hence, Γ fully implements f in dominant
strategy equilibria.
Since f is dominant strategy implementable, the revelation principle
implies that telling then trutho is na dominanto  strategy of the direct revela000tion mechanism Γ = θ1 , θ1 × θ2 , θ2 , f . However, the direct revelation
mechanism Γ0 cannot fully dominant strategy implement f , because an
untruthful revelation as well as the truthful announcement is always a dominant strategy of Γ0 for agent 2, and because, when she plays the untruthful
dominant strategy, the equilibrium outcome does not coincide with thesocial goal.2
Another important topic on the revelation principle is to explore therelationship between implementation in dominant strategy equilibria andtruthful implementation in dominant strategy equilibria. The revelation
principle states that, in order for social choice functions to be implemented
in dominant strategy equilibria, it is necessary for them to be truthfully implemented in dominant strategy equilibria. However, it is still open whether
truthful implementability (i.e., strategy-proofness) is a sufficient condition
for dominant strategy implementation in pure exchange economies.
2

The multiple equilibrium problem in dominant strategy implementation might not be
disturbing, because, to quote Dasgupta et al. (1979), “[i]n direct mechanisms where telling
the truth is one of several dominant strategies, it may be reasonable to suppose that players
will in fact tell the truth.” (See also Chapter 23 in Mas-Colell et al. (1995).) However, sinceeach agent is indifferent among dominant strategies irrespective of messages of the otheragents, there is no guarantee that she will play truthful dominant strategies. Indeed, recent
experimental results indicate that agents can choose a spiteful strategy (e.g., see Saijo (2005)).

4

These problems do not arise when indifference in preferences is notallowed, because three notions of dominant strategy implementation—
truthful implementation, implementation by the direct revelation mechanism, and implementation with indirect mechanisms—are equivalent in
the sense of implementability. In this case, the revelation principle has amore powerful implication: in order to find out dominant strategy implementable social choice functions, it is necessary and sufficient to search forsocial choice functions that are truthfully implementable in dominant strategy equilibria.3 However, when indifference is possible, the equivalence
does not in general hold. Thus, the revelation principle loses the powerful
implication, because not all truthfully implementable social choice functions may be able to be fully implemented in dominant strategy equilibria
not only by the direct revelation mechanism but also by any indirect mechanism. In this paper, we explore the relationships among three notions ofdominant strategy implementation to examine the implications of revelation principle in classical pure exchange economies with free disposal.
First, we search for conditions that are necessary and sufficient for a social choice function to be implemented4 in dominant strategy equilibria by
the direct revelation mechanism. In Theorem 1, we show that quasi-strongnon-bossiness is a necessary condition for dominant strategy implementation
via the direct revelation mechanism in pure exchange economies. Quasi-strongnon-bossiness requires that if a change in one agent’s type keeps her utility
unchanged irrespective of the other agents’ types, then the consumption bundleof each agent should not be changed. This is a version of non-bossiness,5 therequirement that if a change in one agent’s type retains her consumption bundle unchanged, then the bundle of each agent should be unchanged. Notethat quasi-strong-non-bossiness is not a necessary condition for dominant
strategy implementation if indirect mechanisms can be used. Example 1
above demonstrates the existence of a social choice function that fails to satisfy quasi-strong-non-bossiness but which is implementable in dominant
strategy equilibria via an indirect mechanism.
In Theorem 2, we prove that quasi-strong-non-bossiness and strategyproofness together are sufficient conditions for dominant strategy implementation by the direct revelation mechanism. Therefore, it follows fromthe revelation principle and Theorems 1 and 2 that a social choice function
is dominant strategy implementable via the direct revelation mechanism inpure exchange economies if and only if it satisfies both quasi-strong-nonbossiness and strategy-proofness (Corollary 1).6 A well-known example
3This is because every social choice function that is truthfully implementable in dominant
strategy equilibria can be fully implemented in dominant strategy equilibria.
4
The term “implement” should be interpreted as “fully implement” hereafter.
5
Non-bossiness was first introduced by Satterthwaite and Sonnenschein (1981).
6
Saijo et al. (2004) has independently obtained necessary and sufficient conditions fordominant strategy implementation via the direct revelation mechanism.

5

of social choice functions satisfying both quasi-strong-non-bossiness andstrategy-proofness is the so-called fixed-price rule (see Barberà and Jackson(1995) for details of the fixed-price rule).
Next, we look for a sufficient condition for dominant strategy implementation when indirect mechanisms are allowed to be used. In Theorem
3, we construct an augmented revelation mechanism similar to the onethat Jackson et al. (1994) devised for undominated Nash implementation,
so that we prove that strategy-proofness is a sufficient condition for social
choice functions to be dominant strategy implemented in pure exchange
economies. This theorem answers the open question mentioned above.
Together with the revelation principle, Theorem 3 leads to Corollary
2: every strategy-proof social choice function is dominant strategy implementable in pure exchange economies. This reveals a stark contrast between
the set of social choice functions that can be implemented in dominant strategy equilibria with a certain indirect mechanism, and that of social choicefunctions that can be implemented in dominant strategy equilibria withthe direct revelation mechanism. An important social choice function thatsatisfies strategy-proofness but violates quasi-strong-non-bossiness is aninversely dictatorial social choice function,7 i.e., one where there exists someagent who always receives nothing. It might appear that inversely dictatorial social choice functions cannot be implemented in dominant strategy
equilibria. But, Corollary 2 indicates that they are dominant strategy implementable by a certain indirect mechanism.
The robustness of implementation has recently deserved attention in
implementation theory (e.g., see Bergemann and Morris (2003) for details).
From this point of view, dominant strategy implementation has an advantage, because it does not need strong assumptions on the information
structure: it needs neither common knowledge about each other’s types
nor common knowledge about prior beliefs over type profiles.

The Related LiteratureThis paper closely relates to both Jackson et al. (1994) and Sjöström (1994),
which showed that almost all social choice functions are implementable inundominated Nash equilibria by a bounded mechanism. One might guessthat all of the strategy-proof social choice functions are implementable indominant strategy equilibria by their mechanisms. Indeed, for almost every strategy-proof social choice function, it is easy to check that the truthfulrevelation of own type by each agent is the unique dominant strategy equilibrium of their mechanisms; thus their mechanisms can implement it in7
Inversely dictatorial social choice functions are considered important in the sense that
Zhou (1991) conjectured that it is only inversely dictatorial social choice functions that satisfy
both strategy-proofness and Pareto efficiency in pure exchange economies with three or moreagents.

6

dominant strategy equilibria. However, not all strategy-proof social choicefunctions are dominant strategy implementable by their mechanisms. In
fact, their mechanisms cannot dominant strategy implement inversely dictatorial social choice functions, because their mechanisms cannot implement any social choice function that gives the zero consumption bundle
to some agent.8 In contrast, our mechanism constructed in the proof of
Theorem 3 can implement every social choice function whenever the social
choice function satisfies strategy-proofness.
This paper is also related to implementation in undominated strategies with a bounded mechanism. In fact, our bounded mechanism can
implement strategy-proof social choice functions via undominated strategies in pure exchange economies. Jackson (1992) considered implementation in undominated strategies with a bounded mechanism, and showedthat strategy-proofness is a necessary condition for bounded implementation in undominated strategies. Thus, combining the result of Jackson(1992), we can conclude that strategy-proofness is both necessary and sufficient for bounded implementation via undominated strategies in pure exchange economies (Theorem 4). The result indicates that, in pure exchange
economies, dominant strategy implementation is equivalent to bounded implementation in undominated strategies, in the sense that every dominant
strategy implementable social choice function can be boundedly implemented in undominated strategies, and vice versa. This is the same result
as in voting environments with only strict preferences (e.g., see Jackson(1992) and Jackson and Srivastava (1996) for details).
This paper is organized as follows. Section 2 describes the model andgives some definitions. We explore dominant strategy implementation by
the direct revelation mechanism in Section 3. In Section 4, dominant strategy
implementation by an indirect mechanism is considered. Section 5 contains
some concluding remarks.

2 The Model
Consider a pure exchange economy with free disposal. Let N := {1, 2, . . . , n} bethe set of agents, where 2 ≤ n < +∞. Let L := {1, 2, . . . , l} be the set of goods,
where 2 ≤ l < +∞. The set of feasible allocations is



X
X 




A := 
ai ≤ωi (a1 , a2 , . . . , an ) ∈ R+l × R+l × · · · × R+l
,




i∈N

i∈N

l
denotes
where ai ∈ R+l denotes agent i’s consumption bundle and ωi ∈ R++
agent i’s initial endowment.
8This is why it has not yet been proved that strategy-proofness is a sufficient condition
for dominant strategy implementation in pure exchange economies.

7

For each agent i ∈ N, let Θi be the set of all types, each of which prescribes
her preference relation over R+l . Each agent i ∈ N is equipped with a utility
function ui : R+l × Θi → R. We assume that each agent is selfish, i.e., shecares only about her own consumption bundle. For each agent i ∈ N, letΘEi ⊂ Θi be agent i’s set of admissible types: θi ∈ ΘEi if and only if ui (·; θi )is (i) continuous, (ii) strictly increasing, and (iii) strictly quasi-concave. A typeprofile is a list θ = (θ1 , θ2 , . . . , θn ) ∈ ΘE , where ΘE := ΘE1 × ΘE2 × · · · × ΘEn .
A social choice function is a single-valued function f : ΘE → A that assigns
a feasible allocation a ∈ A to each type profile θ ∈ ΘE .
Let Mi denote a message or strategy space of agent i ∈ N. We call mi ∈ Mia message or strategy of agent i ∈ N. A mechanism is a pair Γ = (M, 1), whereM := M1 × M2 × · · · × Mn and 1 : M → A is an outcome function. Given amechanism (M, 1), let 1i denote agent i’s outcome of the mechanism. Given asocial choice function f , a mechanism (M, 1) is the direct revelation mechanism
if Mi = ΘEi for every i ∈ N and 1 = f . A message or strategy profile is denotedby m = (m1 , m2 , . . . , mn ) ∈ M.
A strategy m∗i ∈ Mi is a dominant strategy of mechanism (M, 1) at θi ∈ ΘEi
if ui (1(m∗i , m−i ); θi ) ≥ ui (1(m0i , m−i ); θi ) for all m0i ∈ Mi and all m−i ∈ M−i . For
each agent i ∈ N, let DSΓi (θi ) ⊆ Mi be the set of her dominant strategies ofmechanism Γ at θi ∈ ΘEi .
A strategy profile m∗ = (m∗1 , m∗2 , . . . , m∗n ) ∈ M is a dominant strategy equilibrium of mechanism (M, 1) at θ ∈ ΘE if, for any agent i ∈ N, ui (1(m∗i , m−i ); θi ) ≥ui (1(m0i , m−i ); θi ) for any m0i ∈ Mi and any m−i ∈ M−i . Let DSEΓ (θ) :=DSΓ1 (θ1 ) × DSΓ2 (θ2 ) × · · · × DSΓn (θn ) ⊆ M be the set of all dominant strategy equilibria of mechanism Γ at θ ∈ ΘE . With an abuse of notation,E
we write DSEΓn(θ) = (DSΓ1 (θ1 ), DSΓ2 (θ2 ), . . . , DSΓn (θn )) foro any θ ∈ Θ . LetΓΓ
1(DSE (θ)) := a ∈ A a = 1(m) for some m ∈ DSE (θ) be the set of dominant strategy equilibrium outcomes of mechanism Γ = (M, 1) at θ ∈ ΘE .
A mechanism Γ = (M, 1) dominant strategy implements a social choicefunction f if 1(DSEΓ (θ)) = f (θ) for any θ ∈ ΘE .9 A social choice function
f is implementable in dominant strategy equilibria if there exists a mechanism
Γ = (M, 1) such that 1(DSEΓ (θ)) = f (θ) for all θ ∈ ΘE .
Remark 1. The single-valuedness of a social choice function, say f , implies
that if a mechanism Γ = (M, 1) implements f in dominant strategy equilibria,then, for each θ ∈ ΘE , 1(DSEΓ (θ)) is a singleton, i.e., 1(m) = 1(m0 ) for any
m, m0 ∈ DSEΓ (θ).
Remark 2. If a social choice function f is implementable in dominant strategy equilibria by the direct revelation mechanismSΓ = (M1 ×M2 ×· · ·×Mn , 1)
where Mi = ΘEi for every i ∈ N and 1 = f , then θi ∈ΘE DSΓi (θi ) = ΘEi = Mii9To simplify notation, we write 1(DSEΓ (θ)) = f (θ) as 1(DSEΓ (θ)) = f (θ).

8for any i ∈ N, because truth telling is a dominant strategy of the directrevelation mechanism for all θi ∈ ΘEi and all i ∈ N.
Now we introduce two properties of social choice functions. Strategyproofness is an incentive compatibility requirement that no agent shouldbe able to change her type in a way that results in a direct gain to her,irrespective of the other agents’ types.
Definition 1 (Strategy-proofness). A social choice function f satisfies strategyproofness if, for all θ ∈ ΘE and all i ∈ N, there is no θ0i ∈ ΘEi such thatui ( f (θ0i , θ−i ); θi ) > ui ( f (θ); θi ).
Quasi-strong-non-bossiness, which is a version of non-bossiness,10 requiresthat if a change in one agent’s type does not affect her utility regardless ofthe other agents’ types, then it does not change the consumption bundle
everyone receives.
Definition 2 (Quasi-strong-non-bossiness). A social choice function f satisfies quasi-strong-non-bossiness if, for all i ∈ N and all θi , θ0i ∈ ΘEi , ifui ( f (θ); θi ) = ui ( f (θ0i , θ−i ); θi ) for all θ−i ∈ ΘE−i , thenf (θ) = f (θ0i , θ−i ) for all θ−i ∈ ΘE−i .
Remark 3. Quasi-strong-non-bossiness is weaker than strong-non-bossiness,1112
which is a stronger version of non-bossiness.
We can easily rewrite the definition of quasi-strong-non-bossiness asfollows: a social choice function f satisfies quasi-strong-non-bossiness if, forall θ ∈ ΘE , all i ∈ N, and all θ0i ∈ ΘEi , if ui ( f (θ); θi ) = ui ( f (θ0i , θ−i ); θi ) for allθ−i ∈ ΘE−i , then f (θ) = f (θ0i , θ−i ). It is easy to check that this is equivalent to
weak non-bossiness defined in Saijo et al. (2004).

3 Implementation by the Direct Mechanism
In this section, we identify a necessary and sufficient condition for a social choice function to be dominant strategy implemented via the directrevelation mechanism in pure exchange economies.
We begin by providing a necessary condition for dominant strategy
implementation via the direct revelation mechanism.
10
A social choice function f satisfies non-bossiness if, for all i ∈ N, all θi , θ0i ∈ ΘEi , and allθ−i ∈ ΘE−i , if fi (θ) = fi (θ0i , θ−i ), then f (θ) = f (θ0i , θ−i ).
11
A social choice function f satisfies strong-non-bossiness if, for all i ∈ N, all θi , θ0i ∈ ΘEi ,and all θ−i ∈ ΘE−i , if ui ( f (θ); θi ) = ui ( f (θ0i , θ−i ); θi ), then f (θ) = f (θ0i , θ−i ).
12
Ritz (1983) first introduced the notion of strong-non-bossiness, called non-corruptibility.

9Theorem 1. If a social choice function f is dominant strategy implementableby the direct revelation mechanism in pure exchange economies, then it satisfies
quasi-strong-non-bossiness.
Proof. Pick any i ∈ N and any θi , θ0i ∈ ΘEi such thatui ( f (θ); θi ) = ui ( f (θ0i , θ−i ); θi ) for all θ−i ∈ ΘE−i .

(1)Since f is implementable in dominant strategy equilibria via the directrevelation mechanism Γ = (ΘE , f ), it holds thatf (DSEΓ (θ)) = f (θ) for all θ ∈ ΘE ,(2)

ui ( f (DSEΓ (θ)); θi ) = ui ( f (DSEΓ (θ0i , θ−i )); θi ) for all θ−i ∈ ΘE−i .

(3)

o
n
where f (DSEΓ (θ)) = a ∈ A a = f (θ) for some θ ∈ DSEΓ (θ) . Substituting(2) for f in (1), we obtain

Suppose θ̂i ∈ DSΓi (θ0i ). Then, it follows from (3) and Remark 1 thatui ( f (DSΓi (θi ), DSΓ−i (θ−i )); θi ) = ui ( f (DSΓi (θ0i ), DSΓ−i (θ−i )); θi )= ui ( f (θ̂i , DSΓ−i (θ−i )); θi )for all θ−i ∈ ΘE−i . This implies thatui ( f (θ̂i , θ−i ); θi ) = ui ( f (DSΓi (θi ), θ−i ); θi )for any θ−i ∈ ΘE−i =

S

Q
j,i

θ j ∈ΘEjDSΓj (θ j ) by Remark 2, so we obtain θ̂i ∈DSΓi (θi ). Therefore, DSΓi (θ0i ) ⊆ DSΓi (θi ).
Since DSΓi (θ0i ) ⊆ DSΓi (θi ), we havef (DSΓi (θ0i ), DSΓ−i (θ−i )) ⊆ f (DSΓi (θi ), DSΓ−i (θ−i )) for all θ−i ∈ ΘE−i .

(4)

Substituting (2) for f in (4), we havef (θ0i , θ−i ) ⊆ f (θ)
for all θ−i ∈ ΘE−i . Therefore, by the single-valuedness of f , we obtainf (θ0i , θ−i ) = f (θ)
for all θ−i ∈ ΘE−i .

10Next, we look for sufficient conditions for dominant strategy implementation by the direct revelation mechanism. If a social choice function satisfies both quasi-strong-non-bossiness and strategy-proofness, then there isalways a unique dominant strategy equilibrium outcome in the direct revelation
mechanism (although there may exist some dominant strategy equilibria
in the mechanism). So, since the direct revelation mechanism rules out
undesired equilibrium outcomes, the mechanism can implement the social
choice function in dominant strategy equilibria.13
Theorem 2. If a social choice function f satisfies both quasi-strong-non-bossinessand strategy-proofness, then it is dominant strategy implementable by the directrevelation mechanism in pure exchange economies.
Proof. Consider the direct revelation mechanism Γ = (M, 1) where Mi = ΘEi
for every i ∈ N and 1 = f . Since f satisfies strategy-proofness, ui ( f (θ); θi ) ≥ui ( f (θ0i , θ−i ); θi ) for all θ ∈ ΘE , all i ∈ N, and all θ0i ∈ ΘEi , implying thatθi ∈ DSΓi (θi ) for all i ∈ N and all θi ∈ ΘEi ; i.e., θ ∈ DSEΓ (θ) for any θ ∈ ΘE .
no So, we have f (DSEΓ (θ)) = a ∈ A a = f (θ) for some θ ∈ DSEΓ (θ) ⊇ f (θ)
for every θ ∈ ΘE .
Suppose θ̄i ∈ DSΓi (θi ). Then, since θi , θ̄i ∈ DSΓi (θi ),ui ( f (θi , θ−i ); θi ) ≥ ui ( f (θ̄i , θ−i ); θi ) for all θ−i ∈ ΘE−iandui ( f (θi , θ−i ); θi ) ≤ ui ( f (θ̄i , θ−i ); θi ) for all θ−i ∈ ΘE−i .
These imply thatui ( f (θ); θi ) = ui ( f (θ̄i , θ−i ); θi )for all θ−i ∈ ΘE−i . So, quasi-strong-non-bossiness implies thatf (θ) = f (θ̄i , θ−i ) for any θ−i ∈ ΘE−i .
Thus, f (θ̄i , θ−i ) = f (θ) for θ̄i ∈ DSΓi (θi ) and any θ−i ∈ ΘE−i , which implies
that f (DSΓi (θi ), θ−i ) = f (θ) for any θ−i ∈ ΘE−i . Since similar arguments holdfor any θi ∈ ΘEi , we obtain f (DSΓi (θi ), θ−i ) = f (θ) for any θi ∈ ΘEi and any
θ−i ∈ ΘE−i , i.e., for any θ ∈ ΘE .
Iteration of these arguments for further agents in N establishes thatf (DSEΓ (θ)) = f (θ) for all θ ∈ ΘE .

13
Laffont and Maskin (1982) proposed the notion of strictly truthful implementation, which
requires that the direct revelation mechanism should have no untruthful dominant strategy
equilibria. It is easy to see that not all strategy-proof and quasi-strong-non-bossy social
choice functions are strictly truthfully implementable in dominant strategy equilibria because the direct revelation mechanisms may have untruthful dominant strategy equilibria.

11

By the revelation principle, if a social choice function is implementable
in dominant strategy equilibria, then truth telling by each agent is a dominant strategy equilibrium of the direct revelation mechanism, i.e., the social
choice function satisfies strategy-proofness. Therefore, combined with Theorems 1 and 2, this leads to the following corollary.
Corollary 1. A social choice function f is dominant strategy implementable via
the direct revelation mechanism in pure exchange economies if and only if it satisfies
both quasi-strong-non-bossiness and strategy-proofness.
Note that Corollary 1 holds even when the set of feasible allocations consists of all balanced allocations. It is easy to check that the social choice function defined in Example 1 satisfies strategy-proofness but violates quasistrong-non-bossiness. Therefore, as seen in the example, the social choicefunction is not implementable in dominant strategy equilibria via the directrevelation mechanism. In contrast, fixed-price social choice functions (Barberà and Jackson (1995)), as well as dictatorial ones, satisfy both strategyproofness and quasi-strong-non-bossiness, so they are dominant strategy
implementable by the direct revelation mechanisms.

4 Implementation by an Indirect Mechanism
In Section 3, we show that strategy-proofness and quasi-strong-non-bossinessare both necessary and sufficient for dominant strategy implementation via
the direct revelation mechanism. In this section, we search for a condition
that is sufficient for social choice functions to be implemented in dominant
strategy equilibria. Before proceeding, let us introduce two properties onenvironments and the definition of weakly dominated strategies.
Property 1 (A Common Worst Allocation). There exists w = (w1 , w2 , . . . , wn ) ∈A such that ui (a; θi ) ≥ ui (w; θi ) for all i ∈ N, all θi ∈ ΘEi , and all a ∈ f (ΘE ),nowhere f (ΘE ) := a ∈ A a = f (θ) for some θ ∈ ΘE .
Property 1 says that there exists an allocation that is always considered
to be the worst allocation for any agent. For instance, by setting w =(0, 0, . . . , 0), Property 1 is satisfied in our environments.
Given w ∈ A that satisfies Property 1, let




X


 1 2

+
l
l
h
h
h
h
Cw := 
(c
,
c
,
.
.
.
,
c
)
∈
R
c
≥
max
w
and
c
≤
ω
for
all
h
∈
L
.

+
i
i




i∈N
i∈N

The next property is strict value distinction which was introduced by
Palfrey and Srivastava (1991).

12

Property 2 (Strict Value Distinction). For all i ∈ N and all θi , θ0i ∈ ΘEi , if
θi , θ0i , then there exist c, c̃ ∈ C+w such that ui (c; θi ) > ui (c̃; θi ) and ui (c; θ0i ) <ui (c̃; θ0i ).
Property 2 requires that if types change, then indifference curves crosssomewhere in C+w . Note that Properties 1 and 2 hold in our environments,
i.e., in pure exchange economies with free disposal and with continuous,strictly increasing, and strictly convex preferences. In fact, these properties are satisfied in many environments (see Jackson et al. (1994) for otherexamples of environments where Properties 1 and 2 are satisfied).
A strategy mi ∈ Mi is a weakly dominated strategy of mechanism (M, 1)
at θi ∈ ΘEi if there exists a strategy m0i ∈ Mi such that ui (1(m0i , m−i ); θi ) ≥ui (1(mi , m−i ); θi ) for all m−i ∈ M−i and ui (1(m0i , m−i ); θi ) > ui (1(mi , m−i ); θi ) forsome m−i ∈ M−i . In this case, m0i is said to weakly dominate mi at θi ∈ ΘEi .
We are now ready to state the main result regarding a sufficient condition
for dominant strategy implementation in pure exchange economies.
Theorem 3. If a social choice function f satisfies strategy-proofness, then it isdominant strategy implementable in pure exchange economies.
Proof. For a strategy-proof social choice function f , pick w = (w1 , w2 , . . . , wn ) ∈A in a way that satisfies Property 1. Let




X


 1 2

h
h
h
h
l
l
C++
:=
c
>
max
w
and
c
≤
ω
for
all
h
∈
L
(c
,
c
,
.
.
.
,
c
)
∈
R
.


w
++
i
i




i∈N
i∈N

Now we construct an augmented revelation mechanism Γ = (M, 1),
where M = M1 × M2 × · · · × Mn , by using ideas similar to those of themechanism constructed by Jackson et al. (1994) for undominated Nash
implementation. Agent i’s message space is
Mi := ΘEi ∪ (C+w × C+w ).
That is, each agent announces either own type or a pair of consumption
bundles. A typical message for agent i ∈ N is denoted by mi = θii or (ci , c̃i ).
The outcome function 1 is defined as follows.
Rule 1: If all agents announce their types, i.e., mi = θii ∈ ΘEi for all i ∈ N, then1(m) := f (θ11 , θ22 , . . . , θnn ). Note that, by Property 1, ui (1(m); θii ) ≥ ui (w; θii ) for
all i ∈ N and all θii ∈ ΘEi .

Rule 2: Suppose that only one agent, say i, announces her type and all otheragents j , i announce a pair of consumption bundles, i.e., mi = θii ∈ ΘEi andm j = (c j , c̃ j ) ∈ (C+w × C+w ) for any j , i. Then,no1i (m) := arg max ui (c; θii ), where C̄ := c j , c̃ j ∈ C+w j , i ,
c∈C̄

13

and, for any j , i,


 

whj X
 



h
h

 , 0for any h ∈ L.
1 j (m) := z j , where zhj := max 
w
−
1
(m)

P


i
i




h
 j,i wji∈NNote that ties are broken in some arbitrary manner unless arg maxc∈C̄ ui (c; θii ).PPhhis a singleton, and that whj
j,i w j = 0. Note also thatj,i w j := 0 if
1i (m) ≥ wi because c ≥ wi for all c ∈ C̄, and that 1 j (m) ≤ w j for all j , i byconstruction.
Rule 3: In all other cases, 1(m) := w.
We want to show that DSΓi (θi ) = {θi } for all i ∈ N and all θi ∈ ΘEi .
Step 1: For each agent, announcing a pair of consumption bundles isweakly dominated by the truthful revelation of own type.
Suppose that the true type profile is θ∗ = (θ∗1 , θ∗2 , . . . , θ∗n ). Let mi ∈ Mi besuch that mi = (ci , c̃i ) ∈ (C+w × C+w ), and m0i ∈ Mi be such that m0i = θ∗i .
jCase 1-1: m j = θ j ∈ ΘEj for all j , i.

We have 1(mi , m−i ) = w and 1(m0i , m−i ) = f (θ∗i , θ−i) by Rule 3 and by Rule−i

1, respectively. Since ui ( f (θ∗i , θ−i); θ∗i ) ≥ ui (w; θ∗i ) by Property 1, we obtain−iui (1(m0i , m−i ); θ∗i ) ≥ ui (1(mi , m−i ); θ∗i ) for any m−i ∈ ΘE−i .

Case 1-2: m j = (c j , c̃ j ) ∈ (C+w × C+w ) for all j , i.

We have 1(mi , m−i ) = w by Rule 3, while 1i (m0i , m−i ) = arg maxc∈C̄ ui (c; θ∗i ) bynoRule 2, where C̄ = c j , c̃ j ∈ C+w j , i . Since c ≥ wi for all c ∈ C̄ by construction, we obtain 1i (m0i , m−i ) ≥ 1i (mi , m−i ), which implies ui (1(m0i , m−i ); θ∗i ) ≥ui (1(mi , m−i ); θ∗i ) for any m−i ∈ (C+w × C+w )n−1 . In particular, since c > wi for all++++c ∈ C̄ by construction if m̄ j = (c j , c̃ j ) ∈ (C++w ×Cw ) ⊂ (Cw ×Cw ) for all j , i, we
00∗have 1i (mi , m̄−i ) > 1i (mi , m̄−i ), implying ui (1(mi , m̄−i ); θi ) > ui (1(mi , m̄−i ); θ∗i )++ n−1 .
for m̄−i ∈ (C++w × Cw )j

Case 1-3: m j = θ j ∈ ΘEj for some j , i and mk = (ck , c̃k ) ∈ (C+w × C+w ) for allk ∈ N \ {i, j}.
 h P
 
wi
h
h
h
P
It follows from Rule 2 that 1i (mi , m−i ) = zi , where zi = maxi∈N wi − 1 j (m) , 0
wh
i, j

i

for any h ∈ L. On the other hand, 1(m0i , m−i ) = w by Rule 3. Since wi ≥ zi ,we get ui (1(m0i , m−i ); θ∗i ) ≥ ui (1(mi , m−i ); θ∗i ) for any m−i ∈ ΘEj ×(C+w × C+w )n−2 .
Case 1-4: All other cases.

Rule 3 implies 1(mi , m−i ) = w and 1(m0i , m−i ) = w, implying ui (1(m0i , m−i ); θ∗i ) ≥ui (1(mi , m−i ); θ∗i ).
14

The above cases together establish that mi is weakly dominated by m0i . Thus,
announcing a pair of consumption bundles is weakly dominated by telling
the truth.
Step 2: For every agent, misrepresenting own type is weakly dominatedby the truthful announcement of own type.
Suppose that the true type profile is θ∗ = (θ∗1 , θ∗2 , . . . , θ∗n ). Let mi ∈ Mi besuch that mi = θii ∈ ΘEi \{θ∗i }, and m0i ∈ Mi be such that m0i = θ∗i .
jCase 2-1: m j = θ j ∈ ΘEj for all j , i.

) and 1(m0i , m−i ) = f (θ∗i , θ−i). Since
Rule 1 implies 1(mi , m−i ) = f (θii , θ−i−i−i); θ∗i ) ≥ ui ( f (θii , θ−i); θ∗i ), we obtainstrategy-proofness implies ui ( f (θi∗ , θ−i−i−iui (1(m0i , m−i ); θ∗i ) ≥ ui (1(mi , m−i ); θ∗i ) for any m−i ∈ ΘE−i .

Case 2-2: m j = (c j , c̃ j ) ∈ (C+w × C+w ) for all j , i.

It follows from Rule 2 that 1i (mi , m−i ) = arg maxc∈C̄ ui (c; θii ) and 1i (m0i , m−i ) =noarg maxc∈C̄ ui (c; θ∗i ), where C̄ = c j , c̃ j ∈ C+w j , i . Since agent i’s true type isθ∗i , we obtain ui (1(m0i , m−i ); θ∗i ) ≥ ui (1(mi , m−i ); θ∗i ) for any m−i ∈ (C+w × C+w )n−1 .
Suppose in turn that agent i’s true type is θii . Then, since her true type is θii ,ui (1(m0i , m−i ); θii ) ≤ ui (1(mi , m−i ); θii ) for any m−i ∈ (C+w × C+w )n−1 . Especially,
by Property 2, we haveui (1(m0i , m̄−i ); θ∗i ) > ui (1(mi , m̄−i ); θ∗i )
andui (1(m0i , m̄−i ); θii ) < ui (1(mi , m̄−i ); θii )for some m̄−i ∈ (C+w × C+w )n−1 ; otherwise, for any m̄−i ∈ (C+w × C+w )n−1 , (i) if
ui (1(m0i , m̄−i ); θ∗i ) > ui (1(mi , m̄−i ); θ∗i ), then ui (1(m0i , m̄−i ); θii ) = ui (1(mi , m̄−i ); θii ),(ii) if ui (1(m0i , m̄−i ); θii ) < ui (1(mi , m̄−i ); θii ), then ui (1(m0i , m̄−i ); θ∗i ) = ui (1(mi , m̄−i ); θ∗i ),or (iii) ui (1(m0i , m̄−i ); θ∗i ) = ui (1(mi , m̄−i ); θ∗i ) and ui (1(m0i , m̄−i ); θii ) = ui (1(mi , m̄−i ); θii ),all of which contradict Property 2.14
Case 2-3: All other cases.
By Rule 3, we have 1(mi , m−i ) = w and 1(m0i , m−i ) = w, which implies
ui (1(m0i , m−i ); θ∗i ) ≥ ui (1(mi , m−i ); θ∗i ).

The above cases together establish that mi is weakly dominated by m0i . Thus,
misreporting own type is weakly dominated by truthful reporting.
Steps 1 and 2 together imply that the truthful revelation of own typeweakly dominates both announcements of a pair of consumption bundles
This is because, in any case, there are no c, c̃ ∈ C+w such that ui (c; θ∗i ) > ui (c̃; θ∗i ) ≥ ui (w; θ∗i )and ui (c̃; θii ) > ui (c; θii ) ≥ ui (w; θii ).
1415and false reports of own type. Thus, we establish that DSΓi (θi ) = {θi } for alli ∈ N and all θi ∈ ΘEi ; i.e., DSEΓ (θ) = {θ} for all θ ∈ ΘE . Therefore, we canconclude from Rule 1 that 1(DSEΓ (θ)) = f (θ) for all θ ∈ ΘE .

Note that our mechanism works not only for n > 3 but also for n = 2,
as the mechanism of Jackson et al. (1994) works. Note also that Theorem
3 is critically dependent on Property 1. This is because it is impossible topunish agents who do not announce their truthful types if Property 1 does
not hold.
The following corollary follows immediately from the revelation principle and Theorem 3.
Corollary 2. A social choice function f is dominant strategy implementable inpure exchange economies if and only if it satisfies strategy-proofness.
Corollary 2 tells us that every strategy-proof social choice function is
implementable in dominant strategy equilibria if indirect mechanisms areallowed to be used. This is in stark contrast to Corollary 1, because it statesthat only quasi-strong-non-bossy and strategy-proof social choice functions
are dominant strategy implementable by the direct revelation mechanism.
A well-known social choice function that satisfies strategy-proofness
but fails to satisfy quasi-strong-non-bossiness is an inversely dictatorial one,which was introduced by Zhou (1991). So, it follows from Corollaries 1 and2 that inversely dictatorial social choice functions are not implementable indominant strategy equilibria by the direct revelation mechanism, but are
implementable in dominant strategy equilibria by the indirect mechanism
constructed in the proof of Theorem 3.
As mentioned before, our mechanism appears to be similar to the one
devised by Jackson et al. (1994). Indeed, their mechanism as well as themechanism constructed by Sjöström (1994) can dominant strategy implement almost all social choice functions whenever the social choice functions
satisfy strategy-proofness. However, an important difference is that ourmechanism can implement inversely dictatorial social choice functions indominant strategy equilibria, whereas their mechanisms cannot dominant
strategy implement the social choice functions.15 Thus, our mechanism
has the advantage of being able to implement strategy-proof social choicefunctions that assign someone the zero consumption bundle (although theadvantage is somewhat limited because our mechanism is not necessarily
useful for undominated Nash implementation).
We conclude this section with a brief discussion of implementation inanother equilibrium concept. Since our bounded mechanism constructed in
the proof of Theorem 3 can implement strategy-proof social choice functions
15

The difference stems from the fact that Jackson et al. (1994) and Sjöström (1994) neededa slightly stronger property than Property 1.

16even in undominated strategies, Theorem 3 implies the following theorem
when coupled with Corollary 1 in Jackson (1992) which says that strategyproofness is necessary for implementation in undominated strategies by abounded mechanism.
Theorem 4. A social choice function f is implementable via undominated strategies with a bounded mechanism in pure exchange economies if and only if it satisfies
strategy-proofness.
Theorem 4 indicates that, in pure exchange economies, implementationin dominant strategy equilibria is equivalent to bounded implementation in
undominated strategies, in the sense that the set of social choice functions
implementable in dominant strategy equilibria coincides with that of social
choice functions boundedly implementable in undominated strategies.

5 Conclusion
In this paper, we have considered the relationships among three notionsof dominant strategy implementation in classical pure exchange economies
with free disposal.16 First, in Theorem 1, we have shown that quasi-strongnon-bossiness is necessary for social choice functions to be dominant strategy implemented by the direct revelation mechanism. Next, in Theorem
2, we have proved that quasi-strong-non-bossiness and strategy-proofness
together are sufficient for dominant strategy implementation by the directrevelation mechanism. Finally, in Theorem 3, we have proved that strategyproofness is sufficient for dominant strategy implementation, by using an
augmented revelation mechanism.
Since there exists a social choice function that is strategy-proof but which
is not quasi-strong-non-bossy (e.g., an inversely dictatorial social choicefunction), Theorems 1–3 together with the revelation principle imply thefollowing relationships: from the point of view of implementability in classical pure exchange economies with free disposal, (i) dominant strategy
implementation via the direct revelation mechanism implies, but is not
implied by, dominant strategy implementation by a certain indirect mechanism, and (ii) dominant strategy implementation via a certain indirect
mechanism is identical to truthful implementation in dominant strategy
equilibria. As noted in the introduction, when indifference is possible, therevelation principle loses the powerful implication. However, our theorems
indicate that, in classical pure exchange economies with free disposal, the16
It is worth noting that Theorems 1–3 hold not only in classical pure exchange economies
with free disposal but also in other environments where Properties 1 and 2 introduced in
Section 4 are satisfied; furthermore, Theorems 1 and 2 hold even without Properties 1 and2.

17revelation principle has the same powerful implication as in the case where
indifference is impossible.
It is worth discussing relationships among dominant strategy implementation, Nash implementation, and bounded implementation in undominated Nash equilibria. It might seem at first glance that all of thedominant strategy implementable social choice functions are both Nash
implementable and boundedly implementable in undominated Nash equilibria. However, there is no relationship among them, because inversely
dictatorial social choice functions are dominant strategy implementable but
are not boundedly implementable in undominated Nash equilibria as well
as not being Nash implementable.
Our mechanism constructed in the proof of Theorem 3 is similar to themechanism of Jackson et al. (1994); thus our mechanism possesses worrisome features as their mechanism possesses. For instance, as mentioned
before, our mechanism makes frequent use of Property 1 to punish agents
who do not truthfully announce their types. Property 1 is consistent withpure exchange economies with free disposal, but would hardly seem consistent with ones without free disposal. It is an interesting topic for further
research to construct a more “natural” mechanism for dominant strategy
implementation.

18

ReferencesB̀, S.  M. O. J (1995): “Strategy-proof Exchange,” Econometrica, 63, 51–87.
B, D.  S. M (2003): “Robust Implementation: The Roleof Large Type Spaces,” mimeo., Yale University.
D, P., P. H,  E. M (1979): “The Implementation ofSocial Choice Rules: Some General Results on Incentive Compatibility,”
Review of Economic Studies, 46, 185–216.
J, M. O. (1992): “Implementation in Undominated Strategies: A
Look at Bounded Mechanisms,” Review of Economic Studies, 59, 757–775.
J, M. O., T. R. P,  S. S (1994): “Undominated Nash
Implementation in Bounded Mechanisms,” Games and Economic Behavior,
6, 474–501.
J, M. O.  S. S (1996): “A Characterization of GameTheoretic Solutions Which Lead to Impossibility Theorems,” Review of
Economic Studies, 63, 23–38.
L, J.-J.  E. M (1982): “Nash and Dominant Strategy Implementation in Economic Environments,” Journal of Mathematical Economics,
10, 17–47.
M-C, A., M. D. W,  J. R. G (1995): Microeconomic
Theory, Oxford University Press.
M, D.  S. R (1990): “Implementation via Augmented Revelation Mechanisms,” Review of Economic Studies, 57, 453–475.
P, T. R.  S. S (1989): “Implementation with Incomplete
Information in Exchange Economies,” Econometrica, 57, 115–134.
——— (1991): “Nash Implementation Using Undominated Strategies,”
Econometrica, 59, 479–501.
P, A.  D. S (1986): “Implementation in Differential
Information Economies,” Journal of Economic Theory, 39, 14–33.
R, R. (1986): “On the Revelation Principle under Complete and Incomplete Information,” in Economic Organization as Games, ed. by K. Binmore and P. Dasgupta, Basil Blackwell, 179–195.
R, Z. (1983): “Restricted Domains, Arrow-Social Welfare Functions andNoncorruptible and Non-manipulable Social Choice Correspondences:
The Case of Private Alternatives,” Mathematical Social Sciences, 4, 155–
179.
19

S, T. (2005): “Spiteful Behavior in Voluntary Contribution Mechanism
Experiments,” in Handbook of Experimental Economics Results, ed. by C. R.
Plott and V. L. Smith, North-Holland.
S, T., T. S̈̈,  T. Y (2004): “Secure Implementation,”
mimeo., Osaka University.
S, M. A.  H. S (1981): “Strategy-Proof Allocation Mechanisms at Differentiable Points,” Review of Economic Studies,48, 587–597.
S̈̈, T. (1994): “Implementation in Undominated Nash Equilibria
without Integer Games,” Games and Economic Behavior, 6, 502–511.
Z, L. (1991): “Inefficiency of Strategy-proof Allocation Mechanisms inPure Exchange Economies,” Social Choice and Welfare, 8, 247–254.

20