School Choice with Flexible Diversity Goals and Specialized Seats

1 Introduction

Diversity goals are prevalent in many scenarios including the hiring of employees, student-intake, and public housing [Benabbou et al., 2018]. These may be affirmative action legal requirements, institutional policies, or guidelines for ensuring a healthier and better balance of various groups. As important decisions are made concerning who gets the next job or who gets their preferred school seat, it is critical that the algorithms are transparent and fair. This is especially so when they make complex decisions that simultaneously take into account merit, priority, and diversity.

In the past few years, diversity issues have been heavily studied in school choice [Abdulkadiro˘glu and S¨onmez, 2003], the prototypical model of two-sided matching. In the basic school choice problem, students have preferences over schools and schools have priorities over students. The typical goal is to match the students to schools in a way that is stable (no student wants to take an vacant slot or wants to replace a lower priority student). Another property that is important in this context is strategyproofness (no student has an incentive to misreport her preferences).

In school choice with diversity goals, schools accept students while not just taking into account the priority ordering over students (that could be based on test scores) but also considering diversity requirements (such as keeping in mind a target number of students with special talents or disadvantaged backgrounds). Student placement under diversity concerns has been considered in many countries including Israel [Gonczarowski et al., 2019] and India [Baswana et al., 2019]. A prominent and successful approach for these problems is to specify diversity requirements via upper and lower bounds on the types of students at the school [Ehlers et al., 2014; Aziz et al., 2019]. Based on these quotas, diversity is achieved by first admitting students whose types have not reached the minimum quotas and then admitting students whose types have not reached the maximum quotas (see e.g., [Kurata et al., 2017; Aziz et al., 2020; Sun, 2020]).

There are limitations of specifying diversity goals just by imposing upper and lower bounds on types. The first concern is whether one should indeed treat the status of being undersubscribed equally. For instance, suppose one school imposes minimum quota 10 on two types. Type t1 admits just 1 student while type t2 admits 8 students. It is reasonable to give higher precedence to students of type t1, who will help to achieve a diversity balance. The second concern is whether we should treat all types equally. It is common that some types are more important than others. Thirdly, lower and upper quotas are not sufficient to target proportionality ratios of types (that captures desirable distributions of different types of students). In particular, having targets on absolute numbers does not achieve proportionality goals effectively.

We explain the third issue through the following example. Suppose there is a market where students are associated with one of the three types t1, t2, and t3. Consider one school c with capacity 100 that has the target proportions of students are as follows: t1 : 30%, t2 : 30%, t3 : 40%. If we wish to capture these targets via setting of lower bounds, one can impose minimum quotas 30, 30 and 40 on type t1, t2, t3 respectively. Suppose 15, 60, and 60 students of type t1, t2, t3 apply for the school c. Then notable algorithms for the problem that use minimum quotas would return an outcome with type distribution (t1 : 15, t2 : 45, t3 : 40). However, there exists an outcome with type distribution (t1 : 15, t2 : 37, t3 : 48) that is closer to the target proportions. Such an outcome will be computed by the algorithm we propose.

In this paper, we aim to address the following questions. What is a powerful yet computationally tractable framework of specifying diversity goals, that encompasses most of the particular diversity approaches in theory and practice? Can it also capture meaningful and well-motivated diversity goals not yet addressed in the literature? Can we use such a framework and achieve desirable objectives in two-sided matching market design such as stability and strategyproofness in a robust manner? What are the limits of such an approach when students are allowed to express preferences over individual school seats?

1.1 Contributions

We present a new model of matching markets that generalizes school choice with diversity goals in two important ways. (1) Firstly, we allow schools to have specialized seats that are motivated by additional features such as accompanying scholarships, tuition-fee waiver etc. (2) Secondly, we greatly expand the type of diversity goals that can be specified. Our model introduces a flexible and general ordinal approach to specifying diversity goals that capture lower and upper quotas as well as proportionality concerns. We discuss how existing approaches that only minimum and maximum quotas in the intended ratios may not achieve outcomes that are closest to the intended ratios. The approach applies to many other settings including social choice and multi-agent decision making in which diversity is a concern.

