Discussion Paper No. 699

SECURE IMPLEMENTATIONIN ECONOMIESWITH INDIVISIBLE OBJECTSAND MONEY
Yuji Fujinaka
Takuma Wakayama

October 2007

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

Secure Implementation in Economies with
Indivisible Objects and Money∗
Yuji Fujinaka†‡

Takuma Wakayama§

October 5, 2007

Abstract
This paper studies the application of the notion of secure implementation (Cason, Saijo, Sjöström, and Yamato, 2006; Saijo, Sjöström, and Yamato,2007) to the problem of allocating indivisible objects with monetary transfers.
We propose a new domain-richness condition, termed as minimal richness. We
then establish that on any minimally rich domain, only constant social choicefunctions are securely implementable.

Keywords: Secure implementation, Dominant strategy implementation, Nash
implementation, Indivisible goods, Strategy-proofness.
JEL codes: C72, C78, D61, D63, D71.

∗

We would like to thank an anonymous referee and the editor, Eric Maskin for helpful comments and suggestions. We are also grateful to Jun Iritani, Kaoru Ishiguro, Noritsugu Nakanishi,
Tatsuyoshi Saijo, Toyotaka Sakai, and Shohei Takagi for their helpful comments and discussions.
†
JSPS Research Fellow.
‡
Correspondence: ISER, Osaka University, 6-1 Mihogaoka Ibaraki Osaka 567-0047, JAPAN;+81-6-6879-9179; fujinaka@iser.osaka-u.ac.jp; http://www.geocities.jp/yuji fujinaka/§
Faculty of Urban Liberal Arts, Tokyo Metropolitan University, 1-1 Minami-Osawa, Hachioji,
Tokyo 192-0397, JAPAN; t waka@center.tmu.ac.jp; http://www.geocities.jp/takuma wakayama/

1

Introduction

In this paper, we study the problem of allocating indivisible objects when monetarytransfers are possible.1 We assume that each agent consumes one and only one
indivisible object. To illustrate the problem, let us consider a situation where a groupof regions jointly construct various types of public facilities. When a region accepts
a desirable facility such as a library, it can enjoy a utility. On the other hand, whenanother region accepts an undesirable facility such as a garbage disposal facility,
it must bear a disutility. Thus, there arises a need to assign such facilities among
regions and simultaneously distribute money to compensate for the diﬀerences in
the characteristics of facilities. This problem also applies to the allocation of houses
or rooms or to the assignment of jobs. In this model, each allocation consists of anassignment of indivisible objects and the speciﬁcation of an amount of money foreach agent. A social choice function (or direct revelation mechanism) is the functionthat associates an allocation with each preference proﬁle.
Strategy-proofness, which states that no one gains by preference misrepresentation, is a primary requirement in mechanism design. Saijo, Sjöström, and Yamato (2007) indicate that many strategy-proof mechanisms (to be exact, the directrevelation mechanisms associated with strategy-proof social choice functions) admit
multiple Nash equilibrium outcomes that are diﬀerent from the “true” outcome,thereby making these mechanisms somewhat ineﬀective.2 Therefore, Cason, Saijo,
Sjöström, and Yamato (2006) and Saijo, Sjöström, and Yamato (2007) develop a newconcept, namely, secure implementation. A social choice function is securely implementable if there exists a mechanism that implements it through dominant strategy
equilibria and if the set of dominant strategy equilibrium outcomes coincides withthe set of Nash equilibrium outcomes.3
Our purpose is to examine the social choice functions that are securely implementable in our economies.4 We provide a new mild domain-richness condition,termed as minimal richness. Then, we show that on any minimally rich domain,
only constant social choice functions are securely implementable.
This paper is organized as follows: Section 2 deﬁnes the basic notions as wellas the concept of secure implementation, and introduces the concept of minimalrichness. Section 3 provides the primary result. Section 4 concludes the paper.

1

