Full text of DOI:10.1111/1468-0262.00166

Ž
.
Econometrica, Vol. 68, No. 6 November, 2000 , 1403᎐1433
STRATEGYPROOF ASSIGNMENT BY
HIERARCHICAL EXCHANGE
1
BY SZILVIA PAPAI
´
We give a characterization of the set of group-strategyproof, Pareto-optimal, and
reallocation-proof allocation rules for the assignment problem, where individuals are
assigned at most one indivisible object, without any medium of exchange. Although there
are no property rights in the model, the rules satisfying the above criteria imitate a trading
procedure with individual endowments, in which individuals exchange objects from their
hierarchically determined endowment sets in an iterative manner. In particular, these
assignment rules generalize Gale’s top trading cycle procedure, the classical rule for the
model in which each individual owns an indivisible good.
KEYWORDS: Strategyproof, housing market, indivisible goods.
1. INTRODUCTION
CONSIDER THE PROBLEM of allocating heterogeneous indivisible goods to individ-
uals so that each individual receives at most one good without any monetary
compensation. For example, a manager may want to allocate offices to employ-
ees, or tasks to workers, or a professor may intend to assign projects to students.
This study investigates whether there are some ‘‘nice’’ solutions to this pure
distribution assignment problem2 that take into account the individuals’ strate-
gic behavior. In particular, we are interested in strategyproof assignment rules,
rules that don’t permit successful manipulation of the outcome via misrepresen-
tation of privately known preferences.
Ž
.
An early paper by Hylland and Zeckhauser 1979 proposed a lottery mecha-
nism for assigning positions to individuals, in which the individuals ‘‘purchase’’
probability shares for obtaining positions. Although they were concerned with
eliciting honest preferences, their rule is not entirely immune to cheating. More
Ž
.
recently, Zhou 1990 proved Gale’s conjecture that, allowing for lotteries over
pure assignments, there do not exist allocation rules that satisfy symmetry,
Pareto-optimality, and strategyproofness. For the deterministic setting Svensson
Ž
.
1994 proposed a strategyproof and Pareto-optimal queue allocation procedure
that accommodates indifferences in the valuations of the indivisible objects. This
procedure is essentially what is known as a serial dictatorship,3 one in which the
individuals choose their favorite object among the ‘‘remaining’’ objects, accord-
1I am grateful to Ahmet Alkan for helpful discussions, as well as to the referees and the co-editor
for very useful suggestions. I am particularly indebted to Lars-Gunnar Svensson whose insightful
comments led to a significant improvement of the contents of this paper. Finally, I would also like to
thank the participants of the XIXth and XXth Bosphorus Workshops on Economic Design and of
the Fourth International Meeting for Social Choice and Welfare in Vancouver.
2An introduction to the results and literature on assignment problems with money can be found
Ž
.
in Roth and Sotomayor 1990 .
3
Ž
.
See, for example, Satterthwaite and Sonnenschein 1981 .
1403

1404
SZILVIA PAPAI
´
Ž
.
ing to a hierarchy of the individuals. A recent paper by Svensson 1999 showed
that the set of strategyproof, nonbossy, and neutral allocation rules is the set of
serial dictatorships, if every individual is assumed to be assigned an object.
Although there are no strategyproof and Pareto-optimal assignment rules that
treat individuals equally, the question arises whether there can be found more
flexible and less discriminating non-probabilistic rules than serial dictatorships.
The current paper answers this question by identifying a larger class of solu-
tions, to be called hierarchical exchange rules, which are strategyproof and
Pareto-optimal for the pure distribution assignment problem, when the number
of objects and the number of individuals are not necessarily the same. The main
result we present is that, even though there are no property rights in our model,
the assignment rules satisfying group-strategyproofness, Pareto-optimality, and
Ž
reallocation-proofness a criterion that rules out an obvious case of manipula-
.
tion via misrepresenting preferences and swapping objects ex post can be
described by an iterative procedure in which, at each stage, the individuals
exchange objects according to Gale’s top trading cycle algorithm, as if the
objects were owned by them. Thus, a striking feature of our result is that, for
this pure distribution problem with collective endowments, the assignment rules
satisfying our criteria imitate a market procedure with individual property rights.
To put it more sharply, one can draw the conclusion that if we want to efficiently
distribute heterogeneous indivisible goods, and nobody is to receive more than
Ž
.
one good, all we can and need to do is to assign individual property rights and
let people trade. Of course, since the objects need not be given as endowments
on a one-to-one basis, and the individuals receive at most one object, ‘‘property
rights’’ will have to be assigned in a hierarchical manner.
As indicated above, the hierarchical exchange rules can be regarded as
generalizations of Gale’s well-known top trading cycle procedure. This proce-
Ž
.
dure was first described by Shapley and Scarf 1974 , who introduced the
Ž
housing market, a model in which each individual owns an indivisible object a
house initially. Gale’s procedure gives a constructive way of finding a core
.
allocation of a housing market, which, subsequently, was shown to be unique by
Ž
.
Roth and Postlewaite 1977 , when indifferences among objects are not allowed.
Ž
.
Roth 1982 proved that the core solution, and thus the top trading cycle
Ž
.
Ž
.
procedure, is strategyproof. Furthermore, Ma 1994 and Svensson 1999 showed
that it is the only Pareto-optimal, individually rational, and strategyproof rule
for the housing market. Group-strategyproofness of the core solution was
proved by Bird 1984 and Moulin 1995 . Recently, Abdulkadiroglu and Sonmez
1998 proposed the ‘core from random endowments’ rule for the house alloca-
tion problem the pure distribution assignment problem with an equal number
of objects and individuals , a rule that selects the core of a random housing
Ž
.
Ž
.
˘
¨
Ž
.
Ž
.
market, and showed that it is equivalent to the random serial dictatorship rule.
Ž
.
Another related result is presented in Abdulkadiroglu and Sonmez 1999 who
˘
¨
investigated a mixed model of a house allocation and a housing market. They
propose a Pareto-optimal, individually rational, and strategyproof procedure for
their model, which accommodates an exogenous hierarchy, subject to existing

STRATEGYPROOF ASSIGNMENT
1405
property rights. The proposed class of procedures corresponds to a special class
of hierarchical exchange rules. The results of the present study and those of
Ž
.
Abdulkadiroglu and Sonmez 1999 were obtained independently.
˘
¨
2. HIERARCHICAL EXCHANGE RULESᎏAN INFORMAL DISCUSSION
First, we describe Gale’s top trading cycle procedure. Given a housing market,
let everyone point to the person who owns their favorite house. A top trading
cycle consists of individuals such that each individual in the cycle points to the
next individual. A single person may also constitute a cycle, by pointing to
herself, if her top choice is the house she owns. Note that there is at least one
top trading cycle, since there are a finite number of individuals. Give every
individual in each top trading cycle their top choice, and remove them from the
market with their assigned houses. Repeat the process until each individual
receives her assignment. The resulting allocation is unique if preferences are
strict, and it is the core allocation.
The allocation obtained by a hierarchical exchange rule can be described by
the following iterative procedure. Individuals have an initial individual ‘‘endow-
ment’’ of objects such that each object is exactly one individual’s endowment.
Otherwise, the distribution of initial endowments is arbitrary. It is important to
note that some individuals may not be endowed with any objects. Now apply the
top trading cycle procedure to this market with individual endowments. Notice
that individuals who don’t have endowments cannot be part of a top trading
cycle, since nobody points to them, and therefore they need not point. Given
that multiple endowments are allowed, after the individuals in top trading cycles
leave the market with their top-ranked object, unassigned objects in the initial
endowment sets of individuals who received their assignment may be left
behind. These objects are reassigned as endowments to individuals who are still
in the market, that is, they are ‘‘inherited’’ by individuals who have not yet
received their assignments. Furthermore, the objects in the initial endowment
sets of individuals who are still in the market remain the individual endowments
of these individuals. Thus, notice that each unassigned object is the endowment
of exactly one individual who is still in the market. Now apply the top trading
cycle procedure to this reduced market with the new endowments. Repeat this
procedure until every individual has her assignment or all the objects are
assigned. Since there exists at least one top trading cycle at every stage, this
procedure, similarly to Gale’s original procedure, leads to an allocation of the
objects in a finite number of steps. In particular, there are at most as many
stages as there are individuals or objects, whichever number is smaller, since at
each stage at least one person receives her assignment. Furthermore, for any
strict preferences of the individuals, the resulting allocation is unique.
A hierarchical exchange rule is determined by the initial endowments and the
hierarchical endowment inheritance at later stages. While the initial endowment
sets are given a priori, the hierarchical endowment inheritance may be endoge-
nous. In particular, the inheritance of endowments may depend on the assign-

1406
SZILVIA PAPAI
´
ments made at earlier stages. The exact ‘‘rules’’ of endowment inheritance will
be explained in Section 4, where we provide a formal definition of hierarchical
exchange rules, and in Section 5 we will illustrate the definition by examples. For
now, we would like to point out an intuitive and simple rule of endowment
inheritance, the Assurance Rule, which is always satisfied by hierarchical ex-
change rules. The Assurance Rule requires that individuals keep their endowed
objects until they leave the market, and thus endowments can only be inherited
from people who are exiting the market. We give an example below to illustrate
how a hierarchical exchange rule works, without specifying how the endowments
are determined at the noninitial stages of the iterative procedure.
Ž
EXAMPLE 1: A hierarchical exchange rule without specifying endowment inheri-
.
tance . We have six individuals, numbered from 1 to 6, and seven objects,
denoted a, . . . , g. Let the initial endowments be the following:
1
2
3
ᎏ
4
ᎏ
5
f
6
g
a, b, c d, e
Consider the preference profile below, which shows the individuals’ rankings
Ž
.
of objects from top to bottom :
R1 R2 R3 R4 R5 R6
d
c
c
f
.
.
.
e
g
.
.
.
e
d
c
.
.
.
.
.
.
.
.
.
b
.
.
.
The following figures illustrate the iterative procedure for this preference
profile. The arrows in the figures indicate who points to whom, based on the
endowments and the top choices of the individuals among the objects that are
still in the market at the corresponding stage.
Ž
.
At stage 1 Figure 1 there is one top trading cycle, which consists of
individuals 1 and 2. Thus, 1 is assigned object d, and 2 is assigned object c. Since
individuals 1 and 2 have received their assignments, objects a and b from 1 and
object e from 2 come up for inheritance. Without specifying the endowment
inheritance, let’s assume that 3 inherits b, 4 inherits a, and 5 inherits e.
FIGURE 1.ᎏStage 1.

STRATEGYPROOF ASSIGNMENT
1407
FIGURE 2.ᎏStage 2.
Then we have the following endowments at the beginning of stage 2:
3
4
5
6
b
a
e, f
g
Note that f and g remain 5’s and 6’s endowments, respectively, given the
Assurance Rule.
Ž
.
The top choices at stage 2 Figure 2 are f for 3, e for 4 and 5, and b for 6.
The only top trading cycle at this stage consists of 5, who is assigned e.
Assuming that 4 inherits f from 5, the Assurance Rule implies that we have the
following endowments at the beginning of stage 3:
3
4
6
b
a, f
g
Ž
.
At stage 3 Figure 3 there is a single top trading cycle that includes all three
remaining individuals. Thus, the assignments of 3, 4, and 6 are f, g, and b,
respectively, the respective top choices at this stage. The procedure stops here
since all the individuals have received their assignments. In sum, the assign-
ments are: 1yd, 2yc, 3yf, 4yg, 5ye, 6yb. Object a remains unassigned.
To complete our informal discussion of hierarchical exchange rules, let us
point out two special types of hierarchical exchange rules that are well studied
in the literature, namely, Gale’s top trading cycle rules and serial dictatorships.
For problems with no more objects than individuals, a hierarchical exchange
rule in which each individual has at most one object as initial endowment is just
Gale’s top trading cycle procedure applied to the corresponding housing market.4
On the other hand, serial dictatorships are characterized by a single individual
being endowed with all the unassigned objects at each round. For these
FIGURE 3.ᎏStage 3.
4 If there are more objects than individuals, then there is no hierarchical exchange rule that
imitates a housing market, since in this case at least one individual is endowed with more than one
object.

