Coalition Strategy-Proofness and Monotonicity in
Shapley–Scarf Housing Markets∗
Koji Takamiya†
Economics Department, Hokkaido University
29 May, 2000

Abstract
This paper studies (single-valued) solutions to housing markets (Shapley and Scarf,
1974) with strict preferences. I show that a solution is monotonic if and only if it iscoalition strategy-proof. I point out that the strong core solution is the only solution
which is monotonic, individually rational and an onto function. (As Roth and Postlewaite (1977) showed, the strong core solution is single-valued when the preferences
are strict.) This result follows from the above equivalence theorem and a preceding characterization of the strong core solution by Ma (1994). My characterization
sharpens Sönmez’s (1996) similar result by weakening Pareto optimality to ontoness.
I also provide some related results. A solution is strategy-proof and nonbossy if andonly if it is monotonic. Thus the strong core solution is the unique solution which isstrategy-proof, nonbossy, individually rational, and onto.
JEL Classification— C71, C78, D71, D78.
Keywords— Shapley-Scarf housing market, coalition strategy-proofness, monotonicity, equivalence theorem.

0Introduction

This paper examines single-valued solutions to housing markets by an axiomatic method.
A housing market consists of finitely many agents each of whom is endowed with one unitof perfectly indivisible good (say a house). Each agent has a preference over the goods. A
single-valued solution is a function which specifies one allocation of the indivisible goods
for each preference profile. Since in this paper I consider only single-valued solutions, I
refer to them simply as solutions.
Housing markets were introduced by Shapley and Scarf (1974). They examined thecore, the strong core and competitive equilibria of housing markets. They proved thenonemptiness of the core and the existence of competitive equilibria for any preference
profiles, and that the strong core may be empty if weak preferences are admissible (i.e.
∗An earlier version of this paper was presented at 1999 Autumn Meeting of the Japanese Economic
Association in Tokyo. At the starting point of this research, I benefited much from the lecture given by
Prof Yves Sprumont at Workshop on Mathematical Methods and Models for Social Choice and Distributive Justice at University of British Columbia in July 1998. I am grateful to Profs Ryo-ichi Nagahisa,
Shinji Ohseto, Tomoichi Shinotsuka and Shigehiro Serizawa for valuable comments. I am also indebted
to the Editor in charge and the referee of this journal for useful comments. And I thank Profs Yukihiko
Funaki, Eiichi Miyagawa, Hiroshi Ono, Tatsuyoshi Saijo, Manimay Sengupta, Manabu Toda, Takehiko
Yamato, Naoki Yoshihara and the participants of the above Meeting, seminars in Hokkaido University,
Kansai University, ISER (Osaka University) and Otaru University of Commerce. All errors are my own
responsibility.
†
Economics Department, Hokkaido University, Kita9 Nishi7 Sapporo 060-0809 Japan1

an agent can be indifferent between two goods.) However, Roth and Postlewaite (1977)
showed that if every agent has a strict preference, then the strong core is always a singleton,and coincides with the unique competitive equilibrium. In this paper, I basically postulate
strict preferences. Specifically, I investigate the strong core solution (or the strong core,
simply) as a relevant solution.
The strong core satisfies various ‘desirable’ properties. Among others, here I am particularly interested in monotonicity and strategy-proofness properties. Strategy-proofness
properties are incentive compatibility requirements. A solution is strategy-proof if the solution is immune to individual manipulations, i.e. no single agent can be better off bymisrepresenting his preference. Also I consider situations where a solution is even robust to manipulations by groups. In this case, according to the strength of the definitionof coalitional manipulation, two nonmanipulability concepts are defined: weak coalition
strategy-proofness, and coalition strategy-proofness. Roth (1982) proved that the strong
core is strategy-proof. Furthermore, by Bird (1984), the strong core is even coalition
strategy-proof (thus also weakly coalition strategy-proof). Ma (1994) proved that thestrong core is the unique solution which is strategy-proof, individually rational and Pareto
optimal.
In this paper, a solution being monotonic means that the chosen allocation does notvary by a ‘monotonic’ change of the preference profile. It is well known that similar
monotonicity properties play significant roles in implementation theory (see e.g. Maskin,1985). The strong core is monotonic in this sense. Sönmez (1996) showed that the strong
core is the only solution which is monotonic, individually rational and Pareto optimal.1
I question how these strategy-proofness properties and monotonicity are related toeach other. My motivation is famous results from studies on voting rules2 : The Gibbard–
Satterthwaite theorem asserts that if a voting rule (with at least three alternatives) isan onto function, then the rule is strategy-proof if and only if it is dictatorial (Gibbard,
1973; Satterthwaite, 1975). Muller and Satterthwaite (1977) proved that for voting rules,
monotonicity is equivalent to strategy-proofness. This says that an onto voting rule with atleast three alternatives is dictatorial if and only if it is monotonic. These results motivate
to ask whether there are analogous relations between monotonicity and strategy-proofness
in housing markets.
Answering to this question, I prove that monotonicity is equivalent to coalition strategyproofness. And combining the above result with a preceding characterization of the strong
core by Ma (1994), I show that the strong core is the unique solution which is monotonic,
individually rational and an onto function. This characterization sharpens Sönmez’s (1996)
result mentioned above by weakening Pareto optimality to ontoness.
I also provide some additional results in connection with the well-known axiom ‘nonbossiness’. I point out that a solution is strategy-proof and nonbossy if and only if it ismonotonic. This result implies another new characterization: the strong core is the only
solution that is strategy-proof, nonbossy, individually rational and onto.
Throughout the paper, though basically assuming strict preferences, I examine how
the results change when weak preferences are admissible.
The plan of this paper is as follows: The next section provides definitions. Section
2 states the main results. Section 3 discusses the additional results. Section 4 proves
independences of the axioms used in the characterizations of the strong core. Finally,1Sönmez (1996) showed this result as a corollary to his theorem that deals with the Nash implementation
problem in a more general environment than housing markets.
2
In this paper, a voting rule means a function (called ‘social choice function’) specifying one alternative(candidate) for each preference profile of a finite number of individuals (voters). For each individual,
precisely all the strict preferences are admissible (the unrestricted domain assumption). I followed Moulin(1988) on this terminology.

