Discussion Paper No. 727

SECURE IMPLEMENTATIONIN SHAPLEY-SCARF
HOUSING MARKETS

Yuji Fujinaka
andTakuma Wakayama

December 2008
Revised February 2009

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

Secure implementation in Shapley-Scarf
housing markets∗
Yuji Fujinaka†

Takuma Wakayama‡

February 19, 2009

Abstract
This paper considers the object allocation problem introduced by Shapley and Scarf (1974). We study secure implementation (Saijo, Sjöström, andYamato, 2007), that is, double implementation in dominant strategy and Nashequilibria. We prove that (i) an individually rational solution is securely implementable if and only if it is the no-trade solution, (ii) a neutral solution
is securely implementable if and only if it is a serial dictatorship, and (iii)
an eﬃcient solution is securely implementable if and only if it is a sequential
dictatorship. Furthermore, we provide a complete characterization of securely
implementable solutions in the two-agent case.
Keywords: Secure implementation; Sequential dictatorship; Strict core; Strategyproofness, Shapley-Scarf housing markets.
JEL codes: C72; C78; D61; D63; D71.

∗

We thank Toyotaka Sakai, Koji Takamiya, Jun Wako, and Takahiro Watanabe for their helpfulcomments. Wakayama gratefully acknowledges the ﬁnancial support by KAKENHI (20730135).
†
JSPS Research Fellow/ Institute of Social and Economic Research, Osaka University,
6-1 Mihogaoka, Ibaraki, Osaka 567-0047, JAPAN; E-mail: fujinaka@iser.osaka-u.ac.jp;
URL: http://www.geocities.jp/yuji fujinaka/‡
Institute of Social and Economic Research, Osaka University, 6-1 Mihogaoka, Ibaraki, Osaka
567-0047, JAPAN; wakayama@iser.osaka-u.ac.jp; http://www.geocities.jp/takuma wakayama/

1

Introduction

We consider the object allocation problem introduced by Shapley and Scarf (1974)
with strict preferences. There is a group of agents, each of whom initially owns
one object.1 A solution reallocates the objects with the condition that each agent
consumes one and only one object. Important real-life examples of this model are
the assignment of campus housing to students (Abdulkadiroǧlu and Sönmez, 1999;
Chen and Sönmez, 2002, 2004; and Sönmez and Ünver, 2005) and kidney exchange(Roth, Sönmez, and Ünver, 2004).
In this context, the “strict core solution” is a central one since it satisﬁes various desirable properties. Some characterizations of the solution can be found in
Ma (1994), Svensson (1999), Takamiya (2001), and Miyagawa (2002). Furthermore,
the solution is dominant strategy implementable (Mizukami and Wakayama, 2007)
and Nash implementable when there are at least three agents (Sönmez, 1996). However, these results do not guarantee that the solution is securely implementable (Saijo,
Sjöström, and Yamato, 2007); note that here, the notion of implementation signiﬁes
double implementation in the two equilibrium concepts. Thus, it is natural to raise
the following question: Can the strict core solution be securely implemented? Infact, the answer to this question is no (Saijo, Sjöström, and Yamato, 2007). Basedon the result, this paper seeks solutions that can be securely implemented in ourmodel.
Our main results consist of two parts. We ﬁrst focus on the two-agent case.
In this case, we provide a complete characterization of securely implementable solutions; a solution is securely implementable if and only if it is either a constantsolution or a “serial dictatorship.” By a serial dictatorship, we mean that one agent
chooses her best object from among the set of objects, then the second agent chooses
his best object from among the set of remaining objects, then the third agent chooses,
and so on; the order in which agents make their choices is ﬁxed in advance.
Next, we consider the general case where there are more than two agents. In
contrast to the two-agent case, it is hard to characterize the class of securely implementable solutions in the general case. Thus, in the general case, we then pin
down smaller classes of securely implementable solutions by adding some properties.
1

In this paper, the sets of agents and objects are ﬁxed. Some studies consider object allocation
problems where either the set of agents or the set of objects varies; for instance, Ergin (2000),
Ehlers, Klaus, and Pápai (2002), and Ehlers and Klaus (2003a) consider house allocation problems
where each agent consumes at most one object, and Klaus and Miyagawa (2001) and Ehlers andKlaus (2003b) consider multiple assignment problems where agents may consume more than one
object.

1

First, we show that the “no-trade solution” is the unique securely implementable
one that satisﬁes individual rationality (no agent is worse oﬀ after trading with otheragents). The no-trade solution is the one that selects the initial endowments for eachpreference proﬁle. Second, we prove that a securely implementable solution satisﬁes
neutrality (symmetric treatment of objects) if and only if it is a serial dictatorship.
Finally, we establish that an eﬃcient solution is securely implementable if and only
if it is a “sequential dictatorship.” For any sequential dictatorship, there exists theﬁrst dictator in every preference proﬁle. However, in contrast to serial dictatorships,
in the sequential dictatorship, the second agent, who chooses his best object fromamong the set of remaining objects, is decided by the choice of the ﬁrst dictator.
Similarly, the third agent is decided by the choices of the previous agents, and so on.
As far as we know, ours is the ﬁrst result that characterizes the class of sequential
dictatorships in Shapley-Scarf housing markets.
Our model has a close relationship with multiple assignment problems. Klaus
and Miyagawa (2001) show that serial dictatorships are the only ones that satisfy
eﬃciency and strategy-proofness in the two-agent case. In the general case, Pápai(2001) and Ehlers and Klaus (2003b) characterize sequential dictatorships by means
of eﬃciency, strategy-proofness, and non-bossiness. Their characterizations still holdeven if strategy-proofness and non-bossiness are replaced by secure implementability.
On the other hand, it should be noted that the results of Klaus and Miyagawa(2001), Pápai (2001), and Ehlers and Klaus (2003b) do not hold in our model. Thisis because the strict core solution satisﬁes eﬃciency, strategy-proofness, and nonbossiness. Therefore, results in multiple assignment problems cannot directly apply
to our model.
When monetary transfers are admissible, Fujinaka and Wakayama (2008) showthat constant solutions are the only ones that are securely implementable. Thismeans that many solutions including “ﬁxed-price core solutions” (Miyagawa, 2001)
that satisfy many desirable properties are not securely implementable when monetary transfers are allowed.
The rest of the paper is organized as follows: Section 2 provides basic notationand deﬁnitions. Section 3 addresses the two-agent case. Section 4 analyzes thegeneral case. Section 5 discusses our results. Section 6 concludes the paper. Appendix A contains the proofs of the results omitted from the main text. Appendix
B proves that the strict core solution is dominant strategy implemented by its associated direct revelation mechanism; further, the strict core solution is not Nash
implementable in the case of two agents.

2

2Preliminaries

