Are Affirmative Action Policies so Impossible?

Julien Combe

doi:10.3917/redp.286.1123

Notes

[1]
We will not enter here into the details of the entire french procedure. For instance Hiller and Tercieux [2014] showed that the algorithm is equivalent to a college proposing Deferred Acceptance algorithm. See also Fack and Grenet [2011] for the history and an analysis of the reform.
[2]
A School Choice Problem is defined in the literature as the problem of matching students to schools in respecting capacity constraints and where the priorities in each school are fixed (by law for example). In this setting, schools are considered as “consumed objects” and are not strategic agents. Welfare evaluations only consider the preferences of the students. Problems where schools have intrinsic preferences are called College Admission Problems.
[3]
More formally, it is a dominant strategy for them to do so, i.e. for any priorities of the schools and preferences of the other students, a student cannot obtain a strictly better school by reporting a false list of preferences. This result was proved by Dubins and Freedman [1981] and Roth [1982].
[4]
Concerning the positive interpretation of stability, Roth [1991] studied seven different assignment markets for new physicians and surgeons in the United Kingdom, and showed that procedures leading to a stable assignment were still in use while most of the unstable ones were quickly abandoned.
[5]
The Parcoursup procedure is different from a purely centralized algorithm. A centralized platform sends the applications of the students to the universities that then select them. Moreover, it only asks students to report a non-ordered list of universities contrary to the standard school choice procedures, such as DA, that ask for an ordered list. We only want to highlight here the use of the quotas in the system. The interested reader can find details of the procedure on many French newspapers (e.g. lemonde.fr [2018]) or on the official website https://www.parcoursup.fr/. Concerning the quotas, one can also refer to Studyrama [2018].
[6]
In Paris, the grades of the two students are used to break the tie. In other regions, the birthdate is also used. However, from a student perspective, it is unlikely that he exactly knows the characteristics (birthdate, grades...) of every other student so that he perceives the procedure as random. In that context, the use of an interim-welfare approach is also justified.
[7]
By interim-welfare, we mean the expected utility of each student once he has learned his own preferences but there is still some randomness in the assignment, e.g. the tie-break. The cited authors used the word “ex-ante” but, in a recent work, Troyan [2012] used an even earlier evaluation of welfare prior to the realization of students’ preferences.
We choose here to adopt the classical terminologies of the mechanism design literature in calling ex-ante welfare the one before any realization of information, taking expectations over all the possible types of the students. Interim-welfare refers to the welfare once each player has learnt his own type but not the one of the others. And the ex-post welfare is simply the utility that each student obtains once all the uncertainty is resolved, i.e. his final assignment’s utility.
[8]
Recent works studied the probabilistic differences between STB and MTB rules. Ashlagi and Nikzad [2015] showed that, when there are enough seats for all the students, there are efficiency trade-offs between the two rules. However, aSTB rule is preferable when there is a shortage of seats. Ashlagi, Nikzad and Romm [2015] showed that a STB rule leads to a constant fraction of students being assigned their first ranked school contrary to a MTB rule where this fraction vanishes with the size of the market. Arnosti [2016] highlighted the trade-off of the two rules between minimizing the number of unassigned students and maximizing the number of students being assigned their first choice.
[9]
In the following analysis, we will assume that all students (resp. schools) find all the schools (resp. students) acceptable.
[10]
Since a student’s matching is a singleton, we will abuse of notations and write μ (i) = c iff μ (i) = {c}.
[11]
In the case where there are unacceptable schools or students, we need to add an individual rationality constraint, i.e. ∀i, μ (i) ≻_i ∅ and ∀c, μ (c) ≻_c ∅.
[12]
The reader can refer to the cited articles for the formal definitions.
[13]
Note that, at each step, the acceptance of a student is temporary since it can be rejected at a later step in the case where new students apply to the school.
[14]
In their first introduction of affirmative action policies, Abdulkadiroglu and Sönmez [2003] defined different groups of minority students. Other papers also studied these multiple-groups models, the reader can refer to Ehlers et al. [2014] who introduced ways to implement quota policies using DA. Other similar works followed: see Kamada and Kojima [2014], Echenique and Yenmez [2015] or Kamada and Kojima [2017]. However, their goal is different from ours. They mainly focus on distributional concerns i.e. the existence of stable matchings that respect the quotas and how to correctly define DA in their setting. Here, as mentioned, we chose to have a welfare oriented analysis.
[15]
As mentioned, we suppose here that every school (resp. student) finds all the students (resp. schools) acceptable.
[16]
Here the definition does not distinguish between seats in clearly separating open from reserved seats. This stability notion only uses the number of students of different types assigned to a school. Recent works are dealing with priorities that are determined for each seat of a school to allow more complex priority stuctures. The general model introduced by Kominers and Sönmez [2013] that was inspired by the cadet-branch matching problem of Sönmez and Switzer [2013]. We describe it in Section 3.2.
[17]
For vectors, we write x > x′ if all the coordinates of x are weakly higher and some strictly.
[18]
The reader can easily find this matching in applying DA. The same ordinal preferences for the students ensures the uniqueness of the stable matching.
[19]
In this setting, any matching is Pareto-efficient.
[20]
There are two possible explanations for the use of expected utilities. The first one is that priorities are coarse and that ties are broken randomly during the algorithm so that the students do not know their particular ranking at a school when they submit their preferences. The second one is to assume that the priorities are strict but that the students do not know the characteristics of the other students that determine their ranking relative to their one.
[21]
Majority students will face a different distribution. The analysis for them will be the exact symmetric of the one for minority students.
[22]
This strongly relies on our assumption that all schools have the same number of seats. The analysis is similar if one allows schools to have different capacities. This assumption just avoids the heaviness of dealing with sums of the form q_l if quotas are different from one school to another. The assumption that there are enough seats for all students is a natural one if we think of the context of public school choice problems. Assuming, N = Mq avoids to deal with empty seats and unassigned students but relaxing this assumption will not change any of our results.
[23]
Note that, as stated, the direct effect concerns an increase in the probability of being assigned to the new prioritized school and the indirect affect corresponds to the increase in the expected utility conditional on being rejected from the latter school. Thus, they deal with different mathematical objects. To compare the effects, one can compare the increase in the expected utility conditional on not being rejected by the new prioritized school to the increase in the expected utility conditional on being rejected from that school. However, the difference in values crucially depends on the vNM cardinal utilities so that, for some of them, the direct effect will be bigger than the indirect one and vice-versa for other vNM utilities.
[24]
A distribution F first order stochastically dominates another distribution G, if ∀x, F (x) ≤ G (x).
[25]
As discussed before, we assume that our policy respects an anonymous criterion when treating minority students. One can also interpret the prioritized seats as a HB or a SB policy. For a HB policy, the prioritized seats must find the majority students as unacceptable.
[26]
Once again, we focus on policies that aim to improve minority students’ welfare. Objectives focusing on the distribution of the students between different schools pursue a different goal, we refer the interested reader to the previously cited literature.
[27]
As mentioned, Dogan [2016], proposed a modification of the DA algorithm to ensure that the algorithm respects the spirit of affirmative actions as defined by Kojima [2012]: it ensures that at least one minority student is strictly better-off after the reinforcement of a policy. Contrary to him, as mentioned, to seek positive results, we chose to impose the Pareto-domination rather than precluding the Pareto-inferiority of the resulting matching.
[28]
I would like to thank Olivier Tercieux for pointing the equivalence with their result.
[29]
For HB or SB policies, the only positive result is when all the seats in all schools are prioritized for minority students.
[30]
In France, roughly 25 % of the students are boursiers so that we chose to keep the same proportion.
[31]
This simulation technique is standard in the literature. See for instance Erdil and Ergin [2008], Hafalir, Yenmez and Yildirim [2013] or Hiller and Tercieux [2014].
[32]
One can note that since r_ij, r_i ∈ [0, 1] and that the difference of points between any two students who do not belong to the same class is greater than 2, then these students are still ranked in the same way once ties are broken. Moreover, the reader can check that, with probability one, these two rules indeed induce strict orderings of the students that correspond to the MTB and STB rules.
[33]
One can check that, with the chosen values, the ordering between minority (resp. majority) students belonging to the same class and the ordering between any two students from two different classes remains them after the policy.
[34]
The codes must be changed if one wants to simulate policies that prioritize only a fraction of the seats of a school. Our qualitative results won’t be affected by such change.
[35]
To obtain the exact expected utility, we would have to compute all the possible priority vectors of the schools. This cannot be done in polynomial time. For example for 10 students with L = 1, there are already 3,628,800 possible rankings for one school. Our estimates already give good comparative statics. Our codes allow the user to freely set of the parameters (number of students, schools, capacities, iterations, indifference classes, correlations...) so that one can easily replicate and extend our results if needed.
[36]
Our simulations already iterate for many values of β, L and m so that the total number of iterations is already high. As mentioned or goal is not to perform an exhaustive simulation exercise but to provide some key observations once one relaxes our assumptions.
[37]
At the exception of the STB policy for the combination of low values of m and high values of β where the number decreases. We are not able to provide a good intuition of why it is the case.
[38]
This intuition is somehow in line with the analysis of Ashlagi, Nikzad and Romm [2015] and Arnosti [2016]. Indeed, the former state that “under STB, the more schools a student is rejected from, the less likely she is to cause other students (who may be assigned to their top choices) be rejected from other schools” and so the more likely he is to be rejected from these schools. They state that this effect can explain why a STB rule tends to assign, in a large market analysis, more students to their top choices.
[39]
For each k from 1 to 50, we calculate the number of minority students being assigned up to their k-th most preferred school.
[40]
The empirical distributions of our simulations are not stochastically ordered. However, Corollary 2 states that the true distributions are. The number of iterations of tie-break to calculate the expected utilities and the distributions is probably too low.
[41]
The number of iterations is already high. Our goal is not to provide an exhaustive analysis. However, our codes allow to let any parameter vary. Variations in the correlation of schools’ priorities have already been studied in the literature with strict priority orderings, see Hafalir, Yenmez and Yildirim [2013]. Our main contribution being to introduce the interim stage analysis, we want to compare it with the ex post one, i.e. in letting L vary.
[42]
Note that, when m = 50, all schools move minority students at the top of the ranking inside their class. It does not imply that minority students are ranked at the top of the priority ranking of the school since the ranking between classes remains the same. Thus, when L > 0 and m = 50, this is not a maximal priority based affirmative action as defined in Section 4 and minority students can still be worse-off after the policy.
[43]
By iteration, we refer to fixed preferences, distribution of the students in the classes and priority points for the classes.
[44]
Of course, there is no first order stochastic ordering between any two distributions.
[45]
We refer the reader to the cited articles in the introduction dealing with such objectives.
[46]
Paris is divided into four districts (North, South, East, West) with around 10 to 17 schools in each district. For further details, one can refer to the official website, in french, https:// www.ac-paris.fr/portail/jcms/p1921184/affectation-en-2de-gt-pour-un-eleve-scolarise-a-paris-etablissement-public-ou-prive-sous-contrat or the description, in english, provided on the Matching in Practice website: http://www.matching-in-practice.eu/matching-practices-in-secondary-schools-france/.
[47]
For instance, the bonus can induce a minority student to reject a majority student who will then reject a minority student from outside the district and make him/her worse-off.
[48]
Results available upon request. The distributions are similar to those reported in Section D of the Appendix (figure 3 for instance) except that the values are averaged over all preferences’ iterations rather than reported for only one of them.
[49]
See for instance Lee [2016], Lee and Yariv [2014], Che and Tercieux [2015b] and Che and Tercieux [2015a].
[50]
Formally, we fix ε > 0 and study the asymptotic behavior of the percentage of minority students whose utility after the reinforcement of the policy is less than their utility before the reinforcement minus ε.
[51]
By our assumption on k^*, we are sure that the event happens with a strictly positive probability. Also note that, since we condition on and that i is a minority student, then the number of minority students accepted before step k^* must be strictly lower than n.
[52]
Indeed, note that the policy transfers probability mass to which, because of aligned preferences, is always strictly greater than the expected utility conditional on being rejected by since the latter is at most equal to .
[53]
Indeed, the probability that exactly two minority students are assigned to the two first slots of c₁ is simply the probability that a minority student is assigned the open slot, i.e. under ▷ and under ▷ ′ . It is easy to see that it is higher under ▷ ′ .

1. Introduction

1 Over the past years, many cities around the world have adopted procedures that give more freedom to parents to express their preferences over the schools that they would like their children to attend rather than constraining them to a pure geographical assignment. In France for instance, the 2007 reform of the school zoning in secondary schools weakened the former pure geographical assignment of students, called carte scolaire, in allowing parents to submit their preferences to a centralized procedure, called Affelnet, that determines the assignment. [1] Other examples of similar reforms are well-known in the matching literature. The July 2005 Boston Public School reform, following the work of Abdulkadiroglu and Sönmez [2003], Abdulkadiroglu et al. [2005] and Abdulkadiroglu et al. [2006], adopted the student proposing Deferred Acceptance (DA) algorithm found by Gale and Shapley [1962]. Indeed, DA offers many attractive properties for a School Choice Problem: [2]

It returns a stable matching: if a student prefers a school to its assigned one, then all the students assigned to this school have a higher priority than him. Moreover, it returns the student optimal stable matching: students all prefer it to any other stable matching.
It is strategy-proof: students have the incentive to report their true list of preferences to the centralized procedure. [3]

3 Stability is an important requirement when assigning students to schools. Indeed, it is often viewed as a “fairness” criterion leading to no no justified envies: if a seat was granted to a student with a lower priority than another one, then the parents of the latter would have a justifiable claim over the seat. In the U.S., Abdulkadiroglu and Sönmez [2003] also provided examples of parents suing the legislator for the existence of such cases. [4]

4 Strategy-proofness raises the problem of the existence of strategic behaviors. In Boston for instance, the previously used algorithm was not strategy-proof. Abdulkadiroglu et al. [2006] showed that the parents who failed to correctly strategize were mostly low income families. It has been one of the main arguments that convinced the Boston Public School Board to rather adopt the DA algorithm.

