GCOE Discussion Paper Series
Global COE Program

Human Behavior and Socioeconomic Dynamics
Discussion Paper No.279

An Equivalence of Secure Implementability andFull Implementability in Truthful Strategies
in Pure Exchange Economies with Leontief Utility Functions

Katsuhiko Nishizaki

September 2012GCOE Secretariat
Graduate School of Economics

OSAKA UNIVERSITY

1-7 Machikaneyama, Toyonaka, Osaka, 560-0043, Japan

An Equivalence of Secure Implementability andFull Implementability in Truthful Strategies
in Pure Exchange Economies with Leontief Utility Functions ∗Katsuhiko Nishizaki †September 20, 2012

Abstract
This paper investigates the relationship between secure implementability (Saijo, T., T. Sjöström,and T. Yamato (2007) “Secure Implementation,” Theoretical Economics 2, pp.203-229) and full implementability in truthful strategies (Nicolò, A. (2004) “Efficiency and Truthfulness with Leontief
Preferences. A Note on Two-Agent, Two-Good Economies,” Review of Economic Design 8, pp.373382) in pure exchange economies with Leontief utility functions. In general, secure implementability
is stronger than full implementability in truthful strategies. However, we find that the opposite relationship is established if the social choice function satisfies non-wastefulness (Li, T. and J. Xue(2011) “Egalitarian Division under Leontief Preferences,” mimeo). Together with the result of Li
and Xue (2011), this relationship implies the existence of desirable and securely implementable social choice functions in pure exchange economies with Leontief utility functions contrary to almost
all environments.
Key words: Secure implementability, Full implementability in truthful strategies, Strategy-proofness,
Pure exchange economy, Leontief utility function.
JEL classification: C72, D51, D52, D71, D78.

∗ The author would like to thank Shigehiro Serizawa for his guidance to this topic and acknowledge for the Global COE

program of Osaka University for the financial supports. The responsibility for any errors that remain is entirely the author.
† Graduate School of Economics, Osaka University, 1-7, Machikaneyama, Toyonaka, Osaka 560-0043, Japan. E-mail:gge008nk@mail2.econ.osaka-u.ac.jp.

1 Introduction
1.1 Back BackgroundIn this paper, we study strategy-proof social choice functions in pure exchange economies with n ≥2 agents and m ≥ 2 divisible goods. Strategy-proofness requires that truthful revelation is a weakly
dominant strategy for each agent in the direct revelation mechanism associated with the social choicefunction. 1 This property is standard for non-manipulability.
In pure exchange economies, as Hurwicz (1972) notes, Walrasian allocations are manipulable. Moreover, he shows that there exists no social choice function that satisfies strategy-proofness, Pareto-efficiency,
and individual rationality in pure exchange economies with n = 2 agents and m = 2 divisible goods onclassical domains. After his seminal work, such negative results have been established on specific domains: classical domains (Dasgupta, Hammond, and Maskin, 1979; Zhou, 1991; Serizawa, 2002; Serizawa and Weymark, 2003), Cobb-Douglas domains (Hashimoto, 2008), CES domains (Ju, 2003), andlinear domains (Schummer, 1997). 2 The only exceptions are Leontief domains. Nicolò (2004) andLi and Xue (2011) demonstrate that certain social choice functions do satisfy strategy-proofness, Pareto
efficiency, and individual rationality on Leontief domains. The above mentioned results illustrate howdifficult it is to find strategy-proof social choice functions with desirable properties in pure exchange
economies.
Although strategy-proofness is a desirable property, it has one shortcoming; the strategy-proof directrevelation mechanism might have a Nash equilibrium that induces a non-optimal outcome. This problem
is solved by secure implementation (Saijo, Sjöström, and Yamato, 2007) that is identical with double
implementation in dominant strategy equilibria and Nash equilibria. 3 This concept is considered to be abenchmark for constructing mechanisms that work well in laboratory experiments. 4 The possibility of
secure implementation has been studied in several environments: voting environments (Saijo, Sjöström,
and Yamato, 2007; Berga and Moreno, 2009), public good economies (Saijo, Sjöström, and Yamato,
2007; Nishizaki, 2011), the problems of providing a divisible and private good with monetary transfers(Saijo, Sjöström, and Yamato, 2007; Kumar, 2009), the problems of allocating indivisible and private
goods with monetary transfers (Fujinaka and Wakayama, 2008), queueing problems (Nishizaki, forthcoming), Shapley-Scarf housing markets (Fujinaka and Wakayama, 2011), and allotment economies withsingle-peaked preferences (Bochet and Sakai, 2010). 5 These studies illustrate the difficulty of finding
securely implementable social choice functions with desirable properties.

