Institute for Economic Studies, Keio University
Keio-IES Discussion Paper Series

When is a sequential school choice system (non-)deficient?
Tetsutaro Hatakeyama
2 July, 2023
DP2023-012
https://ies.keio.ac.jp/en/publications/22879/

Institute for Economic Studies, Keio University
2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan
ies-office@adst.keio.ac.jp
2 July, 2023

When is a sequential school choice system (non-)deficient?
Tetsutaro Hatakeyama
Keio-IES DP2023-012
2 July, 2023
JEL Classification: C78; D47; D61; D78
Keywords: sequential assignment system; non-wastefulness; straightforwardness;tiered domain

Abstract
We study sequential assignment systems in which objects are assigned to agents in
multiple stages. While such systems are prevalent in real-life school choice and college
admissions, Dur and Kesten (2019) show that these systems are neither non-wastefulnor straightforward in general. To overcome this negative observation, we consider amodel in which the mechanism designer chooses an allocation schedule, i.e., in which
stage to allocate each object, as well as the allocation mechanisms it uses within asystem. Our analysis newly reveals that (i) in general, no allocation schedules avoid
wastefulness/non-straightforwardness and (ii) a nonwasteful/straightforward
allocation schedule exists if and only if the preference domain is "tiered." This result
supports practices in which the tiered domain naturally arises (e.g., Chinese college
admissions practice). However, this also highlights the difficulty of sequential
assignments in more diverse preference domains.
Tetsutaro Hatakeyama
Graduate School of Economics, Keio University
2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japant.hatakeyama@keio.jp

When is a sequential school choice system (non-)deficient?∗
Tetsutaro Hatakeyama†
July 2, 2023

Abstract
We study sequential assignment systems in which objects are assigned to agents in multiple
stages. While such systems are prevalent in real-life school choice and college admissions, Dur
and Kesten (2019) show that these systems are neither non-wasteful nor straightforward ingeneral. To overcome this negative observation, we consider a model in which the mechanism
designer chooses an allocation schedule, i.e., in which stage to allocate each object, as wellas the allocation mechanisms it uses within a system. Our analysis newly reveals that (i) ingeneral, no allocation schedules avoid wastefulness/non-straightforwardness and (ii) a nonwasteful/straightforward allocation schedule exists if and only if the preference domain is“tiered.” This result supports practices in which the tiered domain naturally arises (e.g.,Chinese college admissions practice). However, this also highlights the difficulty of sequential
assignments in more diverse preference domains.
JEL Classification: C78; D47; D61; D78
Keywords: sequential assignment system; non-wastefulness; straightforwardness; tiered domain

1

Introduction

In recent decades, market design has been successful in analyzing and improving real-life resource
allocations where monetary transfers are not allowed, for example, school choice (Abdulkadiroğlu
and Sönmez, 2003) and college admissions (Balinski and Sönmez, 1999). While much of the existing
literature concentrates on (and contributes by) designing static allocation systems, several systems∗

I am grateful to Onur Kesten and Morimitsu Kurino for helpful comments and suggestions. I also thank Takashi
Akahoshi, Yuji Fujinaka, Ryo-ichi Nagahisa, Nariaki Nishino, Ryosuke Sakai, and seminar participants at Kansai
University and the 2023 JEA Spring Meeting for comments. I acknowledge financial support from JST SPRING
Grant Number JPMJSP2123 and the Keio Economic Society.
†Graduate School of Economics, Keio University, 2-15-45 Mita, Minato-ku, Tokyo 108-8345, Japan. E-mail:t.hatakeyama@keio.jp

1Order1
2
3
4

Position category
National ministries
Metropolitan government
Prefectural governments
City offices

Example(s)Ministry of FinanceTokyo
Osaka, Kyoto
many local cities

First exam
April 9April 30
June 18
September 19

Announcement of result
June 8July 14
Augustdepends on cities

Table 1: 2023 exam timeline in Japanin reality allocate resources sequentially in the sense that some are allocated first (e.g., this month)and the remaining are next (e.g., the next month).
In many regions of the United States, for example, Boston, Chicago, and New York, student
enrollment systems for exam, charter, magnet, private, and specialized schools are operated separately from the enrollment system for regular (mainstream) schools with different timelines. Every
student can participate in multiple systems where different systems adopt different mechanisms(e.g., student-proposing deferred acceptance or serial dictatorship) and different priority structures(e.g., lottery numbers or exam scores). Therefore, one student may participate in the exam school
system and proceed to the regular school system only when she is not assigned to any exam school,
while another student may only participate in the regular school system.
In China, the college admissions system comprises several stages where admissions for toptier (the most prestigious) colleges are followed by admissions for lower-tier (less prestigious)
colleges. In Japan, a similar sequential system is used in employment exams for public officers,that is, exams for the most prestigious national employee positions are followed by those for lessprestigious prefecture/city-level employee positions (see Table 1).1 Although extensively practiced,
as shown in Dur and Kesten (2019), a sequential enrollment/admission has deficiencies, including
inefficiency of allocations (wastefulness) and student incentives in reporting true preferences (nonstraightforwardness).2
These examples pose a puzzle: a sequential assignment is not desirable in theory, but it isso prevalent in practice. In fact, static resource allocation is not that easy in some practices.
According to Manjunath and Turhan (2016), a journalist says that it is difficult to unify public
and private school enrollment systems in Milwaukee because they are in competition for the same
students and have no incentives for coordination. Toward addressing this puzzling observation, we
ask if there are circumstances when these deficiencies can be avoided. We show that despite thegeneral result, under a restrictive but realistic condition (the tiered preference domain), a sequential
assignment overcomes the above deficiencies. More interestingly, outside the tiered domain, thegeneral impossibility result always holds (Proposition 2). Thus, our results also highlight thedifficulty of sequential assignments in general diverse domains.
By slightly modifying the setting of Dur and Kesten (2019) and Andersson et al. (2018), this1
2

