Affirmative Action and School Choice

MQITE WORKING PAPER SERIES WP # 12-03 Affirmative Action and School Choice José Alcalde and Begoña Subiza  Affirmative Action and School Choice∗ José Alcalde† Begoña Subiza‡ February 19, 2012 ∗ We wish to thank Teodosia del Castillo, Pablo Revilla, Antonio Romero-Medina and the par- ticipants at the MECA Seminar for their comments. This work is partially supported by the Institut Valencià d’Investigacions Econòmiques. Alcalde acknowledges financial support by FEDER and the Spanish Ministerio de Educación y Ciencia under project SEJ2007-62656/ECON. † Corresponding Author. Department of Quantitative Methods and Economic Theory and IUDESP, University of Alicante. [email protected] ‡ Department of Quantitative Methods and Economic Theory and IUDESP, University of Ali- cante. [email protected] 1  Abstract This paper proposes a reform for school allocation procedures in order to help integration policies reach their objective. For this purpose, we suggest the use of a natural two-step mechanism. The (equitable) first step is introduced as an adaptation of the deferred-acceptance algorithm designed by Gale and Shapley (1962), when students are divided into two groups. The (efficient) second step captures the idea of exchanging places inherent to Gale’s Top Trading Cycle. This latter step could be useful for Municipal School Boards when implementing some integration policies. Keywords: Integration Policy, School Allocation, Affirmative Action. Journal of Economic Literature Classification Numbers: C72, I28, J18.  I. Introduction On March 6, 1961 President John F. Kennedy issued Executive Order 10925. This can be seen as the beginning of a ‘new era’ against intolerance and discriminatory practices. At that time, the way to fight against some of these ‘customs’ was by promoting the use of affirmative action policies. In a static setting, these policies can be seen as discriminatory practices; whe- reas, from a dynamic perspective, the existence of a certain degree of ‘historical discrimination’ justifies the use of affirmative action policies, as a necessary pre- vious step, before concentrating on avoiding discriminatory practices. In other words, policies against circumstantial discrimination are useless if they are not accompanied by measures to reduce structural inequalities. Evidence suggests that the ‘long run’ arguments have prevailed, which is why, for instance, the OECD countries explicitly implemented affirmative action mea- sures to reach integration objectives. As a recent example concerning this matter, let us mention the MENA-OECD conference on gender equality in government and business, held in Paris on 4 May 2010.1 Other illustrative examples include firstly, the presence of several policies to prevent gender gaps in terms of salary and/or political representation and upon which legal reforms in some countries are based; and secondly, the existence of intensive migration movements over re- cent years that has justified the adoption of certain integration policies (from race, ethnic and/or national origin perspectives). 1 The conclusions from this conference are summarized in a document available at the OECD web page. 1  There is a controversial debate against affirmative action policies as some agents believe that they are discriminatory practices. As an illustrative example, we can mention that2 During the November 5, 1996 election, California voters voted 54% to 46% to amend the California Constitution through an initiative commonly known as Proposition 209, or the California Civil Rights Initiative. The proposition has been incorporated into the California Constitution under Article 1, Section 31. Although the constitution- ality of the initiative was legally challenged, the U.S. Supreme Court denied further appeal and let stand the new California law on Novem- ber 3, 1997. [. . . ] Students and state lawmakers had urged the repeal, arguing that the ban on “affirmative action" had caused the university to be per- ceived as inhospitable to minority students. Proponents of the repeal cited a sharp drop in the number of in-state black and Hispanic first- year students and the hiring rates of women and underrepresented minority faculty members. The aim of the present paper is to shed some light onto the debate on affir- mative action measures versus non-discriminatory practices. Our point is that, in agreement with the 1964 Civil Rights Act, and also the Supreme Court’s opinion,3 2 This quotation has been borrowed from the University of California at Irvine, Office of Equal Opportunity and Diversity (OEOD). Website: http://www.oeod.uci.edu. 3 See the arguments by Justice O’Connor on Grutter v. Bollinger, at the end of this Introduction. 2 these policies should cease to exist when the effects of ‘historic discrimination practices’ are dissipated. Therefore, it is important to concentrate on how these ‘everlasting’ inequalities could be reduced. In this sense, we believe that the ed- ucational training of ‘future generations’ is one of the most relevant variables to be taken into account, as whenever children have unequal opportunities to achieve a comparable educational level, in the broadest sense, they will not be able to compete fairly in the job market. Moreover, since (a) there is empirical evidence to show the positive correlation between school quality and housing prices in their ‘influence areas’ (see, for instance Kane et al., 2006 or Dougherty et al., 2009), and (b) one of the two main factors for a student to be attached to a certain school is to reside in its ‘influence area’, the main conclusion is that the non-application of affirmative action measures, in favor of certain population groups, will lead to a more inequitable income distri- bution in the long run. This is why we concentrate on the analysis of school allocation procedures as a way to reduce certain inter-group inequalities. We propose to introduce inte- gration policies into the processes used for school allocation at elementary level. To reach our objective we introduce a two-step procedure. For the first step, we suggest a tentative allocation procedure with a minimal segregation level.4 The 4 Frankel and Volij (2011) propose an exhaustive analysis for segregation indexes. Our ap- proach differs from that of Frankel and Volij (2011) as our aim does not consider the different districts into which each municipality is divided, but rather each municipality as a whole. 3 second step adopts the idea of trading places, proposed by Alcalde and Romero- Medina (2011) to attain efficiency in the allocation process. Concerning the first step, we proceed as follows. Each school is allocated a number of available places, commonly known as its quota. We distribute each school quota among the different groups of agents5 in such a way that (unless it is impossible) each group has a number of ‘reserved places’ and, if we analyze how many places have been assigned to each group, the share is equitable between groups. Note that such a division allows one isolated School Choice Problem to be considered for each group. We then propose an initial distribution of its schools places for each group satisfying ‘internal non-justified envy’.6 This objective is reached by applying (a modified version of) the classical ‘deferred-acceptance algorithm’ introduced by Gale and Shapley (1962), where offers are made by students. This algorithm is applied to each group separately. Once this first step is concluded, we can proceed to an ‘integrate’ second step, whose main objective is to achieve improvements, in terms of efficiency, related to the previous distribution. In this sense, we consider two different scenarios, related to the Municipal School Board, MSB henceforth, objectives. (a) Minimizing segregation is the main objective of the MSB. By this we mean that the MSB would prefer to implement an inefficient allocation than ‘to 5 Although our model, in Section III, deals with two-group problems, our results are straight- forwardly extended to any number of population groups. What it is important is that the number of available places at each school is high enough to distribute them among the groups by guaranteeing some diversity representation at each school. 6 The term non justified envy was coined by Abdulkadiro˘glu and Sönmez (2003) to re-interpret, in the framework of school allocation, the classical notion of stability in matching problems. 4  sacrifice’ the level of integration. (b) The MSB objective is to obtain an efficient allocation; whilst minimizing segregation is a secondary although relevant objective. The two scenarios described above highlight the existence of some trade-offs which are difficult to solve. The first incompatibility, referred to in situation (a) above, concerns a trade-off between efficiency and non justified envy from an intra- group perspective. This was pointed out by Alcalde and Romero-Medina (2011), showing that no procedure always proposes an allocation system that satisfies the two properties above. Their solution was to propose an allocation procedure sat- isfying non justified envy, in a weaker sense, and efficiency. The second trade-off, proposed in statement (b) above, marks the incompatibility of global efficiency and minimal segregation. Our suggestion to counteract this fact is to concentrate on efficiency as the main objective and, then, select the efficient solution that minimizes the segregation level. This approach is related to a controversy on in- dividual versus collective rights. It seems to be clear that, from a social point of view, segregation must be prevented. Sociologists and lawyers study the benefits of integration from a social perspective.7 Nevertheless, there are some popular comments suggesting that certain groups are against integration. In this respect van Buren (1995) says, on pg. 179, Jews resist, for example any form of quotas for admission to pro- 7 From a Sociological perspective, see the paper by Oliver (1985) for an old debate, or Curran et al. (2006) for an analysis of migration and integration. Legal aspects are studied among others in Seitles (1998) and Garda (2009). 5  fessional schools, because they remember their own experience of having been excluded by quotas in the past. Blacks, on the other hand, demand “afirmative action,” knowing from their own past that “open admission” in a white society has always meant black exclu- sion. So blacks conclude that Jews are racists, and Jews conclude that blacks are anti-Judaic. Their common experience of suffering only serves to set them at odds. Therefore, what we propose in affirmation (b) can be seen as a test to contrast whether this ‘popular belief’ about others’ aversion to be integrated is empirically sustained or not. A further question that we wish to highlight in our proposal is legal imple- mentability. In this sense, Gajendragadkar (2006) says: [. . . ] racial balancing provisions, as governmental uses of race, must survive the strictest judicial scrutiny to accord with the Equal Protection Clause of the Fourteenth Amendment. Moreover, bearing in mind the case of Grutter v. Bollinger, and relative to the con- troversial (long run) affirmative action policies versus (short run) non-discrimina- tory practices, Justice O’Connor argued that race-conscious admissions policies must be limited in time: We take the Law School at its word that it would “like nothing better than to find a race-neutral admissions formula” and will ter- minate its race-conscious admissions program as soon as practicable. 6  [. . . ] It has been 25 years since Justice Powell first approved the use of race to further an interest in student body diversity in the context of public higher education. Since that time, the number of minority applicants with high grades and test scores has indeed increased. We expect that 25 years from now, the use of racial preferences will no longer be necessary to further the interest approved today. At this point, in order to avoid any misinterpretation, we want to stress that by integration policies we are not necessarily meaning racial policies for integra- tion. This term should be understood as widely as possible. For instance, some policymakers could be interested in gender integration by reducing the structural gap favoring men over women; others might well be interested in income-based integration by helping children from low-income families to access high-income district schools. What is important in this paper is that, once the policymakers have decided which specific integration policy they are interested in, the popula- tion is partitioned into mutually exclusive groups; and therefore, no agent is free to decide which group she belongs to. In this way we avoid certain types of strategic behavior. II. Related Literature and Overview The problem that we study here can be viewed as a many-to-one, two-sided match- ing problem, following the original model by Gale and Shapley (1962). There is a large tradition on this family of problems, as pointed out in the overview by Roth 7 and Sotomayor (1990). These models have been used to study, both from a pos- itive and a normative point of view, how several specific markets work or would be redesigned. For instance, Roth and Xing (1994) identify the general class of market failures due to the unraveling of appointment dates; Roth and Peranson (1999) analyze some modifications introduced into the National Resident Match- ing Program; and Niederle et al. (2008) overview some of the recent literature in that matter. For the case of school allocation, some recent papers explore the former Boston system and propose modifications to reach a better allocative process (Abdulka- diro˘glu et al., 2005b, Abdulkadiro˘glu et al., 2006 or Ergin and Sönmez, 2006, among others), whilst others suggest improvements to the current Boston system (Alcalde and Romero-Medina, 2011, or Kesten, 2010); the New York City system for high schools has also been explored in some papers (Abdulkadiro˘glu et al., 2005a, or Abdulkadiro˘glu et al., 2009). Nevertheless, as far as we know, not many papers explore the school admis- sion problem taking into account the possibility of affirmative action ingredients. Abdulkadiro˘glu (2005) deals with college admissions, and considers that the col- leges are the only agents that decide how their affirmative action policy should be implemented, i.e. each school decides how to distribute its quota among the different groups of agents. Then, he proposes a strategic analysis for the student optimal stable matching mechanism. To the contrary, in the present paper, we consider that schools do not have any capacity to influence the way in which their places are ex-ante distributed among the different groups of agents. Our interest 8 is not about global stability, as in Abdulkadiro˘glu (2005), but internal stability plus inter-group fairness, which is not mentioned by this author. Moreover, our analysis in the present paper does not concentrate on agents’ strategic behavior. Recently, Kojima (2010) explores the possibility of proposing affirmative action policies that do not hurt the disadvantaged students, in terms of efficiency. What he finds is general impossibility of reaching such an objective. Meanwhile, Ehlers (2010) studies a model closer to the one proposed in this paper. The main differ- ence between the model in Ehlers (2010) and ours is that he considers that schools places are ex-ante distributed among the two groups of agents and that this restric- tion should be satisfied ex-post. However, our proposal does not require ex-post distribution to satisfy any pre-established condition. The rest of the paper is organized as follows. Section III introduces the basic model and discusses the notions of stability and efficiency from an intra-group perspective. It also proposes a way to formalize the notion of the degree of exter- nal fairness. Section IV introduces an algorithmic procedure yielding a matching combining internal stability and external fairness. Moreover, the matching that our procedure suggests is the unique second-best efficient allocation, restricted to the two properties above. Section V explores two ways to improve the allocation suggested in the previous section, in terms of efficiency. Each of these possibilities for improvement follows one of the MSB objectives proposed in the Introduction. The main objective for Section VI is to propose a value for the fairness param- eter. We also suggest a method to evaluate the fairness degree of any matching. Section VII introduces our main conclusions. Finally, the proofs are gathered in 9 the Appendices. III. School Choice Problem and Diversity. A Model We consider a city with n schools. Let qi denote the set of available places for new students that school ci has, ci ∈ C = {c1 , . . . , ci , . . . , cn }. Q = (q1 , . . . , qi , . . . , qn ) is called the vector of quotas. Pn We also consider a group of m new students, m ≤ i=1 qi = q,8 each of them belonging to one of the two mutually exclusive classes F and D, having f and d individuals, respectively. For interpretative purposes, D is considered the group of disadvantaged students (i.e., the set of agents that eventually benefit from affirmative action policies), whereas F is referred as the group of favored students. Each student sj ∈ S = F ∪ D has a preference relation defined on the set of schools. Let linear preorder Pj denote student sj ’s preferences, and Ri the induced weak preferences.9 Similarly, we assume that each school has a linear preorder on S that is interpreted as its priority list. Let Πi denote the priority list for school   ci .10 Vector P = {Πi }ni=1 ; {Pj }m j=1 summarizing both school priorities and student preferences will be called a profile of preferences. 8 This assumption implies that there are enough places to allocate each student a place in some school. Note that this requirement is not necessary to define a matching problem, and will not be used in the description provided for some of our allocation procedures. Therefore, the only reason we introduce such a consideration is the capacity for providing realistic interpretations in agreement with the fact that compulsory schooling is established by law. 9 i.e., given a student sj and two schools, ci and ch , ci Rj ch is interpreted as either ci Pj ch or ci = ch . 10 We do not discuss here how these lists are (or should be) built. The paper by Alcalde and Romero-Medina (2012) gives some insights on this matter. 10  The problem that we would like to solve is how to distribute the students among the available school places. A first approach to answer such a question is given by the notion of matching. Definition 1 Let SCP = {C, S, P, Q} be a School Choice Problem. A matching for SCP is a correspondence µ : C ∪ S  C ∪ S such that (a) For each ci ∈ C, µ (ci ) ⊆ S; (b) For each sj ∈ S, µ (sj ) ∈ C ∪ {sj }; (c) |µ (ci )| ≤ qi 11 for each school ci ; and (d) For each school-student pair, (ci , sj ), sj ∈ µ (ci ) if, and only if, ci = µ (sj ). Among the set of matchings that a SCP admits, there are two particular re- quirements that have been commonly asked to be satisfied by a solution in order to be considered a satisfactory allocation. The first, called efficiency, implies that students are unable to obtain a place each in a preferred school. The second, called stability, establishes that student envies in the allocation process, if any, are based on the way in which schools prioritize the students.12 Therefore, as far as the MSB builds priority lists based on equity criteria, these envies could be considered as unjustified. Definitions 2 and 3 formalize these ideas. 11 Given a set A, |A| denotes its cardinal. 12 The paper by Abdulkadiro˘glu and Sönmez (2003) proposes an interpretation of stability in terms of absence of justified envy. 11 Definition 2 Let SCP = {C, S, P, Q} be a School Choice Problem, and µ a matching for SCP. We say that µ is efficient if for any other matching µ0 6= µ there is a student, say sj , such that13 µ (sj ) Pj µ0 (sj ). Definition 3 Let SCP = {C, S, P, Q} be a School Choice Problem, and µ a matching for SCP. We say that µ is stable if for each student sj and school ci such that ci Pj µ (sj ), we have that (a) |µ (ci )| = qi ; and (b) sh Πi sj for each sh ∈ µ (ci ). Any SCP whose students are divided into two groups, F and D, allows us to consider two School Choice Problems, namely SCP F and SCP D separately. There can be described easily, once we have been able to disaggregate school quotas by describing two vectors, QF and QD such that (a) Q = QF + QD ; and Pn F Pn D ≥ d, where qiF qiD , resp. denotes the number of
(b) i=1 qi ≥ f, i=1 qi places that school ci reserves for students in F (in D, resp.). Given QF and QD we define SCP F = C, F, PF , QF where the preference    profile PF = ΠF  F i ci ∈C , P j s ∈F agrees with P in the new set of agents, i.e. j (a) for each ci ∈ C, and any two students in F, say sj and sh , sj ΠF i sh if and only if sj Πi sh ; and 13 For the sake of simplicity, we consider in this paper that the to be unmatched option is worse than to be matched to any school, i.e. ci Pj sj for each student sj and school ci . 12 (b) for each sj ∈ F, and any two schools, say ci and ck , ci PjF ck if and only if ck , ci P j ck . SCP D , the School Choice Problem that QD induces, involving schools and students in D, can be described in a similar way. Therefore, given a SCP and a matching µ, we can study how students in F and D are located by µ, from an intra-group point of view, when considering only students in any of the two classes. To reach our objective, for µ given, we consider the disaggregate school quotas by defining for each school ci such that qiD = |µ (ci ) ∩ D|.14 Given vectors QF and QD described above, we denote by [µ]F and [µ]D the matchings for SCP F and SCP D respectively that agree with µ, i.e. for each ci ∈ C, [µ]F (ci ) = µ (ci ) ∩ F; and, similarly [µ]D (ci ) = µ (ci ) ∩ D. The above considerations are useful for introducing certain properties that a matching might exhibit from an intra-group perspective. Definition 4 Let SCP = {C, S, P, Q} be a School Choice Problem, and µ a matching for SCP. We say that (a.1) µ is F-stable if [µ]F is stable for SCP F ; (a.2) µ is D-stable if [µ]D is stable for SCP D ; (b) µ is G-stable if it is both F-stable and D-stable; 14 Provided that agents in D benefit from the affirmative action policy, and that some of our definitions are sensitive to the way in which excess places are distributed among both groups of students, we might consider that these places are (ex-post) attributed to agents in F as a way to compensate the effect of such a policy. 13 (c.1) µ is F-efficient if [µ]F is efficient for SCP F ; (c.2) µ is D-efficient if [µ]D is efficient for SCP D ; (d) µ is G-efficient if it is both F-efficient and D-efficient. The next result, whose straightforward proof is omitted, reveals a close rela- tionship between stability and G-stability; and a similar connection between effi- ciency and G-efficiency. Proposition 5 Let SCP = {C, S, P, Q} be a School Choice Problem, and µ a matching for such a problem. If µ is stable (resp. efficient), then it is G-stable (resp. G-efficient). The converse is, in general, not true; i.e. G-stability does not imply stability and G-efficiency does not guarantee efficiency either. Note that the notions introduced in Definition 4 deal with internal stability and/or efficiency for agents in any of the two groups, F and D. Nevertheless, they do not consider any comparison involving students belonging to the two classes. What we next propose is a way to evaluate external fairness, from the point of view of the agents belonging to the same class. Related to this point, let us consider that agents in a certain class assume that a proportion of places, say α, has to be reserved for the students in the other category. Taking this premise as a fact, the possibilities that a student might have to object to an allocation (based on the priority lists) are reduced, related to what stability suggests. Definition 6 Let SCP = {C, S, P, Q} be a School Choice Problem, and α and β, 0 ≤ α, β ≤ 1 two real numbers. We say that matching µ is 14 (a) αF -fair, or α-fair from F’s point of view if, and only if, for each school ci ∈ C, if |D ∩ µ (ci )| > [αqi ]+ , then {sh ∈ F : ci Ph µ (sh )} = ∅. (b) β D -fair, or β-fair from D’s point of view if, and only if, for each school ci ∈ C, if |F ∩ µ (ci )| > [βqi ]− , then {sh ∈ D : ci Ph µ (sh )} = ∅. (c) α-fair if it is αF -fair and (1 − α)-fair from D’s point of view; where for a real number r, [r]+ is the integer v such that v − 1 < r ≤ v; and [r]− is the integer z such that z ≤ r < z + 1. Note that Definition 6 implicitly contains a flavor of ‘affirmative action pol- icy’ benefiting agents in D. The first requirement that α-fairness suggests is that agents in both sets agree how these places should be distributed, in relative terms. The second assumption is that the fact that places are indivisible should not hurt students in D. Just to illustrate this, let us consider two schools with 25 and 23 places respectively to be distributed. Let us assume that there is a consensus estab- lishing that 70.83 % should be assigned to agents in F and the remaining 29.17 % correspond to students in D. Therefore, and provided that school places are indivisible, students in D would be prioritized in 7 or 8 places at the first school and 6 or 7 at the second. Since our aim is to promote affirmative action for these 15 students, we should consider that they have priority in 8 places at the first school and 7 at the second. Continuing with the above illustrative example, we can proceed as follows. Let us consider two independent SCPs, one involving the students in F, with school quotas (17, 16), and the other including students in D, with school quotas (8, 7), as previously argued. Now, let us assume that f = 34 and d = 14. Note that any solution that we could propose should imply that one student in F must have no school place and simultaneously one school has to have one unassigned place. This proposal is hardly justifiable as a solution for our problem. The next section deals with how to divide school quotas among the two groups of agents in such a way that each student might be allocated a place. IV. G-Stability and Inter-Group Fairness The aim of this section is to propose a formal procedure showing the existence of G-stable allocations. What we introduce here is a family of sequential procedures, one for each parameter α used to distribute the school places among both groups of students. Just to introduce our next proposal, let Ω be the set of values for α guar- anteeing that each student in D would be allocated a school place, i.e. Ω = α ∈ [0, 1] : d ≤ ni=1 [αqi ]+  P Definition 7 For α given, α ∈ Ω, we define the α-fair deferred-acceptance pro- cedure, that associates to each SCP = {C, S, P, Q} the matching µα , to be called 16 its α-fair matching, where (a) for each sj ∈ D, µα (sj ) is sj ’s mate at the student optimal stable matching for C, D, PD , QD , where the quota for school ci is qiD = [αqi ]+ ; and  (b) for each sh ∈ F, µα (sh ) is sh ’s mate at the student optimal stable matching for C, F, PF , QF , with qiF = qi − |{sj ∈ D : µα (sj ) = ci }|.  What the α-fair deferred-acceptance procedure suggests is the following. First, let us consider the sub-problem involving disadvantaged students and a number of school places guaranteeing that each D-student would be allocated a place at a school. These places should be uniformly distributed across the schools. For this sub-problem, let us apply the deferred-acceptance algorithm introduced by Gale and Shapley (1962) in which students made the proposals. Then a new sub- problem emerges. In such a case, the set of students coincides with F, and each school still has available all the places that have been reserved for the favored stu- dents, or no student in D previously applied for such a place. Now, let us apply again the student optimal algorithm proposed by Gale and Shapley (1962) to this second problem. Since no student belongs to both categories, i.e. F and D do not intersect, the above description on how to allocate students among schools defines a matching for the original problem. The next result points out some of the properties satisfied by the matching obtained when the α-fair deferred-acceptance procedure is applied. Theorem 8 Let SCP be a School Choice Problem and, for α given, α ∈ Ω, let µα 17 be the matching obtained by applying the α-fair deferred-acceptance procedure. Then µα satisfies the following properties (a) µα is G-stable; (b) Each student is attached to a school, i.e. for each student sj , µα (sj ) ∈ C; (c) µα is α-fair; and (d) No student has any incentive to misreport her preferences. The above result shows that the outcome for the α-fair deferred-acceptance procedure satisfies some interesting properties. Nevertheless, it can be far from efficient, as the following situation illustrates. Let us consider a problem with d = 50 and f = 100. Now let us imagine that there are 8 schools with 21 vacancies each, and fix α = 1/3. If c1 is the best school for all the students in D and, similarly, it is the worst school for all the students in F, only 7 students in D will obtain a place at school c1 and its remaining 14 places will stay vacant as no student in F will apply for a place in such a school. Therefore, what this example shows is that the matching proposed by the α-fair deferred-acceptance procedure might be inefficient; and such an inefficiency, which is not present when students are not segregated into two classes, can be reduced by reallocating the unassigned school places. A way to reduce the inefficiency of the allocation procedure is by introducing what we call the multi-stage α-fair procedure. It can be described straightfor- wardly by iteratively applying the procedure proposed in Definition 7. Let us 18 consider a given SCP. As a first tentative matching, we propose its α-fair match- ing. We now investigate to determine whether there is any school with vacancy at µα that has been over-demanded by agents in D. If there is no such school, the process is over and µα is implemented. Otherwise, let us reconsider the share of school quotas among the two groups, by increasing the quotas for agents in D, and proceed in a way similar to the one proposed in Definition 7. This process ends up when no school being under-demanded was over-demanded by disadvantaged students. Definition 9 For α given, 0 ≤ α ≤ 1, we define the multi-stage α-fair proce- dure which associates to each SCP the matching µmsα obtained throughout the following algorithm. (Step 1) Let µ1 be the matching described as follows (a) For each sj ∈ D, µ1 (sj ) is her student optimal stable matching for D(1) C, D, PD , QD(1) , where the quota for school ci is qi = [αqi ]+ ;  and (b) For each sh ∈ F, µ1 (sh ) is her student optimal stable matching for F (1) C, F, PF , QF (1) , with qi  = qi − |{sj ∈ D : µ1 (sj ) = ci }|. D(1) If, for each school ci , |{sj ∈ D : µ1 (sj ) = ci }| < qi , then the algorithm stops proposing µmsα = µ1 . Otherwise, go to Step 2. .. . 19 (Step t) Let µt be the matching described as follows (a) For each sj ∈ D, µt (sj ) is her student optimal stable matching for D(t) C, D, PD , QD(t) , with qi = qi − |{sj ∈ F : µt−1 (sj ) = ci }|; and  (b) For each sh ∈ F, µt (sh ) is her student optimal stable matching for F (t) C, F, PF , QF (t) , with qi = qi − |{sj ∈ D : µt (sj ) = ci }|.  If µt ≡ µt−1 , then the algorithm stops proposing µmsα = µt . Otherwise, go to Step t + 1. We would like to point out that Definition 7 assumes that α ∈ Ω, whereas Def- inition 9 does not impose a lower bound for α. The only reason for introducing such a formal difference is that this assumption is both necessary and sufficient for the former to guarantee that each student will be assigned a place in a school, pro- vided that there are enough places; nevertheless this lower bound is not necessary for the latter to reach such an objective. Let us observe that this algorithm is student monotonic, i.e. for two given steps 0 t and t0 , t < t0 , and each student sj we have that µt (sj ) Rj µt (sj ). Therefore, a natural question arises regarding the study of the restricted efficiency relative to matching µmsα . Definition 10 introduces the notion of sub-optimality that we are going to explore, and Theorem 11 points out that by applying the above mecha- nism we always reach a sub-optimal allocation. Definition 10 Let SCP = {C, S, P, Q} be a School Choice Problem, and µ a matching for such an instance. Given α, 0 ≤ α ≤ 1, we say that µ is G-Stable α-fair optimal for SCP whenever 20  (1) µ is G-Stable; (2) µ is α-fair; and (3) for any G-Stable matching µ0 6= µ, such that |µ0 (ci ) ∩ D| ≥ |µ (ci ) ∩ D| for each school ci , there is a student, say sj , such that µ (sj ) Pj µ0 (sj ). What the above notion for restricted optimality proposes is that we restrict our analysis to matchings satisfying both G-stability and α-fairness. Moreover, since integration is a relevant feature for the MSB policies, any alternative matching to be considered should respect the integration level that the one proposed has. This is the aim of the Condition (3) in Definition 10, which states that the presence of students in D should be not reduced at any school. Theorem 11 Let SCP = {C, S, P, Q} be a School Choice Problem and, for α given, µmsα be the outcome of the multi-stage α-fair procedure for SCP. Then µmsα is a G-Stable α-fair optimal matching for SCP. The next corollary points out that the complex sequentiality introduced in Def- inition 9 is not present when the number of excess places is low enough. Corollary 12 Let SCP = {C, S, P, Q} be a School Choice Problem, with m = q, and let α be a distribution parameter, α ∈ Ω. Then µα is a G-Stable α-fair optimal matching for SCP. 21  V. Towards Efficiency The main aim of this section is to explore how the MSB could act to improve the allocation proposed by the multi-stage α-fair procedure, in terms of efficiency. As anticipated in the Introduction, we distinguish two scenarios, depending on the MSB objectives. Therefore, each possible objective for the MSB is analyzed in an independent subsection. The solutions for both policies can be summarized in a simple way. Given a SCP, and fixed α, let us compute its multi-stage α-fair matching, µmsα . An inter- pretation of what this matching proposes can be established in terms of students having usufruct right on their places, and thus they are free to exchange the use of their places.15 Consequently, the allocation that µmsα proposes to each student can be understood as her initial endowment to be exchanged (if she wished to) in a market for school places. Based on this approach, what we propose here is to apply Gale’s top trading cycle algorithm, introduced in Shapley and Scarf (1974). For the MSB to reach its objective, it is important to decide how to use the information about the students’ declared preferences for exchanging places. To formalize this, we need to introduce additional notation. From now on, we assume that each student, say sj , is endowed with a linear preorder Ej on S. For student sj , sh Ej sk might be interpreted as, ceteris paribus, sj would prefer to exchange her place with student sh rather than with sk . The MSB role in this section can be summarized as follows: Given matching µ 15 Alcalde and Romero-Medina (2011) propose a legal justification for such an interpretation. 22 for SCP = {C, S, P, Q} and students’ preferences for exchanging E = {Ej }m j=1 , the MSB determines, for each student sj , her MSB-agreeing preferences for ex- change. Let Pj be the linear preorder in S that MSB associates to student sj when, given the above primitives, it wants to implement policy P.   b and sj , let B sj ; Sb be the only Pj -maximal in Given subset of students S, b Similarly, for any two sets of students, say S¯ and S, S. b we denote   [   ¯ B S; S = b B sj ; S . b sj ∈S¯ Before introducing matching µttc , in Definition 14, we need to formalize when students are said to be involved in a minimal cycle. Definition 13 Let S¯ and Sb be two groups of students, with ∅ = 6 S¯ ⊆ S.b We say  m that S¯ forms a minimal cycle on Sb according to Pj j=1 if, and only if,   (a) B S; ¯ Sb = S, ¯ and   ¯ (b) B S 0 ; Sb 6= S 0 , for each non-empty S 0 ( S. Similarly, for a given set of students S, b we say that sj is a S-cycle b student if there exists S 0 , sj ∈ S 0 ⊆ S, b such that S 0 forms a minimal cycle on Sb according to  P m j j=1 . Definition 14 Let SCP be a School Choice Problem, and µ a matching for it. Let us assume that each student is endowed with a linear preorder Pj in S, we define its top trading cycle matching, denoted by µttc , as the solution for the next iterative process. 23 (Step 1) Let S (C1) ⊆ S be the set of S-cycle students. Then, for each sj ∈ S (C1) set µttc (sj ) = µ (B (sj ; S)). If S (C1) = S, matching µttc is implemented and the process stops. Otherwise, let set S 1 = S \ S (C1) and go to Step 2. .. . (Step t) Let S (Ct) ⊆ S t−1 be the set of S t−1 -cycle students. Then, for each sj ∈ S (Ct) set µttc (sj ) = µ (B (sj ; S t−1 )). If S (Ct) = S t−1 , matching µttc , as described trough steps 1 to t, is implemented and the process stops. Otherwise, let set S t = S t−1 \ S (Ct) and go to Step t + 1.  A. Towards Partial Efficiency, without Increasing Segregation This subsection deals with policy P1 , the first possible objective for the MSB, establishing that minimizing segregation is its main target. Therefore, once a matching µ is socially supported because a distribution parameter α has been agreed, any further modification that the MSB might propose should exhibit the segregation level that µ does. To reach this objective, a simple way to proceed is by restricting any alternative suggestion, say µ0 , by imposing that, for each school ci , |µ (ci ) ∩ F| = |µ0 (ci ) ∩ F| , and |µ (ci ) ∩ D| = |µ0 (ci ) ∩ D| . What we propose is to apply the next procedure. Given α, let us associate 24 each SCP with its multi-stage α-fair matching. Next, given µmsα and {Ej }m j=1 , let us consider MSB-agreeing preferences for exchange satisfying that,16 for each sj ∈ D, and any two students sh and sk , (a) If sh ∈ F, then sj Pj 1 sh , (b) If sh and sk are in D, (i) If µmsα (sh ) 6= µmsα (sk ) then sh Pj 1 sk if µmsα (sh ) Pj µmsα (sk ); and (ii) If µmsα (sh ) = µmsα (sk ) then sh Pj 1 sk whenever sh Ej sk . The description for students in F is made in a similar way, just by exchanging the roles for F and D. The main properties satisfied by this procedure might be summarized as fol- lows. Theorem 15 Given a School Cllocation Problem, SCP, a distribution parameter, α, and {Ej }m j=1 , the students’ preferences for exchanging, let µ msα and µttc1 be the matchings obtained by applying the multi-stage α-fair procedure and the top m trading cycle algorithm, according to preferences Pj 1 j=1 , respectively. Then,  (a) µttc1 is G-efficient; (b) for each school ci , |µmsα (ci ) ∩ F| = |µttc1 (ci ) ∩ F|; 16 Note that, since we do not impose how students in F are compared under P 1 j , our conditions do not fully determine a specific preorder. In fact it is not necessary for our purposes. 25  (c) for each school ci , |µmsα (ci ) ∩ D| = |µttc1 (ci ) ∩ D|; and (d) for each student sj , µttc1 (sj ) Rj µmsα (sj ). Let us note that statements (a) and (d) inform us that µttc1 is not only efficient from each group point of view, but also that it is obtained by Pareto improving matching µmsα . On the other hand, (b) and (c) establish that the transition from µmsα to µttc1 does not require any modification on the segregation level, measured from the distribution of D-students among the schools. B. Towards Global Efficiency and the Level of Segregation This subsection deals with policy P2 , the second possible objective proposed for the MSB. It consists of obtaining an efficient allocation in which the level of segregation is as low as possible. To reach our aim we proceed following a similar structure to the one shown in the previous subsection. Therefore, taking µmsα as given, we propose a way to build MSB-agreeing preferences for exchanging that capture what policy P2 m suggests. Then, once Pj 2 j=1 has been specified, we apply Gale’s top trading  cycle algorithm to obtain what the MSB would propose, namely µttc2 . Given student sj ∈ D, we define Pj 2 as the preorder satisfying that, for each two students sh and sk , (a) If µmsα (sh ) Pj µmsα (sk ) then sh Pj 2 sk ; and (b) Otherwise, i.e. if µmsα (sh ) = µmsα (sk ), then 26  (i) If sh ∈ D and sk ∈ F, then sh Pj 2 sk ; (ii) If both sh and sk belong to the same group, D or F, and sh Ej sk , then sh Pj 2 sk . For each student in F, say sj , preorder Pj 2 is described in the same way as above, just exchanging the roles of D and F. Our first result in this framework deals with the global stability for the alloca- tion suggested by the MSB. Theorem 16 Let SCP = {C, S, P, Q} be a School Choice Problem, α a distribu- tion parameter, and {Ej }m j=1 the students’ preferences for exchanging. If µ ttc2 is the matching that results from applying policy P2 , then it is globally efficient, i.e. for any other matching µ0 6= µttc2 it should be sj ∈ S such that µttc2 (sj ) Pj µ0 (sj ). We next deal with the analysis of situations where segregation can be a natural property. To reach our objective, we need to introduce some additional concepts. Definition 17 Let SCP = {C, S, P, Q} be a School Choice Problem. We say that C D , C D ⊂ C, is a group of D-schools if (D.a) For each sj ∈ D, and any two schools ci ∈ C D and ck ∈ / C D , ci Pj ck , and (D.b) For each sh ∈ F, and any two schools ci ∈ C D and ck ∈ / C D , ck Ph ci . Similarly, we say that C F , C F ⊂ C, is a group of F-schools if (F.a) For each sj ∈ F, and any two schools ci ∈ C F and ck ∈ / C F , ci Pj ck , and 27 (F.b) For each sh ∈ D, and any two schools ci ∈ C F and ck ∈ / C F , ck Ph ci . Lemma 18 [Segregation Lemma] Let SCP = {C, S, P, Q} be a School Choice Problem. Let us assume that there is a group of D-schools, say C D , such that X qi ≥ d, ci ∈C D then for each distribution parameter α and any students’ preferences for exchang- ing, {Ej }m j=1 , µttc2 (sj ) ∈ C D , for each D-student sj . What the above Segregation Lemma points out can be seen as a first approach to sufficient conditions guaranteeing that segregation is a natural consequence of student characteristics. Let us observe that the above result can also be established in terms of F-students, related to conditions for a group of F-schools, as assumed in Lemma 19. Lemma 19 Let SCP = {C, S, P, Q} be a School Choice Problem. Let us assume that there is a group of F-schools, say C F , such that X qi ≥ f, ci ∈C F 28 then for each distribution parameter α and any student preferences for exchanging, {Ej }m j=1 , µttc2 (sj ) ∈ C F , for each student sj ∈ F. As a direct consequence of Theorem 16 and Lemma 18, we can find a suffi- cient condition for segregation. Theorem 20 [Segregation Theorem] Let SCP = {C, S, P, Q} be a School Choice Problem. Let us assume that there is a group of D-schools, say C D , such that X qi ≥ d, and ci ∈C D X q− qi ≥ f, ci ∈C D then for each distribution parameter α and any student preferences for exchanging, {Ej }m j=1 , µttc2 (sj ) ∈ C D , 29 for each D-student sj , and / CD µttc2 (sh ) ∈ for any sh ∈ F. Let us observe that, as long as students in D and F are treated symmetrically, we can also establish a result similar to the Segregation Theorem 20, when condi- tions are imposed on a group of F-schools. Theorem 21 Let SCP = {C, S, P, Q} be a School Choice Problem. Let us as- sume that there is a group of F-schools, say C F , such that X qi ≥ f , and ci ∈C F X q− qi ≥ d, ci ∈C F then for each distribution parameter α and any student preferences for exchanging, {Ej }m j=1 , µttc2 (sj ) ∈ C F , for each F-student sj , and / CF µttc2 (sh ) ∈ 30 for any sh ∈ D. We now proceed to give some insight on a condition guaranteeing the exis- tence of a unique school, to be called a border school, where integration occurs. Definition 22 Let SCP = {C, S, P, Q} be a School Choice Problem. We say that ci is a border school if there are two non-empty sets of schools, S F and S D such that (a) C D is a group of D-schools, (b) C F is a group of F-schools, and (c) C F ∩ C D = {ci } The next result provides sufficient conditions to have a unique school where both types of students are allocated. Theorem 23 Let SCP be a School Choice Problem. Let us assume that ci is a border school satisfying X X q1 = qk < d < qi + q 1 , and q 2 = qk < f < q i + q 2 , ck ∈C 1 ck ∈C 2 where C 1 (resp. C 2 ) is the set of schools preferred by all the students in D (resp. F), rather than ci . Then, for each α and any {Ej }m j=1 , the matching µ ttc2 satisfies (a) For each ck ∈ C 1 , µ (ck ) ∩ F = ∅; 31  (b) For each ck ∈ C 2 , µ (ck ) ⊆ F; and (c) |µ (ci ) ∩ F| = f − q 2 , and |µ (ci ) ∩ D| = d − q 1 . VI. On α and the Degree of External Fairness The aim of this section is to provide some insight on the determination of a rea- sonable range for the value of α. As a first approach, let us suppose that q = f +d. In such a case it seems reasonable to select d α= , f +d as, with no historic discrimination, it could be considered that students would be uniformly distributed around the city. Therefore, it might be expected that each district has the same proportion of D-students, yielding our previous proposal. Now, for a more general setting, when q ≥ f +d, and taking into consideration that the dispersion of students among the districts is a consequence of previous discrimination practices, students belonging to each group would propose (a) From the point of view of F-students, agents in D should have priority as regards, at most, d places, therefore the value for α should be d αF = , q (b) From the D students viewpoint, there should be, at most, f places in which students in F would have priority. Therefore, and in agreement with this 32  opinion, the value for α would be q−f αD = , q Therefore, provided that there is a conflict of interest on how the extra-places should be distributed between the students in both groups, it could be assumed that each α ∈ [αF , αD ] can somehow be justified. When evoking segregation in a particular school, what is argued is that the ratio of D-students in that school, related to the total number of accepted students, differs from an ideal ratio. In our opinion, there are some relevant variables that are not taken into account, such as the (potential) number of places, some of which may be unoccupied. This is why we propose distinguishing two types of segrega- tion, one for each reason that causes an unbalanced ratio (a) F-segregation. This is related to the case in which the number of places allocated to F-students is too large and thus the D students cannot be inte- grated; and (b) D-segregation. This occurs when the number of D students with a place is too large and prevents integration for agents in F. Definition 24 Let SCP be a School Choice Problem, and µ a matching for such an instance. We say that µ exhibits 33  (i) F-segregation at school ci if qi − |µ (ci ) ∩ F| < [αF qi ]+ ; (ii) D-segregation at school ci if |µ (ci ) ∩ D| > [αD qi ]+ ; and (iii) Segregation at school ci if it exhibits F-segregation or D-segregation. In accordance with Definition 24, given a School Choice Problem, we can describe the degree of segregation at school ci , associated to matching µ, as |µ (ci ) ∩ F| − [(1 − αF ) qi ]−  if |µ (ci ) ∩ F| ≥ [(1 − αF ) qi ]−        qi      |µ (ci ) ∩ D| − [αD qi ]+  ∆ (ci ; µ) = if |µ (ci ) ∩ D| > [αD qi ]+    qi         0   otherwise The considerations above are useful to introduce a way to measure the degree of segregation associated to a matching µ, Definition 25 Let SCP be a School Choice Problem, and µ a matching for SCP. We define the degree of segregation associated to µ as the expected segregation 34 level for the set of schools, n X qi Ψ (µ) = ∆ (ci ; µ) . i=1 q Our next result points out that the presence of a high segregation level can be a consequence of some of the following factors (1) The selection of an inappropriate value for α; (2) The existence of a high number of excess places; (3) The selected matching process. Theorem 26 Let SCP be a School Choice Problem, with m = q, and let us as- αqi ]+ = d. Then, the matching obtained ˆ such that ni=1 [ˆ P sume that there exists α by applying the multi-stage α ˆ -fair procedure, satisfies Ψ µmsαˆ = 0.
Corollary 27 Let SCP be a School Choice Problem, with m = q, and let us ˆ such that ni=1 [ˆ αqi ]+ = d. Then, for any {Ej }m P assume that there exists α j=1 , the matching that results by implementing Policy P1 , for distribution parameter α ˆ , satisfies Ψ µttc1 = 0.
35  To conclude this section, let us point out the general difficulty of guaranteeing the possibility of always reaching a null value for the segregation level. As it is usual in the (real life) description of school quotas, let us consider that there is a number of places associated to each classroom, which is the same for all schools. Let us assume that this number is 20 and, for the sake of simplicity, let us imagine that there are 150 classrooms equally distributed in 50 schools, i.e. there are 50 schools with a quota of qi = 60 each. This means that 3000 new students can be accepted. Now, let us assume that we have exactly 3000 new students so that, as assumed in Theorem 26, m = q, and they are distributed among the two categories where d = 483 and f = 2517, i.e. 16.1% of students are in D and the remaining 83.9% belong to F. In such a case, there should not be α ˆ satisfying the condition assumed in Theorem 26. This is because the number of schools is even, and thus for each α, ni=1 [αqi ]+ must be even too. Nevertheless, d is odd. P Provided that we must treat all schools in a symmetrical way, we should re- serve (at least) 10 places for D-students in each school to give them the possibility of having a place each. Let us observe that, for α0 = 0.161, [50α0 ]+ = 10. Now, to evaluate the maximum possible value of Ψ, let us assume that all the students show the same preferences, which satisfy c1 Pj c2 . . . Pj ci Pj ci+1 . . . Pj c50 Pj sj 0 In such a case matching µmsα satisfies: 36  0   • µmsα (ci ) ∩ D = 10 for each school ci ∈ C \ {c49 , c50 }; 0   • µmsα (c49 ) ∩ D = 3; 0   • µmsα (c50 ) ∩ D = 0; and 0 0     • µmsα (ci ) ∩ F  = 60 − µmsα (ci ) ∩ D, for each school ci . 0
Let us observe that this implies that ∆ ci ; µmsα = 0 for each ci ∈ / {c49 , c50 }; 0 0 ∆ c49 ; µmsα = 0.117; and ∆ c50 ; µmsα = 0.167. Therefore, Ψ (µ0 ) = 0.006,

which is the minimal value for Ψ associated to this problem, whereas its maximal value is 0.272. VII. Conclusions and Policy Suggestions This paper aims to contribute to solving a social debate, namely the design of poli- cies against segregation (or promoting integration). We concentrate on proposing procedures for the distribution of primary school places, helping to reduce the observed segregation level. This is the aim of the so-called multi-stage α-fair pro- cedure, introduced in Section IV. We then deal with the possibility of improve- ments, in terms of efficiency, for the above-mentioned allocation process. For this purpose, we consider two different frameworks, each of them associated with a different policy. The first policy deals with the case in which the level of inte- gration cannot be waived. Therefore, the notion of efficiency should be adjusted to each group of students separately. For the second policy, the efficiency level should be global. Therefore, the (previously suggested) tentative matching allows 37 the disadvantaged students a chance to obtain a better school place, in comparison with what they could obtain if the integration process was not implemented. Finally, Section VI introduces a debate on how the integration level should be evaluated. For this, according to Aristotle’s idea of potency, we consider that all the places that have not been assigned to the favored students can be distributed amongst the disadvantaged students as they wish. Therefore, in our opinion, the relevant variable to be considered for evaluating whether a particular matching procedure induces segregation is not the final outcome, based on the students’ desires. For us, it is the possibilities that the procedure itself provides to the disadvantaged students, if they wished to be integrated, that should be taken into account. To conclude we wish to layout some specific recommendations, related to a question that the MSB should solve: How many places should be offered? One could be tempted to answer by suggesting that as many as possible. Note that, by setting qi = m for each school ci , we can guarantee that each student obtains a place at her preferred school. Nevertheless, this option is neither possible, due the large number of students, nor reasonable, due to the degree of overcrowding it could induce. Imagine a small number of schools being the preferred option for all the students! On the contrary, our recommendation is highly related to avoiding an excessive offer of places, i.e. we propose to adjust, as far as possible, the number of offered places to the students’ needs, thus equalizing school quotas,17 so that 17 Our recommendation is made under the assumption that all the schools have the same number of classrooms for the new students. Otherwise, expression (1) should be reconsidered by replacing n for the total number of classrooms. In such a case, the ratio proposed in expression (1) would 38 for each school ci , h m i+ qi = (1) n Then, since the number of excess places is low enough, when α is high enough and students do not act strategically, the outcomes for the α-fair and the multi-stage α- fair deferred-acceptance procedures should coincide. Therefore, given the above school quotas, let us choose α = αD and apply the αD -fair deferred-acceptance procedure. By Theorem 8 we know that students are expected to report their true preferences. And, Theorem 26 informs us that the matching so implemented induces maximal integration, i.e. Ψ (µαD ) is close to zero. In a further step, the MSB might be interested in applying either of the policies P1 or P2 . Note that, in such a case, the strategy-proof property might be lost. Moreover, if P2 is implemented, the search for a higher efficiency could induce a lower integration level, i.e. Ψ (µttc2 ) might be very high. A further problem that has not been explored in this paper is related to the need for me MSB to implement policies P1 or P2 . Note that when q ' m the multi- stage α-fair and the α-fair deferred-acceptance procedures coincide, for α ∈ Ω. This implies that the multi-stage α-fair procedure satisfies, in such a case, the properties proposed in theorems 8 and 11. In particular, students have no reason to misreport their preferences. The introduction of policies P1 or P2 may provide students with an incentive to play strategically, and thus strategy-proofness might reflect the quota for each classroom. 39 be lost. A way to avoid such a problem can be found in how schools build their priority lists. In particular, and following Proposition 2 in Alcalde and Romero- Medina (2012), we know that when schools rankings satisfy the so called Uniform Priorities Condition, there exists a unique matching which is stable and Pareto efficient. This allows policies for the MSB to be reconsidered by redesigning how school rankings may be built, in order to avoid the implementation of policy P1 or P2 to reach optimality. References Abdulkadiro˘glu, A., 2005. College Admissions with Affirmative Action. Interna- tional Journal of Game Theory 33, 535–549. Abdulkadiro˘glu, A., Pathak, P.A., Roth, A.E., 2005a. The New York City High School Match. American Economic Review, Papers and Proceedings 95, 364– 367. Abdulkadiro˘glu, A., Pathak, P.A., Roth, A.E., 2009. Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. American Economic Review 99, 1954–1978. Abdulkadiro˘glu, A., Pathak, P.A., Roth, A.E., Sönmez, T., 2005b. The Boston Public School Match. American Economic Review, Papers and Proceedings 95, 368–371. Abdulkadiro˘glu, A., Pathak, P.A., Roth, A.E., Sönmez, T., 2006. Changing 40  the Boston School Choice Mechanism: Strategy-Proofness as Equal Access. Mimeographed. Harvard University. Abdulkadiro˘glu, A., Sönmez, T., 2003. School Choice: A Mechanism Design Approach. American Economic Review 93, 729–747. Alcalde, J., Romero-Medina, A., 2011. Fair School Placement. QM&ET Working Paper no. 11-01.. Alcalde, J., Romero-Medina, A., 2012. Equity and Efficiency in School Choice Problems. Mimeographed, University of Alicante. Alcalde-Unzu, J., Molis, E., 2011. Exchange of Indivisible Goods and Indiffer- ences: The Top Trading Absorbing Sets Mechanisms. Games and Economic Behavior, forthcoming. van Buren, P.M., 1995. A Theology of the Jewish-Christian Reality: A Christian Theology of the People Israel. University Press of America, Lanham, MD. Curran, S.R., Shafer, S., Donato, K.M., Garip, F., 2006. Mapping Gender and Migration in Sociological Scholarship: Is It Segregation or Integration? Inter- national Migration Review 40, 199–223. Dougherty, J., Harrelson, J., Maloney, L., Murphy, D., Smith, R., Snow, M., Zan- noni, D., 2009. School Choice in Suburbia: Test Scores, Race, and Housing Markets. American Journal of Education 115, 523–548. 41 Ehlers, L., 2010. School Choice with Control. Mimeographed. Université de Montréal. Ergin, H., Sönmez, T., 2006. Games of School Choice under the Boston Mecha- nism. Journal of Public Economics 90, 215 – 237. Frankel, D.M., Volij, O., 2011. Measuring School Segregation. Journal of Eco- nomic Theory 146, 1–38. Gajendragadkar, S.S., 2006. The Constitutionality of Racial Balancing in Charter Schools. Columbia Law Review 106, 144–181. Gale, D., Shapley, L.S., 1962. College Admissions and the Stability of Marriage. American Mathematical Monthly 69, 9–15. Garda, R.A., 2009. The White Interest in School Integration. Mimeographed. New Orleans College of Law, Loyola University. Kane, T.J., Riegg, S.K., Staiger, D.O., 2006. School Quality, Neighborhoods and Housing Prices. American Law and Economics Review 8, 183–212. Kesten, O., 2010. School Choice with Consent. Quarterly Journal of Economics 125, 1297–1348. Kojima, F., 2010. School Choice: Impossibilities for Affirmative Action. Mimeographed. Stanford University. 42 Niederle, M., Roth, A.E., Sönmez, T., 2008. Matching and Market Design, in: Durlauf, S.N., Blume, L.E. (Eds.), The New Palgrave Dictionary of Economics. Palgrave Macmillan, Basingstoke. Oliver, M., 1985. The Integration–Segregation Debate: Some Sociological Con- siderations. British Journal of Sociology of Education 6, 75–92. Roth, A.E., 1982. The Economics of Matching: Stability and Incentives. Mathe- matics of Operations Research 7, 617–628. Roth, A.E., Peranson, E., 1999. The Redesign of the Matching Market for Amer- ican Physicians: Some Engineering Aspects of Economic Design. American Economic Review 89, 748–780. Roth, A.E., Sotomayor, M.O., 1990. Two-Sided Matching: A Study in Game- Theoretic Modeling and Analysis. Cambridge University Press, New York. Roth, A.E., Xing, X., 1994. Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions. American Economic Review 84, 992–1044. Seitles, M., 1998. The Perpetuation of Residential Racial Segregation in Amer- ica: Historical Discrimination, Modern Forms of Exclusion, and Inclusionary Remedies. Journal of Land Use and Environmental Law 14, 1–38. Shapley, L.S., Scarf, H., 1974. On Cores and Indivisibility. Journal of Mathemat- ical Economics 1, 23–37. 43  APPENDIX A. Proving Theorem 8 The aim of this appendix is to propose formal proof for Theorem 8. Let us remem- ber that this statement informs about certain properties satisfied by the matching µα , obtained by applying the α-fair deferred-acceptance procedure. Let us observe that what this allocation procedure proposes is the following. First, given a School Choice Problem, SCP = {C, S, P, Q}, let us associate to each school ci a number of reserved places for students in D, say di ≤ qi , such that18 n X d≤ di (A1) i=1 Then, we can consider the School Choice Problem whose elements are (i) The set of schools is C, where the quota for school ci is di ; and its priority list is ΠD i ; and (ii) The set of students is D, where preferences for student sj ∈ D are Pj . Let us compute the student optimal stable matching for such a problem. Then, when the quotas for schools are induced by some α, as assumed in Theorem 8, for each student in D, its mate at µα coincides with the student optimal matching for the above problem. 18 The assumption that α ∈ Ω induces the next condition, which is sufficient for all the properties satisfied by µα except the one related to α-fairness. 44  Since for each student sj ∈ D, and any college ci , ci Pj sj ; each student is admissible at any school; and, by condition (A1), the number of available places is not lower than the number of students, we have that (a) µα is D-stable; (b) For each student sj ∈ D, µα (sj ) ∈ C; and (c) By Theorem 5 in Roth (1982), we have that truthful revelation is a dominant strategy for all students in D. The second step in the description of the α-fair deferred-acceptance procedure lies in agents in F. In this step, given the previously determined allocation for the D-students, {µα (sh )}sh ∈D , the School Choice Problem to be considered is the following (i) The set of schools is C, where the quota for school ci , namely qiF , is qiF = qi − |µα (ci ) ∩ D| ; and its priority list is ΠF i . (ii) The set of students is F, where preferences for student sj ∈ F are Pj . To complete the α-fair deferred-acceptance procedure, we apply the student optimal stable mechanism to the previous problem. Let us observe that (a) µα is F-stable; 45  Pn F (b) i=1 qi = q − d ≥ f . Moreover, students in F consider that any school is preferred to not being allocated a place; and all schools consider that all students are acceptable. Therefore, for each student sj ∈ F, µα (sj ) ∈ C; and (c) By Theorem 5 in Roth (1982), we have that truthful revelation is a dominant strategy for all students in F. Now, let us observe that, for each α, α ∈ Ω, and any school ci , |µα (ci ) ∩ D| ≤ [αqi ]+ , which implies that µα is αF -fair. To conclude, let us assume that, for some SCP there is α yielding a matching µα which is not (1 − α)-fair from D’s point of view. This implies that there is a student sj ∈ D and school ci such that ci Pj µα (sj ) and |µα (ci ) ∩ F| > [(1 − α) qi ]− which is equivalent to |µα (ci ) ∩ D| < [αqi ]+ , contradicting D-stability of µα .  46  B. Proving Theorem 11 This appendix proposes formal proof for Theorem 11. To reach our objective, we proceed as follows. Let SCP be a School Choice Problem, and µmsα the realization of the algorithm introduced in Definition 9. First, we see, in Lemma A1, that µmsα is G-stable. Secondly, Lemma A2 establishes the α-fairness of µmsα . Finally, through Lemma A3, we show that the optimality condition (3) in Definition 10 is satisfied by µmsα . Let us remember that µt denotes the (tentative) matching obtained at the end of the t-th step of the multi-stage α-fair algorithm introduced in Definition 9. Lemma A1 Let SCP be a School Choice Problem and, for α ∈ [0, 1] given, µmsα its multi-stage α-fair matching. Then µmsα is G-stable for SCP. Proof Let us observe that, by Theorem 8, µ1 is α-fair and G-stable. Moreover, by con- struction, at each step t, µt is also G-stable. Since there is some finite tˆ, at which µtˆ = µmsα , the result follows.  Lemma A2 Let SCP be a School Choice Problem and, for α ∈ [0, 1] given, µmsα its multi-stage α-fair matching. Then µmsα satisfies α-fairness. Proof To see that µmsα is α-fair, let us assume that, contrary to our conclusion, there is a School Choice Problem, SCP, and an α ∈ [0, 1] such that its multi-stage α-fair 47 matching, say µmsα , fails to be α-fair. This implies that there is a school ci and student sj such that ci Pj µmsα (sj ) and (a) If sj ∈ D, then |µmsα (ci ) ∩ F| > [(1 − α) qi ]− ; or (b) If sj ∈ F, then |µmsα (ci ) ∩ D| > [αqi ]+ . We next show that none of the above situations could occur. Let us assume that sj above is a student in F. Then µ1 should satisfy that µ (ci ) ∩ D ≤ [αqi ]+  1  Therefore, there should be one step, say t, such that  t    µ (ci ) ∩ F  < qi − µt (ci ) ∩ D . (A2) Let t0 be the lowest value of t for which condition (A2) holds. 0 Since the algorithm is student monotonic, this contradicts F-stability of µt . This is because 0 (1) Since ci has a vacancy at stage t0 , this would imply that µt (sj ) Pj ci ; 48  0 (2) By student monotonicity, µmsα (sj ) Rj µt (sj ); then, (3) By transitivity, µmsα (sj ) Pj ci . Therefore, if µmsα is not α-fair, then sj should be a student in D. Then, since (1) ci Pj µmsα (sj ), by hypothesis, and (2) µmsα (sj ) Rj µ1 (sj ), by student monotonicity, we have that transitivity implies that ci Pj µ1 (sj ). Therefore, since µ1 is G-stable, we have that µ (ci ) ∩ F  ≤ [(1 − α) qi ]− .  1  Note that, since µmsα is not α-fair, there should be some step, say t, in which µ (ci ) ∩ F  > [(1 − α) qi ]− .  t  (A3) Let t0 be the lowest value of t for which condition (A3) holds. This implies that, at stage t0 , µ 0 (ci ) ∩ D < [αqi ]+ .  t  Then, G-stability of µt0 implies that µt0 (sj ) Pj ci . A contradiction.  49 Lemma A3 Let µ0 be a G-stable matching for SCP, µ0 6= µmsα , such that for all sj ∈ S, µ0 (sj ) Rj µmsα (sj ). Then, there exists ci ∈ C such that |µ0 (ci ) ∩ D| < |µmsα (ci ) ∩ D| . (A4) Proof Let µ0 be a matching satisfying the assumptions of Lemma A3. Let us assume that condition (A4) does not hold. Then, for each school ci |µ0 (ci ) ∩ D| ≥ |µmsα (ci ) ∩ D| . (A5) Since each student sj will be allocated a place at some school, we have that X X d= |µmsα (ch ) ∩ D| ≤ |µ0 (ch ) ∩ D| . (A6) ch ∈S ch ∈S Note that (A5) and (A6) together imply that, for each ci |µ0 (ci ) ∩ D| = |µmsα (ci ) ∩ D| . (A7) Now, let tˆ be the last step in the multi-sequential α-fair deferred-acceptance algorithm, i.e. tˆ is such that µtˆ = µmsα . In sub-step tˆ.a , when analyzing the
n o problem C, D, PD , QD(t) , we have that, for each school ci , ˆ D(tˆ) qi ≥ |µmsα (ci ) ∩ D| = |µ0 (ci ) ∩ D| . 50 Note that G-stability of both µmsα and µ0 implies stability of [µmsα ]D and [µ0 ]D , n o respectively, for C, D, PD , QD(t) . ˆ Given that [µmsα ]D is the student-optimal stable matching for the problem n o C, D, PD , QD(t) , and [µ0 ]D Pareto dominates [µmsα ]D , following Theorem 2 in ˆ Roth (1982), we should conclude that [µmsα ]D is D-unstable. A contradiction.  C. Proving Results in Section V The aim of this appendix is to provide formal proof for each of the main results in Section V. To reach our objective, we will highlight the close relationship between the processes described in this section, and ways to solve housing problems, in- troduced by Shapley and Scarf (1974). The situation described in these problems can be introduced as follows. A group of individuals, each owning an indivisi- ble object, face the possibility of reallocating the objects according to their own interests. The primitives for such problems are • A set of m agents, A = {1, . . . , j, . . . , m}; • A set of m objects, O = {o1 , . . . , oj , . . . , om },19 and • For each agent, say j, a transitive and complete binary relation on O, %j . This is interpreted as j’s preferences on the set of objects. According to our model, given a SCP and a matching µ, S can represent the set of agents. Therefore, the set of objects can be identified with the set of person- alized school places; i.e. for each student sj , oj = µ (sj ). The element which is 19 In this description object oj is usually interpreted as the initial endowment of agent j. 51 still momentarily imprecise is how to describe students’ preferences. In general, for a given student, say sj , %j might depend eventually on four factors, namely (1) student preferences, Pj ; (2) the initial matching, µ; (3) student preferences for exchanging, Ej ; and (4) the policy that the MSB wish to implement. Proof of Theorem 15 Let us observe that, when policy P1 is implemented, the MSB-agreeing prefer- ences for exchange imply that, for any two students, sj ∈ D and sh ∈ F, and any initial matching µ, µ (sj ) Pj 1 µ (sh ) , and µ (sh ) Ph 1 µ (sj ) (A8) Taking into account Alcalde-Unzu and Molis (2011), Theorem 4, we have that m µttc1 should be efficient regarding preferences Pj 1 j=1 . Let us observe that  efficiency and condition (A8) imply that (a) All the exchanges are intra-group; i.e., for each student sj , if when applying the top trading cycle algorithm, sj ∈ S (Ct) , then B sj ; S t ∈ D if, and only if sj ∈ D;
which implies that for each school ci ,   |µmsα (ci ) ∩ D| = µttc1 (ci ) ∩ D , 52  and   |µmsα (ci ) ∩ F| = µttc1 (ci ) ∩ F  . D (b) [µttc1 ] is efficient for SCP D ; F (c) [µttc1 ] is efficient for SCP F . To conclude, let us assume that, for student sj , µttc1 (sj ) is determined at stage t. This implies that µttc1 (sj ) = µmsα (B (sj ; S t )). Since sj ∈ S t , we have that µttc1 (sj ) Ri µmsα (sj ).  Proof of Theorem 16 Let us observe that implementation of policy P1 by the MSB implies that the reallocation of places for the two groups of students might be considered as an isolated problem, as illustrated in condition (A8). Nevertheless, when policy P2 is implemented, it is not necessarily the case. Therefore, our result follows on from Theorem 4 in Alcalde-Unzu and Molis (2011).  Proof of Lemma 18 Let us assume that there is a group of D-schools, say C D satisfying X qi ≥ d. ci ∈C D Since µmsα is G-stable, as shown in Theorem 11, we have that, for each sj ∈ D, if / C D , then it should be the case that |µmsα (ci )| = qi for each ci ∈ C D . µmsα (sj ) ∈ 53 Moreover, by Theorem 16 we know that µttc2 must be efficient. This implies that µ (sj ) ∈ C D , for each sj ∈ D, yielding the desired result.  Proof of Theorem 20 Note that, under our assumptions, by Lemma 18 we have that the students in D should get a place at a D-school. Moreover, since X f ≤q− qi , ci ∈C D we have that C \ C D is a set of F-schools with enough places to allocate to all the F-students. Therefore, since µttc2 has to be efficient, we have that µttc2 (sj ) ∈ C \ C D ; which is the desired result.  Proof of Theorem 23 Let us observe that C 1 ∪{ci } is a group of D-schools. Therefore, by Lemma 18 we have that no D-student would occupy a place in a school being in C 2 . Similarly, we can see that C 2 ∪ {ci } constitutes a group of F-schools. Thus, by Lemma 19, we have that µttc2 (ck ) ⊆ F, for each ck ∈ C 2 ∪ {ci }. On the other hand, since X X qk < d < q i + qk , ck ∈C 1 ck ∈C 1 54 and µttc2 is efficient, we have that for each school ck ∈ C 1 ,  ttc  µ 2 (ck ) ∩ D = ck , which implies that  ttc  X µ 2 (ci ) ∩ D = d − qk . ck ∈C 1 A similar reasoning for students in F, related to colleges belonging to C 2 , informs us that the number of F-students getting a place at ci is f − q 2 .  D. Proving Theorem 26 To prove Theorem 26, let us observe that the existence of α ˆ such that n X αqi ]+ = d, [ˆ (A9) i=1 and the fact that m = q imply that µmsαˆ = µαˆ , i.e. the multi-stage α ˆ -fair algorithm stops at its first step. This implies that, for each school, say ci , α q i ]+ .  msαˆ  µ (ci ) ∩ D = [ˆ 55    Moreover, since m = q, we have that, for each school, say ci , µmsαˆ (ci ) = qi . Therefore α q i ]+ ;     qi − µmsαˆ (ci ) ∩ F  = µmsαˆ (ci ) ∩ D = [ˆ which is equivalent to establishing ˆ ) q i ]− ,  msαˆ  µ (ci ) ∩ F  = [(1 − α
which implies that, for each ci ∈ C, ∆ ci ; µmsαˆ = 0.  56