1408
SZILVIA PAPAI
´
assignment rules there is one top trading cycle at each stage, which consists of a
single person, the ‘‘dictator’’ for that stage, where the sequence of dictators is
determined for all preference profiles by an exogenously given hierarchy of the
individuals. These two types of rules, the ones that imitate housing markets and
the serial dictatorships, can be regarded as two opposite extremes within the
class of hierarchical exchange rules: one distributes priorities for objects among
the individuals entirely, so that there is no inheritance, while the other one gives
the priorities for all objects, at every stage, to one individual, so that all the
objects remaining in the market are inherited at each stage.
3. NOTATION AND DEFINITIONS
There are nG3 individuals and kG3 objects.5 We denote the set of individu-
als by N and the set of objects by K. Individuals are numbered from 1 to n, and
are denoted, in general, by i, j, h, l, while objects are denoted by a, b, c, d, etc.
Ž
.
An allocation xs x1, . . . , xn is a list of the assignments for the n individuals,
where xi gK or xi s0 for each i. If xi sa where agK, then individual i is
assigned object a in allocation x. If individual i is not assigned any object in x,
we write xi s0, where 0 is an artificial null object which can be ‘‘assigned’’ to
any number of individuals. An allocation x is feasible if none of the objects is
assigned to more than one individual.
An individual’s preferences over allocations are selfish and the preferences
over assignments are strict. Thus, individual i’s preferences, denoted by Ri, are
Ž
.
Ž
given by a reflexive for all a, aRi a , transitive for all a, b, c, aRi b and bRi c
.
Ž
.
Ž
imply aRi c , complete for all a, b, aRi b or bRi a , and antisymmetric for all
a, b, aRi b and bRi a imply asb binary relation over K. The associated strict
relation is denoted by Pi. We write aP b if aRi b and a/b. A preference profile
.
i
Ž
.
or simply a profile is an n-tuple of preferences, denoted by R. As usual, Ryi is
a profile of all the individuals except for i. Also, for M;N, let RM denote a
profile of all individuals in M, and let RyM denote a profile of all the
Ž
.
individuals in NyM. Let top Ri denote the top-ranked object according to Ri.
Ž
.
Furthermore, for all KЈ:K, let top Ri, KЈ sa if agKЈ, and for all bgKЈ,
aRi b. Besides Ri, i’s preferences will also be denoted by Ri, Ri, and Ri, with
corresponding strict relations Pi, Pi, and Pi, respectively.
˜
ˆ
˜
ˆ
An assignment rule f associates an allocation with each profile. Denoting the
set of profiles by R and the set of feasible allocations by X, an assignment rule
Ž .
is a function f: R¬X. Let fi R denote the assignment prescribed to individ-
Ž .
ual i by f at R, and let fM R denote the assignments prescribed to individuals
in M:N.
5Our characterization result also holds for the cases where ns2 or ks2. We rule them out in
order to ease the exposition, since these cases entail special relationships that don’t hold in general.

STRATEGYPROOF ASSIGNMENT
1409
4. HIERARCHICAL EXCHANGE RULESᎏA FORMAL DEFINITION
4.1. Inheritance Trees
First we define an inheritance tree ⌫a for each object agK, where ⌫a shows
Ž
.
ag K
how a is inherited. A list of inheritance trees ⌫s ⌫a
determines a hierarchi-
cal exchange rule f ⌫, which we will define afterwards.
Ž
.
An inheritance tree ⌫a s V, Q for object a is a rooted tree, where V is the set
Ž
.
of vertices, and Q;V=V is the set of arcs; if ¨i, ¨j gQ for ¨i, ¨j gV, then
ꢀ
4r
there is an arc from ¨i to ¨j. A Q-path from ¨1 to ¨r is a sequence ¨s ss1, where
Ž
.
rG2, such that for all ss1, . . . , ry1, ¨s, ¨sq1 gQ. The length of a Q-path is
the number of the connecting arcs.
Since ⌫a is a rooted tree, Q is acyclic: if there is a Q-path from ¨i to ¨j, then
Ž
.
¨j, ¨i fQ, i.e., there are no cycles. Furthermore, for all ¨1, ¨r gV there is at
ꢀ
4r
most one Q-path from ¨1 to ¨r. Thus, if ¨s ss1 is a Q-path, the distance of ¨r
Ž
.
from ¨1 is unambiguously defined by the length of the Q-path: d ¨1, ¨r sry1.
Finally, ⌫a has a unique root ¨0 gV, that is, ¨0 is the only vertex such that there
Ž
.
is no ¨ gV with ¨, ¨0 gQ.
The inheritance tree ⌫a shows how a is inherited as a function of the
assignments of the individuals who leave the market before a is inherited. Thus,
the vertices of ⌫a correspond to the individuals, and the arcs from a vertex are
labeled by the possible assignments of the individual who is represented by the
vertex. More precisely, ⌫a has the following properties.
Ž
.
Ž
.
Properties A.1 and A.2 concern the labeling of vertices:
(
)
Ž .
A.1 All ¨ertices are labeled by indi¨iduals: for all ¨ gV, L ¨ gN.
(
)
A.2 E¨ery ¨ertex of a Q-path represents a different indi¨idual: for all ¨i, ¨j gV
Ž . Ž .
such that there is a Q-path from ¨i to ¨j, we ha¨e L ¨i /L ¨j .
Ž
. Ž
.
Ž
.
Properties B.1 , B.2 , and B.3 concern the labeling of arcs:
(
)
ꢀ 4
Ž
.
Ž
.
B.1 All arcs are labeled by objects other than a: for all ¨i, ¨j gQ, H ¨i, ¨j g
Ky a .
(
)
B.2 E¨ery arc of a Q-path represents a different object: for all ¨1, ¨r gV such
ꢀ
4r
Ž
.
that there is a Q-path ¨s ss1 from ¨1 to ¨r , where rG3, we ha¨e H ¨1, ¨2 /
Ž
.
H ¨ry1, ¨r .
(
)
B.3 Arcs from the same ¨ertex represent different objects: for all ¨i, ¨j, ¨l gV
Ž
.
Ž
.
Ž
.
Ž
.
such that ¨i, ¨j gQ, ¨i, ¨l gQ and j/l, we ha¨e H ¨i, ¨j /H ¨i, ¨l .
Ž
. Ž
.
Ž
.
Properties C.1 , C.2 , and C.3 define the structure and dimensions of an
Ž . Ž .
inheritance tree as a function of the number of individuals n and objects k :
(
(
(
)
Ž . ꢀ 4
d ¨0, ¨ smy1, where msmin n, k .
C.1 max¨
g V
)
C.2 The number of arcs starting from ¨0 is ky1.
)
Ž
.
C.3 For all ¨ gV such that there is a Q-path from ¨0 to ¨, with d ¨0, ¨ sr-
my1, the number of arcs starting from ¨ is kyry1.

1410
SZILVIA PAPAI
´
The inheritance tree ⌫a and the properties listed above can be interpreted as
Ž
.
follows. Object a is individual L ¨0 ’s initial endowment; hence, this initial
endowment is independent of any assignments made. Depending on the assign-
Ž
.
ment of individual L ¨0 , the next individual to inherit a, or at least influence
its inheritance, is determined by following the arc labeled by the object that
Ž
.
L ¨0 is assigned. Continuing in this way we can determine all the potential
inheritances by following the appropriate arcs. Thus, we can interpret each
Ž
.
Q-path from the root as an inheritance path. Therefore, property A.2 insures
that there is no repetition in the hierarchy of inheritors, following any Q-path
Ž
.
Ž
.
Ž
.
from ¨0. Moreover, property A.2 combined with B.2 and B.3 insures that
there is no incompatibility among the required assignments for a particular
Ž
. Ž . Ž
.
Ž
.
inheritance. Properties B.2 , B.3 , C.2 , and C.3 together imply that for every
possible assignment of earlier potential owners there is a designated inheritor.
Note also that object a may not be inherited if it is assigned to somebody, and
Ž
.
thus none of the arcs are labeled a, as required by B.1 . Finally, it is clear that
there is no need to specify more than m individuals in any of the hierarchies
when there are more individuals than objects where m is the minimum of the
Ž
.
Ž
.
number of the individuals and the number of the objects , which is why C.1
Ž
.
says that each inheritance path starting from the root should have a length of
my1.
Let Ga denote the set of inheritance trees for a that satisfy all of the
properties listed above, and let Gs=
Ga. Then for each list of inheritance
ag K
trees ⌫gG, a hierarchical exchange rule f ⌫ associated with ⌫ is defined using
the endowments that we specify next. In general, we say that an assignment rule
f is a hierarchical exchange rule if there exists ⌫gG such that f is the
hierarchical exchange rule associated with ⌫ . In this case we will also say that ⌫
is an underlying inheritance tree list for f.
In what follows we describe how a hierarchical exchange rule f ⌫ associated
with ⌫ chooses the allocation at each preference profile.
4.2. Endowments
<
<
< <
For all M;N and L;K such that M s L /0, let
ꢀ
4
is a bijection
M , L
⌽
M , L s ␸M , L : M¬L : ␸
be the set of bijections from M to L. Here M refers to the set of individuals
who have already received their assignments, and L is the set of objects that
have already been assigned; furthermore, ␸
shows the assignments.
M, L
Now we can define the endowments E ⌫ for each individual igN, which is
i
based on the list of inheritance trees ⌫ . First, the initial endowments Ei⌫ л ,
Ž .
when MsLsл, are given by
E ⌫ л s agK : L ¨0 si in ⌫a .
Ž .
1
Ž
.
ꢀ
Ž
.
4
i

STRATEGYPROOF ASSIGNMENT
1411
Thus, each individual i’s initial endowment is just the set of objects for which
the root ¨0 in each of the corresponding inheritance trees designates i as the
first owner. Note that the initial endowments are determined by ⌫ a priori and
they do not depend on the preference profile.
6
The noninitial endowments E ⌫ M, L, ␸
for M;N, L;K such that
Ž
.
,
i
M, L
<
<
< <
M s L /0, ␸M, L g⌽M, L, and for each individual igNyM are given by
E ⌫ M, L, ␸
s agKyL: L ¨ si in ⌫a or
Ž .
2
Ž
.
Ž
.
ꢀ
i
M , L
0
ꢀ
4 r
there exists a Q-path ¨s
in ⌫a from ¨0 to ¨r
ss0
Ž
.
such that L ¨r si, and for all ss0, . . . , ry1,
Ž
.
Ž
.
we have L ¨s gM, H ¨s , ¨sq1 gL, and
Ž
Ž
..
Ž
.
␸
L ¨s sH ¨s , ¨sq1
.
4
M , L
Note that the definition of Ei⌫ implies that the hierarchical endowment inheri-
tance of each object a is determined in accordance with the interpretation of ⌫a
that we gave before. The definition also makes explicit that the noninitial
endowments depend only indirectly on the preference profile: namely the
endowments at any noninitial stage of the iterative procedure are a function of
Ž
.
only the set of individuals who already left the market M , the set of objects
Ž .
Ž
.
.
they are assigned L , and the assignments made ␸
M, L
⌫
ꢀ
Ž
.4ig NyM
partition the set
M, L
Finally, note that the endowments E M, L, ␸
i
⌫
i
Ž
.
of unassigned objects KyL: we have Dig NyM
␧
M, L, ␸
sKyL, and
M, L
Ž
⌫
for all i, jgNyM such that i/j, E ⌫ M, L, ␸
F Ej M, L, ␸
sл.
Ž
.
.
Thus, at any stage of the iterative procedure all Mth, Le unassigned objects are
i
M, L
distributed as endowments to individuals who are still in the market.
4.3. The Iterati¨e Procedure
Once the inheritance of the objects is defined, that is, once we have the
definition of the endowments E ⌫ based on ⌫gG, we apply an iterative
i
procedure, essentially the top trading cycle procedure, to these endowments in
order to find the assignments prescribed by the hierarchical exchange rule f ⌫
associated with ⌫ .
Fix a preference profile RgR. Then f ⌫ R can be defined by an iterative
Ž .
ꢀ
4
procedure with a finite number of stages, which is at most msmin n, k . For
each remaining individual i we give recursive definitions of the hierarchical
endowments Et i, R , the top choices Tt i, R , and the trading cycles St i, R ; then
Ž
.
Ž
.
Ž
.
Ž
.
Ž .
we define recursively the set of assigned indi¨iduals Wt R , the assignments of
these individuals fi⌫ R for all igWt R , and the set of assigned objects Ft R .
Ž .
Ž .
Ž .
7
ꢀ
4
All of these are indexed by the corresponding stage tg 1, . . . , m .
6 With a slight abuse of notation, we denote both the initial and noninitial endowments of i
by E ⌫.
i
7 We suppress the reference to ⌫ since it will be obvious to which hierarchical exchange rule we
are referring.