For the new model, we present an algorithm called Generalized Deferred Acceptance with Flexible Diversity (GDAFD). It is a novel algorithm that we design for schools to choose students while taking into account flexible diversity goals. GDA-FD satisfies a natural notion of stability, strategyproofness, and non-wastefulness when each agent has one type and there are no specialized seats.

We then show that allowing for specialized seats but enforcing diversity over students leads to several challenges in achieving stability and strategyproofness. In view of these challenges, we then turn to an important domain in which we allow for specialized seats but there is exactly one school. 1 In this domain, we show that even if students have overlapping types, GDA-FD algorithm satisfies weak Pareto optimality and two notions of strategyproofness. En route to proving these results, we provide an alternative view of GDA-FD by showing its equivalence with an algorithm called Sequential Allocation Under Dynamic Diversity Goals.

Finally, we turn to a class of preferences called schoolbased that generalizes the case of homogenous school seats as well as the case of exactly one school. For school-based preferences, we show that GDA-FD is not strategyproof even if each agent has a single type. However, strategyproofness is regained by using another algorithm called Modified GDAFD that calls GDA-FD on a modification of the problem instance. Since Modified GDA-FD is equivalent to GDA-FD when there are no special seats, our key message is that the modified GDA-FD works well on several important domains. Some of our results are summarized in Table 1.

1 The domain captures various committee selecting or hiring scenarios that take into account diversity goals.

2 RelatedWork

Abdulkadiro˘glu and S¨onmez [2003] presented one of the seminal works on the use of matching market design for school choice. The problem of school choice with diversity constraints or goals is an active area of research in market design. In some of the earlier works [Echenique and Yenmez, 2015; Abdulkadiro˘glu and S¨onmez, 2003; Ehlers et al., 2014], it is assumed that each agent has at most one type. Recent papers have started exploring the case of 'overlapping types' (e.g., [Kurata et al., 2017; Aziz et al., 2019; Ayg¨un and Turhan, 2020; Gonczarowski et al., 2019]).

Typically, each school imposes a maximum quota and a minimum quota on each type [Ehlers et al., 2014; Gonczarowski et al., 2019; Hafalir et al., 2013; Kojima, 2012; Kominers and S¨onmez, 2013; S¨onmez and Yenmez, 2019; Baswana et al., 2019; Aziz et al., 2019]. Since stable matchings are not guaranteed to exist for hard lower quotas, and the corresponding problems are NP-hard [Kurata et al., 2017; Cheng et al., 2008], most of the successful approaches treat the quotas as soft (see, e.g. Ehlers et al. [2014] and followup works). We also adopt the approach of treating the quotas as soft.

Most work on school choice with diversity goals focuses on minimum and maximum quotas. Although there is some recent work on ratio constraints [Nguyen and Vohra, 2019], our diversity goals are more general and flexible, and our algorithmic solutions are different as well. Kominers and S¨onmez [2016] considered a matching model in which each school seat may have a different priority ordering over students and students have rankings over schools.

We assume that when students are matched, they contribute to the counts of all the types they satisfy. In a companion paper [Aziz and Sun, 2021], we take an alternative assumption that students contribute to the count of exactly one of the types they satisfy.

3 AModel for School Choice with Flexible Diversity Goals and Specialized Seats

In this section, we formalize the model of School Choice with Flexible Diversity Goals and Specialized Seats. An instance I of the setting consists of a tuple (S, T,H,C,X ,≿S,≿C , RC). There is a set of students denoted by S = {1, . . . , n}, each of whom belongs to some of the types from the type space T = {t1, . . . , tk}. Let T(i) denote the set of types of student i. We will denote by C the set of schools with a generic school denoted by bj or b. We will denote by H the set of school seats with a genertic seat denoted by h. School seats H are partitioned into |C| schools, where bj ⊆ H is the set of school seats controlled by school bj ∈ C. For any two different schools bi, bj ∈ C, we have bi ∩ bj = ∅. The symbol RC denotes the precedence profile of schools that captures flexible diversity goals. Section 4 is devoted to the precedence profile RC.