2.1

The model

We denote the set of agents by N = {1, 2, . . . , n}, where 2 ≤ n < +∞. Each agenti ∈ N owns one object, denoted by i. Thus, N also stands for the set of objects.
Each agent i ∈ N has a complete and transitive binary relation %i over N , i.e.,a preference relation. We denote the associated strict preference relation by Âi andindiﬀerent relation by ∼i . We assume that all preferences are strict; i.e., for eachh, k ∈ N , if h ∼i k, then h = k. Let P denote the set of all strict preferences.
A preference proﬁle is a list of preferences % ≡ (%1 , %2 , . . . , %n ) ∈ P N . We often
denote N \ {i} by “−i.” With this notation, (%0i , %−i ) is the preference proﬁle where
agent i has %0i and agent j 6= i has %j . Similarly, given S ⊆ N , we denote N \ S
by “−S,” and (%0S , %−S ) is the preference proﬁle where each agent i ∈ S has %0i
and each agent i ∈/ S has %i . We often represent %i by an ordered list of objects asfollows:%i : h1 , h2 , h3, . . .
This means that agent i prefers object h1 the most; further, i prefers h1 to h2 , h2 to
h3 , and so on.
An allocation is a bijection x : N → N . Let x(i) denote the object allocated toagent i ∈ N . For convenience, we use the notation xi instead of x(i). Let X be theset of allocations.

2.2

Solutions

A solution is a function f : P N → X that associates an allocation x ∈ X with eachpreference proﬁle % ∈ P N . Let fi (%) denote the object allocated to agent i at %.
Let x, y ∈ X and S ⊆ N with S 6= ∅. Then, x weakly dominates y via S at∪
% ∈ P N if S = i∈S {xi }, and xi %i yi for each i ∈ S and xj Âj yj for somej ∈ S. The strict core for % ∈ P N is the set of all allocations that are not weakly
dominated by any other allocation at % ∈ P N . The strict core solution is thesolution C : P N → X such that for each % ∈ P N , C(%) is the strict core for %.2
A solution f is constant if there exists x ∈ X such that for each % ∈ P N ,2Under strict preferences, the strict core is a singleton for every preference proﬁle (Roth andPostlewaite, 1977). Thus, the strict core solution C is well-deﬁned.