5 Priorities of the schools are often set by the legislator and can use different criteria to sort students. An important one is the geographical proximity of the student to the school. For instance, for the assignment of secondary school students, called Affelnet, Paris is split into four districts in which students living in a particular district receive more points in this district than those living in another one. Another criterion used in France concerns students who are boursiers, i.e. being eligible to a public grant based on the family income. In Affelnet, each boursier receives a priority increase in all the schools. Recently, a new assignment procedure for students to universities has been adopted. The new procedure, called Parcoursup, imposes quotas of boursiers students in universities receiving more applications than their capacity. [5] These two types of policies are called affirmative action policies and the group of targeted students are referred to as minority students.

6 Targeting students and improving their priority ranking can pursue different goals:

Distributional objective: the policy maker wants to promote diversity, as it is called in the literature, in implementing the right balance between different types of students. There can be several motivations: reinforcing peer-effects between students, favoring exchanges between different social groups, avoiding spatial segregation and so on. These policies are assessed by their impact on the distribution of the different types of students in the schools.
Welfare objective: the policy maker wants these students to have a better access to schools that they prefer. To assess such policy, one has to check the final assignment of the targeted students and whether they indeed have been able to access more preferred schools.

8 Mixed goals are obviously possible and both of them are clearly interconnected: influencing the outcome of the matching necessarily has an impact on students’ welfare. However, depending on the policy maker main objective, the policy recommendations can differ. An important challenge is to assess the impact of a modification of the priority of the schools on the final assignment determined by the algorithm. Indeed, the preferences of the students and the priorities of the schools interact through the algorithm to determine the final outcome. These interactions can lead natural affirmative action policies to undesirable effects on the minority students’ welfare. Two important affirmative action policies have been studied in the matching literature:

Quotas: a certain number of schools are reserved in some schools and only minority students can be assigned to them.
Priority based: the ranking of some minority students in some schools is increased. The Parisian boursier policy belongs to this class.

10 This article focuses on policies with welfare objectives in evaluating affirmative action policies according to their effects on minority students’ welfare. Kojima [2012] showed that the two aforementioned affirmative action policies can ultimately hurth the welfare of the minority students. Hafalir, Yenmez and Yildirim [2013], further studied quota policies and also showed, through simulations, that the results in Kojima [2012] were not specific cases and that a significant proportion of minority students can be hurt by these policies. However, to evaluate the loss in minority students’ welfare, they take an ex-post perspective, i.e. the utility of the final assignment of each minority student. They assume that there is no intrinsic randomness in the allocation procedure. However, in practice, schools’ priorities involve ties between different students. In the Parisian point system that is used to determine schools’ priorities, many students can end up having the same number of points. To run the DA algorithm, ties must be broken and it is often done randomly. [6] Abdulkadiroglu, Che and Yasuda [2015] and Abdulkadiroglu, Che and Yasuda [2011] took an interim-welfare perspective to analyze the DA and the Boston algorithms. [7] Our goal is to merge Kojima [2012]’s affirmative action analysis and Abdulkadiroglu, Che and Yasuda [2011]’s random environment. In the latter, the authors assume that the students all agree on the ordinal ranking of the schools but can differ in the cardinal values that they attach to them. The schools are assumed to be completely indifference between the students and ties are broken randomly. Even if this environment is extreme, it can be viewed as approximating a strong correlation between students’ preferences.

11 We will show that, in this setting, any reinforcement of an affirmative action policy always increases the expected utility of a minority student. Moreover, our analysis precisely decomposes the two effects of prioritizing some seats for minority students in a school: i) a direct one: for a minority student, it increases his probability to be assigned to the school and ii) an indirect one: conditional on being rejected by the school to which the policy is applied, it decreases the competition of other minority students for seats prioritized in less preferred schools and so increases the conditional expected utility of the minority student. Dur et al. [2017] highlighted the distributional effects of the order in which prioritized seats are filled during the algorithm, called precedence order. In our setting, we show that this order can also have effects on the interim-welfare of minority students and that it can also be used as a policy tool for such objective. We provide counter examples to show that our results do not hold when one relaxes any of the assumptions, i.e. one can build examples where minority students are hurt even from an interim perspective. We also provide results on ex-post welfare. Last, we perform simulations to assess the interim-welfare effects of affirmative action policies when students’ preferences can differ and when schools are not fully indifferent. When one only allow different preferences for the students but still completely indifferent schools, they support that the more the correlation, the better the affirmative action policy performs. They also highlight another important result. When schools are indifferent between the students and that ties must be broken randomly, there are two possible rules: 1) the Single Tie Breaking rule where schools all use the same ranking to break the their ties and 2) the Multiple Tie Breaking rule where each school break its ties independently of the other schools. In the literature, see Abdulkadiroglu, Pathak and Roth [2009] for instance, some arguments in favor of a STB rule for students’ welfare has been given. Our simulations show that, in the case of affirmative action policies, the reverse holds: aMTB rule tends to lead to less minority students being hurt by an affirmative action policy. [8] Finally, our work emphasizes that taking an interim welfare perspective in assessing the performance of affirmative action policies can lead to more positive results. Such approach opens the door to future works using this approach, notably in trying to balance the welfare and the distributional objectives of affirmative action policies.

12 In Section 2, we review the different frameworks and results of the matching literature important for our analysis. In Section 3, we show and discuss our main results concerning the interim-welfare impact of affirmative action policies. Section 4, will provide further ex-post results and Section 5 will provide the results of our simulations. Last, Section 6 will conclude and discuss implications for the different French assignment procedures.

2. Models, notations and main results of the literature

13 A classical School Choice Problem is a tuple T = ⟨ I, C, q, ≻ c ⟩ formed by:

A finite set I: = { i₁,..., i_N } of N students. A generic student will be denoted by i.
A finite set C: = { c₁,..., c_M } of M schools. A generic school will be denoted by c.
Each student i ∈ I has a linear order of preferences ≻_i over the set of schools. ≻_I is the vector containing the linear order of each student, i.e. ≻_I = (≻_i )_i _{∈ I} .
Each school c ∈ C has a linear order of priorities ≻_c over the set of students. ≻_C is the vector containing the linear order of each school, i.e. ≻_C= ( ≻_c) _c _{∈ C}.
q is a vector in which each coordinate q_k represents the number of seats in school c_k ∈ C. For a generic school c we let q_c be its capacity.

15 We say that student i (resp. school c) finds school c (resp. student i) acceptable if c ≻_i ∅ (resp. i ≻_c ∅) where ∅ represents the null match, i.e. remaining unassigned. [9] We will be interested in a specific domain of preferences for the students. The preferences (≻_i )_i_∈I are aligned preferences if ∀i ≠ j ∈ I, ≻_i = ≻_j, i.e. all the students have the same preference ordering over the schools. A matching is a correspondence μ: I ∪ C ⇉ I ∪ C where:

μ (i) ∈C and where μ (i) =∅ means that student i remains unassigned. [10]
μ (c) ⊂ I where |μ (c) | ≤ q_c.
μ (i) = c ⇔ i ∈ μ (c).

17 A matching μ is stable, if and only if there does not exist a pair (i, c) ∈ I × C s.t. c ≻_i u (i) and i ≻_c i′, for some i′ ∈ μ (c). [11]

18 A matching mechanism is a function ϕ which, for each School Choice Problem T, returns a matching ϕ (T). A mechanism is stable if, ∀T, ϕ (T) is stable for the problem T. Other types of mechanisms exist. For instance, it is well-known that a stable matching is not necessarily Pareto-efficient for the students so that one can reassign students s.t. they are all weakly better-off and some strictly. The Top Trading Cycle (TTC) algorithm, initially proposed by Shapley and Scarf [1974] for reassigning houses and later extended by Abdulkadiroglu and Sönmez [2003] for school choice problems, is an example of a non stable but Pareto-efficient mechanism. [12] In the following, we will restrict our analysis to the Deferred Acceptance (DA) algorithm proposed by Gale and Shapley [1962]. It works as follows:

Step 1. All students apply to their first ranked school. If a school receives more applicants than its number of seats then it selects the best students according to its priority ordering and rejects the others.
Step k ≥ 2. All the rejected students at step k − 1 apply to their favorite school among those that have not rejected them yet. Each school considers the set of its previously accepted students and its new applicants: if there are more students than its number of seats, then it again selects the best according to its priority ordering and rejects the others. [13]

20 In the environment of aligned preferences, the DA and TTC mechanisms lead to the same matching that is stable and also Pareto-efficient for the students. Moreover, this matching is the only stable matching so that our results will also apply to any other stable mechanism in this setting. However, if preferences are not aligned, this equivalence does not hold anymore.

2.1. Types of affirmative action policies

21 We closely follow Kojima [2012] who was inspired by the notion of the respect of improvements proposed by Balinski and Sönmez [1999]. The goal of the policy is to favor a targeted group of n < N students that we will call the minority students and who belong to the set I^m ⊂ I with |I^m| = n. We will also refer to the set of majority students as I^M = I \ I^m. This group of minority students is defined prior to the report of any list of preferences based on some exogenous criteria. For instance, we can keep in mind the case of the boursiers students in Paris: their status is solely based on the income status of their household. Similar to Kojima [2012], we focus our analysis on an unique group of minority students. [14] We can distinguish three types of affirmative action policies in the literature: the Hard-Bounds quotas (HB) affirmative action policies, the Priority-Based (PB) affirmative action policies and a third one proposed by Ehlers et al. [2014] and Hafalir, Yenmez and Yildirim [2013], the Soft-Bounds quotas (SB) affirmative action policies.

22 HB policies. Let m = (m₁,..., m_M ) be a vector of quotas. Each coordinate m_k represents the number of seats that the school c_k ∈ C has to reserve to minority students. Given the vector of quotas m, we impose an additional constraint: for any matching equation im1 , i.e. the m_c seats of school c are reserved for minority students only. To incorporate such type of constraints into DA one has to define an alternative notion of stability. A matching μ is HB-stable iff ∀i ∈ I:

μ (i) ≻_i ∅. [15]
if c_k ≻_i μ (i), either:
1. |μ (c_k ) | = q_k and i
2. and we have i′ ≻_ck i.

24 Condition (2b) is now added. It imposes that a majority student cannot claim the reserved seat of a minority one even if the latter has a lower priority than him. The former can only claim the open seats that are not reserved. [16] With this new stability notion, it is easy to redefine the DA algorithm: we modify the way schools reject majority students. At a given step where a school fills all its quota of minority students and the other seats with majority ones, when an additional majority student applies to it, the school only compares him with the other majority students but not with the minority ones; even if some of them have a lower priority. The formal description, can be found in Kojima [2012]. Kominers and Sönmez [2013] reported that Chicago had some seats reserved for certain types of students.

25 PB policies. To help minority students to obtain more preferred schools, one can increase their priority ranking in some schools. A priority-based affirmative action policy is the change of the tuple T = ⟨ I, C, q, ≻_I, ≻_C ⟩ into a tuple T ′ = ⟨I, C, q, ≻_I, ≻′_C ⟩ where ∀c ∈ C:

if i, i′ ∈ I^M or i, i′ ∈ I^m, then
if i ∈ I^m and i′ ∈ I^M, then

27 A priority based affirmative action policy keeps the same ordinal ranking between the members of the same group and weakly increases minority students in the ranking of some schools. Here, the definition of stability remains the same and the standard version of DA can be used with these new priorities. For example, boursiers students in Paris, as we described, are an example of such policy.

28 SB policies. Ehlers et al. [2014] introduced, the notion of Soft-Bounds. A HB policy imposes strong constraints on the way that schools accept or reject students along the DA algorithm. Hafalir, Yenmez and Yildirim [2013] used such notion in the same framework than ours, i.e. with only one group of minority students. The constraints imposed by the quotas can lead to important welfare losses, especially for majority students. The idea is simple: if a seat in a school is reserved for minority students only and that none of them apply to it, then majority students are still rejected from this school and the seat remains empty. A SB affirmative action policy takes the same vector of quotas m = (m₁,..., m_M ) but interprets it differently. First, it does not impose any additional constraint on the feasibility of any matching. It just defines a new notion of stability: a matching μ is SB-stable iff ∀i ∈ I, if c_k ≻_i μ (i), then |μ (c_k ) | = q_k and either:

i ∈ I^m and .
i ∈ I^M, |μ (c_k ) ∩ I^m| ≤ m_k and.
i ∈ I^M, |μ (c_k ) ∩ I^m| > m_k and

30 This new definition allows to differentiate between the case where the school reaches its quota and where it does not. Now, a majority student has “more blocking power” once the school fills its quota. One can redefine the DA mechanism in allowing the priorities of the schools to change dynamically along the algorithm. If a school has a SB quota, it starts by accepting minority students applying to it until it reaches its quota and then accepts or rejects students according to its initial priority ranking. Majority students can still be accepted by the school even if the latter has not reached its quota. Quotas are flexible and take into account the process of applications under DA which are driven by the students’ preferences. The details of this new version of DA can be found in Hafalir, Yenmez and Yildirim [2013].

2.2. Main results and impossibilities of the previous literature

31 To assess the effects of affirmative action policies, we follow Kojima [2012]. A School Choice Problem T ′ has a stronger affirmative action policy than another problem T if:

32 For HB and SB policies. T = ⟨ I, C, q, m, ≻_I, ≻_C ⟩ and T ′ = ⟨ I, C, q, m′, ≻_I, ≻_C ⟩ with m′ > m. [17]

33 For PB policies. T ′ is the tuple obtained with a PB policy, as earlier defined, over T, i.e. minority students are ranked higher in the priority ranking of some schools.

34 For the three types of policies, we just strengthen the tools that each policy uses to favor minority students. A matching μ ′ is Pareto inferior for I ′ to a matching μ, where I ′⊂ I if ∀i ∈ I ′, we have μ (i) ≽_i μ ′ (i) and strictly for some i ∈ I ′ . With these notions, we can state the main property in Kojima [2012]: a matching mechanism ϕ respects the spirit of affirmative action if, for any School Choice Problem, a stronger affirmative action policy never leads to a matching that is Pareto inferior for I^m to the matching obtained before the reinforcement of the policy. With this definition, the goal is to exclude situations under which the policy hurts the minority students without improving any of them. Since he was interested in impossibility results, he excluded situations where the policy hurts some minority students but succeeds to improve others.

