Theoretical Economics Letters, 2013, 3, 340-349
Published Online December 2013 (http://www.scirp.org/journal/tel)
http://dx.doi.org/10.4236/tel.2013.36056
Open Access TEL
Cycles and Rationalization
Patrick de Lamirande
Financial and Information Management, Cape Breton University, Sydney, Canada
Email: Patrick_deLamirande@cbu.ca
Received September 27, 2013; revised October 27, 2013; accepted November 4, 2013
Copyright © 2013 Patrick de Lamirande. This is an open access article distributed under the Creative Commons Attribution License,
which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accor-
dance of the Creative Commons Attribution License all Copyrights © 2013 are reserved for SCIRP and the owner of the intellectual
property Patrick de Lamirande. All Copyright © 2013 are guarded by law and by SCIRP as a guardian.
ABSTRACT
This paper studies the composition of the Paretian allocation set in the context of a finite number of agents and a finite
number of indivisible goods. Each agent receives at most one good and no monetary compensation is possible (typically
called the house allocation problem). I introduce the concept of a cycle which is a sequence of allocations where each
allocation is linked to the following allocation in the sequence by the same switch of goods between a subset of agents.
I characterize the profiles of agent preferences when the Paretian set has cycles.
Keywords: Indivisible Goods; Cycle; Rationalizability; Pareto Allocations
1. Introduction
The house allocation problem consists of the assignment
of indivisible goods to a set of agents who can receive
only one object in the final allocation. Such problems are
very common: allocation of rooms between roommates,
lectures between professors, offices between colleagues,
etc.
This class of problems was introduced by [1]. For this
paper, agents own all goods collectively. While authors
prove the existence of a competitive equilibrium, [2]
shows that this competitive equilibrium is unique when
preferences are strict over the set of goods. Reference [3]
proves that this unique solution can be implemented by a
strategy-proof allocation mechanism. Furthermore, there
is a unique strategy-proof, individually rational and Pare-
to optimal allocation mechanism leading to the unique
core allocation [4]. Reference [5] shows the equivalence
between the competitive allocation from random en-
dowments and the random serial dictatorship while [6]
proves that all mechanisms that are strategy-proof, non-
bossy and neutral must be serially dictatorial. Reference
[7] models the case where there exists at the same time
tenants and new comers on the same market. They intro-
duce the top trading cycles mechanism in this set-up and
show that it is Pareto efficient, individually rational and
strategy-proof. Reference [8] introduces the possibility of
having weak preferences over the set of goods and shows
some restrictions on agent preferences for which effi-
ciency and coalitional strategy-proofness are compati-
ble1.
The purpose of this paper is to look at rationalizability
in the context of the house allocation problem. In other
words, I am interested in answering the following ques-
tions: is it possible to say if, for a given set of allocations,
there is a preference profile which supports this set as a
Paretian allocation set? An example is students’ seats in
class. For every lecture, there is an allocation of seats.
Considering the set of allocations, it is possible to test the
rationality of students’ preferences over seats by studying
observed allocations.
In existing papers on the house allocation problem,
only the [9] mentions explicitly the composition of the
Paretian allocation set. They show that for any two allo-
cations in the Paretian set, there exists a sequence of al-
locations belonging to the Paretian set such that they are
pairwise connected, i.e. there are only two agents swi-
tching their goods and all others stay with the same good.
This means that a set with two allocations that are not
pairwise connected cannot be rationalized.
The main difficulty of using direct inference, i.e. test-
ing each possible preference profile if it supports the al-
location set as a Paretian allocation set, is linked to
number of such preference profiles. As an example, if the
number of goods is 5, then the number of possible allo-
1This list of papers treating of the house allocation problem is not ex-
haustive.
P. DE LAMIRANDE 341
cations is 120 but the number of preference profiles is
close to 25 billion2. Consequently, it seems reasonable to
find a quickest method to study rationalizability.
In this paper, I introduce the concept of a cycle. A cy-
cle is a subset of allocations in which a subset of agents
switches their goods according to a specific scheme. The
presence of cycles in a given set of allocations which is
presumingly a Paretian set gives us information on the
potential preference profiles which would support this set
as a Paretian allocation set. With the concept of a cycle, I
derive some conditions regarding the number of alloca-
tions that have to belong to an allocation set in order for
it to be a Paretian allocation set.
The paper is organized as follows. In Section 2, I pre-
sent the house allocation problem and I define the con-
cept of a cycle. Section 4 talks about the properties of the
cycle and Section 5 presents the implication of the pres-
ence of cycles in the Paretian allocation set. Section 6
concludes.
2. Definitions and Notations
Let
1, 2,,N
2
denote the set of agents with
. The set of goods is
12
,,,
X
xx x
where all
goods are different. I define an allocation

12
,,,aaa a
where i
aX
is the good allocated
to agent i with ij
for . For any set of
agents and for any set of goods
aaij
NN
X
X
with
NX

,
,
NX
 denotes the set of all possible al-
locations of goods in to agents in .
X
N
Agent ’s preferences are represented by a binary re-
lation i which is complete, transitive and antisymmet-
ric (strict preference). Given 12
i
P
,
x
xX, 1i2
x
Px means
that agent strictly prefers
i1
x
to 2
x
. Also,
ij
YY means agents and
PPi
j
have the same pre-
ferences over the set of goods . I define a profile as
Y
1,,PP P
and the domain of all possible profiles is
denoted by
,NX.
Definition 1: An allocation is Pareto optimal for a
given profile if
a
P
ˆ
aA,NX such that
ˆforatleastone
ˆˆ
or1, 2,,
iii
jjjj j
aPai N
aPaa aj


PO P
denotes the set of all Paretian allocations
when the profile is . Then, must be an ele-
ment of which is the set of all non-empty
subsets of
P

PO P
,NX
,
NX . It is important to note here that, for
all preference profiles , the set is never
empty. This means that, for every preference profile ,
there is at least one allocation which is not Pareto domi-
nated by another allocation.
P

PO PP
Definition 2: A set is rationalizable if there is pre-
ference profile such that the Paretian allocation set
for is , i.e.
S
P
PS
SPOP
.
3. Cycles
Since direct inference is at least difficult, it seems natural
to look at the structure of the Paretian set to identify
some patterns that can be used to find one associated
preference profile. Two groups of Paretian sets are trivi-
ally easy to rationalize. First, consider a Paretian set with
only one allocation. Any preference profile where every
agent has the allocated good as his most preferred good
rationalizes this Paretian set. The second case is the other
extreme case where the Paretian set is composed be all
possible allocations. In such case, any preference profile
where agents have the same preferences rationalizes this
set.
However, intermediate cases are more difficult to infer
directly. To solve this problem, I propose the concept of
cycle.
Definition 3: Let the set and
NN
X
X
with
NX

. Let
,n
12
,,nnn

with
12 ,n
N
,,
nn and
12
,,,
e
x
xxx

with
12
,,,
x
xxX
. A set has a cycle

,NXSA
,Cnx
 if
a S
12
,,,Saa
s

12
12
12
12
11
12
22
23
11
,,
,,
,,
,,
nn
nn
nn
nn
ax
ax
ax
ax




such that
1
2
1
1
12
11
,
,
,
,
n
n
n
n
ax
ax
ax
ax

ax
ax
ax
ax
















S
For example, if the set has the cycle
12 , this means there are three alloca-
tions and belonging to such that
3
xx
3
11
11 2
22
122
33
13 2
,,
,,
axax
ax
axax

1,2, 3,C
1
,aa
,
2
,x
aS
1
2 33
2
33
3
132
,,
ax
axax
ax
1


It is important to underline that and
n
x
are vectors
and not subsets of and
N
X
respectively. The reason
is that the order of appearance within the vector is im-
portant to the definition of the cycle. To illustrate the
importance of this distinction, consider the two following
sets:

232
13 1
,,, ,
,,, ,
xx xx
xxxx


31312
32 321
,, ,,
,,, ,
x xxx
x xxx
11
2
x
x
2
S
S
S
The set 1 has the cycle
123
1,2, 3,,,Cxxx
and
2 the cycle S
13
2, 3,,,C2. But those two cy-
cles are different. For this reason, vectors must be used to
define a cycle.
1, xxx
2The number of possible allocation is given by while the number !n
of possible preference profiles is .

!n
n
Open Access TEL
P. DE LAMIRANDE
342
Also, it should be noted that it is possible to write the
same cycle in many ways. Lemma 1 gives the number of
ways to write the same cycle3.
Lemma 1: Any cycle of
elements can be written
in
2
card R
ways where
 

1, 2,,1with0R
mod
 
 
where mod is the modulo operator and
card R
re-
turns the number of elements in R
(cardinality of
R
)4.
The following example illustrates the lemma.
Example 1: Suppose I have the set

123 231 312
,,,,, , ,,Sxxxxxxxxx
. Then, by Lem-
ma 1, there are
2
3
33card R18
ways to write the
cycle:


































123 231
312 123
231 312
123 231
312 321
213 132
321
1, 2, 3,,,1, 2, 3,,,
1, 2, 3,,,2, 3,1,,,
2, 3,1,,,2, 3,1,,,
3,1, 2,,,3,1, 2,,,
3,1, 2,,,3, 2,1,,,
3, 2,1,,,3, 2,1,,,
2,1,3 ,,,2,1,
CxxxCxx
CxxxCxx
CxxxCxx
CxxxCxx
CxxxCxx
CxxxCxx
CxxxC


x
x
x
x
x
x










213
132 321
213 132
3,, ,
2,1,3,,,1,3, 2,,,
1,3,2,,,1,3, 2,,,
x
xx
CxxxCxx
CxxxCxx
x
x
It must be noted that
card R
is always higher or
equal to 2 when
is higher or equal to 3. The number
1 and1
always belong to R
.
Since the number of ways to write the same cycle can
be large5, I propose using the lexicographic ordering to
have a unique notation for a given cycle.
Definition 4: For two vectors and of l com-
ponents, is lexicographically dominated by w if
v w
v
11
112 2
112 2
or
,or
,,,
ll
wv
wvwv
wvwv wv

 
The first step is to choose from all possibilities of
writing a given cycle the ways for which the vector is
lexicographically dominated by (or equal to) the others.
Secondly, from those variants, I choose the one for which
the component subscripts of
n
x
are lexicographically
dominated by the other vector
x
.
Let’s apply this process to the cycle in Example 1. The
first step tells us to select the vector which is lexico-
graphically dominated by the others. This vector is
n
1,2, 3. Then, from the different ways to write the cycle
with
1,2, 3n
, which are
123
1, 2,,,Cxx3 ,x
,
23
3 ,,,x
1 and
1, 2,C xx
312
1, 2,,,Cxx3 ,x
, we
select the one which has the vector
x
whose component
subscripts are lexicographically dominated by the com-
ponent subscripts of the other
x
’s. I find that the unique
solution is
123
I most emphasize that the definition of a cycle is inde-
pendent of what other agents get. For example, consider
the two following sets:
1,2, 3,C, ,xxx
.




1
12345 1245312534
2
2134521453 12534
,,,,, ,,,,, ,,,,
,,,,,,,,,,,,,,
S
x
xxxx xxxxx xxxxx
S
x
xxxxxxxxx xxxxx
These sets have the same cycle
345
3, 4, 5,,,Cxxx
even if they do not have the
same allocations.
An interesting question is how many different cycles
could the set have for set of agents and a given
subset of goods ? There are
SN
X
!
different vectors n
and
!
different possible vectors
x
. There are

2
!
possibilities. But, I have already shown that there are
car
2
d R
ways to write the same cycle. So there
are

2
1!
card R
different cycles for a given subset of
agents and a subset of goods .
N
X
Also, it is possible that a Paretian set contains more
than one cycle. In particular, it could happen that the
Paretian set
PO P has two cycles:
,Cnx
 and
,Cnx with NN and XX. To examine this
case, I define the concept of subcycle.
Definition 5: Suppose that the set has
a cycle
,SAXN
,Cnx
 . The cycle
,xCn is a subcycle of
,Cnx
 if NN and XX.
Example 2 illustrates the concept of subcycle.
Example 2: Suppose that the set has a cycle S
1234
1, 2,3, 4,,,,Cxxxx
. Let s is the set of
allocations
SS
s
a belonging to such that S
1122 33 44
12 2334 41
13 24 3142
14 2132 43
,,,
,,,
,,,
,,,
ss ss
ssss
ssss
ssss
axaxaxax
axaxaxax
axaxaxax
axaxaxax




or
or
or
3All proofs are in Appendix.
4For ,
, mod
is the remainder of the division of
by
.
5For example, if , then we can write the same cycle in 200 dif-
ferent ways.
5m
Then, this cycle contains 4 different subcycles:
13
1, 3,,Cxx
,
 
24
1, 3,,Cxx
,
13
2, 4,,Cxx
and
24
2, 4,,Cxx
Open Access TEL
P. DE LAMIRANDE 343
To know if the cycle
,Cnx
 has subcycles, I study
the set R
. The next lemma tells us the condition nec-
essary for
,Cnx
 to have subcycles.
Lemma 2: If
1card
R
, then
,Cnx
 has
subcycles.
Example 3: Suppose a set has the cycle S
,Cnx

456
,,,
with and

1, 2,3, 4,5, 6n
123
,,
x
xxxx
16
,,aa
xx
.
This means there are 6 allocations belonging
to such that:
S
11 11 11
112233445566
222222
12233445566
666666
16213243546
,,,,,
,,,,,
,, ,,,
axaxaxaxaxax
axaxaxaxaxax
axaxaxaxaxax



1
5
Set . Then, cycle
62,3, 4,6R
,Cnx with
1,n4 and
14
,
x
xx is a subcyle of
,Cnx.
The last definition about cycles is the following:
Definition 6: The set has a complete
cycle
,SAXN
,
c
CNX
 with and
NN
X
X
where
cardXN card

if for all

12 ,n,,nnn

with
12
,, ,nnnN

and

12
,,,
x
xxx
 
with
12
,, ,
x
xx

X
, contains the cycle S
,Cnx
 .
In other words, the set has a complete cycle
T
,
c
CNX
 if there is at least one allocation that belongs
to
A
for all possible permutations of goods belonging
to between agents belonging to .
X
N
4. Properties of Cycles and Complete Cycles
The presence of a cycle
,Cnx
 in a Paretian set

PO P gives information about the preferences of
agents. The first insight given by a cycle is about pairs of
goods which are neighbors in the vector
x
.
Proposition 1: If has a cycle

PO P
,Cnx
 , then
,ij N
11
11
,,
,,
and kk kk
ij
xx xx
ij
xx xx
PP
PP
1, 2, 3,,1k
 
.
Consequently, if the Paretian set has a cycle, then all
agents belonging to the cycle have same preferences over
any pairs of neighbor goods in that cycle. With this
proposition, some information on the associated profile
is provided by the presence of a cycle in the Paretian
set. However, information on preferences is only over
each pair
P
1
,
kk
xx
and the pair
1
,
x
x
. No informa-
tion about the preferences over all pairs of goods be-
longing to the set can be extracted from the cycle.
The following example demonstrates the problem.
X
Example 4: Suppose the cycle

1234
1, 2,3, 4,,,,Cxxx

PO P
1234
1313
3131
2222
4444
PPP P
x
xxx
x
xxx
x
xxx
x
xxx
Then when the good 3
x
is allocated to someone who
belongs to
1, 3, the good 1
x
is allocated to the other
agent in that set. The cycle does not contain an allocation
where the good 1
x
is allocated to someone in
1, 3
and the good 3
x
to someone in . This means that
agents in

2, 4
1, 3 could have different preferences over
the set
13
,
x
x than agents in . The same is true
for the set of goods

2, 4
24
,
x
x.
To analyze preferences over a pair of goods which are
not neighbors to each other in the vector
x
, I use the
concept of subcycle. In Section 2, I showed that a subcy-
cle is a cycle. So, if a cycle has subcycles, Proposition 1
can be used to infer agents’ preferences.
Proposition 2: Suppose has a cycle

PO P
,Cnx
 . For R
,
 
,,
ii
yy yy
nn
xx xx
PP



1, 2,,,1,2,,iy




Let’s apply this proposition to the following example.
Example 5: Suppose has a cycle

PO P
,Cnx

with
1, 2,3, 4,5, 6n
and

,,,
123456
,,
x
xxxxxx
.
Then, this means there are six allocations
123456
,,,,,aaaaaa POP
11
such that
1
1122 66
22 2
1223 6
333
1324 6
44 4
1425 6
55 5
1526 6
66 6
1621 6
,,,
,,,
,,,
,,,
,,,
,,,
axax ax
axax ax
axax ax
axax ax
axaxax
axax ax

1
2
3
4
5





Consider goods 1
x
and 4
x
. Then,
11
11 44
44
144
,
,
axax
axax
1
Then agents 1 and 4 have same preferences over the
14
,
x
x. If we continue, we find that
1) Agents in
1, 2,3, 4,5, 6 have the same prefer-
ences over sets
12
,
x
x2
,,