1412
SZILVIA PAPAI
´
Stage 1
Ž
.
Hierarchical Endowments Initial Endowments : For all igN, individual i’s
hierarchical endowment at stage 1 is just her initial endowment:
⌫
Ž .
3
Ž
.
Ž
.
E1 i, R sE л .
i
Ž
.
Note that E1 i, R is independent of the profile R, and we use this notation
for convenience.
Top Choices: Each individual igN ‘‘points’’ to the person who is endowed
with her favorite object, namely, her top choice at stage 1:
Ž
.
Ž
.
T1 i, R stop Ri .
Trading Cycles: Since the number of individuals and the number of objects are
finite, there is always at least one trading cycle, that is, a set of individuals who
form a cycle by ‘‘pointing’’ to the person endowed with their top choice. A
trading cycle, thus, consists of individuals who would like to exchange objects
from their initial endowments according to this cycle, so that each would receive
Ž
.
her top choice. Formally, i’s trading cycle at stage 1, S1 i, R , is comprised of the
Ž
.
set of individuals in her trading cycle at stage 1, if she is part of one, and S1 i, R
is defined to be the empty set otherwise. Thus, for all igN,
ꢀ
¡
4
j1 , . . . , jg
if there exist j1 , . . . , jg gN
such that for all ss1, . . . , g,
Ž
.
Ž .
T1 js , R gE1 jsq1 , R ,
~
Ž
.
S1 i, R s
where we let jgq1 sj1 , and isjs
for some ss1, . . . , g;
otherwise.
¢
л
Ž
.
ꢀ 4
Ž
.
Ž
.
Note that S1 i, R s i if T1 i, R gE1 i, R . That is, if i’s favorite object is in
her endowment, then i’s ‘‘trading cycle’’ consists of herself.
Individuals in a trading cycle are assigned their top choices and are removed
from the market with their assigned objects.
Ž .
ꢀ
Ž
.
4
Assigned Indi¨iduals: W1 R s i:S1 i, R /л .
⌫
Ž .
Ž .
Ž
.
Assignments: For each igW1 R , fi R sT1 i, R .
Ž .
ꢀ
Ž
.
Ž .4
Assigned Objects: F1 R s T1 i, R :igW1 R .
This procedure is repeated iteratively in the remaining reduced market.
Ž
ꢀ
4.
.
Having determined iteratively, for stages 1 to t tg 1, . . . , my1 , the sets of
assigned individuals W1 R , . . . , Wt R , their assignments T1 i, R , . . . , Tt i, R
Ž . Ž .
Ž
Ž
.
Ž . Ž .
for all i in W1 R , . . . , Wt R , respectively, and the set of assigned objects
Ž . Ž .
F1 R , . . . , Ft R , we will show next how the procedure works at stage tq1,
assuming that NyDtzs1Wz R /л and KyD zs1 Fz R /л. For each stage
t
Ž .
Ž .
tЈ
tЈ
tЈg 1, . . . , m , we use the notation W R sD zs1Wz R and FtЈ R s
ꢀ
4
Ž .
Ž .
Ž .
DtzЈs1 Fz R .
Ž .

STRATEGYPROOF ASSIGNMENT
1413
Stage tq1
Ž
.
Hierarchical Endowments Noninitial Endowments : First, let␸ tŽ R., F tŽ R. g
W
W
such that for all igW t R ,
Ž .
tŽ R., F tŽ R.
⌽
⌫
Ž .
Ž .
tŽ R., F tŽ R.
␸
i sfi R .
W
For all igNyW t R , the hierarchical endowments at stage tq1 are based on
Ž .
the set of assigned individuals in the first t stages, namely, MsW t R , the set
Ž .
tŽ .
of objects they are assigned, namely, LsF R , and the assignments made at
the first t stages, namely, ␸M, L s␸W tŽ R., F tŽ R.. That is, for all igNyW t R ,
Ž .
⌫
Etq1 i, R sE W t R , F R , ␸
t
Ž .
4
Ž
.
Ž
.
t Ž
.
Ž
.
i
W tŽ R., F Ž R.
.
Top Choices: Each remaining individual igNyW t R ‘‘points’’ to the person
Ž .
tŽ .
who is endowed with her favorite object among the remaining objects KyF R ,
namely, her top choice at stage tq1:
Ž
.
Ž
t Ž ..
Ttq1 i, R stop Ri , KyF R .
Trading Cycles: Again, there is at least one trading cycle, that is, a set of
individuals who form a cycle by ‘‘pointing’’ to the person endowed with their top
choice at stage tq1. A trading cycle, thus, consists of individuals in the reduced
market at stage tq1 that would like to exchange objects from their hierarchical
endowments at this stage according to this cycle. As a result of such a trade each
individual in the cycle would receive her top choice among the remaining
objects. Thus, for all igNyW t R ,
Ž .
j1 , . . . , jg
if there exist j1 , . . . , jg gNyW t
such that for all ss1, . . . , g,
¡
ꢀ
4
Ž .
R
Ž
.
Ž .
Ttq1 js , R gEtq1 jsq1 , R ,
~
Ž
.
Stq1 i, R s
where we let jgq1 sj1 , and isjs
for some ss1, . . . , g;
otherwise.
¢
л
Ž
.
ꢀ 4
Ž
.
Ž
.
Note that Stq1 i, R s i if Ttq1 i, R gEtq1 i, R .
Individuals in a trading cycle are assigned their top choices among the
remaining objects and are removed from the market with their assigned objects.
Ž .
ꢀ
Ž
.
4
Ž
Assigned Indi¨iduals: Wtq1 R s i: Stq1 i, R /л .
⌫
Ž .
Ž .
.
Assignments: For each igWtq1 R , fi R sTtq1 i, R .
Ž .
ꢀ
Ž
.
Ž .4
Assigned Objects: Ftq1 R s Ttq1 i, R : igWtq1 R .
This procedure is repeated iteratively until there are no individuals or objects
remaining in the market. Note that the procedure terminates in a finite number
of stages that is no more than m, since at every stage at least one individual is
assigned an object. More precisely, for every profile R there exists a last stage
ꢀ
4
t*Ž .
t*Ž .
t*g 1, . . . , m such that either W R sN or F R sK, and for all t-t*,
NyW t R /л and KyF R /л.
Ž .
tŽ .

1414
SZILVIA PAPAI
´
If there are more individuals than objects, then at the last stage t* we have
Ft* R sK, i.e., all the objects are assigned, and the remaining individuals do
Ž .
⌫
not receive any object: for all igNyW t* R , we have fi R s0.
In sum, for all ⌫gG, the hierarchical exchange rule f ⌫ associated with ⌫ is
defined as follows. For all RgR and for all igN,
Ž .
Ž .
Ž
.
Ž
.
ꢀ
4
Tt i, R
0
if jgWt R for some tg 1, . . . , m ;
fi⌫ R s
Ž
.
½
otherwise.
Note that f ⌫ is unambiguously defined, since for every profile R and
individual i there exists at most one stage t such that igWt R .
Ž .
5. ENDOWMENT INHERITANCE
The inheritance of endowments is the key feature of hierarchical exchange
rules that goes beyond Gale’s top trading cycle procedure, and thus makes this
class of rules a generalization of the top trading cycle algorithm, one which even
includes the seemingly unrelated serial dictatorships. This new feature, endow-
ment inheritance, is also the most complex feature of hierarchical exchange
rules, and thus it deserves further illustrations and remarks. We collect these in
this section. First, in Subsection 5.1, we focus on rules of inheritance that are
always satisfied by hierarchical exchange rules, such as the Assurance Rule
mentioned in Section 2. Then, in Subsection 5.2 we provide examples of
hierarchical exchange rules, complete with inheritance trees, and discuss some
special cases. In particular, we introduce the subclass of fixed endowment
hierarchical exchange rules for which the endowment inheritance is independent
of the assignments made at earlier stages. Finally, in Subsection 5.3 we will
make some remarks about the interpretation and uniqueness of the inheritance
tree lists underlying hierarchical exchange rules.
5.1. Inheritance Rules
Two important rules of inheritance that are always satisfied by hierarchical
exchange rules are the Assurance Rule, which pertains to inheritance across
stages, and the Twin Inheritance Rule, which pertains to inheritance across
preference profiles. These inheritance rules provide some intuition about en-
dowment inheritance, and they are extensively used in the proof of our charac-
terization theorem. We first give their formal definitions.
Ž
.
ASSURANCE RULE: Let igN and RgR such that agEt i, R for some
t-m and agK, and let igNyW t R . Then agEtq1 i, R .
TWIN INHERITANCE RULE: Let R, RgR such that, for some t-m,
Ž .
Ž
.
Ž .
i for all zFt, W R sW R ,
zŽ .
zŽ .
Ž . Ž .
tŽ . Ž .
ii for all jgW R , fj R sfj R ,
Ž .
tŽ R.
iii RW tŽ R. sRW
.
Then for all igNyW t R , Etq1 i, R sEtq1 i, R .
Ž .
Ž
.
Ž
.

STRATEGYPROOF ASSIGNMENT
1415
As already discussed in Section 2, the Assurance Rule ensures that once an
individual is endowed with an object, then this object remains the individual’s
endowment as long as she is in the market. We can see that the Assurance Rule
Ž .
2 implies that for all igNy
holds, given any ⌫gG, as follows. Firstly,
⌫
MЈ, Ei⌫ M, L, ␸
:E MЈ, LЈ, ␸
Ž
.
Ž
.
, where M;MЈ, L;LЈ, and for all
MЈ, LЈ
M, L
i
Ž .
i s␸
Ž .
igM, ␸
i . Then, since for any two stages t and tЈ such that
M, L
Ž .
MŽЈ, L.Ј
Ž .
tЈ
t-tЈ, W t R ;W R , the Assurance Rule follows from 4 .
The Twin Inheritance Rule says that if we have two profiles at which the
iterative procedures associated with the hierarchical exchange rule f ⌫ are the
Ž
Ž .
same up to stage t i.e., we have the same sets of assigned individuals i ,
Ž .
the same assignments ii , and the same preferences for the assigned individuals
iii at stages 1 to t then the endowments are the same at stage tq1 for these
two profiles. It follows immediately from 4 that the Twin Inheritance Rule is
Ž .
.
Ž .
satisfied by any hierarchical exchange rule f ⌫ associated with ⌫gG. In fact, 4
Ž .
reveals, in accordance with our interpretation of Ei⌫, that a stronger version of
the Twin Inheritance Rule also holds: for all R, R and t, t, if W t R sW R ,
Ž .
tŽ .
and for all jgW t R , fj R sfj R , then for all igNyW R , Etq1 i, R s
Ž . Ž .
Ž .
tŽ .
Ž
.
Ž
.
Etq1 i, R . We focus on the weaker version stated above, since it is sufficient for
use in the proofs, and it covers the most relevant cases when comparing
endowment inheritance between preference profiles.
5.2. Examples and Special Cases
First we give an example of a hierarchical exchange rule.
Ž
.
EXAMPLE 2: A hierarchical exchange rule with a list of inheritance trees . We
have five individuals and three objects, denoted a, b, c. The inheritance trees are
those shown in Figure 4.
Ž
.
The list of inheritance trees ⌫a, ⌫b, ⌫c determines the hierarchical exchange
rule f ⌫. We will illustrate the use of inheritance trees by showing how to find
Ž
the assignments for the preference profile below the prescribed assignments are
FIGURE 4.

1416
indicated by squares :
SZILVIA PAPAI
´
.
R1
c
R2 R3 R4
R5
b
b
c
a
b
a
a
c
b
a
b
c
a
c
ⅷ
Ž
.
ꢀ
4
Ž
.
ꢀ 4
Ž
.
Ž
.
Initial endowments: E1 1, R s a, b , E1 2, R s c , E1 3, R sE1 4, R s
Ž
.
E1 5, R sл. The initial endowments are found from the label of the root of
each tree.
ⅷ
Stage 1: The only trading cycle consists of 1 and 2, and the assignments are
1yc and 2yb.
ⅷ
Ž
.
Ž
.
Ž
.
ꢀ 4
Endowments at Stage 2: E2 3, R sE1 4, R sл, E1 5, R s a . The only
remaining object is a, which comes up for inheritance since individual 1 has left
the market. Object a is inherited by individual 5, as can be seen by following the
Ž
.
right-hand-side branch of ⌫a, labeled c 1yc , and then, given that 2 has also
Ž
.
left, following the second arc 2yb .
ⅷ
Stage 2: Individual 5 receives a.
Note that at the displayed preference profile both 1 and 2 left the market
after stage 1 and thus individual 2 did not inherit object a; instead, a was given
to 5, as an endowment, immediately. On the other hand, it is clear that not all
the assignments made at an earlier stage will necessarily affect the inheritance
of a particular object. For instance, if we change individual 2’s preferences so
that her top-ranked object becomes a, then 1 and 2 would trade objects a and c,
and object b would be inherited. Then, following the right-hand-side branch in
Ž
.
⌫
1yc we get to 4, who is still in the market. Thus, 4 inherits b in this case,
b
regardless of what 2’s assignment is.
A special class of hierarchical exchange rules, known as sequential dictator-
Ž
Ž
.
Ž
..
ships see, for example, Ehlers and Klaus 1999 and Papai 2000 are similar to
´
serial dictatorships, but allow the choice of the dictator at any noninitial stage
to depend on the assignments chosen by the dictators at earlier stages. In order
to further illustrate the use of inheritance trees, we provide an example of a
sequential dictatorship below.
EXAMPLE 3: A sequential dictatorship. There are three individuals and four
objects. The inheritance trees in Figure 5 define a sequential dictatorship where
the first dictator is individual 1; if 1 chooses object a, then the second dictator is
individual 2, and otherwise the second dictator is individual 3. In other words, if
Ž
.
1 receives a, the hierarchy is 1, 2, 3 , and if 1 receives an object other than a,
then the hierarchy is 1, 3, 2 .
Ž
.
As illustrated by Example 2 and Example 3, the inheritance trees allow for the
Ž
inheritance to depend on the assignments of the individuals who own or are at

