Stable Matchings with Diversity Constraints: Affirmative Action is beyond NP

1 Introduction

Stability is a classic and central property of assignments, or matchings, of agents to each other, describing that no two agents prefer each other to their respective situations in the matching. Stability is desirable in many scenarios and spawned numerous works in various contexts [Manlove, 2013]. In this work we investigate the notion of stability in combination with diversity, which is key in many real-world matching applications, ranging from education, through health-care systems, to job and housing markets [Abdulkadiroˇglu, 2005; Huang, 2010; Kamada and Kojima, 2015; Kurata et al., 2017; Ahmed et al., 2017; Benabbou et al., 2019; Gonczarowski et al., 2019; Aziz et al., 2019].

For this we conceptually distinguish two sets-a set of students which should be matched to a set of colleges (each with a maximum capacity to accommodate students) with the additional constraint that the set of students matched to any single college has to be diverse. The diversity requirements are modeled as types which are attributes that a student may or may not have, and upper and lower quotas that specify how many students of a certain type may be matched to a given college. The terminology arises from the context of controlled public school choice, a typical application of this paradigm where it is desirable to match colleges to students to ensure stability as well as demographic, socio-economic, and ethnic diversity (see also affirmative action).

The study of stable matchings with diversity constraints was initiated by Abdulkadiroˇglu [2005] in the context of college admissions. It has since become an ongoing and actively researched topic among economists and computer scientists, covered for example by two chapters [Heo, 2019; Kojima, 2019] in the recently published book "On the Future of Economic Design" [Laslier et al., 2019]. One of the fundamental questions in this area is whether there is a diverse and stable matching between students and colleges; the corresponding computational problem is called SMTIDIVERSE (see Section 2 for formal definitions).

As has already been observed in the work of Aziz et al. [2019] and hinted at in Huang's earlier work on a closely related problem [2010], SMTI-DIVERSE is NP-hard. The authors further claimed that the problem(s) under consideration belong to NP (see also [Manlove, 2013, Chapter 5.2.5]). We disprove this claim by presenting an involved reduction showing that the problem is complete for the complexity class ΣP2 , even under severe restrictions to the input instances. Hence, the problem is substantially more difficult than all NP problems, unless a widely believed complexity-theoretical assumption collapses. In particular, this implies that the problem is not easily amenable to SAT or ILP solvers.

Complementing this hardness finding, we systematically analyze the complexity of the problem by considering natural relaxations (such as dropping lower quotas or dropping stability) or restrictions (such as bounding the number n of students, the number t of types, the number m of colleges, and/or the maximum upper quota u∞, and the maximum capacity q∞). The outcome of our analysis is a full classification of the complexity of SMTI-DIVERSE with respect to the considered restrictions and relaxations, presented in Table 1. We highlight three key technical contributions of our work: (1) SMTI-DIVERSE is ΣP2 -complete even when the preferences do not have ties and m = 4, while two natural relaxations of the problem (either dropping the lower quotas or the stability requirement) lower the complexity to NP-complete. (2) When n, m+t, or m+q∞ is a constant, SMTI-DIVERSE can be solved in polynomial time.

1. SMTI-DIVERSE is NP-complete even if lower quotas are

all zero and t + u∞ + q∞ is a constant. This result also fixes a technical flaw in [Aziz et al., 2019, Proposition 5.3].

Relatedwork. For one type, SMTI-DIVERSE is equivalent to the Hospitals/Residents with Lower Quotas problem where no hospital is allowed to be closed (HR-LQ-2), as studied by Hamada et al. [2016]. This problem is polynomial-time solvable when no ties are allowed [Manlove, 2013, Chapter 5.2.3]. We show that SMTI-DIVERSE becomes NP-hard even for only two types.

Huang [2010] introduced the closely related CLASSIFIED STABLE MATCHING (CSM) problem, which asks for a matching that fulfills the diversity constraints and does not admit blocking coalitions. We show that our ΣP2 -hardness reduction can be adapted to show ΣP2 -completeness for CSM.

