Proportionally Fair Matching via Randomized Rounding (aaai25-33805)

Given finite endpoint type sets \(A\) and \(B\), rational masses \(\mu^A\) and \(\mu^B\), compatible type pairs \(E_0\subseteq A\times B\), rational nonnegative weights \(w_e\), a color map \(\chi:E_0\to[\ell]\), and \(0<\beta<1\), choose nonnegative assignment masses \(x_e\) maximizing \(\sum_{e\in E_0}w_ex_e\), subject to \(\sum_{e\ni a}x_e\le\mu^A_a\), \(\sum_{e\ni b}x_e\le\mu^B_b\), and \(\sum_{\chi(e)=c}x_e\le\beta\sum_{e\in E_0}x_e\) for every \(c\in[\ell]\).

A society is given by its support: disjoint finite endpoint type sets \(A,B\), with positive binary-rational masses \(\mu^A_a,\mu^B_b\). Let \(\tau=|A|+|B|\) be the support size, not the number of possible types; masses need not sum to one.
Input also specifies compatible pairs \(E_0\subseteq A\times B\), nonnegative rational weights \(w_e\), one color \(\chi(e)\in\{1,\ldots,\ell\}\) per pair, and rational \(0<\beta<1\). Write \(m=|E_0|\) and let \(L\) be the total input bit length.
An assignment consists of divisible masses \(x_e\geq0\), with \(\sum_{b:(a,b)\in E_0}x_{ab}\leq\mu^A_a\) and \(\sum_{a:(a,b)\in E_0}x_{ab}\leq\mu^B_b\). It is fair if \(\sum_{\chi(e)=c}x_e\leq\beta\sum_{e\in E_0}x_e\) for every color \(c\); the zero assignment is permitted.
Let \(\mathrm{OPT}\) be the maximum fair assignment weight \(\sum_e w_ex_e\). For rational \(0<\varepsilon<1\), let \(S_\varepsilon\) be the largest total assigned mass among maximum-weight assignments satisfying the same constraints with \(\beta\) replaced by \((1-\varepsilon)\beta\).

For every rational \(0<\varepsilon<1\), can a randomized algorithm, polynomial in \(m,\tau,\ell,L\) and the encoding length of \(\varepsilon\), output an assignment obeying the endpoint capacities, with expected weight at least \(\frac{1-\varepsilon}{2}\mathrm{OPT}\) and probability of fairness at least \(1-2\exp(-\varepsilon^2\beta S_\varepsilon/28)\), or is achieving these guarantees NP-hard?

