On Stability and Efficiency in School Choice Problems

M PRA Munich Personal RePEc Archive On Stability and Efficiency in School Choice Problems Jose Alcalde and Antonio Romero-Medina University of Alicante 13. February 2011 Online at http://mpra.ub.uni-muenchen.de/28891/ MPRA Paper No. 28891, posted 21. February 2011 01:26 UTC  On Stability and Eciency in School Choice Problems∗ † ‡ José Alcalde Antonio Romero-Medina February 13, 2011 Abstract This paper proposes a way to allocate students to schools such that conciliates Pareto eciency and stability. Taking as a starting point the recent reform proposed by the Boston School Committee, we propose a marginal modication to reach our objective redene how students are prioritize. Our proposal is to allow schools to prioritize only a small set of students an then use a common priority order for the rest. Under this condition we propose a score based priority ranking that makes the output of the new Boston Mechanism Pareto ecient and stable. Keywords: School allocation problem, Pareto ecient matching. Journal of Economic Literature Classication Numbers: C71, C72, D71. ∗ The authors acknowledge Salvador Barberà, Josep E. Peris and Pablo Revilla for the many discussions we had around this paper. We would also like to acknowledge the nancial support by the Institut Valencià d'Investigacions Econòmiques, FEDER and the Spanish Ministerio de Educación y Ciencia under projects SEJ2007-64649 (Alcalde) and ECON2008- 027038 (Romero-Medina). † Corresponding Author. IUDESP, University of Alicante. [email protected] ‡ Universidad Carlos III de Madrid. [email protected] 1 Introduction On the school choice procedures the way municipalities decide the design in- strument to allocate student to schools play a key role. In this instruments the municipalities are forced to establish priorities in order to allow break the ties that arise when the system takes into account the parents' interests for the schools. In this present paper we deal with way in which the schools' priority lists are built. We propose a conditions on agents' characteristics that solve the eciency-equity trade o by proposing a priority structure able to reconcile eciency and stability. Municipalities use dierent criteria to build priority as preference for, oth- erwise indierent, centers. When the list of criteria that provides priorities to students is not enough to break all relevant ties the municipalities are forced to use a sort of random process to break the ties. Even though the criteria used by the schools to prioritize students can be seen as eciency criteria, the realization of the procedure, to match students and schools' places, could induce inecient allocations. This is due to the particular procedure employed to allocate the schools' places among the students. In this sense, we can mainly nd two systems: The centralized ones, that focus on stability, and the decentralized ones, focusing on Pareto eciency. The mechanism used in the Boston area, from 2005, can be seen as a representative example for the rst one, whereas the Boston mechanism, used in the same area until that date, is a representative example for the second one. The reader can nd a description for both mechanisms in the survey by Sönmez and Ünver (2009). In this paper we concentrate on the former, the Student-Optimal Sta- ble mechanism, (SOSM hence for) which coincides with the realization of the deferred acceptance algorithm in which students send proposals to the schools. This mechanism, introduced by Gale and Shapley (1962), always selects a sta- ble allocation. Moreover, all the students (weakly) prefer this allocation to any other stable allocation. Furthermore, when this mechanism is use, students have no interest on acting strategically. Along with the Boston area the redesign that has been introduced in several markets have presented the SOSM as the best option for school markets, i.e. for one sided-markets with indierences. However, the fact this mechanism is, in general, not ecient has trouble scholars (see Kesten, 2010 and Abdulkadiro§lu, Patha, and Roth, 2009). In general it can be shown that the welfare lost due to select the SOSM can be large. There has been several attends to address this problem. In general this attempts accommodate any preexisting priority struc- ture by allowing a nal allocation that relax some priorities in order to achieve eciency (see Kesten, 2010) or allows the agents to trade their initially stable endowments until reaching an allocation that can not be justiably objected by any student (see Alcalde and Romero-Medina, 2010). In any of those attempts the initial priority structure is, at some point, either modify or ignored. In both case it seem a better design approach to build a priority structure that reconciles eciency and stability rather than impose priorities that will impose eciency lost or, ultimately, will be relax or ignore. 1  The usual way to prioritize students in most school districts to establish priorities comes from the use of a scoring rule. In practical terms the way to deal with the problem of how students would be prioritized is solved by municipalities building a function that associates each student a score for each school. This function often depends on two classes of variables: the relationship between the student and each school includes and the student's characteristics that are not related to any school. Among the rst, are the distance from the student's residence to the school; and the number of siblings, already attending to the school. Among the second group we can mention the household income, the student's household size or the presence of any health condition. Further more, this criteria is based on continuous variables that are transform into discrete counterparts in order to be processed. For instance the distance to school is a continuous criteria that is transform into a discrete one using attendance area boundaries that denes the schools in which each students will be prioritized based on her address. By its denition the School Attendance Area Policies assign the same score to students in the same area and forces the procedure to relay on a lottery drawn to build strict priority list. In our model, we do not assume any particular geographical distribution of students and/or schools, we will assume that schools' priority lists need not to be correlated and each school might exhibit any priority list. This is why, throughout this paper claim that each school is free to decide how it prioritizes the students. Accordingly, we refer the policy of accurately redesigning each school attendance area as schools limited freedom to prioritize the students. In this paper we show that eciency and equity are compatible if we proceed as follows: Let us consider two classes of priority lists, namely the local and the school lists. Then, for a given school, its priority list is used to prioritize (at most) as much students as it can accept. These students will have priority over any other student. The remaining students are prioritized by following the local committee 's list. Following this approach, the general recommendation of this paper is to restrict, for each school, the number of students belonging to its inuence area. Therefore, what the Local School Committees would do is to redesign their school attendance areas. Following, Abdulkadiro§lu et al. (2006), the recent reforms in the alloca- tion mechanisms lies on avoiding the possibility of students' strategic behavior. What it seems to be relevant when designing a mechanism for school allocation problems is to accurately combine stability, eciency and strategy-proofness. Let us notice that restricting the possible priority lists that schools can pro- pose, our results point out that the use of the new mechanism in the Boston Area always selects stable and ecient allocations and this mechanism is fully strategy-proof1 , i.e. not only students have no interest on misrepresenting their preferences, but it should be also expected that schools do not prioritize students in a wrong way.2 1 The result follows from Alcalde and Barberà (1994) 2 In Valencia, Spain, the admission process is similar tothe Boston mechanism. The schools prioritize students according to a scoring function that is established by law. Nevertheless, the score that a school assigns to a student is evaluated by the school, and it is not monitored 2  As Ergin (2002) shows the conditions that reconciles stability and Pareto eciency are very stringent and involves check the preferences and priorities of agents in both sides of the market. In particular, if each student is free to rank any school as her best school, it is always possible to nd non-scarce problems having a stable and Pareto ecient matching. Therefore, if conditions are es- tablished on individual characteristics, it is very hard to have in mind natural necessary conditions guaranteeing the existence of a stable and Pareto ecient matching. Our work is closely related to Ergin (2002) and latter extended by Elhers and Erdil (2010) . They characterize priority structures under which the constrained ecient assignments are ecient. Our proposal diers from theirs in the fact that we explore the possibility to propose score based priority rankings. The rest of the paper is organized as follows. Section 2 introduces the basic framework and provides some denitions which are classical in the literature. Section 3 explores conditions on agents' characteristics under which ecient and stable allocations exist. Our conclusions point out a general diculty to conciliate both concepts. This diculty advices us that we should shift the focus on how the allocation problem could be solved. The solution could be found in a reconsideration on how the schools give priorities to the students. We propose a general formulation that can be used as a new way to discuss how the system should be reformed. The way in which this mechanism is described points out how the actual Boston system might be re-reformed. Conclusions are gathered to Section 4. Finally, all the proofs are relegated to the Appendix. 2 The School Allocation Problem The School Allocation Problem family of problems faces two set of non-empty disjoint agents to be called Students and Schools. The set of Students is denoted by S , and has n individuals, i.e. S = {s1 , . . . , si , . . . , sn }. The set of Schools is denoted by C , and has m elements, i.e. C = {c1 , . . . , cj , . . . , cm }. Each school has a number of seats (or places), to be distributed among the students, that will be called its capacity. Let qcj ≥ 1 denote school cj 's capacity; and let Q = qc1 , . . . , qcj , . . . , qcm the vector summarizing schools' capacities. Schools are also endowed a priorities linear ordering over the set of students. Let πcj ∈ <n be the students' ordering for school cj and Π the (m × n)-matrix summarizing these priorities. Formally, πcj is described as a n-dimensional vector such that for each k ∈ {1, . . . , n} there is a unique student si for which πcj si = k ; given this description, the j -th row for matrix Π coincides with vector πc j . Note that, under our description, no school would consider a student to be inadmissible. Notice that most of the legislative norms impose such a restriction in the way that the schools rank their potential students. Nevertheless, our model might capture the possibility of a student to be inadmissible at a low by the local administration. This lack of monitoring allows the schools to favor some students. This behavior can be interpreted as a manipulation by some schools administrators. 3 cost: just by introducing a new variable for each school dening the priority level of the last admissible student. On the other side, each student has linear preferences over the set of schools, so that no student will consider two dierent schools as equivalent (or indier- ent), and no school is neither considered as inadmissible by any student. Let ρsi denote the schools' ranking induced by student si 's preferences,3 and Φ the (n × m)-matrix summarizing these rankings. Note that our model assumes that each student considers all the school as admissible.4 Nevertheless, we can also reformulate this model by assuming that each student might consider some schools as unacceptable. The essence of this paper is the same in both frame- works. Therefore, a School Allocation Problem can be described by listing the el- ements above: SAP = {S, C; Φ, Π, Q}. We will say that a School Allocation Problem is non-scarce whenever there is enough places to allocate all the stu- dents X qcj ≥ n. cj ∈C Given a School Allocation Problem, SAP , a solution for it is an application µ that matches students and schools' places. Such a correspondence is called a matching. Formally, Denition 1 A matching for SAP , a School Allocation Problem, is a corre- spondence µ, applying S ∪ C into itself, such that: (a) For each si in S , if µ (si ) 6= si , then µ (si ) ∈ C ; (b) For each cj in C , µ (cj ) ⊆ S , and |µ (cj )| ≤ qcj ; 5 and (c) For each si in S , and any cj in C , µ (si ) = cj if, and only if, si ∈ µ (cj ). The central solution concept used through the literature is stability, as de- ned by Balinski and Sönmez (1999). This stability notion coincides with the pair-wise stability introduced by Gale and Shapley (1962). Under our consider- ations (i.e., each school is acceptable for any student and vice versa), stability is dened as follows. Denition 2 A matching for SAP , say µ, is said stable if there is no student- school pair (si , cj ) such that (a)µ (si ) = si , or ρs c < ρs µ(s ) ; and i j i i (b) |µ (cj )| < qcj , or πcj si < πcj sh for some sh ∈ µ (cj ). Throughout this paper, we adopt the convention that ρsi µ(si ) = m + 1 whenever µ (si ) = si . 3 I.e., ρ indicates that student si considers that cj is her third-best school. si cj = 3 4 Here, we can also invoke legislative regulations establishing that school attendance is compulsory for the children of certain ages. 5 Throughout this paper |T | will denote the cardinality of set T . 4  The idea of instability comes basically from the notion of justied envy. (See Haeringer and Klijn, 2009). Let us consider a matching µ, and let us assume that student si prefers to study at school cj rather that developing her educative formation at her actual school µ (si ). If si has a priority higher than that of some of the actual students attending school cj , or this school is still having some vacant, she might claim that the allocation process has been unfair. A second notion that has also been analyzed in this framework is that of eciency. To introduce appropriately this concept, let us remember that the only role for the schools is to provide educational services needed by the students. Therefore the natural notion of eciency, as proposed by Balinski and S
'onmez (1999) for this framework, is Pareto eciency (from the students' point of view). Denition 3 Given a School Allocation Problem, SAP , we say that matching µ is Pareto ecient if for any other matching µ0 there is a student, say si , such that ρsi µ(si ) < ρsi µ0 (si ) . Note that, for any non-scarce School Allocation Problem, stability and/or eciency of a matching µ implies that, for each student si , µ (si ) ∈ C . A matching mechanism is a regular procedure that associates to each School Allocation Problem a matching for such a problem. A matching mechanism M is said to be stable if, for any given problem, it always selects a stable matching. Similarly, we say that a matching mechanism is Pareto ecient whenever its outcome is always Pareto ecient, related to its input. It is easy to see that there are stable matching mechanisms. In fact, any of the versions of the deferred- acceptance algorithms proposed by Gale and Shapley (1962) associates a stable matching for the related School Allocation Problem. On the other hand, the now-or-never mechanism introduced by Alcalde (1996) always selects a Pareto ecient matching when the proposals are made by the students.6 It is a well known result that it might be an impossible task to conciliate stability and Pareto eciency, i.e. there is no matching mechanism selecting a stable and Pareto ecient allocation for each School Allocation Problem. In the next section we seek the existence of natural conditions on Φ and Π guaranteeing the existence of matching mechanisms being stable and Pareto ecient. 3 On the existence of stable and Pareto ecient allocations In this section we explore natural conditions under which stability and Pareto eciency are compatible for some matching mechanisms. Given that set of stable matchings has a lattice structure and one of its extremes can be reached by applying the student-proposing deferred acceptance algorithm. Therefore, the 6 The now-or-never mechanism is also known as the Boston mechanism because it was used in the Boston school district. 5 unique stable matching mechanism that could eventually be Pareto ecient is the so called Student-Optimal Stable mechanism. The question is whether on the framework of the school choice problem are conditions able to encompass both the uses of school districts on the priorities matrices under which the students optimal stable matching is always ecient. To provide a positive answer to the above question, let us consider the following condition on schools' priorities: Denition 4 We say that the schools' priorities matrix Π satises the Com- mon Priorities Condition , CPC in short, if, and only if, there is a (xed) relation of students' priorities, π = (πs , . . . , πs , . . . , πs ), such that for each 1 i n school  cj , and `preferred set of students' for such a school, S ⊆ S , with j S  ≤ qs , its priority relation satises: j j (a) πc s ≤ qc , for each si ∈ S j ; and j i j (b) πcj si = S j  +  sh ∈ S \ S j : πsh ≤ πsi , for each student si ∈/ S j .     Let us imagine that students are ordered following a common criterion, which is independent from the schools characteristics and does not depend on the distance from the students' residence to the school, neither on whether the students have or not any sibling at the school, or any similar criteria. Then, once such common priorities have been xed, each school can modify it by selecting its ideal set of students, whose size must be not higher than the number of its available positions, but the rest of (`non-ideal') students must be prioritized following a common criterion. We can now establish the following result. Proposition 5 Let SAP be a School Allocation Problem. If Π satises CPC, then it has only one matching being stable and Pareto ecient. We can dene a condition, similar to CPC, applying to students' character- istics. This is the essence of CRC. Denition 6 We say that the students' rankings matrix Φ satises the Com- mon Ranking Condition, CRC in short, if, and only if, it is possible to nd a linear order over the set of schools C , described by the ranking ρ = ρc , . . . , ρc , . . . , ρc , such that for each student, si , and school cj ,
1 j m if ρck < ρcj  1 + ρcj ρsi cj (si ) = ρcj if ρck > ρcj where ck is such that ρsi ck = 1. To introduce the idea underlying CRC, let us imagine that there is an unam- biguous way to order the schools (that can be derived from some quality index that is commonly accepted), but each student has a preferred school due to some specic criteria (for instance due to its proximity to the student's residence ad- dress; or because she has some sibling attending to that school; or because her 6 parents studied at that school; etc.) CRP says that all the students will share the same preferences except that they can dier on which her ideal school is. Unfortunately, as the next example points out, a result similar to Proposition 5 can not be reached just by assuming that students' ranking satises CRC. We need an extra qualication, which is that all the students share the opinion on which her ideal school is. Example 7 Let us consider a School Allocation Problem involving three stu- dents and two schools, having one vacant each. Let us assume the ranking and priorities matrices are   1 2   2 3 1 Φ= 2 1 ; and Π= 1 3 2 2 1 Note that this School Allocation Problem satises CRC. Nevertheless, the unique stable matching is described as µ, where µ (s1 ) = c2 ; µ (s2 ) = c1 ; and µ (s3 ) = s3 , which is inecient. What this example might suggest is that the non ex- istence of a stable and ecient matching is related to the fact that this School Allocation Problem is scarce. Nevertheless, it is not true. Just to show it, let is imagine that there is a new school, c3 and the new problem, consistent with the previous one, is described by     1 2 3 2 3 1 0 Φ = 2  1 3 ; and 0 Π = 1  3 2  2 1 3 3 2 1 Note that, for any qc3 ≥ 1, the unique stable matching is µ0 , where µ0 (s1 ) = c2 ; µ0 (s2 ) = c1 ; and µ0 (s3 ) = c3 . The next result proposes conditions that, when imposed on students' rank- ings, guarantee the existence of a stable and Pareto ecient matching. Proposition 8 Let SAP be a School Allocation Problem. If Φ satises CRC, and all the students exhibit the same ranking, then there is a unique stable and ecient matching. Let us mention that the CRC was proposed by Alcalde and Barberà (1994) as an example for Top Dominance, a condition guaranteeing the existence of strategy-proof stable matching mechanisms for the marriage problem.7 It is also easy to check that, given the close (formal) relationship between the School Allocation and the Marriage Problems, CPC is also related to the fulllment of Top Dominance by the schools' declared preferences (or priorities). 7 A marriage problem, as modeled by Gale and Shapley (1962), can be described as a School Allocation Problem in which all the colleges have just a vacant position. 7 Denition 9 Let Ri be a set of possible rankings for student si . We say that Ri satises Student Top Dominance if for each cj and ck in C , and any two rankings ρs and ρ0s in Ri if ρs c < ρs c and ρ0s c < ρ0s c then i i i j i k i k i j ch ∈ C : ρsi ch ≤ ρsi cj ∩ ch ∈ C : ρ0si ch ≤ ρ0si ck = ∅.   Denition 10 Let cj ∈ C be a school, with admission quota qc , and Pj be a j set of possible priorities for such a school. We say that Pj satises School Top Dominance if there is a set of students S j ⊂ S , with S j  ≤ qc − 1 , such that j for each si and sf in S , and any two priorities πc and πc0 in Pj if πc s < πc s j j j i j f and πc0 s < πc0 s then j f j i n o sh ∈ S : πcj sh ≤ πcj si ∩ sh ∈ S : πc0 j sh ≤ πc0 j sf ⊆ S j .  The idea that schools have some freedom on how to order their chosen stu- dents is behind School Top Dominance. But such a freedom is not full range in the sense that the student which is prioritized to fulll the college's quota (i.e. πcj si = qcj ) determines which the priority for the rest of students is. In particular, let us observe that, when qj = 1 for each school cj , the School Top Dominance introduced in Denition 10 coincides with the Top Dominance as dened by Alcalde and Barberà (1994). The next example points out a general diculty to generalize the notions of CPC and/or CRC having positive results similar to the ones proposed in Propositions 5 and 8. Example 11 Let us consider a School Allocation Problem involving three stu- dents and three schools, having one vacant each. Let us suppose that schools priorities are described by matrix, satisfying School Top Dominance,   3 2 1 Π= 2 1 3  1 3 2 Now, let us assume that all the students agree that school c2 is their worst option. In such a case, and when imposing Student Top Dominance, we have the following two possibilities: (a) All the students exhibit the same ranking, and (b) Students might have opposite opinions on how to rank schools c1 and c3 . Note that if the rst case holds Proposition 8 applies and thus, there is a unique (assortative) stable matching, which is also Pareto ecient. Nevertheless, if it is not the case, the rankings matrix might be   1 3 2 Φ= 3 1 2  3 1 2 8 and the unique stable matching that this problem has is not Pareto ecient. As a conclusion we can say that when the students exhibit rankings satisfying Top Dominance and there is a common opinion on ranking some school as the best one (or the worst one) we can have any of the following two conclusions: (i) If we add an anonymity condition, as Alcalde and Barberà (1994) proposed, to the Top Dominance idea, all the students will exhibit the same rank- ing. Therefore, the conclusion is that there is a unique (assortative) stable matching which is also ecient, as established in Proposition 8. (ii) On the contrary, if such an anonymity is not demanded, we cannot guar- antee the existence of a stable and Pareto ecient matching. We proposes a way to reformulate how students would be prioritized. As we have mentioned before students are prioritized following a scoring function that can be seen as a function which is separable on two classes of variables. The rst type of variables lies on the relationship between any student and each school. Following this conception, it is expected that each student obtains dierent scores from two schools and also that each school assigns dierent scores to any two students. Relative to the second class of variables, they are not related to any school. Therefore, we can identify the score that each student obtain, from a school, relative to the rst scoring function, with its score by that school;8 whereas the score assigned to each student, that does not depend on their relationship with any school, can be seen as a score assigned by the Local School Committee. The above interpretation allows us to dene two scoring functions, to be called the School Scoring Function, CS , and the Local Scoring Function, LS . The last question that we deal with, related to this score-based way to build schools' priority list, lies on how to combine the School Scoring Function and the Local Scoring Function to dene a Global Scoring Function. Following the idea beyond the procedure used by the Seattle School Board, let us dene, for each school, its Priority students as those for which the School Scoring Function is the relevant function for deciding their score. Therefore, we can formally describe the Global Score for an student as follows.9 Denition 12 Let S and C be the sets of students and colleges respectively. We dene the Global Score Function induced by the School Scoring Function CS : S × C → <+ ; the Local Scoring Function LS : S → <+ ; and the Priority 8 Let us remember that the scores are determined by the Local School Committees, and also that schools do not determine their priority lists. Thus, we are abusing interpretation when saying that the school determines the score. We hope the reader not to be induced to confusion due to such an abuse. 9 The reader can think on dierent ways to describe a Global Scoring Function by, for instance, adding the Local and the School Scoring Functions. Nevertheless, what it is rele- vant to reach our positive results formalized in Theorem 14 is not related to the particular composition but on the fact that it induces schools priorities satisfying CPC. 9 Function P : C → 2S as the function GS : S × C → <+ assigning each student-school pair the value if si ∈ P (cj )   LS (si ) + CS (si , cj ) GS (si , cj ) =  LS (si ) otherwise To introduce the next denition, for a Local Scoring Function, LS , let M denote the maximum score allocated to a student, M = max LS (si ) (1) si ∈S Denition 13 Let S and C be the sets of students and colleges respectively, and let Q be the vector summarizing school's capacities. Given the Scoring Functions LS , CS ; and P , we say that the Scoring Function GS , satises the Limited Freedom Condition , LFC henceforth, if it fullls: (a) For each school cj , and student si , CS (si , cj ) > M. (b) For each school cj , |P (cj )| ≤ qcj , and (c) For any two students si , sh , si 6= sh , LS (si ) 6= LS (sh ) . Note that, under LFC, the induced priority ordering for a school, if it chooses the function CS, allows the school to decide which its best students are, to fulll its available places. Nevertheless, once some student has been declared not to be one of the qcj -top students, the school's opinion is not taken into account to determine such a student's priority. A second aspect that we want to remark is that, even though in our model each priority ordering is linear, Denition 13 allows that some students, in the qcj rst positions, share the same priority. Note that this fact does not inuence the stability of any matching, even though if it considers that all those students are equaled prioritized. The reader is refer to Ehler and Erdil (2010) for a full characterization of Stable and Ecient allocations in this environment. Theorem 14 Let S and C be the sets of students and colleges respectively, and let Q be the school's capacities vector. Then for each Scoring Function GS that satises LFC, and any SAP = {S, C; Φ, Π, Q}, where priorities are induced by GS , there exists a unique stable and Pareto ecient matching. 10  Note that Theorem 14 establishes that LFC is a sucient condition to guar- antee the existence of matchings conciliating the notions of stability and Pareto eciency. Let us remark that the usual way to prioritize students comes from the employ of some scoring rule. These functions are usually expressed as the addition of two scoring functions. The rst one just takes into account the particular characteristics of the students, isolated from the schools, whereas the second one lies on each student's characteristics related to the considered school. This additively separable functional form follows the shape used in Denition 13. We would like to point out that it is very hard to nd a result establishing necessary conditions conciliating stability and Pareto eciency. In particular, if each student is free to rank any school as her best school, it is always possi- ble to nd non-scarce problems having a stable and Pareto ecient matching. Just, consider that students rankings are such that, for each school cj the num- ber of students for which this school is the rst-ranked, i.e. ρsi cj = 1, is not greater than qcj . In such a case, no matter which the matrix Π is, the matching that associates each student her best school is both stable and Pareto ecient. Therefore, if conditions are established on individual characteristics, it is very hard to have in mind natural necessary conditions guaranteeing the existence of a stable and Pareto ecient matching. 4 Concluding Remarks Let us start this section by quoting the paper by Abdulkadiro§lu et al. (2005). Recent Developments Section. A memorandum from Superintendent Payzant in December 2004 states that BPS plans to change the computerized process used to assign students to schools. Although the task-force report recom- mended that BPS adopt the TTC assignment algorithm, the School Committee is interested in simulations of both mechanisms and in understanding the extent of preference manipulation under the Boston mechanism. They are also thinking through their philosoph- ical position on the trade-o between stability and eciency. This interest for dening a philosophical approach on the trade-o between stability and eciency is at the origin of a modication in the mechanism used in the Boston Area, decided by July 2005, see Abdulkadiro§lu et al. (2006). As these authors mention, the solution was to adopt a deferred acceptance mechanism because it is strategy-proof. Nevertheless, as we have pointed out in the present paper, this solution is far from solving the trade-o which is at the origin of this reform. In fact the employ of such a solution can be justied because it considers that stability is the central issue. If, moreover, the best that agents can do is to reveal their true characteristics, it is straightforward to conclude, as the Boston School Committee did, that the Student-Optimal Stable mechanism would be adopted. 11  The main conclusion of this paper is to provide a ways to avoid the eciency- equity dilemma. It allows to slightly modify the last reform introduced by the Boston School Committee, comes from redening how the schools inuence on designing which students are prioritized. In this sense, the solution comes from the use of scoring rules that, applied to the students' characteristics, fulll our Limited Freedom Condition. Appendix I. Proof for Propositions 5 and 8. To prove Propositions 5 and 8, let us start by establishing some claims that will be helpful to understand the structure of stable and ecient matchings. Claim 15 Let SAP be a School Allocation Problem. Then it has, at most, one stable and ecient matching. Proof. First of all, and following Martínez et al. (2001), let us note the set of stable matchings has a lattice structure. The operators proposed by Martínez et al. (2001) to prove such a structure are just the students' rankings and the schools' priorities. Therefore, if a stable matching µ is ecient for SAP , it must be the student optimal stable matching. Claim 16 Let SAP be a School Allocation Problem, and µ be a stable matching for it. Then µ is ecient if, and only if, there is no (non-empty) ordered set of students s1 , . . . , si , . . . , sk ⊆ S , such that  for all si ∈ S , and
(a) µ si ∈ C (b)each student si ranks her mate as worse than her next-in-the-order stu- dent's mate, ρsi µ(si+1 ) < ρsi µ(si ) for each i < k, and ρsk µ(s1 ) < ρsk µ(sk ) . Proof. First of all, let us note that if there exists a set of students fullling the statement of Claim 16, it is easy to see that the matching is not ecient. To see that,given a matching µ, let us construct µ0 such that µ0 (si ) = µ
(si ) for each / s1 , . . . , si , . . . , sk and for any student si in such a set, µ0 si = µ si+1 ,
si ∈ modulo k . Note that µ0 Pareto dominates µ. On the other hand, let us assume that µ is a stable matching that fails to be ecient. Then, there should be another matching µ0 that dominates µ. This is equivalent to say that µ0 6= µ and, for each student si such that
µ0 (si ) 6= µ (si ), ρsi µ0 (si ) < ρsi µ(si ) . Let s1 be a student such that µ0 s1 6= µ s1 . Note that, by the Decomposition Lemma,10
10 See, for instance Gale and Sotomayor (1985). Note that Martínez et al. (2000) pointed out that this results is still valid in our framework. 12  and provided that µ is stable, it must be the case that µ s1 6= s1 . Let denote
µ s1
= c ∈ C . Since µ is stable, and ρs1 c1 < ρs1 µ(s1 ) , it must be the
case that 0 1
1 µ c  = qc1 . Therefore, there should be a student, say s2 ∈ µ c1 \ µ0 c1 .
Since µ0 Pareto dominates
µ,2 and µ s 6= µ s 1
, there2 should be an school, 2
2
say c such that µ s = c . Note that if µ s = 2 0 2
c 0 the2
result is proved. Otherwise, there should be a student, say s3 ∈ µ c2 \ µ c . Let us observe that if µ c = µ c , the result follows. Otherwise, since the set of students 0 3
1
is nite, an iterative argument yields the desired result. We can now proceed to prove Propositions 5 and 8. Proof of Proposition 5. Let SAP be a School Allocation Problem. Let us assume that Π satises CPC. By Claim 15 we now that, if there is a stable and Pareto ecient matching, it must be µSO , the student optimal stable matching. Since µSO is stable, let us assume that it is not ecient. Then, by Claim 16, there must be a matching µ0 , and an ordered set of students, say s , . . . , s , . . . , s = S 0 , such that for each si ∈ S 0 , ρsi µ0 (si ) <  1 i k ρsi µSO (si ) , with µ0 si = µSO si+1 for each i ≤ k − 1, and µ0 sk = µSO s1 .



Since µS is stable, we have that, for each student si ∈ S 0 , (a) πµSO (si+1 )si > qµSO (si+1 ) ; and (b) πµSO (si+1 )si > πµSO (si+1 )si+1 . where sk+1 = s1 . By CPC, there must be a priorities order π such that, for each school cj ∈ C , and any two students si , sh such that min πcj si , πcj sh > qcj , it holds that   πcj si < πcj sh ⇔ [πsi < πsh ] . Therefore, by CPC and stability of µ, we have that πs1 < · · · < πsi < πsi+1 < · · · < πsk < πs1 , which contradicts that π might represent a priorities order. Proof of Proposition 8. Let SAP be a School Allocation Problem. Let us assume that Φ satises CRC, relative to ρ, which is the ranking that all the students exhibit. Note that, in such a case it is straightforward to see that there is a unique stable matching, which is also Pareto ecient. This matching can be obtained in a simple sequential way. If we denote by ct ∈ C the t-th college according ρ, we proceed as follows: (1) µS c1 = {si ∈ S : πc1 si ≤ qc1 };
13 (2) µS c2 is the set containing the qc2 prioritized students, according to πc2 ,
that are not in µS c1 ; . . .
(t) µS (ct ) is the set containing the qct prioritized students, according to πct , that are not in µS ch for any h < t.
It is easy to see that this assortative matching is both stable and ecient. II. Proof for Theorem 14. To prove Theorem 14, let us consider a School Allocation Problem. Let us assume that there is a `scoring function' GS : S × C → < inducing the priorities matrix Π. Note that this is equivalent to say that for each cj ∈ C , and any two students si and sh in S , πcj si < πcj sh whenever GS (si , cj ) > GS (sh , cj ). Let us assume that GS satises LFC. Then there are three functions LS : S → <+ , P : C → 2S , and CS : S × C → <+ decomposing GS as established in Denition 13. For function LS given, let us dene the `common priority' π as πsi = |{sh ∈ S : LS (sh ) ≥ LS (si )}| . Then, since GS satises LFC, and, for each cj ∈ C , πcj is induced by LFC, it follows that Π satises CPC related to π . Thus, as Proposition 5 establishes, SAP has a unique stable and ecient matching. References Strategy-proofness [1] A. Abdulkadiro§lu, P.A. Pathak and A.E. Roth (2009). versus Eciency in Matching with Indierences: Redesigning the NYC High School Match. American Economic Review, Papers and Proceedings, 99, 19541958. [2] A. Abdulkadiro§lu, P.A. Pathak, A.E. Roth and T. Sönmez (2005). The Boston Public School Match. American Economic Review, Papers and Pro- ceedings, 95, 368371. [3] A. Abdulkadiro§lu, P.A. Pathak, A.E. Roth and T. Sönmez (2006). Chang- ing the Boston School Choice Mechanism: Strategy-proofness as Equal Ac- cess , mimeographed. Harvard University. [4] J. Alcalde (1996). Implementation of Stable Solutions to Marriage Markets. Journal of Economic Theory, 69, 240254. [5] J. Alcalde and S. Barberà (1994). Top Dominance and the Possibility of Strategy-Proof Stable Solutions to Matching Markets. Economic Theory, 4, 417435. 14  [6] J. Alcalde and A. Romero-Medina (2010). Re-Reforming the Bostonian System: A Novel Approach to the Schooling Problem. Mimeo. Available at SSRN: http://ssrn.com/ [7] M. Balinski and T. Sönmez (1999). A Tale of Two Mechanisms: Student Placement. Journal of Economic Theory, 84, 7394. [8] L. Ehlers and A. Erdil (2010). Ecient assignment respecting priorities. Journal of Economic Theory, 145, 12691282. [9] A. Erdil and H. Ergin (2008). What's the Matter with Tie-Breaking? Im- proving Eciency in School Choice. American Economic Review, 98:3 , 669689. [10] Ergin H., Ecient resource allocation on the basis of priorities. Economet- rica 70 (2002), 24892497. [11] D. Gale and M. Sotomayor (1985). Some Remarks on the Stable Matching Problem. Discrete Applied Mathematics, 11, 223232. [12] D. Gale and L. Shapley (1962). College Admissions and the Stability of Marriage. American Mathematical Monthly, 69, 915. [13] G. Haeringer and F. Klijn (2009). Constrained School Choice. Journal of Economic Theory, 144, 19211947. [14] Kesten (2010). School choice with consent, Quarterly Journal of Economics, 125 (3): 12971348. [15] R. Martínez, J. Massó, A. Neme and J. Oviedo (2000). Single Agents and the Set of Many-to-One Stable Matchings. Journal of Economic Theory, 91, 91105. [16] R. Martínez, J. Massó, A. Neme and J. Oviedo (2001). On the Lattice Struc- ture of the Set of Stable Matchings for a Many-to-One Model. Optimization, 50, 439457. [17] T. Sönmez and M.U. Ünver (2009). Matching, Allocation, and Exchange of Discrete Resources, Jess Benhabib, Alberto Bisin, and Matthew Jackson (eds.) Handbook of Social Economics, Elsevier, forthcoming. 15