2Section 5 concludes the paper.

1

Model

A housing market is a triple (N, H, R). Here N = {1, . . . , n} with n ≥ 2 is the set of
agents. Each agent i owns an indivisible good wi . Then H := {wi }i∈N is the set of goods.
R = (Ri )i∈N is a profile of preference relations on H. Any Ri is assumed to be complete(i.e. h, k ∈ H ⇒ (hRi k or kRi h)) and transitive (i.e. (h, k, m ∈ H & hRi k & kRi m) ⇒hRi m). For two indivisible goods h, k ∈ H, hRi k reads that to agent i h is at least as good
as k. P i and I i denote the asymmetric part and the symmetric part of Ri , respectively.
Thus hP i k means agent i prefers h to k, whereas hI i k denotes the indifference between hand k. Call Ri strict if Ri is anti-symmetric (i.e. (h, k ∈ H & hI i k) ⇒ h = k). And Ri
is weak if Ri is either strict or not. In what follows, I assume preference relations are allstrict unless
Q noted. Denote the set of strict preferences on H by P. For S ⊂ N , denote
P S := i∈S P i with P i = P. 3 An allocation is a bijection x : N → H. Here, x(i)is the good allocated to agent i. Denote the set of allocations by A . Let the sets N
and H be given. A single-valued solution is a function ϕ : P N → A . Thus for i ∈ N
and R ∈ P N , ϕ(R)(i) denotes the good allocated to agent i. In the following, I call asingle-valued solution simply a solution.
Let a housing market (N, H, R) be given. Let x, y ∈ A and S ⊂ N with S 6= ∅.
Then say that x weakly dominates y via S if {wi ∈ H | i ∈ S} = {x(i) ∈ H | i ∈ S}
& (∀i ∈ S : x(i)Ri y(i) & ∃j ∈ S : x(j)P j y(j)). An allocation x is in the strong core if
there does not exist any other allocation which weakly dominates x.4 It is known that thestrong core is a singleton for each R ∈ P N , and coincides with the (unique) competitive
allocation5 (Roth and Postlewaite, 1977). I refer to the solution which specifies the strong
core allocation for each R ∈ P N as the strong core solution (strong core, for short).
I examine the following properties (axioms) of a solution ϕ. First, I introduce three
versions of strategy-proofness.
Strategy-Proofness (SP): ∀i ∈ N : ∀R ∈ P N : ∀R0i ∈ P : ϕ(R)(i)Ri ϕ(R−i , R0i )(i).
This axiom (SP) says that no single agent can be strictly better off by misrepresenting his
preference.
Weak Coalition Strategy-Proofness (wCSP): ∀S ⊂ N, S 6= ∅ : ∀R ∈ P N : ∀R0S ∈P S : (∀i ∈ S : ϕ(R−S , R0S )(i)Ri ϕ(R)(i)) ⇒ (∃j ∈ S : ϕ(R−S , R0S )(j)I j ϕ(R)(j)).
This axiom (wCSP) implies (SP). This says that no group of agents can collusively misrepresenting their preferences in a way that each member of the group will be strictly
better off.
Coalition Strategy-Proofness (CSP): ∀S ⊂ N, S 6= ∅ : ∀R ∈ P N : ∀R0S ∈ P S :(∀i ∈ S : ϕ(R−S , R0S )(i)Ri ϕ(R)(i)) ⇒ (∀i ∈ S : ϕ(R−S , R0S )(i)I i ϕ(R)(i)).
3Inclusion ‘⊂’ is weak.
Say that x dominates y via S if {wi ∈ H | i ∈ S} = {x(i) ∈ H | i ∈ S} & (∀i ∈ S : x(i)P i y(i)). Thisdefines the core in the same way (see Shapley and Scarf, 1974).
5
A competitive allocation is an allocation x which satisfies for some price vector (pi )i∈N (pi is the priceof the good wi ), ∀i, j ∈ N : x(i) = wj ⇒ pj ≤ pi (budget constraints), and wj P i x(i) ⇒ pi < pj (utility
maximization).
4