STRATEGYPROOF ASSIGNMENT
1417
FIGURE 5.
.
least ‘‘qualified’’ to own the object at prior stages. This flexibility may be useful
in some situations. For example, one may want to use the sequential dictatorship
in Example 3 in a situation where 1 is senior to 3 and 3 is senior to 2, but 2 is
connected to object a so that if 1 likes a then she promotes 2 to a more senior
position than 3 has. As another example, one may consider a situation in which
property rights are secondary to seniority, and it is desirable to give priority over
Ž
.
some remaining objects, as a compensation, to less senior people, whose
objects were chosen by their more senior peers.
In situations where it is not desirable or necessary to base the inheritance on
the choices of the more favored or more senior individuals, it is natural to use
the simpler ‘‘exogenous’’ inheritance rules that only depend on who has left the
market and which objects have already been assigned, but not on the assign-
ments themselves. We refer to this subclass of hierarchical exchange rules as
fixed endowment hierarchical exchange rules.
A fixed endowment hierarchical exchange rule can formally be defined by the
following restriction on the inheritance trees. We call ⌫gG a fixed endowment
Ž
.
Ž
.
inheritance tree list if for all agK, for all ¨, ¨ЈgV such that d ¨0, ¨ sd ¨0, ¨Ј ,
Ž .
Ž .
we have L ¨ sL ¨Ј in ⌫a. An assignment rule f is a fixed endowment
hierarchical exchange rule if there exists a fixed endowment inheritance tree list
⌫gG such that f is the hierarchical exchange rule associated with ⌫ .
In a fixed endowment inheritance tree list, for each inheritance tree, vertices
that have the same distance from the root must be labeled by the same
individual. This means that the inheritance is independent of the assignments
made at earlier stages, and that the endowments Ei⌫ are only a function of the
set of assigned individuals M and the set of assigned objects L. Accordingly,
each inheritance tree reduces to a permutation of m individuals, i.e., to a
Ž
Ž
.
Ž
.
Ž
..
Ž
.
hierarchy L ¨0 , L ¨1 , . . . , L ¨my1 , where d ¨0, ¨s ss for all ss1, . . . , m
y1. Therefore, a fixed endowment inheritance tree list can be replaced by a
single endowment inheritance table consisting of a hierarchy of endowment
inheritance for each object, as illustrated by the next example.

1418
SZILVIA PAPAI
´
Ž
EXAMPLE 4: A fixed endowment hierarchical exchange rule with an endowment
.
inheritance table . Consider the following endowment inheritance table:
a
b
c
d
e
f
g
1
2
4
3
5
6
1
3
2
4
5
6
1
2
4
5
6
3
2
1
3
6
5
4
2
5
3
4
1
6
5
4
6
1
2
3
6
2
3
4
5
1
We have six individuals and seven objects, denoted a, . . . , g. Each object
corresponds to a column. Moreover, since ms6, each column is a permutation
of the set of individuals, indicating the hierarchy of inheritance for the corre-
sponding object.
This endowment inheritance table generates the endowments given in Exam-
ple 1, and thus we will demonstrate the use of the table for the preference
profile specified in Example 1.
ⅷ
Ž
.
ꢀ 4
ꢀ
4
Ž
.
ꢀ
4
Ž
.
Ž
.
Initial endowments: E1 1, R s a, b, c , E1 2, R s d, e , E1 3, R sE1 4, R
Ž
.
ꢀ 4
Ž
.
sл, E1 5, R s f , E1 6, R s g . The initial endowments are given by the first
row of the table.
ⅷ
Ž
.
ꢀ 4
Ž
.
ꢀ 4
Ž
.
ꢀ
4
Endowments at Stage 2: E2 3, R s b , E2 4, R s a , E2 5, R s e, f ,
Ž
.
ꢀ 4
E2 6, R s g . Object a becomes 4’s endowment, since individual 4 is the next
Ž
highest ranked person after 1 in the first column of the table corresponding to
.
object a who is still in the market. Object b becomes 3’s endowment, since 3 is
Ž
.
listed below 1 in the second column corresponding to object b . Similarly, e is
inherited from 2 by 5.
Endowments at Stage 3: E3 3, R s b , E3 4, R s a, f , E3 6, R s g .
Individual 4 inherits f from 5, as seen from the penultimate column of the table.
ⅷ
Ž
.
ꢀ 4
Ž
.
ꢀ
4
Ž
.
ꢀ 4
Note that an arbitrary list of permutations of m individuals, that is, any
endowment inheritance table, defines a fixed endowment hierarchical exchange
rule, which follows from the definition of hierarchical exchange rules.
The two special classes of hierarchical exchange rules mentioned earlier,
serial dictatorships and Gale’s top trading cycle procedure applied to an arbi-
Ž
.
trary housing market when kFn , are both subclasses of the set of fixed
endowment inheritance rules. Thus, for example, the endowment inheritance
table associated with the hierarchical exchange rule that corresponds to
Ž
.
the serial dictatorship with the exogenously given hierarchy 1, . . . , m is the
following:
a
b
c
. . .
1
2
1
2
1
2
. . .
. . .
.
.
.
.
.
.
m
m
m
. . .

STRATEGYPROOF ASSIGNMENT
1419
Now consider the inheritance table:
a
1
b
2
c
3
d
4
. . .
. . .
This table completely determines a top trading cycle rule, given that if each
individual is endowed with no more than one object, i.e., if we have a housing
market, then there is no endowment inheritance.
It is interesting to note that the solution proposed by Abdulkadiroglu and
˘
Ž
.
Sonmez 1999 to a problem that allows for initial property rights of houses can
¨
be interpreted as a combination of these two extreme procedures, serial dicta-
torships and housing markets, and hence they are also a special subset of the set
of fixed endowment hierarchical exchange rules. In particular, existing tenants
are endowed with their own house, and the rest of the houses are the endow-
ment of a single person at every stage, according to an a priori given hierarchy
of seniority. Thus, the inheritance tables corresponding to the proposed assign-
ment rules are restricted to have the same hierarchy of endowment inheritance
Ž
.
for each object as in a serial dictatorship , except for the objects that are
initially owned, for which this hierarchy is modified by lifting the owner to the
Ž
.
top of the hierarchy as in a housing market .
5.3. On the Interpretation and Uniqueness of Inheritance Trees
Inheritance tables have a somewhat different interpretation from that of
inheritance trees, which follows logically from the nature of the collapse of an
inheritance tree to a single inheritance hierarchy. Individuals associated with
vertices in a path of an inheritance tree need not inherit the object in question
at any preference profile; it may very well be the case that an individual
necessarily leaves the market by the time it would be her turn to inherit the
object. Nonetheless, the assignment of such an individual may affect the choice
of the person inheriting the object. Hence, the individuals in any particular path
of an inheritance tree are a mixture of potential inheritors of the object
Ž
potential in the sense that actual inheritance depends on the preference
.
profile and of individuals who don’t inherit themselves at any preference profile
but whose assignments may influence the identity of subsequent individuals in
that path, just as earlier inheritors’ assignments may have an effect.
By contrast, individuals listed in an endowment inheritance table as part of
the hierarchy for a particular object may only be interpreted as potential
inheritors, since the assignments themselves cannot influence the hierarchy of
Ž
inheritance for fixed endowment hierarchical exchange rules which is why a
.
single inheritance table suffices to identify such an assignment rule . This
difference in interpretation sheds some light on the complexity of non-fixed-en-
dowment hierarchical exchange rules; indeed, the inheritance trees are decep-
tively simple. Since it is tempting to interpret the inheritance trees simply as a
collection of hierarchies of potential inheritors, which allows the hierarchy to

1420
SZILVIA PAPAI
´
vary with the assignments of earlier inheritors, one may easily lose sight of the
fact that the identity of an inheritor of an object may be influenced by not only
the assignments of earlier owners of the object but also by the assignments of all
the individuals who trade with these earlier owners.
The interpretation of inheritance trees and tables leads naturally to the issue
of uniqueness. Can we specify an inheritance tree list that includes some
individual whose position in all the trees implies that she never inherits a
particular object for which she is listed, and whose assignment never affects the
subsequent hierarchy for this object? If so, deleting the vertex associated with
Ž
.
such an individual and the arcs starting from it from the inheritance tree of the
object in question does not yield a different hierarchical exchange rule, or leave
the assignment rule unspecified. The answer is yes, which can easily be seen
from a housing-market-type inheritance table, for which specifying more than
the first row is redundant. Indeed, the underlying list of inheritance trees ⌫gG
is typically not unique for a hierarchical exchange rule. It may contain some
redundant information, so that another list ⌫ ЈgG may exist that leads to the
same allocation at every preference profile as ⌫ does.8 That is, we may have
⌫
Ј
f ⌫ R sf R for all RgR. It is important to note, however, that the iterative
Ž .
Ž .
procedures for f ⌫ and f ⌫ are identical at every profile. Thus, for a given
Ј
hierarchical exchange rule f, it is only the underlying inheritance tree list
describing endowment inheritance that may not be unique, as opposed to the
iterative procedure, which is necessarily unique, since the realized endowment
inheritance is the same for all underlying inheritance tree lists for f.
Determining which parts of a particular inheritance tree list, if any, are
redundant may not be a trivial task. The only exception to this, in general, is the
label of the root of each tree, i.e., the initial endowments, which are never
redundant. The simple inheritance tree list in Example 2 can be used to
demonstrate the difficulties. Since object c is 2’s initial endowment, individual 1
can only receive c if 2 leaves the market at the same stage as 1, given that, by
the Assurance Rule, 2 keeps c as long as she is in the market. Thus, the
specification of ⌫a implies that 2 cannot inherit a from 1 at any profile.
Moreover, 2 does not appear in ⌫b, and thus 2’s only endowment is object c at
Ž
all the profiles. Therefore, 2 exits the market with object c by taking it or
.
exchanging it , which reveals that specifying more than 2’s initial ownership in
⌫c is redundant.
The detection of equivalences is not intractable, as it turns out. We can find
the equivalence classes by using the ‘‘canonical form’’ of hierarchical exchange
rules, or more precisely, their canonical inheritance tree lists. To determine if
two inheritance tree lists are equivalent in the sense that they both define the
8 This type of redundancy is not to be confused with the trivial redundancies that follow from
Ž
.
indicating the last object or individual. Namely, when n)k as in Example 2 , the labeling of the
Ž
.
arcs leading to the terminal vertices can be omitted. Similarly, when nFk as in Example 3 ,
labeling the terminal vertices by the last individual, and thus indicating the terminal arcs, is not
necessary. We defined the dimensions and labeling of inheritance trees uniformly for the sake of
simplicity.

STRATEGYPROOF ASSIGNMENT
1421
FIGURE 6.
same hierarchical exchange rule, we need only construct the canonical form for
each and check if these are the same.
Here is how one can construct the canonical form of a hierarchical exchange
rule.9 Fix a vertex in ⌫a, and assume that the labels of all the vertices preceding
this vertex are already determined, given an appropriate labeling of the arcs.
Consider a preference profile with the following specifications. For each individ-
Ž
ual in the path preceding this vertex the ‘‘preceding individuals,’’ which may be
.
the empty set , let the top choice of the individual be the object that labels the
corresponding arc in ⌫a. For all the other individuals, let the top choice be
object a. It can be checked that any hierarchical exchange rule assigns the
top-ranked object to each ‘‘preceding individual’’ at this profile, and thus some
individual among the remaining ones receives a. Label the vertex by this
individual. We can construct the entire tree in this manner, as well as the other
trees. Without going into details of the construction, we provide the canonical
inheritance tree list for Example 2.
EXAMPLE 5: The canonical form of the hierarchical exchange rule specified in
Ž
.
Example 2 Figure 6 . Note that ⌫c in the canonical form is completely different
from the original ⌫c, with the exception of the label of the root, indicating that
the rest of the tree is redundant, in accordance with our discussion above.
It is natural to ask why we focus on the canonical form in each equivalence
class of inheritance tree lists. Without providing a formal definition, we may
remark that the canonical form of a hierarchical exchange rule is the only
underlying inheritance tree list that is internally consistent, in the sense that the
redundant parts reflect inheritances that would yield, if ever realized, assign-
ments resulting from other nonredundant parts of the inheritance trees via
trading. Interestingly, this also implies that the canonical form of an inheritance
table is typically not a fixed endowment inheritance tree list, and therefore a
single specification of a hierarchical exchange rule may not reveal immediately
9
A formal description of the construction of the canonical form is given in Step 1 of the necessity
proof in the Appendix.