Aziz et al. [2019] studied school choice with diversity constraints, but with a slightly different stability condition: an unmatched student-college pair {u,w} is d-blocking if it is a blocking pair (in our sense) and the new solution fulfills the diversity constraints for all colleges instead of only for w. This means that a d-blocking pair is also a blocking pair, but the converse is not true. However, dropping the lower quotas requirements renders both concepts equivalent. Our model of blocking pairs is a direct extension of HR-LQ-2, where a student and a college already form a blocking pair once the new solution is better for them, regardless of the other colleges' lower quotas. Such a model assumes that the blocking condition is tested based on local information of whether the deviating college's diversity constraints are fulfilled after the rematching. This is a standard assumption in many controlled school choice articles [Abdulkadiroˇglu, 2005; Kurata et al., 2017; Hamada et al., 2016]. Nevertheless, our ΣP2 -hardness reduction establishes the same hardness for their variant. Other related work includes recent papers by Nguyen and Vohra [2019], Kurata et al. [2017], Ismaili et al. [2019].

2 Preliminaries

Given an integer z, let [z] denote the set {1, . . . , z}. Given two integer vectors x, y of the same dimension, i.e., x, y ∈ Zz for a non-negative integer z, we write x ≤ y if for each index i ∈ [z] it holds that x[i] ≤ y[i]; otherwise, we write x ̸≤ y. A preference list ⪰ over a set A is a complete and transitive binary relation on A. We use ≻ to denote the asymmetric part (i.e., x ⪰ y and ¬(y ⪰ x)) and ∼ the symmetric part of ⪰ (i.e., x ⪰ y and y ⪰ x). We say that x is (strictly) preferred (resp. weakly preferred) to y if x ≻ y (resp. x ⪰ y), and that x and y are tied in ⪰ if x ∼ y; ⪰ is said to contain ties in this case. We write [A] to denote an arbitrary but fixed linear order on A. The expression "x ≻ Y " (resp. "x ⪰ Y ") means that x is strictly (resp. weakly) preferred to every one in Y .

Problem-specific terminology. The problem we study has as input a set T := [t] of types, a set U := {u1, u2, . . . , un} of n students and a set W := {w1, w2, . . . , wm} of m colleges together with the following information. Each student u∈U has (i) a preference list ⪰u over a subset A(u) ⊆ W of the colleges, and (ii) a type vector τu ∈ {0, 1}t , where τu[z] = 1 means that u has type z. Each college w ∈ W has (i) a preference list ⪰w over a subset A(w) ⊆ U of the students, and (ii) a lower-quota and upper-quota for each type which is described, respectively, via the vectors ℓw and uw ∈ [n]t , where ℓw ≤ uw, and (iii) a capacity qw ∈ [n] which is the maximum number of students allowed to be admitted to w. Note that while the capacity can be modeled by introducing an extra type, separating it from the types allows for a more refined analysis of the problem's complexity.

For each x ∈ U ∪ W, we call A(x) the acceptable set of x, which contains all students or colleges that are acceptable to x. Throughout the paper, we assume that no student or college has an empty acceptable set, and for each student u and each college w it holds that u ∈ A(w) iff. w ∈ A(u).

A matching M is a set of student-college pairs of the form {u, w}, where each student u is involved in at most one pair in M and w ∈ A(u). If {u, w} ∈ M, then we say that u and w are assigned to each other by M. Slightly abusing the notation, given a student u ∈ U if there exists a college w ∈ W with {u,w} ∈ M, then define M(u) := w; otherwise define M(u) := ⊥. We assume that each student u prefers every acceptable college w ∈ A(u) to ⊥. Similarly, given a college w ∈ W, we write M(w) := {u | {u,w} ∈ M} to denote the set consisting of all students assigned to w by M.

Feasible and stable matchings. A matching M is feasible for an instance (U,W, T, (τu,⪰u)u∈U, (⪰w, ℓw, uw, qw)w∈W) if it is feasible for each college w ∈ W, i.e., college w (i) is assigned at most qw students, i.e., |M(w)| ≤ qw, and (ii) meets the lower and upper quotas for each type, i.e., ℓw ≤ ∑u∈M(w) τu ≤ uw.