Table 1 is based on the webpage https://90r.jp/schedule.html (written in Japanese, accessed March 26, 2023).
See Section 4 of Dur and Kesten (2019).

2paper introduces a problem of designing an allocation schedule: Given a fixed number of stages(available dates) in which objects can be allocated, a mechanism designer (a local government)chooses in which stage to allocate each object to agents. The designer has two standard objectives:
non-wastefulness (no object should be disposed if there is someone who wishes it) and straightforwardness (no lie should be profitable). We assume that objects (schools) are not strategic andthey can coordinate enough to follow a fixed schedule. To focus on the design of the allocation
schedule, we assume that each mechanism used at each stage satisfies certain desirable properties.3
If we pick one stage and allocate all the objects in that stage, because it is a static system, we canreadily achieve both non-wastefulness and straightforwardness. While we wish to allocate objects
in two or more stages, Proposition 1 shows a negative result in general domains. This means that
there are cases in which any schedule comprising multiple stages leads to wastefulness and nonstraightforwardness. Afterward, we search for a condition for a positive result, that is, a condition
under which non-wasteful and straightforward allocation schedules exist. The main result is thata special type of domain, the so-called “tiered domain,” is necessary and sufficient for a possibility(Proposition 2). Roughly speaking, this domain contains two types of profiles: the one with allagents partially agreeing on which objects are good (bad) and the other with agents preferring
only specific objects to being unassigned.
Proposition 2 gives us an implication on when sequential assignment costs (does not cost)wastefulness or non-straightforwardness. The tiered domain is highly restricted but it naturally
arises under specific circumstances. In Chinese college admissions (Japanese employment exams),
it is commonly presumed that everyone prefers a more prestigious college (position). As longas these presumptions are realistic, prestige-based preference tiers naturally arise, and thus, nonwastefulness and straightforwardness are both achievable via a sequential assignment. Interestingly,
the allocation schedule in reality is actually “better tiers in earlier stages,” which achieves nonwastefulness and straightforwardness.4 This observation indicates that the schedule in reality may
not be problematic in theory. In contrast, under more general, diverse preference profiles where
no tiers exist, such a positive result does not hold.5
Related literature. After pioneering works by Balinski and Sönmez (1999) and Abdulkadiroğlu andSönmez (2003), many papers study real-life school choice and college admissions systems. Amongthem, Abdulkadiroğlu et al. (2005) document a concern on that two-stage implementation of stable mechanisms for specialized and regular schools possibly violates stability. Recently, several
3

The properties are described in the next section. Specific mechanisms that satisfy these properties appear in
Corollary 2.
4
See Example 1 for this type of schedule. In cases (ii) and (iii), {a, b} are better objects for everyone and thus
they are allocated earlier than other objects.
5
The example of school choice is a bit more complicated. If we just focus on regular and specialized schools, it
is not implausible to assume that students who apply to specialized schools prefer them to any regular schools
and the other majority students prefer being unassigned to any specialized schools. Under this assumption,
regular/specialized-based preference tier arises. However, it is ambiguous if we can treat other (e.g., private)schools in the same manner. Preference tier may not exist in this example.

3

papers study sequential assignment problems similar to ours. Ekmekci and Yenmez (2019) study
school incentives to join the common enrollment system and explain why exam and regular school
markets operate separately. Dur and Kesten (2019) show that sequential allocation systems inpractice suffer from several deficiencies, including wastefulness and non-straightforwardness, andanalyze equilibria of associated preference revelation games. Andersson et al. (2018) and Doğan
and Yenmez (2023) also study the properties of equilibria in sequential preference revelation games.
The former finds a straightforward allocation system that minimizes wasted seats, while the latter finds a condition under which an additional stage improves student welfare. Our approach isdifferent from these papers’ in two directions: in this study, (i) we view the allocation schedule asa design variable, i.e., chosen by the mechanism designer, instead of a primitive, and (ii) to overcome deficiencies of the system, we restrict the preference domain instead of weakening normativerequirements or restricting the priority structure. A similar problem is also studied under different commitment assumptions (Manjunath and Turhan, 2016; Turhan, 2019; Doğan and Yenmez,2019). In their models, multiple mechanisms allocate school seats to students simultaneously, andstudents choose the most preferred school seat from assigned ones. That is, students participate
in all the stages and can dispose assigned seats. Since this assumption makes the problem essentially different from ours, the solution to recover non-wastefulness is also different from ours. For
instance, in Manjunath and Turhan (2016), a sufficient number of iterative re-matching processes
recover non-wastefulness.
The paper is structured as follows. Section 2 describes the model. Section 3 establishes theresults. Section 4 concludes. Proofs are in the Appendix.