35 Kojima [2012] provided examples to show that stable mechanisms, as well as the TTC mechanism, do not respect the spirit of affirmative action policies. His results are full domain impossibility results with respect to preference and priority profiles. They apply to all stable mechanisms, in particular DA. The interested reader can refer to Kojima [2012] for the counter example concerning HB policies and to Hafalir, Yenmez and Yildirim [2013] for a counter example concerning SB policies. The main intuition is the following: reinforcing the policy can lead to the rejection of a majority student who will trigger a sequence of rejections that ends up hurting all the minority students. Recently, Dogan [2016] characterized the situations under which a reinforcement of the policy can hurt minority students without benefiting any. He proposed a modification of the policies to identify minority students who would never benefit from a reinforcement of the policy but who would hurt the other minority students. In implementing his proposed policy, one can be sure that at least one minority student is strictly better-off. In the framework of aligned preferences for the students, Proposition 1 provides an ex-post result for any PB policy and shows that if the matching changes after the reinforcement of the policy, then at least one minority student will obtain a strictly preferred school. So in such framework, DA respects the spirit of affirmative actions as defined earlier. We use a superscript a (resp. b) to denote the matching obtained after (resp. before) the policy.

36 Proposition 1. Under a priority based affirmative action with the same ordinal preferences for students. Either μ^a (i) = μ^b (i) ∀i ∈ I or ∃i ∈ I^m s.t μ^a(i) ≻_i μ^b(i).

37 We relegate the proof to Section A of the Appendix. In fact, in the case of the same ordinal preferences, it is well known that there is a unique stable matching. Proposition 1 can also be applied to other stable mechanisms than DA. However, this is the only positive result that we can hope in this domain of preferences. The notion of respecting the spirit of affirmative actions becomes very weak if one is looking for positive results. Indeed the following example shows that it is possible for a policy to improve only one minority student while making all the other ones strictly worse-off:

38 Example 1. There are 6 schools with one seat each and 6 students. All students agree on the ranking of the schools so that ∀i ∈ I, k < k ′ ⇔ c_k ≻_i c_k_′. Priorities of the schools are given by:

≻_c₁ : i₁^M, i₁^m, i₂^M, i₃^M, i₂^m, i₃^m
≻_c₂ : i₁^m, i₃^M, i₁^M, i₂^M, i₂^m, i₃^m
≻_c₃ : i₁^M, i₂^M, i₃^M, i₁^m, i₂^m, i₃^m
≻_c₄ : i₂^M, i₁^M, i₂^m, i₃^M, i₁^m, i₃^m
≻_c₅ : i₁^M, i₂^M, i₂^m, i₃^m, i₃^M, i₁^m
≻_c₆ : ...

39 Here, the dots mean that priorities can be arbitrary. A superscript M (resp. m) means that the student is a majority (resp. minority) one, and subscripts are the indexes among each subset of students. With these preferences, the unique stable matching is given by: [18]

(^c^{1 c2 c3 c4 c5 c6})
μ=
i₁^M i₁^m i₂^M i₂^m i₃^m i₃^M

40 where each column of the matrix represents a match. Now, we apply a PB policy that gives the following priorities of the schools:

≻ ′c₁ : i₁^m, i₂^m, i₃^m, i₁^M, i₂^M, i₃^M
≻ ′c₂ : i₁^m, i₃^M, i₂^m, i₃^m, i₁^M, i₂^M
≻ ′c₃ : i₁^M, i₁^m, i₂^m, i₃^m, i₂^M, i₃^M
≻ ′c₄ : i₂^M, i₂^m, i₁^m, i₃^m, i₁^M, i₃^M
≻ ′c₅ : i₂^m, i₃^m, i₁^m, i₁^m, i₂^M, i₃^M
≻ ′c₆ : ...

41 The unique stable matching with these preferences is given by:

(^c^{1 c2 c3 c4 c5 c6})
μ′ =
i₁^m i₃^M i₁^M i₂^M i₂^m i₃^m

42 We can note that equation im14 is better-off and equation im15 are worse-off.

43 It is easy to reproduce this example in a many-to-one matching problem where schools can have more than one seat. In order to obtain positive results, we will now focus on the notion of Pareto-dominance rather than Pareto-inferiority. A matching μ ′ Pareto dominates for I ′ another matching μ, with I ′ ⊂ I iff ∀i ∈ I ′, μ ′ (i) ≽_i μ (i) and strictly for some.

3. Aligned preferences, interim-welfare and affirmative action policies

3.1. Stronger affirmative action policies

44 We adopt the same environment as in Abdulkadiroglu, Che and Yasuda [2011] to study affirmative action policies. For simplicity, we assume that all the schools have the same capacity of q > 0. We also assume that there are enough seats for all the students, i.e. Mq = N. We consider an environment of aligned preferences so that students all agree on the ordinal ranking of the schools. Without loss of generality, we assume that ∀i ∈ I if k < k ′, then c_k ≻_i c_k_′ . Abdulkadiroglu, Che and Yasuda [2011] indeed showed that, in Boston, the submitted preferences of the students are strongly correlated: they simulated completely independent preferences and showed that, in this case, the number of schools that receive more students than their available seats at the first step of the DA algorithm would be much higher than the one observed in the data. So one can see this environment as an approximation of strong correlation. Our simulation results in Section 5 will show that the correlation of the preferences indeed has an important impact on the effectiveness of affirmative action policies. In this framework, schools have coarse priorities. Again, as an extreme case, we assume that schools are completely indifferent between the students and that ties are broken randomly. This tractable environment allows us to formally decompose the effects of a reinforcement of an affirmative action policy. The matching literature distinguishes two types of random tie-breaking rules:

Single Tie Breaker (STB) For each student, a random number is picked, say in the uniform distribution over [0, 1] . Indifferences in the schools are all broken using this number: if a school c is indifferent between students i and i′, then the one with the highest number is ranked above the other one.
Multiple Tie Breaker (MTB) Each school draws for each student a random number, say again from an uniform distribution over [0, 1] . Ties inside this school are broken according to this number. Contrary to the STB rule, the number is school and student specific so that if two different schools are indifferent between the two same students, then the final strict ordering of those students can differ between the two schools.

46 In the aforementioned setting, with aligned preferences and completely indifferent schools, it is worth noting that, in DA, the two methods are equivalent. Indeed, only the q first ranked students in c₁ will be assigned to it, then the q first ranked students among the remaining students at school c₂ and so on. The DA algorithm becomes easily tractable: at each step, all the remaining students apply to the same school and, once some are rejected, they all apply next to the same school and so on. The acceptance decision of a school at each step is now definitive since there will be no additional applicant at later steps. A careful reader can note that, in this environment, DA is equivalent to the well-known TTC algorithm and thus that the induced matching is also Pareto-efficient for the students. [19]

47 Each student i ∈ I evaluates school c_k ∈ C according to a vNM cardinal utility u_i (c_k ). Since students all agree on the ordinal ranking: ∀i ∈ I, if k < k ′ then u_i (c_k ) > u_i (c_k _′ ). Students can still differ in their cardinal values i.e. can have different intensities of preferences. Since, once they submit their preferences to the procedure, students do not know their ranking in the school, they will use expected utilities. [20]

48 We now have to define an affirmative action policy in this framework. As before, there is a vector of quotas m = (m₁,..., m_M ) s.t. the coordinate m_k ≤ q is the number of prioritized seats in school c_k. If m_k > 0, then school c_k has to prioritize m_k of its seats for minority students. Since schools are indifferent between all students and that preferences are aligned, this policy has several interpretations. For minority students, HB or SB policies are identical in this setting since all the students apply to the same school at each step so that the decision of a school with a prioritized seat will be the same under both policies: it will randomly pick one of the minority students applying to it. However, for majority students, the two policies are different: if all the minority students have been accepted at a prior step, then under a HB policy, the prioritized seat will remain empty even if a majority student applies to it. Since we focus on the welfare of minority students, we do not distinguish between the two policies. For a minority student, a priority vector m induces a lottery L (m) over the schools with the probabilities to be assigned to each school, i.e. L (m) = (p^m (c₁ ), ..., p^m (c_M )) where p^m (c_k ) is the probability to be matched with school c_k when the priority vector is m. [21] Note that if m = (0,..., 0), then L (m) is just the uniform distribution where equation im16  [22] For a priority vector m, a stronger affirmative action à la Kojima defines a new vector m′ s.t. m′ > m. We can now state our main result. To ease the notations and intuitions, we assume a one-to-one framework, i.e. where there are the same number of schools than the number students and where each school has a unique seat. This statement is without loss of generality and the argument can easily be extended when capacities are greater than one. In a one-to-one setting, a priority vector is defined by m ∈ { 0, 1 }^N. The proof allows us to decompose two effects of a reinforcement of a policy: a direct and an indirect one. Prioritizing a seat in a school increases the probability to be assigned to it for a minority student, this is the direct effect. However, if the student is being rejected by the school, his conditional expected utility is higher than before the reinforcement of the policy: this is the indirect effect.

49 Proposition 2. Take two priority vectors m and m′ s.t. equation im17 and equation im18 . Then, for both HB and SB policies, either ∀i ∈ I^m, Eu_i (L (m′)) = Eu_i (L (m)) or ∀i ∈ I^m, Eu_i (L (m′)) > Eu_i (L (m)).

50 Proof. The proof is relegated to Section B of the Appendix.

51 Since preferences are aligned, students will all apply to the same school at each step of the algorithm so that we can sequentially compute the conditional expected utility of a minority student. Since each school is indifferent between all students, it will randomly pick a student among those who are applying to it. If the school c_k is s.t. m_k = 1, it is forced to restrict the support of its distribution to minority students if at least one of them is applying to it so that only the number of minority students applying to it matters. If m_k = 0, then only the total number of students applying is important and the assignment probability of a minority students is independent of the number of minority students among the applicants. The proof considers two vectors m and m′ as in the statement of Proposition 2, i.e. m′ prioritize the seat of one school that was not prioritized under m. It starts to show that the probability to apply to that newly prioritized school, i.e. to be rejected from schools strictly preferred to it, is the same between the two vectors. Then, under the vector m′, when a minority student applies to that school, he now only competes with the applying minority students at that step rather than all the applicants like it was the case under m. Since he is now competing with fewer students, his probability to be assigned to this school increases: this is the direct effect of the policy. To finish the proof, one has then to show that the expected utility of a minority student conditional on being rejected from that school is higher under m′ than under m. But even if the minority student is rejected from that school, we are now sure that, under m′, the latter school has accepted for sure a minority student so that the number of remaining minority students has decreased by one at the next step of DA. But before, under m, the seat was not prioritized and there was still a chance that the school accepted a majority student so that the number of remaining minority students would have remained the same at the next step. Since m′ and m are equal for the remaining schools, one just has to show that the conditional expected utility of a minority student at the beginning of a step of DA is always higher when there are fewer minority students left at that step. When applying to a school that does not prioritize its seat, the probability to be assigned to it does not depend on the number of remaining minority students. However, when applying to a prioritized school, the probability of being assigned to it is always higher when there are fewer minority students applying to it since less students compete for the seat. So overall, the expected utility of a minority student, conditional on being rejected from the newly prioritized school is higher under m′ than under m: this is the indirect effect of the policy. The proof formalizes the above intuitions. [23]

52 When one studies the expected utility of a minority student under aligned preferences, it is irrelevant whether the affirmative action policy is a SB or HB policy. Indeed, for a prioritized seat of a school, the two policies only differ when no minority student applies to that school. In that case, the SB policy allows any majority student applying to the school to be assigned to it whereas the HB policy leaves the seat empty. But, if no minority student is applying to a school, it means that they all have been assigned to a more preferred school at prior steps. So the acceptance decision of that school does not influence their assignment since the rejected students, because of aligned preferences, will not apply again to these preferred schools.

53 With Proposition 2 in hands, we can deduce the following corollary:

54 Corollary 1. Take two priority vectors m and m′ s.t. m′ ≥ m, then either ∀i ∈ I^m, Eu_i (L (m′)) = Eu_i (L (m)) or ∀i ∈ I^m, Eu_i (L (m′)) > Eu_i (L (m)).

55 Indeed, the difference between Proposition 2 and the above corollary is that the former only prioritizes the seat of one school between m and m′ and the latter prioritizes the seat of several schools at the same time. But since the vector m in the statement of Proposition 2 is arbitrary, one can still decompose the prioritization of the seat in several schools into sequences of prioritizations of the seat of only one school. Each time one prioritizes the seat in only one school, Proposition 2 tells us that the minority students are all interim better-off so that the statement of Corollary 1 easily follows.

56 Note that it is perfectly in Kojima’s ideas of a stronger affirmative action policy. In our environment, stronger affirmative action policies can only benefit to minority students from an interim-welfare perspective. It is stronger than the pure respect of the spirit of affirmative actions as defined in Kojima [2012] since no minority student can be hurt by a stronger policy. Note that our argument does not rely on the vNM cardinal utilities. Using the well-known characterization of stochastic dominance, one can also immediately deduce the following corollary:

57 Corollary 2. The distribution L (m′) first order stochastically dominates the distribution L (m). [24]

58 The one-to-one framework of the proof is not restrictive when we have to study the effects of a stronger policy and the arguments can be easily extended to the case where schools have multiple seats without adding more intuition.

59 As mentioned, the priority vector can be interpreted either as a HB or a SB policy. It is not hard to see that here, if we compute the expected utility of the majority students, we obtain the reverse result: the stronger the affirmative action policy, the worse the majority students are. Kojima [2012] provided an example where a stronger affirmative action policy can, ex-post, lead to all students being weakly better-off and some strictly. We can see that it is not the case here: the affirmative action policy is always at the detriment of the majority students in terms of interim-welfare. However, for majority students, we can find exactly the same type of results between an HB and a SB policy as the ones in Hafalir, Yenmez and Yildirim [2013]: if we fix the priority vector m, then a SB policy makes every majority student interim better-off compared to the same quotas under a HB policy. As in the ex-post analysis of Hafalir, Yenmez and Yildirim [2013], the SB policy is less constraining than the HB one.

60 Concerning PB affirmative action policies, the policy needs to respect an anonymity property with respect to the minority students, i.e. it should not discriminate between them. Indeed, in general, a PB policy just selects the identity of one particular minority student that is improved in the priority ordering of some schools. If, for some reason, the policy does not improve a minority student, then the same result as the one for majority students will apply to him: he will be interim worse-off. We can think of different types of non-anonymous policies where we increase the ranking of one minority student, say i, in one school, say c_k, and the one of another minority student, say i′, in another less preferred school, c_k_′ with k ′ > k. It is clear that the first student i will be interim better-off than without any policy since he will never be rejected by c_k. However, for student i′, the result depends on his vNM cardinal utilities. Even if we prioritize him in school c_k_′ , we also decrease his chances to be assigned to school c_k. This example also highlights the problem that one can face in the presence of multiple groups of minority students. If there are several types of students that the policy-maker wants to make better-off, then these different goals can lead to some groups being worse-off under a policy. In all cases, results are likely to depend on the particular vNM cardinal utilities which is not very desirable since they are difficult to precisely elicit.

