## Controlled School Choice with Hard Bounds:

## Existence of Fair and Non-wasteful Assignments

### Kentaro Tomoeda

^{∗}

### December 21, 2012

Abstract

In the model of controlled school choice employing type specific constraints with lower bounds and upper bounds, it was shown that the set of feasible and fair assignments may be empty. This paper proposes a sufficient condition on a schools’ priority profile for the existence of feasible assignments that are fair and non-wasteful. The condition is that the priority orders for the same type students are common across schools. We introduce an algorithm called Controlled Student Proposing Deferred Acceptance Algorithm with Reproposal (CDAAR) which finds such an assignment under that sufficient condition. For incentives of students, it is shown that CDAAR is not always dominant strategy incentive compatible under the sufficient condition.

### 1 Introduction

In the United States, affirmative action is an important method to create a diverse environment for students in schools or workers in firms. In the context of school choice, controlled school choice programs which try to balance the racial or socioe- conomic status at schools as well as to expand students’ choices are implemented. There are many examples of school boards that implemented controlled school choice programs such as Boston Public Schools, Educational Option in New York City high school match, Miami-Dade County Public Schools, or Chicago Public Schools.

In the literature of affirmative actions in school choice problems, Abdulkadiro˘glu and S¨onmez (2003) and Abdulkadiro˘glu (2005) considered type-specific quotas as maximum numbers of students from each type who can be admitted to the schools.

∗Harvard University, tomoeda@fas.harvard.edu.

Kojima (2010) considers a controlled school choice problem by incorporating the quota for majority students, and Hafalir, Yenmez and Yildirim (2011) analyzes it by employing both the majority quota and minority reserves. Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011) analyze the problem by introducing lower bounds of type specific constraints that schools must admit students of a certain type and upper bounds of type specific constraints that schools cannot admit more students of a certain type than the bounds.

When we look at real-life instances of controlled school choice programs, there are some cases which require not only maximum quotas but the range of numbers or percentages of certain type students for schools. Educational Option in New York City and the Jefferson County School District are the examples. Therefore, the model studied in Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011) is applicable and captures important features of controlled school choice problems. However, there is a difficulty in the model which has both lower and upper bounds for type specific constraints. By naturally extending the fairness notion to the model, they find that there may not exist feasible and fair assignments. In order to cope with this problem, Abdulkadiro˘glu and Ehlers (2008) weakened the fairness and non-wasteful concepts to show the existence of the desirable assignments. Ehlers, Hafalir, Yenmez and Yildirim (2011) give another solution; they interpret the constraints as soft bounds and find fair and non-wasteful assignments.

In this research, I will analyze the same model as Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011) and give a sufficient condi- tion on a schools’ priority profile for the existence of feasible, fair and non-wasteful assignments. The sufficient condition I propose is consistency of priority orders for the same type students across schools. As I discuss in Section 3, while this condition does not seem to hold in some situations, it can be satisfied if school districts can al- ter the classification of types of students or priority structures. Therefore, the main result suggests that even without weakening the solution concepts or changing the interpretation of constraints, it may be possible to implement fair and non-wasteful assignments.

The rest of the paper proceeds as follows. Section 2 introduces the model. Section 3 presents the main results and section 4 considers the incentive properties of the algorithm I propose. Section 5 concludes.

### 2 Model: Controlled School Choice

I will consider a controlled school choice problem which was studied by Abdulka- diro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011). A con-

trolled school choice problem is written as (S, C, (qc)c∈C^{, P}S^{,}≻C^{, T, τ,}(q^{T}_{c}, q^{T}_{c})c∈C)
which consists of the following elements.

1. a finite set of students S = {s1^{, ..., s}n};
2. a finite set of schools C = {c1^{, ..., c}m};

3. a capacity vector q = (q_{c}1, ..., q_{c}_{m}), where q_{c} is the capacity of school c ∈ C or
the number of seats in c ∈ C;

4. a students’ preference profile PS = (Ps1, ..., P_{s}_{n}), where Psis the strict prefer-
ence relation of student s ∈ S over C, i.e. cPsc^{′} means that student s strictly
prefers school c to school c^{′};