3
x
x,

34
,
x
x,
45
,
x
x,
56
,
x
x and
16
,
x
x.
2) Agents in
1, 3, 5 have the same preferences over
sets
13
,
x
x,
24
,
x
x,
35
,
x
x,
46
,
x
x,
51 ,
x
x
and
26
,
x
x.
3) Agents in
2, 4, 6 have the same preferences over
sets
13
,
x
x,
24
,
x
x,
35
,
x
x,
46
,
x
x,
51 ,
x
x
x
belongs to the Paretian set
. Then the following profile supports the cycle.
Open Access TEL
P. DE LAMIRANDE
344
and
26
,
x
x.
4) Agents in
1, 4 have the same preferences over
sets

14
,
x
x,
25
,
x
x and
36
,
x
x.
5) Agents in
have the same preferences over
sets
2,5

14
,
x
x,
25
,
x
x and
36
,
x
x.
6) Agents in
have the same preferences over
sets
3, 6

14
,
x
x,
25
,
x
x and
36
,
x
x.
This result gives additional information about the pro-
file since it provides information on preferences over
pairs of goods which are not neighbors in the cycle.
Subcycles can be analyzed on their own since they are
themselves distinct cycles, but they could be supported
by different preference profiles across agents than the
larger cycle. However, by using subcycles, it is only pos-
sible to show that agents which are neighbors in a subcy-
cle have the same preferences over all pairs of goods
which are neighbor in this subcycle and it is possible that
two distinct subsets of agents in the cycle hold different
preferences over the same subset of goods.
P
While Proposition 2 gives us information about pref-
erences over pairs of goods that are neighbors in a sub-
cycle, Proposition 3 deals with the other pairs.
Proposition 3: Suppose that has a cycle