3.2. Welfare effects of precedence orders.

61 A many-to-one environment can lead to the study of other types of policies. Indeed, if there are multiple seats in each school, one can see that if we wanted to apply the same sequential construction as in the proof of Proposition 2, then we would have to decide in which order to fill the prioritized seats of a given school along the algorithm.

62 This idea was first emphasized by Dur et al. [2017] who showed that the order in which the prioritized seats are filled along the algorithm can affect the resulting matching. In their paper, they adopted a general framework introduced by Kominers and Sönmez [2013] which was inspired by the cadet-branch matching model of Sönmez and Switzer [2013]. The model allows each seat of a given school to have its own priority ordering. Indeed, in prioritizing some seats in a school, we introduce heterogeneity between them. First, one has to slightly change the definition of a School Choice Problem. The sets I, C, the vector q, the preferences of the students in the vector ≻_I and our priority vector m remain the same. We additionally introduce:

The set S^k of seats (or also called slots) of school c_k ∈ C. A particular slot will be denoted by s and, in our many-to-one model where all schools have the same capacities, we have that |S^k| = q.
The vector ▷ where each coordinate ▷_k is the precedence order of school c_k ∈ C i.e. a linear order over its slots S^k that determines in which order the slots are filled along the matching procedure. We will refer to as being the l-th ranked slot of school c_k according to ▷_k.
Each slot s ∈ S^k is embedded with a priority ordering π_s over the set of students I. The interpretation is exactly the same as the priorities of the schools in our previous setting except that, now, seats of a given school can have different priorities. We will distinguish between two types of seats: open ones, that are completely indifferent between the students and the prioritized seats that rank all the minority students before the majority ones but are still indifferent between the students inside the same group. [25]

64 The probability to be matched to a school now depends on both the number of prioritized seats, given by the vector m, and the precedence orders of the schools, given by the vector ▷. The induced distribution will be denoted L (m, ▷). We can now state the following result:

65 Proposition 3. Let m be a priority vector with m_k * < q and ▷ be a vector of precedence orders s.t. ∃l < q where equation im20 with equation im21 being a prioritized slot and equation im22 an open slot. Let ▷ ′ be a new precedence order that switches the prioritized slot s_l^k^*with the open slot equation im23 , i.e. equation im24 Then ∀i ∈ I^m: Eu_i (l (m, ▷ ′)) > Eu_i (L (m, ▷)).

66 Proof. The proof is relegated to Section C of the Appendix

67 In decreasing the ranking of the prioritized slot in the precedence order, we allow the minority students to be matched to some open slots before the prioritized one. If the student “looses” his chance for the open slot, then the prioritized slot will secure him a higher match probability. All these slots belong to the same school and so the minority student is indifferent between an open or a prioritized seat. This difference allows us to change the precedence order to increase his expected utility. If the prioritized slot is the first to be filled, then the minority student will compete with all the other minority students applying to the school. However, if the slot is ranked below an open slot in the precedence order, then a minority student can still be assigned to the open slot and the competition for the prioritized seat will decrease: it increases the probability to be assigned to the school.

68 In Dur et al. [2017], the goal is to study the effect of the precedence orders on walk-zones priorities at schools in order to increase the number of students assigned to their walk-zone school: it is a distributional analysis. As said, our analysis is welfare oriented and we have shown here that their precedence order can also be a policy tool to improve the welfare of minority students.

4. Further interim and ex-post results

4.1. Can we relax the assumptions?

69 We provide two examples to show that Proposition 2 does not hold if we relax one of our two main assumptions: i) aligned preferences for the students and ii) the complete indifference of the schools. Example 2 relaxes the assumption that students have aligned preferences. In that case, a reinforcement of the policy leads to the rejection of a majority student who will then “more often” claim the seat of a minority student in a less preferred school, decreasing the expected utility of the latter. We can note that the policy hurts the student because it increases his ranking in a school that he prefers the least.

70 Example 2. There are 3 schools, c₁, c₂, c₃ and 3 students with 2 minority students: equation im25 , equation im26 i^M. Their cardinal utilities are given by:

			i^M
c₁	4	0	4
c₂	1	1	0
c₃	0	4	1

71 We have 6 possible realizations of priorities for each school which are given by:

73 Without any policy, all these rankings are equally likely in all the schools, so we have 216 possible realizations of priority vectors for the schools. We will focus on the expected utility of student equation im36 so that we will omit the subscript: Eu will denote the expected utility of equation im37 and μ ( r₁, r_,, r₃ ) will be the school to which he is matched when the rankings of the schools c₁, c₂ and c₃ are respectively given by r₁, r₂, r₃ ∈ { 1, 2, 3, 4, 5, 6 }. Each integer denotes the corresponding ranking in the above list. We can now find all the possible schools to which the student is matched:

First, if r ₃ ∈ { 3, 4 }, then he will be ranked first by his most preferred school and so will always be matched to it i.e. μ (., ., r₃ ) = c₃ where the dots mean that the priorities of the other schools are arbitrary. For each of these “dots” there are 6 possible rankings, so there are 72 possible vectors of priorities under which the student is ranked first by school c₃.
If r ₁ ∈ { 1, 2, 3 }, then, at the first step of the DA algorithm,will reject i^M who will then apply to c₃ and will not rejectin c₃ if the priority ranking of c₃ is given by 1. Note that here, we do not count the cases where the priority ranking is given by 3, 4 since we already counted these cases above. So, μ (r₁, ., 1) = 3. Again, since there are 6 possible priority rankings for the dot, we have a total of 18 vectors in this case.
Now, if the priority ranking of c ₁ is given by r₁ ∈ { 4, 5, 6 }, thenwill be rejected by i^M in c₁ at the first step of DA, will apply to c₂ and will be accepted. So to not count the cases that we already counted in the first case, we have μ (r₁, ., r₃ ) = c₃, where r₁ ∈ {4, 5, 6} and r₃ ∈ {1, 2, 5, 6} which gives a total of 72 vectors.
To finish, when r ₁ ∈ { 1, 2, 3 }, we have seen that i^M will be rejected at the first step of DA and so will be able to rejectin c₃ if the priority ranking in that school is given by r₃ ∈ { 2, 5, 6 } so μ (r₁, ., r₃ ) = c₂. There are 54 possible vectors.

75 If we sum the number of vectors in the three first cases, we will find 162 possible vectors of priority rankings where equation im42 is matched to his most preferred school, c₃ and 54 vectors where he is matched to c₂. There is indeed a total of 216 cases. We can now calculate the expected utility of student equation im43 before the affirmative action policy:

b 1 13
Eu = 216 (54 × 1 + 162 × 4) = 4̄ = 3.25

76 Now, assume that we prioritize the seat of school c ₁. In that case, it is equivalent to always rank the majority student the last in the ranking of that school, i.e. restricting the possible priorities to r ₁ ∈ { 1, 3 }. There are now a total of 72 possible vectors of priorities for the schools. i^M can never be matched to school c₁ so he will apply to school c₃ and will have a probability of one half to reject equation im45 (36 possible vectors) who will then be matched to school c₂. So his expected utility is now given by:

Eu^a = 12 (1 + 4) = 2.5

77 Which is lower than before the policy: he is interim worse-off. The policy induces a systematic rejection of the majority student who is the only competitor at school c ₃ for equation im47 since it is the worst school for the other minority student. Before the policy, allowing equation im48 to be rejected allowed i^M to not claim the seat at c₃ and so to not reject equation im49 . The reader can note that the argument does not depend on the cardinal utility values: he will always be interim worse-off even if c₂ is slightly less preferred to c₃.

78 Example 3 relaxes the assumption of the absence of priorities for the schools. The extreme case is obviously that priorities are strict so that Kojima [2012]’s counter examples will apply. However, we want to show that even if we “slightly” depart from our framework, the result still fails. We allow schools to still be indifferent between students and we evaluate minority students’ welfare in expected utility terms.

79 Example 3. There are 3 schools, each with 2 seats and 6 students with half minority students. Students all agree on the ranking of the schools: c₁, c₂, c₃. Priorities in schools are not complete and are given by ordered subsets of students:

≻_c : {i₁^m, i₂^m, i₁^M} {i₃^m, i₂^M, i₃^M}
1
≻_c : { i₁^M, i₂^M, i₁^M } { i₃^M, i₃^m } { i₁^m, i₂^m }
2
≻_c₃ : ...

80 The dots mean that the priorities are arbitrary. Each school is indifferent between the students belonging to the same set, ties are broken randomly and uniformly with a MTB rule.

81 Take the minority student equation im51 and let u_k be his vNM cardinal utility for school c_k. Under the aforementioned priorities, it is easy to compute his expected utility:

b4 8
Eu m = × u + × u
i₃ 12 2 12 3

82 Now it is easy to see that if we increase the priority of both minority students equation im53 and equation im54 , student equation im55 is ex ante worse-off since equation im56 will be rejected. In the extreme case, suppose that equation im57 and equation im58 have a higher priority than equation im59 in school c ₁, then equation im60 will be matched to school c ₃ with probability one.

83 The examples showed that even if we derive “slightly” from our previous framework, it is possible that a stronger affirmative action policy hurts some minority students from an interim-welfare perspective. When priorities or preferences can differ, the assignments occurring during the algorithm are not definitive anymore since a rejected student can lead to the rejection of another one who has been assigned to a school at a prior step. It is exactly the idea that we applied: the policy can lead to the rejection of a majority student, who will in turn reject a minority one, worsening its match compare to the situation without any policy.

84 The two examples raise an important issue: an affirmative action policy can hurt the group of students that it is supposed to help, [26] even with simple structures of preferences and priorities. However, correlation between students’ preferences seems to be a driving force for the effectiveness of the policy. In Section 5, we provide simulations to support this claim.

4.2. Can we give more ex-post results?

85 If one is seeking positive ex-post results for PB policies, then only extreme policies can ensure to always help minority students. [27] Formally, a Maximal Priority Based (PB) affirmative action policy transforms the priority ordering of each school c ∈ C from equation im61 to equation im62 s.t.:

∀i, i′ ∈ I^m or
if i′ ∈ I^m and i′ ∈ I^M, then

87 Then, we can obtain the following result:

88 Proposition 4. Under DA student or college proposing, a maximal PB affirmative action policy makes all minority students weakly better-off.

89 This property can be viewed as a direct corollary of Theorem 2.24 in Roth and Sotomayor [1992]: in the case of a one-to-one problem, if we remove some agents from one side of the market – in our case, the majority students – then all the remaining agents – the minority students – cannot be worse-off. It is exactly what a maximal PB policy does: from the perspective of the minority students, moving all them at the top of the ranking of each school “deletes” the majority students from the market. [28] If the PB policy is not maximal, it is easy to find a counter example where at least one minority student is strictly worse-off. With these two propositions, the following proposition easily follows:

90 Proposition 5. In the DA student and college proposing, when there are no priorities in schools and ties are broken randomly with a STB or MTB rule, a maximal PB affirmative action policy always makes every minority student strictly interim better-off. [29]

5. Simulations

91 This section introduces our simulation framework and its results. Up to now, we have shown that:

Ex-post results on affirmative action policies show that affirmative action policies can hurt a significant number of minority students even in the case where all students have the same preferences.
With an interim-welfare approach when schools are indifferent, we can still obtain interim-welfare losses if schools are not completely indifferent or if students can have different preferences.
In Abdulkadiroglu, Che and Yasuda [2011]’s environment where students all agree on the ranking of the schools and where schools are completely indifferent, stronger affirmative action policies always increase the interim-welfare of minority students.

93 We want to assess the effectiveness of affirmative action policies from an interim-welfare perspective when one relaxes our assumptions of: i) aligned preferences and ii) indifference of the schools. Note that, when one assumes that schools are not completely indifferent between students, there are two dimensions to consider: the number of indifferences and the correlation between schools’ rankings. To precisely evaluate the impact of each assumption, our simulations study three settings:

Schools are still completely indifferent between all students and break ties using a MTB or STB rule but we allow the students to have different preferences over the schools. We let the correlation between students’ preferences vary. These results are discussed in Section 5.1 and the figures are reported in Section D of the Appendix. The main results are that:
- The less correlated the preferences, the more minority students are hurt at an interim stage by an affirmative action policy.
- A STB rule lead to more minority students hurt by a policy than a MTB one.
Students have the same ordinal preferences but we allow the schools to have ordered classes of indifferences for the students, ties inside each class are broken using a MTB or STB rule. We let the number of classes vary but keep the correlation between the orderings of the classes by the schools fixed. These results are discussed in Section 5.2 and the figures are reported in Section D of the Appendix. The results are:
- The more indifference classes, the more minority students are hurt at an interim stage by an affirmative action policy.
- A STB rule lead to more minority students hurt by a policy than a MTB one.
Schools’ number of classes is fixed and we let the correlation between students’ preferences vary. The figures are reported at the end of Section D of the Appendix.
- The effect of the correlation of students’ preferences is non monotonic and has an inverted U-shape.
- A STB rule lead to more minority students hurt by a policy than a MTB one.

95 Our simulation framework presented below allows for many different combinations of parameters that can be used for future research. In our simulations’ results, we focus only on a subset of them and let some of the parameters fixed.

96 To generate the data, we proceed as follows: we fix 500 students with 125 minority students. [30] There are 50 schools with 10 seats each. The utility of a student i for school c_k, is determined by two random variables. [31] The first one, equation im65 is fixed for school c_k and drawn in an uniform distribution over (0, 1). This number is common for all the students, it captures the correlated part of the students’ preferences. The second one, equation im66 is also picked in a uniform distribution over (0, 1) but is drawn for each student-school pair. The utility of student i for school c_k is defined by:

u_i (c_k ) = β Z_ick + (1 − β) Z_ck [1]

97 The parameter β controls the correlation between students’ preferences: if it is equal to 1, then the preferences are completely independent and if it is equal to 0, then the preferences of all the students are the same. These cardinal utilities are used to calculate the expected utility of each student.