We follow the model of matching with contracts [Hatfield and Milgrom, 2005] where each contract x = (i, h, b) is a student-seat-school tuple indicating that student i is matched to seat h at school b. The set of all contracts is denoted by X ⊆ S × H × C and we assume that for any (i, h, b) ∈ X , we have h ∈ b. Given any X ⊆ X , for each student i, we denote by Xi as the set of contracts pertaining to student i; for each seat h, we denote by Xh as the set of contracts pertaining to seat h; for each school b, we denote by Xb as the set of contracts pertaining to school b. We denote by Xt b = {(i, h, b) ∈ Xb | t ∈ T(i)} as the set of contracts involving students of type t and school b. We extend the notation of each individual to a set of agents by taking the union, i.e., for any S′ ⊆ S, XS′ = ⋃i∈S′ Xi.

The preference profile of students S is denoted by ≿S= {≿1, . . . ,≿n} where for student i ∈ S, each ≿i specifies the preference of student i over contracts Xi. For instance, (i, h1, b1) ≿i (i, h2, b2) means that student i weakly prefers the contract (i, h1, b1) to the contract (i, h2, b2). Let ≻i and ∼i denote the strict and indifferent relation, respectively. In Section 5.2, we will assume that a student is indifferent between all contracts involving seats of the same school. In general, if some algorithm of ours requires strict preferences, we will assume that the ties are broken according to a fixed tie-breaking rule.

The priority profile of schools C is denoted by ≿C= {≿b1 , . . . , ≿b|C| } where each ≿b specifies the priority ordering of school b over contracts Xb. We will assume that a school's priority over contracts is based on an underlying priority relation over students, which could be based on first-come firstserved basis, entrance exam scores or randomization.

Next, we introduce several important properties for a desirable outcome. A contract (i, h, b) is acceptable to student i and school b if both (i, h, b) ≿i ∅ and (i, h, b) ≿b ∅ hold where ∅ represents the option of being unmatched. Without loss of generality, we consider acceptable contracts only, since we can remove any unacceptable contract from X . An outcome or a matching X is a set of contracts, i.e. X ⊆ X . An outcome is feasible if each student is matched to at most one contract, i.e. ∀i ∈ S, |Xi| ≤ 1, and each seat is matched to at most one student, i.e. ∀ h ∈ H, |Xh| ≤ 1. A feasible outcome Y is non-wasteful if there exists no (i, h′ , b′ ) ∈ Y such that there exists another contract (i, h, b) with (i, h, b) ≻i (i, h′ , b′ ) and Y ∪ {(i, h, b)} \ {(i, h′ , b′ )} is feasible. Given an instance I, an algorithm is strategyproof for students if no student can be matched to a strictly better contract when the student misreports his preferences.

4 Framework for Flexible Diversity Goals

In this section, we present a novel way for schools to select students. A key component of the method is to design a novel method to specify dynamic priorities of a school over students. The dynamic priorities of a school b are based on the static priority relation ≿b over students, and a dynamic precedence relation Rb over the types in T that we specify below. Given a feasible outcome X, each school b has a dynamic precedence ordering Rb(X) over types T. If t1Rb(X)t2 holds, then for the outcome X, type t1 is weakly preferred to type t2 in terms of achieving diversity goals of school b. Let Pb and Ib denote the strict and indifferent relation, respectively. We denote by RC = {Rb1 , . . ., Rb|C| } the precedence profile of all schools.

4.1 Dynamic Precedence Representation

Next, we explain how we represent the dynamic precedence Rb over types. First, each school b specifies different levels over each type t, denoted by Lb,t where each level ℓjb,t ∈ Lb,t specifies the range of number of students of type t that are matched to school b. For instance, in Figure 1, ℓ1b,t = [0, 10) means that when the number of students of type t matched to school b is weakly larger than 0 and smaller than 10, then it falls into the level ℓ1b,t . We refer to Ljb = {ℓjb,t }t∈T as level j of school b for convenience. Note that for each type t, it is not necessary to define levels for every integer from [1, ..., |S|].

