Consistency and unanimity in the house allocation
problem I: Collective initial endowments∗
Koji TAKAMIYA†
Institute of Social and Economic Research,
Osaka University
Preliminary version, April 11 2006

Abstract
This paper studies allocation correspondences in house allocation problems with collective initial endowments. We examine the implications of two
axioms, namely “consistency” and “unanimity.” Consistency requires the allocation correspondence be invariant under reductions of population. Unanimity requires the allocation correspondence respect unanimity, that is, it
assigns to every agent the object that ranks best for him whenever possible.
We prove that if an allocation correspondence satisfies these two axioms, thenit is a subcorrespondence of the Pareto correspondence. Further, we give acharacterization of the Pareto correspondence using a version of “converse
consistency.”
JEL Classification— C78, D70.
Keywords— house allocation problem, axiomatic characterization, consistency, unanimity, Pareto efficiency.

0Introduction

0.1

Background

This paper studies allocation correspondences for house allocation problems.
In a house allocation problem, there is a set of finitely many agents, and a setof indivisible objects, and each agent has a preference over the set of objects. The
objects are to be allocated to the agents so that each agent receives exactly one
object. Regarding the initial state of the objects, there are two (extreme) cases:
In the case of collective initial endowments, all the objects are initially owned
collectively by the set of agents. In the case of private initial endowments,
each agent has exactly one object at the start.1 This paper concentrates on the∗

All errors are my own responsibility.
Institute of Social and Economic Research, Osaka University. 6-1 Mihogaoka Ibaraki Osaka
567-0047 JAPAN. tel: +81-6-6879-8556. E-mail: takamiya@iser.osaka-u.ac.jp.
1
The in-between case has been also studies, where, at the start, some objects are privately
owned and the others are not. See Abdulkadirouglu and Sönmez (1999), and Sönmez and Ünver(2005).
†

1

collective initial endowment case. Given the set of agents and the set of objects,
an allocation correspondence associates a subset of allocations to each profile
of preferences.
This kind of problems arise in various real life situations in which monetarycompensation is not feasible. Since Shapley and Scarf (1974) first considered the
problem (of the private initial endowment case), numerous papers have studied
this theme. In particular, a growing number of papers have appeared in recent
years.
The purpose of this study is to examine properties of allocation correspondencesthat satisfy two axioms, namely “consistency” and “unanimity.”“Consistency” is a unifying property that is used many axiomatic studies ofgame-theoretic models of resource allocation. It is worth noting that many allocation rules in various models are characterized using consistency. (For survey,
Thomson 1996, 1998.) Consistency basically requires the allocation rule be “invariant” to reduction of population: To be illustrative, consider a group of agentsfacing an allocation problem and some “allocation method” with which we want tosolve this problem. Let us apply this allocation method to the problem, and obtainan allocation x. Then suppose that some of the agents have left the scene, and theremaining agents faces the “same” problem again, which is called the “reduced”
problem. Now the allocation method being “consistent” means that applying theallocation method to the “reduced” problem again yields the allocation x restricted
to the remaining group. In defining consistency for each specific environment, it
is essential how to define “reduced” problems. In the case of the present environment, there is the natural definition due to Ergin (2000), which we will use in thispaper, too.
“Unanimity” is simple and uncontroversial principle in collective decision making in general. The axiom requires the rule adopt those choices (whenever available)
which is unanimously approved by the agents. This seems a minimum requirementin terms of collective welfare. In the present context, unanimity is implied by
Pareto efficiency .
Consistent allocation correspondences (and single-valued rules, too) for thisenvironment has first considered by Ergin (2000), and subsequently studied byEhlers and Klaus (2005) and others. In the previous studies, Pareto efficiency isa prevalent axiom. To our knowledge, however, no authors have ever explicitly
considered unanimity or similar axioms in this context.

0.2

Results

As the main theorem, we prove that if an allocation correspondence is consistentand unanimous, then the correspondence is a subcorrespondence of the Pareto
correspondence. Since the Pareto correspondence itself is consistent and unanimous, the Pareto correspondence is the unique maximal correspondence that satisfies these two axioms. In the previous studies of consistency in this environment,
Pareto efficiency constantly has been considered as an axiom. That is, they require
allocation correspondences to be Pareto efficient, and examine its consequences together with other axioms. In contrast, the present study obtains Pareto efficiency

