d4-conf-atal-2022-0160 (d4-conf-atal-2022-0160)

Given finite student types \(U\) with rational masses \(\mu_a\), project types \(V\) with rational slot masses \(q_b\), admissible type pairs \(E\), a per-capita grant limit \(\kappa\), and a strict priority order on \(E\), compute a feasible assignment \(x_{ab}\geq 0\) that lexicographically maximizes the masses assigned to type pairs in priority order, subject to student, project, and grant capacities.

Let \(U\) be the student types and \(V\) the project types, with \(\tau=|U|\) and \(m=|V|\). A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not all possible types.
Student masses satisfy \(\mu_a>0\) and \(\sum_{a\in U}\mu_a=1\). Each project type has a positive binary-rational slot mass \(q_b\), measured in the same units as student mass; project slot masses need not sum to one.
The input also contains committee-approved admissible pairs \(E\subseteq U\times V\), a strict total priority order \(e_1,\ldots,e_r\) on \(E\), and a nonnegative binary-rational per-capita grant limit \(\kappa\). Pairs outside \(E\) cannot receive assignments.
A feasible assignment consists of rational masses \(x_{ab}\geq0\) for \((a,b)\in E\), satisfying \(\sum_{b:(a,b)\in E}x_{ab}\leq\mu_a\), \(\sum_{a:(a,b)\in E}x_{ab}\leq q_b\), and \(\sum_{(a,b)\in E}x_{ab}\leq\kappa\). Mass may be split, and students and slots may remain unassigned.
The objective is to compute an assignment maximizing \((x_{e_1},\ldots,x_{e_r})\) lexicographically: at the first differing coordinate, the larger assigned mass is preferred. Student preferences impose no additional constraints. Let \(L\) be the total binary input length.

Is computing this lexicographically optimal assignment solvable in polynomial time in \(m,\tau,|E|,L\), or is it NP-hard?

For discrete students and projects with unit capacities and an integer upper bound on funded pairs, a polynomial-time greedy mechanism returns a lexicographically optimal matching ([source](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p687.pdf)). This discrete result does not classify the problem with divisible rational masses.

Result

Computing the lexicographically optimal assignment is polynomial-time solvable in \(m,\tau,|E|,L\). A greedy algorithm suffices, and its output is unique.

The [cited paper](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p687.pdf) establishes a discrete greedy result. The proof below establishes the divisible rational case directly from the stated constraints.

Algorithm

Write \(r=|E|\) and \(e_i=(a_i,b_i)\). Maintain residual student masses \(s_a\), residual project capacities \(t_b\), and residual grant capacity \(g\), initialized by
\[ s_a=\mu_a,\qquad t_b=q_b,\qquad g=\kappa. \]

For \(i=1,\ldots,r\), in the given priority order, set
\[ x_{e_i}=\min\{s_{a_i},t_{b_i},g\}, \]
and then update
\[ s_{a_i}\leftarrow s_{a_i}-x_{e_i},\qquad t_{b_i}\leftarrow t_{b_i}-x_{e_i},\qquad g\leftarrow g-x_{e_i}. \]

Return all \(r\) coordinates. When \(r=0\), return the empty assignment.

Proof of feasibility

Initially, every residual capacity is nonnegative. At each step, the assigned mass is nonnegative and no larger than any of the three residual capacities it consumes. Thus all residual capacities remain nonnegative.

After the last step, the update rules give
\[ s_a=\mu_a-\sum_{b:(a,b)\in E}x_{ab},\qquad t_b=q_b-\sum_{a:(a,b)\in E}x_{ab},\qquad g=\kappa-\sum_{e\in E}x_e. \]
Their nonnegativity proves every required capacity inequality. All coordinates are rational because the algorithm uses only comparison and subtraction of rational numbers.

Proof of lexicographic optimality

Fix a step \(i\). Before that step, its relevant residual capacities are
\[ s_{a_i} =\mu_{a_i}-\sum_{\substack{j<i\\a_j=a_i}}x_{e_j}, \qquad t_{b_i} =q_{b_i}-\sum_{\substack{j<i\\b_j=b_i}}x_{e_j}, \qquad g=\kappa-\sum_{j<i}x_{e_j}. \]

Let \(y\) be any feasible assignment satisfying
\[ y_{e_j}=x_{e_j}\qquad\text{for every }j<i. \]
The student capacity constraint and nonnegativity of all remaining coordinates imply
\[ y_{e_i} \leq \mu_{a_i}-\sum_{\substack{j<i\\a_j=a_i}}y_{e_j} =s_{a_i}. \]
The project capacity constraint similarly implies
\[ y_{e_i}\leq t_{b_i}, \]
and the grant constraint implies
\[ y_{e_i}\leq\kappa-\sum_{j<i}y_{e_j}=g. \]
Consequently,
\[ y_{e_i}\leq\min\{s_{a_i},t_{b_i},g\}=x_{e_i}. \]

This bound is attainable while preserving the preceding coordinates: assign the greedy value to \(e_i\) and assign zero to every later edge. The feasibility invariant proves that this partial assignment is feasible. Here the permission to leave students, slots, and grant capacity unused is essential.

Now take any feasible \(y\neq x\), and let \(i\) be its first differing coordinate. The preceding bound applies because \(y\) and \(x\) agree before \(i\). Since they differ at \(i\), it gives
\[ y_{e_i}<x_{e_i}. \]
Thus \(x\) is lexicographically larger than every other feasible assignment, proving both optimality and uniqueness.

Polynomial bit complexity

It remains to verify that exact rational arithmetic and the output have polynomial size.