Then the dynamic precedence ordering Rb(X) is determined as follows with indifference classes in decreasing order of precedence from left to right: Rb(X) : {t ∈ T : |Xt b | ∈ ℓ1b,t }, {t ∈ T : |Xt b | ∈ ℓ2b,t }, . . . , {t ∈ T : |Xt b | ∈ ℓkb,t }, where |Xt b | denotes the number of students of type t matched to school b in the outcome X. Intuitively, for a given outcome X, school b gives the highest precedence to types that fall into level 1 of school b, the second highest precedence to types that fall into level 2 of school b and so on.

Next, we explain how to capture different diversity goals through the dynamic precedence relation Rb(X).

Lexicographic. Let there be a fixed precedence ordering over types, say t1, . . . , t|T|. The lexicographic diversity goal of school b is that whenever possible, it prefers to be matched to students of type t with smaller index. In that case, for each type ti, create one level ℓib,ti = [0, |S|].

Min and MaximumQuotas. For each school b, let ηtb and ηtb denote the minimum quota and the maximum quota of type t, respectively. The diversity goal of school b under minimum and maximum quotas is that, school b gives the highest precedence to the student whose type has not reached the minimum quota, medium precedence to the student whose type has reached the minimum quota but not the maximum quota, and the lowest precedence to the student whose type has reached the maximum quota [Ehlers et al., 2014]. In that case, for each type t, school b has three levels ℓ1b,t = [0, ηtb - 1], ℓ2b,t = [ηtb , ηtb - 1] and ℓ3b,t = [ηtb , |S|].

Proportional. Let there be |T| positive integers, say r1, · · · , r|T| corresponding to each type t. The proportional diversity goal of school b is that the number of students of each type matched to school b is proportional to r1 : · · · : r|T|. In that case, each school b has multiple levels over each type t and leve number j, ℓjb,t = [(j - 1) ∗ rt, j ∗ rt - 1]. For example, ℓ1b,t = [0, rt - 1] and ℓ2b,t = [rt, 2rt - 1].

Egalitarian. Egalitarian is a special case of proportionality where the ratio among all types is 1. In that case, each school b has multiple levels over each type t where each level ℓjb,t = [j - 1, j - 1].

Our diversity framework can also capture combinations of the above objectives. Next, we give an example of how our approach can capture proportionality goals.

Example 1 (Proportional Diversity Goals). Consider a school b and a set of types T = {t1, t2, t3, t4} with desired ratios 1: 2: 3: 2. Then Rb is depicted graphically in Figure 2. Based on a current allocation of a school, each type has its own count of how many admitted students satisfy that type. Which types have the highest precedence for the school depends on current level of the types based on their counts. Suppose that the current allocation leads to the following counts t1 : 0, t2 : 1, t3 : 4, and t4 : 7. Then, then precedence level of the types are as follows: t1 : 1, t2 : 1, t3 : 2, and t4 : 4. Hence, t1 and t2 are the highest precedence types.

4.2 Choice Function for Flexible Diversity Goals

For a given school b, its priority relation ≿b over the students along with its precedence relation Rb over types can guide the school to select students from applicants. We specify a particular choice function for the schools.

We define a natural choice function of school b that chooses a set of contracts in Algorithm 1. The high level idea is that it identifies the types whose precedence is most important (based on which students are already selected) and then selects the highest priority contract that involves a student who Algorithm 1 Choice function Chb of school b

Input: A set of contracts Yb, Rb, and ≿b Output: A set of contracts Z ⊆ Yb

• 1: Remove unacceptable contracts from Yb.
• 2: Z ← ∅ %Z stores the set of contracts chosen by school b.
• 3: while Yb ̸= ∅ and |Z| is no more than school capacity do
• 4: Identify the set of types T ′ such that i) each type t ∈ T ′ has the highest precedence based on Rb(Z) and ii) there exists some contract y = (i, h, b) ∈ Yb with T (i) ∩ T ′ ̸= ∅.
• 5: Scan over Yb based on priority ordering ≻b and select the first contract y = (i, h, b) such that T (i) ∩ T ′ ̸= ∅.
• 6: Z ←Z ∪ {y}, Yb ← Yb \ {y}.
• 7: Remove all contracts from Yb that involve i or h.
• 8: return Z