1 A social choice function is a function that associates an outcome with agents’ private information.

A direct revelation
mechanism associated with a social choice function is a mechanism in which (i) the set of strategy profiles is equivalent to thedomain and (ii) the game form is equivalent to the function. For strategy-proofness, see Barberà (2010) in social choice theory
and Jackson (2001, 2003) and Maskin and Sjöström (2002) in mechanism design theory.
2 Barberà and Jackson (1995) abandon Pareto-efficiency and study strategy-proof and individually rational social choicefunctions.
3 See Mizukami and Wakayama (2007) and Saijo, Sjöström, and Yamato (2007) for dominant strategy implementation and
Maskin (1977), Repullo (1987), and Saijo (1988) for Nash implementation.
4 See Cason, Saijo, Sjöström, and Yamato (2006) for experimental results on secure implementation.
5 See also Saijo, Sjöström, and Yamato (2003) for theoretical results on secure implementation.

11.2 Motivation
Almost all previous studies show negative results on secure implementation; there rarely exists a nontrivial and securely implementable social choice function. Such results prompt the investigation into
environments in which non-trivial and securely implementable social choice functions exist. In thispaper, we investigate pure exchange economies with Leontief utility functions.
Previous studies demonstrate that strategy-proofness is weaker on Leontief domains than other domains. In fact, Nicolò (2004) and Li and Xue (2011) show not only strategy-proof, Pareto efficient, andindividually rational social choice functions but also more non-manipulable social choice functions withdesirable properties. Note that such non-manipulability is necessary for secure implementation. On thebasis of these results, we examine the possibility of secure implementation in pure exchange economies
with Leontief utility functions.
In addition, practical interests prompt our investigation. It is natural to assume that each agent hasa Leontief utility function in computer science literature. 6 For example, we can consider the problemof allocating some resources (CPU, memory, I/O resources, and so forth) in cloud computing systems.
Each user demands such resources to do their jobs. The key point is that each user demands them in a
fixed-proportion according to their jobs.

1.3 Related LiteratureThis paper is most closely related to those of Saijo, Sjöström, and Yamato (2007), Nicolò (2004), and Li
and Xue (2011).
Saijo, Sjöström, and Yamato (2007) introduce secure implementation and show a necessary andsufficient condition for secure implementability. 7 They study the possibility of secure implementation in
specific environments. In standard quasi-linear environments, they show that Groves-Clarke mechanisms(Clarke, 1971; Groves, 1973) are securely implementable if the private or non-excludable public goods
are divisible but not if the goods are not divisible. In single-peaked voting environments, they show that
only dictatorial social choice functions are securely implementable. 8
Nicolò (2004) and Li and Xue (2011) study pure exchange economies with Leontief utility functions. Nicolò (2004) introduces full implementation in truthful strategies, that is stronger than dominant strategy implementation but weaker than secure implementation, and characterizes a set of social
choice functions that are fully implementable in truthful strategies in addition to certain desirable properties. 9 Note that this characterization is established in environments in which there exist n = 2 agentswith private endowments and m = 2 divisible goods. Li and Xue (2011) characterize such social choicefunctions in environments with n ≥ 2 agents and m ≥ 2 divisible goods, assuming that the resources aresocially endowed. To characterize them, they impose non-wastefulness (Li and Xue, 2011). If an agent
has a Leontief utility function, then a certain amount of specific goods may be redundant to maintain her
utility level. In such cases, it is better to transfer the amount of goods to other agents who demand them
6 See Ghodsi, Zaharia, Hindman, Konwinski, Shenker, and Stoica (2011) for Leontief utility functions and computer science.
7 See Mizukami and Wakayama (2008) for their alternative characterization of securely implementable social choice func-

tions in terms of a stronger version of Maskin monotonicity (Maskin, 1977).
8 Note that they require dictatorship on the range of the social choice function.
9 See Berga and Moreno (2009) for their alternative characterization of minmax rules in terms of full implementability intruthful strategies in single-peaked voting environments.

2

outside the economy. Non-wastefulness requires such transfers and is incompatible with the balancenessof goods, that Nicolò (2004) imposes on his characterization. Imposing non-wastefulness strongly constrains manipulation and enables more desirable social choice functions that are fully implementable intruthful strategies.