3f (%) = x. In particular, we term the constant solution that selects the initialendowments for each preference proﬁle as the no-trade solution.
A permutation π on N is a bijection π : N → N . Let ΠN denote the set of all
permutations on N . Given that i ∈ N and S ⊆ N , let b(%i , S) be agent i’s most
preferred object under %i in S, i.e., b(%i , S) ∈ S and for each h ∈ S, b(%i , S) %i h.
A solution f is a sequential choice function if for each % ∈ P N , there exists a
permutation π% ∈ ΠN such that
fπ% (1) (%) = b(%π% (1) , N );fπ% (2) (%) = b(%π% (2) , N \ {fπ% (1) (%)});
fπ% (3) (%) = b(%π% (3) , N \ [{fπ% (1) (%)} ∪ {fπ% (2) (%)}]);
..
.
])
(
\[n−1
}
∪{
fπ% (i) (%).
fπ% (n) (%) = b %π% (n) , N
i=1

We then say that π%(i) is the i-th dictator at %.
The class of sequential dictatorships is a subclass of sequential choice functions.
For any sequential dictatorship, there exists a unique ﬁrst dictator who chooses her
best object in every preference proﬁle. However, the second dictator, who chooses hisbest object from among the set of remaining objects, is decided by the choice of theﬁrst dictator. Similarly, the next dictator is decided by the choices of the previous
dictators. Formally, a solution f is a sequential dictatorship if it is a sequential choicefunction that satisﬁes the following properties: for each %, %0 ∈ P N , (i) π%(1) =π%0 (1) and (ii) for each j ∈ N \ {1}, if π%(i) = π%0 (i) and fπ% (i) (%) = fπ% 0 (i) (%0 ) for
each i ∈ {1, 2, . . . , j − 1}, then π%(j) = π%0 (j).
The class of serial dictatorship is a subclass of sequential dictatorships. For any
serial dictatorship, the order in which an agent chooses an object from the set ofremaining objects is ﬁxed. That is, the order does not depend on the choices of theprevious dictators. Formally, a solution f is a serial dictatorship if it is a sequential
dictatorship and there exists π̄ ∈ ΠN such that for each % ∈ P N , π% = π̄.

2.3

Axioms and secure implementation

In this subsection, we ﬁrst deﬁne a number of basic axioms. The ﬁrst axiom is avoluntary participation condition, according to which no agent receives an object
that she considers worse than her endowment.

4

Individual rationality: For each % ∈ P N and each i ∈ N , fi (%) %i i.
The next axiom says that it is impossible to make an agent better oﬀ without
making someone else worse oﬀ.
Eﬃciency: For each % ∈ P N , there does not exist x ∈ X such that xi %i fi (%)
for each i ∈ N and xj Âj fj (%) for some j ∈ N .
The next axiom states that a solution is deﬁned independently of the names ofthe objects. For each % ∈ P N and each π ∈ ΠN , let T (%, π) be a preference proﬁle%0 such that for each i, j, k ∈ N ,j %i k ⇐⇒ π(j) %0i π(k).
Neutrality: For each % ∈ P N , each π ∈ ΠN , and each i ∈ N , fi (T (%, π)) =π(fi (%)).
The last axiom states that no agent can obtain a beneﬁt by misrepresenting her
preferences.
Strategy-proofness: For each % ∈ P N , each i ∈ N , and each %0i ∈ P, fi (%) %ifi (%0i , %−i ).
The strict core solution is the central solution in our model. The reason for this isthat the strict core solution is the only one that satisﬁes strategy-proofness, eﬃciency,
and individual rationality (Ma, 1994).3 Moreover, the solution is dominant strategy
implementable (See Appendix B) and Nash implementable when there are at least
three agents (Sönmez, 1996).
Saijo, Sjöström, and Yamato (2007) say that a solution is securely implementable
if there exists a mechanism that doubly implements the solution in dominant strategy and Nash equilibria.4 They provide a characterization of the class in the abstract
setting:5
Proposition 1 (Saijo, Sjöström, and Yamato, 2007). A solution is securely
implementable if and only if it satisﬁes strategy-proofness and the rectangular property.
3

The strict core solution satisﬁes not only strategy-proofness (Roth, 1982) but also coalitional
strategy-proofness (Bird, 1984). Other studies on coalitional strategy-proofness are, for example,
Takamiya (2001) and Ehlers (2002). See those for the deﬁnition of coalitional strategy-proofness.
4
See Saijo, Sjöström, and Yamato (2007) for the formal deﬁnition of secure implementation.
5
Mizukami and Wakayama (2008) provide an alternative characterization of securely implementable solutions.

5

Rectangular property: For each %, %0 ∈ P N , if fi (%0 ) = fi (%i , %0−i ) for eachi ∈ N , then f (%) = f (%0 ).
Note that the rectangular property implies non-bossiness, according to which
when each agent unilaterally changes her preference report, she cannot inﬂuence thetotal allocation without changing her own consumption.
Non-bossiness: For each % ∈ P N , each i ∈ N , and each %0i ∈ P, if fi (%) =fi (%0i , %−i ), then f (%) = f (%0i , %−i ).
Fact 1. If f satisﬁes the rectangular property, then it satisﬁes non-bossiness.
Since the strict core solution is both dominant strategy implementable and Nash
implementable, one might conjecture that it is securely implementable. However,
Saijo, Sjöström, and Yamato (2004) point out that the strict core solution is notsecurely implementable.6 To see this, consider the following example:
Example 1. Suppose that N = {1, 2, 3}. Let % ∈ P N and %01 , %02 ∈ P be suchthat
%1 : 1, 2, 3;%01 : 2, 1, 3;%2 : 1, 2, 3;%02 : 2, 1, 3;%3 : 3, 2, 1.
Then,C(%1 , %2 , %3 ) = C(%1 , %02 , %3 ) = C(%01 , %02 , %3 ) = (1, 2, 3);C(%01 , %2 , %3 ) = (2, 1, 3).
Since C(%1 , %02 , %3 ) = C(%01 , %02 , %3 ) and C(%1 , %02 , %3 ) = C(%1 , %2 , %3 ), the rectangular property requires that C(%1 , %02 , %3 ) = C(%01 , %2 , %3 ). However, since
C(%1 , %02 , %3 ) 6= C(%01 , %2 , %3 ), the strict core solution violates the rectangularproperty and is thus not securely implementable.7¥
Thus, this paper seeks to identify which solutions are securely implementable.
6

Saijo, Sjöström, and Yamato (2004) illustrate this for the two-agent case. However, as we show
in Appendix B, the strict core solution is not even Nash implementable in the two-agent case. On
the other hand, it is Nash implementable when there are at least three agents. Thus, it is not
obvious whether the strict core solution is securely implementable when there are three or moreagents.
7This can be directly derived from Theorem 2.

6

3

The two-agent caseIn this section, we consider the two-agent case. For each i ∈ N , let%12
i : 1, 2;%21
i : 2, 1.
Proposition 2 provides a complete characterization of the class of solutions satisfying
strategy-proofness and the rectangular property in the two-agent case.
Proposition 2. Assume n = 2. A solution f satisﬁes strategy-proofness and therectangular property if and only if it is either a constant solution or a serial dictatorship.
Proof. It is easy to verify the “if” part. We prove the “only if” part below. Let f
be a solution satisfying the two axioms. We now discuss the following two cases:
12
12
21
12
21
12
%12
Case 1: f (%1 , % 2 ) = (1, 2). If f (%1 , %2 ) = (2, 1), then f2 (%1 , %2 ) Â2121221
f2 (%12
1 , %2 ), which is in violation of strategy-proofness. Therefore, f (%1 , %2 ) =(1, 2).
12
We ﬁrst consider the case f (%21
1 , %2 ) = (1, 2). By the rectangular property,21f (%21
1 , %2 ) = (1, 2). Hence, f is constant.
12
21
21
Next, we consider the case f (%21
1 , %2 ) = (2, 1). If f (%1 , %2 ) = (1, 2), then, by
12
the rectangular property, f (%21
1 , %2 ) = (1, 2). This is a contradiction. Therefore,21Nf (%21
1 , %2 ) = (2, 1). Then, f1 (%) = b(%1 , N ) for each % ∈ P . This implies thatf is a serial dictatorship.
12%12Case 2: f (%1 , % 2 ) = (2, 1). By an argument similar to that in Case 1, we
have that f is either a constant solution or a serial dictatorship.

The two axioms in Proposition 2 are independent. It is easily veriﬁable thatthe strict core solution satisﬁes strategy-proofness but violates the rectangular property. The following solution satisﬁes the rectangular property but violates strategyproofness: for each % ∈ P N ,{f (%) =

(2, 1)
C(%)

21
if % = (%12
1 , %2 );otherwise.

By Proposition 1, we immediately obtain the characterization of the class of
securely implementable solutions in the two-agent case.

7

Theorem 1. Assume n = 2. A solution f is securely implementable if and only if
it is either a constant solution or a serial dictatorship.
Considering other axioms, we obtain the following corollary:
Corollary 1. Assume n = 2.
1. An individually rational solution f is securely implementable if and only if itis the no-trade solution.
2. A neutral solution f is securely implementable if and only if it is a serial
dictatorship.
3. An eﬃcient solution f is securely implementable if and only if it is a serial
dictatorship.

4

The general case

In contrast to the two-agent case, in the general case where there are more than two
agents, there exists a securely implementable solution other than constant solutions
and serial dictatorships. To verify this, consider the following example:
Example 2. Let N = {1, 2, 3}. Let f be a solution satisfying the following: foreach % ∈ P N ,{f (%) =

(2, 1, 3)(2, 3, 1)

if 1 Â2 3;
if 3 Â2 1.

It is easy to see that the solution is securely implementable.

¥

It would be expected that there are a lot of securely implementable solutions in
the general case. In fact, as we will see later, in the general case, there are several
diﬀerent types of securely implementable solutions. Thus, the main purpose of thissection is to characterize the class of securely implementable solutions satisfying acertain property.

4.1

Individual rationality and neutrality

This subsection ﬁrst considers the class of securely implementable solutions thatsatisfy individual rationality. The next proposition would be helpful in characterizing
the class.

8

Proposition 3. A solution f satisﬁes individual rationality and the rectangularproperty if and only if it is the no-trade solution.
Proof. Since the “if” part is obvious, it will suﬃce to show the “only if” part. Let f
be a solution satisfying the two axioms. Let %0 ∈ P N be such that for each i ∈ N ,b(%0i , N ) = i. By individual rationality, fi (%0 ) = i for each i ∈ N . Let % ∈ P N .
Then, individual rationality implies that fi (%i , %0−i ) = i for each i ∈ N . Hence,by the rectangular property, f (%0 ) = f (%). This implies that f is the no-trade
solution.
It is easy to check that none of the axioms in Proposition 3 are redundant. The
strict core solution satisﬁes individual rationality but violates the rectangular property. A constant solution that is not the no-trade solution satisﬁes the rectangularproperty but violates individual rationality.
Interestingly, Proposition 3 enables us to pin down the class of securely implementable solutions satisfying individual rationality without using strategy-proofness.
Thus, we immediately obtain the following result.
Theorem 2. An individually rational solution f is securely implementable if andonly if it is the no-trade solution.
Next, we consider the class of securely implementable solutions that satisfy neutrality. Svensson (1999) establishes that a solution is strategy-proof, non-bossy, andneutral if and only if it is a serial dictatorship.8 From the logical relationship between
the rectangular property and non-bossiness, we obtain the following result:
Theorem 3. A neutral solution is securely implementable if and only if it is a serial
dictatorship.

4.2

Eﬃciency

In this subsection, we characterize the class of securely implementable solutions thatsatisfy eﬃciency. We ﬁrst provide a characterization of the class of solutions thatsatisfy strategy-proofness, the rectangular property, and eﬃciency.
Proposition 4. A solution f satisﬁes strategy-proofness, the rectangular property,
and eﬃciency if and only if it is a sequential dictatorship.
8

Svensson (1999) considers a situation where the total number of objects is at least as great as
the number of agents. Therefore, Theorem 3 holds in this situation.

9

Proof. The “if ” part. Let f be a sequential dictatorship. Since it is obvious thatf satisﬁes eﬃciency, we show that f satisﬁes strategy-proofness and the rectangularproperty.
• Strategy-proofness: Let % ∈ P N , j ∈ N , and %0j ∈ P be such that π%(k) = j.
First, let k = 1. Then, obviously, j cannot manipulate at %. Next, let
k = 2. Since the ﬁrst dictator π%(1) (= π(%0j ,%−j ) (1)) reveals the same preference %π% (1) at both % and (%0j , %−j ), it holds that fπ% (1) (%) = fπ% (1) (%0j , %−j ).
(\{})
fπ% (1) (%)
Therefore, π%(2) = π(%0j ,%−j ) (2) = j. Since fj (%) = b %j , N
(
\{
})
(
\{
})
and fj (%0j , %−j ) = b %0j , N
fπ% (1) (%0j , %−j )= b %0j , N
fπ% (1) (%) ,agent j cannot manipulate at %. Repeating a similar argument for eachk ∈ {3, 4, . . . , n}, we can establish that f is strategy-proof.
• Rectangular property: Let %, %0 ∈ P N be such that for all i ∈ N , fi (%0 ) =fi (%i , %0−i ). Without loss of generality, we assume that π%0 (i) = i for each i ∈N . First, let us consider agent 1. Note that π%0 (1) = π(%1 ,%0−1 ) (1) = π%(1) = 1.
Then, f1 (%0 ) = f1 (%1 , %0−1 ) implies b(%01 , N ) = b(%1 , N ). Therefore,
f1 (%0 ) = b(%01 , N ) = b(%1 , N ) = f1 (%).

(1)

Next, let us consider agent 2, who is the second dictator at %0 . Since agent
1 reveals the same preference relation %01 at both %0 and (%2 , %0−2 ), f1 (%0 ) =f1 (%2 , %0−2 ). Thus, π%0 (2) = π(%2 ,%0−2 ) (2) = 2. Then, f1 (%0 ) = f1 (%2 , %0−2 )and f2 (%0 ) = f2 (%2 , %0−2 ) together imply thatb (%02 , N \ {f1 (%0 )}) = b (%2 , N \ {f1 (%0 )}) .

(2)

Furthermore, by (1), π%0 (2) = π%(2) = 2. Therefore, (1) and (2) together
imply thatf2 (%0 ) = b (%02 , N \ {f1 (%0 )}) = b (%2 , N \ {f1 (%)}) = f2 (%).
Iterating a similar augment for the other agents in N yields f (%0 ) = f (%).
The “only if” part. Let f be a solution satisfying the three axioms. We begin byproving that there exists the ﬁrst dictator. For each i ∈ N , let %̂i be such that
%̂i : n, n − 1, . . . , k + 1, k, k − 1, . . . , 2, 1.

10Let %̂ ≡ (%̂1 , %̂2 , . . . , %̂n ). Without loss of generality, assume that for each i ∈ N ,fi (%̂) = i. For each k ∈ N , let Nk ≡ {1, 2, . . . , k}. We establish the following claim:
Claim 1. For each k ∈ N and each %Nk ∈ P Nk ,fi (%Nk , %̂−Nk ) = i∀ i ∈ N \ Nk ;fk (%Nk , %̂−Nk ) = b(%k , Nk ).
The proof for Claim 1 can be found in Appendix A. When k = n, Claim 1 implies
that for each % ∈ P N , fn (%) = b(%n , N ). Therefore, agent n is the ﬁrst dictator.
Now, we show that f is a sequential dictatorship. Since agent n is the ﬁrst
dictator, we can set π%(1) = n and fn (%) = b(%n , N ) for each % ∈ P N . We will
now establish the following claim:
Claim 2. For each % ∈ P N and each %0−n ∈ P N \{n} , if for each i ∈ N \ {n},c %i d ⇐⇒ c %0i d ∀ c, d ∈ N \ {b(%n , N )},(3)then f (%) = f (%n , %0−n ).
The proof for Claim 2 can be found in Appendix A. Pick any % ∈ P N . Leta ≡ b(%n , N ). Let P|N \{a} denote the set of all strict preferences %i |N \{a} over()N \{n}N \ {a}. Then, let f a : P|N \{a}→ N \ {a} be a solution such that for eachai ∈ N \ {n}, fi (%|N \{a} ) = fi (%) where for each i ∈ N , b(%i , N ) = a and for eachi ∈ N \ {n},c %i |N \{a} d ⇐⇒ c %i d ∀ c, d ∈ N \ {a}.
Since f satisﬁes strategy-proofness, the rectangular property, and eﬃciency, f a alsosatisﬁes the three axioms. Therefore, by adopting an argument similar to that forproving that there is the ﬁrst dictator of f , we can prove that there is a dictator off a . Let j(a) be the dictator of f a . Then,a(%|N \{a} ) = b(%j(a) |N \{a} , N \ {a}) = b(%j(a) , N \ {a}),fj(a) (%) = fj(a) (%n , %0−n ) = fj(a)where for each i ∈ N \ {n}, %0i is a preference relation such that b(%0i , N ) = a and(3) holds; the ﬁrst equation follows from Claim 2. Hence, we observe that for each% ∈ P N , if b(%n , N ) = a, then π%(2) = j(a) and fj(a) (%) = b(%j(a) , N \ {a}).

11By repeating a similar argument, we can establish that f is a sequential dictatorship.
Remark. We can see that the proof of Proposition 4, particularly Claim 1, does
not work in a situation where the null object, which means “not receiving any real
object,” may be preferred to a real object. Therefore, we cannot apply Proposition 4 to such a situation. On the other hand, the proof can be extended, in astraightforward way, to a situation where every real object is preferred to the null
object.
It is easy to verify that the “only if” part of Proposition 4 does not hold when anyof the three axioms—eﬃciency, strategy-proofness, and the rectangular property—
is dropped. The strict core solution satisﬁes eﬃciency and strategy-proofness but
violates the rectangular property. The no-trade solution satisﬁes strategy-proofness,and the rectangular property but violates eﬃciency. Finally, the following solution
satisﬁes eﬃciency and the rectangular property but violates strategy-proofness: letf be a sequential choice solution such that for each % ∈ P {1,2,3} ,{(π%(1), π%(2), π%(3)) =(1, 2, 3)(2, 3, 1)

if b(%i , N ) = b(%j , N ) ∀ i, j ∈ N ;otherwise.

The following result is a characterization of securely implementable solutions
satisfying eﬃciency and follows easily from Proposition 4.
Theorem 4. An eﬃcient solution f is securely implementable if and only if it is asequential dictatorship.
It is well-known that strategy-proofness together with non-bossiness implies eﬃciency as long as no alternative is excluded in advance (Takamiya, 2001); this is anaxiom called ontoness. This axiom can be expressed as follows:
Ontoness: For each x ∈ X, there exists % ∈ P N such that f (%) = x.
Since ontoness is a necessary condition for eﬃciency, ontoness deems a minimal
eﬃciency condition. Then, we have the following corollary:
Corollary 2. An onto solution f is securely implementable if and only if it is asequential dictatorship.

12

5

Discussions

5.1

Other securely implementable solutions

Thus far, we have considered securely implementable solutions satisfying certain
properties in the general case. Now, we present other securely implementable solutions in the general case.
Example 2 (continued). It can easily be veriﬁed that f is securely implementable
but satisﬁes none of the other axioms.
¥
Example 3. Let N = {1, 2, 3, 4}. Let f be a solution satisfying the following: foreach % ∈ P N ,f1 (%) = b(%1 , {1, 2, 3});f2 (%) = b(%2 , N \ {f1 (%)});
f3 (%) = b(%3 , N \ {f1 (%), f2 (%)});
f4 (%) = N \{f1 (%), f2 (%), f3 (%)}.
This solution is securely implementable but satisﬁes none of the other axioms.

¥

It follows from Examples 2 and 3 that the class of securely implementable solutions is expected to be of complicated form. Thus, the characterization of the classof securely implementable solutions remains for future research.

5.2

Reallocation-proofness and anonymityPápai (2000) studies solutions that are robust to pairwise manipulations throughreallocations of assignments. Such a robustness is formalized by a requirement thatrules out the possibility that any two agents can gain by swapping objects after
reporting dishonestly. This can be expressed as follows:
Reallocation-proofness: There does not exist % ∈ P N , i, j ∈ N , and %0{i,j} ∈P {i,j} such that (i) fj (%0{i,j} , %−{i,j} ) %i fi (%), (ii) fi (%0{i,j} , %−{i,j} ) Âj fj (%),
and (iii) fh (%) = fh (%0h , %−h ) 6= fh (%0{i,j} , %−{i,j} ) for h = i, j.
Pápai (2000) discusses reallocation-proofness as well as strategy-proofness, eﬃciency, and non-bossiness. She establishes that a solution satisﬁes the four axioms

13

if and only if it is a hierarchical exchange solution.9 It immediately follows from thedeﬁnitions that the rectangular property implies reallocation-proofness. Therefore,
Theorem 4 implies that any hierarchical exchange solution other than sequential
dictatorships is not securely implementable.
The next axiom, which is ﬁrst introduced by Miyagawa (2002), is related tofairness. It states that a solution does not depend on the names of agents andobjects. Given that % ∈ P N and π ∈ ΠN , let T̂ (%, π) be the preference proﬁle %0
deﬁned by the condition that for each i, j, k ∈ N ,j %i k ⇐⇒ π(j) %0π(i) π(k).
Anonymity: For each % ∈ P N , each π ∈ ΠN , and each i ∈ N , fπ(i) (T̂ (%, π)) =π(fi (%)).
In the two-agent case, we obtain the following result from Theorem 2:
Theorem 5. Assume n = 2. An anonymous solution f is securely implementable
if and only if it is constant.
In the general case, characterizing the class of anonymous and securely implementable solutions is still an open question. We point out that the class in the casen ≥ 4 may be substantially diﬀerent from that in the case n = 3. To verify this, wedeﬁne the modiﬁed strict core solution C m , which is proposed by Miyagawa (2002):
for each % ∈ P N , C m (%) = C(%∗ ), where %∗ is a preference proﬁle such that foreach i ∈ N , %∗i is identical to %i except for the agent’s initial endowment; further,
the endowment ranking is worst at %∗i . It can easily be veriﬁed that the modiﬁed
strict core solution satisﬁes the rectangular property in the case n = 3 although thesolution violates it in the case n ≥ 4. This hints toward a diﬀerence between thecharacterization results.

5.3

Coalitional stability

As shown in Section 2, the strict core solution is not securely implementable. One
way to avoid this result is to consider an equilibrium concept related to coalitional
stability instead of Nash equilibrium. This approach is adopted from Bochet andSakai (2007), who study secure implementation in allotment economies. In ourmodel, Takamiya (2009) shows that the strict core solution is implemented by its
9

See Pápai (2000) for the formal deﬁnition of a hierarchical exchange solution.

14

associated direct revelation mechanism in strict strong Nash equilibria. Thus, it isdoubly implemented through dominant strategy and strict strong Nash equilibria.10
However, the characterization of the class of solutions that can be doubly implemented through dominant strategy equilibrium and an equilibrium notion related
to coalitional stability remains for future research.

6

Conclusion

We succeeded in classifying the class of securely implementable solutions satisfying a certain property such as individual rationality, neutrality, and eﬃciency inShapley-Scarf housing markets. This paper discussed a deterministic object allocation model and proved that a serial dictatorship is securely implementable but thestrict core solution is not. On the other hand, in a random allocation model, twosolutions related to a serial dictatorship and the strict core solution are equivalent:
Abdulkadiroǧlu and Sönmez (1998) establish the equivalence between the random
serial dictatorship and the core solution from random endowment.11 The examination of whether or not the solution is securely implementable and the identiﬁcation of
the securely implementable solutions in the random allocation model are interesting
issues left for future research.

A

Appendix: Proofs of claims

Before proving claims, we deﬁne monotonicity (Maskin, 1999) and provide a usefulfact. We denote by L(h, %i ) ≡ {k ∈ N : h %i k} agent i’s lower contour set of objecth ∈ N at %i ∈ P.
Monotonicity: For each %, %0 ∈ P N , if L(fi (%), %i ) ⊆ L(fi (%), %0i ) for eachi ∈ N , then f (%) = f (%0 ).
Fact 2. If f satisﬁes both strategy-proofness and the rectangular property, then it
satisﬁes monotonicity.
Proof. It follows from Fact 1 and Theorem 4.12 in Takamiya (2001).
10

Wako (1999) establishes that the strict core solution is strong Nash implementable by constructing a “natural” mechanism. However, the mechanism does not implement the solution via
dominant strategy equilibria.
11
See Abdulkadiroǧlu and Sönmez (1998) for the formal deﬁnitions of the two solutions.

15

A.1

Proof of Claim 1

We now prove this claim by using an induction argument.
• Basic step: When k = 1, the claim holds: Pick any %1 ∈ P. Note thatf1 (%̂) = 1. Since L(1, %̂1 ) = {1}, L(1, %̂1 ) ⊆ L(1, %1 ). Thus, by monotonicity (Fact 2), f (%1 , %̂−1 ) = f (%̂). Therefore,fi (%N1 , %̂−N1 ) = i ∀ i ∈ N \ N1 ;f1 (%N1 , %̂−N1 ) = 1 = b(%1 , N1 ).
• Induction hypothesis: When k = ` − 1, it holds that for each %N`−1 ∈ P N`−1 ,fi (%N`−1 , %̂−N`−1 ) = i ∀ i ∈ N \ N`−1 ;f`−1 (%N`−1 , %̂−N`−1 ) = b(%`−1 , N`−1 ).

(4)
(5)

• Induction step: Let k = `. We will now prove the three steps.
%N` , %̂%−N` ) = b(%%`, N`).
Step 1: For each % N` ∈ P N` , f`(%
Let %N` ∈ P N` . Furthermore, let x ≡ f (%N` , %̂−N` ), y ≡ f (%N`−1 , %̂−N`−1 ),b ≡ b(%` , N` ), and s ≡ b(%` , N` \ {b}). Note that by the induction hypothesis,y` = `. Moreover, since y` = ` %̂` x` by strategy-proofness, then x` ∈ N` . There arethree cases:
Case 1-1: b = `. Since y` = ` and N` = L(`, %̂` ) ⊆ L(`, %` ), by monotonicity (Fact 2), f` (%N` , %̂−N` ) = ` = b.
Case 1-2: s = `. By strategy-proofness, x` %` ` = y` . This and x` ∈ N`
together imply that either x` = b or x` = `. Suppose that x` = `. By the induction
hypothesis, (4) implies that∪{yi } = N`−1 .

(6)i∈N`−1Since b 6= s = `, then b ∈ N`−1 . Therefore, by (6), there exists j ∈ N`−1 such thatyj = b.
Deﬁne %̄N`−1 as follows:

16

(7)

P1. %̄j : `, b, . . . ;P2. For each i ∈ N`−1 \ {j}, %̄i : yi , . . .
Since y` = ` = x` ,y` = x` = f` (%N` , %̂−N` ).

(8)

For each i ∈ N`−1 \ {j}, L(yi , %i ) ⊂ N = L(yi , %̄i ). Thus, by monotonicity (Fact 2),
y = f (%N`−1 \{i} , %̄i , %̂−N`−1 ).

(9)

By the induction hypothesis, f` (%N`−1 \{j} , %̄j , %̂−N`−1 ) = `, which implies
fj (%N`−1 \{j} , %̄j , %̂−N`−1 ) 6= `.
Then, by (7) and strategy-proofness,
yj = b = fj (%N`−1 \{j} , %̄j , %̂−N`−1 ).

(10)Then (8), (9), and (10) together imply that by the rectangular property,f (%̄N`−1 , %` , %̂−N` ) = y.

(11)

Thus,
b Â` ` = f` (%̄N`−1 , %` , %̂−N` );` Â̄j b = fj (%̄N`−1 , %` , %̂−N` ),which is a contradiction to eﬃciency. Hence, x` = b.
Case 1-3: b 6= ` and s 6= `. Pick any %0` such that b(%0` , N ) = b andb(%0` , N \ {b}) = `. Then, by Case 1-2, f` (%N`−1 , %0` , %̂−N` ) = b. Since x` ∈ N` , bystrategy-proofness, x` = b.
%N` , %̂%−N` ) ∈ N`.
Step 2: For each % N` ∈ P N` and each i ∈ N`, fi(%
Pick any %N` ∈ P N` . Let x ≡ f (%N` , %̂−N` ) and b ≡ b(%` , N` ). By Step 1,x` = b. Let %0` be such that b0 ≡ b(%0` , N` ) = b and L(b0 , %0` ) = N` . Let %0N`−1 besuch that for each i ∈ N`−1 , b(%0i , N ) = b0 and the ordering other than b0 is the sameas that of %i . Let x0 ≡ f (%0N` , %̂−N` ). By Step 1, x0` = b0 .

17

We ﬁrst show that x0i ∈ N` for each i ∈ N` . Suppose, by contradiction, that
there exist j ∈ N`−1 such that x0j ∈/ N` . Then,x0j Â0` b0 ;b0 Â0j x0j ,which is a contradiction to eﬃciency. Thus, x0i ∈ N` for each i ∈ N` .
Next, we show that x = x0 . By Step 1, x0i 6= b0 for each i ∈ N`−1 . Therefore,
for each i ∈ N`−1 , by the deﬁnition of %0i , we have either L(x0i , %i ) = L(x0i , %0i )or L(x0i , %i ) = L(x0i , %0i ) ∪ {b0 }. This implies that L(x0i , %0i ) ⊆ L(x0i , %i ) for eachi ∈ N`−1 . By monotonicity (Fact 2), for each i ∈ N`−1 ,x0 = f (%0N` \{i} , %i , %̂−N` ).

(12)x0` = b0 = b = f` (%0N`−1 , %` , %̂−N` ).

(13)

Furthermore, by Step 1,

By (12) and (13), the rectangular property implies that x = x0 .
Hence, we obtain xi = x0i ∈ N` for each i ∈ N` .
%N` , %̂%−N` ) = i.
Step 3: For each % N` ∈ P N` and each i ∈ N \ N`, fi(%
Suppose, by contradiction, that there exist %N` ∈ P N` and i ∈ N \ N` such thatfi (%N` , %̂−N` ) 6= i.

(14)

We now construct the preference proﬁle %∗N` as follows:P∗1. %∗` : n, n − 1, . . . , ` + 2, ` + 1, b(%` , N` ), . . . ;P∗2. For each j ∈ N`−1 , b(%∗j , N ) = fj (%N` , %̂−N` ).
By Step 1,f` (%N`−1 , %∗` , %̂−N` ) = b(%∗` , N` ) = b(%` , N` ) = f` (%N` , %̂−N` ).

(15)

For each j ∈ N`−1 , by strategy-proofness,fj (%N` \{j} , %∗j , %̂−N` ) = fj (%N` , %̂−N` ).

18

(16)

By (15) and (16), the rectangular property implies thatf (%∗N` , %̂−N` ) = f (%N` , %̂−N` ).

(17)Then, (14) and (17) together imply that fi (%∗N` , %̂−N` ) 6= i. Note that by Step 2,
we have}∪ {fk (%∗N` , %̂−N` ) = N \ N` .
k∈N \N`

Therefore, there exists j ∈ N \ N` such that j > fj (%∗N` , %̂−N` ). Now, let %∗∗j besuch that∗∗%∗∗j : n, n − 1, . . . , j + 1, j, b(%` , N` ), fj (%N` , %̂−N` ), . . .
∗∗Let x∗ ≡ f (%∗N` , %∗∗j , %̂−(N` ∪{j}) ) and y ≡ f (%N` , %̂−N` ). By strategy-proofness,∗∗∗∗x∗j %∗∗
j yj . If xj ≥ j, then xj Â̂j yj , which is a contradiction to strategy-proofness.
Therefore, we have either x∗j = b(%∗` , N` ) or x∗j = yj∗ .

Case 3-1: x∗j = yj∗. By non-bossiness (Fact 1), x∗ = y ∗ . Then, since yj∗ ∈ N \N`
and y`∗ = b(%∗` , N` ) by Step 1,∗∗b(%∗` , N` ) Â∗∗j yj = xj ;yj∗ Â∗` b(%∗` , N` ) = x∗` ,which is a contradiction to eﬃciency.
%∗` , N`). By eﬃciency, x∗` Â∗` b(%∗` , N` ); otherwise, weCase 3-2: x∗j = b(%deﬁne the allocation z as follows:
Z1. For each k ∈ N`−1 , zk = b(%∗k , N );Z2. zj = b(%∗` , N` );Z3. For each k ∈ {h ∈ N \ (N` ∪ {j}) : x∗h ∈ N \ N` }, zk = x∗k .
Z1, P∗ 2, and (17) together imply that zk = yk for each k ∈ N`−1 . Step 1 implies that∪zj = y` . Thus, by Step 2, k∈N`−1 ∪{j} {zk } = N` , which implies that zk ∈ N \ N` foreach k ∈ N \ (N`−1 ∪ {j}). Therefore, by Z1, Z2, and Z3,z` Â∗` b(%∗` , N` ) Â∗` x∗` ;19∗zj ∼∗∗
j xj ;

zk %̂k x∗k∀ k ∈ N \ (N` ∪ {j}) ;zh %∗h x∗h∀ h ∈ N`−1 .

Then the allocation z Pareto dominates x∗ , which is a contradiction to eﬃciency.
Thus, x∗` ∈ N \ N` . Then, L(x∗` , %∗` ) ⊆ L(x∗` , %̂` ). Therefore, by monotonicity (Fact 2),x∗ = f (%∗N`−1 , %∗∗j , %̂−(N`−1 ∪{j}) ).

(18)

By the induction hypothesis, j = fj (%∗N`−1 , %̂−N`−1 ). Then, L(j, %̂j ) ⊆ L(j, %∗∗j ).
Therefore, by monotonicity (Fact 2),∗
f (%∗N`−1 , %∗∗j , %̂−(N`−1 ∪{j}) ) = f (%N`−1 , %̂−N`−1 ).

(19)Then, (18) and (19) together imply that x∗ = f (%∗N`−1 , %̂−N`−1 ). This is a contradiction to x∗j = b(%∗` , N` ) 6= j = fj (%∗N`−1 , %̂−N` ).
¤A.2

Proof of Claim 2

Pick any % ∈ P N . Let %0−n ∈ P N \{n} be such that (3) holds. Let us consider%00−n ∈ P N \{n} such that for each i ∈ N \{n}, b(%00i , N ) = b(%n , N ) and the orderingother than b(%n , N ) is the same as that of both %i and %0i . Note that since agent
n is the ﬁrst dictator, fn (%n , %00−n ) = b(%n , N ). Therefore, fi (%n , %00−n ) 6= b(%n , N )for each i ∈ N \ {n}. These imply that for each i ∈ N \ {n},L(fi (%n , %00−n ), %00i ) ⊆ L(fi (%n , %00−n ), %i );L(fi (%n , %00−n ), %00i ) ⊆ L(fi (%n , %00−n ), %0i ).
By monotonicity (Fact 2), f (%n , %−n ) = f (%n , %00−n ) = f (%n , %0−n ).

20

¤

B

Appendix: Implementability of the strict coresolution

B.1

Dominant strategy implementation

To the best of our knowledge, no one has previously attempted to explicitly identify whether the strict core solution is dominant strategy implementable. Thus,
below, we show that the strict core solution is dominant strategy implementable byexploiting the result of Mizukami and Wakayama (2007). They show that if a solution satisﬁes strategy-proofness and quasi-strong-non-bossiness, then it is dominant
strategy implemented by its associated direct revelation mechanism (see Theorem 2
in Mizukami and Wakayama, 2007).
Quasi-strong-non-bossiness: For each % ∈ P N , each i ∈ N , and each %0i ∈ P,
if fi (%i , %00−i ) ∼i fi (%0i , %00−i ) for each %00−i ∈ P N \{i} , then f (%) = f (%0i , %−i ).
Proposition 5. The strict core solution is dominant strategy implemented by its
associated direct revelation mechanism.
Proof. It suﬃces to show that the strict core solution C satisﬁes quasi-strong-nonbossiness. Let % ∈ P N , i ∈ N , and %0i ∈ P be such that Ci (%i , %00−i ) ∼i Ci (%0i , %00−i )for each %00−i ∈ P N \{i} . Since preferences are strict, Ci (%i , %00−i ) = Ci (%0i , %00−i ) for
each %00−i ∈ P N \{i} . Thus, Ci (%) = Ci (%0i , %−i ). Since C satisﬁes non-bossiness,
C(%) = C(%0i , %−i ).

B.2

Nash implementation in the case of two agents

Although the strict core solution is Nash implementable in the case where there areat least three agents, it is not Nash implementable in the two-agent case.
Proposition 6. Assume n = 2. The strict core solution is not implementable in
Nash equilibria.
Proof. Suppose, by contradiction, that the strict core solution is Nash implementable.
Then, there is a mechanism Γ = (M, g) implementing the strict core solution C in
Nash equilibria. Here, M ≡ M1 × M2 is a message space and g : M → X is an outcome function. Given that i ∈ N and m ∈ M , let gi (m) denote agent i’s consumption
associated with a message proﬁle m. For each % ∈ P N , let NE(%, Γ) ⊆ M be theset of all Nash equilibria of the mechanism Γ at % ∈ P N and g(NE(%, Γ)) be the21set of the Nash equilibrium outcomes of Γ at %. Since the mechanism Γ = (M, g)
implements C,
121212g(NE((%12
1 , %2 ), Γ)) = (1, 2) = C(%1 , %2 );

(20)

21
12
21
g(NE((%12
1 , %2 ), Γ)) = (1, 2) = C(%1 , %2 );122112g(NE((%21
1 , %2 ), Γ)) = (2, 1) = C(%1 , %2 );212121g(NE((%21
1 , %2 ), Γ)) = (1, 2) = C(%1 , %2 ).

(21)

21
Now, let m21,21 ∈ NE((%211 , %2 ), Γ). Then, by (21),
21,21
21
21,21
0
) ∀ m01 ∈ M1 ,) %21
1 = g1 (NE((%211 g1 (m1 , m2
1 , %2 ), Γ)) = g1 (mwhich implies that
g1 (m01 , m21,21) = 1 ∀ m01 ∈ M1 .
2

(22)

12
Next, let m12,12 ∈ NE((%121 , %2 ), Γ). Then, by (20),
12,12
12
12,12
2 = g2 (NE((%12) %12, m02 ) ∀ m02 ∈ M2 ,1 , %2 ), Γ)) = g2 (m2 g2 (m1which implies thatg2 (m12,12, m02 ) = 2 ∀ m02 ∈ M2 .
1

(23)Then, (22) and (23) together imply that21,21
0
1 = g1 (m12,12, m21,21) %21) ∀ m01 ∈ M1 ;1
2
1 g1 (m1 , m2
12,12
2 = g2 (m12,12, m21,21) %12, m02 ) ∀ m02 ∈ M2 .
1
2
2 g2 (m112,1212This implies that (m12,12, m21,21, m21,21) ∈ NE((%21)=
1221 , %2 ), Γ). However, g(m112
21
(1, 2) 6= (2, 1) = g(NE((%1 , %2 ), Γ)), which is a contradiction.

22

References
Abdulkadiroǧlu, A. and T. Sönmez (1998) “Random serial dictatorship and the corefrom random endowments in house allocation problems,” Econometrica, 66,
689–701.
Abdulkadiroǧlu, A. and T. Sönmez (1999) “House allocation with existing tenants,”
Journal of Economic Theory, 88, 233–260.
Bird, C.G. (1984) “Group incentive compatibility in a market with indivisible goods,”
Economics Letters, 14, 309–313.
Bochet, O. and T. Sakai (2006) “Secure implementation in allotment economies,”
mimeo.
Chen, Y. and T. Sönmez (2002) “Improving eﬃciency of on-campus housing: anexperimental study,” American Economic Review, 92, 1669–1686.
Chen, Y. and T. Sönmez (2004) “An experimental study of house allocation mechanisms,” Economics Letters, 83, 137–140.
Ehlers, L. (2002) “Coalitional strategy-proof house allocation,” Journal of Economic
Theory, 105, 298–317.
Ehlers, L. and B. Klaus (2003a) “Resource-monotonicity for house allocation problems,” International Journal of Game Theory, 32, 545–560.
Ehlers, L. and B. Klaus (2003b) “Coalitional strategy-proofness, resource-monotonicity,and separability for multiple assignment problems,” Social Choice and Welfare, 21, 265–280.
Ehlers, L., B. Klaus, and S. Pápai (2002) “Strategy-proofness and population-monotonicity
for house allocation problems,” Journal of Mathematical Economics, 38, 329–
339.
Ergin, H. (2000) “Consistency in house allocation problems,” Journal of Mathematical
Economics, 34, 77–97.
Fujinaka, Y. and T. Wakayama (2008) “Secure implementation in economies withindivisible objects and money,” Economics Letters, 100, 91–95.

23

Klaus, B. and E. Miyagawa (2001) “Strategy-proofness, solidarity, and consistency
for multiple assignment problems,” International Journal of Game Theory,30, 421–435.
Ma, J. (1994) “Strategy-proofness and the strict core in a market with indivisibilities,”
International Journal of Game Theory, 23, 75–83.
Maskin, E. (1999) “Nash equilibrium and welfare optimality,” Review of Economic
Studies, 66, 23–38.
Miyagawa, E. (2001) “House allocation with transfers,” Journal of Economic Theory,
100, 329–355.
Miyagawa, E. (2002) “Strategy-proofness and the core in house allocation problems,”
Games and Economic Behavior, 38, 347–361.
Mizukami, H. and T. Wakayama (2007) “Dominant strategy implementation in economic environments,” Games and Economic Behavior, 60, 307–325.
Mizukami, H. and T. Wakayama (2008) “Secure implementation: an alternative characterization,” mimeo.
Pápai, S. (2000) “Strategyproof assignment by hierarchical exchange,” Econometrica,
68, 1403–1433.
Pápai, S. (2001) “Strategyproof and nonbossy multiple assignments,” Journal of Public Economic Theory, 3, 257–271.
Roth, A.E. (1982) “Incentive compatibility in a market with indivisible goods,” Economics Letters, 9, 127–132.
Roth, A.E. and A. Postlewaite (1977) “Weak versus strong domination in a market
with indivisible goods,” Journal of Mathematical Economies, 4, 131–137.
Roth, A.E., T. Sönmez, and U. Ünver (2004) “Kidney exchange,” Quarterly Journalof Economics, 119, 457–488.
Saijo, T., T. Sjöström, and T. Yamato (2004) “Secure implementation,” COE Discussion Paper Series No. 8, Osaka University.
Saijo, T., T. Sjöström, and T. Yamato (2007) “Secure implementation,” Theoretical
Economics, 2, 203–229.

24

Shapley, L. and H. Scarf (1974) “On cores and indivisibility,” Journal of Mathematical
Economics, 1, 23–37.
Sönmez, T. (1996) “Implementation in generalized matching problems,” Journal of
Mathematical Economics, 26, 429–439.
Sönmez, T. and U. Ünver (2005) “House allocation with existing tenants: an equivalence,” Games and Economic Behavior, 52, 153–185.
Svensson, L.-G. (1999) “Strategy-proof allocation of indivisible goods,” Social Choiceand Welfare, 16, 557–567.
Takamiya, K. (2001) “Coalitional strategy-proof and monotonicity in Shapley-Scarf
housing markets,” Mathematical Social Sciences, 41, 201–213.
Takamiya, K. (2009) “Preference revelation games and strong cores of allocation
problems with indivisibilities,” Journal of Mathematical Economics, 45, 199–
204.
Wako, J. (1999) “Coalition-proofness of the competitive allocations in an indivisible
goods market,” Fields Institute Communications, 23, 277–283.

25