最近の更新履歴 yyasuda's website

全文

(1)

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.

(2)

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-

(3)

trolled school choice problem is written as (S, C, (qc)c∈C, PS,C, T, τ,(qTc, qTc)c∈C) which consists of the following elements.

1. a finite set of students S = {s1, ..., sn}; 2. a finite set of schools C = {c1, ..., cm};

3. a capacity vector q = (qc1, ..., qcm), where qc is the capacity of school c ∈ C or the number of seats in c ∈ C;

4. a students’ preference profile PS = (Ps1, ..., Psn), 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= (≻c1, ...,≻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 = {t1, ..., 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 qT

c = (q t1

c , ..., q tk c )

and qTc = (qtc1, ..., qtck) such that qct ≤ qtc ≤ qc for all t ∈ T , and Pt∈T qtc ≤ qcPt∈T qtc.

The difference from other specifications of controlled school choice models comes from the last element. qt

c is the minimal number of slots that school c must allocate to students of type t and qtc is the maximal number of slots that school c is allowed to allocate to students of type t. We call (qtc, qtc) 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 , qtc ≤ |{s ∈ S|τ (s) = t}| ≤ qtc. An assignment µ respects constraints if for every school c, µ(c) respects constraints at c, i.e., |µ(c)| ≤ qc holds and qtc ≤ |µt(c)| ≤ qtc 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

(4)

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,

(5)

(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).

(6)

Example 1. (Ehlers, Hafalir, Yenmez and Yildirim (2011)) Consider the following problem consisting of schools {c1, c2, c3} and {s1, s2, s3}. Students s1 and s2 are of

type t1 and student s3is of type t2. The schools’ priorities and students’ preferences are in the following table.

c1c2c3 Ps1 Ps2 Ps3

s2 s2 s1 c2 c3 c2 s1 s1 s2 c3 c2 c3 s3 s3 s3 c1 c1 c1

capacities 1 1 1

ceiling for t1 1 1 1 floor for t1 1 0 0 ceiling for t2 1 1 1 floor for t2 0 0 0 There are four feasible assignments in Example 1:

µ1 =

à c1 c2 c3 s1 s2 s3

! , µ2 =

à c1 c2 c3 s1 s3 s2

! ,

µ3 =

à c1 c2 c3 s2 s3 s1

! , µ4 =

à c1 c2 c3 s2 s1 s3

! ,

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 {c1, c2, c3} and {s1, s2}. Students s1 and s2 are of the same type t. The schools’ priorities and students’ preferences are in the following table.

c1c2c3 Ps1 Ps2

s2 s2 s1 c2 c3 s1 s1 s2 c3 c2 c1 c1

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=

à c1 c2 c3 s1 s2

! , µ2 =

à c1 c2 c3 s1 ∅ s2

! ,

µ3=

à c1 c2 c3 s2 ∅ s1

! , µ4 =

à c1 c2 c3 s2 s1

! ,

(7)

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, s2 has a higher priority than s1 at c2 while s1 has a higher priority than s2 at c3. If s2 had a higher priority than s1 at c3, 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.

(8)

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), f1(2),..., f1(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 Pf−1(1), say c1. If there is some µ ∈ F such that µ(f1(1)) = c1, then set ν1(f1(1)) = c1 and ν1(s) = ν0(s) = s for all s ∈ S \ {f1(1)}. Otherwise f1(1)’s status for c1 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

(9)

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

maxn0, 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) |νkc)| < 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

(10)

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

¯

¯

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

c∈C

maxn0, 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 si 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) = cb. 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 caat step t′′′ ∈ [t, t] and was assigned to a school cb such that qτ(sc i)

b =

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

sk leaves ca by reproposing to cc with ccPskca: Since sk couldn’t be enrolled in cc at step t′′′ but is assigned to cc later, there is a school cd (which can be ca or cc) which had a student sl 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 ce by the proposal of another student sn. Note that sn

has the parallel structure as sk and sn cannot be si, sj, sk, sl or sm.

sk is rejected by ca by the proposal of another student sp: One possibility is that sp leaves ca by reproposing to cc with ccPspca. 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 sr who was enrolled in ca after step t′′′ and left ca by reproposing to more preferable

(11)

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 ca or cc) which had a student sl 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 ce by the proposal of another student sn. Note that sn has the parallel structure as sk and sn cannot be si, sj, sk, sl, sm, sr.

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 si was unfree at cb, a student sj such that τ (sj) = τ (si) and f (sj) > f(si) was assigned to ca with caPsicb before step t′′, and si became free by reproposing to ca based on condition (ii). In order to have this situation, si 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 ca at step t′′′ but must leave ca 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 µ.

(12)

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.

(13)

Proof: Consider the following problem consisting of schools {c1, c2, c3, c4} and {s1, s2, s3, s4, s5}. Students s1 and s2 are of type t1, student s3 and s4 are of type t2 and student s5 is of type t3. The schools’ priorities and students’ preferences are in the following table.

c1c2c3c4 Ps1 Ps2 Ps3 Ps4 Ps5

s1 s5 s3 c2 c4 c1 c3 c2

s2 s1 s4 c1 c1 c3 c4

s3 c4

c2

capacities 2 1 1 2

ceiling for t1 2 1 1 2

floor for t1 1 0 0 0

ceiling for t2 2 1 1 2

floor for t2 0 0 1 0

ceiling for t3 2 1 1 2

floor for t3 0 0 0 0

Ordering for omitted schools and students in the table are arbitrary as long as s1 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, s3, s4, s2, s5)

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

µ=

à c1 c2 c3 c4 s1 s5 s3 {s2, s4}

! .

Suppose student s3misrepresents her preference to Ps3 such that c1Ps3c4Ps3c3Ps3c2. Then, the assignment produced by CDAAR would be

µ =

à c1 c2 c3 c4 {s1, s3} s5 s4 s2

! .

Since s3does better off by stating Ps3, 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

(14)

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.”

Updating...

参照