5. a schools’ priority profile ≻_{C}= (≻_{c}1, ...,≻cm^{), where ≻}c is the strict priority
ranking of school c ∈ C over S; s ≻c ^{s}^{′} means that student s has higher
priority than student s^{′} to be enrolled at school c;

6. a type space T = {t_{1}, ..., tk};

7. a type function τ : S → T , where τ (s) is the type of student s;
8. for each school c, two vectors of type specific constraints q^{T}

c ^{= (q}
t1

c ^{, ..., q}
t_{k}
c ^{)}

and q^{T}_{c} = (q^{t}_{c}^{1}, ..., q^{t}_{c}^{k}) such that q_{c}^{t} ≤ q^{t}_{c} ≤ qc for all t ∈ T , and ^{P}_{t∈T} q^{t}_{c} ≤
q_{c} ≤^{P}_{t∈T} q^{t}_{c}.

The difference from other specifications of controlled school choice models comes
from the last element. q^{t}

c is the minimal number of slots that school c must allocate
to students of type t and q^{t}_{c} is the maximal number of slots that school c is allowed
to allocate to students of type t. We call (q^{t}_{c}, q^{t}_{c}) the floor and the ceiling for type
tat school c.

An assignment µ is a function from the set C ∪ S to the set of all subsets of C∪ S such that

1. µ(s) ∈ C for every student s;

2. |µ(c)| ≤ qc and µ(c) ⊆ S for every school c; 3. µ(s) = c if and only if s ∈ µ(c).

Here we have another notation: µ^{t}(c) denotes the students of type t that are as-
signed to school c, i.e., µ^{t}(c) = µ(c) ∩ St with St≡ {s ∈ S|τ (s) = t}.

A set of students S^{′} ⊆ S respects (capacity and controlled choice) constraints
at school c if |S^{′}| ≤ qc and for every type t ∈ T , q^{t}_{c} ≤ |{s ∈ S^{′}|τ (s) = t}| ≤ q^{t}_{c}.
An assignment µ respects constraints if for every school c, µ(c) respects constraints
at c, i.e., |µ(c)| ≤ qc holds and q^{t}_{c} ≤ |µ^{t}(c)| ≤ q^{t}_{c} holds for every type t ∈ T .
An assignment µ is legally feasible if µ respects constraints and every student is
assigned to a school. Ehlers, Hafalir, Yenmez and Yildirim (2011) propose another
way to interpret the type specific constraints as soft bounds; schools can admit

fewer students than their floors or more than their ceilings but they give highest priority to types who do not fill their floors, medium priority to types who fill their floors but not ceilings, and lowest priorities to types who fill their ceilings. Since positive results are already shown under the idea of soft bounds, we will stick to the interpretation of constraints as hard bounds, i.e. an assignment µ is feasible only if µ respects constraints.

Even when there are enough seats for students in total, a controlled school choice problem (with hard bounds) may not have a feasible solution when there are less students of a certain type than the sum of the floors for that type for all schools or there are more students of a certain type than the sum of the ceilings for that type for all school. Therefore, as in Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011), I will only analyze problems whose legal constraints ensures the existence of a legally feasible assignment.

Next, let us introduce desirable properties of feasible assignments in the con- trolled school choice problem. The first property in Definition 1 is about non- wastefulness as in Balinski and S¨onmez (1999), but since we have type specific constraints, students are allowed to claim an empty slot only when the legal con- straints will not be violated when the student is assigned a slot.

Definition 1. Student s justifiably claims an empty slot at school c under the feasible assignment µ if

(nw1) cPsµ(s) and |µ(c)| < qc,
(nw2) q^{τ(s)}_{µ(s)}<|µ^{τ(s)}(µ(s))|, and
(nw3) |µ^{τ(s)}(c)| < q^{τ(s)}c .

A feasible assignment µ is non-wasteful if there is no student who justifiably claims an empty slot at any school.

(nw1) means student s prefers an empty slot at school c to her own assignment, and (nw2) and (nw3) mean that legal constraints are not violated when s is assigned the empty slot without changing other students’ assignments.

The second property is about no-envy, which is also widely used in the context of school choice. But due to the structure of controlled school choice, as in Definition 1, even when a student prefers a school to her own and there is a student with lower priority in the school, the envy is not justified if the student’s move violates the legal constraints. Definition 2 formally states the condition for a student to have justified envy.