1.4 Our Result
Our main result shows that the rectangular property (Saijo, Sjöström, and Yamato, 2007) is weaker
than strong non-bossiness (Ritz, 1983; 1985) if the social choice function satisfies strategy-proofness
and non-wastefulness in pure exchange economies with Leontief utility functions. 10 The rectangularproperty is a necessary condition for secure implementation. On the other hand, strong non-bossinessis a necessary condition for full implementation in truthful strategies. Because the rectangular property
is generally stronger than strong non-bossiness, our main result implies that secure implementability
is equivalent to full implementability in truthful strategies if the social choice function satisfies nonwastefulness in pure exchange economies with Leontief utility functions. Together with the result of Li
and Xue (2011), this relationship implies the existence of desirable and securely implementable social
choice functions contrary to almost all environments.
This paper is organized according to the following sections. Section 2 introduces our model. We
define properties of social choice functions related to secure implementability, full implementability intruthful strategies, and non-wastefulness in Section 3. Certain preliminary results on the properties areshown in Section 4. In Section 5, we present our main result. Section 6 concludes this paper.

2 ModelSimilar to Li and Xue (2011), we consider pure exchange economies with n ≥ 2 agents and m ≥ 2divisible goods. Let I ≡ {1, . . . , n} be the set of agents and K ≡ {1, . . . , m} be the set of goods. Let
R+ ≡ {r ∈ R | r ≥ 0}. For each k ∈ K, let ek ∈ R+ be the social endowment of good k. For each i ∈ I andeach k ∈ K, let xik ∈ R+ be consumption of good k for agent i and xi ≡ (xik )k∈K ∈ Rm
+ be consumption
for agent i. For each i ∈ I, xi = 0 means that agent i consumes no goods. Let x ≡ (xi )i∈I ∈ Rmn+ be anallocation and()
X≡x ∈ Rmn+∑ xik ≤ ek for each k ∈ Ki∈Ibe the set of feasible allocations.
A preference of an agent is represented by a Leontief utility function. For each i ∈ I, let ui : Rm+→Rm
be a Leontief utility function for agent i; there exists (λik )k∈K ∈ R++ with ∑k∈K λik = 1 such that foreach xi ∈ Rm
+,
 
xik
,
ui (xi ) = mink∈K
λik
where R++ ≡ {r ∈ R | r > 0}. For each i ∈ I, let Ui be the set of utility functions for agent i. Letu ≡ (ui )i∈I be a profile of utility functions and U ≡ ∏i∈I Ui be the set of profiles of utility functions. For
10 Strong non-bossiness is called non-corruptibility by Ritz (1983, 1985) and non-bossiness by Saijo, Sjöström, and Yamato(2007).

3each i ∈ I, let u−i ≡ (u j ) j∈I\{i} be a profile of utility functions other than agent i and U−i ≡ ∏ j∈I\{i} U j be
the set of profiles of utility functions other than agent i. For each I1 , I2 ⊆ I with I1 ∩ I2 = 0/ and I1 ∪ I2 = I
and each u, u0 ∈ U, let (uI1 , u0I2 ) be the profile of utility functions in which agent i ∈ I1 has ui and agenti ∈ I2 has u0i .
A social choice function associates a desirable allocation with a profile of utility functions. Let
f : U → X be a social choice function. For each u ∈ U and each i ∈ I, let fi (u) be the consumption foragent i at the allocation f (u).
Remark 1. Li and Xue (2011) assume that each social choice function inherently satisfies non-wastefulness
that is defined in Section 3 (see Definition 4).
Remark 2. Our main result is established even if an agent has a “generalized” Leontief utility function(see Section 5, Remark 6). 11 For each i ∈ I and each k ∈ K, let ϕik : R+ → R be a strictly increasing
function. For each i ∈ I and each ui ∈ Ui , ui is a generalized Leontief utility function for agent i if andonly if there exists (ϕik )k∈K such that for each xi ∈ Rm+,
ui (xi ) = min {ϕik (xik )} .
k∈K

3

Properties of Social Choice Functions

This paper investigates the relationship between secure implementability (Saijo, Sjöström, and Yamato,2007) and full implementability in truthful strategies (Nicolò, 2004) in pure exchange economies with
Leontief utility functions. In this section, we define the associated properties.