Basic models of economies with indivisible objects and monetary transfers were provided by
Svensson (1983) and Alkan, Demange, and Gale (1991).
2
The results of the experiments conducted by Cason, Saijo, Sjöström, and Yamato (2006)
support this idea.
3
In other words, secure implementation signiﬁes double implementation in dominant strategy
equilibria and Nash equilibria. Fujinaka and Sakai (2006) present a study of Nash implementationin our economies.
4
In several economic environments, some results on secure implementation have been established. For example, Saijo, Sjöström, and Yamato (2007) for economies with a public good andmoney, and Bochet and Sakai (2007) for allotment economies with single-peaked preferences.

1

2

Model

2.1

Basic Notion

Let I ≡ {1, 2, . . . , n} be a ﬁnite set of agents. There are ﬁnite types of indivisible
objects T ≡ {1, 2, . . . , s} and a divisible good which is called “money.” For eachtype t ∈ T , let αt ≥ 1 be the integer number of type-t indivisible objects. In thispaper, we assume the following.
∑
A1.
t∈T αt ≥ n.
A2. Each agent i ∈ I has the consumption space denoted by T × R.
A1 states that the total number of indivisible objects is at least as great as thenumber of agents, while A2 states that each agent consumes precisely one indivisible
object and an amount of money. A consumption bundle in T × R is denoted by(t, mi ), where t ∈ T denotes a type-t object, and mi ≥ 0 (mi < 0) denotes theamount of money that agent i receives (pays).
It should be noted that A1 allows us to deal with the case where the numberof indivisible objects are less than the number of agents. To observe this, let us
consider a situation where there is the only one type of indivisible object and thenumber of objects of this type is one, i.e., T = {1} and α1 = 1. In this situation, all
the agents, except one, cannot receive any indivisible object. Therefore, they cannot
enjoy any utility from the assignment of the indivisible object. Now, we additionallyconsider a ﬁctitious object, say, a “null” object, from whose type no agent can gain
any utility. If we regard the null object as a type-2 object, we can rewrite thesituation as follows: T 0 = {1, 2}, α1 = 1, and α2 = n − 1. If we interpret that theagents who are initially not assigned a type-1 object receive a type-2 object, eachanalysis on the new situation corresponds to one on the initial situation. Therefore,
based on our assumptions, we can deal with the situation where there is only one
indivisible object.
Each agent’s preferences over T × R are quasi-linear with respect to money.
If agent i consumes a type-t object and her monetary transfer is mi ∈ R, then her
utility level is vi (t)+mi , where vi (t) ∈ R is agent i’s valuation for a type-t object. Let
Vi (t) ⊆ R be a non-empty set of i’s valuation∏ for a type-t object. Agent i’s valuation
vector is vi ≡ (vi (t))t∈T ∈ RT . Let Vi ≡ t∈T Vi (t) ⊆ RT be the set of valuation
vectors for agent i. We denote a proﬁle of valuation ∏vectors by v ≡ (v1 , v2 , . . . , vn ),and the set of proﬁles of valuation vectors by V ≡ i∈I Vi . The set V is called adomain. Since agents’ preferences are usually unknown to a mechanism designer,
the following assumption is natural and reasonable.
A3. There exist i ∈ I and t ∈ T such that |Vi (t)| ≥ 2.5
We often denote I \ {i} by “−i,” and I \ {i, j} by “−i, j.” With this notation,(vi0 , v−i ) is the proﬁle of valuation vectors where agent i has vi0 and agent j 6= i has
vj . We deﬁne (vi0 , vj0 , v−i,j ) similarly.
5

Given a set A, we denote the cardinality of A by |A|.

2