3

This axiom (CSP) implies (wCSP). (CSP) means that no group of agents can collusively
misreport their preferences in a way that some member of the group will be better off without any other member being worse off. The strong core satisfies all these three strategyproofness axioms ((SP), (wCSP) and (CSP)) (Roth, 1982; Bird, 1984). The following two
axioms are standard.
Individual Rationality (IR): ∀R ∈ P N : ∀i ∈ N : ϕ(R)(i)Ri wi .
Pareto Optimality (PO): ∀R ∈ P N : ∀x ∈ A : (∀i ∈ N : x(i)Ri ϕ(R)(i)) ⇒ (∀i ∈ N :x(i)I i ϕ(R)(i)).
It is immediate that the strong core satisfies the axioms (IR) and (PO). Also the strong
core satisfies the following axiom.
Ontoness (ONTO): ∀x ∈ A : ∃R ∈ P N : ϕ(R) = x.
The axiom (ONTO) says that ϕ is an onto function. That is , no allocation is excluded apriori. Note that the axiom (PO) implies (ONTO).
Next, I introduce monotonicity. Let Ri ∈ P and h ∈ H. Then denote by L(h, Ri ) theset {k ∈ H | hRi k}.
Monotonicity (MON): ∀R, R0 ∈ P N : (x = ϕ(R) & (∀i ∈ N : L(x(i), Ri ) ⊂ L(x(i), R0i ))) ⇒x = ϕ(R0 ).
Note that since N is a finite set, the axiom (MON) is equivalent to the following condition:∀R ∈ P N : ∀i ∈ N : R0i ∈ P : (x = ϕ(R) & L(x(i), Ri ) ⊂ L(x(i), R0i )) ⇒ x = ϕ(R−i , R0i ).
(MON) says that the if an allocation is chosen, then that allocation will still be chosen if
each agent changes his preference keeping or improving the relative ranking of the good
allocated to him. The strong core satisfies (MON). This follows from the equivalence
between (CSP) and (MON) (to be proved in Theorem 2.1) and the fact that the strong
core satisfies (CSP) (Bird, 1984). Essentially the same property can be defined also forvoting rules.6 (MON) is a version of ‘Maskin monotonicity’, which plays an importantrole in implementation theory (see e.g. Maskin, 1977; 1985).

2

Main Results

The following is the main result. Let ϕ denote a solution.
Theorem 2.1 ϕ satisfies (MON) if and only if ϕ satisfies (CSP).
Proof (If part) Let ϕ satisfy (CSP). Suppose that ϕ does not satisfy (MON). Then ∃i ∈N : ∃R ∈ P N : ∃R0i ∈ P : (x = ϕ(R) & L(x(i), Ri ) ⊂ L(x(i), R0i )) & x 6= ϕ(R−i , R0i ).
Let ϕ(R−i , R0i ) = y. And denote C := {j ∈ N | y(j) 6= x(j)}. Clearly, C is not empty.
Case 1: Assume i ∈ C. Then either y(i)P i x(i) or x(i)P i y(i) is true. Suppose thatthe former is true. Then I have ϕ(R−i , R0i )(i)P i ϕ(R)(i). That is, agent i gains frommisreporting his preference as R0i instead of Ri . Thus this contradicts (CSP). And supposethat the latter is true. Then x(i)P 0i y(i). Thus I have ϕ(R)(i)P 0i ϕ(R−i , R0i )(i). That is,agent i gains from misreporting his preference as Ri instead of R0i . Again, a contradiction
to (CSP).
6