Definition 2. Student s justifiably envies student s^{′} at school c under the feasible
assignment µ if there exists another feasible assignment µ^{′} such that

(f1) µ(s^{′}) = c, cPsµ(s) and s ≻cs^{′},

(f2) µ^{′}(s) = c, µ^{′}(s^{′}) 6= c, and µ^{′}(ˆs) = µ(ˆs) for all ˆs∈ S \ {s, s^{′}}.

A feasible assignment µ is fair across types (or fair) if there is no student who justifiably envies any other student.

(f1) is the normal condition which says that there is a student who has lower
priority than s at school c which s prefers to her own assignment. (f2) means that
(µ(c) \ {s^{′}}) ∪ {s} respects the controlled choice constraints at school c and student
s^{′} can be assigned to school c^{′} = µ^{′}(s^{′}) such that (µ(c^{′}) \ {s}) ∪ {s^{′}} respects the
controlled choice constraints at c^{′}.

There is a weaker version of fairness where envy is justified only if both the envying student and the envied student are of the same type.

Definition 3. Student s justifiably envies student s^{′} of the same type at school c
under the feasible assignment µ if

(f1*) µ(s^{′}) = c, cPsµ(s) and s ≻c ^{s}^{′}, and
(f2*) τ (s) = τ (s^{′}).

A feasible assignment µ is fair for same types if there is no student who justifiably envies any other same type student.

(f1*) is the same condition as (f1). Since student s and student s^{′} are of the
same type by (f2*), the assignment is still feasible when students s and s^{′} exchange
their slots. Namely, we can make µ^{′} in a way that µ^{′}(s) = µ(s^{′}), µ^{′}(s^{′}) = µ(s), and
µ^{′}(ˆs) = µ(ˆs) for all ˆs∈ S \ {s, s^{′}}.

### 3 Existence of Fair and Non-wasteful Assign-

### ments

Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011) showed two impossibility results on compatibility of legal constraints and desirable properties such as fairness and non-wastefulness.

Theorem 1. (Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011))

(1) The set of feasible assignments that are fair across types may be empty in a controlled school choice problem.

(2) The set of feasible assignments that are both fair for same types and non- wasteful may be empty in a controlled school choice problem.

I will give counterexamples for each of (1) and (2) used in the proof of the theorems in Abdulkadiro˘glu and Ehlers (2008) and Ehlers, Hafalir, Yenmez and Yildirim (2011).

Example 1. (Ehlers, Hafalir, Yenmez and Yildirim (2011)) Consider the following
problem consisting of schools {c_{1}, c_{2}, c_{3}} and {s1^{, s}2^{, s}3}. Students s1 ^{and s}2 ^{are of}

type t_{1} and student s_{3}is of type t_{2}. The schools’ priorities and students’ preferences
are in the following table.

≻c1 ≻c2 ≻c3 Ps1 Ps2 Ps3

s_{2} s_{2} s_{1} c_{2} c_{3} c_{2}
s_{1} s_{1} s_{2} c_{3} c_{2} c_{3}
s_{3} s_{3} s_{3} c_{1} c_{1} c_{1}

capacities 1 1 1

ceiling for t_{1} 1 1 1
floor for t_{1} 1 0 0
ceiling for t_{2} 1 1 1
floor for t2 0 0 0
There are four feasible assignments in Example 1:

µ_{1} =

Ã c_{1} c_{2} c_{3}
s_{1} s_{2} s_{3}

!
, µ_{2} =

Ã c_{1} c_{2} c_{3}
s_{1} s_{3} s_{2}

! ,

µ_{3} =

Ã c_{1} c_{2} c_{3}
s_{2} s_{3} s_{1}

!
, µ_{4} =

Ã c_{1} c_{2} c_{3}
s_{2} s_{1} s_{3}

! ,

but there is a student who justifiably envies another student in each assignment.
Example 2. (Abdulkadiro˘glu and Ehlers (2008)) Consider the following problem
consisting of schools {c_{1}, c_{2}, c_{3}} and {s_{1}, s_{2}}. Students s_{1} and s_{2} are of the same
type t. The schools’ priorities and students’ preferences are in the following table.