A student u and a college w form a blocking pair in a matching M if: (i) u ∈ A(w) and {u,w} /∈ M, (ii) w ≻u M(u), (iii) there exists a (possibly empty) subset U ′ ⊆ M(w) such that u ≻w U ′ , and (iv) M∪{{u, w}}\{{u′ , w} | u′ ∈ U ′ } is feasible for w. Accordingly, we say that U ′ is a witness for {u,w} to block M. A matching M is stable if it has no blocking pairs.

Problem variants. Now, we formally state our main problem of interest-the natural generalization of the classical MANY-TO-ONE STABLE MATCHING WITH TIES AND IN- COMPLETE PREFERENCES (SMTI) [Manlove, 2013] to incorporate diversity constraints:

SMTI-DIVERSE

Input: A set U of n students, a set W of m colleges, a set T of types, the type vectors and preference lists (τu,⪰u)u∈U for the students, the preference lists, lower-quota vectors, upper-quota vectors, and capacities (⪰w, ℓw, uw, qw)w∈W for the colleges.

Question: Is there a feasible and stable matching?

We use SMI-DIVERSE to denote the restriction of SMTIDIVERSE to the case with no ties. Moreover, we use FIDIVERSE to denote the problem of deciding whether there is a feasible matching (representing a generalization for FEASIBLE MATCHING WITH INCOMPLETE PREFERENCES).

For an illustration, let there be four students u1, . . . , u4, two colleges w1, w2, with the following type vectors (T.) and the preference lists (Pref.) of the students (S.) as well as the preference lists (Pref.), the lower quotas (LQ.), the upper quotas (UQ.), and the capacities (C.) of the colleges depicted as follows; preferences always ordered by ≻:

There are two feasible matchings M1 and M2 with M1(w1)={u1, u3}, M1(w2)={u2, u4}, M2(w1)= {u2, u3}, M2(w2)={u1, u4}. But M1 is blocked by {u3,w2} while M2 is stable. If u1 does not accept w2, then no feasible and stable matching exists.

3 HowHard is Diversity?

General complexity. Aziz et al. [2019, Proposition 5.1] proved that FI-DIVERSE is NP-complete; the hardness result holds even for a single college. They also claimed that determining a matching without any d-blocking pairs is NPcomplete [2019, Proposition 5.3]. However, the proof used to show NP-membership is technically flawed-in particular, while the proof claims that "Deciding whether a stable outcome exists is in NP, since we can guess an outcome X and check whether X admits blocking pair in polynomial time", by adapting the reduction in [Aziz et al., 2019, Proposition 5.1] we can show that this is impossible unless coNP ⊆ P.

Proposition 1. Deciding whether a given feasible matching has no blocking pairs or no d-blocking pairs is coNP-hard.

Note that Proposition 1 itself does not rule out that SMIDIVERSE is in NP. It just suggests the given proof is incorrect. There could in principle be a different non-deterministic algorithm to place the problem in NP. We show that this is not the case in our main result (Theorem 1), by showing ΣP2 - hardness. For this we introduce a crucial gadget which is used in several of our reductions throughout this section.

Lemma 1. Let T = {1, 2}, and let U ⊎ {r1, r2, r3} be a set of students with three distinguished students r1, r2, r3, and let W ⊎ {a, b} be a set of colleges with two distinguished colleges a and b. Similar to the format given in Section 2, the preference lists and type vectors of students r1, r2, and r3, All students in U have zero types and arbitrary but fixed preferences. All lower quotas are zero. The following holds for every matching M. (1) If M(a)={r2}, M(b)={r1, r3}, and |M(w) ∩ U|=qw for all w ∈ W, then no pair {u,w} with "u∈{r1, r2, r3} and w∈{a, b}" or with "u = r2 and w ∈ W" is blocking M. (2) If |M(w) ∩ U|<qw for some w∈W, thenM is not stable.

