Improving matching under hard distributional constraints

Fragiadakis, Daniel; Troyan, Peter Article Improving matching under hard distributional constraints Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Fragiadakis, Daniel; Troyan, Peter (2017) : Improving matching under hard distributional constraints, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 12, Iss. 2, pp. 863-908, https://doi.org/10.3982/TE2195 This Version is available at: https://hdl.handle.net/10419/197206 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/3.0/ Theoretical Economics 12 (2017), 863–908 1555-7561/20170863 Improving matching under hard distributional constraints Daniel Fragiadakis Department of Economics, Texas A&M University Peter Troyan Department of Economics, University of Virginia Distributional constraints are important in many market design settings. Prominent examples include the minimum manning requirements at each Army branch in military cadet matching and diversity considerations in school choice, whereby school districts impose constraints on the demographic distribution of students at each school. Standard assignment mechanisms implemented in practice are unable to accommodate these constraints. This leads policymakers to resort to ad hoc solutions that eliminate blocks of seats ex ante (before agents submit their preferences) to ensure that all constraints are satisfied ex post (after the mechanism is run). We show that these current solutions ignore important information contained in the submitted preferences, resulting in avoidable inefficiency. We then introduce new dynamic quotas mechanisms that result in Pareto superior allocations while at the same time respecting all distributional constraints and satisfying important fairness and incentive properties. We expect the use of our mechanisms to improve the performance of matching markets with distributional constraints in the field. Keywords. Minimum quotas, floors, ceilings, affirmative action, school choice, diversity, strategyproofness, deferred acceptance. JEL classification. C78, D61, D63, I20. 1. Introduction The theory of matching has been extensively developed and applied to solve a wide array of practical allocation problems in recent years. Important formal settings include Daniel Fragiadakis: [email protected] Peter Troyan: [email protected] We are extremely grateful to Fuhito Kojima, Muriel Niederle, and Al Roth for numerous conversations regarding this project. We would like to thank Brian Baisa, Scott Baker, Andrey Fradkin, Guillaume Haeringer, Matt Jackson, Scott Kominers, Vikram Manjunath, Paul Milgrom, Krishna Rao, Itay Saporta-Eksten, Ilya Segal, Rodrigo Velez, Pablo Villanueva, Alex Westkamp, Alex Wolitzky, and Edison Yu for helpful comments and suggestions, as well as seminar participants at Virginia, Iowa, Cal State East Bay, Texas A&M, Western Ontario, and Illinois. We also thank a co-editor and an anonymous referee for helpful comments that improved both the results and the exposition of the paper. Generous support from the B. F. Haley and E. S. Shaw Fellowship (Troyan) and the Leonard W. Ely and Shirley R. Ely Fellowship (Fragiadakis), both through the Stanford Institute for Economic Policy Research, is gratefully acknowledged. This paper was originally circulated under the title “Market design under distributional constraints: Diversity in school choice and other applications.” Copyright ©2017 The Authors. Theoretical Economics. The Econometric Society. Licensed under the Creative Commons Attribution-NonCommercial License 3.0. Available at http://econtheory.org. DOI: 10.3982/TE2195 864 Fragiadakis and Troyan Theoretical Economics 12 (2017) matching doctors to hospitals, elementary and high school students to school seats, and military cadets to Army branches; less formally, similar problems arise in many other areas, such as assigning groups of students to projects in a class or groups of employees to tasks in a firm. As the scope of applications has expanded, designers have increasingly encountered various types of practical constraints that were not present in the early analysis. In this paper, we study an important class of these constraints and show that an intuitive and common way in which they are handled results in avoidable inefficiencies. In addition, we propose new mechanisms, and show that they Pareto dominate current ad hoc approaches without compromising key fairness or incentive properties. The constraints we consider are called distributional constraints, because they relate to the distribution of the final assignments of the agents across objects, projects, or institutions. As an example, consider medical residency matching, in which hospitals in rural areas commonly suffer doctor shortages relative to their urban counterparts.1 Many governments are concerned about access to health care in rural communities, and try to implement policies to balance the distribution of doctors between urban and rural areas. One policy instituted by the Japanese government is to reduce the capacities of the urban hospitals to ensure that more doctors are assigned to rural hospitals. To produce the final assignment, they then run the very popular deferred acceptance mechanism (which is widely used in many medical residency markets, including in the United States) under these lower (“artificial”) capacities, a mechanism we call artificial caps deferred acceptance (ACDA).2 As a second example of distributional constraints, consider the United States Military Academy (USMA), which every year must assign newly graduated cadets to positions in Army branches (for example, aviation or infantry). An October 1, 2007 memorandum from the Army Deputy Chief of Staff to the USMA titled “Branch Allocation Methodology” describes the following three phase procedure: first, minimum and maximum quotas for the number of cadets who must be assigned to each branch—or, “floors” and “ceilings,” respectively—are calculated based on the Army’s current staffing needs; second, artificial caps are calculated such that any final assignment that obeys these caps necessarily satisfies all of the true ceilings and floors as well; and third, the matching algorithm is run under the artificial (rather than the true) capacities.3The memo states that the assignment is done in three phases because “there is no ex-ante 1For example, Talbott (2007) notes that the United States as a whole has 280 doctors per 100,000 people, but the 18-county Mississippi delta area has only 103 doctors per 100,000 people. Similar doctor shortages in rural areas are present in many countries (e.g., Nambiar and Bavas 2010 document such shortages in Australia). 2More precisely, the Japanese government imposes regional maximum quotas that guarantees that no more than a certain number of doctors are assigned to each region of the country. In practice, however, this is implemented by simply reducing the individual capacities of the hospitals by some fixed percentage that guarantees that, when aggregated, the regional quotas will not be violated. See Kamada and Kojima (2015) for more details on this market. 3Sönmez and Switzer (2013) proposes new algorithms for the third (final) phase of the branching procedure, but does not consider the problem of how the capacities themselves are determined (second phase). Theoretical Economics 12 (2017) Improving matching under constraints 865 closed form algorithm that optimizes program participation subject to manning requirements” (emphasis added). Providing such algorithms and studying their properties are precisely the goals of this paper.4 A final well known example of distributional constraints arises in school choice mechanisms, which many cities have recently adopted to give parents more choice over schools (examples include New York, Boston, Chicago, and Denver). An additional consideration for many school districts when implementing school choice plans is achieving (demographic) diversity, which can be thought of as distributional constraints on the demographic distributions of the students at the schools. Usually, this is done using socioeconomic status (SES) or some proxy for it. For example, Chicago classifies students into four SES tiers and requires that all selective high schools enroll enough students from each tier.5To take another concrete example, consider Cambridge, MA, which divides students into high and low SES. They then require that the percentage of students at each school from each class must lie within a certain range; in other words, there is both a floor and a ceiling for the number of students of each type at each school.6 Louisville, KY and White Plains, NY have very similar controlled choice plans.7 The common theme that ties all of these applications together is the presence of floors, i.e., a minimum number of agents who must be assigned to each institution. (In many cases, there are actually multiple floors at each institution, such as floors for each socioeconomic class in school choice.) While the literature thus far has been extremely successful at developing mechanisms that work very well in the field for markets with ceiling constraints, most of these existing mechanisms are inadequate for the many institutions that also have floor constraints. For instance, the original school choice mechanisms found in the seminal paper of Abdulkadiro˘ glu and Sönmez (2003) would allow a school to have (for example) a total capacity of 100 seats in addition to ceiling constraints of at most 50 high SES students and at most 50 low SES students. Note, however, that an assignment of 50 high SES students would satisfy these constraints, yet would be completely segregated, and thus would not satisfy the true diversity objectives of many school districts. 4Military branching can also be thought of as a special case of a firm (the Army) that must assign employees to projects (the branches), with each project having a minimum staffing requirement. For example, some technology firms in Silicon Valley use centralized mechanisms to assign new interns to positions. In a similar vein, for many new medical residents, the first year after medical school is a transitional year in which they rotate through various departments of a hospital. While the hospitals try to accommodate preferences as much as possible, each department has a minimum staffing requirement. All of these problems can also be modeled as a matching problem with floor constraints, and our mechanisms can be applied. 5See the website of the Chicago Public Schools Office of Access and Enrollment at http://www.cpsoae. org/apps/news/show_news.jsp?REC_ID=184188. 6Each school is required to be within 10% of the districtwide average for each SES class, which translates into ranges of approximately 25–45% for low SES students and 55–75% for high SES students (these numbers may vary slightly from year to year). See “Case studies of school choice and open enrollment in four cities” (Cowen Institute for Public Education Initiatives 2011). 7Achieving socioeconomic diversity in schools is also an issue in many European countries. For example, Sweden implements a school choice procedure, but is considering “restricting the ability of some parents to choose their children’s schools by introducing ‘controlled choice schemes that supplement parental choice to ensure a more diverse distribution of students in schools’” (Orange 2015). See http:// www.matching-in-practice.eu for more examples. 866 Fragiadakis and Troyan Theoretical Economics 12 (2017) Suppose the school in the above example also imposed floors of 25 high and 25 low SES students (in addition to the ceilings of 50). This ensures a minimum level of diversity at the school. One convenient way the district can ensure that these floors are met is to (i) lower the ceilings at other schools and then (ii) run an “off-the-shelf” mechanism designed to handle only ceiling constraints. As mentioned above, we call this approach artificial caps (and when the off-the-shelf mechanism is the deferred acceptance (DA) mechanism of Gale and Shapley (1962), we obtain the artificial caps deferred acceptance (ACDA) mechanism). It works by the simple intuitive principle that restricting someone from one school results in their being assigned to another. Artificial caps is in fact a commonly used approach, likely because it is so intuitive. As described above, this is precisely how the Japan Residency Matching Program (JRMP) guarantees enough doctors are assigned to rural hospitals, and how the USMA ensures enough cadets are assigned to each Army branch.8They first eliminate sufficiently many positions ex ante (i.e., before preferences are submitted) to guarantee that all of desired floors are satisfied ex post (i.e., when the final matching is reached). In this paper, we first show that imposing artificial caps results in avoidable inefficiency. The reason is that, to satisfy all of the constraints, ACDA must eliminate positions aggressively. To understand why, note that in a given matching problem, only one set of preferences, P, is submitted. It may be the case that the ceilings required for DA to satisfy all floors under Pare not as low as those that were imposed by ACDA (which must be low enough to ensure that the floors are met ex post for any possible preferences that could have been submitted). This is problematic, since eliminating a seat at a school makes every student weakly worse off. Accordingly, we introduce the idea of a dynamic quotas (DQ) mechanism, where dynamic quotas deferred acceptance (DQDA) runs as follows: Start with the original ceilings and run DA. If the matching is feasible (i.e., meets all floors), end the algorithm. Otherwise, lower the ceiling at one school by 1. This causes a rejection chain, where that school rejects a student, who then applies to her next most preferred school, which then (may) reject a student, and so forth, until a student applies to a school with an open seat. When this rejection chain ends, if the matching is feasible, end the algorithm; if not, lower the ceiling of another school by 1, and so forth. We show that if we choose the order in which ceilings are lowered carefully, DQDA (i) always produces a matching that satisfies all distributional constraints and (ii) Pareto dominates artificial caps DA. By construction, the final ceilings implemented depend on the submitted preferences. This is precisely how we obtain the efficiency gain over ACDA: by using information contained in the submitted preferences to determine the final ceilings, we are 8The case of the Japan Residency Matching Program is slightly subtle because, while they do not have explicit floors, it seems clear that the end goal of the artificial capacities they impose is not to limit the number of doctors in urban areas per se; instead, artificial caps are likely used as a simple, ad hoc way to increase the number of doctors in rural areas. Kamada and Kojima (2015) provide improvements to the current JRMP mechanism if the regional maximum quotas are taken at face value as the true objective, but their mechanisms cannot handle floors explicitly. If the true objectives are actually as-to-now implicit floor constraints, then we argue it would be an improvement to model these constraints explicitly and use the mechanisms provided in this paper. Doing so satisfies the actual distributional goals (the true floors and ceilings), and, as we show, makes all doctors better off, compared to the current approach of imposing regional caps and hoping that the resulting distribution of doctors turns out to be satisfactory. Theoretical Economics 12 (2017) Improving matching under constraints 867 able to eliminate fewer seats at each school than artificial caps. A concern that arises from this modification is that individuals now have the ability to change the ceilings by submitting different preferences. This poses a potential incentive problem: perhaps an individual can do better by misreporting her preferences than by stating them truthfully, i.e., the mechanism may not be strategyproof. Non-strategyproof mechanisms are often unattractive because they allow some agents to “game the system” and profit at the expense of less sophisticated players (this is especially true in school choice, where school districts are often worried that some parents may not fully understand the mechanism and will be harmed by not strategizing appropriately).9Thus, before implementing a dynamic quotas mechanism, it is crucial to fully understand its incentive properties. While it may seem that allowing the final ceilings to depend on the preferences introduces obvious avenues for manipulation, one of our main results is to show that this is not the case. Indeed, we show that if the algorithm is constructed carefully, DQDA is in fact strategyproof. A final key concern is how to determine who is assigned where when demand exceeds supply. In school choice, many school districts create priority lists for each school, giving students higher priority for neighborhood schools, sibling attendance, languages spoken, or various other factors. The districts then wish to respect priorities in the following sense: if student iis assigned to school Abut prefers the assignment of a student j(e.g., school B) who is of the same socioeconomic status, then jmust have a higher priority at school Bthan i.Thus,i’s envy toward jis not justified. Eliminating such justified envy concerns is often an important fairness consideration in other settings as well. For example, in the military, cadets are ranked according to an Order of Merit list, which combines academic, physical fitness, and leadership scores (among others). To give good incentives for the cadets to achieve high scores, the Army desires that higher ranking cadets be assigned their more preferred branches, i.e., they also want to eliminate justified envy. We show that DQDA does indeed satisfy this property. We would also like to note that the paper makes not only a practical contribution, but a theoretical one as well. While the incredibly influential paper of Gale and Shapley (1962) first introduced the now very popular deferred acceptance (DA) mechanism, it did not study the mechanism’s incentive properties. It has since come to be widely accepted that good incentive properties are integral to success, not only in matching, but in a broad array of economic contexts. With regard to DA, Dubins and Freedman (1981) and Roth (1982) were the first to prove that it is strategyproof for the proposing side in simple one-to-one matching models. As the potential applications of DA have rapidly grown, an active topic of research in the literature has been trying to understand the most general settings that are compatible with strategyproofness (Martínez et al. 2000, Abdulkadiro˘ glu 2005,Hatfield and Milgrom 2005,Hatfield and Kominers 2011,2012, Hatfield and Kojima 2010). The presence of the floors makes our model quite different from these papers in a technical sense. In particular, they often rely on the existence of 9Non-strategyproof mechanisms also make it much more difficult for participants to reach equilibrium in practice, and so it is unclear whether real-world outcomes will conform to theoretical predictions of such mechanisms. Additionally, the need to strategize creates additional costs to participants from participating in the mechanism that are not present if it is in their best interest to simply report their true preferences. 868 Fragiadakis and Troyan Theoretical Economics 12 (2017) student-optimal stable matchings, a condition that fails in our setting. In addition, all of the previous papers assume that the choice functions of the receiving side are fixed throughout the algorithm. We are the first to show that dynamically adapting choice functions are compatible with strategyproofness.10 In the Appendix,westudygeneral sufficient conditions on the evolution of the choice functions that guarantee good properties of DA. Interestingly, our conditions are related to the key substitutability conditions in the model of Hatfield and Milgrom (2005) (see also Kelso and Crawford 1982 and Roth and Sotomayor 1990). Both guarantee monotonicity of the corresponding cumulative offer process, which is crucial in proving our main results. Besides being useful in practice, these results deepen our understanding of the enormously successful deferred acceptance mechanism. Related literature Early papers that discussed distributional constraints in matching focused on the rural hospital problem and obtained mostly negative results. Papers such as Gale and Sotomayor (1985a,1985b), Roth (1984,1986), Martínez et al. (2000), and Hatfield and Milgrom (2005) prove various versions of the “rural hospital theorem,” which says that if a doctor or a position at a hospital is unmatched at some stable matching, then they are unmatched at any stable matching.11 This suggests that the rural hospital problem is difficult to solve without imposing any additional structure on the market, which is what led the Japan Residency Matching Program (JRMP) to impose regional caps on the number of doctors in urban areas, an issue studied in detail by Kamada and Kojima (2015). Since it is an important goal of many school districts, diversity constraints have been much discussed in the school choice literature. Much of the work thus far has dealt with upper quotas/ceilings. In their seminal paper on school choice from a mechanism design perspective, Abdulkadiro˘ glu and Sönmez (2003) show how type-specific ceilings can be easily incorporated into standard matching mechanisms. Ceiling constraints do not fully capture diversity constraints, however, since they can still result in completely segregated schools. In addition, in a model with two types of students (majority and minority), Kojima (2012) points out that simple ceiling constraints can actually make all minority students (the supposed beneficiaries) worse off. Hafalir et al. (2013)correct this by proposing deferred acceptance with minority reserves, a mechanism further generalized by Kominers and Sönmez (2016), who introduce slot-specific priorities. 10Our use of the word “dynamic” should not be confused with the strand of literature on “dynamic matching markets” that introduces a time dimension and allows agents to enter/exit the market and matches to change each period (as in Kennes et al. 2014a,2014b,Kadam and Kotowski 2014, and Akbarpour et al. 2016). In our model, agents play a static game where they submit their preferences once, at the start of the game, and take no further action. Once lists are submitted, the quotas/choice functions of one side of the market may change as the algorithm progresses, hence operating in a possibly dynamic manner, but ultimately, a single final match is produced. 11Afacan (2013) studies whether hospitals can manipulate their preferences to change the number of positions filled. Sönmez (1997) studies the complementary question of whether hospitals can manipulate their capacities to obtain a more preferred assignment of doctors. Theoretical Economics 12 (2017) Improving matching under constraints 869 Do˘ gan (2016) notes that in the mechanism of Hafalir et al. (2013), stronger affirmative action constraints may actually harm some minority students without helping others, and proposes a modification to rectify this. Abdulkadiro˘ glu (2005), Erdil and Kumano (2013), Aygün and Bó (2016), and Echenique and Yenmez (2015) study various generalizations of school priorities over sets of students and how they can capture certain types of diversity goals.12 The main difference between our model and the aforementioned works is that we treat the ceilings and floors as hard constraints, i.e., constraints that must be satisfied at any feasible matching. Most prior papers interpret floors as soft constraints; that is, the constraints are more like “guidelines,” and they may end up being violated at the final assignment. Working with hard constraints complicates the problem considerably, and leads to the incompatibility of several important properties (non-wastefulness, elimination of justified envy and strategyproofness) that could be achieved simultaneously in prior models. Recently, there is a growing literature that has begun to deal with hard floor constraints.13 Ehlers et al. (2014) start by looking at a school choice model with hard floors and ceilings similar to that studied here. After noting the above impossibility results, they advocate for a “soft” interpretation of the constraints where the floors and ceilings can be violated, and provide new mechanisms in this context.14 While such a soft bounds approach may be acceptable in certain settings, there are many situations in which it is inadequate, such as medical markets suffering from the rural hospital problem, school districts with court-mandated desegregation guidelines, or the military, where minimum manning requirements must be filled. Our paper provides a strategyproof mechanism that ensures that all floors are filled, and so can be used in these settings. Fragiadakis et al. (2015) also study a model with hard floor constraints. The model here is more general, as the model in Fragiadakis et al. (2015) is restricted to the case of aggregate floor constraints; for example, they would not allow a school to have separate floors for different types of students. We must construct different solutions in this paper so as to handle multiple types (diversity constraints), and the arguments become more complex. In addition, we show that our mechanisms Pareto dominate mechanisms that are used in practice. In a more recent paper, Kojima et al. (2014)analyze certain classes of distributional constraints using the tools of discrete convex analysis. While they are able to encompass many types of constraints (including the simpler mechanisms of Fragiadakis et al. 2015), they note that they are unable to accommodate the constraints we consider, because of the complexities introduced by type-specific floors and ceilings. Allowing for more general constraint structures that accommodate such goals introduces substantial complications in constructing appropriate mechanisms and in proving important incentive and efficiency results. Given the importance 12See also Westkamp (2013), who proposes similar mechanisms in the context of German university admissions, and Braun et al. (2014), who conduct an experimental analysis of these mechanisms. 13In the context of object allocation, Budish et al. (2013) study what types of constraints admit expected assignments that can be implemented as lotteries over deterministic assignments. 14They also provide an algorithm for the hard constraints case but, unlike ours, their mechanism is not strategyproof. 870 Fragiadakis and Troyan Theoretical Economics 12 (2017) of these types of constraints in real-world markets, we view this as one of the key contributions of the current paper. Finally, the problem of distributional constraints has also garnered interest from computer scientists. For example, Biró et al. (2010) study college admissions in Hungary, in which colleges are allowed to declare minimum quotas for their programs, and Hamada et al. (2011) study hospital–resident matching with lower bounds. Both papers focus mainly on computational hardness results: the former shows that the problem of determining the existence of a stable matching is NP-complete, while the latter shows that the same is true of finding a matching that minimizes the number of blocking pairs. These papers provide another perspective which says that introducing floors into matching markets complicates the problem substantially. 2. Model There is a set of agents I={i1in}and a set of objects to which they can be assigned, S={s1sm}, each of which has total capacity Qs. The finite set of types for agents is ={θ1θr}, and each agent is of exactly one type. The function τ:I→gives the type of each agent, and Iθis the set of agents of type θ. Types are fixed and are publicly observable (i.e., types cannot be misreported). In addition to a capacity Qs, each s∈S has a type-specific floor Lsθ (or lower quota) and a type-specific ceiling Usθ (or upper quota) for the number of agents of each type θwho can be assigned to it. We assume 0≤Lsθ ≤Usθ ≤Qsfor all (s θ).LetQ=(Qs)s∈Sbe the vector of all capacities and let L=(Lsθ)s∈Sθ∈and U=(Usθ)s∈Sθ∈be the matrices of all type-specific floors and ceilings, respectively. One application of the model is that Iis a set of students and Sis a set of schools. Then can be interpreted as a set of socioeconomic classes corresponding to the diversity constraints of the school district.15 Other potential applications include the military assigning cadets to branches, residency programs assigning doctors to hospitals (as in Japan), firms assigning workers to tasks, or business schools assigning students to projects.16 For concreteness, from here on we mostly stick to the language of students 15School districts sometimes state diversity constraints in terms of percentages (rather than absolute numbers) because they are simpler to communicate, but these percentages are usually converted into absolute numbers of seats when actually running the algorithm. This is done in Cambridge, for example (see http://www3.cpsd.us/video/controlled_choice_video for a video describing the implementation of the Cambridge algorithm, targeted toward parents). From a technical perspective, the use of percentages introduces complementarities, which leads to many impossibility results (see Echenique and Yenmez 2015), and percentages likely do not truly capture a school district’s goals, since they also want the total population of a school to lie in some range (for example, a school with one high SES student and one low SES student would be “unsegregated,” but having so few students in a school would not be cost effective from the school district’s perspective). For these reasons, most formal models use absolute numbers (e.g., Ehlers et al. 2014 and Hafalir et al. 2013). When there is only a single type (e.g., in military cadet matching), this distinction is immaterial. 16In fact, the true prevalence of these types of distributional constraints in the real world is likely to be underestimated. This is because artificial caps may be set internally in such a way that they are unobserved to outsiders. That is, before running an algorithm, capacities may be set so as to implicitly satisfy some floors (as in the JRMP in Japan), but to an outside analyst, it would appear as if the artificial caps were Theoretical Economics 12 (2017) Improving matching under constraints 877 Definition 2. A reduction sequence is minimal if the following statements hold for all k: (i) For one (s θ),Uk+1 sθ =Uk sθ −1and Qk+1 s=Qk s−1. (ii) For all (sθ)= (sθ),Uk+1 sθ=Uk sθ. (iii) For all s = s,Qk+1 s =Qk s . In words, a reduction sequence is simply a monotonically decreasing sequence of ceiling–capacity pairs. Minimality means that in moving from stage kto k+1, we choose a school-type pair (sθ) and lower the type-θceiling at sand the capacity of sby exactly one seat; the ceilings and capacities of the remaining schools are unchanged. To avoid trivialities, we assume that for any feasibility-ensuring artificial caps (UKQK),sucha nondegenerate reduction sequence exists.24 Dynamic quotas deferred acceptance Let η={(U1Q1) (U2Q2)(UKQK)}be a reduction sequence. Stage 1. Compute the outcome of standard DA (as defined in Section 2)under (U1Q1). If the resulting matching is feasible, end the algorithm and output this matching. If not, proceed to stage 2. Stage kfor k≥2. k.0. Lower the ceilings and capacities to (UkQk). Divide each school sinto Lsθ type-specific seats for each type θand Qk s−θLsθ open seats that can be assigned to any type. k1. Beginning with an applicant pool equal to the set of students held at the end of stage k−1, school stentatively fills the type-specific seats for each type θwith the Lsθ highest ranked type θstudents according to s. If there are students remaining in the applicant pool, school s tentatively admits students one by one from the top of its priority order to the open seats, unless either some stage ktype-specific ceiling Uk sθ would be violated or Qk s−θLsθ open seats have already been filled. All students not accepted are rejected. 24We say a reduction sequence is degenerate if for all k<Kand all PI,DA(UkQk)(PI)is feasible only if DA(UkQk)(PI)=DA(UKQK)(PI). For an example of a market with only degenerate reduction sequences, consider the special case where the sum of the floor constraints is exactly equal to the total number of students. When this is true, the ceiling constraints are effectively irrelevant because the floors alone exactly pin down the distribution of students across schools. Because there is no flexibility in the final distribution, the problem is trivial. Our model is only interesting when the primitives allow for some flexibility, which is indeed the case in many real-world markets. Examples 1and 2both exhibit markets that admit nondegenerate reduction sequences. 878 Fragiadakis and Troyan Theoretical Economics 12 (2017) kj. Each student who was rejected in stage k(j −1)applies to her most preferred school that has not yet rejected her. Each school sconsiders its new applicants jointly with the students held at the end of stage k(j −1), and tentatively accepts students in the same manner as described in k1. All students not accepted are rejected. Stage kcontinues until the substage kj at which no students are rejected. If the tentative matching at this point is feasible, end the algorithm and output this matching. If not, proceed to stage k+1. The basic idea behind DQDA is to start with high ceilings and capacities, and check whether given the submitted preferences, the output of DA satisfies the floors as well.25 If so, the algorithm ends with the high ceilings. If not, only then do we lower the ceilings. This initiates a rejection chain. The rejected students then apply to their next most preferred school, which rejects its lowest priority students, and so forth, continuing until no further students are rejected. We continue gradually lowering the ceilings until all floors are filled. The key is that the dynamic adjustment process of DQDA only lowers ceilings after taking the submitted preferences of the students into account and stops as soon as all floors are filled, which results in fewer seats being eliminated unnecessarily. Example 2. The following example provides an illustration of the DQDA algorithm. Let S={s1s2s3s4},={ h},andI={1h1h2}. Consider the school quotas/priorities and student preferences given in the following table. All floors are zero except for the type hfloor at s4. Schools Ls Lsh Us Ush Qss s100111h1s1h2s11 s2001111s2h1s2h2 s3001111s3h2s3h1 s401122h1s4h2s41 Students P1:s2s3s1s4 Ph1:s2s1s4s3 Ph2:s3s4s1s2 The last object needed is a reduction sequence. Consider η=⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ ⎛ ⎜ ⎜ ⎜ ⎝ ⎡ ⎢ ⎢ ⎢ ⎣ 11 11 11 12 ⎤ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎣ 1 1 1 2 ⎤ ⎥ ⎥ ⎥ ⎦ ⎞ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎝ ⎡ ⎢ ⎢ ⎢ ⎣ 10 11 11 12 ⎤ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎣ 0 1 1 2 ⎤ ⎥ ⎥ ⎥ ⎦ ⎞ ⎟ ⎟ ⎟ ⎠ ⎛ ⎜ ⎜ ⎜ ⎝ ⎡ ⎢ ⎢ ⎢ ⎣ 10 10 11 12 ⎤ ⎥ ⎥ ⎥ ⎦ ⎡ ⎢ ⎢ ⎢ ⎣ 0 0 1 2 ⎤ ⎥ ⎥ ⎥ ⎦ ⎞ ⎟ ⎟ ⎟ ⎠ ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭  In words, this reduction sequence starts with (U1Q1)=(U Q). At the beginning of stage 2, we lower the capacity and type hceiling at s1by 1, while at the beginning of 25A potential concern of the reader may be that the DQDA algorithm does not produce a feasible assignment and/or may leave some students unmatched. Given our construction of the algorithm and the reduction sequence, this is not an issue. In particular, we choose the reduction sequence such that the final capacities (UKQK)ensure a feasible match (and hence all students are assigned). We show that under minimality, DQDA Pareto dominates DA under (UKQK), and so these properties hold under DQDA as well. Theoretical Economics 12 (2017) Improving matching under constraints 879 stage 3, we lower the capacity and type hceiling at s2by 1. Note that the final entry, (U3Q3), ensures a feasible matching, while (U1Q1)and (U2Q2)do not. The output of stage k=1is μ1=s1s2s3s4 h11h2∅ The type hfloor at s4is not satisfied, and so we must move to stage 2. At the beginning of stage 2, Us1h and Qs1are lowered by 1, and so student h1is rejected from s1, beginning a rejection chain. When this rejection chain ends, the output at the end of stage 2 is μ2=s1s2s3s4 ∅1h2h1 Matching μ2satisfies all of the primitive floors and ceilings, and thus there is no need to move to stage 3. The final output is μ2, which Pareto dominates the matching that would have been implemented by ACDA under artificial caps of (¯ U ¯ Q) =(U3Q3): μACDA =s1s2s3s4 ∅∅1{h1h2} Student h1is indifferent between the two outcomes, but both 1and h2strictly prefer DQDA. ♦ There is an alternative way to define a dynamic quotas algorithm that is very natural. At the end of each stage, rather than leaving everyone at their assigned schools and lowering the ceilings from (Uk−1Qk−1)to (UkQk), we could instead remove all students from their assigned schools and run the entire deferred acceptance algorithm from the beginning under the lower ceilings (UkQk). We call this version of the algorithm sequential deferred acceptance (SDA). Sequential deferred acceptance Recall that DA(UQ)(·)denotes the DA mechanism using ceilings and capacities (UQ). Given a reduction sequence η={(U1Q1)(U2Q2)(UKQK)},thesequential deferred acceptance algorithm is defined as follows. Stage 1. Compute DA(U1Q1)(PI), the outcome of DA under (U1Q1).IfDA(U1Q1)(PI) is a feasible matching, end the algorithm and output this matching. If not, proceed to stage 2. In general, proceed as follows. Stage k. Lower the ceilings and capacities to (UkQk)and compute DA(UkQk)(PI), the outcome of DA under (UkQk).IfDA(UkQk)(PI)is a feasible matching, end the algorithm and output this matching. If not, proceed to stage k+1. 880 Fragiadakis and Troyan Theoretical Economics 12 (2017) While DQDA and SDA are similar, in general they are not equivalent mechanisms. However, there is an important class of reduction sequences where they in fact are equivalent: minimal reduction sequences. Theorem 3. Let ηbe a minimal reduction sequence. For any preferences PI, the matching produced by DQDA under ηis equivalent to that produced by SDA under η. The important implication of Theorem 3 is that the final matching output by DQDA is ex post equivalent to the matching that would have been produced by standard DA under some (fixed) ceilings and capacities (UkQk). This will be helpful in proving our main result below. It is imperative to note, however, that ex ante, it is not known what the final (UkQk)will be, as this will be determined by the submitted preferences. The main result With these preliminary results in hand, we can now state and prove Theorem 4,themain result. Theorem 4. (i) Every ACDA mechanism is Pareto dominated by some DQDA mechanism under a minimal reduction sequence η. Further, for any minimal reduction sequence η, the following statements hold: (ii) DQDA under ηeliminates justified envy among same types. (iii) DQDA under ηis strategyproof. Before discussing the intuition behind the proofs of these results, we first comment on their interpretation. Note that DQDA takes the reduction sequence ηas an input, and different reduction sequences lead to different DQDA mechanisms. DQDA under any minimal η={(U1Q1)(UKQK)}Pareto dominates ACDA under (UKQK),and while DQDA under ηmay not Pareto dominate ACDA under some other (UQ),the important point to note is that, given such a (UQ),thereisanalternative reduction sequence η(= η) that will Pareto dominate ACDA under (UQ).26 Thus, the upshot 26Given two different reduction sequences ηand η,DQDAunderηand DQDA under ηin general are Pareto incomparable, as different students will have different preferences over the order in which quotas are reduced. However, all students will prefer DQDA to the relevant artificial caps. As an analogy, consider the serial dictatorship, a popular mechanism for allocating discrete objects when there are no priorities. The serial dictatorship works by first fixing some ordering of the students, and then allowing the students to pick their favorite schools according to this ordering. The formal definition of the serial dictatorship takes the fixed student ordering as an input, similar to how DQDA takes ηas an input, and different orderings lead to different serial dictatorship mechanisms. Obviously, there will be no Pareto dominance relation between serial dictatorships with different student orderings (each student will prefer the ordering that allows her to choose first), just as there will be no Pareto dominance relation between DQDA mechanisms with different choices for η. However, the importance of this result is that it is always possible to improve on ACDA without compromising fairness or incentives. The key feature needed to retain strategyproofness is that ηbe fixed ex ante, i.e., the submitted student preferences cannot affect the order in which ceilings Theoretical Economics 12 (2017) Improving matching under constraints 881 of the theorem is that any choice of artificial caps (including those that are used in practice by institutions like the JRMP or the military) is inefficient in a strong sense: it is always possible to achieve a Pareto improvement using a dynamic quotas mechanism. The remaining parts of Theorem 4 show that, importantly, these Pareto improvements can be achieved without harming the fairness or incentive properties of the algorithm. Thus, there seems to be little reason for any market using an artificial caps mechanism in practice not to consider switching to a dynamic quotas mechanism instead. Intuition for Theorem 4 Next, we discuss the intuition for Theorem 4 (the full proof is given in Appendix B). First, we note that Theorem 4 is actually a special case of a more general result that we build in Appendix B. Remark 1. While early hospital–resident and school choice matching models assume simple linear preference/priority relations over individual agents on the other side of the market (as we do in the main text here), as the theory has developed, this has been continually expanded to accommodate other types of priority structures that do not take this simple form. At the most general level, one can define abstract choice functions Chs(·)for the schools, where Chs(I)⊆Ireturns the students school sadmits from any potential subset of applicants I(see, for example, Hatfield and Milgrom 2005 or Abdulkadiro˘ glu 2005). It is possible to generalize our model in a similar way and to define a generalized DQDA algorithm where ηis a sequence of choice functions. To ensure the good properties from Theorem 4 hold in general, we must place additional structure on the choice functions. The most important condition is monotonicity,whichsaysthat, fixing the set of applicants at a school, the set of rejected students expands as we move to later stages. This purpose of this condition is analogous to the substitutability condition of Hatfield and Milgrom (2005): both guarantee that as the algorithm progresses, a school never wants to admit a student it has previously rejected. Our condition is different, however, because of the dynamic nature of the choice functions in our generalized algorithm: as the choice functions evolve from stage kto stage k+1, we must ensure that they evolve in such a way that no school ever wants to admit a student it previously rejected in an earlier stage. Minimal reduction sequences are a special case of monotonic choice functions. So as not to obscure the main insight of the paper, we refer interested readers to Appendix A for details. Part (i) For part (i), note that DQDA ends under some ceilings and capacities (UkQk)≥(UKQK). At first glance, it may seem obvious that the final matching produced by DA under higher ceilings and capacities should be preferred by all students to the outcome under lower ceilings and capacities. However, the full argument is more subtle, as lower ceilings for one type of student may actually be beneficial to other types. For example, consider a model with two types, ={ h}, and a school swith priority are reduced. Within these constraints, policymakers may actively choose the ceiling that is to be reduced at each stage so as to achieve some desirable policy goals; alternatively, at each stage kwe can randomly choose some pair (sθ), subject to feasibility constraints (just as the random serial dictatorship randomly chooses a student ordering and implements the serial dictatorship using this ordering). 882 Fragiadakis and Troyan Theoretical Economics 12 (2017) relation sand upper quotas and capacities in stages kand k+1as given by Us Ush Qs k222 k+1212 s:h1h21. Note that the preceding table is not a minimal reduction sequence, because Ush is reduced, while Qsis not. If the set of students who apply to school sunder the stage k quotas is I={h1h21}, the students admitted would be {h1h2}. However, under the stage k+1quotas, the admitted students would be {h11}.Soif1prefers school s(if sis the first choice for all students, for example), then 1will actually be strictly worse off in stage k, under the “higher” capacities. This insight can be embedded into a full market example to show that DQDA does not Pareto dominate DQDA for any arbitrary reduction sequence. The reason this occurs in the above example is because in both stages, school shas a total capacity of 2,butinstagek, both of these seats can go to a type hstudent, while in stage k+1, only one of these seats can go to a type hstudent. The higher ceiling for type hstudents in stage kmakes student 1worse off, because the type hstudents then prevent her from getting a seat at s. Formally, to ensure the Pareto dominance result holds, what is needed is that the set of students chosen from any given set of applicants must be weakly larger (in the set inclusion sense) in earlier stages compared to later stages. This is exactly the monotonicity assumption that was discussed in Remark 1.Thisis not true in the above example; however, the assumption that ηis a minimal reduction sequence guarantees that this holds. Part (ii) Part (ii) is the simplest part of the theorem: it follows from the fact that standard DA with type-specific ceilings eliminates justified envy among same types together with the fact that, ex post, the final matching produced by DQDA is equivalent to standard DA for some (UkQk)(of course, it is not known ex ante what the final stage k will be, which is precisely why we need to run the dynamic quotas algorithm in the first place).27 Part (iii) Parts (i) and (ii) can be shown by analyzing DA within each stage kseparately. Analyzing the incentive properties of DQDA is significantly more complicated, because 27Recall that there is an impossibility result that says that matchings that eliminate justified envy (across types) may not even exist (see Section 3), and so the most we can hope to achieve is elimination of justified envy among same types. If, in addition, we require non-wastefulness, another impossibility result obtains: matchings that simultaneously eliminate justified envy among same types and are non-wasteful may also fail to exist (see Ehlers et al. 2014 and Fragiadakis et al. 2015). Thus, one of these properties must be weakened. Markets that use ACDA are opting to keep elimination of justified envy among same types and weaken non-wastefulness. However, as Theorem 4 shows, ACDA weakens non-wastefulness more than necessary, as DQDA Pareto dominates ACDA while still satisfying elimination of justified envy among same types and strategyproofness. Theoretical Economics 12 (2017) Improving matching under constraints 883 they cannot be understood by looking at each stage independently. The submitted preferences themselves have the potential to alter the final capacities, which may (potentially) give the agents the ability to manipulate their preferences in such a way as to change when the algorithm ends and make themselves better off. To understand the intuition behind why DQDA is strategyproof, it is easiest to restrict to the case of a single type, so that each school has only one aggregate floor constraint and one aggregate capacity constraint. Then fix the preferences of all students other than iat P−i.Letkbe the final stage of DQDA if isubmits her true preferences Pi. The potential manipulations P ithat ican make can be classified into three types: contractions (P icauses DQDA to end at some k<k), extensions (P icauses DQDA to end at some stage k>k), and equivalences (P icauses DQDA to end in stage k=k). The last category is the easiest to rule out as being profitable: if both Piand P icause DQDA to end in stage k, then, since DQDA is equivalent to standard DA in stage k,strategyproofness of DA implies that any such manipulation is not profitable. For extensions, if P icauses DQDA to continue beyond stage k, then there are less seats available for all students. This makes every student worse off (by the same argument used for part (i) above), and so extensions are never profitable. The most difficult types of manipulations to rule out are contractions. Contractions seem to have the most potential for profitability, because just as less seats tend to make students worse off, more seats may have the potential to make students better off. The question, though, is whether the algorithm allows student ito manipulate her preferences to end the algorithm under higher ceilings, and to do so in such a way that makes her better off. The first part is true (it is possible for a student to manipulate to cause the algorithm to end under higher ceilings), but the second is not (due to the way we have constructed the algorithm, any false report she can submit to do so makes her weakly worse off). To understand why, consider a student iwith preferences Pi:s1s2s3.Beginby running DA on all students other than i,28 and assume after this is done that there is only one floor seat left to be filled, at school s2. Now, DQDA ends the next time any student applies to s2. One option available to student iis to lie and list school s2as her true first choice, thereby ending the algorithm immediately (a contraction) with her receiving s2.Ifiinstead submits her true preferences and first applies to s1, she may initiate a chain of rejections that ends with some other student applying to s2,inwhich case ireceives s1, her true first choice. The key observation is that even if iis eventually rejected from s1(e.g., if a seat at s1is eliminated at some point during the running of the algorithm), she then simply applies to s2and the algorithm ends. The seat at s2is always available until someone applies to it, at which point the algorithm ends and all assignments are made permanent. Thus, there is no harm in ireporting her top choices truthfully, because seats at lower ranked schools are always available to her. Note that when there is a single type, monotonicity of the school choice functions (as discussed above) holds trivially, since lowering the capacity at a school automatically eliminates 28The order in which students are allowed to apply is irrelevant, a result first shown by McVitie and Wilson (1971). 884 Fragiadakis and Troyan Theoretical Economics 12 (2017) the seat for all students, since everyone is the same type. More generally, with multiple types, we may run into problems similar to those in the discussion of part (i) above. In the general model in Appendix A, monotonicity of the choice functions is a key property used in the proof of strategyproofness.29 Note that while Theorem 4 shows that DQDA Pareto dominates ACDA, it does not say that DQDA always selects a Pareto efficient matching. This is unsurprising because, even without floors, the DA outcome may not be Pareto efficient due to the fairness (no justified envy) constraints. DA is still widely used, however, because fairness is considered an important property in many markets. Given this, it is natural to ask whether DA and/or our DA-type mechanisms are constrained efficient. We say that a feasible matching μthat eliminates justified envy among same types is constrained efficient if there is no other feasible matching μthat eliminates justified envy among same types and Pareto dominates μ.30 We say a mechanism ψis constrained efficient if it always selects a constrained efficient matching. When there are no floor constraints, DA is strategyproof, eliminates justified envy, andisconstrainedefficient(Gale and Shapley 1962,Abdulkadiro˘ glu and Sönmez 2003). As we have seen, the introduction of floor constraints creates complications that lead to the incompatibility of many of the good properties of DA in the standard model, and this continues here: neither ACDA nor DQDA is a constrained efficient mechanism. This follows from the following impossibility result, shown by Ehlers et al. (2014). Proposition 1(Ehlers et al. 2014). There is no feasible mechanism that is strategyproof, eliminates justified envy among same types, and is constrained efficient.31 Since DQDA is strategyproof and eliminates justified envy among same types, it is not constrained efficient. The impossibility result shows that this is a general problem caused by the presence of floors, and so trade-offs are required between these three desirable properties. Markets that currently make use of ACDA are choosing to prioritize strategyproofness and elimination of justified envy, while weakening efficiency. What we show is that ACDA weakens efficiency more than necessary, and we are the first to provide a new mechanism that is more efficient without compromising important fairness or incentive properties. 29An implicit, yet important, feature of the definition of DQDA is that the reduction sequence ηbe determined exogenously to the submitted preferences, which is key in proving strategyproofness. In the Supplemental Material (available in a supplementary file on the journal website, http://econtheory.org/supp/ 2195/supplement.pdf), we define an alternative endogenous reduction DQDA (EDQDA) algorithm that allows the reduction sequence to be determined endogenously. EDQDA is not strategyproof. 30We focus on eliminating justified envy among same types only because even with this weaker condition, there is an impossibility result (Proposition 1). 31Ehlers et al. (2014) actually show a stronger result, namely that there is no mechanism that is strategyproof, eliminates justified envy among same types, and is constrained non-wasteful. Their definition of constrained non-wastefulness is implied by constrained efficiency, and so there also is no mechanism that is strategyproof, eliminates justified envy among same types, and is constrained efficient. Theoretical Economics 12 (2017) Improving matching under constraints 885 5. General mechanisms with dynamic quotas For most of this paper, we have focused specifically on deferred acceptance. However, the main ideas behind artificial caps and dynamic quotas can easily be applied to any mechanism that has inputs for ceiling constraints but not for floors. This includes most standard mechanisms used in practice, such as the immediate acceptance mechanism, the serial dictatorship, and top trading cycles. Formally, we define a class of mechanisms called upper quota mechanisms.Upper quota mechanisms are indexed by vectors of ceilings and capacities (UQ),which we refer to jointly as upper quotas. Let M(UQ)={μ∈M:|μθ(s)|≤U sθ and |μ(s)|≤Q sfor all (s θ)}be the set of all matchings that respect (UQ). An upper quota mechanism is a function ψ(UQ):Pn→Msuch that ψ(UQ)(PI)∈M(UQ) for all PI∈Pn. A collection of mechanisms, one for each (UQ), is denoted := {ψ(UQ)}(UQ). We refer to as a class of upper quota mechanisms. As an example, could be the class of DA mechanisms as defined in Section 2:={DA(UQ)}(UQ). Note that upper quota mechanisms always satisfy the given ceilings and capacities (UQ), but again need not be feasible, for reasons similar to those discussed for DA in Section 2.If(¯ U ¯ Q) are such that ψ(¯ U ¯ Q)(PI)is feasible for all PI,thenwecallψ(¯ U ¯ Q) an artificial caps mechanism. For example, when is the class of DA mechanisms, then ψ(¯ U ¯ Q) is ACDA under artificial caps (¯ U ¯ Q). Definition 3. Let (UQ)and (UQ)be such that (UQ)≤(UQ)and θ∈(U sθ −U sθ)≤Q s−Q sfor all s∈S. The class of mechanisms is resource monotonic if, for all such (UQ)and (UQ),ψ(UQ)weakly Pareto dominates ψ(UQ). Resource monotonicity means that raising the ceilings and capacity of a school makes all students weakly better off, provided that the type-specific ceilings are not raised more than the capacity.32 We now generalize dynamic quotas to any class of mechanisms . Dynamic quotas (DQ) Fix a sequence of ceiling–capacity vectors η={(U1Q1) (U2Q2)(UKQK)}such that (i) (Uk+1Qk+1)≤(UkQk)≤(UQ) for all kand (ii) ψ(UKQK)(PI)is feasible for all PI. The algorithm then proceeds in a series of stages. Stage 1. Calculate ψ(U1Q1)(PI).Ifψ(U1Q1)(PI)is a feasible matching, end the algorithm and output this matching. If not, proceed to stage 2. 32Resource monotonicity has been used as an important axiom in many allocation settings (see, for example, Ehlers and Klaus 2004,Kesten 2006, and Thomson 2010). The previous works do not have typespecific ceilings, and prior notions of resource monotonicity say that raising just the capacity of a school makes all agents better off (in a Pareto sense). This is implied by Definition 3, but for our purposes, we want to allow the type-specific ceilings to be raised as well. However, we must do this in a “controlled” manner: raising the type-specific ceilings by more than the number of capacity seats may make students of other types whose ceilings were not raised worse off (see the discussion after Theorem 4). 886 Fragiadakis and Troyan Theoretical Economics 12 (2017) In general, proceed as follows. Stage k. Calculate ψ(UkQk)(PI).Ifψ(UkQk)(PI)is a feasible matching, end the algorithm and output this matching. If not, proceed to stage k+1. We define dynamic quotas as the function DQ:Pn→Mthat produces, for each input, the matching at the end of the above algorithm. Theorem 5. Assume that is resource monotonic and ηis a minimal reduction sequence. Then the dynamic quotas mechanism DQweakly Pareto dominates the artificial caps mechanism ψ(UKQK). DQDA is a special case of DQwhen is the set of deferred acceptance mechanisms and ηis a minimal reduction sequence (by Theorem 3). Dynamic quotas can also be applied to many other choices of . Besides DA, common upper quota mechanisms used in practice include the serial dictatorship (SD), immediate acceptance (IA), and top trading cycles (TTC).33 Versions of immediate acceptance are used in the Cambridge, MA and Minneapolis, MN school districts, and the algorithm has previously been used in Seattle, WA and Boston, MA. Versions of TTC are currently used in school districts in San Francisco, CA and New Orleans, LA. Since these are popular mechanisms, they are all natural candidates for use in the presence of floor constraints as well. Again, by imposing sufficiently strict artificial caps, it is possible to ensure a feasible matching. However, doing so results in the same inefficiencies as with deferredacceptance, because artificial caps still eliminates seats ex ante, ignoring important information contained in the student preferences. We thus argue that any market that uses artificial caps SD/IA/TTC would be better served by switching to dynamic quotas SD/IA/TTC. Because SD and IA are indeed resource monotonic, dynamic quotas SD/IA will Pareto dominate artificial caps SD/IA. TTC, alternatively, is not resource monotonic (Kesten 2006), and so, the Pareto dominance of dynamic quotas over artificial caps will not hold for TTC. However, it is still be true that the final matching implemented under dynamic quotas have higher ceilings than artificial caps, which intuitively makes the students better off on average. We thus suggest that policymakers may want to consider dynamic quotas over artificial caps, even if resource monotonicity does not hold formally. 6. Conclusion This paper shows that a common approach used in many matching markets with distributional constraints may result in avoidable inefficiencies. We introduce a new class of mechanisms based on a concept of dynamically adapting quotas. By using agents’ submitted preferences to allocate positions more flexibly given the reported demand, we 33The serial dictatorship is a simple mechanism where students are ordered and then one at a time, choose their favorite school that has space remaining. Immediate acceptance (also known as the Boston mechanism) and TTC (first defined by Shapley and Scarf 1974) are mechanisms that are common in the field and are well known in the literature, and so we refer the reader to other papers for their full definitions and analysis. A good introduction can be found in Abdulkadiro˘ glu and Sönmez (2003). Theoretical Economics 12 (2017) Improving matching under constraints 893 all θ. We show that (¯ U ¯ Q) ensures a feasible match. Let PIbe an arbitrary profile of preferences, and let νdenote the final assignment produced by DA under preferences PI. It is obvious that |νθ(s)|≤ ¯ Usθ ≤Usθ and |ν(s)|≤ ¯ Qs≤Qsby definition. What remains to be shown is that every student is assigned a school (i.e., no student is unmatched) and |νθ(s)|≥Lsθ. First, assume that some student iis unmatched. An equivalent way to run the deferred acceptance algorithm is to use the cumulative offer process of Hatfield and Milgrom (2005) (see the description of GDQDA in Appendix A). As shown in the proof of Lemma 2 below, the school choice functions for each school induced by (¯ U ¯ Q),denoted Chs(·), are substitutable and satisfy the law of aggregate demand. By definition, ν(s) =Chs(As(T)),whereAs(T ) denotes the cumulative set of offers received by school sat the end of the cumulative offer process. Let τ(i) =θ,andforallθ,letνopen θ(s) be the number of type θstudents who are assigned to a school sthrough its open seats. Since we assume that iis unmatched, we have i∈As(T) for all s(i.e., ihas applied to every school) and i/∈ν(s) for all s. Since i is not chosen by any school, one of the following (or both) must hold at every school s: (i) |νθ(s)|= ¯ Usθ or (ii) the type θseats at sare all filled with Lsθ other type θstudents and the open seats of sare filled with ¯ Qs−θ∈Lsθstudents of any type (i.e., θνopen θ(s) = ¯ Qs−θ∈Lsθ). Note first that it cannot be true that |νθ(s)|= ¯ Usθ for all s.Ifthiswere to hold, then s∈S|νθ(s)|=s∈S¯ Usθ =|Iθ|, but since iis not matched, at most |Iθ|−1 type θstudents are assigned under ν. Therefore, there must be at least one school for which (i) does not hold and, therefore, (ii) does hold. Thus, let ˆ sbe such a school, where θ|νopen θ(ˆ s)|= ¯ Qˆ s−θ∈Lˆ sθholds but |νθ(ˆ s)|<¯ Uˆ sθ. By construction, at school ˆ s, for every type θ,|νopen θ(ˆ s)|≤ ¯ Uˆ sθ−Lˆ sθ. Because θ∈¯ Usθ=¯ Qs, the only way for the ¯ Qˆ s−θ∈Lˆ sθopen seats at ˆ sto be filled is if |νopen θ(ˆ s)|= ¯ Uˆ sθ−Lˆ sθfor all θ.41 If ¯ Uˆ sθ >L ˆ sθ, then |νθ(ˆ s)|= ¯ Uˆ sθ (because all type θfloor seats must be assigned before any open seats can go to type θstudents). If ¯ Uˆ sθ =Lˆ sθ, then once again, |νθ(ˆ s)|= ¯ Uˆ sθ (because otherwise, one of the type θfloor seats would be empty and iwould have been accepted to s). In either case, |νθ(ˆ s)|= ¯ Uˆ sθ, which is a contradiction. Now that we know all students are matched to a school under ν, we can show that all floors are satisfied. Assume not, i.e., assume there is some pair (s θ) such that |νθ(s)|< Lsθ.Thens∈S|νθ(s)|<s∈S¯ Usθ =|Iθ|.42 But this implies that under ν,thereexists some student iof type θwho is not assigned to any school, which is a contradiction to what we just showed in the preceding paragraph. Proof of Theorem 2 Lemma 2 below shows that for any stage kof DQDA, the induced within-stage choice functions of the schools satisfy substitutability and the law of aggregate demand. Since 41If |νopen θ(ˆ s)|<¯ Uˆ sθ−Lˆ sθfor some θ,thenwecansumoverθto get θ|νopen θ(ˆ s)|< θ(¯ Uˆ sθ−Lˆ sθ)=¯ Qs−θLˆ sθ, which contradicts that the open seats are filled. 42The first inequality follows from the fact that s∈S\{s}|νθ(s)|≤s∈S\{s}¯ Usθ (because νrespects (¯ U ¯ Q) by construction) and that |νθ(s)|<L sθ ≤¯ Usθ. 894 Fragiadakis and Troyan Theoretical Economics 12 (2017) ACDA is equivalent to DA using the stage Kchoice functions, strategyproofness follows from Hatfield and Milgrom (2005), who show that substitutability and the law of aggregate demand are sufficient for strategyproofness. To show that ACDA eliminates justified envy among same types, note that ACDA is equivalent to DA under (UKQK). Denote the matching produced by DA under (UKQK)as μ. Assume that some student ienvies another student jof her same type: μ(j) Piμ(i) and τ(i) =τ(j) =θ. Let step tbe the step of the DA algorithm at which iis rejected from μ(j).Instept,iis rejected because the type θspecific seats are filled with Lμ(j)θ students of type θranked higher than iaccording to μ(j), and the open seats are filled with either (i) UK μ(j)θ −Lμ(j)θ students of type θranked higher than iaccording to μ(j) or (ii) QK μ(j) −θ∈Lμ(j)θ students of any type ranked higher than iaccording to μ(j). As the algorithm progresses, a student accepted in step tcan be rejected from the type θspecific seats only if a higher ranked student of type θapplies, and the same is true of the students at the open seats. Thus, at the end of the algorithm, all students assigned to μ(j) through either the type θspecific seats or the open seats must be ranked higher than i. Since τ(j) =θas well, this implies that jμ(j) i, i.e., idoes not justifiably envy j.43 Proof of Theorem 3 We first note the following lemma, which is proved in Appendix C. With slight abuse of notation, let η={Ch1ChK}be the sequence of choice functions induced by a reduction sequence {(U1Q1)(UKQK)}as in Definition 1. Lemma 2. The reduction sequence η={Ch1ChK}is monotonic, and Chk s(·)satisfies substitutability and the law of aggregate demand for all kand s. If, in addition, {(U1Q1)(UKQK)}is minimal in the sense of Definition 2,thenη={Ch1ChK} is minimal in the sense of Definition 7. Given Lemma 2,Theorem 3 then is a special case of Corollary 1. Proof of Theorem 4 Consider an ACDA mechanism with corresponding caps denoted (UKQK), and consider any nondegenerate reduction sequence {(U1Q1)(UKQK)}that is minimal (in the sense of Definition 2).44 Let η={Ch1ChK}be the reduction sequence of induced choice functions. Note that by Lemma 2,ηis monotonic, is minimal (in the sense of Definition 7), and Chk s(·)satisfies substitutability and the law of aggregate demand for all kand s. 43Of course, there may be students of other types θ= θwhom ienvies and has higher priority over, since these students could be assigned through the type θspecific seats. 44Recall that our model considers only markets where such nondegenerate reduction sequences exist. When they do not, the problem is trivial and uninteresting (see footnote 24). Theoretical Economics 12 (2017) Improving matching under constraints 895 Part (i). That all students weakly prefer the outcome of DQDA under ηto ACDA under (UKQK)for all PIfollows from Lemma 2 and Theorem 7.Itissimpletoconstruct a preference profile that exhibits a strict improvement for some student under DQDA. Part (ii). By Corollary 1, the final matching produced by DQDA is equivalent to SDA, which in turn is equivalent to DA under Chkfor some k≤K. That DA under Chkeliminates justified envy among same types can be shown using the same argument as in the proof of Theorem 2. Part (iii). Fix the reports of the other students at P−i,andleti’s true preferences be Pi. We show that there is no report P ithat gives ia better assignment than reporting the truth. In the proof, we move back and forth between the GDQDA and GSDA algorithms, which, by Corollary 1, are equivalent. We begin by working with GSDA, and make use of the fact that the DA algorithm within each stage kis equivalent to the cumulative offer process of Hatfield and Milgrom (2005). It is well known (McVitie and Wilson 1971;see also Dubins and Freedman 1981 or Hatfield and Kojima 2010) that the order in which students are allowed to apply does not matter, as any such order will lead to the same final matching. Consider an ordering in which student iapplies last. In stage kof the GSDA algorithm, let ˜ Bk sdenote the cumulative set of applicants that school sreceives in the cumulative offer process under Chkon all students other than i. Now, let ienter the market. This causes a rejection chain, which simply records the action of the algorithm:45 Step Action Cumulative offer sets 0None Bk ˆ s(0)=˜ Bk ˆ sfor all ˆ s 1Studentiapplies to school sBk s(1)=Bk s(0)∪{i} Bk ˆ s(1)=Bk ˆ s(0)for all ˆ s= s 2srejects iBk ˆ s(2)=Bk ˆ s(1)for all ˆ s 3iapplies to sBk s(3)=Bk s(2)∪{i} Bk ˆ s(3)=Bk ˆ s(2)for all ˆ s= s        The rejection chain in stage kends at the first step ˆ Tkfor which some student i applies to some school sand sdoes not reject a student. At this point, the applicant pools for each school are Bk s(ˆ Tk)and, as described above, the stage koutput μkis defined by μk(s) =Chk s(Bk s(ˆ Tk)). Note that by substitutability, if i∈Rejk s(Bk s(t)) for some step t,theni∈Rejk s(Bk s(t)) for all t≥t.Inparticular,i∈Rejk s(Bk s(ˆ Tk)), which implies that under μk, each student is assigned to exactly one school (by Corollary 2,nostudent is unmatched). Also, note that the law of aggregate demand guarantees at each rejection step, at most one student is rejected, which implies that in each application step, there is a unique student iwho applies to the next school on his preference list s. 45In the above description of the cumulative offer process, both the application and the rejection phases occurred in the same step. Here, we have broken the steps up into rejection steps and application steps for clarity. This changes the numbering of the steps, but does not affect the algorithm or the results in any other way. 896 Fragiadakis and Troyan Theoretical Economics 12 (2017) For any school sand applicant pool B⊆I,defineδs(B)=θ∈max{Lsθ −|B∩Iθ|0}. In words, δs(B)is the number of floor seats unfilled at swhen its applicant pool is B.46 Let k=s∈Sδs(˜ Bk s).Inwords,kis the total number of floor seats unfilled at all schools in stage kafter all students but ihave applied. Lemma 3. The following statements hold for all k: (i) If k=0,thenDAChk(P iP−i)∈Mffor all P i∈P. (ii) If k>1,thenDAChk(P iP−i)/∈Mffor all P i∈P. (iii) We have k≥k+1≥k−1. If 1=0, then all floor seats have been filled before ienters the market in stage 1, and the GDQDA algorithm ends in stage 1 for any report P iof agent i. Therefore, from the perspective of agent i, the mechanism is equivalent DACh1which is known to be strategyproof, and so she has no profitable manipulation. So assume that 1≥1.Lemma 3, part (iii) then implies that there is some critical stage k∗for which k∗=1and k>1 for all k<k ∗.ByLemma 3, part (ii), the algorithm does not end in stage k<k ∗for any report of student i. By the construction of GSDA, we can ignore the first k∗−1stages of the algorithm, and begin at stage k∗using choice functions Chk∗. From here forward we switch from GSDA and work with the GDQDA algorithm definition. Starting at k∗,let{˜ Ak∗ s}s∈Sbe the cumulative offer sets of the schools after running DA under Chk∗on all students other than i.47 Then let ienter the market with some reported preferences P i. As above, her entering again causes a rejection chain, an example of which is Stage Step Action Cumulative offer sets k∗0None Ak∗ ˆ s(0)=˜ Ak∗ ˆ sfor all ˆ s 1Studentiapplies to school sAk∗ s(1)=Ak∗ s(0)∪{i} Ak∗ ˆ s(1)=Ak∗ ˆ s(0)for all ˆ s= s 2srejects iAk∗ ˆ s(2)=Ak∗ ˆ s(1)for all ˆ s 3iapplies to sAk∗ s(3)=Ak∗ s(2)∪{i} Ak∗ ˆ s(3)=Ak∗ ˆ s(2)for all ˆ s= s k∗+11 Choice functions become Chk∗+1Ak∗+1 ˆ s(0)=Ak∗ ˆ s(3)for all ˆ s 2 School s rejects student i Ak∗+1 ˆ s(1)=Ak∗+1 ˆ s(0)for all ˆ s        46Recall that at every stage k, each school salways reserves Lsθ seats for students of type θ, and so if |B∩Iθ|≤Lsθ, then all type θstudents will be chosen, while if |B∩Iθ|>L sθ,atleastLsθ students of type θ will be chosen. 47These are equivalent to {˜ Bk∗ s}s∈S, the cumulative offer sets of standard DA under choice functions Chk∗ (by Lemma 1) on all students other than i. We switch the notation from Bto Ato emphasize the switch from GSDA to GDQDA and to remain consistent with the notation used above in their respective definitions. Theoretical Economics 12 (2017) Improving matching under constraints 897 As before, the rejection chain simply records the action of the algorithm. However, now note that because we are using the GDQDA algorithm, we include quota reductions as part of the rejection chain (stage k∗+1,step1above). There are several features to note about rejection chains. First, at stage k,steptof the rejection chain, the set of applicants being tentatively held by school sis Chk s(Ak s(t)). Second, monotonicity and substitutability guarantee that if at some stage and step (kt) we have i∈Rejk s(Ak s(t)), then i∈Rejk s(Ak s(t)) for all (kt)such that either (i) k>kor (ii) k=kand t≥t. This, together with the law of aggregate demand and minimality, guarantees that at each step, there is at most one student who is not currently being held by any school, and it is this student who makes the next application according to her preferences.48 Third, within a stage, the school rejecting a student at some step is the same as the last school to receive an application (since the cumulative offer sets of the other schools have not changed). However, across stages, this may not be true (because the school that (potentially) must reject a student at the beginning of a stage is determined by the reduction sequence). For example, at stage k∗,step3,sreceives an application. When the choice functions become Chk∗+1, school s rejects a student, but it may be that s = s. At stage k∗,k∗=1(by definition of k∗), which means that δy(˜ Ak∗ y)=1for some school yand δs(˜ Ak∗ s)=0for all s= y. By definition of δs(·),itmustbethat|˜ Ak∗ y∩Iφ|= Lyφ −1for some type φ∈,and|˜ Ak∗ s∩Iθ|≥Lsθ for all (s θ) = (y φ). In words, this means that every school has enough students in its choice set to fill all type-specific floors except for school y, which is one student short of filling its type φfloor. We next note the following important fact about rejection chains: The GDQDA algorithm ends the next time a type φstudent applies to y.(1) This is an “if and only if” statement: the algorithm ends at the next stage step (k t) at which a type φstudent applies to y, and cannot end earlier.49 The next part of the proof is inspired by the scenario lemma of Dubins and Freedman (1981). Define a scenario Sias a sequence of applications for agent i, i.e., a partial rank ordering over Sfor student i.SoascenariocouldbeSi={suv}, which means that ifirst applies to s,thentou,thentov. The list need not include all schools. Since the preferences of the other students are fixed at P−i, each scenario induces a corresponding rejection chain. We use R(Si)to denote the rejection chain corresponding to scenario Si. The rejection begins with iapplying to the first school in Si, and then records all subsequent applications, rejections, and quota reductions. The rejection chain for any scenario Siends in one of two ways: 48The law of aggregate demand guarantees this within a stage, while minimality guarantees it across stages. 49The algorithm obviously cannot end before (1) occurs. To see that it ends immediately once (1) occurs, note that by definition of the school choice functions, once a school sfills a type-specific floor, it never drops below it, because all schools salways reserve Lsθ seats for each type θ.Thus,once(1) occurs, the current stage ends (because no further student is rejected from s), and all floors are filled at all schools, so the algorithm ends. 898 Fragiadakis and Troyan Theoretical Economics 12 (2017) (i) Some student jof type φapplies to school y: Stage Step Action Cumulative offer sets ktjapplies to yAk y(t) =Ak y(t −1)∪{j} Ak ˆ s(t) =Ak ˆ s(t −1)for all ˆ s= s (ii) Agent iis rejected by the last school in Si: Stage Step Action Cumulative offer sets ktiis rejected by vAk s(t) =Ak s(t −1)for all s The following lemma is key to the remainder of the proof. Lemma 4. Consider two scenarios Siand ˆ Sisuch that every school in ˆ Siis also named in Si(order is immaterial), and assume that in R(Si),studentiapplies to every school in Si. Then every step in R(ˆ Si)also occurs at some point in R(Si). With this lemma in hand, we can continue the proof. Suppose, without loss of generality, that i’s true preferences are Pi:s1s2sm. Say that if isubmits her true preferences, she receives school sh, and suppose that there is some scenario ˆ Si={uv}, where igets some school vsuch that vP ish. Then rejection chain R(ˆ Si)must end with some student jof type φapplying to y, while iis assigned to v. Case (i): sP ivfor all s∈ˆ Si\{v}.Compare ˆ Sito a scenario Si={s1sh−1}.By assumption, ˆ Si⊆Si, and in R(Si),imakes every application in Si.50 In particular, the last step of R(Si)is “sh−1rejects i.” By Lemma 4, every application in R(ˆ Si)is also made in R(Si).Inparticular,jmust also apply to yin R(Si), which contradicts the fact that R(Si)ends with ibeing rejected by sh−1. Case (ii): vP isfor at least one s∈ˆ Si.Delete all schools s∈ˆ Sisuch that vP isto create a smaller scenario ˆ ˆ Si⊂ˆ Si.Bycase(i),R(ˆ ˆ Si)must end with irejected by v. Since ˆ ˆ Si⊂ˆ Si, Lemma 4 implies that imust also be rejected by vin R(ˆ Si), which is a contradiction. Proof of Theorem 5 Since (UKQK)ensures a feasible match under , we know that DQends no later than stage Kfor every PI;thatis,DQ(PI)=ψ(UkQk)(PI)for some k≤K. Since ηis a minimal reduction sequence, θ∈(Uk sθ −UK sθ)≤Qk s−QK sfor all s∈S.Byresource monotonicity, DQ i(PI)=ψ(UkQk) i(PI)Riψ(UKQK) i(PI)for all i∈I. Since this holds for all PI, the result follows. Appendix C: Omitted proofs of lemmas Proof of Lemma 1 We first start with two sub-lemmas. 50This follows because ireceives shwhen he submits his true preferences. Theoretical Economics 12 (2017) Improving matching under constraints 899 Lemma 5. If k≥k,thenBk s(ˆ Tk)⊆Bk s(ˆ Tk)for all s. Proof. By monotonicity, Chk s(I)⊆Chk s(I)for all s∈Sand all I⊆I. The statement then follows from Lemma 1, part (2) of Kamada and Kojima (2015).51  The next sub-lemma makes use of the following definition of stability. Note that this is only a technical definition used to prove the results below and is not related to the justified envy definitions used in the main text. Let Ch:= {Ch s1Ch sm}be a vector of choice functions (which again need not be equal to the primitive Ch). Definition 8. A matching μis stable with respect to Chif the following statements hold: (i) We have μ(s) =Ch s(μ(s)) for all s∈S. (ii) There exists no pair (i s) such that sP iμ(i) and i∈Ch s(μ(s) ∪{i}). Part (i) says that a school does not unilaterally reject any student assigned to it. The corresponding “individual rationality” property holds for students automatically, because we assume that all students find all schools acceptable. Given this definition, we have the following lemma. Lemma 6. Under νk, each student is assigned to at most one school, and νkis stable with respect to Chk. Proof. For the first part, note that within a stage k, substitutability implies Rejk s(Ak s(t −1)) ⊆Rejk s(Ak s(t)) for all t=1Tk, and across stages, monotonicity ensures that Rejk−1 s(Ak−1 s(Tk−1)) ⊆Rejk s(Ak s(0)) for all s.Thus,ifiis rejected by a school sat some step tof some stage k, then iis rejected in all later steps and stages, implying that no student is assigned to more than one school. For stability, first note that by irrelevance of rejected students (see footnote 34), Chk s(Ak s(Tk)) =νk(s) =Chk s(νk(s)).For the second part, if sPiνk(i),theniwas at some point rejected from s. This implies that i∈Ak s(Tk)but i/∈νk(s).Thismeansthatνk(s) =Chk s(Ak s(Tk)) ⊆νk(s) ∪{i}⊆Ak s(Tk), which, together with irrelevance of rejected students, implies that Chk s(νk(s) ∪{i})= νk(s), i.e., i/∈Chk s(νk(s) ∪{i}). Therefore, νkis stable with respect to Chk. We now use induction to show that Ak sTk=Bk sˆ Tkfor all s∈S(2) holds for all k. Since stage 1 of both algorithms is just the cumulative offer process starting with the empty matching and using choice functions Ch1,(2) holds for k=1. Assume the inductive hypothesis that (2) holds for 1k−1. We show that this implies it holds for kas well. 51See also the “capacity lemma” of Konishi and Ünver (2006) for a related result. 900 Fragiadakis and Troyan Theoretical Economics 12 (2017) First, note that since stage kof GSDA is simply the DA algorithm under Chk, we know that μkis the student-optimal stable match with respect to Chk(Hatfield and Milgrom 2005). Further, by Lemma 6,νkis some match that is stable with respect to Chk.This implies that μk(i) Riνk(i) for all i∈I. This implies that Bk s(ˆ Tk)⊆Ak s(Tk)for all s∈S.52 Last, we must show that Ak s(Tk)⊆Bk s(ˆ Tk)for all s∈S. Assume to the contrary, i.e., that there exists some ssuch that Ak s(Tk)Bk s(ˆ Tk),andlettbe the first step of stage k of GDQDA such that Ak s(t) ⊆Bk s(ˆ Tk)for all t<t and all s∈S,butAk s(t)Bk s(ˆ Tk).53 Let ibe the student who applies to sat step t.Thismeansthatiis rejected from μk(i) (the school she is matched to under GSDA) in some step of stage kof GDQDA; let the earliest of these steps be t,sothati∈Rejk μk(i)(Ak μk(i)(t)).54 Further, note that t <t ,which,by the definition of t,impliesthatAk μk(i)(t)⊆Bk μk(i)(ˆ Tk). Substitutability of the choice functions within stage kthen implies that Rejk μk(i)(Ak μk(i)(t)) ⊆Rejk μk(i)(Bk μk(i)(ˆ Tk)), which means i∈Rejk μk(i)(Bk μk(i)(ˆ Tk)), which contradicts the fact that iis assigned to school μk(i) under GSDA in stage k. Proof of Lemma 2 Substitutability. Consider a school s,stagek, and set of students Isuch that i∈Rejk s(A), and another set of students A such that A⊆A.Letτ(i) =θ. When the set of applicants is A,studentiis rejected because the type θspecific seats are filled with Lsθ higher ranked type θstudents, and the open seats are filled with either (i) Uk sθ −Lsθ higher ranked type θstudents or (ii) Qk s−θ∈Lsθ higher ranked students of any type. In either case, since all students in Aare also in A, when school sis choosing from A, the type θspecific seats are once again filled with Lsθ higher ranked type θstudents, and either condition (i) or (ii) also still holds. So i∈Rejk s(A)as well. Monotonicity. If sis not the school whose quotas are reduced in moving from stage kto k+1, then Rejk s(A)=Rejk+1 s(A)trivially. So let sbe the school whose capacity is reduced in moving from stage kto k+1,Qk+1 s=Qk s−1and Uk+1 sθ =Uk sθ −1, while Uk+1 sθ=Uk sθfor all other θ= θ. We want to show that Rejk s(A)⊆Rejk+1 s(A)for all kand all A⊆I.Todoso,weshow the contrapositive: i∈Chk+1 s(A)=⇒ i∈Chk s(A) Assume not, and let ibe the highest ranked student according to ssuch that i∈ Chk+1 s(A),buti/∈Chk s(A)(equivalently, i∈Rejk s(A)). Let τ(i) =θ,whichmayormay 52If this were not the case, then there exists some ssuch that Bk s(ˆ Tk)Ak s(Tk). This means that in GSDA in stage k,somestudentiis rejected from νk(i) (her match under GDQDA). But this contradicts the fact that μk(i) Riνk(i). 53Such a texists because Ak s(0)=Ak−1 s(Tk−1)=Bk−1 s(ˆ Tk−1)⊆Bk s(ˆ Tk)for all s∈S,wherethefirstequality is by definition, the second is by the inductive hypothesis, and the set inclusion is by Lemma 5. 54Note that imust be rejected at some step t of stage k(and not in an earlier stage). To see this, assume that iwas rejected from μk(i) in some earlier stage kof GDQDA. This implies that μk(i) Piνk(i).Since k<k, Lemma 1, part (1) of Kamada and Kojima (2015)impliesthatμk(i) Riμk(i). By combining these two inequalities, we conclude that μk(i) Piνk(i), which contradicts the inductive hypothesis. Theoretical Economics 12 (2017) Improving matching under constraints 901 not be equal to θ.Ifiis admitted through the type θspecific seats in stage k+1, then she is one of the Lsθhighest ranked type θstudents in A, and so she will be admitted in stage kas well. So imust be admitted through an open seat in stage k+1. Therefore, when i’s application is considered in stage k+1, the following statements both hold: (a) at most Uk+1 sθ−Lsθ−1higher ranked type θstudents have been accepted to the open seats and (b) at most Qk+1 s−θ∈Lsθ −1students in total have been accepted to the open seats. Define J={j∈Rejk+1 s(A):jsi}. Note that (b) implies that for all j∈J, the type-specific ceiling Uk+1 sτ(j) is reached before j’s application is considered in stage k+1, which, in particular, means that τ(j) = θfor all j∈J. Since Qk s=Qk+1 s+1,forito be rejected under stage kquotas, there must be two j1j2∈Jsuch that j1j2∈Chk s(A); without loss of generality, let j1sj2si. Since j1∈ Chk s(A),itmustbethatτ(j1)=θ.55 Then, after j1is admitted, the Uk sθ ceiling is now binding (since Uk sθ =Uk+1 sθ +1and all jsj1who are admitted under stage k+1quotas are also admitted under stage kquotas by the assumption that iis the highest ranked such student for which this is not the case). So when j2’s application is considered, she will be rejected, which is a contradiction.56 Minimality. As for monotonicity, we only need consider the school swhose quotas are reduced in moving from kto k+1.Letsbe the school such that Qk+1 s=Qk s−1and Uk+1 sθ =Uk sθ −1for some θ, while Uk+1 sθ=Uk sθfor all θ= θ. Consider a set of applicants A⊆I,withCh k s(A)the set that is admitted in stage k. There are four cases. Case (i): |Chk s(A)|<Q k sand |Chk s(A)∩Iθ|<U k sθ. In this case, Chk+1 s(A)=Chk s(A), which implies |Chk s(A)|−|Chk+1 s(A)|=0. Case (ii): |Chk s(A)|=Qk sand |Chk s(A)∩Iθ|<U k sθ.Letibe the lowest ranked student admitted through the open seats in stage k.ThenCh k+1 s(A)=Chk s(A)\{i},which implies |Chk s(A)|−|Chk+1 s(A)|=1. Case (iii): |Chk s(A)|<Q k sand |Chk s(A)∩Iθ|=Uk sθ.Letibe the lowest ranked type θstudent admitted through the open seats in stage k.ThenCh k+1 s(A)=Chk s(A)\{i}, which implies |Chk s(A)|−|Chk+1 s(A)|=1. Case (iv): |Chk s(A)|=Qk sand |Chk s(A)∩Iθ|=Uk sθ.Letibe the lowest ranked type θstudent admitted through the open seats in stage k.ThenCh k+1 s(A)=Chk s(A)\{i}, which implies |Chk s(A)|−|Chk+1 s(A)|=1. Law of aggregate demand. Within a stage, school sadmits students one by one until either some type-specific ceiling Uk sθ or overall capacity Qk shas been reached. More students in the applicant pool clearly weakly increases the number of students admitted, and the law of aggregate demand is satisfied. 55If τ(j1)= θ,thenUk sτ(j1)=Uk+1 sτ(j1). Then, since all jsj1such that j∈Chk+1 s(A)also satisfy j∈Chk s(A) (by the assumption that iis the highest ranked student for which this is not the case), the ceiling for type τ(j1)students will already have been reached in stage kwhen j1’s application is considered, and j1will be rejected. 56If τ(j2)=θ, this follows from the previous sentence. If τ(j2)= θ, it follows from the same argument as in footnote 55. 902 Fragiadakis and Troyan Theoretical Economics 12 (2017) Proof of Lemma 3 We use the following facts about δs: (a) We have B⊆B=⇒ δs(B)≤δs(B). (b) If δs(B∪{i})<δ s(B)=⇒ Rejk s(B∪{i})=Rejk s(B)for all k. Fact (a) follows immediately from the definition of δ. Fact (b) follows because δs(B∪{i})<δ s(B)implies that student iis of some type θsuch that |B∩Iθ|<L sθ. But this means that when the applicant pool at school sis B∪{i},studentiis accepted through one of the type θseats. This does not affect the students accepted by the type θseats for θ= θor the open seats, and thus Chk s(B∪{i})=Chk s(B)or, equivalently, Rejk s(B∪{i})=Rejk s(B). Part (i). Since k=0,theset ˜ Bk scontains at least Lsθ students of type θfor all schools s.LetBk s(ˆ Tk)be the cumulative set of applicants to school sat the end of stage k. Since ˜ Bk s⊆Bk s(ˆ Tk)for any submitted preferences of student i,Ch k(Bk s(ˆ Tk)) is a feasible assignment for school s, and the algorithm ends in stage k. Part (ii). We can have k>1in two ways: either δs(˜ Bk s)>1for some school or δs(˜ Bk s)≥1for multiple schools. First, consider δs(˜ Bk s)>1for some school s.Thismeans that there are at least two floor seats at sthat are not yet filled because not enough students have applied to s. When student ienters the market in stage k,hecausesarejection chain. As described in the proof of Theorem 4, the rejection chain is such that in each application step, only one student makes an application. So stage kends the first time a school gets an application from a student iand does not reject an additional student. Since any time a floor seat is filled, no further student is rejected, at the end of stage k, at most one of the unfilled floor seats at scan be filled, and so the assignment of school swill still not be feasible. Thecasewhereδs(˜ Bk s)≥1for multiple schools is argued similarly. Part (iii). By Theorem 6,˜ Bk+1 scan equivalently be computed by starting with ˜ Bk sand then reducing the choice functions to Chk+1. Doing so causes a rejection chain that ends the first time a student iapplies to a school sand sdoes not reject a student. Since ˜ Bk s⊆˜ Bk+1 s,wehaveδs(˜ Bk+1 s)≤δs(˜ Bk s), which implies that k≥k+1.Toseethat k+1≥k−1, note that in the rejection chain, the first time a student applies to a school and fills a floor, no further student is rejected (by fact (b)) and the rejection chain ends. Thus, at the end of the rejection chain, at most one floor seat that was not filled under ˜μkcan be filled under ˜μk+1,andsok+1≥k−1. Proof of Lemma 4 We use the notation (k t) to denote the line corresponding to stage k,steptof a rejection chain (note that we calculate the algorithm by starting at k∗, so in the remainder of this proof k≥k∗holds). Let Ak s(t) denote the cumulative offer set of school sat line (kt) of R(Si),andlet ˆ Ak s(t) denote the corresponding set at line (k t) of R(ˆ Si). Similarly, let tkdenote the final step of stage kunder scenario Si,andletˆ tkdenote the final