An assignment is a list σ ≡ (σ1 , σ2 , . . . , σn ) such thatσi ∈ T for each i ∈ I,|{i ∈ I : σi = t}| ≤ αt for each t ∈ T.
Given i ∈ I, σi is the object assigned to agent i, and σi = t means that agent i
receives a type-t object. A monetary transfer is a list m ≡ (m1 , m2 , . . . , mn ) suchthat mi ∈ R for each i ∈ I. Note that we do not require any feasibility constraint
on monetary transfers. If we establish an impossibility result, this strengthens theresult. An allocation is a list (σ, m) ∈ T I × RI such that σ is an assignment and m
is a monetary transfer.
A social choice function on a domain V is a function f : V → T I ×RI associatingwith each proﬁle of valuation vectors v ∈ V an allocation f (v) ≡ (fi (v))i∈I ∈ T I ×RI .
For convenience, given v ∈ V and i ∈ I, we write fi (v) ≡ (σi (v), mi (v)).

2.2

Secure Implementation

A social choice function is securely implementable if there exists a mechanism thatsimultaneously implements the social choice function in dominant strategy equilibria
and Nash equilibria.6 In this paper, we would like to characterize the class of
securely implementable social choice functions in our economies. Saijo, Sjöström,
and Yamato (2007) provide a characterization of the class in the general model7 : A
social choice function is securely implementable if and only if it satisﬁes strategyproofness and the rectangular property.
Strategy-proofness: For each v ∈ V , each i ∈ I, and each vi0 ∈ Vi , vi (σi (v)) +mi (v) ≥ vi (σi (vi0 , v−i )) + mi (vi0 , v−i ).
0
Rectangular Property: For each v, v 0 ∈ V , if vi (σi (v 0 ))+mi (v 0 ) = vi (σi (vi , v−i))+00mi (vi , v−i ) for each i ∈ I, then f (v ) = f (v).

2.3

Minimal Richness

We now present a new domain-richness condition, called minimal richness. In orderto formally deﬁne minimal richness, we use the following notation. Given i ∈ I,vi ∈ Vi , and t0 , t00 ∈ T , let ∆vi (t0 ; t00 ) ≡ vi (t0 ) − vi (t00 ).
Minimal Richness: For each i ∈ I, each vi0 , vi00 ∈ Vi , each t0 , t00 ∈ T , and eachM ∈ R, if ∆vi0 (t0 ; t00 ) > M > ∆vi00 (t0 ; t00 ), there exists vi∗ ∈ Vi such that(i) ∆vi∗ (t0 ; t00 ) = M ,(ii) ∆vi0 (t; t00 ) ≥ ∆vi∗ (t; t00 ) for each t ∈ T \ {t0 , t00 }.
6

See Saijo, Sjöström, and Yamato (2007) for the formal deﬁnition of secure implementation.
Mizukami and Wakayama (2007) provide an alternative characterization of securely implementable social choice functions.
73

Minimal richness requires that for any agent i ∈ I, any distinct valuation vectors

vi0 , vi00 ∈ Vi , any distinct types t0 , t00 ∈ T , and any real number M ∈ R, if the number
M lies in the range from ∆vi00 (t0 ; t00 ) to ∆vi0 (t0 ; t00 ), there exists another valuation
vector vi∗ ∈ Vi satisfying the following: (i) ∆vi∗ (t0 ; t00 ) is equal to the number M , and(ii) the value of t00 for vi∗ , relative to any other types, is greater than or equal to thatof t00 for vi0 .
Since many reasonable domains satisfy minimal richness, it is considered as amild requirement for domains in our model. The following domain, which is referred
to as a box-shaped domain, is an example of a minimally rich domain.8 It roughly
states that Vi (t) takes the form of a certain interval for each i ∈ I and each t ∈ T .
Box-shapedness: For each i ∈ I, each t ∈ T , and each vi (t), vi0 (t) ∈ Vi (t) withvi0 (t) ≥ vi (t), vi00 (t) ∈ Vi (t) for each vi00 (t) ∈ [vi (t), vi0 (t)].
Let V U , V G , and V B be domains such that any vector of valuations are possible,
each type of indivisible object is “good” and each is “bad”; i.e., for each i ∈ I
and each t ∈ T , ViU (t) = R, ViG (t) = R+ , and ViB (t) = R− .9 By the deﬁnition ofbox-shapedness, these are box-shaped domains, and therefore, are minimally richdomains.
Given t ∈ T , if Vi (t) = {0} for each i ∈ I, i.e., no agent gains any utility from thetype-t object, then type-t objects can be interpreted as “null.” Box-shaped domains
include the case where some types are null objects, since the singleton is an interval.
Thus, minimally rich domains also include the abovementioned case.
We will now provide an example of non-minimally rich domains.
Example 1. Let I = {1, 2} and T = {1, 2}. Let V ∗ be such that V1∗ (2) = V2∗ (2) ={0}, V1∗ (1) = R \ {1}, and V2∗ (1) = R. To observe that V ∗ is not minimally rich, let
v10 , v100 ∈ V1∗ be such that v10 (1) = 2 and v100 (1) = 0. Let M = 1. Then, there is nov1∗ ∈ V1∗ such that v1∗ (1) − v1∗ (2) = M .
¥The key is that V1∗ is not connected. In the domain V ∗ , it is not permissible foragent 1 to have the valuation vector (1, 0); nevertheless, valuation vectors arbitrarilyclose to (1, 0) are permissible. In this sense, such non-connected domains are notreasonable. Therefore, we can consider that minimal richness is a mild requirement.