3.1 Secure Implementability and Full Implementability in Truthful Strategies
Saijo, Sjöström, and Yamato (2007) introduce secure implementation that is identical with double implementation in dominant strategy equilibria and Nash equilibria. They show that the social choice function
is securely implementable if and only if it satisfies strategy-proofness and the rectangular property(Saijo, Sjöström, and Yamato, 2007).
Strategy-proofness requires that truthful revelation is a weakly dominant strategy for each agent in
the direct revelation mechanism associated with the social choice function.
Definition 1. The social choice function f satisfies strategy-proofness if and only if for each u, u0 ∈ U
and each i ∈ I, ui ( fi (ui , u0−i )) ≥ ui ( fi (u0i , u0−i )).
The rectangular-property requires that if each agent cannot change her utility by her manipulation,then the outcome cannot change by the all agents’ manipulation in the direct revelation mechanism
associated with the social choice function.
Definition 2. The social choice function f satisfies the rectangular property if and only if for eachu, u0 ∈ U, if ui ( fi (ui , u0−i )) = ui ( fi (u0i , u0−i )) for each i ∈ I, then f (u) = f (u0 ).

11 See Nicolò (2004) and Li and Xue (2011) for generalized Leontief utility functions in pure exchange economies.

4

Nicolò (2004) introduces full implementation in truthful strategies, that is stronger than dominant
strategy implementation but weaker than secure implementation. By definition, we know that the social choice function is fully implementable in truthful strategies if and only if it satisfies strategyproofness and strong non-bossiness (Ritz, 1983; 1985). 12
Strong non-bossiness requires that each agent cannot change the outcome by her manipulation while
maintaining her utility level in the direct revelation mechanism associated with the social choice function.
Definition 3. The social choice function f satisfies strong non-bossiness if and only if for each u, u0 ∈ U
and each i ∈ I, if ui ( fi (ui , u0−i )) = ui ( fi (u0i , u0−i )), then f (ui , u0−i ) = f (u0i , u0−i ).
By definition, strong non-bossiness is stronger than non-bossiness (Satterthwaite and Sonnenschein,
1981). 13 If n = 2, m = 2, and each agent has a private endowment, then Nicolò (2004) characterizes
a set of social choice functions that are fully implementable in truthful strategies in addition to certain
desirable properties.
Saijo, Sjöström, and Yamato (2007) show that the rectangular property is stronger than strong nonbossiness in general environments. 14 This finding implies that secure implementability is generally
stronger than full implementability in truthful strategies. However, the opposite relationship is established if the social choice function satisfies non-wastefulness (Li and Xue, 2011) in pure exchange
economies with Leontief utility functions.

3.2 Non-Wastefulness
If an agent has a Leontief utility function, then a certain amount of specific goods may be redundant tomaintain her utility level. In such cases, it is better to transfer the amount of goods to other agents who
demand them outside the economy. Li and Xue (2011) define such desirability as non-wastefulness.
For each i ∈ I and each ui ∈ Ui , let

γ (ui ) ≡ {xi ∈ Rm
+ | there exists t ∈ R+ such that xi = (t λik )k∈K }be the critical set for agent i with ui , that is, the ray that consists of the entire kink points of ui beginningat the origin. Note that for each i ∈ I and each ui , u0i ∈ Ui with ui 6= u0i , γ (ui ) 6= γ (u0i ) and γ (ui ) ∩ γ (u0i ) ={0}.
Remark 3. If an agent has a generalized Leontief utility function, then the critical set may be a curveand intersect with other sets at some points other than the origin.
Non-wastefulness requires that the consumption for each agent associated by the social choice function is in her critical set.
Definition 4. The social choice function f satisfies non-wastefulness if and only if for each u ∈ U andeach i ∈ I, fi (u) ∈ γ (ui ).
12 See Mizukami and Wakayama (2007) and Saijo, Sjöström, and Yamato (2007) for dominant strategy implementable social

choice functions.
13 The social choice function f satisfies non-bossiness if and only if for each u, u0 ∈ U and each i ∈ I, if f (u , u0 ) =i i −ifi (u0i , u0−i ), then f (ui , u0−i ) = f (u0i , u0−i ).
14 See Proposition 2 in Saijo, Sjöström, and Yamato (2007). In addition, see their alternative characterization of securely
implementable social choice functions in terms of strong non-bossiness.

5Remark 4. Non-wastefulness is incompatible with the balanceness of goods because it requires transferring the redundant amount of specific goods to other agents outside the economy. The balanceness ofgoods requires that for each u ∈ U and each k ∈ K, ∑i∈I fik (u) = ek , where fik (u) is the consumption ofgood k for agent i ∈ I at the allocation f (u).

4 Preliminary Results
In this section, we present certain preliminary results on full implementability in truthful strategies andnon-wastefulness in pure exchange economies with Leontief utility functions. Note that full implementability in truthful strategies is equivalent to the combination of strategy-proofness and strong nonbossiness.