1422
SZILVIA PAPAI
´
whether it is a fixed endowment hierarchical exchange rule. One may gain a
better understanding of the internal consistency property of the canonical form,
besides inspecting Example 5, by constructing the canonical form of a housing-
market-type hierarchical exchange rule.
Finally, it is useful to remark that specifying every detail of all the inheritance
Ž
.
trees with the exception of the trivial redundancies mentioned in footnote 8 is
necessary in some cases: for example, every sequential and serial dictatorship is
uniquely determined by its canonical form.
6. THE CRITERIA FOR ASSIGNMENT RULES
The main property we require of assignment rules is group-strategyproofness. It
ensures that no subset of the individuals can gain by reporting false preferences.
More precisely, by colluding and jointly misrepresenting preferences, no individ-
ual among the deviators can be made better off without hurting at least one
other deviator.
DEFINITION 1: An assignment rule f is group-strategyproof if for all R, there
˜
˜
Ž
.
Ž .
do not exist M:N and RM such that for all igM, fi RM , RyM Ri fi R and
˜
Ž
.
Ž .
for some jgM, fj RM , RyM Pj fj R .
Group-strategyproofness is a stricter requirement than strategyproofness: the
latter rules out individual manipulations only. In the current context, group-
Ž
strategyproofness is equivalent to strategyproofness and nonbossiness Sat-
Ž
..
terthwaite and Sonnenschein 1981 . Nonbossiness, a criterion frequently used
in the context of strategyproof allocation, ensures that individuals cannot be
bossy, that is, change the assignment for others, by reporting different prefer-
ences, without changing their own. Since it will be convenient in the following to
split up group-strategyproofness into these two properties, we prove this equiva-
lence below.
DEFINITION 2: An assignment rule f is strategyproof if for all R, igN, and
˜
˜
Ž .
Ž
.
Ri, fi R Ri fi Ri, Ryi .
If f is not strategyproof then it is manipulable. Then there exist R, igN, and
˜
˜
Ž
.
Ž .
Ri such that fi Ri, Ryi Pi fi R . We then say that individual i can manipulate at
˜
R ¨ia Ri.
˜
DEFINITION 3: An assignment rule f is nonbossy if for all R, igN, and Ri,
˜
˜
Ž . .
Ž
.
Ž .
Ž
fi R sfi Ri, Ryi implies f R sf Ri, Ryi .
We also need the following definitions. For an assignment rule f and for all
Ž .
Ž
.
ꢀ
4
igN and Ryi , let oi Ryi s a: there exists Ri such that fi R sa be individ-
Ž
.
ual i’s option set at Ryi. That is, oi Ryi is the set of objects that individual i can
get as an assignment by changing her messages when the other individuals
report Ryi. A push-up of a preference ordering for an object a is another

STRATEGYPROOF ASSIGNMENT
1423
preference ordering under which each object that is ranked above a is also
˜
ranked above a in the original preference ordering. That is, Ri is a push-up of
˜
Ri for a if for all bgK, bPi a implies bPi a. Note that if f is strategyproof, then
10
Ž .
Ž
Ž
..
Ž .
for all igN and R, fi R stop Ri, oi Ryi ; otherwise i can manipulate at R.
˜
Thus, if Ri is a push-up of Ri for fi R then strategyproofness implies that
˜
Ž .
Ž
.
fi R sfi Ri, Ryi . Furthermore, if f is nonbossy as well, then we also have
˜
Ž
.
Ž .
f Ri, Ryi sf R .
LEMMA 1: An assignment rule is group-strategyproof if and only if it is strate-
gyproof and nonbossy.11
PROOF: It is obvious that group-strategyproofness implies strategyproof-
ness and nonbossiness. We will prove the converse. Let f be strategyproof
˜
and nonbossy. Let M : N, R, and RM be such that for all i g M,
˜
ˆ
Ž
.
Ž .
ꢀ
4
fi RM , RyM Ri fi R . Let Ms 1, . . . , g . For all igM, let Ri preserve the
ˆ
˜
Ž
Ž
.
˜
Ž
.
ordering of Ri, except, let top Ri sfi RM , RyM . Strategyproofness implies
ˆ
˜
Ž .
Ž
.
Ž .
.
Ž
.
.
Ž
.
Ž .
that f1 R1, Ry1 sf1 R , since f1 RM , RyM fo1 Ry1 if f1 RM , RyM P1 f1 R ,
˜
ˆ
Ž
.
Ž .
Ž
and otherwise f1 RM , RyM sf1 R . Then f R1, Ry1 sf R , by nonbossiness.
ˆ
Ž
.
s
Repeating the same argument for individuals 2, . . . , g, we get f RM , RyM
ˆ
˜
˜
Ž .
Ž
.
f R . Now note that for all igM, Ri is a push-up of Ri, for fi RM , RyM , so
ˆ
˜
Ž
.
Ž
.
that f RM , RyM sf RM , RyM , by strategyproofness and nonbossiness. Thus,
˜
Ž
.
Ž .
f RM , RyM sf R , which implies that f is group-strategyproof.
Q.E.D.
Pareto-optimality, another criterion we impose on assignment rules, ensures
the efficiency of the allocation at every profile.
DEFINITION 4: An assignment rule f is Pareto-optimal if for all R, there does
Ž .
not exist a feasible allocation x such that for all igN, xi Ri fi R and for some
Ž .
jgN, xj Pj fj R .
Group-strategyproofness and Pareto-optimality still allow for an obvious form
of manipulation for assignment problems, namely, where individuals report
preferences dishonestly, and exchange their assigned objects.12 Our last crite-
rion, reallocation-proofness, rules out the possibility that two individuals can gain
by jointly manipulating the outcome and swapping objects ex post, when the
collusion is self-enforcing in the sense that neither party can lose by reporting
false preferences in case the other party does not adhere to the agreement and
reports honestly. Consequently, reallocation-proofness rules out the most likely
10 The definition of an option set and the related observation about strategyproofness follow
Ž
.
Barbera 1983 .
`
11
Ž
.
See Barbera and Jackson 1995 for a related result.
See Moulin 1995 for a discussion of manipulation via swapping objects ex ante and ex post in
the context of the housing market model.
`
12
Ž
.

1424
SZILVIA PAPAI
´
form of cheating via reallocating, since two individuals would find it the easiest
to collude, especially if they stood no risk by doing so.13
DEFINITION 5: An assignment rule f is manipulable through reallocation if
˜ ˜
˜ ˜
Ž
.
Ž .
there exist R, i, j g N and Ri, Rj such that fj Ri, Rj, Ryi, j Ri fi R ,
˜ ˜
˜
˜ ˜
Ž
.
Ž .
Ž .
Ž
.
Ž
.
fi Ri, Rj, Ryi, j Pj fj R , and fh R sfh Rh, Ryh /fh Ri, Rj, Ryi, j for hsi, j.
An assignment rule is reallocation-proof if it is not manipulable through reallo-
cation.14
We give an example of an assignment rule which is group-strategyproof,
Pareto-optimal, and not reallocation-proof, in order to demonstrate that reallo-
cation-proofness is independent of the other properties.15 For simplicity, the
example is given for three individuals and three objects, but similar examples
can be constructed for arbitrary numbers of individuals and objects.
EXAMPLE 6: A group-strategyproof, Pareto-optimal, and not reallocation-proof
assignment rule. When individual 3 prefers object b to a, let the allocation be
determined by the following endowment inheritance table, as if the assignment
rule were a fixed endowment hierarchical exchange rule:
a
b
c
1
3
2
2
3
1
2
1
3
Similarly, when individual 3 prefers object a to b, let the allocation be
determined by the inheritance table:
a
b
c
1
3
2
2
3
1
1
2
3
Note that this assignment rule is not a hierarchical exchange rule since the
initial endowments are not given a priori: the initial endowment of object c
depends on individual 3’s preferences, who is the last one to inherit c at all the
profiles.
13 Requiring reallocation-proofness in the stronger sense that two individuals cannot gain, in any
case, by swapping objects ex post, after reporting dishonestly, leads to an impossibility result, if we
require group-strategyproofness and Pareto-optimality as well.
14 For our characterization result we can weaken this criterion by replacing fj Ri, Rj,
Ryi , j Ri fi
˜ ˜
Ž
˜ ˜
. Ž .
R by fj Ri, Rj, Ryi, j sfi R , as group-strategyproofness and Pareto-optimality imply
.
Ž
Ž .
that it is not possible that both parties strictly gain from exchanging their objects after manipulating
the outcome.
15 This independence does not hold in the special cases: if ks2, group-strategyproofness implies
reallocation-proofness, and if ns2, Pareto-optimality implies reallocation-proofness.

STRATEGYPROOF ASSIGNMENT
1425
It can be verified that this assignment rule is group-strategyproof and Pareto-
optimal. In particular, individual 3 is not bossy, since by switching from one
inheritance table to the other the allocation remains unchanged, or 3’s assign-
ment changes from b to a or vice versa. Moreover, the profiles displayed below
Ž
demonstrate that it does not satisfy reallocation-proofness the allocations
prescribed by the assignment rule are indicated by squares .
.
˜
R1
R1
R2
R3
R2
R3
a
c
b
c
a
b
c
b
a
c
a
b
c
a
b
c
b
a
˜
˜
R1
R2
R3
˜
R1
a
R2
c
R3
c
a
b
c
a
b
c
a
b
c
c
b
a
b
a
b
Given R as the true preference profile, neither 1 nor 3 can change the
˜
˜
allocation alone by dishonestly reporting R1 and R3, respectively. Thus, the
allocation at profile R1, R2 , R3 reveals that individuals 1 and 3 can manipulate
through reallocation.
˜
˜
.
Ž
It is easy to see that the other criteria for assignment rules are independent.
An imposed assignment rule, one that prescribes the same allocation to every
profile, is group-strategyproof and reallocation-proof, but not Pareto-optimal.
Furthermore, consider an assignment rule that acts as a serial dictatorship with
Ž
.
hierarchy 1, 2, 3, 4, . . . , n at all the profiles where individual 1 prefers object a
Ž
.
to b, and otherwise acts as a serial dictatorship with hierarchy 1, 3, 2, 4, . . . , n .
This assignment rule is clearly Pareto-optimal. It is also reallocation-proof, since
no two individuals can change each other’s assignments at any profile. Group-
strategyproofness is violated by this rule, however, since individual 1 is bossy.
7. THE CHARACTERIZATION RESULT
THEOREM: An assignment rule is group-strategyproof, Pareto-optimal, and real-
location-proof if and only if it is a hierarchical exchange rule.
The proof of the theorem is presented in the Appendix.
It is perhaps not obvious to the reader why the hierarchical exchange rules
satisfy our criteria, so let us provide a brief explanation. The intuition behind
the strategyproofness of hierarchical exchange rules is that an individual, by
deviating alone, cannot obtain objects that leave the market before she does.
However, objects that are preferred by an individual to her assignment at a

1426
SZILVIA PAPAI
´
given profile are assigned at a stage prior to this individual’s departure. This
feature is also the key to understanding the Pareto-optimality of these rules.
Clearly, individual i does not envy individual j who leaves at the same stage or
later than i does, where we say that a person envies someone if the envied
individual is assigned an object she prefers to her assignment. Thus, for any
given profile, we can arrange the individuals in a hierarchy in which nobody
envies another person who comes lower in the hierarchy, which means that the
rule is Pareto-optimal.
We remark here that strategyproofness is ensured by any endowment inheri-
tance that satisfies the Assurance Rule and the Twin Inheritance Rule. By
contrast, nonbossiness does not follow from these two inheritance rules alone; it
is only implied by further attributes of the endowment inheritance. It can easily
be seen that individual i cannot be bossy with individual j if j leaves the market
before i or simultaneously with i. It is less transparent that i is not bossy with j
when j leaves after i. In order to understand nonbossiness in this case, one
needs to take a closer look at the endowment inheritance based on inheritance
trees. In particular, in the proof of nonbossiness we appeal to the following
attribute of endowment inheritance: individual j, who is endowed with an object
at some stage at a particular profile, will eventually inherit this object, if she
cares about it, at any other profile where all individuals who leave the market
before j at the original profile get the same assignments. This, although not in a
straightforward manner, implies that no individual who leaves the market before
j can be bossy with j.
Finally, reallocation-proofness can be seen as follows. If two individuals can
manipulate through reallocation, then they can mutually affect each other’s
assignments at the manipulated profile. Given that a hierarchical exchange rule
is group-strategyproof, this can be shown to imply that the two individuals are in
the same trading cycle at that profile. In this case, however, they should be able
to trade, which is a contradiction.
It is somewhat more difficult to explain why these are the only rules that
satisfy our criteria. The proof is structured as follows. As a preliminary result for
this necessity proof, we first show that the required properties of assignment
rules imply that if individual i envies j, then she cannot affect j’s assignment.
This result is the key to establishing that the objects are endowments, or in
other words, that every object can be commanded at all the preference profiles
by some individual. We start the necessity proof by constructing the canonical
inheritance trees for a particular assignment rule that satisfies our criteria
Ž
.
Step 1 . Then we establish that the assignments of individuals who receive their
assignments at the first stage of the hierarchical exchange rule defined by the
constructed canonical form in Step 1 are as prescribed by this hierarchical
Ž
.
exchange rule Step 2 . This is the basis step for the induction argument that we
Ž
.
use. The inductive step Step 3 completes the proof with a similar argument to
that of Step 2, by demonstrating that the assignments at any later stage are also
made in accordance with this hierarchical exchange rule.