≻c1 ≻c2 ≻c3 P_{s}1 P_{s}2

s_{2} s_{2} s_{1} c_{2} c_{3}
s_{1} s_{1} s_{2} c_{3} c_{2}
c_{1} c_{1}

capacities 2 2 2

ceiling for t 2 2 2

floor for t 1 0 0

There are four feasible assignments in Example 2:

µ_{1}=

Ã c_{1} c_{2} c_{3}
s_{1} s_{2} ∅

!
, µ_{2} =

Ã c_{1} c_{2} c_{3}
s_{1} ∅ s_{2}

! ,

µ_{3}=

Ã c_{1} c_{2} c_{3}
s_{2} ∅ s_{1}

!
, µ_{4} =

Ã c_{1} c_{2} c_{3}
s_{2} s_{1} ∅

! ,

but there is a student who justifiably envies another student or justifiably claims an empty slot in each assignment.

As is seen in above examples, the non-existence of such assignments seems to
stem from the properties of schools’ priority orderings in which the orders for two
students of the same type are not consistent across schools. In both examples, s_{2}
has a higher priority than s_{1} at c_{2} while s_{1} has a higher priority than s_{2} at c_{3}. If s_{2}
had a higher priority than s_{1} at c_{3}, then µ_{2} would be an assignment which is both
fair across types and non-wasteful in both examples.

From this point of view, we could conjecture that consistency of priority orders for the same type students across schools might resolve the emptiness of the set of desirable assignments. In order to capture this idea, define a condition on a school’s priority profile.

Definition 4. A schools’ priority profile ≻_{C} has a common priority order for type
t∈ T if

s≻c s^{′} ⇔ s ≻c^{′} ^{s}^{′}

for any c, c^{′} ∈ C and s, s^{′} such that τ (s) = τ (s^{′}) = t.

The main theorem shows that the condition that a schools’ priority profile ≻C

has a common priority order for every type t ∈ T is sufficient for the existence of feasible assignments which are both fair and non-wasteful. This condition may be strong and hard to be satisfied when the classification of types is coarse. For instance, if the type set is {high income, low income} and there is a priority for students who live in each school’s walk zone, priority orders for high income students will differ across schools in general. However, this can be modified by making a finer type classification, {high income, low income} × {c1’s walk zone, c2’s walk zone,...}. In this case, if there are no other priority requirements, it is natural to use a single tie breaking among students with the same priority and the condition of having a common priority order for every type is satisfied. Another possibility is changing priority structures. If the walk zone priority is abolished or replaced by priority that is given to (a subset of) high or low income students, the condition is satisfied. Therefore, with the modification of type division rules or priority structures, this condition is not difficult to be satisfied in reality.

This existence is proved by a constructive way. Abdulkadiro˘glu and Ehlers (2008) proposed an algorithm Controlled Student Proposing Deferred Acceptance Algorithm (CDAA) to show that the set of feasible assignments that are fair for the same type and constrained non-wasteful is not empty. I will propose an algorithm called Controlled Student Proposing Deferred Acceptance Algorithm with Repro- posal (CDAAR), which adds reproposal steps to the original CDAA.

Controlled Student Proposing Deferred Acceptance Algorithm with Re- proposal

Start: Construct a strict ordering on the set of students f : S → {1, ..., n}.
Students are allowed to make proposals to schools in the order of f^{−1}(1),
f^{−}^{1}(2),..., f^{−}^{1}(n). We will always define a tentative assignment ν which al-
lows students to be unassigned. The tentative assignment is such that it is
possible to allocate the unassigned students to schools such that the resulting
assignment is feasible. Let F denote the set of all feasible assignments and
ν_{0} be the empty assignment, i.e. ν_{0}(s) = s for all s ∈ S. For each school c
and each student s, s is either in the rejected status for c or the non-rejected
status for c. At the start of the algorithm, every student is in the non-rejected
status for every school c.

1: Let student f^{−1}(1) apply to the school which is ranked first under P_{f}−1_{(1)}, say
c_{1}. If there is some µ ∈ F such that µ(f^{−}^{1}(1)) = c_{1}, then set ν_{1}(f^{−}^{1}(1)) = c_{1}
and ν1(s) = ν0(s) = s for all s ∈ S \ {f^{−}^{1}(1)}. Otherwise f^{−}^{1}(1)’s status for
c_{1} changes to the rejected status and we set ν_{1} = ν_{0}.