4.1 Full Implementability in Truthful Strategies
Lemma 1 shows the uniqueness of each agent’s utility maximizer that she can induce if the social choicefunction satisfies strategy-proofness and strong non-bossiness.
Lemma 1. Suppose that the social choice function f satisfies strategy-proofness and strong nonbossiness. For each u, u0 ∈ U and each i ∈ I, if fi (ui , u0−i ) 6= fi (u0i , u0−i ), then ui ( fi (ui , u0−i )) > ui ( fi (u0i , u0−i )).
Proof. To the contrary, we suppose that there exist u, u0 ∈ U and i ∈ I such that fi (ui , u0−i ) 6= fi (u0i , u0−i )and ui ( fi (ui , u0−i )) ≤ ui ( fi (u0i , u0−i )). If ui ( fi (ui , u0−i )) < ui ( fi (u0i , u0−i )), then we have a contradiction
to strategy-proofness. If ui ( fi (ui , u0−i )) = ui ( fi (u0i , u0−i )), then we find that f (ui , u0−i ) = f (u0i , u0−i ) bystrong non-bossiness. This is a contradiction because fi (ui , u0−i ) 6= fi (u0i , u0−i ).
Lemma 1 implies Corollary 1; each agent who consumes no goods cannot consume any goods by
her revelation if the social choice function satisfies strategy-proofness and strong non-bossiness.
Corollary 1. Suppose that the social choice function f satisfies strategy-proofness and strong nonbossiness. For each u, u0 ∈ U and each i ∈ I, if fi (ui , u0−i ) = 0, then fi (u0i , u0−i ) = 0.
Proof. To the contrary, we suppose that there exist u, u0 ∈ U and i ∈ I such that fi (ui , u0−i ) = 0 andfi (u0i , u0−i ) 6= 0. These imply that fi (ui , u0−i ) 6= fi (u0i , u0−i ). By Lemma 1, we find that ui ( fi (ui , u0−i )) >ui ( fi (u0i , u0−i )). This is a contradiction because fi (u0i , u0−i ) 6= 0 by the definition of utility functions.

4.2 Non-Wastefulness
Lemma 2 shows that each agent’s non-zero consumption corresponds one-to-one with her utility function
if the social choice function satisfies non-wastefulness.
Lemma 2. Suppose that the social choice function f satisfies non-wastefulness. For each u, u0 ∈ U andeach i ∈ I, if fi (ui , u0−i ) 6= 0 and fi (ui , u0−i ) = fi (u0i , u0−i ), then ui = u0i .
Proof. To the contrary, we suppose that there exist u, u0 ∈ U and i ∈ I such that fi (ui , u0−i ) 6= 0, fi (ui , u0−i ) =fi (u0i , u0−i ), and ui 6= u0i . Because ui 6= u0i , we know that γ (ui ) ∩ γ (u0i ) = {0} by the definition of γ . This isa contradiction because fi (ui , u0−i ) 6= 0 and fi (ui , u0−i ) = fi (u0i , u0−i ).
6Remark 5. Lemma 2 is not established if the agent has a generalized Leontief utility function because
the critical set may be a curve and intersect with other sets at some points other than the origin, that is,
γ (ui ) ∩ γ (u0i ) ⊃ {0} for some i ∈ I and some ui , u0i ∈ Ui with ui 6= u0i .

5 Main Result
As previously stated, the rectangular property is generally stronger than strong non-bossiness. The following theorem shows that the opposite relationship is established if the social choice function satisfies
strategy-proofness and non-wastefulness in pure exchange economies with Leontief utility functions.
Theorem. Suppose that the social choice function satisfies strategy-proofness and non-wastefulness. If
the social choice function satisfies strong non-bossiness, then it satisfies the rectangular property.
Proof. Let f be a social choice function that satisfies strategy-proofness, non-wastefulness, and strong
non-bossiness. Let u, u0 ∈ U be such that ui ( fi (ui , u0−i )) = ui ( fi (u0i , u0−i )) for each i ∈ I. By strong
non-bossiness, this implies thatf (ui , u0−i ) = f (u0i , u0−i ) for each i ∈ I.

(1)

Let I1 ≡ {i ∈ I | fi (ui , u0−i ) = 0} and I2 ≡ {i ∈ I | fi (ui , u0−i ) 6= 0}. Without loss of generality, let 1, 2 ∈ I1 .
By (1), we know that f (u1 , u0I1 \{1} , u0I2 ) = f (u0I1 , u0I2 ) and f2 (u0I1 , u0I2 ) = 0. These imply thatf2 (u1 , u02 , u0I1 \{1,2} , u0I2 ) = 0.

(2)

f2 (u1 , u2 , u0I1 \{1,2} , u0I2 ) = 0.