STRATEGYPROOF ASSIGNMENT
8. CONCLUSION
1427
In this paper we identified a class of rules for the pure distribution assignment
problem that are group-strategyproof, Pareto-optimal, and reallocation-proof.
These assignment rules can be interpreted as trading rules with individual
property rights over the indivisible goods, and they can be conveniently decen-
tralized in practical use. In a decentralized administration, in which at each
stage the remaining individuals are asked to identify their favorite among the
remaining objects, the incentive properties are retained, and typically very little
Ž
.
information about the preferences is used see Example 1 . Furthermore, the
class of hierarchical exchange rules is ‘‘rich’’ in the sense that it allows for
substantially more flexibility than serial dictatorships. In particular, these assign-
ment rules can accommodate any existing property rights or naturally arising
hierarchies of endowment inheritance. Moreover, these are the only rules that
satisfy group-strategyproofness, Pareto-optimality, and reallocation-proofness.
An interesting question for further research is whether similar results can be
obtained if there is no restriction on the number of objects received by an
individual. Under appropriate assumptions on preferences, there may exist
simple trading rules with desirable properties for this related problem as well.
Faculdade de Economia, Uni¨ersidade No¨a de Lisboa, Tra¨essa Este¨ao Pinto,
˜
P-1099-032 Lisboa, Portugal; spapai@fe.unl.pt
Manuscript recei¨ed January, 1999; final re¨ision recei¨ed October, 1999.
APPENDIX: PROOF OF THE THEOREM
PRELIMINARIES
An individual affects another individual at a given profile if she can change the other individual’s
Ž
.
assignment by changing her preferences. Individual i affects j at R with respect to f , if there exists
˜
˜
Ž
.
Ž
.
Ž .
Ri such that fj R /fj Ri, Ryi , where i/j. We write then iA R j.
Ž
.
Ž
.
Ž .
Individual j en¨ies i at R with respect to f , if fi R Pj fj R . We denote this relationship by
Ž
.
Ž .
V
R . That is, if j envies i at R, we write jV R i.
The following terminology and notation are given with respect to a particular hierarchical
Ž .
zŽ zŽ
Ž
.
t
.
.
exchange rule f. Profiles R and R are equi¨alent up to stage t if, i for all zFt, W R sW R ,
ii for all jgW t R , fj R sfj R , and iii RW Ž R. sRW Ž R.. For convenience, we say that all
Ž .
Ž
.
Ž
.
Ž
.
Ž .
t
profiles are equivalent up to zero. We also let W 0 R sF R sл, for all R. Profiles R and R ha¨e
ty1Ž ty1Ž
. Ž . Ž .
R , Et i, R sEt i, R . Note
Ž
.
0Ž
.
identical endowments at t if W ty1 R sW
R
and for all ifW
Ž
.
.
that all profiles have identical endowments at the first stage. Furthermore, the Twin Inheritance
Rule says, in this terminology, that if two profiles are equivalent up to t, then they have identical
endowments at stage tq1.
For all i, j, R, and t, let
if there exist l1 , . . . , lg gNyW ty1
R
Ž .
such that
ꢀ
g 4
l , . . . , l
¡
1
Ž
.
Et l1 , R /л, and for all ss1, . . . , gy1,
~
Ž
.
St j, i, R s
Ž
.
Ž .
Tt ls , R gEt lsq1 , R , where jsl1 and islg ;
¢
л
otherwise.

1428
SZILVIA PAPAI
´
Ž
.
Ž
.
Ž
.
Note that St i, j, R sл unless Tt j, R gEt j, R .
Note also that for all j, R, and t,
Ž
.
Ž
.
S
j, i, R jSt i, j, R
if there exists i such that
¡
t
~
Ž
.
St j, R s
Ž
.
Ž
.
St j, i, R /л and St i, j, R /л;
¢
л
otherwise.
LEMMA 2: Let f be a hierarchical exchange rule. Then, if ifW t
R
Ž
.
.
tŽ
and agF R , we ha¨e
.
Ž
.
.
afoi Ryi
ꢀ
˜
4
tŽ
.
tŽ
PROOF: Fix R, i, and tg 1, . . . , m such that ifW R . Let agF R . Note that a/0. Suppose
˜
˜
Ž
Ž
.
ꢀ
4
.
there exists Ri such that fi Ri, Ry1 sa. Let tЈg 0, . . . , my1 such that igWtЈq1 Ri, Ryi . By the
Ž
.
ꢀ
4
tŽ
.
Twin Inheritance Rule, R and Ri, Ryi are equivalent up to min t, tЈ . Then tЈ-t, since agF R
˜
˜
Ž
.
Ž
.
and fi R /a. Thus, the Twin Inheritance Rule implies that R and Ri, Ryi have identical
tЈ
endowments at tЈq1. Then, since afFtЈ Ri, Ryi , we have afF R and there exists j such that
˜
Ž
.
.
Ž .
Ž
Ž
.
Ž
tŽ
.
agEtЈq1 j, R . If jsi then agEtq1 i, R , by the Assurance Rule, given that ifW R . If j/i,
tЈ
tЈ
tЈ
˜
˜
Ž
.
.
Ž
.
Ž
.
Ž
.
StЈq1 j, i, Ri, Ryi /л. Moreover, since F Ri, Ryi sF R , it follows that for all lfW R
˜
Ž
Ž
..
Ž
.
Ž
.
such that l/i, TtЈq1 l, Ri, Ryi sTtЈq1 l, R , and thus we have StЈq1 j, i, R /л. Then, given that
ifW t R , the Assurance Rule implies that jfW R , Stq1 j, i, R /л, and agEtq1 j, R . There-
Ž
.
tŽ
.
Ž
.
Ž
.
Ž
.
tŽ
.
fore, agEtq1 j, R in either case, which contradicts the fact that agF R .
Q.E.D.
SUFFICIENCY PROOF
Let f be a hierarchical exchange rule. Fix an inheritance tree list ⌫gG underlying f. We will
show that f is Pareto-optimal, strategyproof, nonbossy, and reallocation-proof.
ꢀ
4
PARETO-OPTIMALITY: Fix R. Take a hierarchy of the individuals ␴ : N¬ 1, . . . , n , where ␴ is a
Ž . Ž .
Ž
.
tŽ
.
bijection, such that for all i, j, and t, ␴ i -␴ if igWt R and jfW R . Then for all i, j such
j
Ž . Ž . . .
Ž
Ž
that ␴ i -␴ j , ! iV R j , which implies that f is Pareto-optimal.
˜
f is manipulable. Then there exist i, R, and Ri such that
fi Ri, Ryi Pi fi R . Thus, there exists t such that ifW
fi Ri, Ryi foi Ryi , by Lemma 2, which is a contradiction.
STRATEGYPROOFNESS: Suppose
tŽ
.
tŽ
R and fi Ri, Ryi gF R . Therefore,
Ž
.
.
˜
˜
Ž
Ž
.
Ž
.
˜
.
Ž
.
˜
˜
Ž
.
Ž
.
NONBOSSINESS: Fix R, i, and Ri such that fi R sfi Ri, Ryi . Let t* be the last stage at R. If
˜
Ž
.
Ž
.
fi R s0, then R and Ri, Ryi are equivalent up to t*, by the Twin Inheritance Rule. In this case
Ft* R sK, which implies that f R sf Ri, Ryi
.
.
˜
Ž
Ž
.
Ž
.
Ž
˜
Ž
.
Ž
.
.
If fi R /0, let igWt R and igWtЈ Ri, Ryi . Assume, without loss of generality, that tFtЈ.
˜
Ž
.
Then the Twin Inheritance Rule implies that R and Ri, Ryi are equivalent up to ty1 and that R
ty1
Ž
.
Ž
ty1Ž
.
.
˜
˜
Ž .
Ri, Ryi , for
and Ri, Ryi have identical endowments at stage t. Note that since F
R sF
all jfW ty1
.
and for all jgWt R ySt i, R , fj R sfj Ri, Ryi .
R
such that j/i, Tt j, R sTt j, Ri, Ryi . Hence, Wt R ySt i, R :Wt Ri, Ryi
,
˜
˜
.
Ž
.
Ž
Ž
..
Ž
Ž
Ž
..
Ž
.
˜
Ž
.
Ž
Ž
.
Ž
.
Ž
.
˜
˜
.
Ž
Ž
.
Ž
Ž
..
Ž .
Ž .
If tstЈ then, since fi R sfi Ri, Ryi , we also have Tt i, R sTt i, Ri, Ryi . Thus, Wt R s
˜
˜
˜
˜
Ž
Ž
.
Ž
.
Ž
.
Ž
.
.
Wt Ri, Ryi , and for all jgWt R , we have fj R sfj Ri, Ryi . If t-tЈ, then Wt Ri, Ryi sWt R
˜
Ž
.
Ž
..
.
Ž
.
Ž
Ž
Ž
..
ySt i, R . Since igWtЈ Ri, Ryi and Et i, R sEt i, Ri, Ryi , the Assurance Rule implies that
˜
˜
˜
Ž
.
Ž
Ž
Ž
.
.
Ž
.
Ž
Ž
..
Et i, R :EtЈ i, Ri, Ryi . Then, given that fi R sfi Ri, Ryi , St i, R sStЈ i, Ri, Ryi , by the
˜
Ž
.
Ž
.
Ž
.
Assurance Rule. Hence, for all jgWt R , fj R sfj Ri, Ryi in this case as well. If t is the last
Ž
.
stage tst* , the proof is completed. Thus, assume that t-t*.
Fix z)t such that Wz R sл. Assume that for all jgW zy1 R , fj R sfj Ri, Ryi . Fix
˜
Ž
.
.
ꢀ
Ž
.
Ž
.
Ž
.
Ž
.
Ž
4
Ž
.
Ž
.
Sz h1, R /л. Let Sz h1, R s h1, . . . , hg , gG1, such that for all ss1, . . . , g, fh R gEz
h
sq1, R ,
Ž
R . Thus, agEz hs, R . Then, there exists a vertex
y1
s
.
Ž
.
where we let hgq1 sh1. Fix sFg. Let asfh
s