PO P
,x

Cn . For all pairs of goods ,
x
x

 X with
such that
belongs to R
,
 
,,,
ij
xx xx
PP ij
 

 
N
It must be noted that if
is a prime number, all pairs
of goods are treated by Proposition 3 since
1R
.
In this case, all agents in have the same preferences
over the set .
N
X
Corolla ry 1: If has a cycle

PO P
,Cnx
 and
is a prime number, then ,
,
ij N
ij
YY
PP
This result is very strong. Only one cycle is enough to
conclude that a subset of agents have the same prefer-
ences over a subset of goods. Unfortunately, as showed
above, this result cannot be extended to any number of
individuals in .
N
Another case can lead to the conclusion that agents in
a subset of have the same preferences over a subset
of goods.
N
Proposition 4: If has a complete cycle

PO P
,CNX

X
c, the agents in have the same preferences
N
over .
The presence of a complete cycle gives us more in-
formation about agent preferences. In fact, a cycle could
give the same information if the number of elements in
that cycle is a prime number. Unless it has this charac-
teristic, a cycle by itself does not give information on
preferences over all goods. But, if a single cycle cannot
give the same information than a complete cycle, many
cycles can provide it.
Proposition 5: Let the set be a subset of and
a subset of
N
N
X
X
with
 
.carcardXdN