(3)

By (2) and Corollary 1, we find thatBy (2), (3), and non-bossiness, we find that f (u1 , u2 , u0I1 \{1,2} , u0I2 ) = f (u1 , u02 , u0I1 \{1,2} , u0I2 ). 15 By sequentially replacing u0i by ui for each i ∈ I1 in this manner, we find thatf (uI1 , u0I2 ) = f (u0 ).

(4)

By (1) and Lemma 2, we find that ui = u0i for each i ∈ I2 . This implies thatf (u) = f (uI1 , u0I2 ).

(5)

By (4) and (5), we find that f (u) = f (u0 ).
Our theorem is tight. Nicolò (2004) characterizes social choice functions that satisfy strategyproofness, strong non-bossiness, and the balanceness of goods. Because the balanceness of goods isincompatible with non-wastefulness, they do not satisfy non-wastefulness. By applying the result of
Saijo, Sjöström, and Yamato (2007) in single-peaked voting environments, we find that they do not satisfy the rectangular property. 16 This finding implies that non-wastefulness is necessary for our theorem.
The following example shows that strategy-proofness is necessary for our theorem.
15 Note that strong non-bossiness implies non-bossiness.
16 Note that Nicolò (2004) uses the techniques in single-peaked voting environments to characterize them.

7g (u1 )f 2 (u )f 2 (u )g (u1 )g (u2 )

f1 (u )g (u2 )

f1 (u )# B(u) = 0# B(u) = 1, B(u) Ç Int( X ) = Æg (u1 )f (u )f (u )g (u1 )g (u2 )g (u2 )# B(u) = 1, B(u) Ç Int( X ) ¹ Æ# B(u) > 1

Figure 1: Allocation of f in Example

Example. Suppose that I = {1, 2} and K = {1, 2}. For each u ∈ U, let B(u) ≡ {x ∈ γ (u1 ) × γ (u2 ) | x1k +x2k = ek for each k ∈ K}. Let f be the social choice function such that for each u ∈ U,
(0, 0)
if #B(u) = 0,(0, 0)if #B(u) = 1 and B(u) ∩ Int(X ) = 0,/
f (u) =

x
if #B(u) = 1 and B(u) ∩ Int(X ) 6= 0,
/




((e1 /2, e2 /2), (e1 /2, e2 /2)) if #B(u) > 1,
where x ∈ B(u) ∩ Int(X ), #B(u) means the cardinality of B(u), and Int(X ) means the interior of X (seeFigure 1). Obviously, f satisfies non-wastefulness but not strategy-proofness.
We show that f satisfies strong non-bossiness. Let u, u0 ∈ U and i ∈ I be such that ui ( fi (ui , u0−i )) =ui ( fi (u0i , u0−i )). By the definition of f , this implies that fi (ui , u0−i ) = fi (u0i , u0−i ) and f j (ui , u0−i ) = f j (u0i , u0−i )for j 6= i. Thus, we find that f (ui , u0−i ) = f (u0i , u0−i ). This finding implies that f satisfies strong nonbossiness.
We show that f does not satisfy the rectangular property. Let u, u0 ∈ U be such that #B(u) > 1
and #B(u0 ) = 0. This implies that fi (ui , u0−i ) = fi (u0i , u0−i ) = 0 for each i ∈ I. Thus, we find thatui ( fi (ui , u0−i )) = ui ( fi (u0i , u0−i )) for each i ∈ I and f (u) 6= f (u0 ). This finding implies that f does not8

! (u2 )(u2 )

f 2 (u1 , u ! 1 ) " f 2 (u1!, u ! 1 )Figure 2: Generalization of Theorem