...

k: If there is a student who is unassigned or whose assigned school is not the most preferable one among the schools for which she is in the non-rejected status, let s be the student with minimal number f (s) among those students. Let c be the school which is most preferred under Ps among the schools for which sis in the non-rejected status.

(1) If there is µ ∈ F such that µ(s) = c and µ(s^{′}) = ν_{k−1}(s^{′}) for all students
s^{′} such that ν_{k−1}(s^{′}) 6= s^{′}, then student s justifiably claims an empty slot
at school c under ν_{k−1}. Then we set νk(s) = c and νk(s^{′}) = ν_{k−1}(s^{′}) for
all s^{′} ∈ S \ {s}.

(2) If (1) is not true but there is a student such that student s justifiably
envies that student at school c under ν_{k−1}, then let s^{′} be the student
who has the lowest priority under ≻c among students who are justifiably
envied by student s at school c under ν_{k−1}. Then we set ν_{k}(s) = c,
ν_{k}(s^{′}) = s^{′} and νk(s^{′′}) = ν_{k−1}(s^{′′}) for all s^{′′} ∈ S \ {s, s^{′}}, i.e. school c
rejects s^{′} and tentatively admits s.

(3) If (1) and (2) are not true, we set ν_{k}(s) = ν_{k−1}(s) and student s’s status
for c changes to the rejected status.

Not only student s who proposed to a school in step k but other students may

change their status for some schools. We say a student ˆsis free at µ if

¯

¯

¯{^{s}^{∈ S}τ(ˆs)|f (s) > f (ˆs) and µ(s) = s} ∪ {ˆs}^{¯}^{¯}_{¯}

> ^{X}

c∈C

max^{n}0, q^{τ(ˆ}_{c} ^{s)}− |µ^{τ(ˆ}^{s)}(c) \ {ˆs}|^{o}

Otherwise, ˆsis unfree at µ. A student ˆs’s status for school ˆcchanges from the
rejected status to the non-rejected status at the end of step k if ˆswas in the
rejected status for school ˆc at ν_{k−1} and one of the following conditions holds
(we call them reproposal conditions):

(i) ˆs∈ S_{τ(s)}, f (ˆs) > f (s) and ˆswas unfree at ν_{k−1} but became free at ν_{k}.
(ii) ˆs∈ S_{τ(s)}, f (ˆs) < f (s) and ˆc= ν_{k}(s).

(iii) |νk^{(ˆ}^{c)| < q}ˆc ^{and ˆ}^{s} has the highest priority for ˆc among students who
justifiably claim an empty slot under νk.

End: The algorithm ends when there is no student who is unassigned or whose
assigned school is not the most preferable one among the schools for which
she is in the non-rejected status. Then the tentative assignments become final.
Obviously, this algorithm may not end in finite steps because of complex reproposal
steps. However, owing to these reproposal steps, we allow students to repropose to
schools at which they might justifiably claim an empty slot or justifiably envy some
student if they did not repropose to. Therefore, though this algorithm may not
work well in general, under some conditions it succeeds in producing an assignment
and reducing justified envy and claims. First, we will show that CDAAR ends in
finite steps when ≻_{C} has a common priority order for every type and an ordering
f of CDAAR is constructed in a certain way.

Proposition 1. Suppose that the schools’ priority profile ≻_{C} has a common priority
order for every type t ∈ T and that an ordering f of students in the CDAAR
algorithm satisfies

f(s) < f (s^{′}) ⇔ s ≻c ^{s}^{′}

for some c ∈ C and for any s, s^{′} such that τ (s) = τ (s^{′}). Then, the CDAAR
algorithm ends in finite steps.

Proof: Suppose that the CDAAR algorithm does not end for some problem where

≻C has a common priority order for every type, i.e. there is a step t such that there
is a previous step t^{′} < tin which νt is equivalent to νt^{′}. Let t be the smallest step
among such steps and t^{′} be the previous step with t^{′} < tand νt= νt^{′}. Consider a
cycle from step t^{′}+ 1 to step t.