STRATEGYPROOF ASSIGNMENT
ꢀ
4r
in ⌫a such that L ¨r shs, and for all ss0, . . . , ry1 in the Q-path ¨
s ss0
1429
Ž
R
.
¨
from ¨0 to ¨r , we
r
Ž
.
zy1Ž
. Ž . Ž .
and fL Ž R sH ¨s, ¨sq1 . Then, given that for all ss0, . . . , ry1,
¨ .
s
have L ¨s gW
fL Ž R s fL Ž Ri, Ryi
,
for all zЈ F m such that hs f W zЈy1 Ri, Ryi
,
either a g
˜
Ž
¨ .
s
˜
Ž
.
.
Ž
.
¨
Ž s
.
˜
˜
Ž
..
Ž
Ž
. Ž
..
EzЈ hs, Ri, Ryi , or agEzЈ L ¨s , Ri, Ryi for some ss0, . . . , ry1. Since this holds for all hs
with ss1, . . . , g, and for all zЈFm such that hs fW zЈy1 Ri, Ryi , we have for all s and all such
˜
Ž
.
zЈy1
˜
Ž
.
Ž
.
Ri, Ryi .
zЈ, fh
R fF
Thyer1 efore, an immediate implication is that for all ss1, . . . , g, fh Ri, Ryi /0. Then, for all
s
˜
Ž
.
s
˜
Ž
.
ss1, . . . , g, we can let hs gWz Ri, Ryi , without loss of generality. Now note that since for all
s
.
jgW zy1 R , fj R sfj Ri, Ryi , we have, for all s, fh R Rh fh Ri, Ryi . Hence, for all ss1, . . . , g,
˜
˜
Ž
s
Ž
.
Ž
.
Ž
Ž
.
.
s
individual hs cannot leave at an earlier stage than hsq1 doess, given that fh R fF
z
q1y1
s
˜
Ž
.
Ž
.
Ri, Ryi .
This means that for all s, zs Gzsq1, which in turn implies that there exists szЈFm such that for all
zЈy1
˜
˜
˜
Ž
.
Ž
.
Ž
.
Ž
.
Ž
.
,
s, hs gWzЈ Ri, Ryi . Then, since for all s, fh R fW
Ri, Ryi and since fh R Rh fh Ri, Ryi
s
s
s
s
˜
˜
Ž
Ž
.
..
Ž
.
Ž
.
it must be the case that for all s, TzЈ hs, Ri, Ryi sfh R . Consequently, for all s, fh Ri, Ryi
s
s
s
Ž
.
Ž
zŽ
.
Ž
.
Ž
.
˜
fh R . Since this holds for every Sz h1, R /л, it follows that for all jgW R , fj R sfj Ri, Ryi
Therefore, f R sf Ri, Ryi , by induction.
.
s
˜
Ž
.
Ž
.
Ž
.
LEMMA 3: Let f be a hierarchical exchange rule. Then, if i, jgWt R such that i/j, we ha¨e
Ž
.
Ž
.
Ž
.
fj R goi Ryi if and only if jgSt i, R .
˜
Ž
.
PROOF: Fix R, i, j, and t such that i, jgWt R and i/j. Let Ri be defined as follows. For all
16
ty1Ž
.
.
˜
˜
Ž
i
Ž
.
Ž
.
a/fj R , let aP fj
R
if and only if agF
R . Note that for all a such that aP fj R , we have
i
˜
Ž
.
Ž
.
afoi Ryi , by Lemma 2. Then, by the Twin Inheritance Rule, R and Ri, Ryi are equivalent up to
Ž
.
Ž
..
.
ty1, and they have identical endowments at t. Then, since igWt R and thus Et i, R /л, we
˜
Ž
˜
˜
Ž
Ž
Ž
Ž
..
Ž
Ž
..
Ž
.
Ž
have Et i, Ri, Ryi /л. Thus, Tt i, Ri, Ryi sfj
R
implies that St i, l, Ri, Ryi /л, where
˜
˜
Ž
.
Ž
..
ty1Ž
.
Ž
..
Ž
Ž
.
fj R gEt l, Ri, Ryi . Also, for all hfW
R such that h/i, we have Tt h, Ri, Ryi sTt h, R .
˜
˜
Ž
.
Ž
Ž
.
Ž
Ž
Ž
.. ..
Ž
Ž
Ž
Then, if jgSt i, R , we have lgSt i, R and St l, i, Ri, Ryi /л. Therefore, lgSt i, Ri, Ryi ,
˜
˜
.
Ž
.
Ž
Ž
.
.
Ž
Ž
..
˜
Ž
.
..
and fi Ri, Ryi sfj R . On the other hand, if jfSt i, R , we have St j, Ri, Ryi sSt j, R , and
˜
˜
Ž
.
.
.
Ž
fj Ri, Ryi sfj R . Then, since strategyproofness implies that fi Ri, Ryi stop Ri, oi Ryi , we
Ž
.
Ž
.
have fj R foi Ryi if jfSt i, R .
Q.E.D.
Ž
.
Ž
.
Ž
.
LEMMA 4: Let f be a hierarchical exchange rule. Then, if iA R j and igWt R , we ha¨e jgSt i, R
or jfW t R .
Ž
.
˜
Ž
.
Ž
.
PROOF: Fix R, i, and t such that igWt R . Fix bgoi Ryi . Let Ri be defined as follows. For all
tŽ
. Ž .
Ž .
˜
a/b, let aP b if and only if agF
i
R and hfSt i, R , where fh R sa. Then, for all a such that
i
˜
˜
Ž
.
Ž
.
aP b, we have afoi Ryi , which is implied by Lemma 2 and Lemma 3. Thus, fi Ri, Ryi sb, by
˜
Ž
.
strategyproofness. Furthermore, R and Ri, Ryi are equivalent up to ty1, and they have identical
endowments at t, by the Twin Inheritance Rule. Therefore, for all lgW ty1 R , fl Ri, Ryi sfl R .
˜
Ž
Ž
.
Ž
Ž
.
Ž .
.
˜
Ž
.
Ž
.
..
Ž
Furthermore, for all lgWt R such that lfSt i, R we have l/i, so that Tt l, Ri, Ryi sTt l, R .
This implies that for all lgW t
˜
. Ž . Ž .
R such that lfSt i, R , we have fl Ri, Ryi sfl R . Since
Ž
Ž .
R such that
bgoi Ryi was chosen arbitrarily, it follows from nonbossiness that for all lgW t
. .
Ž
Ž
.
Ž .
.
Ž
Ž
lfSt i, R , we have ! iA R l .
Q.E.D.
˜
˜
˜ ˜
Ž
REALLOCATION-PROOFNESS: Suppose there exist R, i, j and Ri, Rj, such that fj Ri, Rj,
˜ ˜
˜
˜ ˜
.
Ž
.
Ž
.
Ž
.
Ž
.
Ž
.
Ž
.
Ryi , j Ri fi R , fi Ri, Rj, Ryi, j Pj fj R , and fh R sfh Rh, Ryh /fh Ri, Rj, Ryi, j for hsi, j. Then
˜ ˜
Ž
˜ ˜
Ž
.
Ž
.
iA Ri, Rj, Ryi, j j and jA Ri, Rj, Ryi, j i. Thus, Lemma 4 implies that there exists t such that
˜ ˜
˜ ˜
˜
Ž
..
Ž
.
Ž
.
igSt j, Ri, Rj, Ryi, j . This implies, in turn, that fi Ri, Rj, Ryi, j goj Ri, Ryi, j , given Lemma 3.
˜
˜
Ž
.
Ž
.
,
Ž
.
Ž
.
Note that since fi R s fi Ri, Ryi
we have fj R s fj Ri, Ryi ,
by nonbossiness. Thus,
˜ ˜
˜
˜
Ž
Ž
.
Ž
.
.
fi Ri, Rj, Ryi, j Pj fj Ri, Ryi , and j can manipulate at Ri, Ryi , which contradicts strategyproof-
ness.
16
In the following we will say that Ri ranks the objects in Fty1
R first and then fj R .
˜
Ž
.
Ž .

1430
SZILVIA PAPAI
´
LEMMAS FOR THE NECESSITY PROOF
Ž
.
Ž .
LEMMA 5: Let f be group-strategyproof and Pareto-optimal. Then jV R i and jA R i imply that for
all Rj such that fi Rj, Ryj /fi R , we ha¨e fi R Pi fi Rj, Ryj .
˜
˜
˜
Ž
Ž
.
Ž
.
Ž
.
.
˜
˜
Ž
.
Ž
Ž
Ž
.
Ž
.
Ž .
PROOF: Fix R and i, j such that jV R i and jA R i. Fix Rj such that fi Rj, Ryj /fi R .
˜
˜
˜
Ž
Ž
.
Ž
.
Ž
.
.
.
.
Suppose fi Rj, Ryj Pi fi R . Let fj R sc, fi R sb, fj Rj, Ryj sd, and fi Rj, Ryj sa. First note
Ž
Ž . .
that if cs0, then ds0, by strategyproofness, and then ! jA R i , by nonbossiness. Thus, cgK,
and similarly dgK. Furthermore, bgK, since bPj c, and agK, since aP b. Note also that d/b,
i
˜
otherwise j could manipulate at R via Rj, d/c, otherwise j would be bossy, and a/c, otherwise
Pareto-optimality would be violated at R. Thus, feasibility implies that a, b, c, and d are distinct.
Let Rj rank b first, c second, and d third. Let Ri rank a first and b second. Since Rj is a
Ž
.
Ž .
.
push-up of Rj for c, and Ri is a push-up of Ri for b, f Ri, Rj, Ryi, j sf R , by group-strategyproof-
ˆ
Ž
ness. Let Rj rank b first, d second, and c third. Since bfoj Ryj , by strategyproofness, and
dgoj Ryj , we have fj Rj, Ryj sd, by strategyproofness. Then fi Rj, Ryj sa, by nonbossiness.
Thus, fi Ri, Rj, Ryi, j, sa, by strategyproofness, since Ri is a push-up of Ri for a. Therefore,
ˆ
ˆ
Ž
.
Ž
.
Ž
.
ˆ
Ž
.
ˆ
Ž
.
fj Ri, Rj, Ryi, j sd, by nonbossiness.
ˆ
ˆ
ˆ
Ž
.
s
Let Ri rank a first, c second, and b third. Since Ri is a push-up of Ri for a, f Ri, Rj, Ryi, j
ˆ ˆ
ˆ
Ž
.
Ž
.
ˆ
.
ꢀ
4
f Ri, Rj, Ryi, j , by group-strategyproofness. Note that fj Ri, Rj, Ryi, j g c, d , by strategyproof-
ˆ
Ž
.
.
Ž
ness. Note, furthermore, that given fi Ri, Rj, Ryi, j sb, fi Ri, Rj, Ryi, j Ri b, by strategyproofness.
ˆ
ˆ
ˆ
Ž
Ž
.
Ž
.
If fj Ri, Rj, Ryi, j sc, fi Ri, Rj, Ryi, j sa, since fi Ri, Rj, Ryi, j sb would violate Pareto-optimal-
ˆ
ˆ
Ž
.
Ž
.
ˆ
ity. If fj Ri, Rj, Ryi, j sd, then nonbossiness implies that fi Ri, Rj, Ryi, j sa. This is a contradic-
Ž
.
tion, however, since it implies that i can manipulate at Ri, Rj, Ryi, j via Ri.
Q.E.D.
Ž
.
Ž .
LEMMA 6: Let f be group-strategyproof and Pareto-optimal. Then jV R i and jA R i imply that for
all Rj such that fi Rj, Ryj /fi R , we ha¨e fj R goi Rj, Ryi, j .
˜
˜
Ž
.
Ž
.
Ž
.
Ž
.
˜
˜
Ž
.
Ž
.
Ž
.
Ž .
PROOF: Fix R and i, j such that jV R i and jA R i. Fix Rj such that fi Rj, Ryj /fi R .
˜
˜
˜
Ž
Ž
.
Ž
.
Ž
.
Ž
.
Ž
.
.
Suppose fj R foi Rj, Ryi, j . Let fj R sc, fi R sb, fj Rj, Ryj sd, and fi Rj, Ryj sa. First
note that c, dgK, by group-strategyproofness, as in Lemma 5, and bgK, since bPj c. Note also that
d/b, by strategyproofness, and d/c, by nonbossiness, as in Lemma 5. Furthermore, a/c, since
˜
Ž
.
cfoi Rj, Ryi, j . Thus, feasibility implies that a, b, c, and d are distinct.
Let Rj rank b first, c second, and d third. Let Ri rank b first, c second, and, if a/0, a third.
Ž
.
.
Ž .
Since Rj is a push-up of Rj for c, and Ri is a push-up of Ri for b, f Ri, Rj, Ryi, j sf R , by group-
˜
Ž
strategyproofness. Note that Lemma 5 implies that bP a, and thus bfoi Rj, Ryi, j , by strategyproof-
ness. Then, since cfoi Rj, Ryi, j and agoi Rj, Ryi, j , if a/0, we have fi Ri, Rj, Ryi, j sa, by
strategyproofness. If as0, fi Ri, Rj, Ryi, j s0, by strategyproofness. Thus, fj Ri, Rj, Ryi, j sd, by
i
˜
˜
˜
Ž
.
Ž
.
Ž
.
˜
˜
Ž
.
Ž
.
nonbossiness.
ˆ
Ž
.
Let Rj rank b first, d second, and c third. Since bfoj Ri, Ryi, j , by strategyproofness,
ˆ
Ž
.
Ž
.
and dgoj Ri, Ryi, j
,
we have fj Ri, Rj, Ryi, j sd, by strategyproofness. This implies that
ˆ
Ž
.
fi Ri, Rj, Ryi, j sa, by nonbossiness.
ˆ
ˆ
Let Ri rank c first, b second, and, if a/0, a third. Since Ri is a push-up of Ri for a,
ˆ
ˆ ˆ
ˆ
Ž
Ž
Ž
.
Ž
.
.
ꢀ
4
f Ri, Rj, Ryi, j sf Ri, Rj, Ryi, j , by group-strategyproofness. Note that fj Ri, Rj, Ryi, j g c, d , by
Ž
.
.
strategyproofness. Note, furthermore, that cgoi Rj, Ryi, j , given that jV Ri, Rj, Ryi, j i and f is
ˆ
Ž
.
group-strategyproof, otherwise Pareto-optimality would be violated. Thus, fi Ri, Rj, Ryi, j sc, by
ˆ
ˆ ˆ
Ž
.
Ž
.
strategyproofness, and therefore fj Ri, Rj, Ryi, j sd. However, given that fj Ri, Rj, Ryi, j sd and
ˆ ˆ
Ž
.
fi Ri, Rj, Ryi, j sa, nonbossiness is violated.
Q.E.D.
Ž
.
LEMMA 7: Let f be group-strategyproof, Pareto-optimal, and reallocation-proof. Then jV R i implies
. .
Ž
Ž
! jA R i .
Ž
.
Ž
.
Ž .
PROOF: Suppose there exist i, j, and R such that jV R i and jA R i. Let fi R sa and
˜
˜
˜
˜
Ž
Ž
.
Ž
.
Ž
.
.
fj R sb. Fix Rj such that fi Rj, Ryj /a. Note that aP fi Rj, Ryj , by Lemma 5. Let fj Rj, Ryj
i