satisfy the rectangular property.
Remark 6. Our theorem is established even if an agent has a generalized Leontief utility function.
The key point is the existence of agents in I2 . Because Corollary 1 is independent of the property of thecritical sets, there is no problem in replacing utility functions for agents in I1 even if they have generalized
Leontief utility functions. However, there may be a problem in replacing utility functions for agents inI2 because Lemma 2 is dependent on the property of the critical sets as we stated in Section 4, Remark
5. Strategy-proofness solves this problem.
Per (1) in our theorem, let u, u0 ∈ U be such that f (ui , u0−i ) = f (u0i , u0−i ) for each i ∈ I. Without lossof generality, let 1, 2 ∈ I2 and f (u1 , u0−1 ) = f (u01 , u0−1 ). Note that f2 (u02 , u0−2 ) ∈ γ (u2 ), that is, γ (u2 )intersects with γ (u02 ) at f2 (u02 , u0−2 ) because f (ui , u0−i ) = f (u0i , u0−i ) for each i ∈ I (see Figure 2). By
non-wastefulness, we know that agent 2’s consumption assigned by f is in her critical set. This implies
that f2 (u1 , u2 , u0I1 , u0I2 \{1,2} ) is in γ (u2 ). By strategy-proofness, this implies that f2 (u1 , u2 , u0I1 , u0I2 \{1,2} ) =f2 (u1 , u02 , u0I1 , u0I2 \{1,2} ). 17 By non-bossiness, this implies that f (u1 , u2 , u0I1 , u0I2 \{1,2} ) = f (u1 , u02 , u0I1 , u0I2 \{1,2} ).
By sequentially replacing u0i by ui for each i ∈ I2 in this manner, we find that f (u0I1 , uI2 ) = f (u0 ). Together
with the argument for agents in I1 , this finding suggests that our theorem is established even if an agent
has a generalized Leontief utility function. Note that the tightness is confirmed by similar arguments inthe case of Leontief utility functions.
As previously stated, secure implementability is equivalent to the combination of strategy-proofness
and the rectangular property. On the other hand, full implementability in truthful strategies is equivalent
to the combination of strategy-proofness and strong non-bossiness. Because our theorem suggests thatthe rectangular property and strong non-bossiness are equivalent for strategy-proof and non-wastefulsocial choice function, the following corollary is established in pure exchange economies with Leontief
utility functions.
Corollary 2. Suppose that the social choice function satisfies non-wastefulness. The social choicefunction is securely implementable if and only if it is fully implementable in truthful strategies.
In our economies, Li and Xue (2011) demonstrate social choice functions that satisfy full implementability in truthful strategies and non-wastefulness in addition to certain desirable properties. 18
17 This is an advantage of imposing non-wastefulness that makes strategy-proofness weaker.
18 See Theorem 1 and Remark 3 in Li and Xue (2011).

9

Together with their demonstration, Corollary 2 implies the existence of desirable and securely implementable social choice functions in our economy.

6 Conclusion
This paper investigates the relationship between secure implementability and full implementability intruthful strategies in pure exchange economies with Leontief utility functions. In general, secure implementability is stronger than full implementability in truthful strategies. However, we find that the
opposite relationship is established if the social choice function satisfies non-wastefulness. Together
with the result of Li and Xue (2011), this relationship implies the existence of desirable and securely
implementable social choice functions contrary to almost all environments. Because of the observationsof Cason, Saijo, Sjöström, and Yamato (2006), this relationship suggests a possibility of constructing desirable mechanisms that work well in real-life pure exchange economies with Leontief utility functions.
This possibility promotes the study of secure implementation from the perspectives of both theory andexperiment.
The existence of desirable and securely implementable social choice functions is dependent on the
result of Li and Xue (2011). Because secure implementability is very weak in pure exchange economies
with Leontief utility functions, there exist many securely implementable social choice functions. Further
research is needed to characterize such social choice functions in different directions from that of Li andXue (2011) and study the domain-richness in pure exchange economies, as do Fujinaka and Wakayama(2008) in the problems of allocating indivisible and private goods with monetary transfers and Nishizaki(forthcoming) in queueing problems. These interesting topics remain for our future research.

References
Barberà, S. (2010) “Strategy-Proof Social Choice,” Barcelona Economics Working Paper Series 420,
Universitat Autònoma de Barcelona.
Barberà, S. and M. Jackson (1995) “Strategy-Proof Exchange,” Econometrica 63, pp.51-87.
Berga, D. and B. Moreno (2009) “Strategic Requirements with Indifference: Single-Peaked versus
Single-Plateaued Preferences,” Social Choice and Welfare 32, pp.275-298.
Bochet, O. and T. Sakai (2010) “Secure Implementation in Allotment Economies,” Games and Economic
Behavior 68, pp.35-49.
Cason, T., T. Saijo, T. Sjöström, and T.Yamato (2006) “Secure Implementation Experiments: Do
Strategy-Proof Mechanisms Really Work?” Games and Economic Behavior 57, pp.206-235.
Clarke, E. H. (1971) “Multipart Pricing of Public Goods,” Public Choice 11, pp.17-33.
Dasgupta P., P. Hammond P, and E. Maskin (1979) “The Implementation of Social Choice Rules: Some
General Results on Incentive Compatibility,” Review of Economic Studies 46, pp.185-216.

10