Muller and Satterthwaite (1977) called that property ‘strong positive association’.

4Case 2: Assume i 6∈ C. Then ϕ(R−i , R0i )(i) = ϕ(R)(i). Define D := {j ∈ C |y(j)P j x(j)} and E := {j ∈ C | x(j)P j y(j)}. Note that C = D ∪ E and D ∩ E = ∅.
(i) Assume D 6= ∅. Let S = D ∪ {i}. Let R?S = (RS−{i} , R0i ) ∈ P S . Then I have∀j ∈ S − {i} : ϕ(R−S , R?S )(j)P j ϕ(R)(j), and ϕ(R−S , R?S )(i) = ϕ(R)(i).
This says that all the members of S but agent i improve without agent i’s loss by a collusive
misrepresentation of their preferences as R?S instead of RS . That is, a contradiction to(CSP).
(ii) Assume D = ∅. Then E 6= ∅ since C 6= ∅. Let T = E ∪ {i}. Let R??T =T(R −{i} , R0i ) ∈ P T . Note that ∀j ∈ T − {i} : R??j = Rj . Then I have∀j ∈ T − {i} : ϕ(R−T , RT )(j)P ??j ϕ(R−T , R??T )(j) & ϕ(R−T , RT )(i) = ϕ(R−T , R??T )(i).
This says that all the members of T but agent i improve without agent i’s loss by a collusive
misrepresentation of their preferences as RT instead of R??T . Hence, a contradiction again
to (CSP).
(Only if part) Let ϕ satisfy (MON). Suppose that ϕ does not satisfy (CSP). Then
∃S ⊂ N, S 6= ∅ : ∃R ∈ P N : ∃R0S ∈ P S :(∀i ∈ S : ϕ(R−S , R0S )(i)Ri ϕ(R)(i)) & (∃j ∈ S : ϕ(R−S , R0S )(j)P j ϕ(R)(j)).
Let x = ϕ(R) and y = ϕ(R−S , R0S ). Note that x 6= y. Let T = {i ∈ S | y(i)P i x(i)}.
Thus for i ∈ S − T (notice that S − T may be empty), y(i) = x(i). Let R?S be any elementof P S which satisfies7∀i ∈ T : topR?i (H) = y(i) & topR?i (H − {y(i)}) = x(i), and∀i ∈ S − T : topR?i (H) = x(i) = y(i).
Then I have ∀i ∈ S : L(x(i), Ri ) ⊂ L(x(i), R?i ). Recall that x = ϕ(R). Thus (MON)implies that ϕ(R−S , R?S ) = x. Also notice that ∀i ∈ S : L(y(i), R0i ) ⊂ L(y(i), R?i ). Recall
that y = ϕ(R−S , R0S ). Hence by (MON), I have ϕ(R−S , R?S ) = y. Thus I conclude thatx = y. This is a contradiction. 2
Remark 2.2 As mentioned, for voting rules, strategy-proofness is equivalent to monotonicity (Muller and Satterthwaite, 1977). But in housing markets, even the axiom (wCSP)
is too weak to imply (MON). To see this, consider a solution ψ defined as follows:∀R ∈ P N :ψ(R)(1) = topR1 (H),ψ(R)(2) = topR1 (H − {ψ(R)(1)}),
ψ(R)(3) = topR1 (H − {ψ(R)(1), ψ(R)(2)}),. . . proceeding inductively.
Clearly, ψ satisfies (SP) and (wCSP), but not (CSP). (Note that the allocation ψ(R) is
determined independent of Rj with j 6= 1.)
Remark 2.3 Since it is shown that (CSP) is strictly stronger than (wCSP) in the above
remark, one should ask about the logical relation between (SP) and (wCSP). For voting
rules, as shown in Ishikawa and Nakamura (1979), strategy-proofness is equivalent tocoalition strategy-proofness. (In this case, coalition strategy-proofness and weak coalition
7

Let Ri be a preference relation. Let Y ⊂ H. Then I denote topRi (Y ) := {h ∈ Y | ∀k ∈ Y : hRi k}. If
topRi (Y ) is a singleton, then I slightly abuse the notation and denote by topRi (Y ) the single element.

5

strategy-proofness are the same for the assumption of the strict preference domain. Recall
Footnote 2.) But this is not the case for housing markets. The following example showsthat (SP) does not imply (wCSP). Let n be an even integer with n ≥ 4. Let m = n/2.
Then let S1 = {1, . . . , m} and S2 = {m + 1, . . . , n}. Note that {S1 , S2 } is a partitionof the set of agents N , and that |S1 | = |S2 |. And correspondingly, the set of goods H
is partitioned into {H1 , H2 }, where Hp := H|Sp = {wi }i∈Sp with p = 1, 2. Here and in
the sequel, ‘|’ denotes restriction. Then I obtain two ‘split’ housing markets from thesepartitions. For p = 1, 2, let σp : P|Hp Sp → A |Sp be the strong core of the housing market
consisting of the agent set Sp and the set of goods Hp . Here the set of allocations A |Sp
is the set of bijections from Sp onto Hp . Then define a solution ψ to the housing market
consisting of N and H as follows:∀R ∈ P N :∀i ∈ S1 : ψ(R)(i) = σ2 ((Rj |H2 )j∈S2 )(m + i), and∀i ∈ S2 : ψ(R)(i) = σ1 ((Rj |H1 )j∈S1 ))(i − m).
In the above solution, an allocation within subgroup S1 is determined by the preferencesof subgroup S2 over H2 , and vice versa. Thus it is obvious that ψ satisfies (SP). But ψ
does not satisfy (wCSP).
Remark 2.4 8 If I assume weak preferences, then the ‘if’ part of Theorem 2.1 does nothold. I have the following counterexample:
Let N = {1, 2}. Hence H = {w1 , w2 }. Let R denote the set of weak preferences on
H. (Note that P ⊂ R.) Let ψ be a solution such that ∀R ∈ R N :ψ(R) = (the strong core allocation for R) if R ∈ P N ,ψ(R)(i) = topRi (H) and ψ(R)(j) = H − {ψ(R)(i)} if Ri ∈ P and Rj 6∈ P, andψ(R)(i) = wi ∀i ∈ N, otherwise.
ψ satisfies (CSP). The following proves this. Clearly, ψ satisfies (PO). This implies that thegroup {1, 2} does not gain from misreporting. Now suppose that a single agent i gains frommisrepresentation when his true preference is Ri , and the other agent j reports Rj . Thenit must be that Ri ∈ P and ψ(R)(j)P i ψ(R)(i). This implies Rj ∈ P. Then since (PO)is satisfied, I have ψ(R)(j)P j ψ(R)(i). Thus it follows that (ψ(R)(i), ψ(R)(j)) = (wi , wj ).
Now it is easy to check that agent i alone cannot change the resulting allocation by shifting
his preference reporting. This is a contradiction.
ψ does not satisfy (MON). There is an example to check this. Let R1 and R2 satisfy
1
w I i w2 for i = 1, 2. Then ψ(R) = (w1 , w2 ). But when R02 is such that w1 P 02 w2 (notethat H = L(w1 , R2 ) = L(w1 , R02 )), I have ψ(R1 , R02 ) = (w2 , w1 ) 6= ψ(R). Thus the ‘if’part fails to be true. However, the ‘only if’ part still holds true (i.e.(MON) implies (CSP))
under weak preferences. The proof applies without essential change.
Lemma 2.5 If ϕ satisfies (CSP) and (ONTO), then ϕ satisfies (PO).
Proof Let ϕ satisfy (CSP) and (ONTO). Suppose that ϕ does not satisfy (PO). Then
∃R ∈ P N : ∃x ∈ A : (∀i ∈ N : x(i)Ri ϕ(R)(i)) & (∃j ∈ N : x(j)P j ϕ(R)(j)). (ONTO)
implies ∃R0 ∈ P N : x = ϕ(R0 ). Then I have ∃R ∈ P N : ∃R0 ∈ P N : (∀i ∈ N :ϕ(R0 )(i)Ri ϕ(R)(i)) & (∃j ∈ N : ϕ(R0 )(j)P j ϕ(R)(j)). This says that ϕ violates (CSP).
This is a contradiction. 2
8