. Let
be the lowest prime number such that 0
mod
. If
PO P has

12!1

 


cycles with same
n
and same , then the agents in have the same
preferences over .
X
N
X
To illustrate the idea of this proof, consider the fol-
lowing example. Suppose
6card X and suppose
has the following cycles :
S
the 6 cycles given by
12 3
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
124
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
12 5
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
12 6
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
132
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
142
1,2,3,4,5,6 ,,,,,,Cxxx

the 6 cycles given by
152
1, 2,3, 4,5,6,,,,,,Cxxx

the 6 cycles given by
16 2
1, 2,3, 4,5,6,,,,,,Cxxx

S
If has only these cycles, this means agents 1, 3 and
5 could have different preferences over 12
,
x
x than
agents 2, 4 and 6. To have all agents with the same pref-
erences, I must add at least one more cycle.
An interesting question concerning the composition of
the Paretian set is what happens to the remaining agents.
If the Paretian set has a cycle
,Cnx
 , it is interesting to
know if there is an allocation in
,
A
NN XX

such that
agents outside the cycle get the same goods in all alloca-
tions which can constitute the cycle. In other words, if I
define c
X
XX

, , the question is: “Is there a
c
NN
N
,
cc
NX

zA
z
such that the set composed by all
allocations belonging to where agents in
get has a cycle
c
S