Write the input capacity rationals \(\mu_a,q_b,\kappa\) as \(p_j/d_j\), with nonnegative integer numerators and positive integer denominators represented in binary. Let
\[ N=\tau+m+1,\qquad D=\prod_{j=1}^{N}d_j. \]
Since the denominator encodings form part of the input,
\[ \log_2 D=\sum_{j=1}^{N}\log_2 d_j\leq L. \]
Hence \(D\) has \(O(L)\) bits.

Scale every capacity by \(D\). The resulting capacities
\[ C_j=p_j(D/d_j) \]
are integers with \(O(L)\) bits: both \(p_j\) and \(D\) have \(O(L)\) bits. Run the algorithm on these integers. Scaling by the common positive factor \(D\) commutes with minimum and subtraction, so the integer algorithm computes exactly \(D\) times the rational assignment.

Every residual integer remains between zero and its initial capacity. Every assigned integer is bounded by an initial capacity. Therefore all numbers manipulated during the greedy scan have \(O(L)\) bits.

Using elementary integer arithmetic:

• Constructing \(D\) and the scaled capacities takes \(O(NL^2)\) bit operations.
• Each edge requires a constant number of comparisons and subtractions on \(O(L)\)-bit integers, so the scan takes \(O(rL)\) bit operations.
• Each output coordinate can be written as \(X_i/D\), using \(O(L)\) bits, so the complete output has \(O(rL)\) bits. Reduction to lowest terms, if desired, also takes polynomial time.

Including input parsing and indexing, the total running time is polynomial in \(m,\tau,|E|,L\). The algorithm processes only the explicitly listed supported student types; it does not enumerate possible types or expand rational masses into discrete individuals.

⟨structured verdict parsed — rendered above⟩

Verdict

The prover resolves the assigned problem correctly: computing the lexicographically optimal assignment is polynomial-time solvable, and the assignment is unique. The proof is rigorous under the stated rational input model. No major or minor mathematical issues were found.

Step-by-step verification

• The algorithm matches the problem’s constraints.

Each admissible pair consumes exactly three resources: its student mass, its project slot mass, and the common grant capacity. The algorithm assigns the minimum of their residual capacities. It processes precisely the explicitly listed admissible pairs in the supplied priority order.

The argument introduces no additional requirements concerning student preferences, full assignment, or maximum total assigned mass.

• Feasibility is proved correctly.

Initially, every residual is nonnegative under the input assumptions. At each iteration, the assigned mass is nonnegative and does not exceed any residual it consumes. Subtraction therefore preserves nonnegativity.

The final residual identities account for every assigned coordinate exactly once in the appropriate student, project, and grant sums. Consequently, residual nonnegativity implies all three families of capacity inequalities. Rationality follows because minimum and subtraction preserve rational values.

• The coordinatewise upper bound has the correct quantifiers.

At step \(i\), the prover considers an arbitrary feasible assignment \(y\) agreeing with the greedy assignment on every earlier coordinate.

In the student constraint, the earlier incident assignments can be subtracted exactly because of that agreement. Every other coordinate in the same constraint is nonnegative, so omitting those coordinates gives a valid upper bound on \(y_{e_i}\). The same reasoning applies to the project constraint and the grant constraint.

Thus the displayed conclusion
\(y_{e_i}\leq\min\{s_{a_i},t_{b_i},g\}=x_{e_i}\)
is justified. It does not assume agreement on any later coordinate.

• Attainability and the lexicographic conclusion are valid.

The proposed witness retains the greedy prefix through coordinate \(i\) and sets every later coordinate to zero. The feasibility invariant applies to that prefix, and adding zero coordinates consumes no further capacity. This establishes attainability of the bound while fixing all preceding coordinates.

For every feasible \(y\neq x\), finiteness of the coordinate list ensures a first differing coordinate exists. The preceding upper bound applies there. Since the coordinates differ, the weak inequality becomes strict: \(y_{e_i}<x_{e_i}\). This is exactly the stated lexicographic comparison.

Therefore optimality and uniqueness both follow. No exchange argument or external optimization theorem is required.

• The bit-complexity analysis is sound.

Under the stated binary rational representation, the denominator encodings contribute to \(L\), so the bound \(\log_2 D\leq L\) is valid. Hence \(D\) has \(O(L)\) bits.

Each scaled capacity \(p_j(D/d_j)\) is an integer because \(d_j\) divides \(D\). Both factors have \(O(L)\) bits, so their product also has \(O(L)\) bits. Scaling by the common positive denominator preserves the algorithm’s minimum and subtraction operations.

Residuals remain between zero and their initial scaled capacities. Assigned integers are also bounded by initial capacities. Thus arithmetic during the scan operates on \(O(L)\)-bit integers.

The stated \(O(NL^2)\) preprocessing bound is compatible with elementary multiplication and exact division. The scan uses a constant number of comparisons and subtractions per edge, giving the stated \(O(rL)\) arithmetic bound. The output representation \(X_i/D\) has \(O(L)\) bits per coordinate. Parsing and indexing introduce only polynomial overhead.

• Edge cases and scope are adequately covered.

The empty admissible-pair set is explicitly handled. When \(\kappa=0\), or any relevant residual becomes zero, the minimum rule assigns zero and preserves every invariant. Isolated supported student types and project types cause no difficulty.

The algorithm neither enumerates unsupported student types nor expands rational masses into individuals. Its complexity therefore addresses the requested support-based input model.

The [cited paper](https://www.ifaamas.org/Proceedings/aamas2022/pdfs/p687.pdf) supplies discrete background; the continuous proof does not depend on applying its theorem.

Issues and required clarification

None. No additional lemma, assumption, or clarification is needed to verify the claimed result.

⟨structured verdict parsed — rendered above⟩