It is straightforward to verify the correctness of Lemma 1 by case analysis. With Lemma 1 in hand, we can prove that the problem is not NP-complete but instead lies on the second level of the polynomial hierarchy.

Theorem 1. SMTI-DIVERSE is ΣP2 -complete, and remains ΣP2 -hard even if feasible matchings always exist, there are no ties, m = 4, and u∞ = 3.

Proof Sketch. To show that SMTI-DIVERSE is in ΣP2 , observe that checking whether a matching is not stable can be done by an NP-oracle (guess an unmatched pair {u, w} and a subset S of students, and check in polynomial time whether S witnesses that {u, w} is blocking M). Hence, we can guess in polynomial time a matching, ask the NP-oracle whether it is not stable, and return yes iff. the oracle answers no. Containment follows because NP NP = ΣP2 [Papadimitriou, 1994].

To show ΣP2 -hardness, we reduce from a problem called NOT-1-IN-3-∃∀3SAT: Given a Boolean 3CNF formula φ(X, Y ) over two equal-size variable sets X, Y such that each clause contains at least two literals from Y ∪ Y , is there a truth assignment of X such that for each truth assignment of Y at least one clause Cj is not 1-in-3-satisfied, i.e., Cj does not have precisely one true literal. NOT-1-IN3-∃∀3SAT can be shown to be ΣP2 -hard via a standard (and complementing) reduction from ∀∃3SAT, a classic ΠP2 -hard problem [Stockmeyer, 1976].

The idea of our main reduction is to construct, from an instance I of NOT-1-IN-3-∃∀3SAT with |X| = |Y | = r and s clauses, an equivalent instance I ′ of SMI-DIVERSE with 2r "variable-types", s "clause-types" and 2 auxiliary types (the types are ordered in this sequence). Instance I ′ contains a special student d that has all variable-types and all clause-types, and two distinguished colleges v,w which can both accommodate d, but d prefers being in v. I ′ furthermore uses Lemma 1 to construct a gadget which ensures that a matching can only be stable if d is matched to w-in particular, this will force a stable and feasible matching to ensure {d, v} will not form a blocking pair.

Moreover, I ′ contains one clause-student dj for each clause Cj (let D denote the set of all clause-students) and one student lit for each literal in X ∪Y ∪X ∪Y . Student dj only has one type: the clause-type 2r + j corresponding to Cj. Student lit has the variable-type i ∈ [r] corresponding to its variable as well as all the clause-types 2r + j of every clause Cj containing lit. All Y -literal students only want to go to v; all positive X-literal students prefer v to b while all negative X-literal students prefer b to v.

We can now explain the core of the reduction: the quotas of v are set up in a way which ensures (assuming d is matched to w) that precisely one literal-student for each variable in X, both literal-students for each variable in Y , and some clause-students must be matched to v. In particular, a clause-student dj will be matched to v if and only if the literal-student missing from v represents a literal in Cj. Once set up, we show that {d, v} is blocking if and only if there is a witness set of literal-students, and this witness set would represent an assignment which 1-in-3 satisfies I. In other words, a feasible and stable matching M exists if and only if there is an assignment of the X-variables (which can be reconstructed from M) such that no assignment of the Y -variables 1-in-3-satisfies all clauses.

The following describes the preference lists, quotas and capacities of the colleges, together with the preference lists of the students from {r1, r2, r3, d}.

This completes the construction which can be verified to fulfill the restriction stated in the theorem. It now suffices to show that "there exists an X-assignment σX such that for each Y -assignment σY at least one clause is not 1-in-3satisfied" if and only if "matching X′ ∪ Y ∪ Y ∪ D′ to v, ({r1, r3} ∪X ∪X) \ X′ to b, r2 to a, and d to w is feasible and stable, where X′ corresponds to the assignment σX and D′ = {dj | |(X′ ∪ Y ∪ Y ) ∩Cj| = 2}".