PPO c
N
,Cnx
 ?” The answer is: there is no
guarantee that the existence of such an element. Take the
following example:
Example 6: Suppose the preferences for 6 agents are
given by
12345 6
111166
333324
242455
425511
554233
666642
PPP PPP
x
xxxxx
x
xxxxx
x
xxxx x
x
xxxxx
x
xxxxx
x
xxxxy
Open Access TEL
P. DE LAMIRANDE 345
Then
















123456
123465
234156
234165
341256
341265
412356
412365
,,,,,
,,,,,
,,,,,
,,,,,
,,,,,
,,,,,
,, ,,,
,, ,,,
x
xxxxx POP
x
xxxxx POP
x
xxxxxPOP
x
xxxxx POP
x
xxxxx POP
x
xxxxx POP
x
xxxxx POP
x
xxxxx POP
I obtain a cycle
,Cnx
 with
1, 2,3, 4n
and
,,,
1234
x
xxxx
. But the subset of in which
allocations give 5

PO P
x
to agent 5 and 6
x
to agent 6 does
not contain the cycle
,Cnx
 . This is also true for the
subset of in which allocations give
PO P
6
x
to
agent 5 and 5
x
to agent 6.
Example 6 shows that the existence of such an ele-
ments is not guaranteed. Nevertheless if such element
exists and the agents in have the same preferences
over the set , then the Paretian set contains a complete
cycle
N
Y
,X

c
Proposition 6: Let the set be a subset of and
a subset of
CN . N
N
X
X
with
carcard X
d N
. Suppose
that all agents in have the same preferences over the
set . If the subset of
N
X
PO c
N
P composed of alloca-
tions in which agents belonging to get
,
cc
NX

zA has the cycle
,Cnx
 , then
PPO
has a complete cycle
,
c
CNX
 in which get .
c
N
z
To illustrate this proposition, consider the case where
the Paretian set contains the allocations

PO P
12345
,,,,
x
xxxx,
23145
,,,,
x
xxxx and
312 4 5
,,,,
x
xxxx. Then,
PO P has the cycle
123
xx
1,2, 3,,,Cx
. By Proposition 6, the allocations
12 3 45
,,,,
x
xxxx
,
21345
,,,,
x
xxxx and
32145
,,,,
x
xxxx

PO P
must also belong to . Then,

PO P

3 ,,,
has a complete cycle .

123
1, 2,
c
Cxx
x
5. Cycles and Paretian Sets
Finding a preference profile that rationalizes a set is
easy in some cases. When
S
,SANX
a
, then any pref-
erence profile such that agents have same preferences
rationalizes the set has a Paretian set. Also, if the set
has only one allocation , this set can be rational-
ized by any preference profile in which each agent gets
his most preferred good. Even in the case where has
two allocations, this set can be rationalized if the two
allocations are pairwise connected. However, it is not
possible to go further. At the first look, it is impossible to
say if a set can be rationalized even if all allocations
are pairwise connected6.
S
S
S
S
Fortunately, it is possible to find some necessary con-
ditions on rationalizable sets. Before presenting some
conditions on rationalizable sets, I need the following
proposition.
Proposition 7: Suppose has a cycle

PO P
,Ciy.
Let be an agent belonging to and l
iN
x
an element
of . If all agents belonging to
X
Ni
have the same
preferences over the set
l
X
x
, then agents belonging
to have same preferences over
N
l
X
x
.
The next proposition describes the restrictions on the
number of allocations
PO P
3n
must contain.
Proposition 8: If and
,PO PA N X,
then

11cardPO Pn
!n
  . If P
1!1P nnPO
 , then there exist an agent
and a good l
i
x
belonging to
X
such that there is no
allocation belonging to with
h
a

PPO h
i
ax
l
and
the preference profile is given by
1)

,
g
hl
Y
Y
PP ghNYXx
2)

,
gh
X
X
PP ghNi
3)
 

,
,for some
lk
lk
g
ik
xx
xx
PPgNixX 
l
x
Using Proposition 8, it is possible to know if a set
cannot be rationalized just by looking to the number of
allocations belonging to this set. If
11!1,!card Snnn1
 