Here and in the sequel, abusing the notation, for a solution ϕ, ϕ(R) denotes the n-tuple (ϕ(R)(i))n
i=1 .

6

Remark 2.6 Lemma 2.5 still holds true even if I assume weak preferences. The proof isessentially the same.
The strong core can be characterized by strategy-proofness. The following result wasestablished by Ma (1994).
Theorem 2.7 (Ma, 1994) ϕ is the strong core if and only if ϕ satisfies (SP), (IR) and(PO).
Proof See Ma (1994).
Combining my results and Ma’s theorem in the above, I obtain the following characterization of the strong core.
Corollary 2.8 ϕ is the strong core if and only if ϕ satisfies (MON), (IR) and (ONTO).
Proof (If part) Immediate from Theorem 2.1, Lemma 2.5 and Theorem 2.7.
(Only if part) It is immediate that the strong core satisfies (IR) and (ONTO). Since
the strong core satisfies (CSP) (Bird, 1984), Theorem 2.1 implies that it satisfies (MON).
2
Remark 2.9 Sonmez (1996) proved that the strong core is the only solution that satisfies(MON), (IR) and (PO). Corollary 2.8 sharpens this result by weakening (PO) to (ONTO).
Sonmez (1996) showed this result as a corollary to his theorem that deals with the Nash
implementation problem in a more general environment than housing markets.

