Answer: Polynomial-time solvable with the requested guarantee: a rational \(c\gamma\)-stable mass matching of mass at least \(\frac23\mathrm{OPT}\) can be returned in time polynomial in \(m,\tau,L\).
Theorem 3.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMax-𝑐𝛾-smti can be 3 2-approximated in O((𝑠+ 𝑡)|𝐸|) time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite left and right type sets \(A\) and \(B\), rational masses \(\mu_a\) and \(\nu_b\), and contract types \(e\in\mathcal E\) with endpoints \(a(e),b(e)\), preference values \(p_a(e),p_b(e)\), unmatched values, and thresholds \(0<\gamma_{v,e}<\delta_{v,e}\), find a mass matching \(x\ge0\) satisfying \(\sum_{e:a(e)=a}x_e\le\mu_a\) and \(\sum_{e:b(e)=b}x_e\le\nu_b\), maximizing \(\sum_e x_e\), subject to no contract \(e=(a,b)\) having positive masses on statuses \(f,g\in\mathcal E\cup\{\varnothing\}\) such that either \(p_a(e)-p_a(f)\ge\gamma_{a,e}\) and \(p_b(e)-p_b(g)\ge\delta_{b,e}\), or \(p_a(e)-p_a(f)\ge\delta_{a,e}\) and \(p_b(e)-p_b(g)\ge\gamma_{b,e}\). The approximation version asks for a \(c\gamma\)-stable matching with matched mass at least \(\frac{2}{3}\) of the optimum.
A society is given by its support: disjoint finite left and right type sets \(A,B\), with positive binary rational masses \(\mu_a,\nu_b\) summing jointly to \(1\). Let \(\tau=|A|+|B|\) be the support size, not the number of possible types; let \(m=|\mathcal E|\) and \(L\) be the total input bit length.
Each listed acceptable contract \(e\in\mathcal E\) has endpoints \(a(e)\in A,b(e)\in B\); parallel contracts are allowed. Endpoint values \(p_v(e)\ge0\), unmatched values \(p_v(\varnothing)\le0\), and thresholds \(0<\gamma_{v,e}<\delta_{v,e}\) are finite binary rationals. Preferences may have ties; no tie-breaking enters stability. There are no critical types or critical contracts.
Write \(q_a=\mu_a,q_b=\nu_b\) and let \(\mathcal E(v)\) denote incident contracts. A mass matching is \(x\in\mathbb R_{\ge0}^{\mathcal E}\) with \(\sum_{e\in\mathcal E(v)}x_e\le q_v\). Status masses are \(s_v(f)=x_f\) for \(f\in\mathcal E(v)\) and \(s_v(\varnothing)=q_v-\sum_{f\in\mathcal E(v)}x_f\).
Call \(x\) \(c\gamma\)-stable if no contract \(e=(a,b)\) has statuses \(f\in\mathcal E(a)\cup\{\varnothing\}\), \(g\in\mathcal E(b)\cup\{\varnothing\}\) with \(s_a(f)>0,s_b(g)>0\) satisfying either \(p_a(e)-p_a(f)\ge\gamma_{a,e}\) and \(p_b(e)-p_b(g)\ge\delta_{b,e}\), or \(p_a(e)-p_a(f)\ge\delta_{a,e}\) and \(p_b(e)-p_b(g)\ge\gamma_{b,e}\).
Let \(\mathrm{OPT}\) be the maximum of \(\sum_e x_e\) over such stable mass matchings.
Does this problem admit an algorithm polynomial in \(m,\tau,L\) returning a rational \(c\gamma\)-stable mass matching of mass at least \(\frac23\mathrm{OPT}\), or is achieving this approximation guarantee NP-hard?
The discrete maximum-size \(c\gamma\)-stable matching problem, including critical vertices and contracts, admits a polynomial-time \(\frac32\)-approximation. [Discrete result](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p409.pdf)
For unit vertex capacities, the corresponding threshold-stable fractional matching problem admits a polynomial-time \(\frac32\)-approximation even on arbitrary graphs; this covers equal type masses after normalization. No result settling the stated arbitrary-rational-mass problem was located. [Fractional result](https://arxiv.org/html/2409.16173v2)
The arbitrary-rational-mass problem admits the requested approximation: one can compute a rational \(c\gamma\)-stable mass matching \(x\), in time polynomial in \(m,\tau,L\), satisfying
\( \displaystyle \sum_{e\in\mathcal E}x_e\ge \frac23\mathrm{OPT}. \)
The algorithm combines the four-copy preference construction with a polynomial-time stable-allocation algorithm. Capacity expansion is used only in the approximation proof.
For a bipartite contract graph with strict preferences, vertex quotas, and edge upper bounds, an allocation \(y\) is ordinarily stable if there is no edge \(h\) below its upper bound such that both endpoints either have unused quota or have positive allocation on an edge ranked below \(h\).
We use the established theorem that such a stable allocation can be found in strongly polynomial time. The augmenting-path algorithms preserve integrality when quotas and upper bounds are integers. See [Baïou–Balinski’s corrected paper](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302) and [Dean–Munshi, Section 3](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
These algorithms also handle parallel contracts: preference pointers and residual capacities are attached to individual edges. Path and cycle augmentations remain defined on the resulting multigraph, including two-edge cycles.
Give every edge upper bound \(1\). If \(m>0\), both sides are nonempty, and positivity and joint normalization imply \(q_v<1\) for every vertex. Consequently every feasible edge allocation is strictly below its upper bound. Thus ordinary stability becomes precisely the absence of an edge strictly preferred to positive-mass statuses at both endpoints, with unused quota treated as the worst status.
If \(m=0\), return the empty matching. Henceforth assume \(m>0\).
Replace each original contract \(e\) by four parallel contracts
\( \alpha(e),\ \beta_0(e),\ \beta_1(e),\ \chi(e). \)
Keep the original vertex quotas.
The following is the no-critical-types specialization of [Csáji’s four-copy construction](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p409.pdf), expressed as explicit sorting rules.
At a left type \(a\), rank the copies of types \(\alpha,\beta_0,\beta_1\) by decreasing score:
| Copy | Score at \(a\) |
|---|---|
| \(\alpha(e)\) | \(p_a(e)\) |
| \(\beta_0(e)\) | \(p_a(e)-\gamma_{a,e}\) |
| \(\beta_1(e)\) | \(p_a(e)-\delta_{a,e}\) |
At equal scores, prioritize \(\beta_1\), then \(\beta_0\), then \(\alpha\). Resolve remaining ties arbitrarily. Place all \(\chi\)-copies below these copies, ordered by decreasing original value.
At a right type \(b\), rank the copies of types \(\chi,\beta_1,\beta_0\) by decreasing score:
| Copy | Score at \(b\) |
|---|---|
| \(\chi(e)\) | \(p_b(e)\) |
| \(\beta_1(e)\) | \(p_b(e)-\gamma_{b,e}\) |
| \(\beta_0(e)\) | \(p_b(e)-\delta_{b,e}\) |
At equal scores, prioritize \(\beta_0\), then \(\beta_1\), then \(\chi\). Resolve remaining ties arbitrarily. Place all \(\alpha\)-copies below these copies, ordered by decreasing original value.
Every copy is acceptable and ranks above unused quota. These auxiliary strict preferences are computational devices; the returned matching is evaluated using the original thresholds without tie-breaking.
Compute an ordinarily stable allocation \(y\) in this expanded instance. Return its projection
\( \displaystyle x_e=y_{\alpha(e)}+y_{\beta_0(e)}+y_{\beta_1(e)}+y_{\chi(e)}. \)
Summing at each endpoint shows that \(x\) satisfies the original quota constraints.
The sorting rules give the following exact equivalences for incident original contracts:
\( \beta_0(e)\succ_a\alpha(f) \quad\Longleftrightarrow\quad p_a(e)-p_a(f)\ge\gamma_{a,e}, \)
\( \beta_1(e)\succ_a\alpha(f) \quad\Longleftrightarrow\quad p_a(e)-p_a(f)\ge\delta_{a,e}, \)
\( \beta_0(e)\succ_b\chi(g) \quad\Longleftrightarrow\quad p_b(e)-p_b(g)\ge\delta_{b,e}, \)
\( \beta_1(e)\succ_b\chi(g) \quad\Longleftrightarrow\quad p_b(e)-p_b(g)\ge\gamma_{b,e}. \)
The specified priorities at equal scores account for the non-strict threshold inequalities.
Suppose, towards a contradiction, that \(e=(a,b)\) blocks \(x\) through positive-mass statuses \(f,g\).
First suppose
\( p_a(e)-p_a(f)\ge\gamma_{a,e}, \qquad p_b(e)-p_b(g)\ge\delta_{b,e}. \)
If \(f\ne\varnothing\), then at least one copy \(h\) of \(f\) has \(y_h>0\). At \(a\), the scores of the \(\beta\)-copies of \(f\) are strictly below \(p_a(f)\), while \(\chi(f)\) lies in the bottom group. The left inequality and the equality priorities therefore imply
\( \beta_0(e)\succ_a h. \)
If \(f=\varnothing\), the unused quota at \(a\) is positive in \(y\), and \(\beta_0(e)\) ranks above that status.
Likewise, if \(g\ne\varnothing\), choose a positive-allocation copy \(k\) of \(g\). Its score in the right upper group is at most \(p_b(g)\), while an \(\alpha\)-copy lies in the bottom group. The right inequality gives
\( \beta_0(e)\succ_b k. \)
If \(g=\varnothing\), \(b\) instead has positive unused quota.
Thus \(\beta_0(e)\) ordinarily blocks \(y\), a contradiction.
For the other permitted blocking pattern,
\( p_a(e)-p_a(f)\ge\delta_{a,e}, \qquad p_b(e)-p_b(g)\ge\gamma_{b,e}, \)
the same argument uses \(\beta_1(e)\). Hence \(x\) is \(c\gamma\)-stable.
We next justify using integral comparison matchings even though \(\mathrm{OPT}\) ranges over real allocations.
Lemma. Suppose all quotas \(Q_v\) are integers. For every real \(c\gamma\)-stable allocation \(z\), there is an integral \(c\gamma\)-stable allocation \(w\) such that
\( \displaystyle \sum_e w_e\ge\sum_e z_e. \)
Moreover, \(w_e>0\) implies \(z_e>0\), and every vertex saturated by \(z\) remains saturated by \(w\).
Proof. Consider the polytope defined by
\( w_e\ge0,\qquad w_e=0\ \text{whenever }z_e=0, \)
\( \displaystyle \sum_{e\in\mathcal E(v)}w_e\le Q_v, \)
and, at every vertex saturated by \(z\),
\( \displaystyle \sum_{e\in\mathcal E(v)}w_e=Q_v. \)
It is nonempty because it contains \(z\), and it is bounded.
The vertex-edge incidence matrix of a bipartite multigraph is totally unimodular: negating the rows on one side gives a directed incidence matrix. Deleting columns, imposing selected quota equalities, and adding nonnegativity preserve the integrality conclusion. Since the right-hand sides are integers, this polytope has integral vertices.
Maximizing \(\sum_e w_e\) therefore yields an integral optimum of value at least \(\sum_e z_e\).
Every positive contract status of \(w\) was positive in \(z\). Also, if \(w\) has positive unmatched mass at a vertex, then \(z\) had positive unmatched mass there, because all vertices saturated by \(z\) were kept saturated. Thus every pair of positive statuses that could witness a block of \(w\) would already witness the same block of \(z\). Stability of \(z\) rules this out. \(\square\)
Choose a positive integer \(D\) clearing the denominators of the original quotas. Run the stable-allocation primitive on integer quotas \(Q_v=Dq_v\) and edge bounds \(D\), and divide its integral output by \(D\). Write
\( Y_h=Dy_h,\qquad X_e=Dx_e. \)
These quantities are integers.
Let \(z\) be any original stable mass matching. Scaling masses by \(D\) preserves which statuses have positive mass and hence preserves stability. By the lemma, there is an integral stable allocation \(W\), with quotas \(Q_v\), satisfying
\( \displaystyle \sum_e W_e\ge D\sum_e z_e. \)
For the following argument only, replace type \(v\) by \(Q_v\) individual copies.
Realize \(Y\) as an ordinary matching \(M\) on these individuals: for each expanded contract \(h\), connect \(Y_h\) distinct pairs of endpoint individuals, respecting all quotas. Record the label \(h\) on each edge.
Independently realize \(W\) as a matching \(N\) on the same individual sets, recording the original contract labels. Both realizations exist because their incident totals do not exceed the numbers of individuals.
Their sizes are
\( \displaystyle |M|=D\sum_e x_e,\qquad |N|=\sum_e W_e. \)
Keep the two edge colors distinct, even if their endpoints coincide. Their union has degree at most two, and its nontrivial components are alternating paths or alternating cycles.
We show that an alternating path with one more \(N\)-edge than \(M\)-edge cannot have length one or three.
Such a path consists of an \(N\)-edge labeled \(f=(a,b)\), with both endpoint individuals unmatched in \(M\).
Therefore both types \(a,b\) have positive unused quota in \(Y\). Any expanded copy of \(f\) would ordinarily block \(Y\), contradicting its stability.
Write such a path as
\( b'\ \xleftrightarrow{\ N:f\ }\ a\ \xleftrightarrow{\ M:h\ }\ b\ \xleftrightarrow{\ N:g\ }\ a'. \)
Here \(h\) is a copy of an original contract \(e=(a,b)\). The endpoint individuals of types \(b'\) and \(a'\) are unmatched in \(M\), so those types have positive unused quota in \(Y\). Also,
\( Y_h>0,\qquad W_f>0,\qquad W_g>0. \)
Since \(\alpha(f)\) does not ordinarily block \(Y\), the positive status \(h\) at \(a\) cannot rank below \(\alpha(f)\). Strictness of the auxiliary order gives either \(h=\alpha(f)\) or
\( h\succ_a\alpha(f). \)
Similarly, nonblocking of \(\chi(g)\) gives either \(h=\chi(g)\) or
\( h\succ_b\chi(g). \)
Every \(\chi\)-copy ranks below every \(\alpha\)-copy at a left type. Thus \(h\) cannot be a \(\chi\)-copy. Every \(\alpha\)-copy ranks below every \(\chi\)-copy at a right type. Thus \(h\) cannot be an \(\alpha\)-copy.
Consequently \(h\) is either \(\beta_0(e)\) or \(\beta_1(e)\). Neither equality alternative above is now possible.
If \(h=\beta_0(e)\), the exact ranking equivalences give
\( p_a(e)-p_a(f)\ge\gamma_{a,e}, \qquad p_b(e)-p_b(g)\ge\delta_{b,e}. \)
Since \(W_f,W_g>0\), these inequalities make \(e\) block \(W\).
If \(h=\beta_1(e)\), they give
\( p_a(e)-p_a(f)\ge\delta_{a,e}, \qquad p_b(e)-p_b(g)\ge\gamma_{b,e}, \)
again making \(e\) block \(W\).
Both conclusions contradict stability of \(W\).
The argument permits repeated underlying types: it uses only positive allocation and unused quota at those types.
An alternating cycle has equally many edges of each color. An alternating path either has no more \(N\)-edges than \(M\)-edges, or has \(k+1\) \(N\)-edges and \(k\) \(M\)-edges.
In the latter case, Sections 5.1–5.2 imply \(k\ge2\). Therefore
\( \displaystyle k+1\le\frac32k. \)
Summing over all components yields
\( \displaystyle |N|\le\frac32|M|. \)
Combining the inequalities,
\( \displaystyle D\sum_e z_e \le\sum_e W_e =|N| \le\frac32|M| =\frac32D\sum_e x_e. \)
Since \(D>0\), this proves
\( \displaystyle \sum_e x_e\ge\frac23\sum_e z_e \)
for every stable mass matching \(z\).
One may take \(D\) to be the product of the denominators of the input masses. Its binary length is \(O(L)\). The scaled quotas and edge bounds consequently have polynomial encoding length.
The constructed instance has \(\tau\) original vertices and \(4m\) edges. Its preference lists can be sorted using exact rational arithmetic in polynomial time. The stable-allocation primitive runs directly on the encoded quotas; it does not create \(Q_v\) individuals. Its integral output divided by \(D\) has polynomial encoding length. Thus the complete algorithm runs in time polynomial in \(m,\tau,L\).
Finally, the feasible matching polytope is compact. For every contract and every status pair satisfying a blocking threshold pattern, stability imposes the closed condition
\( s_a(f)=0\quad\text{or}\quad s_b(g)=0. \)
There are finitely many such conditions. The stable set is therefore closed, and Section 3 proves it nonempty. The continuous mass objective attains a maximum on this set.
Taking \(z\) to be an optimum in Section 5 establishes the claimed guarantee.
⟨structured verdict parsed — rendered above⟩
The prover establishes the requested polynomial-time approximation algorithm. I found no major or minor mathematical errors. In particular, the capacity expansion appears only in the analysis, so its potentially exponential size does not invalidate the runtime claim.
The cited strongly polynomial stable-allocation result is applicable to the auxiliary instance: the graph is bipartite, preferences are strict, quotas are positive, and edge bounds are finite and nonnegative. Unequal total quotas on the two sides are permitted; unmatched allocation is represented by dummy elements in the cited formulation. [Baïou–Balinski](https://pubsonline.informs.org/doi/pdf/10.1287/moor.27.4.662.302), [Dean–Munshi, Sections 2–3](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The integrality claim is also supported by the described augmenting-path algorithm: integer initialization and augmentations determined by minimum residual capacities preserve integer allocations. The claimed extension to parallel contracts is valid when pointers and residual capacities identify individual contracts, as the prover explicitly requires. Distinct parallel edges can form a two-edge cycle without changing these operations.
For \(m>0\), both sides contain a positive-mass endpoint. Joint normalization therefore gives \(q_v<1\) for every vertex. Consequently,
\[
y_h\le q_v<1
\]
for every auxiliary contract incident to \(v\). Thus no auxiliary edge reaches its upper bound. The analogous statement after scaling is \(Y_h\le Q_v<D\).
This verifies the residual-capacity hypothesis whenever the proof invokes an ordinary blocking edge.
The sorting rules define strict orders after the specified final tie resolution. Negative auxiliary scores cause no difficulty because acceptability is specified separately.
All four ranking equivalences are correct. In each case, comparison of the scores gives the relevant threshold inequality, and the stated priority places the beta copy first at equality. Arbitrary remaining ties cannot affect these cross-copy comparisons.
The projection is feasible: summing the four copies of every original contract preserves each vertex’s total allocated mass. It also preserves unmatched mass.
The construction agrees with the four-copy preference rules described in the discrete source. However, the continuous guarantee is established by the prover’s subsequent argument, rather than inferred from the discrete approximation theorem. [Csáji, Section 3.1](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p409.pdf).
Both blocking patterns are handled correctly.
For the first pattern, the left inequality places \(\beta_0(e)\) above every positive auxiliary copy of \(f\):
The corresponding right argument places \(\beta_0(e)\) above every positive copy of \(g\). If either original status is unmatched, that endpoint has positive unused auxiliary quota and regards the proposed copy as acceptable.
Together with the verified unused edge capacity, these facts produce an ordinary block of \(y\).
The second pattern correctly uses \(\beta_1(e)\) with the other two threshold equivalences.
The proof does not require threshold comparisons involving auxiliary representations of \(p_v(\varnothing)\): an unmatched endpoint accepts every auxiliary copy. This is sufficient for the stated contradiction.
The lemma is valid.
The proposed polytope contains \(z\), is bounded by the finite quotas, and restricts allocation to the support of \(z\). The bipartite incidence matrix is totally unimodular, including with repeated columns arising from parallel contracts. Selected quota equalities and nonnegativity retain the asserted integrality property with integer right-hand sides.
Therefore an integral maximizing vertex exists and has objective at least that of \(z\).
The stability argument correctly checks both kinds of status:
Hence any blocking witness for \(w\) would also be a blocking witness for \(z\). No assumption about rationality of \(z\) is needed.
Section 5 specifies the integer-preserving implementation of the primitive. Dividing its output by \(D\) supplies the auxiliary allocation used in the projection and stability arguments. Thus the proof does not incorrectly assume that an arbitrary real-valued stable allocation is integral after scaling.
Scaling preserves positivity of every status, so it preserves the stated stability definition. Applying the lemma to the scaled comparison allocation is legitimate.
The realizations of \(Y\) and \(W\) as matchings on the same individual sets exist because their incident totals respect the integer quotas. They can be constructed independently. Ordinary stability of the individual realization \(M\) is neither asserted nor needed.
Keeping coincident edges distinct by color gives alternating paths and cycles, including two-edge cycles.
Both endpoint individuals are unmatched in \(M\), so both underlying types have positive unused quota in \(Y\). An acceptable auxiliary copy of the comparison contract has unused edge capacity and would block \(Y\). The exclusion is correct.
The endpoint individuals again certify unused quota at their underlying types.
Nonblocking of \(\alpha(f)\) forces the positive middle status \(h\) at the left endpoint to be at least as preferred as \(\alpha(f)\). Nonblocking of \(\chi(g)\) forces the analogous right comparison.
These conditions exclude chi and alpha middle copies, respectively. If the middle copy is beta, the equality alternatives are impossible because the copy labels differ.
The exact equivalences then give one of the two original blocking patterns for \(e\), witnessed by the positive comparison statuses \(W_f\) and \(W_g\). This contradicts stability of \(W\).
Repeated underlying types and parallel original contracts do not invalidate these deductions: every required fact concerns positive allocation or unused quota at a type.
Every component with more \(N\)-edges than \(M\)-edges has \(k+1\) and \(k\) edges of the respective colors. Exclusion of the one-edge and three-edge cases gives \(k\ge2\), and
\[
k+1\le \frac32k.
\]
All other components satisfy the same comparison immediately. The resulting inequality
\[
|N|\le\frac32|M|
\]
and the subsequent scaling calculation establish the claimed guarantee for every stable comparison allocation.
The product of the mass denominators has binary length \(O(L)\). Scaled quotas, bounds, and integer output therefore have polynomial encoding length. Exact rational sorting is polynomial, and the primitive operates on the encoded auxiliary graph rather than the individual expansion.
Isolated types cause no problem: they retain their unmatched mass, and their processing cost is covered by the permitted dependence on \(\tau\). The case \(m=0\) is handled correctly.
The optimum-attainment argument is also correct. There are finitely many potential blocking status pairs. Each corresponding stability condition is a union of two closed zero-status sets. Their finite intersection with the compact feasible polytope is closed and compact, and the construction proves nonemptiness.
The objective therefore attains its maximum. Substituting an optimum into the verified comparison inequality proves the requested result.
No additional clarification is needed to verify the mathematical argument.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.