P, then there exists
no preference profile such that
SPOP. But,
the reverse is not true. This is a necessary condition.
Furthermore, it is possible to use cycles to find other in-
tervals such that, if the number of allocations of a set
belongs to those intervals, then this set cannot be ration-
alized. However, it is not possible to find a general form
for all of those intervals.
6. Conclusions
The rationalizability in the context of house allocation is
hard to provide. Except in cases where there are only a
few allocations (1, 2 or 3) or for extreme cases (the set of
all possible allocations or for singleton), it is very diffi-
cult to conclude. The use of cycles can help to analyze
the rationalizability of an allocation set.
While Proposition 8 studies the number of elements
necessary for an allocation set to be rationalizable, Pro-
position 6 presents a case where the fact that a set con-
tains a cycle implies that it must contain some specific
allocations too. Proposition 8 could be extended to in-
clude more conditions, but to devise a complete state-
ment of all cases promises to be very long and compli-
cated. From my point of view, the most interesting ave-
6For example, consider the set
1234 2134 1243
,,,,,,,, ,,,T xxxxxxxxxxxx. All allocations are pair-
wise connected but this set cannot be rationalized.
Open Access TEL
P. DE LAMIRANDE
Open Access TEL
346
nue for the use of cycles is to employ them like I do in
Proposition 6. In short, cycles can be useful to study di-
rectly the rationalizability of an allocation set, since by
using cycles, it is possible to say if a given allocation set
is missing some allocations to be rationalizable.
7. Acknowledgements
I would like to acknowledge Mathieu Dufour, Walter
Bossert, Lars Ehlers, Yves Sprumont and Yves Richelle
for their helpful comments. Of course, all remanning
errors are mine.
REFERENCES
[1] L. Shapley and H. Scarf, “On Cores and Indivisibility,”
Journal of Mathematical Economics, Vol. 1, No. 1, 1974,
pp. 23-37.
http://dx.doi.org/10.1016/0304-4068(74)90033-0
[2] A. E. Roth and A. Postlewaite, “Weak versus Strong Do-
mination in a Market with Indivisible Goods,” Journal of
Mathematical Economics, Vol. 4, 1977, pp. 131-137.
http://dx.doi.org/10.1016/0304-4068(77)90004-0
[3] A. Roth, “Incentive Compatibility in a Market with Indi-
visibilities,” Economic Letters, Vol. 9, 1982, pp. 127-132.
http://dx.doi.org/10.1016/0165-1765(82)90003-9
[4] J. Ma, “Strategy-Proofness and the Strict Core in a Mar-
ket with Indivisibilities,” International Journal of Game
Theory, Vol. 23, 1994, pp. 75-83.
http://dx.doi.org/10.1007/BF01242849
[5] A. Abdulkadiroğlu and T. Sönmez, “Random Serial Dic-
tatorship and the Core from Random Endowments in
House Allocation Problems,” Econometrica, Vol. 66, No.
3, 1998, pp. 689-701. http://dx.doi.org/10.2307/2998580
[6] L.-G. Svensson, “Strategy-Proof Allocation of Indivisible
Goods,” Social Choice and Welfare, Vol. 16, 1999, pp
557-567. http://dx.doi.org/10.1007/s003550050160
[7] A. Abdulkadiroğlu and T. Sönmez, “House Allocation
with Existing Tenants,” Journal of Economic Theory, Vol.
88, 1999, pp. 233-260.
http://dx.doi.org/10.1006/jeth.1999.2553
[8] L. Ehlers, “Coalitional Strategy-Proofness House Alloca-
tion,” Journal of Economic Theory, Vol. 105, 2002, pp.
298-317. http://dx.doi.org/10.1006/jeth.2001.2813
[9] A. Ben-Shoham, R. Serrano and O. Volij, “The Evolution
of Exchange,” Journal of Economic Theory, Vol. 114,
2004, pp. 310-328.
http://dx.doi.org/10.1016/S0022-0531(03)00112-1
P. DE LAMIRANDE 347
Appendix
Proof of Lemma 1: Suppose the set has a cycle S
,Cnx
 . Then, the set contains S
allocations such
that:
11 1
112 2
22 2
1223 1
121
,,,
,,,
,,,
axax ax
axaxax
axax ax

 

 
 
 

 

1
I can write this cycle by using 23 1
,,,,
x
xx xx
.
Then, all cycles with
,Cnx
x
which has its com-
ponents switching neighbor to neighbor relative to
x
give the same cycle. This gives
different ways to
write the same cycle. I can do the same thing by switch-
ing elements of and I find also
n
r ways to write the
cycle. Now, consider the number which is a positive
integer strictly lower than
. Suppose that there exists
no positive integer strictly lower than
q
such that
. Let 0modrq
 

 

11 21 11
1,1,21, ,11
,, ,,
rmod rmod r
nrmod rmodr
xxxx x


  


and consider the cycle
,Cn x

. Since r does not
belong to R
, this means all components of n
and
x
 are different. So, the cycle is the same
than
,Cn x
 
,x

Cn . This is true for all which are positive
integers strictly lower than
r
and do not belong to R
.
Finally, I obtain

2
card R
.
Proof of Lemma 2: Without lost of generality (WL-
OG), let’s take the cycle
,Cnx
 with
1, 2,,n
and

12
,,,
x
xx x
. If
1
card R
, it means
that there is atleast one
r
which does not belong to
R
. If does not belongs to rR
, this means there is a
positive integer q strictly lower than
such that
.
0rq
mod
Now, consider the vector of agents
 


1,1,21, ,11
II
nmod modq
 
  and
the vector of goods
 

11 21 11
,, ,,
II
mod mod q
xxxx x

