Group Fairness and Multi-Criteria Optimization in School Assignment

Formally, there is a set $S$ of $n$ students divided into $g$ possibly overlapping groups $S_1,S_2,\mathrm{\dots },S_g$. There is a set $T$ of $m$ schools, and school $j\in T$ has capacity $C_j$. There is also a bipartite graph $G=(S\cup T,E)$, where $(i,j)\in E$ is an edge if for $i\in S,j\in T$, it is possible to assign student $i$ to school $j$. Let $\overrightarrow{y}$ denote an assignment, where $y_e\in \{0,1\}$ denotes whether for edge $e=(i,j)\in E$, student $i\in S$ is assigned to school $j\in T$. This assignment is feasible if it satisfies the capacity constraint of each school, and each student is assigned to some school¹¹1Note that this is without loss of generality, since we can always add a dummy school with infinite capacity to ensure that every student can be matched. However, this naturally affects the fairness objective. For example, the proportional share of demographic groups can increase from this process. . Let $u_{ij}$ be the (non-negative) utility derived by student $i$, if assigned to school $j$.

Given an assignment $\overrightarrow{y}\in 𝒫$, we define the utility of each group $S_k$ as $U_k(\overrightarrow{y})={\sum }_{i\in S_k}{\sum }_{(i,j)\in E}{u}_{ij}{y}_{(i,j)}.$ Let $\overrightarrow{U}=⟨U_1,U_2,\mathrm{\dots },U_g⟩$. The goal is to find a feasible assignment $\overrightarrow{y}$ that maximizes some fairness function on the utilities perceived by the $g$ groups. Let $f(\cdot )$ be a non-decreasing concave function. Then, a general goal is to maximize

In practice, several functions $f$ can be reasonable. For instance, the celebrated Nash welfare objective sets $f=\log$, and the optimal solution $\overrightarrow{U^{\ast }}$ satisfies the following relation: For any other feasible utility vector $\overrightarrow{U^{\prime }}$, we have the relation:

The utilities $\overrightarrow{U^{\ast }}$ in this allocation are proportional for each of the groups, that is, $U_k^{\ast }\ge \frac{U_k^{\prime }}{g}$, meaning each group gets at least $1/g$ of the utility it would have obtained had it been the only group in the system and the social welfare was maximized. This notion of proportionality is the objective considered in [23]. Note that Nash welfare is a much more general objective, capturing proportionality for various subsets of groups, and the approach in [23] does not extend to Nash welfare.

Other examples of utility functions that we can model include the max-min fairness objective, which maximizes

and tries to make the least happy group as happy as possible. This can be modeled with simple linear constraints without needing the use of a convex function. Any objective over the utilities that has Constant Elasticity of Substitution (CES) with certain parameters also falls in this model. Such functions can be modeled as maximizing

for non-negative real numbers $a_k$. When $r\le 1$, this function is concave and can be maximized in our framework. Note that the $r>1$ case models an inherently unfair allocation, since it is always better to allocate more utility to the best-off group.

Finally, we can also capture group fairness through arbitrary covering or packing constraints where we are explicitly given utility requirements for each group. The objective is to find an assignment where each constraint is satisfied. This can capture general multi-criteria optimization for assignment problems in a non-fairness context. Formally, given $g$ arbitrary constraints, we obtain a solution that can violate the capacities by a small function of $g$, and satisfies the constraints up to an additive function of $g$ and $\left|q_{\max }\right|$, the largest magnitude coefficient in the constraint matrix. We discuss this further below.

Our main contribution is a set of polynomial-time approximation algorithms for this problem for arbitrary fairness objectives. In Section 2, we present two approximation algorithms based on rounding a natural convex programming relaxation, which yield somewhat different guarantees, as summarized in the theorem below.

Note that the latter algorithm is slower but yields better violation of capacities if $g\ll |T|$. For practical school choice scenarios [3], the number of students significantly outweighs the number of available schools, while the number of groups $g$ is typically small, even constant. The above violations are, therefore, quite mild. We substantiate this via our empirical results, which we discuss later.