satisfies one of the types. The process is repeated until the school capacity is reached or all students are selected.

Next, we explain Algorithm 1 in more detail. Given a set of contracts Yb that pertain to school b, a priority ordering ≿b over contracts and a precedence ordering Rb over types, the choice function Chb works as follows. In the beginning, we remove all unacceptable contracts from Yb and initialize the set Z to be empty which is used to store the set of contracts selected by school b. Next, we repeat the following procedure until the set of contracts Yb becomes empty or the school capacity is reached: First, we identify the set of types T ′ such that i) each type t ∈ T ′ has the highest precedence based on Rb(Z), and ii) there exists some contract x = (i, h, b) from Yb in which student i has some type from T ′ . Then, we scan over the set of contracts Yb based on the priority ordering ≻b of school b and select the first contract (i, h, b) such that student i has one of the highest precedence types. Finally, we update Z and Y accordingly and remove any contract y′ from Yb that is associated with either student i or seat h.

Note that our new choice function (Algorithm 1) is a generalization of the one by Ehlers et al. [2014], and it is designed for more general diversity goals instead of minimum and maximum quotas only. It is also well-defined for students having overlapping types. Algorithm 1 can also easily incorporate hard upper bounds for each type. All of our results go through with these hard upper bounds.

5 Stable Matching under Flexible Diversity Goals

In this section, we propose a two-sided matching algorithm that deals with general diversity goals.

5.1 Generalized Deferred Acceptance with Flexible Diversity

The algorithm is well-defined whether students have strict preferences over all the school seats or whether they are indifferent between all the school seats of the same school. It is also well-defined even if students have multiple types.

Given a set of contracts X, let Chi(X) denote the choice function of student i that selects her favorite contract among Xi. Let Chb(X) denote the choice function of school b that selects a set of contracts among Xb, which is not necessarily unique. Let ChS(X) = ⋃i∈S Chi(X) and ChC(X) =

Algorithm 2 Generalized Deferred Acceptance (GDA)

⋃b∈C Chb(X) denote the choice functions of students S and schools C, respectively.

Armed with our specified choice function for schools (Algorithm 1) , we consider the framework of the Generalized Deferred Acceptance (GDA) by Hatfield and Milgrom [2005] that works as follows. Student first choose their favorite contract from the set Y . Among all contracts proposed by students, each school then chooses a set of contracts. All contracts that are not selected by any school are removed from the set Y . The algorithm repeats these steps until no contract is removed.

We will refer to the GDA algorithm with the choice function defined in Algorithm 1 as Generalized Deferred Acceptance with Flexible Diversity (GDA-FD).

Here is an example illustrating how GDA-FD works.

Example 2. There are 4 students S = {1, . . . , 4} where students {1, 2, 3} belong to type t1 and student 4 belongs to type t2. Suppose there is one school b that has 3 school seats H = {h1, h2, h3}, a priority list 1, 2, 3, 4 and precedence relation that requires proportionality ratio of 2: 1 between t1 and t2. The preference profile of students are as follows: h1 ≻1 h2 ≻1 h3, h2 ≻2 h3 ≻2 h1, h3 ≻3 h2 ≻3 h1, h3 ≻4 h1 ≻4 h2. We abuse the notation of preferences and contracts, since there is only one school b. In the first round, students propose (1, h1), (2, h2), (3, h3), (4, h3) and school b chooses (1, h1), (2, h2), (4, h3). In the second round, students propose (1, h1), (2, h2), (3, h2), (4, h3) and school b chooses (1, h1), (2, h2), (4, h3). In the final round, students propose (1, h1), (2, h2), (3, h1), (4, h3) and school b chooses (1, h1), (2, h2), and (4, h3).