To see why the reduction behind Theorem 1 can be used to directly show ΣP2 -hardness for the problem studied by Aziz et al. [2019] we observe that in the constructed instance, {d, v} is a blocking pair if and only if it is a d-blocking pair. The proof of Theorem 1 can also be adapted to correct an erroneous theorem pertaining to a related problem called CLASSIFIED STABLE MATCHING (CSM) [Huang, 2010, Theorem 3.1]. In particular, that theorem claims that CSM is NPcomplete, but it is in effect also ΣP2 -hard. The idea for the adaption is to construct dummy variable-students with zerotypes and introduce additional types to ensure that {v, d} is a blocking pair in the proof of Theorem 1 if and only if v forms with d and the dummy variable-students a blocking coalition.

The impact of diversity. The fact that SMI-DIVERSE lies in a higher complexity class than FI-DIVERSE can be attributed to the stability constraints. On the other end of the spectrum, a stable matching without diversity constraints always exists and can be found in polynomial time [Manlove, 2013, Chapter 3]. We can pinpoint the cause of this jump in complexity more precisely to the existence of lower quotas, which in some sense implement affirmative action in the SMI-DIVERSE model. Specifically, we show that if the lower quotas are all zero, then SMTI-DIVERSE becomes NPcomplete (Theorem 2). Lemma 2 will be crucial for showing NP-containment.

Lemma 2. If ℓ∞ = 0, then checking whether a matching is stable can be done in O(n · m · t) time.

Proof Sketch. It suffices to show that a matching M is stable for an instance I = (U,W, T, (τu,⪰u)u∈U, (⪰w, ℓw = 0, uw, qw)w∈W) if and only if the following (polynomially verifiable) condition is met: for each unmatched studentcollege pair {u,w} /∈ M with u preferring w to M(u) either "τu+ ∑u′∈M(w) : u′⪰wu τu′ ̸≤ uw" or "|M(w)|=qw and M(w) ⪰w u", or both holds.

Even though with zero lower quotas SMTI-DIVERSE is in NP, and thus can be considered significantly easier than SMTI-DIVERSE in general, it is actually hard within NP. Hardness for this case was claimed in [Aziz et al., 2019, Proposition 5.3]. However the reduction contains a technical flaw. Indeed, the instance constructed in that proof is always a yes instance, independent of the original 3-SAT instance. To see this, define the matching M for their produced instance as follows (notations taken from that proof): First, let MF := ⋃i∈[k] XiF \ {(ti1 , o(ti1 )), (ti2 , o(ti2 )) | i ∈ [k]}. For each j ∈ [l], let Sj be the set consisting of the first two (if there are fewer than two, then all) students of the form tiz (i ∈ [k], z ∈ [2]) appearing in the preferences of oj. Then M := MF ∪ {(s, oj) | j∈[l] ∧ s∈Sj} is feasible and stable.

Below, we use Lemma 1 to provide a new and simpler NPhardness proof for the case with zero lower quotas.

Theorem 2. For ℓ∞ = 0, SMI-DIVERSE is NP-complete; it remains NP-hard even if ℓ∞ = 0, u∞ = 1, and t = q∞ = 2.

Proof Sketch. To showNP-containment, we guess in polynomial time a matching M, and check whether M is feasible and stable in polynomial time, using Lemma 2.

To establish NP-hardness, we reduce from (2,2)-3SAT, an NP-complete variant [Berman et al., 2003] of 3SAT where each literal lit ∈ X ∪ X appears precisely two times in the set φ(X) of clauses. Given an instance I = (X = {x1, . . . , xr}, φ(X) = {C1, . . . ,Cs}) of (2,2)-3SAT, construct an instance of SMI-DIVERSE as follows. For each clause Cj ∈ φ(X), introduce a clause-college cj. For each variable xi ∈ X, introduce two variable-students xi and yi, four literal-students u1i , u2i , v1 i , and v2 i , and two variablecolleges wi and pi. Introduce three special students r1, r2, r3, and two special colleges a and b. Let T = {1, 2}.

