Achieving Balanced Representation in School Choice with Diversity Goals (aaai25-33547)

Given rational group masses \(\mu_u\) with \(\sum_{u\in U}\mu_u=1\), capacity mass \(\kappa\), ranked quota masses \(\eta_t^j\), and group targets \(\delta_u\), decide whether there exists \(f_{u,t,j}\ge0\) with \(t\in u\cup\{t_0\}\) such that \(\sum_{t,j}f_{u,t,j}\le\mu_u\), \(\sum_{u:t\in u}f_{u,t,j}\le\eta_t^j\), \(\sum_{u,t,j}f_{u,t,j}\le\kappa\), every group receives at least \(\delta_u\) mass, and \(f\) is rank-maximal by maximizing total selected mass and then lexicographically maximizing \(R_j=\sum_{u,t}f_{u,t,j}\).

Let \(T\) be a set of \(m\) privilege types. A society is given by its support: a list \(U\subseteq 2^T\) of \(\tau\) distinct groups with positive binary-rational masses \(\mu_u\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible type combinations; the empty group is allowed.
Input also includes \(r\ge1\) ordered ranks, nonnegative binary-rational capacity \(\kappa\), quota masses \(\eta_t^j\), and group targets \(\delta_u\). Let \(L\) be the total input bit length.
Introduce a general type \(t_0\notin T\), available to every group, with \(\eta_{t_0}^r=\kappa\) and \(\eta_{t_0}^j=0\) for \(j<r\). Smaller ranks have higher priority; quotas are separate capacities for each type and rank.
An allocation consists of real masses \(f_{u,t,j}\ge0\), defined only for \(t\in u\cup\{t_0\}\) and \(1\le j\le r\). Mass may be split among eligible types and ranks, but each portion is counted once.
Write \(a_u=\sum_{t,j}f_{u,t,j}\), \(F=\sum_u a_u\), and \(R_j=\sum_{u,t}f_{u,t,j}\). Feasibility means \(a_u\le\mu_u\), \(\sum_{u:t\in u\cup\{t_0\}}f_{u,t,j}\le\eta_t^j\), and \(F\le\kappa\).
Call an allocation rank-maximal if it lexicographically maximizes \((F,R_1,\ldots,R_r)\) over all feasible allocations, without imposing the group targets. Ties are allowed.
Decide whether a rank-maximal allocation exists with \(a_u\ge\delta_u\) for every \(u\in U\).

Is this decision problem solvable in polynomial time in \(m,\tau,r,L\), or is it NP-hard?

Discrete validity checking admits a polynomial-time flow algorithm, as stated by [Sun and Yokoo](https://ojs.aaai.org/index.php/AAAI/article/download/33547/35702). No result settling this exact rational-mass formulation was identified in the literature search.

Result

The decision problem is solvable in polynomial time in \(m,\tau,r,L\).

The algorithm computes the lexicographic optimum without group targets, retains every allocation attaining that optimum, and then checks whether any such allocation satisfies the targets. Exact rational linear programming suffices; below we also prove that all intermediate optimum values have polynomial encoding length.

1. A polynomial-size allocation polytope

Let \(E=\{(u,t,j):u\in U,\ t\in u\cup\{t_0\},\ 1\le j\le r\}\). There are

\(n=|E|=r\sum_{u\in U}(|u|+1)\le r\tau(m+1)\)

allocation variables.

Let \(P\subseteq\mathbb R^E\) be defined by precisely the feasibility constraints in the question:

• \(f_{u,t,j}\ge0\) for every \((u,t,j)\in E\);
• \(\sum_{t\in u\cup\{t_0\}}\sum_{j=1}^r f_{u,t,j}\le\mu_u\) for every \(u\in U\);
• \(\sum_{u:(u,t,j)\in E}f_{u,t,j}\le\eta_t^j\) for every type and rank;
• \(\sum_{(u,t,j)\in E}f_{u,t,j}\le\kappa\).

Thus \(P\) has \(n+\tau+(m+1)r+1\) inequalities and a polynomial-size rational description. Its variables refer only to the supplied support \(U\); no enumeration of \(2^T\) is required.

The zero allocation belongs to \(P\). Moreover, nonnegativity and the group constraints imply \(0\le f_{u,t,j}\le\mu_u\le1\). Consequently, \(P\) is a nonempty compact polytope.

Define linear objectives \(c_0(f)=F(f)\) and \(c_j(f)=R_j(f)\) for \(1\le j\le r\). Every objective coefficient is either zero or one.

As a useful check, \(\max_{f\in P}F(f)=\min\{\kappa,1\}\). The upper bound follows from total capacity and \(\sum_u\mu_u=1\). To attain it, put \(s=\min\{\kappa,1\}\), assign \(f_{u,t_0,r}=s\mu_u\), and set every other variable to zero. All group constraints hold because \(s\le1\), and the general-type quota and total capacity hold because the total assigned mass is \(s\le\kappa\).

2. Compute the entire set of rank-maximal allocations

Set \(P_{-1}=P\). For \(i=0,1,\ldots,r\), sequentially compute

\(\alpha_i=\max\{c_i(f):f\in P_{i-1}\}\),

and define

\(P_i=\{f\in P_{i-1}:c_i(f)=\alpha_i\}\).

Each step maximizes a linear function over a nonempty compact polytope. Hence its maximum is attained, and \(P_i\) remains nonempty and compact. Each step adds only one equality.

Claim. \(P_r\) is exactly the set of rank-maximal allocations.

Proof. If \(f\in P_r\), then \(c_i(f)=\alpha_i\) for every \(i\). Suppose a feasible allocation \(g\) had a lexicographically larger objective vector, and let \(i\) be its first differing coordinate. Its preceding coordinates equal \(\alpha_0,\ldots,\alpha_{i-1}\), so \(g\in P_{i-1}\). But \(c_i(g)>\alpha_i\), contradicting the definition of \(\alpha_i\).

Conversely, suppose \(f\in P\setminus P_r\). Let \(i\) be the first index for which \(f\notin P_i\). Then \(f\in P_{i-1}\), and therefore \(c_i(f)<\alpha_i\). Any \(g\in P_i\) agrees with \(f\) on all preceding coordinates and has a larger coordinate at index \(i\). Thus \(f\) is not rank-maximal. This proves the claim.

Now check feasibility of the rational linear system consisting of \(f\in P_r\) and

\(\sum_{t\in u\cup\{t_0\}}\sum_{j=1}^r f_{u,t,j}\ge\delta_u\quad\text{for every }u\in U.\)

By the claim, this system is feasible exactly when the answer to the original question is yes. In particular, the targets enter only this final feasibility check.

3. Exact bit complexity

We use the standard polynomial-time rational linear-programming theorem: rational LP feasibility is decidable in polynomial time in the binary encoding length, and a finite attained optimum can be computed exactly in polynomial time. See [Karger’s notes on polynomial-time LP algorithms](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).

To apply this theorem repeatedly, we must bound the encoding lengths of the added values \(\alpha_i\). We give a uniform bound using vertices of the original polytope \(P\).

Write \(P=\{f:Af\le b\}\), including nonnegativity among these inequalities. Every entry of \(A\) belongs to \(\{-1,0,1\}\). Let \(D\) be the product of the denominators of all numerical input entries, and put \(B=\max\{1,\max_\ell|Db_\ell|\}\). Both \(D\) and \(B\) have binary encoding length \(O(L)\).

At any vertex \(v\) of \(P\), the active constraint normals span \(\mathbb R^n\). Indeed, otherwise a nonzero direction orthogonal to every active normal would allow sufficiently small perturbations in both directions while preserving all inequalities, contradicting that \(v\) is a vertex.

We can therefore select \(n\) independent active constraints, giving \(Mv=b'\), where \(M\) is a nonsingular integer matrix with entries in \(\{-1,0,1\}\). Let \(M_k\) be obtained by replacing column \(k\) of \(M\) by \(Db'\). Cramer’s rule gives

\(v_k=\dfrac{\det M_k}{D\det M}.\)

Hadamard’s determinant inequality gives

\(1\le|\det M|\le n^{n/2}\quad\text{and}\quad|\det M_k|\le Bn^{n/2}.\)

The second bound follows because the replacement column has Euclidean norm at most \(B\sqrt n\), and every other column has norm at most \(\sqrt n\).

For any objective \(c_i\), its coefficients are zero or one. Thus \(c_i(v)\) has denominator \(D\det M\) and a numerator of absolute value at most \(nBn^{n/2}\). Its rational encoding length is consequently

\(O\!\left(L+n\log(n+1)\right).\)

It remains to justify applying this bound to every \(\alpha_i\). Each \(P_i\) is the set maximizing a linear function over \(P_{i-1}\), so it is a face of \(P_{i-1}\). A vertex of such a face is also a vertex of the containing polytope: if that vertex were a nontrivial convex combination of two points of the containing polytope, maximality and linearity would force both points into the maximizing face, contradicting extremality there.

Inductively, every vertex of \(P_i\) is a vertex of \(P\). Since a nonempty compact polytope has a vertex, choose one in \(P_i\); at that vertex, \(c_i=\alpha_i\). Hence every \(\alpha_i\) has the uniform polynomial encoding bound above. There is no successive growth beyond that bound.

Each intermediate LP therefore has polynomially many variables and constraints, with polynomially encoded rational coefficients. The final target system has the same property.

4. Conclusion

The procedure uses at most \(r+1\) exact LP optimizations followed by one exact LP feasibility check. Its total running time is polynomial in \(m,\tau,r,L\), and a feasible final LP also supplies a rational rank-maximal allocation meeting all targets.

This proof directly settles the rational-mass formulation. It does not require extending the discrete flow algorithm of [Sun and Yokoo, Theorem 5](https://ojs.aaai.org/index.php/AAAI/article/download/33547/35702).

⟨structured verdict parsed — rendered above⟩

The proof establishes polynomial-time solvability under the intended interpretation that quota masses are nonnegative. The LP construction, lexicographic characterization, and encoding bounds are correct. There is one minor clarification concerning that input-domain assumption.

1. Allocation polytope

The variable set includes exactly the eligible group–type–rank triples. Its size satisfies
\[ n=r\sum_{u\in U}(|u|+1)\le r\tau(m+1). \]
The listed constraints reproduce the task’s feasibility conditions, including counting each allocated portion once and imposing the global capacity separately from individual quotas.

The constraint count is correct, including quota constraints with no eligible variables. The description has polynomial encoding length; even a dense representation remains polynomial in the stated parameters. No enumeration of unsupported groups occurs.

Nonnegativity and the group constraints give
\[ 0\le f_{u,t,j}\le\mu_u\le1. \]
Thus boundedness is justified. Closedness follows from the finite system of non-strict linear inequalities.

Minor issue: The assertion that the zero allocation belongs to \(P\) uses nonnegativity of every quota \(\eta_t^j\). This is the natural interpretation of “quota masses” as capacities, but the prover should state it explicitly. If negative quotas were permitted, even a constraint with an empty sum could make \(P\) empty, invalidating the subsequent nonemptiness assertions.

The calculation
\[ \max_{f\in P}F(f)=\min\{\kappa,1\} \]
is correct under that interpretation. The proposed assignment respects every group bound, the general-type quota, and the global capacity. All other quota usages are zero.

2. Sequential lexicographic optimization

Each optimization is over a nonempty compact polytope, so its optimum is attained. Intersecting with the corresponding optimum equality preserves nonemptiness and compactness.

Both directions of the characterization of \(P_r\) are correct:

• For an allocation in \(P_r\), the first coordinate at which a purportedly better allocation differs would contradict the corresponding optimization.
• For an allocation outside \(P_r\), its first failed optimum equality identifies a strictly smaller coordinate. Any allocation in the corresponding \(P_i\) agrees on all preceding coordinates and improves that coordinate.

The arguments also cover \(i=0\), when the preceding-coordinate condition is empty.

Consequently, \(P_r\) retains all rank-maximal allocations, including ties. Adding the group targets only after constructing this set matches the task exactly.

The redundancy of the final rank coordinate, since
\[ F=\sum_{j=1}^rR_j, \]
does not invalidate the procedure.

3. Exact rational encoding bounds

The integer coefficient matrix claim is correct: every original constraint coefficient lies in \(\{-1,0,1\}\).

The product \(D\) clears every original right-hand-side denominator. Its binary length is bounded by the sum of the input denominator lengths, hence by \(O(L)\). The same bound holds for the encoding length of \(B\).

The active-normal argument correctly applies even when \(P\) is lower-dimensional: failure to span the ambient space would permit sufficiently small feasible perturbations in both directions, contradicting extremality. Therefore the selected matrix \(M\) is nonsingular.

The scaled Cramer formula
\[ v_k=\frac{\det M_k}{D\det M} \]
is correct. Both Hadamard bounds are also correct:
\[ 1\le|\det M|\le n^{n/2}, \qquad |\det M_k|\le Bn^{n/2}. \]
The latter follows from one column having norm at most \(B\sqrt n\) and all remaining columns having norm at most \(\sqrt n\).

All coordinates obtained from this basis share the displayed denominator. Summing at most \(n\) coordinates therefore gives the claimed objective numerator bound and encoding length
\[ O\!\left(L+n\log(n+1)\right). \]
Reduction to lowest terms cannot increase these bounds.

There is no omitted zero-dimensional-variable case: positive support masses summing to one imply \(\tau\ge1\), and the general type together with \(r\ge1\) implies \(n\ge1\).

4. Why the uniform bound applies at every stage

The maximizing-face argument is correct. If a point of a maximizing face is expressed as a convex combination of points of the containing polytope, linearity forces both points to attain the same maximum. Thus a vertex of the face remains a vertex of the containing polytope.

Induction therefore shows that every intermediate vertex is an original vertex of \(P\). Each nonempty compact polytope \(P_i\) has a vertex, and that vertex attains \(\alpha_i\). This justifies the uniform bound on every added equality without cumulative encoding growth.

5. LP theorem and total complexity

The invoked theorem—polynomial-time feasibility and exact optimization for explicitly represented rational LPs—is applicable. Every intermediate system has rational coefficients of polynomial encoding length; every optimization has a finite attained optimum. The cited [Karger notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) discuss polynomial-time LP algorithms, feasibility–optimization equivalence, and recovery of exact optima using encoding bounds.

The final target system is likewise a polynomial-size rational LP. Negative targets, if allowed, cause no difficulty; excessive targets are handled by infeasibility.

There are \(r+1\) optimizations and one feasibility check, so the total running time is polynomial in \(m,\tau,r,L\). The claimed rational witness is also justified by rational LP feasibility.

Minimum requested clarification: Explicitly state that quota masses are nonnegative capacities, as intended in the task. No additional mathematical argument is needed.

⟨structured verdict parsed — rendered above⟩