3

TheoremIn this section, we consider the set of securely implementable social choice functions
whose domains are minimally rich. The next proposition characterizes the class ofsocial choice functions satisfying strategy-proofness and the rectangular property.

8

The relationship between the two domain conditions is discussed in the supplementary notethat is available online at: http://www.iser.osaka-u.ac.jp/library/dp/2007/DP0699N.pdf
9R+ and R− denote the set of nonnegative real numbers and nonpositive real numbers, respectively.

4

Proposition 1. Suppose that V is minimally rich. Then, a social choice function
f on V satisﬁes strategy-proofness and the rectangular property if and only if it isconstant.
Proof. Since the “if” part is obvious, we only show the “only if ” part. Suppose that
V is a minimally rich domain and that a social choice function f satisﬁes strategyproofness and the rectangular property. In what follows, we will prove the following
four claims.
Claim 1. For each i ∈ I, each v`i ∈ V`i , and each vi , vi0 ∈ Vi , if
σi (vi , v`i ) = σi (vi0 , v`i ), then mi (vi , v`i ) = mi (vi0 , v`i ): Suppose, by contradiction, that there exist i ∈ I, v−i ∈ V−i , and vi , vi0 ∈ Vi such that σi (vi , v−i ) =σi (vi0 , v−i ) and mi (vi , v−i ) 6= mi (vi0 , v−i ). Without loss of generality, mi (vi , v−i ) >mi (vi0 , v−i ). Then agent i with the valuation vector vi0 can gain by announcing thefalse valuation vi , contradicting strategy-proofness.
Claim 1 states us that given agent j 6= i announce vj , agent i’s consumption
bundle depends on the type of the indivisible object that she receives. Thus, when
agent i is assigned to type-t object, we denote her consumption bundle allocated toagent i by (t, mti ). Let Oi (v−i ) be the option set for agent i given v−i , deﬁned byOi (v−i ) ≡ {t ∈ T : ∃vi ∈ Vi such that fi (vi , v−i ) = (t, mti )}.
This is the set of the types of indivisible objects that agent i can obtain by changing
her valuation vector.
Claim 2. For each v ∈ V , each i ∈ I, and each t ∈ T such that0fi (v) = (t, mti ), if |Oi (v`i )| ≥ 2, then vi (t) + mti > vi (t0 ) + mti for eacht0 ∈ Oi (v`i ) \ {t}: Suppose, by contradiction, that there exist v ∈ V , i ∈ I
0and t ∈ T such that fi (v) = (t, mti ), |Oi (v−i )| ≥ 2, and vi (t) + mti ≤ vi (t0 ) + mti
for some t0 ∈ Oi (v−i ) \ {t}. Since t0 ∈ Oi (v−i ), there exists vi0 ∈ Vi such that0fi (vi0 , v−i ) = (t0 , mt ). There are two cases.
0
Case 2-1. vi (t) + mti < vi (t0 ) + mti : In this case, we havevi (σi (v)) + mi (v) < vi (σi (vi0 , v−i )) + mi (vi0 , v−i ),which is a contradiction to strategy-proofness.
0
Case 2-2. vi (t) + mti = vi (t0 ) + mti : Since t 6= t0 , f (v) 6= f (vi0 , v−i ). However,0since vi (t) + mti = vi (t0 ) + mti , we havevi (σi (vi0 , v−i )) + mi (vi0 , v−i ) = vi (σi (v)) + mi (v),vj (σj (vi0 , vj , v−i,j )) + mj (vi0 , vj , v−i,j ) = vj (σj (vi0 , vj , v−i,j )) + mj (vi0 , vj , v−i,j ) for each j 6= i,which is a contradiction to the rectangular property.
Claim 3. For each i ∈ I and each v`i ∈ V`i , |Oi (v`i )| = 1: Suppose,by contradiction, that there exist i ∈ I and v−i ∈ V−i such that |Oi (v−i )| ≥ 2. Let0t0 ∈ Oi (v−i ). Since t0 ∈ Oi (v−i ), there exists vi0 ∈ Vi such that fi (vi0 , v−i ) = (t0 , mt ).

5

Now, select any of the following:t00 ∈ argmaxt∈Oi (v−i )\{t0 }vi0 (t) + mti .

(1)00

Since t00 ∈ Oi (v−i ), there exists vi00 ∈ Vi such that fi (vi00 , v−i ) = (t00 , mti ). Let
000
M ≡ mti − mti . By Claim 2, we have
00

0

0

00

∆vi0 (t0 ; t00 ) = vi0 (t0 ) − vi0 (t00 ) > mti − mti = M,−∆vi00 (t0 ; t00 ) = vi00 (t00 ) − vi00 (t0 ) > mti − mti = −M.
Therefore, ∆vi0 (t0 ; t00 ) > M > ∆vi00 (t0 ; t00 ). Since V is minimally rich, there existsvi∗ ∈ Vi such that (i) ∆vi∗ (t0 ; t00 ) = M and (ii) ∆vi0 (t; t00 ) ≥ ∆vi∗ (t; t00 ) for eacht ∈ T \ {t0 , t00 }. Condition (i) implies that000vi∗ (t0 ) + mti = vi∗ (t00 ) + mti .

(2)

Condition (ii) and (1) together imply that for each t ∈ Oi (v−i ) \ {t0 , t00 },00

mti − mti ≥ ∆vi0 (t; t00 ) ≥ ∆vi∗ (t; t00 ).
Therefore, we have00vi∗ (t00 ) + mti ≥ vi∗ (t) + mti for each t ∈ Oi (v−i ) \ {t0 , t00 }.

(3)

By (2) and (3),000vi∗ (t0 ) + mti = vi∗ (t00 ) + mti ≥ vi∗ (t) + mti for each t ∈ Oi (v−i ).

(4)∗

Let fi (vi∗ , v−i ) = (t∗ , mti ). Thus, strategy-proofness and (4) together imply that
0

00

∗

vi∗ (t0 ) + mti = vi∗ (t00 ) + mti = vi∗ (t∗ ) + mti ,which is a contradiction to Claim 2.
Claim 4. f (v) = f (v 0 ) for each v, v 0 ∈ V : Let v, v 0 ∈ V . By Claim00003, fi (vi0 , v−i) = fi (vi , v−i) for each i ∈ I. Therefore, vi (σi (vi0 , v−i)) + mi (vi0 , v−i) =00vi (σi (vi , v−i )) + mi (vi , v−i ) for each i ∈ I. By the rectangular property, we canconclude that f (v) = f (v 0 ).
It can be easily checked the tightness of Proposition 1.10 Proposition 1 suggeststhat strategy-proofness and the rectangular property together imply constancy. However, this impossibility result relies on the domain—on which social choice functions
are required to satisfy the two properties—being minimally rich. In fact, unlessthe domain is minimally rich, there may exist a non-constant social choice function
satisfying the two properties. To observe this, we return to Example 1.
10

The independence of axioms is established in the supplementary note that is available online
at: http://www.iser.osaka-u.ac.jp/library/dp/2007/DP0699N.pdf

6

Example 1 (continued). Let f be a social choice function such that for eachv ∈V,{((1, 0), (2, 0))
if v1 (1) > 1,
f (v) =((2, 1), (1, −1)) otherwise.
Then, the social choice function f on V ∗ satisﬁes both strategy-proofness and therectangular property; however, it is not constant.
¥
Remark 1. Schummer (2000) proposes another domain-richness condition, called
monotonic closedness: For each i ∈ I, each vi0 ∈ Vi , and each t0 ∈ T , there exists
vi00 ∈ Vi such that ∆vi00 (t0 ; t00 ) > ∆vi0 (t0 ; t00 ) for each t00 ∈ T \ {t0 }. It is easy to observethat V ∗ is monotonically closed. Thus, Example 1 implies that a monotonicallyclosed domain is not minimally rich and that on a monotonically closed domain,
there exists a non-constant social choice function that is securely implementable.
Based on Saijo, Sjöström, and Yamato (2007) and our proposition, we can obtainthat no non-constant social choice function can be securely implementable.
Theorem 1. Suppose that V is minimally rich. Then, a social choice function f on
V is securely implementable if and only if it is constant.

4

Conclusion

In this study, we applied the notion of secure implementation to the problem of
allocating indivisible objects with monetary transfers. We then established that
only constant social choice functions on a minimally rich domain can be securely
implemented. This negative result suggests that all non-trivial strategy-proof social
choice functions do not work well in our environment.
In the following, we discuss a remaining problem. Our study leaves open thequestion of what class of social choice functions are securely implementable without
employing a minimally rich domain. We give a partial answer to the open question.
The discussion is based on dual dominance proposed by Saijo (1987). He shows thata social choice function satisﬁes dual dominance and Maskin monotonicity (Maskin,1999) if and only if it is constant. Therefore, it is easy to establish that a secure
implementable social choice function satisﬁes dual dominance if and only if it isconstant. Furthermore, we can strengthen this result by replacing dual dominanceby a weaker condition of social choice functions.11 However, it is open that verifying which social choice functions are securely implementable without imposing
additional conditions of social choice functions and minimal richness.

11

See for detailed discussion the supplementary note which is available online at:
http://www.iser.osaka-u.ac.jp/library/dp/2007/DP0699N.pdf

7

References
Alkan, A., G. Demange, and D. Gale (1991) “Fair Allocation of Indivisible Goods
and Criteria of Justice,” Econometrica 59, 1023–1039.
Bochet, O. and T. Sakai (2007) “Secure Implementation in Allotment Economies,”
mimeo, Maastricht University and Yokohama National University.
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, 206–235.
Fujinaka, Y. and T. Sakai (2006) “Maskin Monotonicity in Economies with Indivisible
Goods and Money,” Economics Letters 94, 253–258.
Maskin, E. (1999) “Nash Equilibrium and Welfare Optimality,” Review of Economic
Studies 66, 23–38.
Mizukami, H., and T. Wakayama (2007) “Full-truthful Implementation in Nash Equilibria,” Research Paper Series No.27, Tokyo Metropolitan University.
Saijo, T. (1987) “On Constant Maskin Monotonic Social Choice Functions,” Journalof Economic Theory 42, 382–386.
Saijo, T., T. Sjöström, and T. Yamato (2007) “Secure Implementation,” Theoretical
Economics 2, 203–229.
Schummer, J. (2000) “Manipulation through Bribes,” Journal of Economic Theory
91, 180–198.
Svensson, L.G. (1983) “Large Indivisibles: An Analysis with Respect to Price Equilibrium and Fairness,” Econometrica 51, 939–954.

8