For ease of description we use the following notation: let c[uzi ] and c[vz i ], (z ∈ [2]) be the clause-college cj such that clause Cj contains the zth occurrence of literal xi, and xi respectively. Further, let sz [cj] (z ∈ [3]) denote the literal-student that corresponds to the zth literal appearing in clause Cj. For instance, if Cj = (x2, x3, x5) and the occurrence of x2 in cj is its second one, then s1 [cj] = v2 2 . Types and preference lists are given below, in a format similar to the one in Lemma 1.

All lower quotas are zero. This completes the construction of the instance for SMI-DIVERSE. One can verify the restrictions stated in the theorem. We show that (X, φ(X))

The "only if" part: let the truth assignment σX satisfy φ(X). It can be verified that the following matching M is feasible. · For each xi ∈ X, if σX(xi) = true, then let M(wi) := {xi, yi} and M(pi) := {v1 i , v2 i }; otherwise let M(wi) := {u1i , u2i } and M(pi) := {xi, yi}. · For each clause Cj ∈ φ(X), let M(cj) := {sz (cj)}, where z ∈ [3] is minimal such that the zth literal in Cj is set to true under σX; note that there exists at least one such literal since σX is a satisfying assignment. · Let M(a) := {r2} and M(b) := {r1, r3}.

To show that M is stable, consider a blocking student-college pair {α, β} for M witnessed by S′ ⊆ M(β). By Lemma 1(1), we infer that α must lie in {xi, yi, u1i , u2i , v1 i , v2 i } for some i ∈ [r]. It then suffices to do a case distinction that rules out α being one of the former 2 students, and also being one of the latter 4 students.

For the "if" part, let M be a feasible and stable matching for the constructed SMI-DIVERSE instance. Define the following assignment σX with σX(xi) := true if there exists a clause-college cj such that u1i or u2i is assigned to cj; let σX(xi) := false if there exists a clause-college cj such that v1 i or vz i is assigned to cj. If no such clause-college exists, then the truth value of xi can be arbitrary; e.g., let σX(xi) = true. The constructed assignment satisfies all clauses because of Lemma 1(2). Thus, to complete the proof, it suffices to show that σX is a valid truth assignment.

We note that the reduction behind Theorem 2 can be adapted to show NP-hardness for FI-DIVERSE, even with three types. Proposition 2. FI-DIVERSE remains NP-hard even if t = 3, u∞ = 1, q∞ = 2.

As a final remark on the impact of diversity, we note that if there are only few types t or the maximum capacity q∞ is a constant, then SMTI-DIVERSE is in NP. The reason for this is that the size of a witness set is upper-bounded by min{t, q∞}.

Observation 1. If t or q∞ is a constant, then SMTIDIVERSE is in NP.

The case with few colleges. The NP-hardness reduction behind Theorem 2 produces a college gadget for each variable in order to maintain as few types as possible. This leads to the question of whether the problem remains NP-hard for few colleges. The following theorem answers the question affirmatively. The idea is to reduce from the NP-complete INDEPENDENT SET problem [Garey and Johnson, 1979] and introduce types corresponding to the vertices and the edges in an input graph, and students corresponding to the vertices such that the students assigned to a special college w must correspond to an independent set. We use Lemma 1 to enforce that w receives at least some given number of students. Theorem 3. SMI-DIVERSE is NP-hard even if m = 4, ℓ∞ = 0 and u∞ = 2.

4 Algorithmic Results

This section provides the algorithmic results that together allow us to complete Table 1. The first result deals with the case where the number of students is bounded by a constant.

Theorem 4. SMTI-DIVERSE can be solved in O(n ·m· t+ 2n · (2n+1)n · n2 · t) time.

Proof Sketch. We show how to preprocess an SMTIDIVERSE instance I = (U,W, T, (⪰u, τu)u∈U, (qw, ℓw, uw)w∈W) to obtain an instance I ′ = (U,W ′ , T ′ , (⪰′u , τ ′u )u∈U , (q′w , ℓ′w , u′w )w∈W ) with n students, n2 + n colleges and 2n types which is equivalent in terms of the existence of a feasible and stable matching. It then suffices to solve I ′ in the claimed running time via an exhaustive brute-force procedure.