Since is not equal to
r
and is strictly lower
then
q
, the set is not equal to . I obtain the
cycle which is a subcycle of
N
N
Cn,x

,Cnx
 .
Proof of Propositio n 1: WLOG, suppose that

1, 2,,n
and
12
,,,
x
xxx
. Consider
1
,
hh
x
x where . Suppose that agent 1
prefers 1h
1, 2,,1hn
x
over h
x
. Because has the cycle

PO P
,Cnx
 , there is an allocation belonging to
PO P
such that 1h
x
is allocated to agent 2 and h
x
to agent 1.
Since this allocation belongs to , then agent 2
must also prefer

PO P
1h
x
to h
x
. Again, because
PO P
has the cycle
,Cnx
 , there is an allocation belonging
to
PO P such that 1h
x
is allocated to agent 3 and
h
x
to agent 2. Since this allocation belongs to
PO P ,
then agent 3 must prefer 1h
x
to h
x
. If I continue for
all agents belonging to
I
, I find that all agents belong-
ing to must have similar preferences for all pairs
N
,
hh1
x
x
with h1, 2,,1
and for the pair 1,
x
x
.
Proof of Propositio n 2: WLOG, suppose that
1, 2,,n
and
,
12
,,
x
xxx
. Let
qr be
the smallest integer such that, for r
and not
belonging to
r
R
,
0modq r r
. If does not
belong to
r
R
, then for every 1,2,, r
and every
1, 2,,1qr
, the cycle
,
s
s
xCn with
 

 

1
,,
,I
II
mod q r
rmod
x


 
s
s
xx

2r
m,,
,, I
rmod
nr
xx
2
,
od
1qr
is a subcyle of
,Cn

x. Because
,
s
s
Cn x is a sub-
cycle of
,x

Cn ,
PO P must have the cycle
,
s
s
Cn x. I can then apply Proposition 1.
Proof of Propositio n 3: WLOG, suppose that
1, 2,,n
and
,
12
,,
x
x
xx x
. Now, take
x
and
x
with 1, 2,,1
and 1,, eta

and let

. By assumption,
belongs to the
set R
.
Suppose that
x
1 P
x
. Because
PO P has the
cycle
,Cnx
 , there is an allocation belonging to
PO P such that
x
is allocated to agent 1
and
x
to agent 1. Since this allocation belongs to
PO P ,
then agent 1
must prefer
x
to
x
. Again, be-
cause
PO P has the cycle
,Cn

x, there is an allo-
cation belonging to
PO P such that
x
is allocated
to agent
2
1mod
and
x
to agent 1
. Since
this allocation belongs to , then agent

PPO
2mod
1
must prefer
x
to
x
.
I can continue until I show that
x
Px

with

, 1mod


1
1,

1, 2mod 1,
 

Since there is no positive integer q
such that
0mod q
, then the set
 
1,1, mod 2 1,

,1 1

mod



has
elements. So all agents belonging to have the same
N
preferences over the set
,
x
x

.
Proof of Proposition 4: Suppose the opposite is true,
i.e. there exists ,ij N
and ,
x
xX

such that
i
j
x
Px
x
Px


This means the good
x
will never be allocated to
j
Open Access TEL
P. DE LAMIRANDE
348
when the good
x
 is allocated to . That contradicts
the existence of a complete cycle.
i
Proof of Proposition 5: Suppose
is prime. By
Corollary 1, if has a cycle

PPO
,x

Cn , then all
agents belonging to have the same preferences over
the set .
N
X
Now, suppose
is not a prime number and let
be the smallest prime number higher than 1 such that
.

0mod
,
Suppose 12
x
x
N
1
X
. Let and be two non-
empty subsets of such that all agents belonging to
prefer goods
1
N2
N
1
N
x
to 2
x
and all agents belonging to
prefer goods
2
N2
x
to 1
x
.
Suppose has

PPO
cycles for
,Cn

t
x
1, 2,,t
. By convention, 11
t
x
x
t for all . For all
cycles , I define
t
,Cn
t
x

the positions of 2
x
in
the vector so that
t
v
2
t
x
x
By Proposition 3, if there is a such that
, and let . 1
t
tt

t
does
not belong to R
, then all agents must have the same
preferences. Suppose t
belongs to R
for all t. Let
the set Π be equal to

,2 ,,

which is a
subset of R
The maximum number such that all
. t
belong to Π
is

21 !



. If
t
12!


 


, then there is
at least one cycle with
,t
Cnx

. By Proposi-
tion 2, then agents belonging to the same set
,,12jj,,j
 
for 1, 2,,j
have
the same preferences. But, agents in different subsets
could have different preferences.
If I add another cycle
,Cnx
 , then
does not
belong to . If
Π
does not belong to R
, by Propo-
sition 3, all agents must have the same preferences over
12
,
x
x. If
belongs to R
, by Proposition 1, for
1, 2,h,
,,hh
, agents belonging to

2
,,h
1mod

 have the same
preferences. Since
does not belong to , then
and
Πh
h
does not belong to the same set
,,12jj,,j

 
1, 2j
for , ,
h. So the
two sets which contain agent and
h
must have
the same preferences. I can continue to conclude that all
agents must have the same preferences.
Proof of Propositio n 6: WLOG, suppose that