Suppose any student who is free (unfree) in some step in the cycle is always free (unfree) in other steps in the cycle. If there is a student who is always unfree in

the cycle, then let ˆsbe such a student. Since

¯

¯

¯{^{s}^{∈ S}τ(ˆs)|f (s) > f (ˆs) and ν_{l}(s) = s} ∪ {ˆs}^{¯}^{¯}_{¯ =}^{X}

c∈C

max^{n}0, q^{τ(ˆ}_{c} ^{s)}− |ν_{l}^{τ(ˆ}^{s)}(c) \ {ˆs}|^{o}

holds for any step l in the cycle, at any school c which ˆsis admitted, q^{τ(ˆ}_{c} ^{s)}= |ν_{l}^{τ(ˆ}^{s)}(c)|
holds for any step l in the cycle. Hence, ˆs’s rejected status for any school which ˆs
once proposed to cannot change to the non-rejected status by reproposal conditions
(i) or (iii). Moreover, since a student s such that s ∈ S_{τ(ˆ}_{s)} and f (ˆs) < f (s) cannot
be assigned to a school which ˆsprefers to her own assignment, reproposal condition
(ii) does not apply to ˆs. Therefore, ˆs is always assigned to the same school in the
cycle. Now we can separate the set of students who are always unfree because they
do not change their assignments in the cycle. With the set of students who are
always free in the cycle, only the reproposal condition (iii) could apply and it is
when there was a reproposal before step t^{′}. But a reproposal based on (iii) gives
a empty slot to a student and does not drop a student from a school. Therefore,
when only the set of students who are always free move, the algorithm ends and
does not form a cycle. This is a contradiction.

Then we know that there is at least one student who is free at some step in
the cycle and unfree at some another step in the cycle. Let s_{i} be such a student,
t^{′′}∈ [t^{′}, t] be a step when si becomes free from unfree, and cb be a school such that
ν_{t}′′(si) = c_{b}. There are two types of changes at step t^{′′}.

1. A student sj such that τ (sj) = τ (si) and f (sj) < f (si) dropped from a
school c_{a}at step t^{′′′} ∈ [t^{′}, t] and was assigned to a school c_{b} such that q^{τ(s}_{c} ^{i}^{)}

b ^{=}

|ν_{t}^{τ(s}′′_{−1}^{i}^{)}(cb)|. Let sk be the student who was assigned to ca at step t^{′′′} and
dropped sj. Since s_{k} was not assigned to caat step t^{′′′}− 1 and this is a cycle,
s_{k} must leave c_{a} after step t^{′′′}. There are two cases on how s_{k} leaves c_{a} after
step t^{′′′}.

sk leaves ca by reproposing to cc with ccPs_{k}ca: Since sk couldn’t be enrolled
in c_{c} at step t^{′′′} but is assigned to c_{c} later, there is a school c_{d} (which can be
c_{a} or cc) which had a student sl who became free from unfree when another
student smsuch that τ (sm) = τ (s_{l}) and f (sm) < f (s_{l}) came to c_{d}and dropped
a student. In order to have this situation, s_{m} must have been dropped from
the previous school ce by the proposal of another student sn. Note that sn

has the parallel structure as s_{k} and sn cannot be si, sj, s_{k}, s_{l} or sm.

s_{k} is rejected by c_{a} by the proposal of another student s_{p}: One possibility is
that sp leaves ca by reproposing to cc with cc^{P}sp^{c}a. If sp is rejected by ca,
then there is another student sq who proposed to ca at that step. In this way,
since this rejection doesn’t continue infinite times, there is a student s_{r} who
was enrolled in ca after step t^{′′′} and left ca by reproposing to more preferable

school. Then, since there is a student sr who left ca by reproposing to more
preferable school and comes back to it later, there is a school cd(which can be
c_{a} or c_{c}) which had a student s_{l} who became free from unfree when another
student smsuch that τ (sm) = τ (sl) and f (sm) < f (sl) came to cdand dropped
a student. In order to have this situation, sm must have been dropped from
the previous school c_{e} by the proposal of another student s_{n}. Note that s_{n}
has the parallel structure as sk and sn cannot be si^{, s}j^{, s}k^{, s}l^{, s}m^{, s}r.