98 To generate schools’ priorities, we use a point system s.t. students with higher points are ranked higher than those with lower points. To simulate them, we proceed as follows. First, we consider L indifference classes for the students: I₁,..., I_L and randomly assign the students in these classes. When L = 1, then all the schools are completely indifferent between all the students so that we maintain the same assumption as in our theoretical analysis. If L tends to infinity then we tend to strict priority orderings and thus we come back to the standard ex-post simulations of the literature as in Hafalir, Yenmez and Yildirim [2013]. For instance, in the French Affelnet point system, one can see an indifference class as a combination of characteristics s.t. all the students with these characteristics would obtain the same number of points in each school (but these points can differ across schools). We assume however that students’ are uniformly distributed in the different classes. In the Affelnet procedure, low income students tend have lower grades and so tend to fall into lower ranked classes and to concentrate into the same class. Our goal is not to provide exhaustive simulation results but to highlight possible trends once one relaxes our assumptions. Simulations of the complete Affelnet procedure, possibly calibrated with data, would be of interest and is left for future research.

99 For each school c, the points it assigns to students of the class I_ℓ:

v_c (I_ℓ ) = 2 × (10 × ⎣αY_ℓc + (1 − α) Y_ℓ⎦)

100 Similarly to students’ preferences, a school starts, for each I_ℓ, to assign a value Y_ℓ that is common for all schools and drawn in an uniform distribution over (0, 1). It captures the correlation of schools’ points between classes of students. For instance, classes representing students with higher grades will tend to be ranked higher by all schools. The second number, Y_ℓc, also drawn in an uniform distribution over (0, 1) is drawn for each class-school pair. The parameter α controls the correlation between the points: if α = 0 then all the schools order the students from two different classes in the same way. If α = 1, this ordering between classes is completely independent and uniform. The rounding and the multiplications by 10 and 2 are here for technical purposes: they ensure that, once one tie-breaks the indifferences and performs an affirmative action policy, the ranking between classes and between any two minority or majority students remains the same.

101 If P is the 500 × 10 matrix where P (i, j) represents the priority points of student i in school j before any tie-breaking. So, for ℓ ∈ {1,..., L}, if i ∈ I_ℓ then for any school j, we define:

P (i, j) = v_cj (ℓ) if i ∈ I_ℓ

102 Next, to define P̃, the point matrix after the tie-break between students belonging to the same class, we consider two possible rules:

103

MTB: ∀i, ∀j, we pick a number r_ij according to the uniform distribution U_{[0, 1]} and define .
STB: ∀i, we pick a number r_i according to the uniform distribution U_[0,1] and define  [32]

104 The matrix P̃ is the priority matrix before the affirmative action policy is performed. We simulate a particular type of affirmative action: we fix a number m of schools and define the priority matrix P̃′ after the affirmative action policy as follows:

P_i′_j = {_P^P̃_iⁱ_j^j⁺¹_o^if_thⁱ_e^≤_rw¹_i²_s⁵_e^{and j ≤ m}

105 The interpretation is that the m schools c_j with j ≤ m rank all the minority students of a given class above the majority students belonging to the same class. [33] Note that, in our theoretical framework, i.e. L = 1, it is equivalent to set m_j = q. [34]

106 For a fixed number of classes L, to calculate the expected utilities, we proceed as follows: once utilities of the students, their distribution in classes and the points of the schools for each class are fixed, we iterate 200 times the two tie-breaking rules of the schools’ priorities. Each iteration gives a realization of the priorities of the schools. We apply the DA algorithm to find the corresponding matching before the policy and we store the vNM utility of the school assigned to each student. Then, for the same realization of the priorities of the schools, we perform the above affirmative action policy. We again use the DA algorithm to determine the resulting matching after the policy and store the vNM utilities of the students. With 200 iterations of tie-breaking, we obtain 400 utility values for each tie-breaking rule: the ones of the assignment before the policy and the ones after the policy. To compute an estimate of the expected utilities of the students, we average the stored vNM utilities over the 200 tie-break iterations. [35] To finish, we iterate the above procedure 500 times in drawing new utilities for the students, their distribution in classes and the points of the schools for each class. We also repeat the procedure for 5 values of m, the number of prioritized schools, ranging from 10 to 50 with increments of 10. When L > 1, we also fix the correlation parameter α for the schools’ points for each class to 0.5. [36]

5.1. Indifferent schools and students’ preferences variations

107 This section considers the results when schools are all indifferent (L = 1) and the preferences’ correlation parameter β varies from 0 to 1 with increments of 0.1.

108 First, we compare the average number of minority students who are interim worse-off after the affirmative action policy. Figure 1 reports the results when we vary β, the correlation between students’ preferences and m, the number of prioritized schools. When β = 0, then, in line with Proposition 2, no minority student can be interim worse-off after any affirmative action policy. The figure supports that the more the correlation between students’ preferences, the less the number of minority students hurt by the policy. [37] The number of worse-off students can be significant. For instance, with 10 prioritized schools (m = 10) and completely independent preferences (β = 1), a MTB policy can hurt in average 23.94 minority students, so around 20 % of them. We can also notice that the STB tie-breaking rule tends to hurt more minority students than the MTB rule. In the matching literature, see for instance Abdulkadiroglu, Pathak and Roth [2009] or Abdulkadiroglu, Che and Yasuda [2015], it has been shown that a STB rule performs better in terms of students’ welfare than a MTB rule. In our setting, when focusing on the number of minority students not hurt in expected utility terms after an affirmative action policy, the reverse tends to hold. For a minority student, after an affirmative action policy, two effects possibly occur for him: higher chances to be assigned to schools with a higher utility value and, when preferences are not fully aligned, potentially higher chances of being assigned to schools with a lower utility. As in Example 2, the intuition for the latter effect is that some minority students, after the policy, can start to reject other students who then come to compete with other minority students in the school these students had before the policy, potentially rejecting them from it. Once rejected from this school, these minority students will start to apply to schools that they rank lower. But even if these schools lead to lower cardinal vNM utilities, these utilities can still be close to the one they had before the policy so that, overall, this higher probability to be assigned to lower ranked schools is compensated, in expected vNM utilities, by the higher chances to be assigned to higher ranked schools. However, note that, with a STB rule, the more a student is rejected, the higher chances he has to be further rejected. Indeed, since under a STB rule, schools all use the same ordinal ranking, then being rejected by many schools means that the student is likely to ranked at the bottom of this common ranking and so increasing is likelihood to be further rejected. However, under a MTB rule, since each school draw independently its ordering, this is not the case and this student is equally likely to be accepted by a school even conditional on having been rejected by other schools. Hence, under a STB rule, a rejected student will tend to be rejected by more schools so that he will tend to be matched to schools with much lower vNM utilities. The negative effect is thus more likely to dominate, in cardinal terms, the positive effect so that this student is more likely to be interim worse-off under a STB rule. [38]

109 Second, we compare the effects of increasing the number of prioritized schools. Figure 2 shows that the more the number of prioritized schools, the less the affirmative action policy hurts minority students. At the extreme, when all schools are prioritized, i.e. m = 50, Proposition 5 tells us that no minority student can be hurt. The results show that the negative effects of an affirmative action policy when students preferences are less correlated can be partially offset by an increase of the number of prioritized schools. For instance, when β = 1 under a MTB rule, the average number of interim worse-off minority students goes from 23 to 9 when the number of prioritized schools goes from 10 to 20.

110 Now, we want to compare the distributions of the final ranks, noted L (m) in Section 3 with aligned preferences, for a given realization of preferences. Figure 3 shows the cumulative distribution of the ranks for minority students, under the STB rule, once we fix a realization of preferences. For each tie-breaking of the priorities of the schools, we calculate the cumulative distribution of the ranks for minority students. [39] We then average each value of the distribution over the 200 iterations of tie-break. Figure 3a shows that, when m = 0, the cumulative distribution is the one of the uniform distribution. The higher the number of prioritized schools, the more the distribution shifts to the left, increasing the chances of a minority student of being assigned a more preferred school. [40] When preferences are not perfectly correlated anymore, Figure 3b shows that the distributions are not ordered anymore. For instance, increasing the number of prioritized schools from 10 to 20 decreases the number of minority students obtaining a school of rank 5 or higher.

5.2. Same students’ preferences and variations over the number of classes

111 This section reports the results when students have the same ordinal preferences (β = 0). We are mainly interested in comparing the effects of having more or less indifferences on the expected utilities of minority students at the interim stage, prior to any tie-breaking. So we fix the correlation of schools’ priorities to α = 0.5 and only let the number of indifference classes vary with L = 1, 5, 25, 150, 1000. [41] As mentioned, the more classes, the stricter the priority orderings so that, with 1000 possible classes for only 500 students, there are only few ties in schools’ priorities. Second, our goal is also to compare the two different tie-breaking rules, MTB and STB, with respect to their effects on the performance of the affirmative action policies.

112 We provide similar figures as in Section 5.1. Figure 4 reports the average number of minority students interim worse-off after an affirmative action policy when the number of indifference classes increases. For better readability, since the highest value of L is 1000 and the second highest 150, the x-axis values are in logarithmic scale. As mentioned, for T = 1000, this interim analysis is almost equivalent to an ex post one. As in Figure 1, we report the results for different numbers of schools in which the policy is performed. First, similar comparisons between the STB and the MTB rules hold: under a STB rule, an affirmative action policy tends to hurt more minority students than under a MTB one. The higher T, i.e. the less indifferences in the schools’ priorities, the higher the number of minority students hurt by an affirmative action policy. For instance, when T = 1000, an affirmative action policy in 10 schools can hurt in average up to 36 (resp. 31) minority students under a STB (resp. MTB) rule, i.e. 28 % (resp. 24 %) of them. Since minority students are moved at the top of the ranking of their indifference class but the relative ranking across classes remains the same, when T = 1000, these classes tend to contain only few students. So performing an affirmative action policy in m = 10 schools only changes the ranking of very few students in very few schools since classes tend to contain only a few of them. However, these few changes lead to significant losses in terms of minority students welfare.

113 Figure 5 reports the same variables but compares different numbers of schools with prioritized seats for each tie-breaking rule. As in Section 5.1, the higher the number of prioritized schools, the lower the number of minority students who are interim worse-off after the policy. [42]

114 Last, Figure 6 reports the cumulative assignment probabilities of a fixed iteration for different values of m and T under a STB rule. [43] Figure 6a reports similar results as Figure 3a concerning our benchmark setting when students have the same ordinal preferences and schools are completely indifferent. The higher the number of prioritized schools, the more the distribution shifts to the left, i.e. the better the minority students are at the interim stage. However, Figure 6b reports the same distributions when there are T = 25 possible indifference classes. In that case, the effect of reinforcing an affirmative action, i.e. increasing m, does not imply a uniformly “better” distribution for minority students. In Section 5.1, when schools were completely indifferent but students had different ordinal preferences, Figure 3b showed high values of m were unambiguously better for minority students. Once again, when schools were completely indifferent, high values of m implied that minority students were moved at the top of the priority ranking of (almost) all schools which was beneficial for them. However, when schools have ordered classes of indifference, minority students are moved at the top of their class but not of the complete priority ranking. Thus, the effect of reinforcing an affirmative action policy is ambiguous. Indeed, the distributions show that improving the minority students in their tier in all schools, m = 50 does not lead to a “better” assignment distribution for them. For instance, the distribution for m = 30 tends to put a higher probability mass to higher ranks. [44]

6. Conclusion

115 The matching literature emphasized the perverse ex-post effects that an affirmative action policy can have on the welfare of the students that it is intended to help. In this work, we evaluate these policies with an interim-welfare perspective using the framework of aligned preferences with completely indifferent schools. In this setting, an affirmative action policy never hurts the minority students. However, even with an interim-welfare approach, positive results cannot be obtained if one relaxes any of the assumptions. Our simulations showed that these policies tend to be more effective in an environment with a strong correlation between students’ preferences. The number of prioritized seats is also an important tool in order to counterbalance the bad effects that can arise when preferences are not perfectly correlated anymore. They also suggest that the Multiple Tie Breaking rule leads to less minority students being hurt by an affirmative action policy. However, the only positive ex-post result concerns a maximal policy that, in all schools, always rank the minority students higher than the majority ones. Our analysis raised several discussions for the French assignment procedures and for future research:

116 The French assignment procedures. As mentioned, two of the main French assignment procedures, Affelnet for high school students and Parcoursup for university students, use affirmative action policies. First, we would like to highlight that our analysis focused on welfare policy objectives, i.e. when these policies are used to improve the rank of the school assigned to the the minority students. As discussed in the introduction, another possible objective is purely in terms of diversity: the policy maker accepts to potentially assign minority students to a lower ranked school as soon as a certain balance between minority and majority students is respected in the schools. This objective aims at creating social diversity in the schools. Thus, if the French affirmative action policies were designed for the latter goal, our results could not be used to assess their performance and another type of analysis would be needed. [45]

117 For instance, the boursier bonus for low income students in the Affelnet assignment procedure in Paris has been criticized based on diversity concerns. In Paris, in point-system for schools’ priorities, two important criteria are: i) the geographical points for students living in the district of the school and ii) the bonus boursier. [46] The point system implies that students living inside a district are systematically ranked by the schools of that district above the students who do not live inside the district. The bonus boursier is high enough to let any low income student be ranked above any majority student, irrespective of their points for other criteria, inside their living district but not if this student applies to other districts. Thus, this policy does not correspond to a Maximal PB affirmative action policy as studied in Section 4 and perverse ex post welfare effects for the minority students are possible. [47] Fack, Grenet and Benhenda [2014] simulated the impact of deleting the bonus boursier in the priorities of the schools. They note that the bonus allows “boursiers to be more often accepted to their first ranked school”. However, they do not report whether some minority students were hurt by the bonus boursier. One consequence of the bonus has been that some high schools have seen their distribution of low income students change significantly. For instance, the Parisian high school Lycée Turgot, reported that, in 2016, the boursiers students represented 83 % of its incoming students against around 40 % the previous years. This important changes in students’ distributions leaded to critics about creating new “ghettos high schools” (see lemonde.fr [2017] or Libération [2017]). These concerns highlight that even though empirical evidences suggest that the bonus boursier was performing relatively well in terms of ex post welfare, policy makers and parents find the diversity constraints important as well. Our interim analysis suggests that relaxing the ex-post objectives can still achieve welfare objectives in terms of expected utilities while potentially giving more flexibility to achieve diversity constraints.