2

as a result, rather than requiring it. By this result, all the foregoing characterization using consistency and Pareto efficiency simultaneously (such as Ergin (2000),and Ehlers and Klaus (2005)) can be strengthen by replacing Pareto efficiency with
unanimity.
Further, we provide an axiomatic characterization of the Pareto correspondence
using a version of “converse consistency” (which is different from the version in theprevious studies of this model) together with the two axioms. It is worth notingthat although the Pareto correspondence has been treated as one of importantconcepts, there has not been axiomatic support to the correspondence itself.
The present study exclusively deals with the case of collective initial endowments. In the companion piece (Takamiya, 2006), however, we are dealing withthe case of private initial endowments. There, we introduce an extended definition of house allocation problems with private endowments that allows a naturaloperation of population reduction. And we show that consistency and unanimity,
the counterpart of the axioms as considered in the present work, characterizes thecore correspondence. We suppose that it is of some interest to compare theresults in the cases of collective and individual initial endowments.
This paper is organized as follows: Section 1 provides preliminaries. Section 2states the results. And Section 3 gives the proofs of the theorems.

1

Preliminaries

Let N be the set of potential agents. And let H be the set of objects. A houseallocation problem (simply, problem, henceforth) is a list E = (N, H, R). Here,N ⊂ N , N 6= ∅, and H ⊂ H, H 6= ∅ such that #N = #H. And R := (Ri )i∈N is apreference profile. Assume each Ri is a linear ordering (“a ranking with no ties”)
over H. That is, Ri is a complete, transitive and anti-symmetric binary relation
over H. As usual, P i (I i , resp.) denotes the asymmetric (symmetric, resp.) part of
Ri . For H 0 ⊂ H, max Ri (H 0 ) denote the element x ∈ H 0 such that for any y ∈ H 0 ,xRi y.
Let a problem E = (N, H, R) be given. An allocation x is a bijection from
N onto H. x(i) denotes the object allocated to i. Let A(E) denote the set ofallocations in problem E. Let x and y be allocations. And let R be a preference
profile. x Pareto dominates y under R if for each i ∈ N , x(i)Ri y(i), and there
exists some j ∈ N such that x(j)P j y(j). x is Pareto efficient under R if noallocation Pareto dominates x under R.
An allocation correspondence (or correspondence, henceforth) is a multivalued function which associates each problem with a set of allocations in thatproblem. Let ϕ denote a correspondence. The Pareto correspondence is thecorrespondence that specifies the set of Pareto efficient allocations for each problem.
Let us denote the Pareto correspondence by P.
Let U 0 denote the correspondence such that for any E = (N, H, R),
U 0 (E) := {x | ∀i ∈ N, x(i) = max Ri (H)}.
ϕ is unanimous if for every problem E = (N, H, R), ϕ(E) = U 0 (E) if U 0 (E) isnonempty.
3

Let a problem E = (N, H, R) be given. Let N 0 ⊂ N (N 0 6= ∅) and x ∈ A(E). A
reduced problem of E relative to N 0 and x is a problem r(N 0 ,x) (E) = (N 0 , H 0 , R0 ).
Here H 0 = x(N 0 ) and R0 = (R0i )i∈N 0 , where R0i = Ri |H 0 for each i ∈ N 0 . ϕ isconsistent if for every problem E = (N, H, R), and every N 0 ⊂ N (N 0 6= ∅) andx ∈ A(E), it is satisfied that x ∈ ϕ(E) implies x|N 0 ∈ ϕ(r(N 0 ,x) (E)).

2

Results