3

Further Results

1. Since it has been proved that the axiom (MON) is equivalent to the axiom (CSP),
it may be questioned if there exists a monotonicity property which is equivalent to theaxioms (SP) or (wCSP). I have a partial answer. I introduce the following definition.
Individual Monotonicity (IMON): ∀R ∈ P N : ∀i ∈ N : ∀R0i ∈ P : (x = ϕ(R) & L(x(i), Ri ) ⊂L(x(i), R0i )) ⇒ x(i) = ϕ(R−i , R0i )(i).
Lemma 3.10 Let ϕ be a solution. Then ϕ satisfies (IMON) if and only if ϕ satisfies(SP).
Proof The proof is very similar to that of Theorem 2.1.
(If part) Let ϕ satisfy (SP). Suppose that ϕ does not satisfy (IMON). Then ∃i ∈ N :∃R ∈ P N : ∃R0i ∈ P : (x = ϕ(R) & L(x(i), Ri ) ⊂ L(x(i), R0i )) & x(i) 6= ϕ(R−i , R0i )(i).
Then either ϕ(R−i , R0i )(i)P i ϕ(R)(i) or ϕ(R)(i)P i ϕ(R−i , R0i )(i) is true. If the former istrue, then it contradicts (SP). If the latter is true, then I also have ϕ(R)(i)P 0i ϕ(R−i , R0i )(i),which contradicts (SP).
(Only if part) Let ϕ satisfy (IMON). Suppose that ϕ does not satisfy (SP). Then∃i ∈ N : ∃R ∈ P N : ∃R0i ∈ P : ϕ(R−i , R0i )(i)P i ϕ(R)(i). Let us denote x = ϕ(R) andy = ϕ(R−i , R0i ). Thus I have x(i) 6= y(i). Then let R?i be any element of P which satisfies
topR?i (H) = y(i) and topR?i (H − {y(i)}) = x(i). Note that L(x(i), Ri ) ⊂ L(x(i), R?i ).
By (IMON), this implies ϕ(R−i , R?i )(i) = x(i). Also note that L(y(i), R0i ) ⊂ L(y(i), R?i ).
By (IMON), this implies ϕ(R−i , R?i )(i) = y(i). Thus I have x(i) = y(i). This is a contradiction. 2

7