Fujinaka, Y. and T. Wakayama (2008) “Secure Implementation in Economies with Indivisible Objects
and Money,” Economics Letters 100, pp.91-95.
Fujinaka, Y. and T. Wakayama (2011) “Secure Implementation in Shapley-Scarf Housing Markets,” Economic Theory 48, pp.147-169.
Ghodsi, A., M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica (2011) “Dominant Resource Fairness: Fair Allocation of Multiple Resource Types,” Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation.
Groves, T. (1973) “Incentives in Teams,” Econometrica 41, pp.617-631.
Hashimoto, K. (2008) “Strategy-Proofness versus Efficiency on the Cobb-Douglas Domain of Exchange
Economies,” Social Choice and Welfare 31, pp.457-473.
Hurwicz, L. (1972) “On Informationally Decentralized Systems,” in Decision and Organization, edited
by C. B. McGuire and R. Radner, North-Holland.
Jackson, M. O. (2001) “A Crash Course in Implementation Theory,” Social Choice and Welfare 18,
pp.655-708.
Jackson, M. O. (2003) “Mechanism Theory,” in Encyclopedia of Life Support Systems, edited by U.
Derigs, EOLSS.
Ju, B.-G. (2003) “Strategy-proofness versus Efficiency in Exchange Economies: General Domain Properties and Applications,” Social Choice and Welfare 21, pp.73-93.
Kumar, R. (2009) “Secure Implementation in Production Economies,” mimeo.
Li, T. and J. Xue (2011) “Egalitarian Division under Leontief Preferences,” mimeo.
Maskin, E. (1977) “Nash Equilibrium and Welfare Optimality,” mimeo, the revised version appeared in
Review of Economic Studies 66 (1999) pp.23-38.
Maskin, E. and T. Sjöström (2002) “Implementation Theory,” in Handbook of Social Choice and Welfare,edited by K. Arrow, A. Sen, and K. Suzumura, North Holland.
Mizukami, H. and T. Wakayama (2007) “Dominant Strategy Implementation in Economic Environments,” Games and Economic Behavior 60, pp.307-325.
Mizukami, H. and T. Wakayama (2008) “Secure Implementation: An Alternative Characterization,”
Working Paper No. 238, University of Toyama.
Nicolò, A. (2004) “Efficiency and Truthfulness with Leontief Preferences. A Note on Two-Agent, TwoGood Economies,” Review of Economic Design 8, pp.373-382.
Nishizaki, K. (2011) “Secure Implementation in Discrete and Excludable Public Good Economies,” Osaka Economic Papers 61, pp.48-56.

11

Nishizaki, K. “Secure Implementation in Queueing Problems,” forthcoming in Theorelical Economics
Letters.
Repullo, R. (1987) “A Simple Proof of Maskin’s Theorem on Nash-Implementation,” Social Choice andWelfare 4, pp.39-41.
Ritz, Z. (1983) “Restricted Domains, Arrow-Social Welfare Functions and Noncorruptible and NonManipulable Social Choice Correspondences: The Case of Private Alternatives,” Mathematical Social
Science 4, pp.155-179.
Ritz, Z. (1985) “Restricted Domains, Arrow Social Welfare Functions and Noncorruptible and Nonmanipulable Social Choice Correspondences: The Case of Private and Public Alternatives,” Journal of
Economic Theory 35, pp.1-18.
Saijo, T. (1988) “Strategy Space Reduction in Maskin’s Theorem: Sufficient Conditions for Nash Implementation,” Econometrica 56, pp.693-700.
Saijo, T., T. Sjöström, and T.Yamato (2003) “Secure Implementation: Strategy-Proof Mechanisms Reconsidered,” RIETI Discussion Paper 03-E-019.
Saijo, T., T. Sjöström, and T. Yamato (2007) “Secure Implementation,” Theoretical Economics 2, pp.203229.
Satterthwaite, M. A. and H. Sonnenschein (1981) “Strategy-Proof Allocation Mechanisms at Differentiable Points,” Review of Economic Studies 48, pp.587-597.
Schummer, J. (1997) “Strategy-Proofness versus Efficiency on Restricted Domains of Exchange
Economies,” Social Choice and Welfare 14, pp.47-56.
Serizawa S. (2002) “Inefficiency of Strategy-Proof Rules for Pure Exchange Economies,” Journal of
Economic Theory 106, pp.219-241.
Serizawa S. and J. Weymark (2003) “Efficient Strategy-Proof Exchange and Minimum Consumption
Guarantees,” Journal of Economic Theory 109, pp.246-263.
Zhou, L. (1991) “Inefficiency of Strategy-Proof Allocation Mechanisms in Pure Exchange Economies,”
Social Choice and Welfare 8, pp.247-257.

12