2

Model

Let I and H be finite sets of agents and objects with |I|, |H| ≥ 2. For each object h ∈ H, qh ∈ N
is its capacity, or the number of available copies. Each agent i ∈ I has a linear preference
relation Pi over H ∪ {∅} and each object h ∈ H has a linear priority h over I ∪ {∅}, where forboth agents and objects, ∅ represents “being unassigned.” Let Ri denote the associated “at least
as good as” relation of agent i. We denote a preference profile by P = (Pi )i∈I and the sets of all
the possible preferences and preference profiles by P and P I . To exclude trivial cases, we assume
for each P ∈ P I , for each h ∈ H, there is i ∈ I such that hPi ∅.6 We call a tuple (I, H, P, q, ),
where q = (qh )h∈H and = (h )h∈H , an (assignment) problem. Throughout the paper, we fix(I, H, q, ) and denote a problem by a preference profile P .
A matching µ : I → H ∪ {∅} is a function such that the number of agents assigned an object
does not exceed its capacity, that is, for each h ∈ H, |µ−1 (h)| ≤ qh . A matching µ is individually
6

Technically, we can add any number of objects that are not preferred to being unassigned by any agents. Such
objects can be assigned at any stage (defined in Section 3), but they are not to be assigned to any agent as long as(ϕs ) are individually rational. Therefore, they do not affect the outcome of mechanisms/systems.

4

rational at P if for each i ∈ I, µ(i)Ri ∅ and i µ(i) ∅. That is, no agent is assigned an object thatis worse than being unassigned nor he is unacceptable for. A matching µ is non-wasteful at P if
there is no agent-object pair (i, h) such that |µ−1 (h)| < qh , i h ∅, and hPi µ(i). That is, there isno object being unassigned, even though an acceptable agent prefers it to what she is assigned.
A mechanism ϕ is a function that associates a matching to each problem, where its domain
is denoted by D = ×i∈I Di ⊆ P I . We denote the matching that ϕ selects for problem P by ϕ(P )and the object that ϕ assigns to i ∈ I at P by ϕi (P ). We say that a mechanism ϕ is individually
rational (non-wasteful) on D if the matching ϕ(P ) is individually rational (non-wasteful) for eachproblem P ∈ D. A mechanism ϕ is strategy-proof on D if for each i ∈ I, for each P ∈ D
and each Pi0 ∈ Di , ϕi (P )Ri ϕi (Pi0 , P−i ). That is, truthfully reporting his preference is alwaysa (weakly) dominant strategy for every agent. A mechanism ϕ is minimally non-bossy on
D if for each i ∈ I, for each P ∈ D and each Pi0 ∈ Di , if ϕi (P ) = ϕi (Pi0 , P−i ) = ∅, then{j ∈ I : ϕj (P ) = ∅} = {j ∈ I : ϕj (Pi0 , P−i ) = ∅}. That is, no unassigned agent can makeother agent unassigned by misreporting without being assigned an object. Remark 1 below showsthat this new property is weak enough in that it is implied by two general axioms. When ϕ isindividually rational, non-wasteful, strategy-proof, or minimally non-bossy on P I , we may omit
the part “on P I .”Remark 1. When ϕ is either non-bossy or stable, it is minimally non-bossy.
We consider a (sequential assignment) system Ψ = (ϕ1 , ..., ϕ|S| , σ), a combination of |S| ≥2 mechanisms and a schedule function. For each (I, H, q, ), a schedule function σ assigns
objects to stages {1, ..., |S|}. We denote the assigned stage for object h by σh (I, H, q, ) ∈{1, ..., |S|}, or simply σh . We note that the outcome of a schedule function does not depend on
the preference profile. This is because, in many real-life situations, the allocation schedule is fixed
before agents report their preferences and the designer commits to a predetermined schedule. To
focus on the design of the schedule function, we fix mechanisms (ϕs ) to be individually rationaland non-wasteful ones. For notational simplicity, for each I 0 ⊆ I and each H 0 ⊆ H, we denoteby P |I 0 , H 0 a restriction of a problem P to agents in I 0 and objects in H 0 (i.e., P |I 0 , H 0 denotes(I 0 , H 0 , (Pi |H 0 )i∈I 0 , (qh )h∈H 0 , (h |I 0 )h∈H 0 ) to be more precise). For each problem P , a system Ψassociates a matching Ψ(P ) (object Ψi (P ) ∈ H ∪ {∅} for agent i ∈ I) in the following sequential
procedure.7
Stage 1. Set I1 = I and H1 = {h ∈ H : σh = 1}. For each i ∈ I, let µ1 (i) = ϕ1i (P |I1 , H1 ).
s−1Stages s = 2, ..., |S|. Set Is = {i ∈ I : µ(i) = ∅} and Hs = {h ∈ H : σh = s}. For each i ∈ I, letϕs (P |I , H ) (i ∈ I )sssiµs (i) =.
µs−1 (i)(i ∈ I\Is )We allow at each stage s, |Is | ∈ {0, 1} or |Hs | ∈ {0, 1}. When |Is | = 1 or |Hs | = 1, the mechanism ϕs works inthe same way as |Is |, |Hs | ≥ 2. When |Is | = 0 or |Hs | = 0, to be precise, the stage s works as follows. If |Is | = 0,
let µ|S| (i) = µs−1 (i) for each i ∈ I and proceed to stage |S| + 1. If |Hs | = 0, let µs (i) = µs−1 (i) for each i ∈ I andproceed to stage s + 1.
7