(IMON) is obviously implied by (MON). It says that if an agent keeps or improves
the relative ranking of the good allocated to him (fixing the others’ preferences), then thegood allocated to him (rather than the allocation itself) does not change.
Remark 3.11 The ‘only if’ part of this lemma holds true on the weak preference domain
R N . But the ‘if’ part does not. A counterexample is the solution ψ in Remark 2.4, which
satisfies (SP) but not (IMON).
2. I examine the results obtained in relation to the following well-known axiom (Satterthwaite and Sonnenschein, 1981).
Nonbossiness (NB): ∀R ∈ P N : ∀i ∈ N : ∀R0i ∈ P : ϕ(R−i , R0i )(i) = ϕ(R)(i) ⇒ϕ(R−i , R0i ) = ϕ(R).
The axiom (NB) says that when an agent changes his preference reporting, he cannot
influence the total allocation without affecting his own allocation. The following fact isstraightforward.
Theorem 3.12 ϕ satisfies (MON) if and only if ϕ is (SP) and (NB).
Proof (If part) By definition, (IMON) and (NB) together imply (MON). Thus by Lemma
3.10, the desired conclusion is obtained.
(Only if part) By Theorem 2.1, (MON) implies (SP). Now I show that (MON) also
implies (NB). Suppose that ϕ satisfies (MON) but not (NB). Then ∃R ∈ P N : ∃i ∈N : ∃R0i ∈ P : ϕ(R−i , R0i )(i) = ϕ(R)(i) & ϕ(R−i , R0i ) 6= ϕ(R). Denote ϕ(R) by x.
Then choose a preference relation R?i of agent i such that x(i) = topR?i (H). Then
Clearly, L(x(i), Ri ) ⊂ L(x(i), R?i ) and L(x(i), R0i ) ⊂ L(x(i), R?i ). Thus (MON) implies
ϕ(R−i , R?i ) = ϕ(R) and ϕ(R−i , R?i ) = ϕ(R−i , R0i ). Thus I have ϕ(R−i , R0i ) = ϕ(R), a
contradiction. 2
Svensson (1999) has already pointed out that [(SP) & (NB)] ⇒ (MON), but not theconverse. Analogous relations are observed in other models (e.g. Barberà and Jackson,
1995).
Remark 3.13 When the domain is the weak preferences R N , the ‘if’ part of Theorem
3.12 does not hold true. To see this, consider the following solution ψ. Let R ∈ R N .
Consider a construction R 7→ R? , R? ∈ P N as to satisfy the following:∀i ∈ N : ∀j, k ∈ N : [[j > k & wj I i wk ] or wj P i wk ] ⇒ wj P?i wk .
Note that this construction is unique. Let us denote by σ the strong core. Then define asolution ψ such that∀R ∈ R N : ψ(R) = σ(R? ).
That is to say, the solution ψ is the strong core with ‘tie-breaking according to the indexesof the goods’. This solution ψ satisfies (SP) and (NB) but not (CSP).9 Recall that as
noted in Remark 2.4, (MON) still implies (CSP) on the domain of weak preferences R N .
Thus ψ does not satisfy (MON).
9This solution ψ is discussed in Bird (1984). He shows by example that ψ satisfies (SP) but not (CSP).

8

Remark 3.14 The ‘only if’ part of Theorem 3.12 still holds true on the domain R N . The
proof is essentially the same. But I note that on this domain (CSP), which is equivalent to(MON) on the domain P N , does not imply (NB), although on the strict preference domain
P N , this implication is trivially true. A counterexample is as follows: Let N = {1, 2, 3}.
Assume that the domain is R N . Let {Q, S } be a partition of R. Define a solution ψ as
to satisfy the following: Let R ∈ R N .
(1) If w1 I 1 w2 & w1 I 2 w2 , then(i) if R3 ∈ Q, then ψ(R) = (w1 , w2 , w3 ), and(ii) if R3 ∈ S , then ψ(R) = (w2 , w1 , w3 ).
(2) Otherwise, ψ(R) = (σ 1 , σ 2 , w3 ).
Here (σ 1 , σ 2 ) coincides with the strong core allocation of the housing market ({1, 2}, {w1 , w2 }, R|{w1 ,w2 } ).
Note that (σ 1 , σ 2 ) is unique for any R in the case (2) above. Then ψ satisfies (CSP) but
not (NB) (since agent 3 changes the total allocation fixing his own).
Remark 3.15 Summing up the results obtained, the following four sets of axioms are all
logically equivalent: {(SP), (NB)}, {(IMON), (NB)}, {(CSP)} and {(MON)}. However,when the domain of a solution is extended to the weak preferences, only the equivalence[(IMON) & (NB)] ⇔ (MON) is preserved. By the examples in Remarks 2.4, 3.11, 3.13
and 3.14, the other pairwise equivalences are all invalidated. (Note that the solution in
Remark 3.11 satisfies (NB).)
Now the following characterization is immediate.
Corollary 3.16 ϕ is the strong core if and only if ϕ satisfies (SP), (NB), (IR) and(ONTO).

4

Independences of the Axioms

I show the logical independences of the axioms in each of the two characterizations of thestrong core: [(MON), (IR) and (ONTO)] and [(SP), (NB), (IR) and (ONTO)]. Since I
have (MON) ⇔ [(SP) & (NB)] (see Theorem 3.12), it suffices to show the independences
for the system [(SP), (NB), (IR) and (ONTO)] by means of examples. Let σ denote thestrong core in the following.
Example 4.17 Let ψ be a solution such that∀R ∈ P N : ∀i ∈ N : ψ(R)(i) = wi .
Then ψ satisfies (SP), (NB) (thus (MON)) and (IR), but not (ONTO).
Example 4.18 Let ψ be a solution such that 10∀R ∈ P N :ψ(R)(1) = topR1 (H),ψ(R)(2) = topR2 (H − {ψ(R)(1)}),
ψ(R)(3) = topR3 (H − {ψ(R)(1), ψ(R)(2)}),. . . proceeding inductively.
Then ψ satisfies (SP), (NB) (thus (MON)) and (ONTO), but not (IR).
10This solution is an example of simple serial dictatorship (Abdulkadiroğlu and Sönmez, 1998; Svensson,1999).