2n types. Observe that types z, z′ ∈ T which describe the same subset of students, i.e., {u∈U| τu[z]=1} = {u ∈ U | τu[z′ ]=1}, can be merged into a single type ζ. For each feasible matching of I, the students assigned to a college w∈W of two types z, z′ ∈ T merged in this way always adhere to the stricter of the upper and lower quotas of the merged types, i.e., max{ℓw[z], ℓw[z′ ]} and min{uw[z], uw[z′ ]}. Exhaustive merging yields the modified types T ′ with |T ′ |≤2n .

n2 + n colleges. First, note that we can reject an instance with more than n colleges with non-zero lower quotas. To upper-bound the number of colleges with zero lower-quotas, denoted as W0, note that in a stable and feasible matching M every student (say, u) matched to a college fromW0 may only be matched to one of her n most preferred colleges in W0 which has enough upper-quotas to accommodate her. Otherwise there would be an empty zero lower-quota college in W0 which u prefers to M(u), forming a blocking pair.

We employ this observation by defining the following marking procedure. Let us begin by setting W ′ = ∅. Now, for each student u ∈ U, we mark the n most preferred colleges in W0 \ W ′ , resolving ties arbitrarily. Clearly, at the end we obtain a set W ′ of size at most n2 . This is easy to prove via a replacement argument and the above observation that the colleges in W0 \W ′ may be deleted without changing the existence of a stable and feasible matching.

Next, we show that SMTI-DIVERSE can be solved in polynomial time if the number m of colleges and the maximum capacity q∞ of all colleges are constants, using a simple brute-forcing algorithm based on the following observation.

Observation 2. Every feasible matching can assign colleges to at most m · q∞ students.

By the above observation, we only need to guess a subset of at most m · q∞ students which are assigned to colleges, and branch for each student in the guessed set on the choice of one out of m possible colleges. For each branch, we check feasibility and stability in O(2q∞ · n · m · t) time since each college obtains at most q∞ students (see Observation 1).

Proposition 3. SMTI-DIVERSE and FI-DIVERSE can be solved in O(nm·q∞ · (m · q∞)m · 2q∞ · n · m · t) time.

Finally, we turn our attention to instances with a small number of colleges and types, and show that in this case SMTI-DIVERSE also admits a polynomial-time algorithm.

We note that while under such restrictions one can use the bounded-variable ILP Encoding technique [Bredereck et al., 2014, Section 3.1] to show that FI-DIVERSE becomes polynomial-time solvable, the same technique is unlikely to work for SMTI-DIVERSE. That is because two students, even with the same type vectors and the same preferences, may be preferred differently by a college.

However, to witness a blocking pair in a matching, only those students assigned to a college w need to be considered that are least preferred by w among all students assigned to w with the same type vector. We introduce two notations to formally describe such students. Given a matching M, a college v, and a type vector τ ∈ {0, 1}t , let S(M, v, τ) := {u ∈ M(v) | τu = τ} denote the set of students with type vector τ that are assigned to v, and let worst(M, v, τ ) denote the set of students inM(v) with type vector τ that v prefers least:

Proposition 4. Let M be a feasible matching in an SMTIDIVERSE instance. Then, an unmatched student-college pair {u,w} with w ≻u M(u) is blocking M if and only if there is a subset of k students U ′ := {ui1 , . . . , uik } ⊆ M(w) (0 ≤ k ≤ |M(w)|) assigned to w such that

• (i) no two students from U ′ have the same type vector,
• (ii) each student u′ ∈ U ′ belongs to worst(M,w, τu′),
• (iii) w strictly prefers u to each student in U ′ , and
• (iv) M ∪ {{u, w}} \ ({{u, M(u)}} ∪ {{u′ , w} | u′ ∈ U ′ }) is feasible for w.