5

Stage |S| + 1. For each i ∈ I, let Ψi (P ) = µ|S| (i).
Following Dur and Kesten (2019), we employ a crucial assumption on agent commitment. (i)At each stage, every agent chooses whether to participate in that stage,8 and (ii) when an object
is assigned to an agent, she cannot dispose that object and proceed to the next stage. Althoughstrong, such a commitment rule is actually adopted, for instance, in Turkish school choice system(Andersson et al., 2018). To benefit from using multiple stages, we restrict our attention on multishot schedule functions. A function σ is multi-shot if for each problem P , there are objects
h, h0 ∈ H such that σh 6= σh0 .9 We say that a system Ψ is individually rational (non-wasteful) on
D if the matching Ψ(P ) is individually rational (non-wasteful) for each problem P ∈ D. As an
incentive property in a sequential assignment, we consider straightforwardness, which is introducedby Andersson et al. (2018). A system Ψ is straightforward on D if for each i ∈ I, for each P ∈ D
and each Pi0 ∈ Di , Ψi (P )Ri Ψi (Pi0 , P−i ). That is, reporting true preference at all stages is always a(weakly) dominant strategy for every agent.

3

Results

We first see the result on the full domain D = P I .
Proposition 1. Let (ϕs ) be individually rational and non-wasteful mechanisms on P I . If σ ismulti-shot, ((ϕs ), σ) is neither non-wasteful nor straightforward on P I .
Motivated by this impossibility result, we characterize a preference domain where a multi-shot
system achieves non-wastefulness/straightforwardness. For |T | ∈ N, a preference profile P ∈ P I is(|T |-)tiered if objects H are partitioned to {HtP }t∈{1,...,|T |} such that for each h ∈ HtP and eachh0 ∈ HtP0 with t < t0 , for each i ∈ I with h, h0 Pi ∅, hPi h0 .10 We call the set of all possible tiered
preference profiles with |T | ≥ 2 as a tiered domain and denote it by P I (T ).
Roughly speaking, 2-tiered preferences are more “similar to each other” than 1-tiered preferences, and 10-tier is much more than 2-tier. However, by definition, P I (T ) also includes preference
profiles in which for each h ∈ HtP and each h0 ∈ HtP0 with t < t0 , there is no i ∈ I with h, h0 Pi ∅. In
such cases, tiered preferences are not similar to each other (see the next example).
Example 1. Agents and objects are I = {1, 2} and H = {a, b, c, d}. Table 2 shows several
preference profiles. In cases (vi) and (v), P1 and P2 are not similar to each other, but they are also
tiered.
8

An agent can choose not to participate in stage s by reporting that all objects to be allocated at stage s areworse than being unassigned.
9
When this does not hold, at problem P , using system ((ϕs ), σ) is equivalent to allocating all objects at somestage s via mechanism ϕs . Such an allocation is not what we intend.
10
A tiered preference domain in a matching environment is also studied in Kesten (2010) and Kesten and Kurino(2019). The definition in the current study is slightly different from theirs in that we do not restrict the number oftiers to be two. Akahoshi (2014) and Kandori et al. (2010) also study similar domains.

6

case
(i)
(ii)
(iii)
(vi)
(v)

P1
P2
|T |
{HtP }a, b, c, d d, c, b, a a, b, c, d b, a, d, c 2{a, b}, {c, d}a, b, c, d a, b, c, d 4 {a}, {b}, {c}, {d}
a, b
c, d
2
{a, b}, {c, d}a, b, c, da2{a}, {b, c, d}σ
σa = σb = 1, σc = σd = 2
σa = σb = 1, σc = σd = 2
σa = σb = 1, σc = σd = 2
σa = 1, σb =σc = σd = 2

Table 2: Example 1
Note: In columns 2 and 3, objects are ordered by preference relations. Objects below ∅ are omitted. Columns 3, 4, and 5 show examples of possible |T |’s, {HtP }’s, and σ’s that attain nonwastefulness/straightforwardness when mechanisms are appropriately chosen (e.g., the serial dictatorship).
Hyphen means no tier (nonexistence).

Our main result is the next proposition.
Proposition 2. The following three are equivalent.
(a) When (ϕs ) are individually rational and non-wasteful, there is a multi-shot σ where Ψ is nonwasteful on D ⊆ P I .
(b) When (ϕs ) are strategy-proof, minimally non-bossy, individually rational, and non-wasteful,
there is a multi-shot σ where Ψ is straightforward on D ⊆ P I .
(c) The domain is a subset of a tiered domain, that is, D ⊆ P I (T ).
As shown in the Appendix, the proof provides a specific class of schedule functions that maps
better tiers to earlier stages without reversal. Using this class joint with well-designed mechanisms,
the result can be extended as follows: when the designer wishes to use three or more stages,
straightforwardness and non-wastefulness are both achievable under sufficiently fine tiers.
Corollary 1. When P ∈ P I (T ) with |T | ≥ |S|, there is a straightforward and non-wasteful system
in which an object is allocated at each stage, that is, for each s ∈ {1, ..., |S|}, there is h ∈ H suchthat σh = s.
Finally, we relate our result with well-known mechanisms that are strategy-proof, individually
rational, and non-wasteful, such as agent/object-proposing deferred acceptance (aDA/oDA), top
trading cycles (TTC), and serial dictatorship (SD). Since oDA, TTC, and SD are non-bossy (Afacan
and Dur, 2017; Pápai, 2000; Svensson, 1999) and aDA is stable, Remark 1 leads to the following.
Corollary 2. When each ϕs is either aDA, oDA, TTC, or SD, there is a multi-shot σ where Ψ isstraightforward and non-wasteful on P I (T ).

