Answer: \(\text{Polynomial-time solvable in }m,\tau,L\).
Corollary 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateA sex-equal stable matching can be computed in polynomial time when either 𝑆𝑀(𝜇𝑀) ≥𝑆𝑊(𝜇𝑀) or 𝑆𝑀(𝜇𝑊) ≤ 𝑆𝑊(𝜇𝑊).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite resident and position type sets \(A\) and \(B\), rational masses \(\mu_a,\nu_b\ge0\) summing to \(1\), and strict orders of each \(a\in A\) over \(B\) and each \(b\in B\) over \(A\), let \(x_{ab}\ge0\) satisfy \(\sum_b x_{ab}=\mu_a\) and \(\sum_a x_{ab}=\nu_b\). Define stability by requiring that no pair \((a,b)\) has both \(P_{ab}(x)=\sum_{b':\,b\succ_a b'}x_{ab'}>0\) and \(Q_{ab}(x)=\sum_{a':\,a\succ_b a'}x_{a'b}>0\). With type ranks \(\rho_A(a,b)\) and \(\rho_B(b,a)\), define \(S_A(x)=\sum_{a,b}x_{ab}\rho_A(a,b)\) and \(S_B(x)=\sum_{a,b}x_{ab}\rho_B(b,a)\). Promised that the \(A\)- or \(B\)-proposing batch-deferred-acceptance extreme matching satisfies \(S_A(x^A)\ge S_B(x^A)\) or \(S_A(x^B)\le S_B(x^B)\), output a stable mass matching minimizing \(\lvert S_A(x)-S_B(x)\rvert\).
Let \(A,B\) be nonempty finite resident and position type sets. Each society is given by its support: the list of types with positive mass, each mass a binary rational; \(\sum_a\mu_a=\sum_b\nu_b=1\). Set \(\tau=|A|+|B|\), the total support size, not the number of possible preference types, and \(m=\max\{|A|,|B|\}\); let \(L\) be the total input bit length. Each type has a strict complete order over the opposite support, with ranks \(\rho_A(a,b),\rho_B(b,a)\) starting at \(1\).
A mass matching is a real matrix \(x\ge0\) with \(\sum_bx_{ab}=\mu_a\) and \(\sum_ax_{ab}=\nu_b\). It is stable when, for every \((a,b)\), at least one of \(P_{ab}(x)=\sum_{b':\,b\succ_a b'}x_{ab'}\) and \(Q_{ab}(x)=\sum_{a':\,a\succ_b a'}x_{a'b}\) is zero.
Define \(S_A(x)=\sum_{a,b}x_{ab}\rho_A(a,b)\) and \(S_B(x)=\sum_{a,b}x_{ab}\rho_B(b,a)\). Define \(x^A,x^B\) by mass deferred acceptance with the indicated side proposing: initially all mass is free; each round, each proposer offers its free mass to its favorite receiver that has not previously rejected positive mass from it; each receiver retains its most preferred offered and previously held mass up to its capacity, allowing partial retention, and rejects the remainder. Repeat until all mass is held.
Restrict inputs to the promise \(S_A(x^A)\ge S_B(x^A)\) or \(S_A(x^B)\le S_B(x^B)\).
Is finding a stable mass matching minimizing \(|S_A(x)-S_B(x)|\) on these promised inputs solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite one-to-one matching with strict complete preferences, the corresponding endpoint-sign promise permits exact sex-equality optimization in \(O(n^2)\) time ([source](https://arxiv.org/pdf/2201.12484)).
Continuous stable allocation admits polynomial-time optimization of arbitrary linear costs ([source](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)); this concerns a different objective. No result explicitly treating the promised absolute rank-gap objective was located.
The promised problem is polynomial-time solvable in \(m,\tau,L\). More precisely:
The essential point is to establish rank-score bounds for every real stable mass matching, and then compute the endpoints using a polynomial-time stable-allocation algorithm.
Use the complete bipartite graph with vertex sets \(A,B\), vertex quotas \(\mu_a,\nu_b\), and edge capacities
\[ u_{ab}=\min\{\mu_a,\nu_b\}. \]
These capacities impose no additional restriction on a mass matching: its marginal equations already imply \(x_{ab}\le u_{ab}\).
In the capacitated stable-allocation model, an edge blocks precisely when
\[ x_{ab}<u_{ab},\qquad P_{ab}(x)>0,\qquad Q_{ab}(x)>0. \]
This agrees with the task’s stability condition. Indeed, if \(x_{ab}=u_{ab}\), then either \(x_{ab}=\mu_a\), making \(P_{ab}(x)=0\), or \(x_{ab}=\nu_b\), making \(Q_{ab}(x)=0\). Thus the additional capacity test cannot exclude any blocking pair under the task’s definition.
The cited algorithm uses dummy vertices to represent unassigned mass. To check that this convention causes no discrepancy, add a dummy resident and a dummy position, each of quota \(1\), and rank a dummy last at every original vertex.
For any feasible augmented allocation, write
\[ r_a=\mu_a-\sum_{b\in B}x_{ab}, \qquad s_b=\nu_b-\sum_{a\in A}x_{ab}. \]
These quantities are the allocations to the opposite dummy. They satisfy
\[ \sum_a r_a=\sum_b s_b. \]
If this common value were positive, some \(a,b\) would satisfy \(r_a>0\) and \(s_b>0\). Consequently,
\[ x_{ab}<\mu_a,\qquad x_{ab}<\nu_b, \]
and both vertices would have positive allocation to a dummy, which they strictly prefer each other to. Hence \((a,b)\) would block. Therefore every stable augmented allocation assigns all original mass to original vertices.
Conversely, a stable mass matching extends to a stable augmented allocation by assigning mass \(1\) between the two dummies and zero between original and dummy vertices. Edges incident to exactly one dummy cannot block because that dummy is last in the original vertex’s list; the dummy–dummy edge is saturated.
Thus restriction and extension identify the two sets of stable solutions exactly.
We use these established results for bipartite stable allocation with strict preferences and real quotas and capacities:
These are provided by Lemma 1, Lemmas 6–8 and the augmenting-path algorithm in Sections 3–4 of [Dean and Munshi, *Faster Algorithms for Stable Allocation Problems*](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
All hypotheses hold here: the graph is finite and bipartite, preferences are strict, and the quotas and capacities are positive rationals.
The task’s batch deferred acceptance produces these same endpoints. To see the correspondence, process a round’s offers sequentially, postponing newly freed mass until the next round. At each receiver, repeated retention of its best mass gives exactly the same result as retaining its best mass from all offers together. Offers to an already saturated edge, or to a receiver that has previously rejected that type, cannot increase the retained amount of that type; omitting these redundant offers gives the standard stable-allocation procedure. Hence its endpoints restrict to the task’s \(x^A,x^B\).
Claim. For every stable mass matching \(x\),
\[ S_A(x^A)\le S_A(x)\le S_A(x^B), \]
and
\[ S_B(x^B)\le S_B(x)\le S_B(x^A). \]
Proof. First orient the structural theorem with \(A\) proposing. Starting from \(x\), follow its stable rotations to the \(B\)-optimal endpoint \(x^B\).
Suppose one rotation transfers mass \(\delta>0\) at resident \(a\) from position \(b_{\mathrm{old}}\) to the less preferred position \(b_{\mathrm{new}}\). Its contribution to the change in \(S_A\) is
\[ \delta\bigl(\rho_A(a,b_{\mathrm{new}}) -\rho_A(a,b_{\mathrm{old}})\bigr)>0. \]
At a participating position \(b\), the corresponding transfer replaces resident \(a_{\mathrm{old}}\) by a more preferred resident \(a_{\mathrm{new}}\). Its contribution to the change in \(S_B\) is
\[ \delta\bigl(\rho_B(b,a_{\mathrm{new}}) -\rho_B(b,a_{\mathrm{old}})\bigr)<0. \]
Nonparticipating vertices contribute zero. Summing over each rotation and then over the finite sequence gives
\[ S_A(x)\le S_A(x^B), \qquad S_B(x)\ge S_B(x^B). \]
Now interchange the sides. Starting from \(x\), the analogous rotation sequence reaches \(x^A\); throughout it, \(S_B\) increases and \(S_A\) decreases. Therefore
\[ S_B(x)\le S_B(x^A), \qquad S_A(x)\ge S_A(x^A). \]
Together these prove the claim. The theorem applies to real allocations, so this argument includes irrational stable mass matchings. \(\square\)
Define the signed gap
\[ D(x)=S_A(x)-S_B(x). \]
The bounds just proved imply, for every stable \(x\),
\[ D(x^A)\le D(x)\le D(x^B). \]
We now treat the two promised cases.
Case 1: \(D(x^A)\ge0\). Every stable \(x\) satisfies \(D(x)\ge D(x^A)\ge0\). Hence
\[ |D(x)|=D(x)\ge D(x^A)=|D(x^A)|. \]
Thus \(x^A\) is optimal.
Case 2: \(D(x^B)\le0\). Every stable \(x\) satisfies \(D(x)\le D(x^B)\le0\). Hence
\[ |D(x)|=-D(x)\ge-D(x^B)=|D(x^B)|. \]
Thus \(x^B\) is optimal.
The promise guarantees that at least one case applies. If both apply, the endpoint bounds force every stable matching to have gap zero.
Compute both endpoints using the polynomial-time stable-allocation algorithm. Return \(x^A\) if \(D(x^A)\ge0\); otherwise return \(x^B\). The preceding proof establishes correctness on every promised input.
For completeness, the arithmetic-operation bound also yields polynomial bit complexity here. Let \(H\) be the product of the denominators of all input masses. Its binary length is \(O(L)\). Scale all quotas and capacities by \(H\), making them integers.
The elementary augmenting-path implementation uses comparisons, minima, additions and subtractions of allocation quantities. Consequently, all allocations remain integers in the scaled instance. Each edge allocation and residual capacity is bounded by \(H\), and total augmented mass is \(2H\); thus the numerical quantities have \(O(L)\) bits.
The augmented graph has
\[ N=\tau+2, \qquad E=|A||B|+O(\tau)\le m^2+O(\tau). \]
The \(O(EN)\) arithmetic-operation bound therefore gives polynomial bit complexity in \(m,\tau,L\). Dividing the output by \(H\) produces an exact rational mass matching. Its rank scores and their signs can likewise be computed exactly in polynomial time.
Ordinary batch deferred acceptance need not itself run in polynomial time; its endpoints are computed by the faster algorithm cited above.
⟨structured verdict parsed — rendered above⟩
The argument is sound in substance and establishes polynomial-time solvability on the promised inputs. I found one minor omission in the specification of the dummy augmentation, and no major mathematical error.
The original edge capacities are valid. Nonnegativity and the marginal equations imply \(x_{ab}\le\mu_a\) and \(x_{ab}\le\nu_b\), hence \(x_{ab}\le u_{ab}\).
The stability equivalence is correct. If \(x_{ab}=u_{ab}\), at least one endpoint assigns its entire quota to that edge. Consequently, at least one of \(P_{ab}(x)\) and \(Q_{ab}(x)\) vanishes. Thus a pair violating the task’s stability condition necessarily satisfies the allocation model’s additional unsaturated-edge requirement.
The dummy argument is also correct under the intended augmentation:
Minor issue: The augmented instance is not completely specified. The prover gives dummy quotas and original vertices’ dummy rankings, but does not explicitly give capacities on dummy-incident edges or the dummies’ own strict preference lists. In particular, feasibility and saturation of the dummy–dummy allocation require its capacity to permit mass \(1\).
Minimum clarification: State the capacities and preference lists for every added edge and dummy vertex, or explicitly adopt the complete dummy convention in the cited paper’s Section 2. This is a specification repair requiring no new mathematical argument.
The citation supports the substantive claims. Lemma 1 establishes finite termination and proposal-order independence, including irrational data. Lemmas 6 and 7 give the direction of partner changes and preservation of stability; Lemma 8 characterizes the receiving-side endpoint. The finite rotation process from an arbitrary stable allocation is explicitly used in the proof of Lemma 12. Section 3 supplies the augmenting-path algorithm and its arithmetic-operation analysis. [Dean and Munshi, *Faster Algorithms for Stable Allocation Problems*](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)
The original instance satisfies the required hypotheses: finite bipartite graph, strict preferences, positive quotas, and positive capacities bounded by endpoint quotas. The augmented instance does so once the minor specification omission above is resolved.
Crucially, the prover does not infer rank-score optimality merely from lexicographic optimality. It uses the stronger, applicable rotation statements.
The sequential processing explanation is valid. At a receiver, retaining its most preferred mass subject to capacity produces the same holdings whether a round’s offers are processed together or sequentially. Deferring newly freed mass reproduces the task’s round boundaries.
Skipping previously rejected offers is justified because subsequent holdings at a receiver cannot become less preferred in a way that makes such offers acceptable again.
The saturated-edge observation is valid for the chosen capacities. Saturation either exhausts the proposer’s quota or fills the receiver entirely with that proposer’s mass. In the latter situation, additional offered mass from that proposer cannot increase its holdings. Thus the capacity-aware procedure does not change the endpoints relevant to the task.
No substantive gap was found in this identification.
The rotation calculations have the correct signs. Moving positive mass to a less preferred partner strictly increases the proposer’s rank score; moving it to a more preferred partner strictly decreases the receiver’s rank score.
Summing along the stated finite rotation sequence therefore gives
\(S_A(x)\le S_A(x^B)\) and \(S_B(x)\ge S_B(x^B)\).
Interchanging the sides gives
\(S_A(x^A)\le S_A(x)\) and \(S_B(x)\le S_B(x^A)\).
These bounds apply to every real stable matching, including irrational ones. Rational input data is needed for the computational argument, not for this comparison.
If a rotation sequence is empty, the corresponding inequalities remain valid as equalities.
The subtraction of the score bounds is correct:
\(D(x^A)\le D(x)\le D(x^B)\).
Both promised cases then follow exactly as written:
The absolute-value inequalities consequently have the correct directions. Zero endpoint gaps are included. If both conditions hold, the bounds force every stable gap to equal zero.
The algorithm’s fallback to \(x^B\) when \(D(x^A)<0\) is justified by the promise.
The denominator scaling argument is correct. The binary length of the product \(H\) is bounded by the sum of the input denominator lengths, hence is \(O(L)\). Scaling also makes the capacities integral.
The specified elementary implementation preserves integrality through comparisons, minima, additions, and subtractions. Its allocation and residual quantities remain bounded by the scaled quotas, with total augmented mass \(2H\). Their bit lengths are therefore polynomially bounded.
The graph-size bounds use the actual support sizes:
\(N=\tau+2\) and \(E=|A||B|+O(\tau)\).
The arithmetic-operation bound thus yields polynomial bit complexity in \(m,\tau,L\). Computing exact rank scores adds only polynomial-size arithmetic, since ranks are at most \(m\).
Singleton supports and unequal support sizes cause no exception to the argument.
The promised optimization target is therefore resolved, subject only to explicitly completing the dummy-instance specification.
⟨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.