Proof Sketch. (iii) and (iv) necessarily hold for every set that witnesses that {u,w} is a blocking pair. (i) can be seen to hold for every minimal such set because at most one student from each type vector has to be removed fromM(w) to make the addition of u to M(w) feasible for w. We can achieve (ii) by swapping each student u /∈ worst(M,w, τu) from a minimal witnessing set for a student in worst(M,w, τu). This modification maintains all previous conditions and the fact that the set witnesses that {u, w} is a blocking pair.

Proof Sketch. Let I = (U,W, T = [t], (τu,⪰u)u∈U, (⪰w, qw, ℓw, uw)w∈W) be an instance of SMTI-DIVERSE. We introduce an extra type possessed by each student, and require each college w ∈ W to have no more than qw students for this extra type to encode capacities by types.

Motivated by Proposition 4, we will exhaustively branch, for each college and each type vector τ ∈ {0, 1}t , on the choice of a student wst(wj, τ) ∈ A(wj) ∪ {⊤} who will be in worst(M,wj, τ) for a hypothetical feasible and stable matching M. Here wst(wj, τ) = ⊤ is interpreted as worst(M, wj , τ) = ∅. Moreover we branch to determine the number #(wj , z) ∈ {ℓwj [z], . . . , uwj [z]} of students of each type z ∈ [t] that each college wj ∈ W receives under M.

For each such branch we iteratively try to extend M0 = {{wst(wj, τ),wj} | wj ∈ W, τ ∈ {0, 1}t } to a feasible and stable matching which conforms to the guesses in the branch, one not yet matched student at a time.

More specifically, we only add a student-college pair to the matching if doing so maintains the status that each guessed wst(wj, τ)-student is least preferred among the students assigned to wj with type vector τ, the guessed number of students for each college and type is not exceeded, and there is no induced blocking pair involving the added student and some guessed wst(wj, τ)-students (as witness). To check these conditions and more importantly to upper-bound the number of considered matchings we keep a record in addition to each constructed (partial) matching, the guessed least preferred students wst(wj, τ), τ ∈ {0, 1}t and the guessed numbers #(wj, z) of students, z ∈ [t], wj ∈ W. A record for a set Ui of students is an (m+ 1) × (t + 1)-dimensional integer matrix Q∈{0, . . . , n}(m+1)×(t+1) storing the typespecific number of students assigned to a college, and the number of students assigned to it in total. Two "partial" matchings in a branch can be argued to be equivalent in terms of existence of feasible and stable extensions whenever they have the same record, which is why in each branch we only need to consider at most n(m+1)·(t+1) matchings.

After having considered the last student un, we check whether there exists a record Q with a matching M that corresponds to the information in #(wj, z), i.e., for each college wj ∈ W and each type z ∈ [t] whether Q[j][z] = #(wj, z) holds. We return M once we found a matching fulfilling the above condition. If no such matching is found, we return that we have a "no"-instance. Correctness can be argued using Proposition 4 and the fact that, in each branch, two partial matchings with the same record are equivalent in terms of existence of feasible and stable extensions.

5 Conclusion

We identified and studied a natural, albeit highly intractable, stable matching problem enhanced with diversity constraints (SMTI-DIVERSE). We showed that while SMTIDIVERSE is in general ΣP2 -complete, it is polynomial-time solvable when n (the number of students), m+t (the number of colleges and types), or m+q∞ (the number of colleges and the capacity) is a fixed constant.

For future work, studying SMTI-DIVERSE through the lens of parameterized complexity [Downey and Fellows, 2013; Flum and Grohe, 2006; Niedermeier, 2006; Cygan et al., 2015] may provide further insights into the fine-grained complexity of the problem. We left open whether the problem is FPT parameterized by m+ t. One can also exploit the structure of interactions between students, colleges and types to identify new tractable instances, for instance via the use of notions such as treewidth. Another future research direction is to investigate the trade-off between stability and diversity by allowing few blocking pairs [Abraham et al., 2005; Chen et al., 2018; Mnich and Schlotter, 2020] or few unsatisfied diversity constraints.

Acknowledgments

JC is supported by the WWTF research project (VRG18012). RG and TH are supported by the Austrian Science Fund (FWF, project P31336).