12
,,,
X
xxx
and
1, 2,N,
. Let the set
c
X
be equal to and .
XX
c
NNN
Now suppose that
aP
OP where agents belong-
ing to get goods belonging to . This means there
exists an allocation
N
X
,b AXI such that
f
or
j
or at least one
2, ,
iii
jjj j
bPa i
bPab ajN
1,
There are three possible cases for the allocation .
The first case consists of a reallocation between agents in
..
b
c
N
But this kind of reallocation cannot Pareto dominate
the allocation because there exists an allocation
belonging to the Paretian set in which agents belonging
to get . If a reallocation between agents in
dominates , then the allocation should not belong
to
aa
c
N
c
Nz
aa
PPO .
The second case is a reallocation between agents in
. Again, it is not possible for this new allocation to
dominate the allocation . I assume that all agents in
have the same preferences over goods in
N
Na
X
. Then
no reallocation between agents in could Pareto do-
minate the allocation .
N
a
Finally, the last possibility is a reallocation between
agents in both sets Because the agents in have the
same preferences,
N
1
y
is preferred to k
y
by all agents
in .
N
Suppose the agent who gets 1
y
in the new allocation
is agent
. Because of the cycle, there is an allocation
in this cycle such that
gets good k
y
. Then this al-
location could not be in the Paretian set because this al-
location will be dominated.
This means that the allocation where
gets k
y
is
Pareto dominated and contradicts the existence of a cycle
,x

Cn in the set . S
Proof of Proposition 7: For all pairs of goods be-
longing to
X
x
, I can apply Proposition 2 or Propo-
sition 3 to find that there is at least one agent belonging
to
N
with the same preferences as
. Because all
agents belonging to
N
have the same preferences
over
X
x
, then all agents belonging to have the
same preferences over
N
X
x
.
Proof of Proposition 8: Let

Ψ,
A
NXPOP.
By assumption,
Ψ1!n
.
Step 1: Consider the good 1
x
. Suppose that agent 1
gets good 1
x
the least often in the allocations belonging
to . Then, the number of allocations in Ψ where
agent 1 gets
Ψ
1
x
is less than
1!
which is strictly lower than
2!
. This means there is
at least one cycle
1
,Cnx
1
with
12,3, ,n
and
1
23
,, ,
X
xxx
since there are exactly
2
! of
such cycles.
Now take 2
x
. Again WLOG, suppose that 2
x
is the
good which is the least assigned to agent 2 in the set
when good 1
Ψ
x
is assigned to agent 1. The number of
allocations in this case is less than

2!
1
which is strictly lower than . This means there is
at least one cycle
3!
2
,Cn2
x with
23, ,n
and
Open Access TEL
P. DE LAMIRANDE
Open Access TEL
349
2
2
3,,
n
x
xx since there are exactly
of
such cycles.
3!
I can continue until 1t
 is a prime number. Let
belong to
1tt
,,,
x
xx
and suppose that agent
x
x
gets good the most often in the allocations be-
longing to when 1
PO
P
x
is allocated to agent 1,
2
x
to agent 1
2,,t
x
to agent . Then, by Corol-
lary 1, all agents who belong to
1t
tt
,1,

,

have
the same preferences over the set
,
1tt
,,
x
xxx
Step 2: Now, consider the general case where agents in
.
,1,,ss
12
,,,
ss s
have the same preferences over the set

,
x
xx xx


. But there is at least one cycle
,Cnx
 with

,,,1nss

12
,,
ss s
and
,,
x
xx xx

N
,,
ss
12
,
s
. By Proposition 7, all agents
belonging to must have the same preferences over
the set

,

x
xx xx


.
Step 3: I can use the same approach with the two re-
maining
x
. Doing so, I find that all agents belonging to
,1,,ss
have the same preferences over the set
12
,,,
ss s,
x
xx x

2,3, ,
.
I use this approach until I find that all agents belong-
ing to

23
,,,
have the same preferences over the
set
x
xx
.
Step 4: If Ψ is strictly lower than , this
means there is at least one cycle

1!n
,Cnx, Then, by
Proposition 7, all agents have the same preferences over
the set
23
,,,
x
xx
. Now, if steps 1 to 3 are done
once again with 2
x
and 3
x
instead of 1
x
, it can be
seen that all agents must have the same preferences over
the set
123
,,,,
x
xxx
.
Step 5: Now suppose that Ψ is equal to
1!
.
Suppose that there are two allocations and be-
longing to
1
a2
a
such that all agents get different goods,
there is no
12
such that aa
1, 2,,
Let the vector be the cycle of goods from to
. In other words, the good allocated to agent
.
1
ai
2
a i
in
the allocation goes to agent 1. Since there are
two allocations composing the same cycle
1
a i
,Cnx and
there are
1!
allocations, this means there is at least
one cycle and I obtain that all agents must have the same
preferences.
The only way to avoid the possibility of having a cycle
of
elements in the set is for all allocations
belonging to

PPO
, there is a good which is never allocated
to an agent.
Suppose this good is
x
and the agent never getting
x
in
PO P is
. Since all allocations belong to
PO P , all agents have the same preferences over the
set
I
and all agents belonging to
X
x
have the
same preferences over the set
X
.
If all agents have the same preferences, then
PO P
must contain all allocations. So, this means there is at
least one good belonging to

X
x
for which agent
and other agents must have different preferences.