118 Concerning the Parcoursup quotas for university admissions, the distinctive features of the procedure, e.g. report of unordered lists of preferences, selection process delegated directly to the universities, does not allow us to apply our analysis that uses a fully centralized assignment algorithm such as DA. However, the results in the matching literature cited along our article can be used to warn the policy makers of the use of such quotas if they have in mind ex-post welfare objectives for low income students. Similarly to our discussion for the bouriser bonus for Affelnet, diversity objectives have to be treated with another type of analysis than ours. Moreover, the criteria of selection used by universities being not clearly known, it is hard to tell whether they face important indifference classes to select their applicants and thus, whether our interim analysis can be useful to apply to such context.

119 Future Research. We adopted, in line with the literature, a very conservative approach to evaluate the welfare effects of affirmative action policies. Indeed, we imposed to never decrease any minority student’s expected utility. However, other weaker notions can be used by policy makers. One can for instance focus on the distribution of the ranks of the schools assigned to minority students and compare the distributions before and after the reinforcement of a policy based on first order stochastic dominance. The policy maker can be interested in a good aggregate performance “almost surely”. In our simulations, in average over all the iterations, the distribution after the reinforcement of the policy always stochastically dominates the one before the reinforcement, independently of the correlation between students’ preferences or the indifference classes of the schools. [48] Probabilistic analysis, e.g. random graph techniques, in a large market setting proved to be a powerful tool to analyze such claims. [49] Another approach inspired by this large market literature is to study the asymptotic behavior of the proportion of minority students who are assigned to school with a “significantly” lower utility after the reinforcement of the policy. [50]

120 Last, as discussed, the objectives of the affirmative action policies, notably in France, can be to achieve diversity constraints rather than welfare objectives. If one wants to study diversity constraints, our analysis suggests that taking an interim perspective with respect to the resulting distributions of students in the schools, prior the tie-breaking of the indifferences for the schools’ priorities, can turn existing negative results into positive ones. Moreover, as discussed for the French boursier bonus, an interim analysis can allow to balance the welfare and diversity objectives together and potentially help to design better mechanisms in the future with respect to these two dimensions. The trade-off between the two objectives remains an open question for future research.

This work was part of my Master thesis done at the Paris School of Economics under the supervision of Olivier Tercieux and the review of Laurent Lamy. I would like to thank them for their advice. I would also like to thank two anonymous referees for their helpful comments. I am also grateful for the support from the ERC Grant No. 682417, Frontiers in Design - Frontiers in Mechanism Design: Methodology and Applications. All potential mistakes are mine.

Appendix

A. Proof of Proposition 1

121 We first redefine the DA algorithm in the case where the ordinal preferences of the students are the same. Each step k of the algorithm is now associated with the school c_k. Let I_k be the set of students who are applying at step k, i.e. they are applying to school c_k. Let A_k be the set of students who are accepted by school c_k at step k. Initialize A₀ = ∅:

122

Step 1. I₁ = I, all students apply to c₁ and the q₁ first ranked ones in c₁ are accepted. Define A₁ as being these students and I₂ = I₁\A₁.
Step k. The students in I_k apply to school c_k and the q_k first ranked ones are accepted. Define A_k as being these students and I_k _+ 1 = I_k\A_k.

123 The procedure ends once I_k = ∅ and the unique stable matching is obtained. Clearly, the procedure ends in less than m steps if equation im73 and in M steps otherwise.

124 In the DA algorithm after the affirmative action policy, take the first step where the set of matched students is different than the one during the algorithm before the affirmative action, i.e. where equation im74 . If no such step exists, since equation im75 then the two outcomes are the same: μ^a (i) = μ^b (i) ∀i ∈ I.

125 If this step exists, then all the steps before will match the same sets of students i.e. equation im76 and equation im77 ∀k ′ < k. At step k, since the set of rejected students is the same as before the affirmative action at the step before, then we have equation im78 and, by assumption, equation im79 .

126

First, we cannot have . Indeed, it would mean that the same set of students is matched to school c_k and that more students are matched to it after the policy. But this is possible only if But then, since students in are matched, before the affirmative action, at a later step, they strictly prefer c_k to their matching under μ^b. But if there are empty seats at school c_k then these students can block the matching μ^b, a contradiction since the DA algorithm produces a stable matching.
With the same argument we cannot have .
So necessarily, ∃i, i′ s.t , and .
- If i and i′ are both minority or both majority students, they were be both applying to c_k before the affirmative action and i was rejected so that . But by definition of a priority based affirmative action, the rank between them is preserved after the policy so that But since i′ was matched at a later step, he can block μ^a, a contradiction.
- If i′ ∈ I^m and i ∈ I^M, then i was rejected by c_k before the affirmative action but not i′ so that . But again, by definition of a priority based affirmative action, the order is preserved between them since i′ is a minority student and cannot “decrease” in the ranking of the schools. Since i′ was rejected and not i in applying to c_k, it means that i′ can block μ^a, a contradiction again.

127 The only remaining case is that i ∈ I^m and i′ ∈ I^M. Since i is matched at an earlier step after the affirmative action policy, it implies that μ^a (i) ≻_i μ^b (i).

B. Proof of Proposition 2

128 Fix a student i ∈ I^m. Let A_̃k (l) be the event: “There are l minority students who have been matched in one of the schools c_k with k ≤ k ̃”. Let R_k̃ be the event: “i has been rejected by all schools c_k with k < k ̃”.

129 The proof uses the following technical lemma:

130 Lemma 1. For any minority student i ∈ I^m, vector of quotas m, k = 1,..., N, and l = 1,..., n − 1:

Eu_i (L (m) |R_k _+ 1, A_k (l + 1)) ≥ Eu_i (L (m) |R_k _+ 1, A_k (l))

131 Moreover, if ∃k ′ > k with m_k _′ = 1, then the above inequality is strict.

132 Lemma 1 states that, for a given minority student, once he applies to his k + 1-th ranked school under DA, i.e. conditional on the event R_k₊₁, his conditional expected utility is weakly higher if there are more minority students who have been accepted at prior steps, i.e. higher conditional on A_k (l + 1) than conditional on A_k (l). The intuition is easy: if more minority students have been accepted at prior steps, there will be less competition for schools with a prioritized seat. With Lemma 1 in hands, we can now turn to the proof of Proposition 2:

133 Proof of Proposition 2. First, if k^* is s.t. | { k: (k < k^* ) ⋀ (m_k = 1) } | ≥ n, then clearly all minority students will always be accepted to the schools preferred to school c_k * and so prioritizing its seat will have no effect on their expected utility i.e. ∀i ∈ I^m, Eu_i (L (m′)) = Eu_i (L (m)).

134 So assume that k^* is s.t. | { k: (k < k^* ) ⋀ (m_k = 1) } | < n. The expected utility of a minority student i under m is given by:

Eu_i (L (m)) = ∑ p^m( c_k ) × u_i ( c_k ) + (1 − ∑ p^m (c_k ))
k* − 1 k* − 1
k=1 k=1
[ⁿ⁻¹ (()
∑^pm^(Ak^*−1^(l)|Rk^*)× 1*^×ui^(ck^*)+ 1− 1*
l=0 N− (k −1) N− (k −1)
× Eu_i (L (m) |R_k* + 1, A_k* − 1 (l)))]

135 And the one under m′ is:

Eu_i (L (m′)) = ∑ p^m^′ (c_k ) × u_i ( c_k ) + (1 − ∑ p^m^′ (c_k ))
k* − 1 k* − 1
k=1 k=1
[ⁿ ^− 1 (
∑^pm^{′ ( A}k^* − 1^{( l )|R}k^{* ) ×} 1 × ui^{( c}k^{* ) + ( 1 −} 1
)
l=0ⁿ^{−l n−l}
× Eu_i (L (m′) |R_k* + 1, A_k* − 1 (l)))]

136 Since the priority vector is the same for schools before school c_k*, we have that equation im93 and so equation im94 , ∀l = 0,..., n − 1. [51] The conditional probability of being matched to school equation im95 , knowing the number of minority students who have been accepted at a prior step, is now equation im96 under m′ and was equal to equation im97 under m. Indeed, under m, only the total number of remaining students at that step was important to calculate this probability since the school was selecting one student among all the applicants. Note that, for all l such that equation im98 , we have:

1= 1 <1
N − (k^* − 1) (n − l) + (N − (k^* − 1) − (n − l)) n − l

137 Where the last inequality holds since N − (k^* − 1) − (n − l) is the number of majority students left once we have to match school equation im100 and that l minority students have been accepted before that step. This is the direct effect of the affirmative action: it increases the direct probability to be matched with school c_k* when the minority student is applying to it. So to prove that the expected utility is higher under m′, it is now enough to show that equation im101 . [52]

138 Under any vector m̃ ∈ { m, m′ }, after the decision of school equation im102 , there are only two possible cases: i) either equation im103 accepted a minority student or ii) it accepted a majority student. Since, at the beginning of step k^*, there were already l minority students accepted at prior steps, we can write the following:

139 Under the vector m, since equation im105 did not prioritize its seat to minority students, i.e. equation im106 school c_k* randomly picked its student among all the applicants. At step k^* of DA, there were N − k^* + 1 applicants with, since we condition on equation im107 minority students among them. So we have that:

p^m (A_k* (l + 1) |R_k* + 1, A_k* − 1 (l)) = Nn−−kl_*−+11
*
p^m (A_k* (l) |R_k* + 1, A_k* − 1 (l)) = NN− k− k−_* +n +1 1

140 Note that the two above probabilities are strictly positive and add up to one. Morover, using Lemma 1, we have that equation im109 so we conclude that:

Eu_i (L (m) |R_k* + 1, A_k* − 1 (l)) ≤ Eu_i (L (m) |R_k* + 1, A_k* (l + 1))

141 But under the new vector m′, school equation im111 now prioritizes its seat to minority students so that it has to accept one of those who are applying to it. So it implies that we are sure that one additional minority student was accepted by school equation im112 under m′ . Formally, it means that equation im113 so we can conclude that:

Eu_i (L (m′) |R_k* + 1, A_k* − 1 (l)) = Eu_i (L (m′) |R_k* + 1, A_k* (l + 1))

142 Since m_k = m′_kfor k > k^*, then once we condition on the events equation im115 and equation im116 , the two DA procedures under m and m′ will start the step k^* + 1 with the same number of minority and majority students and the schools will apply the same probabilistic decisions. So the conditional assignment probabilities of i will be the same between m and m′ implying that equation im117 .

143 But Lemma 1 has already allowed us to conclude that:

Eu_i (L (m) |R_k* + 1, A_k* − 1 (l)) ≤ Eu_i (L (m) |R_k* + 1, A_k* (l + 1)) = Eu_i (L
(m′) |R_k* + 1, A_k* (l + 1))

144 Note that, using Lemma 1 again, if ∃k > k^* s.t. m_k = 1 (remember that both m′ and m are equal for those schools), then the above inequality is strict. This is exactly the indirect effect of the affirmative action policy: conditional on being rejected from the school where the policy was reinforced, i.e. equation im119 , the expected utility of the minority student is strictly higher. This is because the vector m′ now makes sure that a minority student has been accepted in equation im120 . As mentioned after Lemma 1, it thus decreases the competition for prioritized seats in later schools compared to the vector m where there was still a strictly positive probability for a majority student to be accepted by school equation im121 .

145 The above inequality implies that Eu_i (L (m′)) > Eu_i (L (m)), concluding the proof.

146 To finish the proof of Proposition 2.

147 Proof of Lemma 1. Note that if m_k _′ = 0 for all k ′ > k then the two expressions would be equal. Indeed, in that case, the remaining schools do not prioritize their seats for minority students so that only the total number of students left at each step determines the probabilities of being matched with them. So these probabilities are the same under the two events and (R_k _+ 1, A_k (l + 1)) and (R_k _+ 1, A_k (l)) since the number of remaining students is the same, only the composition changes.

148 So now, assume that ∃k ′ > k s.t. m_k _′ = 1. Let k₁: = min {k ′: (k ′ > k) ⋀ (m_k _′ = 1)}. We have that:

k₁ − 1
Eu_i (L (m) |R_k _+ 1, A_k (l + 1)) = ∑ p^m (c_k _′ |R_k _+ 1, A_k (l + 1)) × u_i (c_k _′)
k′ =k+1
(^k^1 − 1)
+ 1 − ∑ p^m (c_k _′ |R_k _+ 1, A_k (l + 1)) × Eu_i (L (m) |R_k , A_k (l + 1))
k′ =k+1¹

k₁ − 1
Eu_i (L (m) |R_k₊₁, A_k (l)) = ∑ p^m (c_k_′ |R_k₊₁, A_k (l)) × u_i (c_k_′)
k′ =k+1
(^k^1 − 1)
+ 1 − ∑ p^m (c_k_′ |R_k₊₁, A_k (l)) × Eu_i (L (m) |R_k , A_k (l))
k* = k + 1¹

149 Note that for k + 1 < k ′ < k₁ − 1, p^m (c_k_′ |R_k₊₁, A_k (l + 1)) = p^m (c_k _′ |R_k _+ 1, A_k (l)). Indeed, since these schools, by definition of k₁, do not give any priority to minority students, only the total number of remaining students is important to calculate their acceptance probability. This number is the same between the two events (R_k₊₁, A_k (l)) and (R_k₊₁, A_k (l + 1)). So to prove our claim, we need to show that equation im124 . We have that:

150 In the second expression, note that equation im126 . Indeed, since all schools c_k _′ with k^* < k ′ < k₁ do not prioritized their seat for minority students, then, since we condition on A_k (l), the n − l minority students not assigned after step k can all be rejected by these schools. So there is still a strictly positive probability that, at the beginning of step k₁, still l minority students have been accepted at prior steps, i.e. that the event equation im127 occurs.

151 Comparing the two expressions, it is enough to show that for any ̃l = l + 1,..., n − 1:

Eu_i (L (m) |R_k₁, A_k_1 − 1 (̃l + 1)) > Eu_i (L (m) |R_k₁, A_k_1 − 1 (̃l))

152 We have that:

