Answer: Polynomial-time solvable; the threshold decision version belongs to \(\mathrm{P}\).
Theorem 2 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateA matching is stable for ≻ if and only if it is an extreme point of e⌦(≻). The above result allows us to construct a stable outcome rule by framing a linear optimization problem over e⌦(≻). This will always yield a stable matching. Definition 3 (Weighted polytope (WP) rule).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite worker-type and job-type sets \(H,D\), strict preferences over opposite-side types and \(\varnothing\), rational masses \(a_h,b_d\) with equal total mass on each side, and rational edge weights \(w_{hd}\), compute an allocation \(x_{hd}\ge 0\) maximizing \(\sum_{h,d} w_{hd}x_{hd}\). Require \(\sum_d x_{hd}\le a_h\), \(\sum_h x_{hd}\le b_d\), and \(x_{hd}=0\) unless both types prefer each other to \(\varnothing\). For every mutually acceptable pair, define \(u_h=a_h-\sum_d x_{hd}\), \(v_d=b_d-\sum_h x_{hd}\), \(A_{hd}=\sum_{d':\,d\succ_h d'}x_{hd'}+u_h\mathbf{1}[d\succ_h\varnothing]\), and \(B_{hd}=\sum_{h':\,h\succ_d h'}x_{h'd}+v_d\mathbf{1}[h\succ_d\varnothing]\); require \(A_{hd}B_{hd}=0\).
Let \(H,D\) be nonempty finite sets of worker and job types. Each type has a strict total preference order over opposite-side types and \(\varnothing\), representing being unmatched.
A society is given by its support: the list of its \(\tau=|H|+|D|\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Require \(\sum_h a_h=\sum_d b_d=T>0\), without normalizing \(T\). Let \(E=\{(h,d):d\succ_h\varnothing,\ h\succ_d\varnothing\}\), \(m=|E|\), and \(L\) be the total input bit length, including preferences and arbitrary signed rational weights \(w_{hd}\).
An allocation has real entries \(x_{hd}\ge0\), satisfies \(\sum_d x_{hd}\le a_h\), \(\sum_h x_{hd}\le b_d\), and has \(x_{hd}=0\) outside \(E\). Define unmatched masses \(u_h=a_h-\sum_d x_{hd}\) and \(v_d=b_d-\sum_h x_{hd}\).
For \((h,d)\in E\), define \(A_{hd}=u_h+\sum_{d':\,d\succ_h d'}x_{hd'}\) and \(B_{hd}=v_d+\sum_{h':\,h\succ_d h'}x_{h'd}\). Call the allocation stable when \(A_{hd}B_{hd}=0\) for every \((h,d)\in E\).
The optimization problem is to maximize \(\sum_{(h,d)\in E}w_{hd}x_{hd}\) over stable allocations; any maximizer is permitted.
Is this optimization problem solvable in time polynomial in \(m,\tau,L\), or is its threshold decision version, with binary rational threshold \(K\), \(\mathrm{NP}\)-hard?
For discrete one-to-one matching with strict preferences, stable matchings are precisely the extreme points of the stable marriage polytope, yielding polynomial-time weighted optimization ([Roth–Rothblum–Vande Vate](https://pubsonline.informs.org/doi/abs/10.1287/moor.18.4.803)).
The continuous optimization problem above is already covered by polynomial-time minimum-cost bipartite stable allocation with real quotas and strict preferences ([Dean–Munshi](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf)); consequently, this target is not open.
The optimization problem is polynomial-time solvable in \(m,\tau,L\). Its threshold decision version therefore belongs to \(\mathrm{P}\).
We prove this by reducing it to minimum-cost bipartite stable allocation, including a check of stability equivalence and binary encoding complexity.
Dean–Munshi establish polynomial-time minimum-cost stable allocation on a bipartite graph with strict preferences, real vertex quotas, and real edge capacities. In their formulation, every vertex receives exactly its quota. An edge blocks precisely when it is unsaturated and both endpoints have positive allocation on less-preferred edges. See Sections 2 and 4 of [Dean–Munshi, *Faster Algorithms For Stable Allocation Problems*](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
We use this theorem as a known result. The construction below verifies its hypotheses and its applicability to the stability definition in the question.
Introduce a dummy worker \(h_*\) and a dummy job \(d_*\). The augmented bipartite graph has edge set
\(E'=E\cup\{(h,d_*):h\in H\}\cup\{(h_*,d):d\in D\}\cup\{(h_*,d_*)\}\).
Give the original vertices quotas \(a_h\) and \(b_d\), and give both dummy vertices quota \(T\). Thus each side has total quota \(2T\).
Give every edge capacity equal to the smaller of its endpoint quotas. In particular, the capacities are:
At every original vertex, retain the original order restricted to incident edges in \(E\), and put its dummy neighbor last. This is valid because every retained real neighbor is preferred to being unmatched. Each dummy vertex ranks all its real neighbors in any strict order, followed by the other dummy vertex.
All quotas and capacities are positive, and all preference lists are strict.
Claim. Feasible allocations in the question correspond bijectively to feasible allocations with exact quotas in the augmented instance.
To prove this, let \(x\) be an original feasible allocation and set \(s=\sum_{(h,d)\in E}x_{hd}\). Define its extension \(y\) by
\(y_{hd}=x_{hd},\qquad y_{h d_*}=u_h,\qquad y_{h_*d}=v_d,\qquad y_{h_*d_*}=s.\)
Every original vertex receives exactly its quota. Moreover,
\(\sum_h u_h=T-s,\qquad \sum_d v_d=T-s.\)
Consequently, the dummy worker receives total allocation \((T-s)+s=T\), and the dummy job does likewise.
The capacity bounds hold: \(x_{hd}\le\min(a_h,b_d)\), \(u_h\le a_h\), \(v_d\le b_d\), and \(s\le T\).
Conversely, restricting any augmented feasible allocation \(y\) to \(E\) gives an original feasible allocation \(x\). The exact-quota equations force \(y_{h d_*}=u_h\) and \(y_{h_*d}=v_d\). The dummy worker’s quota then forces \(y_{h_*d_*}=s\). Hence the extension is unique.
Fix a real edge \((h,d)\in E\). In the extension \(y\), the total allocation at \(h\) on edges less preferred than \((h,d)\) is exactly
\(y_{h d_*}+\sum_{d':\,d\succ_h d'}y_{hd'}=A_{hd}.\)
The corresponding quantity at \(d\) is exactly \(B_{hd}\). Edges outside \(E\) contribute zero to the original sums, so deleting them does not change these identities.
The Dean–Munshi blocking condition for this edge is therefore
\(x_{hd}<\min(a_h,b_d),\qquad A_{hd}>0,\qquad B_{hd}>0.\)
The capacity condition is automatic whenever the other two conditions hold. Indeed, feasibility gives
\(A_{hd}\le a_h-x_{hd},\qquad B_{hd}\le b_d-x_{hd}.\)
Thus \(A_{hd}>0\) and \(B_{hd}>0\) imply \(x_{hd}<a_h\) and \(x_{hd}<b_d\).
Since \(A_{hd}\) and \(B_{hd}\) are nonnegative, we conclude that a real edge blocks in the augmented instance exactly when \(A_{hd}B_{hd}>0\).
No dummy edge can block:
Therefore, \(x\) satisfies every condition \(A_{hd}B_{hd}=0\) if and only if its extension \(y\) is a stable allocation in the Dean–Munshi model.
Assign cost \(c_{hd}=-w_{hd}\) to every real edge and cost zero to every dummy edge. Then
\(\sum_{e\in E'}c_e y_e=-\sum_{(h,d)\in E}w_{hd}x_{hd}.\)
The established bijection preserves stability, so restricting a minimum-cost augmented stable allocation produces a maximizer for the original problem.
The augmented instance has \(N=\tau+2\) vertices and \(M=m+\tau+1\) edges. Its encoding length is polynomial in \(L,m,\tau\): computing \(T\), taking minima, and adding dummy preference entries require only polynomially many operations on binary rationals.
We also check that real-quota arithmetic does not conceal dependence on quota magnitudes. The Dean–Munshi construction uses polynomially many additions, subtractions, and minimum operations to obtain allocations and rotation multiplicities, then solves a minimum-cost closure problem. A rotation’s cost is its multiplicity times the signed sum of its edge costs. These are the algorithmic ingredients described in Sections 3–4 of the [paper](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
Let \(Q\) be the product of the denominators of all input masses, and \(R\) the product of the denominators of all weights. Both have bit length at most \(O(L)\). Scaling all augmented quotas and capacities by \(Q\), and all costs by \(R\), produces integral data of polynomial bit length.
This scaling preserves the problem: allocations scale by \(Q\), stability is unchanged, and the objective scales by the positive factor \(QR\).
On these integral data, additions, subtractions, and minimum operations preserve integrality. After a polynomial number \(p\) of additions or subtractions, integer bit length grows by at most \(p\), beyond the maximum starting bit length. Rotation-cost multiplication and summation also have polynomial bit length. The resulting closure problem has polynomial size and integer costs of polynomial bit length, so an exact polynomial-time minimum-cut algorithm solves it in the binary model.
Reconstructing the chosen allocation and dividing by \(Q\) consequently returns an exact rational optimizer in polynomial time. No expansion into individual workers or jobs is required, and \(T\) need not be normalized.
Finally, evaluate its rational objective and compare it exactly with the input threshold \(K\). This establishes polynomial-time solvability of the threshold version as well.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction preserves feasibility, stability, and the objective, and the encoding argument establishes polynomial time in the binary input model. I found no major or minor mathematical issues requiring repair.
The cited result is applicable. Section 2 uses exact vertex quotas, strict preferences, and edge capacities bounded by endpoint quotas; problem data need not be integral. Its blocking definition requires an unsaturated edge and positive allocation on less-preferred edges at both endpoints. Section 4 establishes polynomial-time minimum-cost optimization through a rotation closure construction, with an optimum obtainable using fully applied rotations. No nonnegativity restriction on edge costs is imposed. [Dean–Munshi, Sections 2 and 4](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The constructed dummy vertices also satisfy the paper’s dummy conventions: their quotas equal the total original quota on the opposite side, and all dummy incidences have the prescribed last-place positions.
Assessment: The theorem is accurately described, and its hypotheses are satisfied.
All original masses are positive by the support definition, and \(T>0\). Consequently, every constructed quota and capacity is positive.
The capacities on dummy edges are correctly calculated: \(a_h\le T\) and \(b_d\le T\), so taking the smaller endpoint quota gives the stated values.
Restricting preferences to mutually acceptable real edges and placing the dummy last preserves their relevant ordering. Preferences over deleted edges cannot affect stability because allocations on those edges are zero.
The counts \(N=\tau+2\) and \(M=m+\tau+1\) are correct.
Assessment: The construction is well-defined, including when original vertices have no acceptable neighbors.
For any original feasible allocation, the total assigned mass satisfies \(0\le s\le T\). The extension assigns unmatched masses to the corresponding dummy edges and assigns \(s\) to the dummy–dummy edge.
The original quota equations hold by the definitions of \(u_h\) and \(v_d\). The identities
\[
\sum_h u_h=T-s,\qquad \sum_d v_d=T-s
\]
correctly establish both dummy quota equations. Every capacity bound follows from original feasibility and \(s\le T\).
Conversely, restricting an augmented feasible allocation yields the original row and column inequalities. Exact quotas uniquely determine every dummy edge as claimed.
Assessment: Both directions and uniqueness are established. The claimed bijection covers all feasible allocations, including real-valued ones.
The less-preferred allocation at each endpoint is exactly the corresponding quantity \(A_{hd}\) or \(B_{hd}\). This correctly includes unmatched mass through the dummy edge.
The inequalities
\[
A_{hd}\le a_h-x_{hd},\qquad B_{hd}\le b_d-x_{hd}
\]
are valid: each left-hand side contains unmatched mass and only a subset of the other incident allocations.
Thus simultaneous positivity implies
\[
x_{hd}<\min(a_h,b_d).
\]
The unsaturated-edge requirement introduces no discrepancy between the two stability definitions.
Both quantities are nonnegative. Therefore their product is positive exactly when both endpoint blocking conditions hold.
Assessment: The equivalence is exact. Saturated real edges are correctly handled rather than silently excluded.
For each original–dummy edge, its original endpoint ranks that edge last and therefore has no less-preferred incident allocation. For the dummy–dummy edge, both endpoints rank it last.
Since blocking requires both endpoints to hold positive less-preferred allocation, none of these edges can block, irrespective of its saturation status.
Assessment: The exclusion of dummy blocking pairs is justified. Combined with the preceding step, this establishes stability equivalence in both directions.
Negating each real weight and assigning zero dummy costs gives exactly the negative original objective.
Because the correspondence preserves stability, an augmented minimum-cost stable allocation restricts to an original maximizer. Arbitrary signed weights and nonunique optima cause no problem.
Assessment: Optimization, rather than merely stable feasibility, is preserved.
The argument correctly distinguishes polynomially many arithmetic operations from polynomial bit complexity.
The products \(Q\) and \(R\) have polynomial bit length because their denominator bit lengths are included in \(L\). Scaling by \(Q\) makes all constructed quotas and capacities integral; scaling by \(R\) makes all costs integral. Both factors are positive, so feasibility, stability, and optimization are preserved under the stated scaling.
The paper’s augmentation arithmetic uses residual differences, minima, and additive updates, supporting the prover’s integrality assertion. Its explicit rotation representation has polynomial size. [Dean–Munshi, Sections 3–4](https://people.computing.clemson.edu/~bcdean/stable_alloc.pdf).
The stated bit-growth bound is valid: each addition or subtraction increases the maximum magnitude bit length by at most one. Polynomially many such operations therefore retain polynomial bit length. Rotation-cost products and sums also retain polynomial bit length.
The subsequent integer closure problem has polynomial size and polynomial-bit costs, so the invoked exact polynomial-time minimum-cut computation supplies the required binary-model guarantee.
Assessment: There is no hidden dependence on quota magnitude or expansion into individual agents. Reconstruction returns an exact rational optimizer of polynomial encoding length.
Exact objective evaluation and rational comparison settle the threshold question. As usual, the threshold decision running time includes the encoding length of \(K\).
The construction accommodates \(m=0\), isolated original vertices, arbitrary positive \(T\), and negative or zero weights. Neither normalization nor uniqueness is needed.
Assessment: The claimed polynomial-time classification addresses the full target.
None. No missing lemma, false computation, unverified theorem application, or blocking clarification was found.
⟨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.