9

Example 4.19 Assume that n ≥ 3. Let R ∈ P N . Consider a construction R 7→ R? , R? ∈P N such that∀i ∈ N : [h, m ∈ L(wi , Ri ) & hP i m] ⇒ hP?i m, and[j < k & wj , wk ∈ H − L(wi , Ri )] ⇒ wj P?i wk .
Let ψ be a solution which satisfies∀R ∈ P N : ψ(R) = σ(R? )Then ψ satisfies (NB), (IR) and (ONTO), but not (SP) (thus nor (MON)).
Example 4.20 Assume that n = 4. Define Q = {R ∈ P N | (w2 P 1 w1 P 1 w3 P 1 w4 ) &(w1 P 2 w2 P 2 w3 P 2 w4 ) & (w4 P 3 w3 ) & (w3 P 4 w4 )}. Let ψ be a solution such that
ψ(R) = (w2 , w1 , w3 , w4 ) if R ∈ Q, andψ(R) = σ(R), otherwise.
Note that for R ∈ Q, σ(R) = (w2 , w1 , w4 , w3 ). Then ψ satisfies (SP), (IR) and (ONTO),
but not (NB) (thus nor (MON)).

5

Conclusion

This paper has investigated logical relations among coalition strategy-proofness, monotonicity and other related axioms for solutions to housing markets with strict preferences.
I showed that the following four sets of axioms are all logically equivalent: {(SP), (NB)},{(IMON), (NB)}, {(CSP)} and {(MON)}. Two new characterizations of the strong corehas been obtained: A solution is the strong core if and only if it satisfies [(MON), (IR)and (ONTO)] or [(SP), (NB), (IR) and (ONTO)].

References[1] Abdulkadiroğlu, A. and Sönmez, T., 1998. Random serial dictatorship and the core fromrandom endowments in house allocation problems. Econometrica 66, 689–701.
[2] Barberà, S. and Jackson, M.O., 1995. Strategy-proof exchange. Econometrica 63, 51–87.
[3] Bird, C.G., 1984. Group incentive compatibility in a market with indivisible goods. Economics
Letters 14, 309–13.
[4] Gibbard, A., 1973. Manipulation of voting schemes: A general result. Econometrica 41, 587–
601.
[5] Ishikawa, S. and Nakamura, K., 1979. The strategy-proof social choice functions. Journal of
Mathematical Economics 6, 283–95.
[6] Ma, J., 1994. Strategy-proofness and the strict core in a market with indivisibilities. International Journal of Game Theory 23, 75–83.
[7] Maskin, E., 1977. Nash equilibrium and welfare optimality. mimeo. M.I.T.
[8] Maskin, E., 1985. The theory of implementation in Nash equilibrium: A survey. In: Hurwicz, L., Schmeidler, D. and Sonnenschein, H. (eds), Social Goals and Social Organization.
Cambridge University Press. Cambridge. pp. 173–204.
[9] Moulin, H., 1988. Axioms of Cooperative Decision Making. Econometric Society MonographNo. 15. Cambridge University Press. Cambridge.

10[10] Muller, E. and Satterthwaite, M.A., 1977. The equivalence of strong positive association andstrategy-proofness. Journal of Economic Theory 14, 412–18[11] Roth, A.E., 1982. Incentive compatibility in a market with indivisible goods. Economics
Letters 9, 127–32.
[12] Roth, A.E. and Postlewaite, A., 1977. Weak versus strong domination in a market withindivisible goods. Journal of Mathematical Economics 4, 131–37.
[13] Satterthwaite, M.A., 1975. Strategy-proofness and Arrow’s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of Economic
Theory 10, 198–217.
[14] Satterthwaite, M.A. and Sonnenschein, H., 1981. Strategy-proof allocation mechanisms at
differentiable points. Review of Economic Studies 48, 587–97.
[15] Shapley, L. and Scarf, H., 1974. On cores and indivisibility. Journal of Mathematical Economics 1, 23–37.
[16] Sönmez, T., 1996. Implementation in generalized matching problems. Journal of Mathematical
Economics 26, 429–39.
[17] Svensson, L-G., 1999. Strategy-proof allocation of indivisible goods. Social Choice and Welfare
16, 557–67.
[18] Toda, M., 1997. Implementation and characterizations of the competitive solution with indivisibility. Mimeo. Tokyo Keizai University.

11