Eu_i (L (m) | R_k₁, A_k_1 − 1 (̃l)) = p^m (c_k₁ | R_k₁, A_k_1 − 1 (̃l)) × u_i (c_k₁)
+ (1 − p^m (c_k₁ | R_k₁, A_k_1 − 1 (̃l))) × Eu_i (L (m) |R_k_1 + 1, A_k₁ (̃l + 1))
Eu_i (L (m) | R_k₁, A_k_1 − 1 (̃l + 1)) = p^m (c_k₁ | R_k₁, A_k_1 − 1 (̃l + 1)) × u_i (c_k₁)
+ (1 − p^m (c_k₁ |R_k₁, A_k_1 − 1 (̃l + 1))) × Eu_i (L (m) |R_k_1 + 1, A_k₁ (̃l + 2))

153 Since by definition, equation im130 gives priority to minority students, we have that:

p^m (c_k₁ |R_k₁, A_k₁₋₁ (l̃)) = n −1 l̃ < n − ̃1l − 1 = p^m (c_k₁ |R_k₁, A_k₁₋₁ (l̃ + 1))

154 So equation im132 assigns a strictly higher conditional probability to be assigned to equation im133 than equation im134 . So to prove the strict inequality, it is enough to prove that:

Eu_i (L (m) |R_k_1 + 1, A_k₁ (l̃ + 2)) ≥ Eu_i (L (m) |R_k₁₊₁, A_k₁ (l̃ + 1))

155 And so we come back to the same claim as the one we had before with k rather than k₁ here. We can apply the same reasoning in defining k₂: = min { k: (k > k₁ ) ⋀ (m_k = 1)}. The exact same calculations will lead us to prove that:

Eu_i (L (m) |R_k_2 + 1, A_k₂ (l̃ + 2)) ≥ Eu_i (L (m) |R_k₂₊₁, A_k₂ (l̃ + 1))

156 In iterating the argument we define an increasing sequence of indexes equation im137 s.t. for any j, equation im138 and for k_j _− 1 < k < k_j : m_k = 0. Each iteration of the argument leads us to prove that:

Eu_i (L (m) |R_kj _+ 1, A_kj (l̃ + 1)) ≥ Eu_i (L (m) |R_kj _+ 1, A_kj (l̃))

157 for any integer l̃ and once this is proved for one k_j, it is proved for all the previous k_j_′ , with j′ < j. Since the sequence represents indexes of the schools and that there is a finite number of them, this procedure must end, i.e. K < ∞. There are only two possible cases:

158 Case 1: k_K = k̄: = {k ′: m_k _′ = 1} and l̃ ≤ n − 2.

159 In that case, applying the same argument as before will lead us to prove the inequality:

Eu_i (L (m) |R_k̄ _+ 1, A_k̄ (l̃ + 1)) ≥ Eu_i (L (m) |R_k̄ _+ 1, A_k̄ (l̃))

160 But now, since by definition of k̄ we have that ∀k > k̄, m_k = 0, then we must have that Eu_i (L (m) |R_k̄ _+ 1, A_k̄ (l̃ + 1)) = Eu_i (L (m) |R_k̄ _+ 1, A_k̄ (l̃)). As mentioned before, since the remaining schools do not prioritize their seat, their acceptance probability only depends on total number of students that is the same between the two events A_k̄ (l̃ + 1) and A_k̄ (l̃).

161 Case 2: k_K =k ̃ < k̄ and l̃ = n − 2.

162 In that case, l̃ + 1 = n − 1 and so, conditional on R_̃k _+ 1 and A_k̄ (l̃ + 1), student i is the only remaining minority student. The decomposition of the two expected utilities conditional on these events are the same as before except that now, student i will be certain to be accepted to the next school with a prioritized seat in the case he applies to it. Under the event A_k̄ (l̃), there are two minority students left and so there is still a positive probability that i faces the competition of the other minority student in the next school with a prioritized seat so that he might be rejected from it. So clearly: Eu_i (L (m) |R_k̃₊₁, A_̃k (̃l + 1)) > Eu_i (L (m) |R_k̃₊₁, A_̃k (̃l)).

163 Since we have proved the claim for k_K, then it implies that the same claim is proved for all k_j with j = 1,..., K − 1 and, in particular:

Eu_i (L (m) |R_k_1 + 1, A_k₁ (̃l + 2)) ≥ Eu_i (L (m) |R_k₁₊₁, A_k̄ (̃l + 1))

164 So that we conclude that:

Eu_i (L (m) |R_k₁, A_k_1 − 1 (̃l + 1)) ≥ Eu_i (L (m) |R_k₁, A_k₁₋₁ (̃l))

165 Finishing the proof of the lemma.

C. Proof of Proposition 3

166 Without loss of generality, we assume that the school equation im143 is the most preferred one and the prioritized slot is the first ranked in equation im144 , i.e. k^* = 1 and l = 1. Indeed, in the case where school equation im145 is not the most preferred one or that the prioritized slot is not the first ranked one in ▷, then, as in the proof of Proposition 2, we can condition on the minority student being rejected from all the more preferred schools c_k with k < k^* and from all the lower ranked slots equation im146 with l ′ < l. The proof will decompose the probability to be assigned to each slot. equation im147 will denote the probability to be assigned to the l-th ranked slot of school c_k in ▷_k (resp. ▷ ′_k). The probability to be assigned to school c_k is simply the sum of the probabilities of each of its slots. Let equation im148 be the event: “There are z minority students who have been matched to one of the slots equation im149 with either k ′ < k or (k ′ = k) ⋀ (l ′ ≤ l)”. Let equation im150 be the event: “i has been rejected by the slots equation im151 with either k ′ < k or (k ′ = k) ⋀ (l ′ ≤ l)”. Remember that the new precedence order ▷ ′₁switches a prioritized slot ranked first in ▷₁ with an open slot ranked second.

167 The probability to be matched to the two first ranked slots of c₁ in ▷ is:

p (s¹₁ ) + p (s¹₂ ) = 1n + (1 − 1n) (_N¹₋₁)

168 Under the precedence order ▷ ′, this probability becomes:

p′ (s¹₁ ) + p′ (s¹₂ ) = N1 + (1 − N1) [_Nⁿ⁻₋¹₁ × n 1− 1 + (1 − Nn −−11) × n1]

169 Then:

p′ (s¹₁ ) + p′ (s¹₂ ) > p (s₁¹ ) + p (s¹₂)
⇔ NN+nn > nN (+Nn−−12)
⇔N> n

170 Which is always true. So the new precedence order increases the probability to be assigned to the first two slots of school c₁. Similar to the proof of Proposition 2, we have:

Eu_i (m, ▷) = (p (s¹₁ ) + p (s¹₂ )) × u_i (c₁ ) + p (R_s12) × Eu_i (m, ▷ |R_s12)
Eu_i (m, ▷ ′) = (p′ (s¹₁ ) + p′ (s¹₂ )) × u_i (c₁ ) + p′ (R_s12) × Eu_i (m, ▷ ′ |R_s₂1)

171 We have to show that equation im156 . We have:

172 Since ▷ and ▷ ′ agree on the ranking of all the slots except equation im158 and equation im159 once we condition on equation im160 , the two conditional expected utilities are the same, i.e. equation im161 . The effect is that ▷ ′ transfers probability mass to z = 2 compared to ▷ since, under ▷ ′, minority students have a higher probability of being assigned to one of the two first slots in c₁. [53] As in the proof of Proposition 2, it is enough to show that equation im162 . The argument is exactly the same as in the proof of Proposition 2.

D. Figures of the simulations of Section 5

Figure 1

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under each tie-breaking rule.

Figure 2

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under different values of m.

Figure 3

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 1 and m increases under different values of β – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 1 and m increases under different values of β – STB rule.

Figure 4

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under each tie-breaking rule.

Figure 5

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under different values of m.

Figure 6

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when β = 0, a = 0.5 and m increases under different values of T – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when β = 0, a = 0.5 and m increases under different values of T – STB rule.

Figure 7

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under each tie-breaking rule.

Figure 8

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under different values of m.

Figure 9

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 25, a = 0.5 and m increases under different values of β – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 25, a = 0.5 and m increases under different values of β – STB rule.

Bibliographie

References

ABDULKADIROGLU A., and SÖNMEZ T. [2003], “School choice: A mechanism design approach.” American Economic Review, 729-747.
ABDULKADIROGLU A., PATHAK P.A., ROTH A.E., and SÖNMEZ T. [2005], “The Boston public school match.” American Economic Review, 368-371.
ABDULKADIROGLU A., PATHAK P.A., and ROTH A.E. [2009], “Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match.” American Economic Review, 99 (5): 1954-1978.
ABDULKADIROGLU A., PATHAK P., ROTH A.E., and SÖNMEZ T. [2006], “Changing the Boston school choice mechanism.” National Bureau of Economic Research.
ABDULKADIROGLU A., CHE Y.-K., and YASUDA Y. [2011], “Resolving conflicting preferences in school choice: The “Boston mechanism” reconsidered.” The American Economic Review, 101 (1): 399-410.
ABDULKADIROGLU A., CHE Y.-K., and YASUDA Y. [2015]. “Expanding “choice” in school choice.” American Economic Journal: Microeconomics, 7 (1): 1-42.
ARNOSTI N. [2016], “Centralized clearinghouse design: A quantity-quality tradeoff.”
ASHLAGI I., NIKZAD A., and ROMM A. I. [2015], “Assigning more students to their top choices: A tie breaking rule comparison.”
ASHLAGI I., and NIKZAD A. [2015], “What matters in tie-breaking rules? How competition guides design.”
BALINSKI M., and SÖNMEZ T. [1999], “A tale of two mechanisms: student placement.” Journal of Economic Theory, 84 (1): 73-94.
CHE Y.-K., and TERCIEUX O. [2015a]. “Efficiency and Stability in Large Matching Markets.” Columbia University and PSE, Unpublished mimeo.
CHE Y.-K., and TERCIEUX O. [2015b], “Payoff Equivalence of Efficient Mechanisms in Large Markets.” Forthcoming, Theoretical Economics.
DOGAN B. [2016], “Responsive affirmative action in school choice.” Journal of Economic Theory, 165: 69-105.
DUBINS L. E., and FREEDMAN D. A. [1981], “Machiavelli and the Gale-Shapley algorithm.” American Mathematical Monthly, 88 (7): 485-494.
DUR U., KOMINERS S. D., PATHAK P. A., and SÖNMEZ T. [2017], “Reserve Design: Unintended Consequences and The Demise of Boston’s Walk Zones.”
ECHENIQUE F., and YENMEZ M. B. [2015], “How to control controlled school choice.” American Economic Review, 105 (8): 2679-2694.
EHLERS L., HAFALIR I. E., YENMEZ M. B., and YILDIRIM M. A. [2014], “School choice with controlled choice constraints: Hard bounds versus soft bounds.” Journal of Economic Theory, 153: 648-683.
ERDIL A., and ERGIN H. [2008], “What’s the matter with tie-breaking? Improving efficiency in school choice.” American Economic Review, 98 (3): 669-689.
FACK G., and GRENET J. [2011], « Que peut-on attendre de la réforme de la sectorisation en France? Quelques enseignements des politiques de choix scolaire. » Revue d’économie politique, 120 (5): 709-737.
FACK G., GRENET J., and BENHENDA A. [2014], « L’impact des procédures de sectorisation et d’affectation sur la mixité sociale et scolaire dans les lycées d’Île-de-France. » Rapport de l’Institut des Politiques Publiques, (3).
GALE D., and SHAPLEY L.S. [1962], “College admissions and the stability of mar riage.” American Mathematical Monthly, 9-15.
HAFALIR I. E., YENMEZ M.B., and YILDIRIM M.A. [2013], “Effective affirmative action in school choice.” Theoretical Economics, 8 (2): 325-363.
HILLER V., and TERCIEUX O. [2014]. “Choix d’écoles en France.” Revue économique, 65 (3): 619-656.
KAMADA Y., and KOJIMA F. [2014], “Efficient matching under distributional constraints: Theory and applications.” American Economic Review, 105 (1): 67-99.
KAMADA Y., and KOJIMA F. [2017], “Stability concepts in matching under distributional constraints.” Journal of Economic Theory, 168: 107-142.
KOJIMA F. [2012], “School choice: Impossibilities for affirmative action.” Games and Economic Behavior.
KOMINERS S. D., and SÖNMEZ T. [2013], “Designing for diversity in matching.” 603-604.
LEE S. M. [2016], “Incentive compatibility of large centralized matching markets.” The Review of Economic Studies, 84 (1): 444-463.
LEE S. M., and YARIV L. [2014], “On the Efficiency of Stable Matchings in Large Markets.” University of Pennsylvania, Unpublished mimeo.
lemonde.fr. [2017], « Affelnet: Paris amende le système d’affectation des lycées. » http://www. lemonde. fr/ campus/ article/ 2017/ 03/ 24/ affelnet-paris-amende-le-systeme-d-affectation-des-lycees_ 5100063_ 4401467. html, [Online; accessed 07-February-2018].
lemonde.fr. [2018], « Parcoursup: la nouvelle procédure pour s’inscrire en première année d’études supérieures. » http://www. lemonde. fr/ campus/ article/ 2018/ 01/ 15/ \parcoursup-la-nouvelle-procedure-pour-s-inscrire-en-premiere-annee-d\-etudes- superieures_5241811_4401467.html, [Online ; accessed 07-February-2018].
Libération [2017], « Lycées: à Paris, des parents d’élèves se mobilisent contre le logiciel Affelnet. » http://www. liberation. fr/ france/ 2017/ 07/ 05/ lycees-a-paris-des-parents-d-eleves-se-mobilisent-contre-le-logiciel-affelnet_ 1581557, [Online; accessed 07-February-2018].
ROTH A. E. [1982], “The economics of matching: Stability and incentives.” Mathematics of Operations Research, 7 (4): 617-628.
ROTH A. E. [1991], “A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the United Kingdom.” American Economic Review, 415-440.
ROTH A. E., and OLIVEIRA SOTOMAYOR M A. [1992], Two-sided matching: A study in game-theoretic modeling and analysis. Vol. 18, Cambridge University Press.
SHAPLEY L., and SCARF H. [1974], “On cores and indivisibility.” Journal of mathematical economics, 1 (1): 23-37.
SONMEZ T., and SWITZER T. B. [2013], “Matching With (Branch-of-Choice) Contracts at the United States Military Academy.” Econometrica, 81 (2): 451-488.
Studyrama [2018], « Parcoursup: un quota minimal de boursiers de lycée fixé. » http://www. studyrama. com/ parcoursup/ parcoursup-un-quota-minimal-de-boursiers-de-lycee-fixe-104275, [Online; accessed 07-February-2018].
TROYAN P. [2012], “Comparing school choice mechanisms by interim and ex-ante welfare.” Games and Economic Behavior.