Theorem 1. The GDA-FD algorithm runs in polynomialtime and returns a feasible outcome that is non-wasteful, even if each student has multiple types.

Next, we propose a stability concept for the setting of School Choice with Flexible Diversity Goals and Specialized Seats by taking the dynamic precedence of schools into account. The following Definition 1 captures a natural idea called dynamic priority proposed in a influential work on school choice with diversity goals [Ehlers et al., 2014]. While our new definition is applicable to any market with flexible diversity goals. When diversity goals are not considered, it is equivalent to the standard stability concept.

Definition 1 (Stability). Given a feasible outcome Y with (i, h′ , b′ ) ∈ Y , a student i and a school b will form a blocking pair if (i, h, b) ≻i (i, h′ , b′ ) and either i) the outcome Y ∪ {(i, h, b)} \ {(i, h′ , b′ )} is feasible; or ii) there exists a contract (j, h, b) ∈ Y such that for all t ∈ T(i) and all t′ ∈ T(j) and for the outcome Y ′ = Y \ {(j, h, b)}, one of the following conditions holds: a) t Pb(Y ′ ) t′ ; or b) (i, h, b) ≻b (j, h, b) and either T(i) = T(j) or t Ib(Y ′ ) t′ holds. A feasible outcome is stable if there is no blocking pair.

We will try to understand how far stability can be achieved under various conditions.

5.2 No Specialized Seats

We first focus on the case in which each school has identical/homogenous school seats or students are indifferent between school seats of the same school. This model is still a significant generalization of the controlled school choice problem [Ehlers et al., 2014] in which all the school seats are identical and schools impose soft minimum and maximum quotas on each type. In contrast, our model allows for much more general diversity goals including type-specific quotas. Our first result is the following Theorem 2.

Theorem 2. When there are no specialized seats and each student has one type, GDA-FD is strategy-proof for the students and yields a stable outcome.

Note that to run GDA-FD, students need to break ties lexicographically to derive a strict preference relation over contracts. The proof idea for Theorem 2 is as follows. We show that in our framework, even though the choice functions of schools capture complex diversity goals, they still satisfy two key properties called substitutability (SUB) and law of aggregate demand (LAD) as defined in [Hatfield and Milgrom, 2005]. Once these properties are established, we invoke a general result in [Hatfield andMilgrom, 2005] that the Generalized Deferred Acceptance is strategy-proof for the students and always yields a stable outcome.

Note that Theorem 2 does not hold when each student may have multiple types, as mentioned in Theorem 3.

Theorem 3. When there are no specialized seats and each student has multiple types, GDA-FD is no longer strategyproof for the students and does not always yield a stable outcome.

6 Specialized Seats

In this section, we delve deeper into the case where students may distinguish between certain seats of a school. We study which positive properties of GDA-FD such as strategyproofness continue to hold under more general preferences, and present negative results that stable outcomes are not guaranteed to exist even under very restrictive conditions.

6.1 Case of a Global School

We first warm up by getting an in-depth understanding of GDA-FD for the case of a global school. The case of a global school is still an important setting that captures scenarios such as hiring of candidates by a company under diversity goals. We provide an alternative view of GDA-FD by showing that it is equivalent to a sequential allocation algorithm (Algorithm 3) under the assumption that there is a policy maker who treats the set of school seats as one global school b that has a global priority and a precedence ordering. Algorithm 3 can be viewed as a generalized version of serial dictatorship or sequential allocation in which dynamic diversity priorities are taken into account.

Algorithm 3 Sequential Allocation Under Dynamic Diversity Goals

Input: An instance I with global priorities and precedence relation for school b

Output: An outcome Z ⊆X

• 1: while some student is unmatched and can get an unallocated school seat do
• 2: Identify the set of types T ′ with the highest precedence based on Rb(Z) for which there exists some student who satisfies some type in T ′
• 3: Among the students who satisfy some type in T ′ , find the student i ∈ S who has the highest school priority based on ≻b (which is achieved from ≿b by any fixed tie-breaking rule)
• 4: Assign student i her favorite contract x = (i, h, b) among X , Z ← Z ∪ {x}
• 5: Remove the student i from the market, S ←S \ {i}
• 6: Remove the set of contracts involving student i and seat h, X \ (Xi ∪Xh)
• 7: return Z