According to these arguments, in any case, in order for sn to leave ce and again come back to it, we need another student so. In this way, there should be infinitely many students and this is a contradiction.

2. When s_{i} was unfree at c_{b}, a student s_{j} such that τ (s_{j}) = τ (s_{i}) and f (s_{j}) >
f(si) was assigned to ca with caPsi^{c}b before step t^{′′}, and si became free by
reproposing to c_{a} based on condition (ii). In order to have this situation, s_{i}
must have been rejected by ca at step t^{′′′} ∈ [t^{′}, t] and was assigned to school
cb. Then, since sj can be admitted to ca later, there is a student sk who was
assigned to c_{a} at step t^{′′′} but must leave c_{a} after step t^{′′′}.

The argument is the same as case 1 by replacing the indices of si and sj. We have shown that there is no cycle and the CDAAR algorithm ends in finite steps.

Because CDAAR has reproposal steps, it eliminates some of envy and claims to empty slots which could occur if it didn’t have reproposal steps. Actually it is shown that whenever CDAAR ends in finite steps, the assignment produced by CDAAR satisfies feasibility, fairness across types, and non-wastefulness.

Proposition 2. When the CDAAR algorithm ends in finite steps, it produces a feasible assignment which is fair across types and non-wasteful.

Proof: By the nature of the algorithm, every student is assigned to the most preferable school among schools for which her status is non-rejected. Let µ be the assignment produced by the CDAAR algorithm and consider a student s and a school c such that cPsµ(s). Think about the steps from when s proposed to c last time to the final step. During these steps, s was always in the rejected status for c. Suppose s was free when she proposed to c. Since there was no reproposal condition (ii) which applied to s for c during those steps, s does not justifiably envy a student of the same type in µ(c). Since there was no reproposal condition (iii) which applied to s for c during those steps, students assigned to c were replaced by those who have even higher priorities and even when there was an empty slot, the student who justifiably claimed the empty slot with the highest priority was not s. Therefore, s cannot justifiably envy some student at c or claim an empty slot at c at the produced assignment µ.

Suppose s was unfree when she proposed to c. Since there was no reproposal
condition (i) which applied to s during those steps, s was unfree through the steps.
This means that q^{τ(s)}_{c} = |µ^{τ(s)}(c)| holds and it is not possible for s to justifiably envy
some student of a different type at c or claim an empty slot at c at µ. Moreover,
because there was no reproposal condition (ii) which applied to s for c during those
steps, s does not justifiably envy a student of the same type.

Henceforth, the assignment produced by the CDAAR algorithm is fair across types and non-wasteful.

Finally, I will formally state the main result and it is directly proved by the previous two propositions.

Theorem 2. Suppose that the schools’ priority profile ≻C has a common priority order for every type t ∈ T . Then there exists a feasible assignment that is fair across types and non-wasteful.

Proof: Consider the CDAAR algorithm whose ordering f satisfies
f(s) < f (s^{′}) ⇔ s ≻_{c} s^{′}

for some c ∈ C and for any s, s^{′} such that τ (s) = τ (s^{′}). This is well-defined since

≻C has a common priority order for every type t ∈ T . Then, it is straightforward from Proposition 1 and 2; the CDAAR algorithm ends in finite steps by Proposition 1 and it produces a feasible assignment which is fair across types and non-wasteful by Proposition 2.

### 4 Incentives of CDAAR

Under the assumption of common priority orders for every type, CDAAR works well to produce a feasible assignment which is fair across types and non-wasteful. Since students’ preferences are usually private information, we need to consider their incentives for CDAAR under the assumption. A mechanism which makes truthful revelation of preferences a dominant strategy is called (dominant strategy) incentive compatible. Here, we state a negative result on the incentives of CDAAR. Theorem 3. Suppose that the schools’ priority profile ≻C has a common priority order for every type t ∈ T and that an ordering f of students in the CDAAR algorithm satisfies

f(s) < f (s^{′}) ⇔ s ≻c s^{′}

for some c ∈ C and for any s, s^{′} such that τ (s) = τ (s^{′}). Then, there is an ordering
f with which the CDAAR mechanism is not dominant strategy incentive compatible.