Mots-clés éditeurs : discrimination positive, affectation, acceptation différée, choix d’écoles

Mise en ligne 04/03/2019

https://doi.org/10.3917/redp.286.1123

Notes

[1]
We will not enter here into the details of the entire french procedure. For instance Hiller and Tercieux [2014] showed that the algorithm is equivalent to a college proposing Deferred Acceptance algorithm. See also Fack and Grenet [2011] for the history and an analysis of the reform.
[2]
A School Choice Problem is defined in the literature as the problem of matching students to schools in respecting capacity constraints and where the priorities in each school are fixed (by law for example). In this setting, schools are considered as “consumed objects” and are not strategic agents. Welfare evaluations only consider the preferences of the students. Problems where schools have intrinsic preferences are called College Admission Problems.
[3]
More formally, it is a dominant strategy for them to do so, i.e. for any priorities of the schools and preferences of the other students, a student cannot obtain a strictly better school by reporting a false list of preferences. This result was proved by Dubins and Freedman [1981] and Roth [1982].
[4]
Concerning the positive interpretation of stability, Roth [1991] studied seven different assignment markets for new physicians and surgeons in the United Kingdom, and showed that procedures leading to a stable assignment were still in use while most of the unstable ones were quickly abandoned.
[5]
The Parcoursup procedure is different from a purely centralized algorithm. A centralized platform sends the applications of the students to the universities that then select them. Moreover, it only asks students to report a non-ordered list of universities contrary to the standard school choice procedures, such as DA, that ask for an ordered list. We only want to highlight here the use of the quotas in the system. The interested reader can find details of the procedure on many French newspapers (e.g. lemonde.fr [2018]) or on the official website https://www.parcoursup.fr/. Concerning the quotas, one can also refer to Studyrama [2018].
[6]
In Paris, the grades of the two students are used to break the tie. In other regions, the birthdate is also used. However, from a student perspective, it is unlikely that he exactly knows the characteristics (birthdate, grades...) of every other student so that he perceives the procedure as random. In that context, the use of an interim-welfare approach is also justified.
[7]
By interim-welfare, we mean the expected utility of each student once he has learned his own preferences but there is still some randomness in the assignment, e.g. the tie-break. The cited authors used the word “ex-ante” but, in a recent work, Troyan [2012] used an even earlier evaluation of welfare prior to the realization of students’ preferences.
We choose here to adopt the classical terminologies of the mechanism design literature in calling ex-ante welfare the one before any realization of information, taking expectations over all the possible types of the students. Interim-welfare refers to the welfare once each player has learnt his own type but not the one of the others. And the ex-post welfare is simply the utility that each student obtains once all the uncertainty is resolved, i.e. his final assignment’s utility.
[8]
Recent works studied the probabilistic differences between STB and MTB rules. Ashlagi and Nikzad [2015] showed that, when there are enough seats for all the students, there are efficiency trade-offs between the two rules. However, aSTB rule is preferable when there is a shortage of seats. Ashlagi, Nikzad and Romm [2015] showed that a STB rule leads to a constant fraction of students being assigned their first ranked school contrary to a MTB rule where this fraction vanishes with the size of the market. Arnosti [2016] highlighted the trade-off of the two rules between minimizing the number of unassigned students and maximizing the number of students being assigned their first choice.
[9]
In the following analysis, we will assume that all students (resp. schools) find all the schools (resp. students) acceptable.
[10]
Since a student’s matching is a singleton, we will abuse of notations and write μ (i) = c iff μ (i) = {c}.
[11]
In the case where there are unacceptable schools or students, we need to add an individual rationality constraint, i.e. ∀i, μ (i) ≻_i ∅ and ∀c, μ (c) ≻_c ∅.
[12]
The reader can refer to the cited articles for the formal definitions.
[13]
Note that, at each step, the acceptance of a student is temporary since it can be rejected at a later step in the case where new students apply to the school.
[14]
In their first introduction of affirmative action policies, Abdulkadiroglu and Sönmez [2003] defined different groups of minority students. Other papers also studied these multiple-groups models, the reader can refer to Ehlers et al. [2014] who introduced ways to implement quota policies using DA. Other similar works followed: see Kamada and Kojima [2014], Echenique and Yenmez [2015] or Kamada and Kojima [2017]. However, their goal is different from ours. They mainly focus on distributional concerns i.e. the existence of stable matchings that respect the quotas and how to correctly define DA in their setting. Here, as mentioned, we chose to have a welfare oriented analysis.
[15]
As mentioned, we suppose here that every school (resp. student) finds all the students (resp. schools) acceptable.
[16]
Here the definition does not distinguish between seats in clearly separating open from reserved seats. This stability notion only uses the number of students of different types assigned to a school. Recent works are dealing with priorities that are determined for each seat of a school to allow more complex priority stuctures. The general model introduced by Kominers and Sönmez [2013] that was inspired by the cadet-branch matching problem of Sönmez and Switzer [2013]. We describe it in Section 3.2.
[17]
For vectors, we write x > x′ if all the coordinates of x are weakly higher and some strictly.
[18]
The reader can easily find this matching in applying DA. The same ordinal preferences for the students ensures the uniqueness of the stable matching.
[19]
In this setting, any matching is Pareto-efficient.
[20]
There are two possible explanations for the use of expected utilities. The first one is that priorities are coarse and that ties are broken randomly during the algorithm so that the students do not know their particular ranking at a school when they submit their preferences. The second one is to assume that the priorities are strict but that the students do not know the characteristics of the other students that determine their ranking relative to their one.
[21]
Majority students will face a different distribution. The analysis for them will be the exact symmetric of the one for minority students.
[22]
This strongly relies on our assumption that all schools have the same number of seats. The analysis is similar if one allows schools to have different capacities. This assumption just avoids the heaviness of dealing with sums of the form q_l if quotas are different from one school to another. The assumption that there are enough seats for all students is a natural one if we think of the context of public school choice problems. Assuming, N = Mq avoids to deal with empty seats and unassigned students but relaxing this assumption will not change any of our results.
[23]
Note that, as stated, the direct effect concerns an increase in the probability of being assigned to the new prioritized school and the indirect affect corresponds to the increase in the expected utility conditional on being rejected from the latter school. Thus, they deal with different mathematical objects. To compare the effects, one can compare the increase in the expected utility conditional on not being rejected by the new prioritized school to the increase in the expected utility conditional on being rejected from that school. However, the difference in values crucially depends on the vNM cardinal utilities so that, for some of them, the direct effect will be bigger than the indirect one and vice-versa for other vNM utilities.
[24]
A distribution F first order stochastically dominates another distribution G, if ∀x, F (x) ≤ G (x).
[25]
As discussed before, we assume that our policy respects an anonymous criterion when treating minority students. One can also interpret the prioritized seats as a HB or a SB policy. For a HB policy, the prioritized seats must find the majority students as unacceptable.
[26]
Once again, we focus on policies that aim to improve minority students’ welfare. Objectives focusing on the distribution of the students between different schools pursue a different goal, we refer the interested reader to the previously cited literature.
[27]
As mentioned, Dogan [2016], proposed a modification of the DA algorithm to ensure that the algorithm respects the spirit of affirmative actions as defined by Kojima [2012]: it ensures that at least one minority student is strictly better-off after the reinforcement of a policy. Contrary to him, as mentioned, to seek positive results, we chose to impose the Pareto-domination rather than precluding the Pareto-inferiority of the resulting matching.
[28]
I would like to thank Olivier Tercieux for pointing the equivalence with their result.
[29]
For HB or SB policies, the only positive result is when all the seats in all schools are prioritized for minority students.
[30]
In France, roughly 25 % of the students are boursiers so that we chose to keep the same proportion.
[31]
This simulation technique is standard in the literature. See for instance Erdil and Ergin [2008], Hafalir, Yenmez and Yildirim [2013] or Hiller and Tercieux [2014].
[32]
One can note that since r_ij, r_i ∈ [0, 1] and that the difference of points between any two students who do not belong to the same class is greater than 2, then these students are still ranked in the same way once ties are broken. Moreover, the reader can check that, with probability one, these two rules indeed induce strict orderings of the students that correspond to the MTB and STB rules.
[33]
One can check that, with the chosen values, the ordering between minority (resp. majority) students belonging to the same class and the ordering between any two students from two different classes remains them after the policy.
[34]
The codes must be changed if one wants to simulate policies that prioritize only a fraction of the seats of a school. Our qualitative results won’t be affected by such change.
[35]
To obtain the exact expected utility, we would have to compute all the possible priority vectors of the schools. This cannot be done in polynomial time. For example for 10 students with L = 1, there are already 3,628,800 possible rankings for one school. Our estimates already give good comparative statics. Our codes allow the user to freely set of the parameters (number of students, schools, capacities, iterations, indifference classes, correlations...) so that one can easily replicate and extend our results if needed.
[36]
Our simulations already iterate for many values of β, L and m so that the total number of iterations is already high. As mentioned or goal is not to perform an exhaustive simulation exercise but to provide some key observations once one relaxes our assumptions.
[37]
At the exception of the STB policy for the combination of low values of m and high values of β where the number decreases. We are not able to provide a good intuition of why it is the case.
[38]
This intuition is somehow in line with the analysis of Ashlagi, Nikzad and Romm [2015] and Arnosti [2016]. Indeed, the former state that “under STB, the more schools a student is rejected from, the less likely she is to cause other students (who may be assigned to their top choices) be rejected from other schools” and so the more likely he is to be rejected from these schools. They state that this effect can explain why a STB rule tends to assign, in a large market analysis, more students to their top choices.
[39]
For each k from 1 to 50, we calculate the number of minority students being assigned up to their k-th most preferred school.
[40]
The empirical distributions of our simulations are not stochastically ordered. However, Corollary 2 states that the true distributions are. The number of iterations of tie-break to calculate the expected utilities and the distributions is probably too low.
[41]
The number of iterations is already high. Our goal is not to provide an exhaustive analysis. However, our codes allow to let any parameter vary. Variations in the correlation of schools’ priorities have already been studied in the literature with strict priority orderings, see Hafalir, Yenmez and Yildirim [2013]. Our main contribution being to introduce the interim stage analysis, we want to compare it with the ex post one, i.e. in letting L vary.
[42]
Note that, when m = 50, all schools move minority students at the top of the ranking inside their class. It does not imply that minority students are ranked at the top of the priority ranking of the school since the ranking between classes remains the same. Thus, when L > 0 and m = 50, this is not a maximal priority based affirmative action as defined in Section 4 and minority students can still be worse-off after the policy.
[43]
By iteration, we refer to fixed preferences, distribution of the students in the classes and priority points for the classes.
[44]
Of course, there is no first order stochastic ordering between any two distributions.
[45]
We refer the reader to the cited articles in the introduction dealing with such objectives.
[46]
Paris is divided into four districts (North, South, East, West) with around 10 to 17 schools in each district. For further details, one can refer to the official website, in french, https:// www.ac-paris.fr/portail/jcms/p1921184/affectation-en-2de-gt-pour-un-eleve-scolarise-a-paris-etablissement-public-ou-prive-sous-contrat or the description, in english, provided on the Matching in Practice website: http://www.matching-in-practice.eu/matching-practices-in-secondary-schools-france/.
[47]
For instance, the bonus can induce a minority student to reject a majority student who will then reject a minority student from outside the district and make him/her worse-off.
[48]
Results available upon request. The distributions are similar to those reported in Section D of the Appendix (figure 3 for instance) except that the values are averaged over all preferences’ iterations rather than reported for only one of them.
[49]
See for instance Lee [2016], Lee and Yariv [2014], Che and Tercieux [2015b] and Che and Tercieux [2015a].
[50]
Formally, we fix ε > 0 and study the asymptotic behavior of the percentage of minority students whose utility after the reinforcement of the policy is less than their utility before the reinforcement minus ε.
[51]
By our assumption on k^*, we are sure that the event happens with a strictly positive probability. Also note that, since we condition on and that i is a minority student, then the number of minority students accepted before step k^* must be strictly lower than n.
[52]
Indeed, note that the policy transfers probability mass to which, because of aligned preferences, is always strictly greater than the expected utility conditional on being rejected by since the latter is at most equal to .
[53]
Indeed, the probability that exactly two minority students are assigned to the two first slots of c₁ is simply the probability that a minority student is assigned the open slot, i.e. under ▷ and under ▷ ′ . It is easy to see that it is higher under ▷ ′ .

Recherches récentes

Des idées pour vous

Recherches récentes

Des idées pour vous

Revue d'économie politique 2018/6 Vol. 128

Article de revue

Are Affirmative Action Policies so Impossible?

Citer cet article

Notes

1. Introduction

2. Models, notations and main results of the literature

2.1. Types of affirmative action policies

2.2. Main results and impossibilities of the previous literature

3. Aligned preferences, interim-welfare and affirmative action policies

3.1. Stronger affirmative action policies

3.2. Welfare effects of precedence orders.

4. Further interim and ex-post results

4.1. Can we relax the assumptions?

4.2. Can we give more ex-post results?

5. Simulations

5.1. Indifferent schools and students’ preferences variations

5.2. Same students’ preferences and variations over the number of classes

6. Conclusion

Appendix

A. Proof of Proposition 1

B. Proof of Proposition 2

C. Proof of Proposition 3

D. Figures of the simulations of Section 5

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when T = 1 and β increases under different values of m.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 1 and m increases under different values of β – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 1 and m increases under different values of β – STB rule.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when β = 0, a = 0.5 and T increases under different values of m.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when β = 0, a = 0.5 and m increases under different values of T – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when β = 0, a = 0.5 and m increases under different values of T – STB rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under each tie-breaking rule.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under different values of m.

Average number of minority students interim worse-off after an affirmative action policy when T = 25, a = 0.5 and β increases under different values of m.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 25, a = 0.5 and m increases under different values of β – STB rule.

Cumulative distributions of the ranks obtained by minority students for a fixed preference profile when T = 25, a = 0.5 and m increases under different values of β – STB rule.

Bibliographie

References

Notes

Raccourcis

Domaines

Cairn.info

Langues

Avec le soutien de

Retrouvez Cairn.info sur

Accès institutions

Toutes les institutions