4Conclusion

This paper searches for a solution to a puzzle in which a sequential assignment is not desirable
in theory but commonly used in practice. The main result gives a rationale for the practice of7

Chinese college admissions but makes clear that a sequential assignment system is always wastefuland non-straightforward in more diverse preference domains. This result provides a practicalinsight on when (not) to use a sequential assignment system.
It may also be valuable to collect evidence on whether the tiered profile is realistic. A positive
result further supports sequential assignment practice and vice versa. We leave it for future
research.

Declarations
Funding This work was supported by JST SPRING Grant Number JPMJSP2123 and the Keio
Economic Society.
Conflict of interest The author has no relevant financial or non-financial interests to disclose.

Appendix
Proof of Remark 1. “Non-bossy⇒minimally non-bossy” is immediate from the definitions. We
show “stable⇒minimally non-bossy.” Let ϕ be a stable mechanism and fix i ∈ I, P ∈ D, andPi0 ∈ Di such that ϕi (P ) = ϕi (Pi0 , P−i ) = ∅. Denote ϕ(P ) = µ and ϕ(Pi0 , P−i ) = µ0 . Immediatelyfrom the definition of a stable matching, in a problem without i, i.e., (I\{i}, H, (Pj )j∈I\{i} , q, ),µ and µ0 are also stable. The rural hospital theorem (Roth and Sotomayor, 1990) implies that{j ∈ I\{i} : µ(j) ∈ H} = {j ∈ I\{i} : µ0 (j) ∈ H}, i.e., {j ∈ I : µ(j) = ∅} = {j ∈ I : µ0 (j) = ∅}.
2
Hereafter, we refer individual rationality as IR, non-wastefulness as NW, strategy-proofness as SP,
minimal non-bossiness as MNB, and straightforwardness as SF. Also, for each tiered profile P ∈P I (T ), for each object h ∈ H, we denote the tier which the object belongs to by t(h) ∈ {1, ..., |T |}.
Proof of Proposition 1. Consider a problem with agents I = {1, 2}, objects H = {h, `},preference P1 : h, `, ∅ and P2 : `, h, ∅, capacity qh = q` = 2, and priority h , ` : 1, 2, ∅. Let |S| = 2
and (ϕ1 , ϕ2 ) be IR and NW. It is sufficient to show that σh 6= σ` leads to violation of NW/SF.
(i) (σh , σ` ) = (1, 2). I1 = {1, 2} and H1 = {h}. Since there is a unique IR and NW matching,
ϕ1 selects ϕ11 (P |{1, 2}, {h}) = ϕ12 (P |{1, 2}, {h}) = h. Thus, (Ψ1 (P ), Ψ2 (P )) = µ = (h, h). µ
is wasteful because |µ−1 (`)| = 0 < 2 = q` , 2 ` ∅, and `P2 µ(2). Moreover, if agent 2 reports
P20 : `, ∅, h, by IR and NW of (ϕ1 , ϕ2 ), (ϕ11 (P1 , P20 |{1, 2}, {h}), ϕ12 (P1 , P20 |{1, 2}, {h})) = (h, ∅) andϕ22 (P1 , P20 |{2}, {`}) = `. It follows (Ψ1 (P1 , P20 ), Ψ2 (P1 , P20 )) = (h, `) and Ψ2 (P1 , P20 )P2 Ψ2 (P ). Ψ is
not SF.

8

(ii) (σh , σ` ) = (2, 1). I1 = {1, 2} and H1 = {`}. The same argument as case 1 leads (Ψ1 (P ), Ψ2 (P )) =µ0 = (`, `). µ0 is wasteful because |µ0−1 (h)| = 0 < 2 = qh , 1 h ∅, and hP1 µ0 (1). For P10 : h, ∅, `,(Ψ1 (P10 , P2 ), Ψ2 (P10 , P2 )) = (h, `) and Ψ2 (P10 , P2 )P1 Ψ2 (P ). Ψ is not SF.
2
Proof of Proposition 2.
(c)⇒(a): Suppose (c) is true and (ϕs ) are IR and NW. Let σ be such that for any t, t0 ∈{1,...,|T|}with t ≤ t0 , for each h ∈ HtP and each h0 ∈ HtP0 , σh ≤ σh0 . Denote Ψ(P ) = µ. Take h ∈ H suchthat |µ−1 (h)| < qh and i ∈ I such that i h ∅ arbitrarily. If there are no such pairs, µ is NW.
Suppose there is at least one such pair and show µ(i)Ri h, i.e., µ(i)Pi h or µ(i) = h.
case 1.1. i ∈/ Iσh . For some s < σh , i is assigned an object µs (i) = ϕsi (P |Is , Hs ) ∈ Hs . Ift(µs (i)) ≥ t(h), since σµs (i) = s < σh , it contradicts to (c). Hence, t(µs (i)) < t(h) implies µs (i)Pi h.
We have µ(i) = µ|S| (i) = µs (i) and µ(i)Pi h.
case 1.2. i ∈ Iσh . Since ϕσh is NW, ϕσi h (P |Iσh , Hσh )Ri h. If ϕσi h (P |Iσh , Hσh ) = ∅, ∅Pi h.
Since (ϕσh +1 , ..., ϕ|S| ) are all IR, µ(i)Ri ∅Pi h. Otherwise, i ∈/ Iσh +1 implies µσh +1 (i) = µσh (i) =ϕσi h (P |Iσh , Hσh ). Repeating this, we have µ(i) = µ|S| (i) = ϕσi h (P |Iσh , Hσh ) and µ(i)Ri h.
(a)⇒(c): We show its contrapositive “not (c)⇒not (a).” Suppose P ∈/ P I (T ). Fix a multi-shot σ
and IR and NW (ϕs ) arbitrarily. We construct a problem, i.e., q and , so that Ψ(P ) is wasteful.
case 2.1. Suppose that there are s, s0 ∈ {1, ..., |S|} with s < s0 , h, ` ∈ Hs , h0 , `0 ∈ Hs0 , and i, i0 ∈ Isuch that h, `0 Pi ∅ and `, h0 Pi0 ∅. We do not exclude h = ` or h0 = `0 , but we exclude hPi `0 Pi ∅and `Pi0 h0 Pi0 ∅, i.e., since the case is symmetric, we specify the case to `0 Pi hPi ∅. This is because,
if for any h, ` ∈ Hs and any h0 , `0 ∈ Hs0 , for any i, i0 ∈ I with h, `0 Pi ∅ and `, h0 Pi0 ∅, hPi `0 and`Pi0 h0 , we immediately have P ∈ P I (T ) by setting {HtP } = {Hs }, i.e., for each t ∈ {1, ..., |T |},HtP := {h ∈ H : σh = t} = Ht . Let (i) i h ∅ and i `0 ∅, (ii) for each j ∈ I\{i}, ∅ h j and∅ `0 j, and (iii) for each k ∈ H\{h, `0 }, ∅ k i. At each stage r ∈ {1, ..., s−1}, by (iii), ϕr , which isIR, never assigns any k ∈ Hr ( H\{h, `0 } to i, thus i ∈ Is . At stage s, by (ii), ϕs , which is IR, neverassigns h ∈ Hs to any j ∈ Is \{i} and by (iii), it never assigns any k ∈ Hs \{h} ( H\{h, `0 } to i.
Since hPi ∅, ϕs , which is NW, assigns h ∈ Hs to i ∈ Is , thus, ϕsi (P |Is , Hs ) = h. We have Ψi (P ) = h.
0
At stage s0 , by (ii), ϕs , which is IR, never assigns `0 ∈ Hs0 to any j ∈ Is0 ( I\{i}, thus for each0j ∈ Is0 , ϕsj (P |Is0 , Hs0 ) 6= `0 , i.e., Ψj (P ) 6= `0 . Ψ(P ) = µ is wasteful because |µ−1 (`0 )| = 0 < q`0 ,i `0 ∅, and `0 Pi µ(i).
case 2.2. Suppose that there are no s, s0 ∈ {1, ..., |S|} with s < s0 , h, ` ∈ Hs , h0 , `0 ∈ Hs0 , andi, i0 ∈ I such that h, `0 Pi ∅ and `, h0 Pi0 ∅, including the cases with h = ` or h0 = `0 . That is, forany s, s0 ∈ {1, ..., |S|} with s < s0 , there is at most one i(s, s0 ) ∈ I such that h, h0 Pi(s,s0 ) ∅. If forany s, s0 , there is no i(s, s0 ), we immediately have P ∈ P I (T ) by setting {HtP } = {Hs }. Thus, we
assume that there is at least one pair (s, s0 ) such that i(s, s0 ) ∈ I.
|M |case 2.2.1. For each |M | ∈ {3, ..., |S|}, there are no {i1 , ..., i|M | } ⊆ I and {{hm , h0m }}m=1 ⊆ Hsuch that (i) for each m ∈ {1, ..., |M |}, σhm = σh0m and for any m, m0 ∈ {1, ..., |M |}, σhm 6= σhm0 ,9and (ii) for each m ∈ {1, ..., |M |}, h0m+1 Pim hm where h0m+1 = h01 . We do not exclude the cases
where for each m, hm = h0m . To show that P ∈ P I (T ), we first see that there is s̄ ∈ {1, ..., |S|}such that for each h ∈ Hs̄ , there is no i ∈ I and no h0 ∈/ Hs̄ with h0 Pi h. Suppose that there areno such s̄, i.e., for each s ∈ {1, ..., |S|}, there is h ∈ Hs such that there is i ∈ I and h0 ∈/ Hs with|M|
h0 Pi h. Then, we can construct {i1 , ..., i|M | } ⊆ I and {{hm , h0m }}m=1 ⊆ H by the following steps.
Step 1. Pick h ∈ H1 such that there is i ∈ I and h0 ∈/ H1 with h0 Pi h. Let i1 = i, h1 = h, andh02 = h0 .
Steps m = 2, ..., |S|. Pick h from the same stage as h0m ’s such that there is i and h0 in anotherstage with h0 Pi h. Let im = i, hm = h, and h0m+1 = h0 .
By assumption, at each step m, σh0m+1 ∈/ {σh1 , ..., σhm−1 }. However, since |S| is finite, at step |S|,0
there is no h|S|+1 such that σh0|S|+1 ∈/ {σh1 , ..., σh|S|−1 }, i.e., either σh0|S|+1 = σh0|S| or |S| = s̄. Hence,
there is s̄ ∈ {1, ..., |S|}. A partition {H1P , H2P } = {Hs̄ , H\Hs̄ } is 2-tier preference, thus P ∈ P I (T ).
|M |case 2.2.2. For some |M | ∈ {3, ..., |S|}, there are {i1 , ..., i|M | } ⊆ I and {{hm , h0m }}m=1 ⊆ H
described above. We show that Ψ(P ) is wasteful. By assumption, there is m ∈ {1, ..., |M |} suchthat σhm < σh0m+1 and for im ∈ I, h0m+1 Pim hm . Let (i) qhm = qh0m+1 = 1, (ii) im hm ∅ andim h0m+1 ∅, (iii) for each j ∈ I\{im }, ∅ hm j and ∅ h0m+1 j, and (iv) for each k ∈ H\{hm , h0m+1 },∅ k im . By the same argument as case 2.1, we have Ψim (P ) = ϕσhm (P |Iσhm , Hσhm ) = hm , andΨ(P ) = µ is wasteful because |µ−1 (h0m+1 )| = 0 < qh0m+1 , im h0m+1 ∅, and h0m+1 Pim µ(im ).
(c)⇒(b): Suppose (c) is true and (ϕs ) are SP, MNB, IR, and NW. Let σ be such that for any
t, t0 ∈{1,...,|T|} with t ≤ t0 , for each h ∈ HtP and each h0 ∈ HtP0 , σh ≤ σh0 . Denote Ψ(P ) = µ. Fix a
problem and take i ∈ I arbitrarily. To lead a contradiction, suppose there is Pi0 ∈ P(T ) such that
Ψi (Pi0 , P−i )Pi Ψi (P ). Denote the agents at stage s under profile P by Is and under (Pi0 , P−i ) by Is0 .
case 3.1. Ψi (P ) = ∅, i.e., for each s ∈ {1, ..., |S|}, ϕsi (P |Is , Hs ) = ∅. Ψi (Pi0 , P−i )Pi Ψi (P ) implies00Ψi (Pi0 , P−i ) 6= ∅, i.e., there is s0 ∈ {1, ..., |S|} such that for each s00 < s0 , ϕsi (Pi0 , P−i |Is0 00 , Hs00 ) =00
0∅ and Ψi (Pi0 , P−i ) = ϕsi (Pi0 , P−i |Is0 0 , Hs0 ) ∈ Hs0 . Since for each s00 < s0 , ϕsi (P |Is00 , Hs00 ) =0000
ϕsi (Pi0 , P−i |Is0 00 , Hs00 ) = ∅ , MNB of ϕs implies Is00 = Is0 00 , i.e., by induction, Is0 = Is0 0 . Ψi (Pi0 , P−i )Pi Ψi (P )000
implies ϕsi (Pi0 , P−i |Is0 , Hs0 )Pi ϕsi (P |Is0 , Hs0 ), a contradiction to SP of ϕs .
case 3.2. Ψi (P ) 6= ∅, i.e., there is s ∈ {1, ..., |S|} such that Ψi (P ) = ϕsi (P |Is , Hs ) ∈ Hs . If
Ψi (Pi0 , P−i ) = ∅, Ψi (Pi0 , P−i )Pi Ψi (P ) implies ∅Pi ϕsi (P |Is , Hs ), a contradiction to that ϕs is IR. Thus,0Ψi (Pi0 , P−i ) 6= ∅, i.e., there is s0 ∈ {1, ..., |S|} such that Ψi (Pi0 , P−i ) = ϕsi (Pi0 , P−i |Is0 0 , Hs0 ) ∈ Hs0 .
0case 3.2.1. s < s0 . By the construction of σ, we have t(ϕsi (P |Is , Hs )) < t(ϕsi (Pi0 , P−i |Is0 0 , Hs0 )).
00Since each ϕs is IR, ϕsi (P |Is , Hs ), ϕsi (Pi0 , P−i |Is0 0 , Hs0 )Pi ∅ implies ϕsi (P |Is , Hs )Pi ϕsi (Pi0 , P−i |Is0 0 , Hs0 ),i.e., Ψi (P )Pi Ψi (Pi0 , P−i ), a contradiction.
00
00
00
case 3.2.2. s ≥ s0 . Since for each s00 < s0 , ϕsi (P |Is00 , Hs00 ) = ϕsi (Pi0 , P−i |Is0 00 , Hs00 ) = ∅ , MNB of ϕs
00
implies Is00 = Is0 00 , i.e., by induction, Is0 = Is0 0 . Ψi (Pi0 , P−i )Pi Ψi (P ) implies ϕsi (Pi0 , P−i |Is0 , Hs0 )Pi ϕsi (P |Is0 , Hs0 ),0a contradiction to SP of ϕs .
(b)⇒(c): We show its contrapositive “not (c)⇒not (b).” Suppose P ∈/ P I (T ). Fix a multi-shot σ
10and (ϕs ) satisfying SP, MNB, IR, and NW arbitrarily. We construct a problem, i.e., q and , sothat Ψ is not SF. By the argument in (a)⇒(c), it is sufficient to see the following two cases.
case 4.1. Consider the same problem as case 2.1. That is, there are s, s0 ∈ {1, ..., |S|} withs < s0 , h, ` ∈ Hs , h0 , `0 ∈ Hs0 , and i ∈ I such that `0 Pi hPi ∅. Let (i) i h ∅ and i `0 ∅, (ii)for each j ∈ I\{i}, ∅ h j and ∅ `0 j, and (iii) for each k ∈ H\{h, `0 }, ∅ k i. Since (ϕs )are IR and NW, it is obvious that Ψi (P ) = h. By misreporting Pi0 in which `0 Pi0 ∅Pi0 h, i obtains
0
ϕsi ((Pi0 , P−i )|Is0 , Hs ) = ∅ and ϕsi ((Pi0 , P−i )|Is0 0 , Hs0 ) = `0 , hence Ψi (Pi0 , P−i ) = `0 . Ψ is not SF.
case 4.2. Consider the same problem as case 2.2.2. That is, there is {i1 , ..., i|M | } ⊆ I and|M |{{hm , h0m }}m=1 ⊆ H such that (i) for each m ∈ {1, ..., |M |}, σhm = σh0m and for any m, m0 ∈{1, ..., |M |}, σhm 6= σhm0 , and (ii) for each m ∈ {1, ..., |M |}, h0m+1 Pim hm where h0m+1 = h01 .
There is m ∈ {1, ..., |M |} such that σhm < σh0m+1 and for im ∈ I, h0m+1 Pim hm . Let (i) qhm =qh0m+1 = 1, (ii) im hm ∅ and im h0m+1 ∅, (iii) for each j ∈ I\{im }, ∅ hm j and ∅ h0m+1 j,and (iv) for each k ∈ H\{hm , h0m+1 }, ∅ k im . By the same argument as case 4.1, we haveΨim (P ) = ϕσhm (P |Iσhm , Hσhm ) = hm and for misreporting h0m+1 Pi0m ∅Pi0m hm , Ψim (Pi0m , P−im ) =σ 0
2
ϕ hm+1 ((Pi0m , P−im )|Iσ0 h0 , Hσh0 ) = h0m+1 . Ψ is not SF.
m+1

m+1

References
Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2005): “The New York City HighSchool Match,” American Economic Review Papers and Proceedings, 95, 364–367.
Abdulkadiroğlu, A. and T. Sönmez (2003): “School Choice: A Mechanism Design Approach,”American Economic Review, 93, 729–747.
Afacan, M. O. and U. M. Dur (2017): “When preference misreporting is Harm [less] ful?”
Journal of Mathematical Economics, 72, 16–24.
Akahoshi, T. (2014): “A necessary and sufficient condition for stable matching rules to be
strategy-proof,” Social Choice and Welfare, 43, 683–702.
Andersson, T., U. Dur, S. Ertemel, and O. Kesten (2018): “Sequential school choice withpublic and private schools,” Working paper.
Balinski, M. and T. Sönmez (1999): “A Tale of Two Mechanisms: Student Placement,” Journalof Economic Theory, 84, 73–94.
Doğan, B. and M. B. Yenmez (2019): “Unified versus divided enrollment in school choice:Improving student welfare in Chicago,” Games and Economic Behavior, 118, 366–373.
——— (2023): “When does an additional stage improve welfare in centralized assignment?” Economic Theory, forthcoming.
11

Dur, U. and O. Kesten (2019): “Sequential versus simultaneous assignment systems and two
applications,” Economic Theory, 68, 251–283.
Ekmekci, M. and M. B. Yenmez (2019): “Common enrollment in school choice,” Theoretical
Economics, 14, 1237–1270.
Kandori, M., F. Kojima, and Y. Yasuda (2010): “Tiers, Preference Similarity, and the Limits
on Stable Partners,” Working paper.
Kesten, O. (2010): “School Choice with Consent,” Quarterly Journal of Economics, 125(3),1297–1348.
Kesten, O. and M. Kurino (2019): “Strategy-proof improvements upon deferred acceptance:
A maximal domain for possibility,” Games and Economic Behavior, 117, 120–143.
Manjunath, V. and B. Turhan (2016): “Two school systems, one district: What to do whena unified admissions process is impossible,” Games and Economic Behavior, 95, 25–40.
Pápai, S. (2000): “Strategyproof Assignment by Hierarchical Exchange,” Econometrica, 68, 1403–
1433.
Roth, A. E. and M. A. O. Sotomayor (1990): Two-sided Matching: A Study in Gametheoretic Modeling and Analysis, Cambridge: Cambridge University Press.
Svensson, L.-G. (1999): “Strategy-proof Allocation of Indivisible Goods,” Social Choice andWelfare, 16, 557–567.
Turhan, B. (2019): “Welfare and incentives in partitioned school choice markets,” Games andEconomic Behavior, 113, 199–208.

12