We also show that the school assignment problem mentioned above is NP-Hard for the max-min fairness objective, even when the number of schools or the number of groups is only two. The latter result extends to the proportionality objective. This motivates the need to relax the capacity constraints (as in Theorem 1) if our goal is to achieve a polynomial time algorithm.

We defer the proofs to Appendix A. We also note that to achieve the proportionality objective, it is known that a capacity violation of $\frac{g}{2}$ is required in the worst-case [23].

Our algorithm uses LP rounding and borrows ideas from the seminal Generalized Assignment Problem (GAP) rounding technique of Lenstra, Shmoys, and Tardos [19, 29]. Their iterative rounding procedure involves the observation that the number of fractional variables in a vertex solution to a linear programming relaxation is bounded. We build on this idea and apply it to a linear program written on paths and cycles instead of assignments, enabling us to combine it with a theorem of Stromquist and Woodall [31]. This approach was recently used in a similar model by the authors in [23], which they called “cake frosting”. This theorem is a consequence of the celebrated ham-sandwich theorem [30], and is, hence, non-constructive. Using this technique, they achieve approximate proportionality while violating the total capacity by $O(g\log g)$, where $g$ is the number of groups.

In contrast, we use convex programming relaxation to handle arbitrary fairness objectives such as proportional fairness, Pareto-optimality, and maximin fairness, vastly generalizing the space of objectives. Our method only loses $O(g^2)$ on the total capacity, while preserving utilities from the fractional relaxation. For instance, our method would achieve exact proportionality, and by Equation 1, it even achieves a generalization of this concept to subsets of groups. Further, we show empirically that the use of convex programming keeps the cake frosting instance very small and hence tractable.

At a high level, our main technical contribution is to show how the cake frosting method can be applied to certain types of fractional solutions, in particular, a vertex solution constructed via GAP rounding of the convex programming relaxation. We hence showcase the full power of the technique in [31]. In addition, as discussed above, our techniques extend smoothly to handle arbitrary covering or packing constraints on the allocations, which is motivated by multi-objective optimization and rank optimization.

We note that the idea of using cake frosting to round fractional solutions has appeared before for packing problems in Grandoni et al. [17], where the authors develop a PTAS for matchings in general graphs with $O(1)$ budget constraints on the set of chosen edges. At a high level, all these approaches – the ones in [17, 23] and our work – apply cake frosting to decompose paths and cycles to approximately preserve constraints, but differ in the details of how the paths and cycles are constructed from the integer or fractional solutions. For instance, in contrast to [23], which defines the frosting function based on schools, we define it based on students, hence avoiding an additive violation on the utility. Further, since [17] consider packing problems, their reduction to cake frosting is entirely different in the technical details.

Recall that there is a set $S$ of $n$ students divided into $g$ possibly overlapping groups sets $S_1,S_2,\mathrm{\dots },S_g$. There is a set $T$ of schools, where school $j$ has capacity $C_j$. Finally, there is a bipartite graph $G=(S\cup T,E)$ between the students and schools that represents possible assignments. An assignment of students to schools is a feasible solution $\overrightarrow{y}\in 𝒬$, where $𝒬$ is the polytope defined by the following constraints:

Let $𝒫$ denote the linear relaxation of $𝒬$, where the last constraint is replaced by $0\le y_{ij}\le 1$. The first step is to write the following convex programming relaxation:

This can be solved in polynomial time. Let the optimal solution to the convex program yield utility vector $\overrightarrow{U^{\ast }}$. We now need to round the following set of constraints so that the $\{y_{ij}\}$ values are integer. Denote this formulation as (LP1).

We now present two rounding algorithms that yield the corresponding guarantees in Theorem 1.

The first rounding algorithm is similar to rounding for generalized assignment (GAP) [19, 29] and is presented in Algorithm 1. We remark that the iterative procedure from Step 1-6 is not necessary; the same can be achieved with a single LP solution. We present it this way for ease of exposition. We show that it achieves the following guarantee, yielding the first part of Theorem 1.