The main theorem of this paper is the following.
Theorem 1 If a correspondence ϕ is consistent and unanimous, then ϕ is a subcorrespondence of the Pareto correspondence.
The proof of Theorem 1 will be provided in Section 3. By this result, all theforegoing characterizations using consistency and Pareto efficiency simultaneously(such as Ergin (2000), and Ehlers and Klaus (2005)) can be strengthen by replacing
Pareto efficiency with unanimity.
Given Theorem 1, in the sequel we are going for characterizations of the Pareto
correspondence. Let us start with the following lemma.
Lemma 1 The Pareto correspondence is consistent and unanimous.
The proof of Lemma 1 is straightforward thus we omit it. Theorem 1 andLemma 1 together yield the following characterization.
Theorem 2 The Pareto correspondence is the unique maximal correspondence
that is consistent and unanimous.
Although Theorem 2 provides a characterization of the Pareto correspondence,
this is not a full axiomatization of the correspondence. Here we will give a fullaxiomatization using “converse consistency.” However, since the existing definitionof converse consistency by Ergin (2000) does not work for this purpose, we haveto modify the definition.
Ergin (2000) introduced the following definition of converse consistency: ϕ isconversely consistent if for any problem E = (N, H, R) with #N ≥ 2, if for any
N 0 ⊂ N with #N = 2, and any x ∈ A(E), x|N 0 ∈ ϕ(r(N 0 ,x) (E)), then x ∈ ϕ(E). It
is pointed out in Ergin’s paper that the Pareto correspondence is not conversely
consistent.
For our purpose, we have to weaken Ergin’s definition in the following way. Let
U denote the correspondence defined as follows: For any E = (N, H, R),(

U(E) :=U 0 (E)A(E)

if U 0 (E) 6= ∅,otherwise.

ϕ is U-conversely consistent if for any problem E = (N, H, R) with #N ≥ 2, if
for any N 0 ⊂ N with ∅ =6 N 0 6= N , and any x ∈ A(E), x|N 0 ∈ ϕ(r(N 0 ,x) (E)) andx ∈ U(E), then x ∈ ϕ(E).
4

In defining U-converse consistency, we have made two modifications to Ergin’s
existing version: First, the present definition considers the reductions not only
to pair subsets of the grand coalition but to all the nonempty proper subsets.
Second, we condition that the allocation in consideration has to be a unanimous
allocation as long as such an allocation is available. The first point is a natural
weakening. The second point looks somewhat artificial. However, similar variations
are used elsewhere such as Peleg and Tijs (1996), Peleg, Potters and Tijs (1996)
and Takamiya (2001).2
Now we present a full axiomatization of the Pareto correspondence.
Theorem 3 A correspondence ϕ is the Pareto correspondence if, and only if, ϕis consistent, unanimous and U-conversely consistent.
The proof of this theorem is provided in Section 3. The tightness of thischaracterization is checked by the examples as follows.
Example 1 The correspondence U is unanimous and U-conversely consistent, but
not consistent. 2
In Example 1, it is easy to see that ϕ violates consistency. Less obvious is tosee that ϕ is U-conversely consistent. This follows from Lemma 4 which comes up
shortly.
Example 2 Let ϕ be such that for any E,
ϕ(E) = A(E)
Then ϕ is consistent and U-conversely consistent, but not unanimous. 2
Example 3 Let  be a linear ordering over N . Let ϕ be such that for any
E = (N, H, R),
i1 = max  (N ), ϕ(i1 ) = {max Ri1 (H)}; and∀k = 2, . . . , #N, ik = max  (N \ {i1 , . . . ik−1 }),ϕ(ik ) = {max Rik (H \ ϕ({i1 , . . . , ik−1 }))}.
In words, ϕ is the serial dictatorship with respect to the fixed order . Then ϕ isconsistent and unanimous, but not U-conversely consistent. 2
2

One can think of two other versions of converse consistency: One is the version in which only
the first modification is made to Ergin’s definition. The other is the one in which only the second
modification is made. We note that the Pareto correspondence does not satisfy either of these
versions of converse consistency thus they do not work for our purpose.

53

Proofs of the main theorems

This section provides the proofs of Theorems 1 and 3. Although this paper studies
the case of collective initial endowments only, in the following proofs, it will be
helpful to consider the case of private initial endowments, too. Let a problem
E = (N, H, R) be given. And let ω ∈ A(E). Then a house allocation problem
with private initial endowments is (E, ω) = (N, H, R, ω).3
Let a problem (E, ω) = (N, H, R, ω) be given. Let x, y ∈ A(E) and S ⊂ N .
Then x dominates y via S if the followings are satisfied:x(S) = ω(S),∀i ∈ S, x(i)Ri y(i),∃j ∈ S : x(j)P j y(j).
The core of (E, ω) is the set of allocations that are not dominated by any allocations. It is well-known that the core is singleton for each preference profile by the
result of Roth and Postlewaite (1977).4 Let us denote the single element of thecore of (E, ω) by C(E, ω).
There is a well-known algorithm called the “top trading cycle algorithm,” which
is attributed to David Gale (Shapley and Scarf, 1974), for computing the uniquecore allocation for each preference profile. We will utilize this algorithm in the
proofs in the sequel. This algorithm works as follows:(1) Let every agent i point out the agent j who has the object (as the initialendowment) that ranks top to the agent i. Let us denote this by “i → j.”
Then there will be at least one cycle i1 → i2 → · · · → ik → ik+1 with
1 denote the cycles formed at this stage. Let
ik+1 = i1 . Let T11 , T21 , . . . , TM1
all agents in these cycles allocate the objects so that if i → j, then i receives
the object ω(j).
1 leave the scene taking away the objects(2) Let the agents in the T11 , T21 , . . . , TM1
allocated in the previous stage. And let the remaining agents do the same
2 .
thing as (1) with the remaining objects to obtain the cycles T12 , T22 , . . . , TM
2(3) Repeat the process recursively until all the objects have been allocated. Thenk }the set of cycles T := {T1k , T2k , . . . , TM
is obtained.
k k=1,...,KIn the subsequent proofs, we will use the following two lemmas. We omit theproofs of these lemmas. The proof of Lemma 3 would be straightforward from thealgorithm.
Lemma 2 For any E, ω ∈ P(E) if, and only if, ω = C(E, ω).
Lemma 3 Let (E, ω) = (N, H, R, ω) be given. Let T be the top trading cycles
corresponding to the core of (E, ω). For any T ∈ T , and any i ∈ T , C(E, ω)(i) =max Ri (ω(T )).
3

We avoid the notation ((N, H, R), ω), which is accurate but more cumbersome.
Recall that we have assumed that a preference profile is a linear ordering. This result does
not hold for the case in which weak preferences (ties) are permitted.
46

Proof of Theorem 1 Let ϕ be a correspondence. Suppose that ϕ is consistentand unanimous, and that for some problem E = (N, H, R), ϕ(E) 6⊂ P(E). Then
there is some x ∈ A(E) such that x ∈ ϕ(E) and x 6∈ P(E). By Lemma 2, x 6∈ P(E)impliesx 6= C(E, x).
Let us denote by T the top trading cycles associated with C(E, x). Let us
denote y = C(E, x). Then there is some coalition T ∈ T such thatx|T 6= y|T(1)

Since T is a trading cycle arising from x,x(T ) = y(T ).
Thus r(T,x) (E) = r(T,y) (E).
Since y is the core allocation of (E, x), Lemma 3 implies y(i) = max Ri (x(T ))for all i ∈ T . Then by the unanimity of ϕ,{y|T } = ϕ(r(T,x) (E)).
On the other hand, since ϕ is consistent, x|T ∈ ϕ(r(T,x) (E)). Therefore,
x|T = y|T .
However, this contradicts (1). 2
Next, we turn to the proof of Theorem 3. The proof is done by two steps. First,
we will check that the Pareto correspondence is U-conversely consistent. (We havealready known that the correspondence satisfies the other two axioms.) Second,
we will show the uniqueness: By Theorem 1, we have already known that if acorrespondence ϕ is consistent and unanimous, then ϕ ⊂ P. We will show that ϕ
is U-converse consistent and unanimous, then ϕ ⊃ P. These entail ϕ = P.
Lemma 4 Let a correspondence ϕ be unanimous. Then if ϕ is a supercorrespondence of the Pareto correspondence, then ϕ is U-conversely consistent.
Proof Suppose that ϕ ⊃ P. Let E and x ∈ A(E) be given. Suppose that x 6∈ ϕ(E).
Then we show either of the following is true:∃N 0 ⊂ N : N 0 6= N & x|N 0 6∈ ϕ(r(N 0 ,x) (E)),(2)

x 6∈ U(E).

(3)

or

Denote C(E, x) by y. Since ϕ ⊃ P by supposition, we have x 6∈ P(E). Thenby Lemma 2, x 6= y. Let T denote the top trading cycles associated with y. Since7x 6= y, there is some T ∈ T such that x|T 6= y|T . And since T is a trading cycle
arising from x, x(T ) = y(T ). Then Lemma 3 implies
x|T 6∈ {y|T } = U 0 (r(T,x) (E)).

(4)

Recall that ϕ is unanimous. Then if T 6= N , then (4) implies (2). If T = N , (4)implies (3). 2
Lemma 5 Let a correspondence ϕ be U-conversely consistent and unanimous.
Then ϕ is a supercorrespondence of the Pareto correspondence.
Proof Let ϕ be a correspondence. Suppose that ϕ is U-conversely consistent andunanimous, and that ϕ 6⊃ P. Then there is some E = (N, H, R) such that x ∈ P(E)and x 6∈ ϕ(E). Then since ϕ is U-conversely consistent, x 6∈ ϕ(E) implies either ofthe following is true:∃N 0 ⊂ N : N 0 6= N & x|N 0 6∈ ϕ(r(N 0 ,x) (E)),(5)

x 6∈ U(E).

(6)

or

Suppose that U 0 (E) 6= ∅. Then since x ∈ P(E), {x} = U 0 (E). Thus the unanimityof ϕ implies {x} = ϕ(E). This is a contradiction. Therefore, we conclude thatU 0 (E) = ∅. In this case, U(E) = A(E) by definition, which implies x ∈ U(E), thenegation of (6). This implies (5) has to be satisfied.
Let E 0 := (N 0 , H 0 , R0 ) denote the reduced problem r(N 0 ,x) (E) in (5). Thensince the above argument asserts (5) holds true, we have x|N 0 6∈ ϕ(E 0 ). Also by
the fact that P is consistent (by Lemma 1), x|N 0 ∈ P(E 0 ). Thus we can apply
the same argument as above to this case, too. Further, recursively applying thisargument, we obtain some problem E ? which consists of only one agent i, andsatisfies x|{i} 6∈ ϕ(E ? ) and x|{i} ∈ P(E ? ). However, the unanimity of ϕ impliesx|{i} ∈ ϕ(E ? ). This is a contradiction. 2
Proof of Theorem 3 By Lemmas 1 and 4, the Pareto correspondence is consistent, unanimous and U-conversely consistent. Conversely, suppose a correspondence is consistent, unanimous and U-conversely consistent. Then by Theorem 1
and Lemma 5, the correspondence has to coincide with the Pareto correspondence.
2

References[1] Abdulkadirouğlu A and Sönmez T (1999): House allocation with existing tenants. J
Econ Theory 88: pp233–260.
[2] Ehlers L and Klaus B (2005): Consistent house allocation. mimeo. Universite deMontreal. forthcoming in Econ Theory.
[3] Ergin Hİ (2000): Consistency in house allocation problems. J Math Econ 34: pp77–97.

8

[4] Peleg B, Potters JAM and Tijs SH (1996): Minimality of consistent solutions forstrategic games, in particular for potential games. Econ Theory 7: pp81–93.
[5] Peleg B and Tijs SH (1996): The consistency principle for games in strategic form.
Int J Game Theory 25: pp13–34.
[6] Roth A and Postlewaite A (1977): Weak versus strong domination in a market withindivisible goods. J Math Econ 4: pp131–37.
[7] Shapley L and Scarf H (1974): On cores and indivisibility. J Math Econ 1: pp23–37.
[8] Sönmez T and Ünver U (2005): House allocation with existing tenants: An equivalence. Games Econ Behavior 52: pp153–185.
[9] Takamiya K (2001): The consistency principle and an axiomatization of the α-core.
Int J Game Theory 30: pp195–207.
[10] Takamiya K (2006) Consistency and unanimity in the house allocation problems II:
Private initial endowments. Mimeo. ISER, Osaka University.
[11] Thomson W (1996): Consistent allocation rules. University of Rochester Working
Paper.
[12] Thomson W (1998): Consistency and its converse: An introduction. Rochester Center
for Economic Research Working Paper, No. 448.

9