STRATEGYPROOF ASSIGNMENT
1431
sc. Then c/b, by nonbossiness, and c/a, by strategyproofness. Moreover, b, cgK, by group-
strategyproofness, as in Lemma 5, and agK, since aPj b.
ˆ
ˆ
ˆ
Let Rj rank a first, b second, and c third. Let Ri rank a first and b second. Then Rj is a
ˆ
ˆ ˆ
Ž
.
Ž .
push-up of Rj for b, and Ri is a push-up of Ri for a, so f Ri, Rj, Ryi, j sf R , by group
strategyproofness.
ˆ
Ž
Ž
.
ꢀ
4
Let Rj rank a first, c second, and b third. Then fi Ri, Rj, Ryi, j g a, b , by Lemma 6 and
ˆ
Ž
.
.
strategyproofness. Suppose fi Ri, Rj, Ryi, j sa. Then fi Rj, Ryj Ri a, by strategyproofness. Since
˜
˜
Ž
.
Ž
Ž
.
Ž
.
Ž
.
aP fi Rj, Ryj , by Lemma 5, this means that fi Rj, Ryj /fi Rj, Ryj . Note that fj Rj, Ryj sc, by
i
Ž
.
.
strategyproofness, since afoj Ryj and cgoj Ryj . In this case, however, nonbossiness is violated,
˜
ˆ
Ž
.
.
Ž
.
given that fj Rj, Ryj sc. Thus, fi Ri, Rj, Ryi, j sb. Then strategyproofness implies that
ˆ
Ž
fj Ri, Rj, Ryi, j sc.
ˆ
Ž
.
Let Ri rank b first and a second. Note that Ri is a push-up of Ri for b, so that f Ri, Rj, Ryi, j
sf Ri, Rj, Ryi, j , by group-strategyproofness. Now consider the profile Ri, Rj, Ryi, j . By strate-
ˆ
ˆ
Ž
.
Ž
.
ˆ
ˆ
ˆ
Ž
.
ꢀ
4
Ž
.
Ž
Ž
.
.
gyproofness, fj Ri, Rj, Ryi, j g b, c . If fj Ri, Rj, Ryi, j sb, then fi Ri, Rj, Ryi, j sa, by strate-
ˆ
ˆ
Ž
.
gyproofness, and Pareto-optimality is violated. Thus, fj Ri, Rj, Ryi, j sc, and f Ri, Rj, Ryi, j s
Ž
.
f Ri, Rj, Ryi, j , by nonbossiness.
Ž .
ˆ ˆ
ˆ ˆ
.
Ž
.
Ž
.
Ž .
Ž
.
In sum, we have
i fi Ri, Rj, Ryi, j sfj Ri, Rj, Ryi, j sb, ii aPj c, where fi Ri, Rj, Ryi, j sa
ˆ
ˆ
Ž
.
Ž
.
Ž
.
Ž
.
Ž
and fj Ri, Rj, Ryi, j sc, and iii f Ri, Rj, Ryi, j sf Ri, Rj, Ryi, j sf Ri, Rj, Ryi, j . Thus, reallo-
cation-proofness is violated.
Q.E.D.
NECESSITY PROOF
Let f be group-strategyproof, Pareto-optimal, and reallocation-proof. We will show that f is a
hierarchical exchange rule.
Step 1. Construction of the Canonical Inheritance Trees.
Ž
.
Fix agK. We will construct its canonical inheritance tree ⌫a. Let ⌫a s V, Q be a rooted tree
Ž
. Ž
.
Ž
.
with root ¨0 that satisfies properties C.1 , C.2 , and C.3 listed in Subsection 4.1. Assume that the
arcs are labeled as required by B.1 , B.2 , and B.3 . In order to determine the labels of the
vertices, we first prove the following claim.
Ž
.
Ž
.
Ž
.
˜
<
<
CLAIM: Fix M;N such that M -k. For all igM, let Ri rank object bi first and object a second,
such that for all i, jgM, bi /bj if i/j. For all igNyM, let Ri rank a first. Then there exists
˜
Ž
.
jgNyM such that fj RM , RyM sa.
PROOF: The claim follows from Pareto-optimality. First, since NyM/л, Pareto-optimality
˜
Ž
.
implies that there exists jgN such that fj RM , RyM sa. Suppose jgM. Then there exists igN
˜
˜
Ž
.
such that fi RM , RyM sbj, by Pareto-optimality. Note, however, that if igM, then we have aP bj,
i
˜
since bi /bj, and if igNyM, then we have aP bj. Given that jgM and bj Pj a, this violates
i
Pareto-optimality. Thus jgNyM, and the claim is proved.
Now we are ready to determine the labels of the vertices in ⌫a, in accordance with properties
Ž
.
Ž
.
A.1 and A.2 . For all igN, let Ri rank a first. Then Pareto-optimality implies that there exists
4r
be the Q-path
Ž
.
Ž
.
ꢀ
jgN such that fj R sa. Let L ¨0 sj. Let ¨r gV, with 0-r-m, and let ¨
s ss0
from ¨0 to ¨r. Assume that for all ss0, . . . , ry1, the label of vertex ¨s is determined. We will show
how to determine the label of ¨r.
ꢀ
Ž
.
4
Let Ms igN: there exists ss0, . . . , ry1 such that L ¨s si . Note that for all ss0, . . . ,
˜
Ž
.
Ž
.
Ž
.
ry1, H ¨s, ¨sq1 /a, by B.1 . For all igM, let Ri rank object H ¨s, ¨sq1 first and a second,
Ž
.
Ž
.
Ž
.
Ž
.
where L ¨s si. Note that for all i, jgM, H ¨s , ¨s q1 /H ¨s , ¨s q1 if i/j, by B.2 , where
i
i
j
j
Ž
Ž
.
Ž
.
L ¨s si and L ¨s sj. Then the claim above implies that there exists jgNyM such that
i
j
˜
.
Ž .
fj RM ,RyM sa. Label
accordance with A.2 .
¨
by j, that is, let L ¨r sj. Note that since jgNyM, this is in
r
Ž
.

1432
SZILVIA PAPAI
´
This completes the recursive definition of all the labels in ⌫a. The canonical inheritance tree is
constructed similarly for each object agK. Thus, we have determined ⌫gG, based on the
assignments rule f.
⌫
⌫
Ž
.
Ž .
In the rest of this proof, we will show that for all R, f R sf R , where f is the hierarchial
exchange rule associated with ⌫gG, as defined in Section 4.
Fix RgR. Let t*Fm be the last stage at profile R. We will show, using induction, that for all
⌫
Ž
.
Ž
.
Ž .
tFt* and for all igWt R , fi R sfi R .
Step 2. Basis Step: Assignments at Stage 1.
˜
.
˜
Ž
.
Ž
Step 2.a: For all igN and for all agE1 i, R , agoi Ryi for all R.
Ž
.
Ž . Ž .
Ž
.
Fix igN and agE1 i, R . Given 1 and 3 , we have L ¨0 si in ⌫a. Thus, by the construction
˜
Ž
.
Ž
.
of ⌫a in Step 1, fi R sa, where top Rj sa for all jgN. Fix R and let isn. Then, since
˜
.
˜
Ž
.
Ž
.
Ž
.
.
1V R n, we have fn R1, Ry1 sa, by Lemma 7. This implies in turn that, since 2V R1, Ry1 n, we
˜
˜
˜
Ž
Ž
have fn R1, R2 , Ry1, 2 sa, by Lemma 7. Continuing iteratively, we get fn Ryn, Rn sa. Thus, for
˜
˜
.
Ž
all R, agoi Ryi , and Step 2.a is completed.
˜
˜ ˜
.
Ž
.
Ž
Note that this step implies that for all igN, for all agE1 i, R , and for all R, fi R Ri a, given
that f is strategyproof.
⌫
Ž
.
Ž
.
Ž .
Step 2.b: For all igW1 R , fi R sfi R .
Ž
.
<
Ž
. <
Ž
.
Ž
.
Ž
.
Ž
Ž
˜
.
Fix igW1 R . If S1 i, R s1, then T1 i, R gE1 i, R , so that fi R sT1 i, R , by Step 2.a. If
<
Ž
.<
Ž
.
ꢀ
4
.
Ž
.
S1 i, R G2, let S1 i, R sSs j1, . . . , jg , such that for all ss1, . . . , g, T1 js, R gE1
j
sq1, R ,
Ž
rank top Rj
sq1
.
where we let jgq1 sj1 and isjs for some ss1, . . . , g. For all ss1, . . . , g, let Rj
s
q1
.
˜
Ž
.
.
Ž
.
Ž
.
Ž
Ž
.
first, and top Rj second. Suppose fj RS, RyS /top Rj . Then, since top Rj gE1 j1, R , we
s
1
1
g
˜
˜
Ž
Ž
.
Ž
.
Ž
.
have fj RS, RyS stop Rj , by Step 2.a. Note that in this case fj RS, RyS /top Rj , and thus
1
g
g
g
˜
Ž
.
Ž
.
, by a similar argument. Hence, an iterative repetition of this argument
y1
fj RS, RyS stop Rj
yields that for all ss1, . . . , g, fj
g
g
˜
. Ž
RS, RyS stop Rj . This implies, however, that for all ss
Ž
.
s
˜
˜
Ž
.
Ž
.
Ž
.
.
1
1, . . . , g, js V RS, RyS
j
sq1, whichsqco1 ntradicts Pareto-optimality. Therefore, fj RS, RyS stop Rj
1
˜
Ž
.
Ž
.
Ž
.
Ž
.
Since top Rj gE1 j2 , R , Step 2.a implies that fj RS, RyS stop Rj , etc. Thus, for all ss
1
˜
2
2
˜
.
Ž
.
Ž
.
Ž
Ž
.
Ž
.
Ž .
1, . . . , g, fj RS, RyS stop Rj sT1 js, R . Then f RS, RyS sf R follows, by group-strate-
s
s
⌫
.
Ž
.
Ž
Ž .
gyproofness. Therefore, for all igW1 R , fi R sT1 i, R sfi R . Note, furthermore, that since R
ˆ
ˆ
Ž
.
Ž .
R .
Ž R.
was chosen arbitrarily, this means that for all RyW Ž R., fW
RW Ž R., RyW
sfW
Ž R.
Ž R.
1
1
1
1
1
Step 3. Inducti¨e Step: Assignments at Stage tq1.
⌫
Fix t-t*. Assume that for all igW t R , fi R sfi R . Let MsW
R
and let LsF R .
Ž
.
Ž
.
Ž
.
tŽ
.
tŽ
.
˜
˜
Ž
.
Ž .
Assume, furthermore, that for all RyM , fM RM , RyM sfM R .
˜
˜
Ž
.
Ž
.
Step 3.a: For all igNyM and for all agEtq1 i, R , agoi RM , RyM, i for all RyM
.
Ž
.
Ž .
Ž .
Ž
.
Fix igNyM and agEtq1 i, R . Given 2 and 4 , either L ¨0 si in ⌫a or there is a Q-path
ꢀ
4r
Ž
.
Ž .
¨
in ⌫a from ¨0 to ¨r such that L ¨r si, and for all ss0, . . . , ry1 we have L ¨s gM,
H ¨s, ¨sq1 gL, and fL Ž R sH ¨s, ¨sq1 . For all jgN, let Rj rank a first. We will show first
s ss0
⌫
Ž
.
Ž
.
.
Ž
.
¨
s
Ž
.
Ž
that fi RM , RyM sa.
.
Ž
.
Ž
.
Note that if L ¨0 si in ⌫a, then fi RM , RyM sa, by Step 2.a. Thus, assume that L ¨0 /i in
ꢀ
Ž
.
4
ꢀ
⌫a. Let Vs jgN : there exists ss0, . . . , ry1 such that L ¨s sj , where ¨
s ss0
4r
is the Q-path in
⌫
Ž .
Ž .
⌫
from ¨0 to ¨r. Note that V:M. Thus, for all jgV, fj R sfj R , by assumption, and hence
a
Ž
ˆ
.
Ž
ˆ
.
Ž
.
Ž
.
fj R sH ¨s, ¨sq1 , where jsL ¨s . Therefore, by the construction of ⌫a in Step 1, fi RV , RyV s
Ž
.
a, where Rj ranks fj
R
first and a second, for all jgV. Now note that for all jgMyV, we have
ˆ
ˆ
Ž
.
Ž
.
Ž
.
s
jV RV , RyV i. Thus, Lemma 7 implies that fi RV , RMyV , RyM sa. Note also that fM RM , RyM
ˆ
.
Ž
.
Ž
.
sfM R , by assumption. Then, since V:M, for all jgV, Rj is a push-up of Rj for fj RM , RyM
ˆ
Ž
.
Ž
.
Ž
fj R . This implies that f RV , RMyV , RyM sf RM , RyM , by group-strategyproofness. In particu-
Ž
.
lar, fi RM , RyM sa, as desired.
˜
˜
Ž
.
Now we show, similarly to Step 2.a, that for all RyM , agoi RM , RyM, i . Since for all i, jgNyM,
Ž
.
j/i, jV RM , RyM i, Step 3.a follows from Lemma 7. Note that this step implies that for all
˜
˜
Ž
.
Ž
.
igNyM, for all agEtq1 i, R , and for all RyM , fi RM , RyM Ri a, given that f is strategyproof.