While the previous section provides a polynomial-time solution, we can improve the capacity violation bound, albeit at the cost of increased runtime. We achieve this by replacing the last step in Algorithm 1 with a more sophisticated ’cake frosting’ technique, building on the work of [23]. We show the following theorem, corresponding to the second part of Theorem 1.

Our algorithm runs in the following steps, which build on Algorithm 1.

1. 1.

   Solve the linear programming relaxation LP, fix and remove the integral variables, and find a vertex solution. Let $E$ be the set of fractional variables, and $S^{\prime }$ be the remaining students.

2. 2.

   Rewrite LP on the variables $E$ and without the capacity constraints Equation 3.

3. 3.

   Keep eliminating integer variables, stopping at a vertex solution where all variables are fractional. Let $E^{\prime }$ be the remaining variables and $S^{\prime \prime }$ be the remaining students.

4. 4.

   Set an arbitrary $y_{ij}>0$ to $1$ for each $i\in S^{\prime \prime }$.

We next generalize Theorem 7. We first apply Algorithm 1 to the linear programming relaxation, stopping before Step 7. We then follow the procedure in Section 2.3 and sequentially apply Algorithms 2 and 3 to the fractional solution. To set up the cake frosting game to apply Algorithm 3, we view each of the $r$ constraints in Equation 4 as a player of the cake frosting instance. Define $u_{even}(\mathrm{\ell },i):=q_{ij}^{\mathrm{\ell }}$ where $(i,j)$ is the even matching edge adjacent to $j$ and define $u_{odd}(\mathrm{\ell },i)$ similarly. The only steps that are different are the assignment steps – Step 3 in Algorithm 2 and Step 7 in Algorithm 3. Here, we perform an arbitrary assignment of the students to the schools. We present all the details in Algorithm 4 for completeness.

We next show that if the constraints $Q$ have an additional monotonicity structure, then we can generalize Theorem 6 without the additive loss in the constraints. We say that $Q$ satisfies monotonicity if for each student $i$, there is an ordering ${⪰}_i$ of the schools $j_1{⪰}_i{j}_2{⪰}_i\mathrm{\dots }{⪰}_i{j}_m$ such that for all $\mathrm{\ell }\in \{1,2,\mathrm{\dots },r\}$ and $k\in \{1,2,\mathrm{\dots },m-1\}$, we have $q_{i{j}_k}^{\mathrm{\ell }}\ge q_{i{j}_{k+1}}^{\mathrm{\ell }}$.

As a special case, we consider the setting in [18]. Here, every student ranks the schools it has an edge to, and this ranking may have ties. Let $r$ be the largest rank any student has, which can be much smaller than the number of schools. Given a matching, the rank of edge $(p,q)$ is the rank of school $q$ in student $p$’s ranking. A matching $M$ has signature $\sigma =({\sigma }_1,{\sigma }_2,\mathrm{\dots },{\sigma }_r)$ if it has ${\sigma }_t$ rank $t$ edges for every $t\in [r]$. We say that signature $\sigma$ weakly dominates⁵⁵5The authors of [18] use “cumulatively better than”. signature $\rho$, or $\sigma \succ \rho$ if

Given an input signature $\rho$, the goal is to find a matching whose signature weakly dominates $\rho$. We term this the matching with ranking problem. We have the following theorems, which directly follow from the observation that the constraints satisfy the monotonicity assumption. At each step where, for some set $X$, we assign $i$ to $\arg {\max }_{j\in X}{u}_{ij}$, we instead assign it to its most preferred school from $X$. This preserves the signature of any fractional assignment. Our approach yields faster $n^{O(r)}$ time deterministic algorithms at the cost of small violations in capacities, whereas the algorithm in [18] is randomized and takes $n^{O(r^2)}$ time. This concludes the proof of Theorem 5.