For discrete weighted bipartite matching, a randomized rounding result reports expected weight at least \(\frac{1-\varepsilon}{2}\mathrm{OPT}\) and fairness probability at least \(1-2\exp(-\varepsilon^2\beta\sum_e z_e/28)\), where \(z\) optimizes the tightened fractional constraints. [Source](https://arxiv.org/html/2412.11238v1#S4.Thmtheorem4.3)
No separate result establishing these guarantees for arbitrary rational endpoint masses was verified.

Conclusion

The guarantees are achievable in deterministic polynomial time. In fact, the algorithm can output a fair assignment of weight exactly \(\mathrm{OPT}\), so its fairness probability is one.

This resolves the stated problem for arbitrary rational endpoint masses. The decisive premise is that assignment masses are divisible.

1. Exact linear programming formulation

For each color \(c\), define \(E_c=\{e\in E_0:\chi(e)=c\}\). Consider the following rational linear program, with one variable \(x_e\) for each compatible pair:

\(\displaystyle \max \sum_{e\in E_0}w_ex_e\),

subject to

• \(\displaystyle x_e\geq 0\) for every \(e\in E_0\);
• \(\displaystyle \sum_{b:(a,b)\in E_0}x_{ab}\leq\mu^A_a\) for every \(a\in A\);
• \(\displaystyle \sum_{a:(a,b)\in E_0}x_{ab}\leq\mu^B_b\) for every \(b\in B\);
• \(\displaystyle \sum_{e\in E_0}\bigl(\mathbf 1_{\{e\in E_c\}}-\beta\bigr)x_e\leq 0\) for every color \(c\).

The last inequality is exactly the specified fairness inequality, after moving its right-hand side to the left. Consequently, the feasible solutions of this program are precisely the fair assignments, and its optimum is \(\mathrm{OPT}\).

The feasible set is nonempty because it contains the zero assignment. For every edge \(e=(a,b)\), nonnegativity and the endpoint constraints imply

\(\displaystyle 0\leq x_{ab}\leq\min\{\mu^A_a,\mu^B_b\}.\)

Thus the feasible set is bounded. It is also closed, being defined by finitely many non-strict linear inequalities. It is therefore compact, and the continuous linear objective attains its maximum.

2. Polynomial bit complexity

We use the standard rational linear programming theorem: a linear program with binary-encoded rational data can be solved in time polynomial in its encoding length; if its feasible set is nonempty and its optimum is finite, an exact rational optimal solution can be returned. This is the polynomial-time linear programming result established through Khachiyan’s algorithm; see [*Khachiyan’s linear programming algorithm*](https://www.sciencedirect.com/science/article/pii/0196677480900024).

Here there are \(m\) variables and \(m+\tau+\ell\) inequalities, counting nonnegativity. Every coefficient is an input rational, zero, one, \(-\beta\), or \(1-\beta\). Computing these coefficients requires polynomial-time rational arithmetic, and each has bit length bounded by a polynomial in \(L\). Hence even a dense encoding of the program has length polynomial in \(m,\tau,\ell,L\).

For completeness, exact output does not require exponentially many bits. When \(m>0\), a linear objective on a nonempty compact polytope has a vertex maximizer. At a vertex, the active constraint normals span the entire variable space: otherwise a nonzero direction orthogonal to them would permit sufficiently small feasible perturbations in both directions, contradicting extremality. Select \(m\) independent active constraints and clear their denominators. The resulting integer system has coefficients and right-hand sides of polynomial bit length, say at most \(H\).

Cramer’s rule expresses each coordinate as a ratio of integer determinants. Each determinant has absolute value at most \(m!2^{mH}\), by expanding over permutations. Thus every coordinate has bit length \(O(mH+m\log m)\), which is polynomial in the input parameters. If \(m=0\), the empty assignment is already optimal.

The algorithm therefore constructs this program and returns an exact optimizer \(x^\star\). Its runtime is polynomial in the requested parameters, including the encoding length of \(\varepsilon\), although it need not use \(\varepsilon\).

3. Verification of both guarantees

Regard this deterministic algorithm as a randomized algorithm whose output distribution is concentrated on \(x^\star\).

By construction, every endpoint capacity is respected and every fairness inequality holds. Moreover,

\(\displaystyle \mathbb E\!\left[\sum_e w_ex^\star_e\right]=\mathrm{OPT}\geq\frac{1-\varepsilon}{2}\mathrm{OPT}.\)

The inequality follows because the zero assignment implies \(\mathrm{OPT}\geq0\), and \(0<\varepsilon<1\).

We also check that \(S_\varepsilon\) is well-defined. Replacing \(\beta\) by \((1-\varepsilon)\beta\) leaves a nonempty compact feasible set, by the same argument as above. Its maximum-weight assignments form a nonempty compact set, so total assigned mass attains a maximum on that set. Summing the endpoint constraints gives

\(\displaystyle 0\leq S_\varepsilon\leq\min\left\{\sum_{a\in A}\mu^A_a,\sum_{b\in B}\mu^B_b\right\}<\infty.\)

Since \(x^\star\) is always fair,

\(\displaystyle \Pr[x^\star\text{ is fair}]=1\geq1-2\exp\!\left(-\frac{\varepsilon^2\beta S_\varepsilon}{28}\right).\)

This proves the requested probability guarantee for every instance, including those whose tightened constraints permit only the zero assignment.

4. Relation to discrete matching

The referenced paper defines its output as a matching, namely a set of edges with no shared endpoints. Its rounding analysis addresses that discrete requirement. [*Proportionally Fair Matching via Randomized Rounding*, Section 3](https://arxiv.org/html/2412.11238v1#S3).

In the present task, the fractional optimizer itself is an admissible assignment. Arbitrary rational endpoint capacities simply become rational right-hand sides of the linear program. No rounding or expansion into individual units is needed.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct: the stated continuous problem is solvable in deterministic polynomial time, and the proposed algorithm satisfies stronger guarantees than requested. No major or minor mathematical issues were found.

1. Agreement with the assigned problem

The prover uses the assignment model in USER_TASK: each variable \(x_e\) represents divisible mass on a compatible pair. There is no integrality or matching requirement.

Consequently, returning a fractional optimizer is an admissible output. This addresses arbitrary rational endpoint masses directly and does not depend on extending the discrete rounding theorem.

2. Exactness of the LP formulation

For each color \(c\), the constraint
\[ \sum_{e\in E_0}\bigl(\mathbf 1_{\{e\in E_c\}}-\beta\bigr)x_e\leq 0 \]
is precisely
\[ \sum_{e\in E_c}x_e\leq\beta\sum_{e\in E_0}x_e. \]

The remaining constraints reproduce nonnegativity and both families of endpoint capacities. The objective reproduces the specified assignment weight. Thus the LP’s feasible assignments and objective agree exactly with the task, and its optimal value is \(\mathrm{OPT}\).

Empty color classes introduce no difficulty: their constraints hold automatically for nonnegative assignments.

3. Feasibility, boundedness, and attainment

The zero assignment satisfies every constraint, so the feasible set is nonempty.

For every compatible pair \(e=(a,b)\), nonnegativity and the two endpoint constraints imply
\[ 0\leq x_e\leq\min\{\mu^A_a,\mu^B_b\}. \]
Both endpoint masses are finite input rationals. Therefore the feasible set is bounded in its finite-dimensional variable space.

The constraints are non-strict linear inequalities, so the feasible set is closed. Compactness and attainment of the continuous objective follow. This reasoning does not require masses to sum to one.

The case \(m=0\) is explicitly handled: the empty assignment is feasible and optimal.

4. Polynomial-time and exact-output claims

The invoked theorem is the standard polynomial-time solvability theorem for explicitly represented rational linear programs, including exact rational optimization when the feasible set is nonempty and the optimum is finite. Its hypotheses are satisfied here. The cited historical reference concerns Khachiyan’s polynomial-time LP algorithm. [*Khachiyan’s linear programming algorithm*](https://www.sciencedirect.com/science/article/pii/0196677480900024)

There are \(m\) variables and \(m+\tau+\ell\) inequalities. The constructed coefficients have polynomial bit length: subtracting the rational \(\beta\) from an indicator introduces only polynomial encoding overhead. Even a dense constraint matrix therefore has encoding length polynomial in the requested parameters.

The supplementary output-length argument is also valid:

• A nonempty compact polytope has a vertex maximizing a linear objective.
• At a vertex, active constraint normals span the variable space. The stated two-sided perturbation argument applies because every inactive constraint has positive slack and there are finitely many constraints.
• Selecting \(m\) independent active constraints gives a nonsingular square system.
• Clearing denominators increases bit length polynomially.
• Cramer’s rule and the bound \(m!2^{mH}\) give polynomial bit length for each coordinate.

This argument remains valid for a feasible polytope of lower dimension; full dimensionality is not an unstated hypothesis.

The algorithm may ignore \(\varepsilon\), since its stronger output guarantee holds for every permitted value. Its runtime consequently satisfies the requested dependence on the encoding length of \(\varepsilon\).

5. Expected-weight guarantee

A deterministic algorithm is a randomized algorithm with a concentrated output distribution. Its expected weight is therefore exactly \(\mathrm{OPT}\).

The zero assignment gives \(\mathrm{OPT}\geq0\), and \(0<\varepsilon<1\) gives
\[ \mathrm{OPT}\geq\frac{1-\varepsilon}{2}\mathrm{OPT}. \]
This also covers zero optimal weight.

6. Definition of \(S_\varepsilon\) and fairness probability

Replacing \(\beta\) by \((1-\varepsilon)\beta\) preserves nonemptiness, closedness, and boundedness. The tightened objective therefore attains its maximum. Its maximizers form a nonempty compact set, so total assigned mass attains a maximum over that set.

Summing each family of endpoint inequalities counts every edge once and yields the stated bound
\[ 0\leq S_\varepsilon\leq \min\left\{\sum_{a\in A}\mu^A_a,\sum_{b\in B}\mu^B_b\right\}<\infty. \]

The returned optimizer is always fair under the original \(\beta\). Hence
\[ \Pr[x^\star\text{ is fair}]=1 \geq1-2\exp\left(-\frac{\varepsilon^2\beta S_\varepsilon}{28}\right). \]
The comparison is valid for every finite \(S_\varepsilon\), including \(S_\varepsilon=0\). Neither computing \(S_\varepsilon\) nor evaluating the exponential is needed by the algorithm.

7. Relation to the discrete reference

The prover accurately identifies the discrete requirement in the referenced paper: a matching is a subset of edges with no shared endpoint. [Section 3 of *Proportionally Fair Matching via Randomized Rounding*](https://arxiv.org/html/2412.11238v1#S3)

That requirement is absent from USER_TASK. The LP argument establishes the continuous result independently of the paper’s rounding analysis.

No repair or additional clarification is needed.

⟨structured verdict parsed — rendered above⟩