An outcome X is weakly Pareto optimal if there is no other outcome X′ such that all the students get a more preferred outcome. An algorithm is type-strategyproof if no student has an incentive to report a subset of her true types. Next, we summarize the properties of the Algorithm 3 in Theorem 4.

Theorem 4. If there is one global school, even if students have multiple types, Algorithm 3 is strategyproof and typestrategyproof and the outcome returned by Algorithm 3 is weakly Pareto optimal.

Next, we show Algorithm 3 has a strong connection with GDA-FD for the setting in which students have strict preferences over the school seats and there is exactly one school.

Theorem 5. When there is exactly one school, the GDA-FD algorithm returns the same outcome as Algorithm 3 even if each student may have multiple types

Proof. (Sketch) Assume Algorithm 2 terminates in m iterations. For each iteration k ∈ [1,m], let Y 1 , . . . , Y m denote the set of contracts proposed by students. We prove that Algorithm 3 also returns the same outcome Y m given the same input in the Appendix.

Although the GDA-FD remains strategyproof when there is one global school and each student has a strict preference over school seats, it does not return a stable outcome even if each student has one type, as mentioned in Theorem 6.

Theorem 6. When each student has a strict preference over school seats, then the GDA-FD algorithm and Algorithm 3 do not return a stable outcome even if there is only one school and each student has one type.

6.2 School-based Preferences

In this section, we consider the case that students have schoolbased preferences. A student has school-based preferences if all the school seats of one school are preferred over all the Algorithm 4 Modified GDA-FD: Algorithm for schoolbased preferences

Input: I,ChS,ChC, a set of contracts Y Output: An outcome Z ⊆ Y

• 1: Let I ′ be the instance in which students are indifferent between school seats of the same school.
• 2: Let Y denote the outcome after applying GDA-FD to I ′ .
• 3: Let Sj denote the set of students who get matched to school bj in the outcome Y .
• 4: for each j ∈ [1, · · · ,m] where m= |C| do
• 5: Apply GDA-FD to the set of students Sj and school bj to allocate the school seats of bj to Sj , with respect to the original preferences ≻S in I. Let the outcome be Y ′ j .
• 6: return Z = ⋃mj=1 Y ′ j .

school seats of another school or vice versa. Note that students may have different preferences over school seats within the same school. For school-based preferences, we assume that all the school seats of a school are acceptable or none. The model of school choice with identical school seats is a special class of school-based preferences. The case of a single school is also a special case of school-based preferences.

Theorem 7. For school-based preferences, GDA-FD is not strategy-proof for students even if each student has one type.

Next, we design a new algorithm (Algorithm 4) for the case of school-based preferences which invokes GDA-FD twice. In the first stage of Algorithm 4, we first run GDA-FD on a modified instance I ′ in which school seats within a school are identical. This gives us information about which students are matched to which schools. In the second stage, we apply GDA-FD to each school and the set of students who are matched to that school based on students' true preferences over school seats. The second step determines which student receives which school seat. Algorithm 4 is strategyproof if each student has a single type as shown in Theorem 8.

Theorem 8. For school-based preferences, when each student has one type, Algorithm 4 is strategy-proof for students.

Next, we point out an impossibility result that the set of stable outcomes may be empty for school-based preferences even if under very restrictive conditions as shown in Theorem 9.

Theorem 9. When each student has a strict preference over school seats, the set of stable outcomes may be empty even if each student has one type and all schools have the same priority ordering over students.

7 Conclusions

We proposed a matching market model for residential markets with flexible diversity goals. We provided a clear understanding of under which conditions a stable matching is guaranteed to exist. Our diversity goal framework can be applied to many other settings in which priorities for different types dynamically change based on the current allocation. An interesting research direction is to identify other sufficient conditions for the guaranteed existence of stable outcomes under diversity goals.