Proof: Consider the following problem consisting of schools {c1^{, c}2^{, c}3^{, c}4} and
{s1^{, s}2^{, s}3^{, s}4^{, s}5}. Students s1 ^{and s}2 are of type t_{1}, student s_{3} and s_{4} are of type
t_{2} and student s_{5} is of type t_{3}. The schools’ priorities and students’ preferences are
in the following table.

≻c1 ≻c2 ≻c3 ≻c4 P_{s}1 P_{s}2 P_{s}3 P_{s}4 P_{s}5

s_{1} s_{5} s_{3} c_{2} c_{4} c_{1} c_{3} c_{2}

s_{2} s_{1} s_{4} c_{1} c_{1} c_{3} c_{4}

s_{3} c_{4}

c_{2}

capacities 2 1 1 2

ceiling for t_{1} 2 1 1 2

floor for t1 1 0 0 0

ceiling for t_{2} 2 1 1 2

floor for t_{2} 0 0 1 0

ceiling for t3 2 1 1 2

floor for t_{3} 0 0 0 0

Ordering for omitted schools and students in the table are arbitrary as long as s_{1}
has a higher priority than s2 and s3 has a higher priority than s4 at any school.
Consider an ordering f such that

(f (1), f (2), f (3), f (4), f (5)) = (s1^{, s}3^{, s}4^{, s}2^{, s}5)

which satisfies the assumption. Then, the assignment produced by CDAAR when all students truthfully represented their preferences is

µ=

Ã c_{1} c_{2} c_{3} c_{4}
s_{1} s_{5} s_{3} {s2^{, s}4}

! .

Suppose student s_{3}misrepresents her preference to P_{s}^{′}_{3} such that c_{1}P_{s}^{′}_{3}c_{4}P_{s}^{′}_{3}c_{3}P_{s}^{′}_{3}c_{2}.
Then, the assignment produced by CDAAR would be

µ^{′} =

Ã c_{1} c_{2} c_{3} c_{4}
{s1^{, s}3} s5 ^{s}4 ^{s}2

! .

Since s_{3}does better off by stating P_{s}^{′}_{3}, there is an ordering f with which the CDAAR
mechanism is not dominant strategy incentive compatible.

### 5 Concluding Remark

This paper proposed a sufficient condition for the existence of feasible, fair across types and non-wasteful assignments in controlled school choice problems. The

CDAAR algorithm finds such an assignment when the sufficient condition that priority orders are common for the same type students across schools is satisfied. The implication to the real-life controlled school choice programs is that school dis- tricts may be able to ensure the condition to hold by modifying the type division rules or priority structures. Another result is that although CDAAR finds such a desirable assignment, it is shown not always to have a good incentive property.

For further research, it will be possible to identify the necessary and sufficient condition for the existence by relaxing our strong condition. The condition could be more complex than the sufficient condition, but it is helpful if such a condition is derived. As for the incentive property, we have not examined whether CDAAR is not incentive compatible if a certain type of an ordering f is used. If we restrict the ordering f used in CDAAR, there might be a positive result for CDAAR with some type of orderings f .

### References

[1] Abdulkadiro˘glu, A. (2005): “College Admission with Affirmative Action,” In- ternational Journal of Game Theory, 33, 535-549.

[2] Abdulkadiro˘glu, A. and E. Ehlers (2008): “Controlled School Choice,” mimeo. [3] Abdulkadiro˘glu, A., and T. S¨onmez (2003): “School Choice: A Mechanism

Design Approach,” American Economic Review, 93, 729-747.

[4] Balinski, M., and T. S¨onmez (1999): “A Tale of Two Mechanisms: Student Placement,” Journal of Economic Theory, 84, 73-94.

[5] Ehlers, E., I.E. Hafalir, M.B. Yenmez, and M.A. Yildirim, (2011): “School Choice with Controlled Choice Constraints: Hard Bounds versus Soft Bounds,” mimeo.

[6] Hafalir, I.E., M.B. Yenmez, and M.A. Yildirim, (2011): “Effective Affirmative Action in School Choice,” mimeo.

[7] Kojima, F (2010): “School Choice: Impossibilities for Affirmative Action.”