Answer: —
Theorem 1 — class: algorithmic
Given finite applicant types \(I\) and position types \(J\), rational supplies \(\alpha_i,\beta_j\), and incomplete weak preference orders with tie classes of at most \(L\) opposite-side types, determine whether a polynomial-time algorithm can return a stable assignment \(x_{ij}\ge 0\) with total matched mass at least \(\frac{2L-1}{3L-2}\) times the maximum stable matched mass. Here \(\sum_j x_{ij}\le\alpha_i\), \(\sum_i x_{ij}\le\beta_j\), and stability means that for every acceptable type pair, at least one side has zero mass that is unmatched or strictly prefers that pair to its current assignment.
Let \(I,J\) be finite, nonempty sets of applicant and position types, with mutually acceptable pairs \(E\subseteq I\times J\). Each type has a weak preference order over its acceptable opposite-side types; every acceptable partner is strictly preferred to being unmatched. Each tie contains at most \(k\) types, where \(k\ge1\) is an integer.
A society is given by its support: the list of the \(\tau=|I|+|J|\) types with positive mass, each mass \(\alpha_i\) or \(\beta_j\) a binary rational. These masses need not sum to one, and the two sides may have unequal total mass. Support size counts listed types, not possible preference orders. Put \(m=\max\{|I|,|J|\}\), and let \(L\) be the total input bit length.
An assignment has real entries \(x_{ij}\ge0\), vanishes outside \(E\), and satisfies \(\sum_jx_{ij}\le\alpha_i\) and \(\sum_ix_{ij}\le\beta_j\). Write \(j'\succeq_i j\) when applicant type \(i\) weakly prefers \(j'\) to \(j\), and define \(i'\succeq_j i\) analogously.
For every \((i,j)\in E\), define \(d_i(j)=\alpha_i-\sum_{j'\succeq_i j}x_{ij'}\) and \(d_j(i)=\beta_j-\sum_{i'\succeq_j i}x_{i'j}\). The assignment is stable precisely when \(d_i(j)=0\) or \(d_j(i)=0\) for every acceptable pair. No additional tie-breaking enters this condition.
Let \(\mathrm{OPT}\) be the maximum of \(\sum_{(i,j)\in E}x_{ij}\) over stable assignments.
Does an algorithm polynomial in \(m,\tau,L,k\) always return a rational stable assignment of matched mass at least \(\frac{2k-1}{3k-2}\mathrm{OPT}\), or is achieving this approximation guarantee NP-hard?
For discrete agents with incomplete lists and ties of size at most \(k\), a polynomial-time algorithm attains this same matched-cardinality guarantee ([Könemann–Pashkovich–Tofigzade](https://arxiv.org/abs/2005.05228)).
For unit-capacity bipartite fractional matchings under the stated ordinal stability condition, every integral matching in a decomposition of a stable fractional matching is stable ([Chen–Roy–Sorge](https://www.ijcai.org/proceedings/2021/0013.pdf)). This result does not settle the approximation question for arbitrary binary-rational masses; no result settling that question was located.
The general question remains unresolved for $k\ge2$ and arbitrary binary-rational masses.
The main advance here is to repair the algorithmic gap identified by the verifier: independently ranked parallel contracts can be handled by a polynomial-size reduction to a simple directed stable-flow instance. Consequently, the $\frac23$ approximation from the notes is an unconditional polynomial-time algorithm.
I also prove two limitations of particular approaches:
Neither limitation establishes hardness of the requested guarantee.
Write $c_v$ for the mass of type $v$, and write $x(v)$ for its total assigned mass. Feasibility gives the identity
$$
d_v(e)=c_v-x(v)+\sum_{f\prec_v e}x_f.
$$
Here the sum runs over incident edges whose partners are strictly worse than the partner on $e$. Every term on the right is nonnegative. Thus a deficit is positive exactly when the type has unmatched mass or positive mass assigned to a strictly worse partner.
We first allow multiple, independently ranked contracts between the same two types.
Let $H$ be a finite bipartite multigraph. Each vertex $v$ has positive rational capacity $c_v$, each contract $e$ has rational upper capacity $u_e>0$, and each vertex strictly ranks its incident contracts.
For a feasible contract allocation $z$, define
$$
D_v(e)=c_v-\sum_{f\succeq_v e}z_f.
$$
Call $e=ij$ blocking when
$$
z_e<u_e,\qquad D_i(e)>0,\qquad D_j(e)>0.
$$
A contract allocation is stable when no contract blocks.
The following algorithmic result will be used.
Stable-flow theorem. In a finite simple directed network with nonnegative capacities, a source, a sink, and strict rankings separately over the incoming and outgoing arcs of each nonterminal, a stable flow can be computed in polynomial time. Stability means absence of a directed walk whose arcs are all unsaturated, whose start is the source or prefers its first arc to a positive-flow outgoing arc, and whose end is the sink or prefers its last arc to a positive-flow incoming arc. The algorithm uses bottleneck augmentations and comparisons. This is [Cseh–Matuschke, Theorem 2](https://arxiv.org/pdf/1309.3701).
Delete isolated vertices, retaining them as unmatched types in the final output. If there are no contracts, return the zero allocation.
For each remaining applicant $i$, position $j$, and contract $e=ij$, create arcs
$$
s\longrightarrow i,\qquad
i\longrightarrow p_e\longrightarrow j,\qquad
j\longrightarrow t,
$$
where every contract has its own new vertex $p_e$. Give these arcs capacities
$$
c(si)=c_i,\qquad
c(ip_e)=c(p_ej)=u_e,\qquad
c(jt)=c_j.
$$
At $i$, rank the outgoing arcs $ip_e$ according to its contract ranking. At $j$, rank the incoming arcs $p_ej$ according to its contract ranking. Every other incoming or outgoing list is a singleton.
This is a simple directed network: distinct contracts have distinct intermediate vertices, even when their endpoints coincide. Every nonterminal has both incoming and outgoing arcs. Its numbers of vertices and arcs are polynomial in the contract input size.
Feasible allocations and feasible flows correspond bijectively:
$$
f(ip_e)=f(p_ej)=z_e,\qquad
f(si)=z(i),\qquad
f(jt)=z(j).
$$
The equalities follow from flow conservation.
Lemma 1. Under this correspondence, a contract allocation is stable if and only if its flow is stable.
Proof. A blocking walk cannot start at $p_e$ or $j$: each has just one outgoing arc, so it cannot strictly prefer that arc to another positive-flow outgoing arc. Similarly, it cannot end at $i$ or $p_e$, because each has just one incoming arc.
The network is layered and acyclic. Therefore every blocking walk contains exactly one segment
$$
i\longrightarrow p_e\longrightarrow j,
$$
possibly preceded by $s\longrightarrow i$ and possibly followed by $j\longrightarrow t$.
The two contract arcs are unsaturated exactly when $z_e<u_e$. A permissible start exists exactly when either:
By the deficit identity, these alternatives are equivalent to $D_i(e)>0$. The corresponding alternatives at the end are equivalent to $D_j(e)>0$. Thus a blocking walk exists exactly when a blocking contract exists. $\square$
This proves polynomial-time computability for the parallel-contract model, without extending a simple-graph stable-allocation theorem by assertion.
For binary-rational capacities, clear denominators using their product $Q$. The product has polynomial bit length. Starting from zero, bottleneck augmentations preserve integral flow values on the scaled instance. All values remain bounded by the scaled capacities, so exact arithmetic has polynomial bit complexity. Dividing by $Q$ gives a rational output.
In all applications below, put
$$
u_e=\min(c_i,c_j)
$$
for every contract $e=ij$. These upper capacities are already implied by vertex feasibility.
If $z_e=u_e$, an endpoint attaining this minimum assigns its entire capacity to $e$. Its deficit at $e$ is therefore zero. Consequently, with these capacities, contract stability is equivalent to
$$
D_i(e)=0\quad\text{or}\quad D_j(e)=0
$$
for every contract, including saturated contracts.
For an original instance, strictly refine each tie and apply the contract algorithm with one contract per acceptable pair. A refined upper contour is contained in the original weak upper contour. Hence a zero refined deficit implies a zero original deficit.
We have therefore also established existence of a rational stable assignment for every instance in the question.
This section establishes attainment of the optimum and the integrality fact needed later.
Let $P$ be the feasible-assignment polytope, with one coordinate for each edge in $E$. It is bounded because
$$
0\le x_{ij}\le\min(\alpha_i,\beta_j).
$$
For each acceptable edge, choose one endpoint. Let $\sigma$ record these choices, and impose zero deficit at the chosen endpoint of every edge. Denote the resulting subset of $P$ by $P_\sigma$.
Every deficit is a nonnegative affine function on $P$. Its zero set, when nonempty, is a face. Intersections of these zero sets are also faces: they are the zero set of the sum of the chosen nonnegative deficits. Directly from the stability condition,
$$
\{x:x\text{ is stable}\}=\bigcup_\sigma P_\sigma.
$$
This is a finite union of compact sets. It is nonempty by Section 1, so $\mathrm{OPT}$ is attained.
Choose a positive integer $Q$ divisible by all input denominators, and scale all capacities and assignments by $Q$.
Proposition 2. Every stable assignment is a convex combination of stable assignments with coordinates in $Q^{-1}\mathbb Z_{\ge0}$. In particular, an optimal stable assignment exists on this grid and has polynomial encoding length.
Proof. The constraint matrix of the scaled feasibility polytope consists of the bipartite vertex-edge incidence matrix and nonnegativity rows. The incidence matrix is totally unimodular: negate all position rows to obtain a directed incidence matrix.
To verify total unimodularity, consider a square submatrix. If some column has at most one nonzero entry, determinant expansion reduces to a smaller submatrix. Otherwise every column has two opposite entries, so the rows sum to zero and the determinant vanishes. Induction gives determinants in $\{0,1,-1\}$. Appending signed unit rows preserves this property by the same expansion argument.
The scaled right-hand sides are integers. At a vertex, a nonsingular square system of active constraints has determinant $\pm1$, so its solution is integral.
Now take a stable assignment $x$ and choose $\sigma$ with $x\in P_\sigma$. Every vertex of this face is a vertex of $P$. Decomposing $Qx$ into vertices of the scaled face therefore gives integral stable allocations. Dividing by $Q$ proves the convex-combination statement.
For an optimum, maximize the mass objective over a face containing that optimum. Some vertex of the face attains the same objective value and is a grid assignment.
Taking $Q$ to be the product of the input denominators gives $\log Q=O(L)$. Each scaled capacity, and each bounded scaled coordinate, has $O(L)$ bits. Thus the optimal grid assignment has polynomial encoding length. $\square$
It follows that the decision problem asking whether a stable assignment reaches a supplied rational threshold belongs to $\mathrm{NP}$: a grid optimum supplies a polynomial-size certificate, and feasibility, stability, and the objective can be checked by exact rational arithmetic.
Replace each acceptable edge $e$ by three parallel contracts
$$
X_e,\quad Y_e,\quad Z_e,
$$
each with capacity $\min(\alpha_i,\beta_j)$. Keep the original vertex capacities.
Fix an order within each original tie. For an ordered tie $T$, let $X(T)$ denote its ordered list of $X$-contracts, and define $Y(T),Z(T)$ similarly.
Use these strict auxiliary rankings:
| Endpoint | For each original tie, in tier order | After all these blocks |
|---|---|---|
| Applicant | $X(T)$ followed by $Y(T)$ | All $Z$-contracts, in original preference order |
| Position | $Z(T)$ followed by $Y(T)$ | All $X$-contracts, in original preference order |
Section 1 computes a rational stable auxiliary allocation $A$ in polynomial time. Project it to
$$
M_e=A_{X_e}+A_{Y_e}+A_{Z_e}.
$$
The projection is feasible because all contract variants share the original vertex capacities.
Lemma 3. The projected assignment $M$ is stable.
Proof. At either endpoint of $e$, every auxiliary contract ranked at least as high as $Y_e$ projects to an original partner weakly preferred to the partner on $e$. Therefore
$$
D_i^A(Y_e)\ge d_i^M(e),\qquad
D_j^A(Y_e)\ge d_j^M(e).
$$
If both original deficits were positive, both auxiliary deficits would be positive, contradicting auxiliary stability under the redundant capacities of Section 1.3. $\square$
Let $M,N$ be feasible assignments with the same vertex capacities. Remove their common part
$$
C_e=\min(M_e,N_e).
$$
Orient the residual $N$-edges from applicants to positions and the residual $M$-edges from positions to applicants.
At an applicant $i$, outgoing mass minus incoming mass is $N(i)-M(i)$. At a position $j$, it is $M(j)-N(j)$.
This weighted directed graph decomposes into directed paths from positive-imbalance vertices to negative-imbalance vertices, together with directed cycles. One justification is to add a source supplying each positive imbalance and a sink receiving each negative imbalance. Flow conservation then holds, and repeatedly removing a positive-weight source-to-sink path or cycle by its bottleneck yields a finite decomposition. Each removal eliminates an arc.
All components alternate between the two assignments. A path starting at an applicant and ending at a position has $q+1$ residual $N$-edges and $q$ residual $M$-edges; call it an $N$-augmenting path. Its endpoints are underfilled in $M$, since
$$
M(i)<N(i)\le\alpha_i,\qquad
M(j)<N(j)\le\beta_j.
$$
Every other path has at most as many $N$-edges as $M$-edges, and every cycle has equal numbers.
Consequently, if every $N$-augmenting path has at least five edges, then
$$
|N|\le\frac32|M|.
$$
Indeed, on such a path $q\ge2$, so
$$
q+1\le\frac32q.
$$
Multiply by the component’s weight and sum over all components. The same inequality holds for the other components and for the common part.
Let $N$ now be stable in the original instance.
An $N$-augmenting path of length one would connect two types underfilled in $M$. Their acceptable edge would have positive deficits at both ends, contradicting Lemma 3.
Suppose there is a length-three $N$-augmenting path
$$
a_0-b_0-a_1-b_1.
$$
Set
$$
e=a_0b_0,\qquad g=a_1b_0,\qquad f=a_1b_1.
$$
The residual masses imply
$$
N_e>0,\qquad M_g>0,\qquad N_f>0.
$$
The endpoint $a_0$ is underfilled in $A$, because projection preserves its total allocation. Thus
$$
D_{a_0}^A(Z_e)>0.
$$
Auxiliary stability forces
$$
D_{b_0}^A(Z_e)=0.
$$
Similarly, underfilling of $b_1$ gives
$$
D_{a_1}^A(X_f)=0.
$$
Choose a variant $T_g$ with $A_{T_g}>0$. The zero deficits imply
$$
T_g\succeq_{b_0} Z_e,\qquad
T_g\succeq_{a_1} X_f.
$$
The contracts belong to distinct original edges, so both inequalities are strict.
At a position every $X$-contract is below every $Z$-contract, excluding $T_g=X_g$. At an applicant every $Z$-contract is below every $X$-contract, excluding $T_g=Z_g$. Hence $T_g=Y_g$.
Within a position’s original tie, all $Z$-contracts precede all $Y$-contracts. Therefore
$$
Y_g\succ_{b_0}Z_e
$$
requires $b_0$ to strictly prefer $a_1$ to $a_0$ in the original instance. Similarly,
$$
Y_g\succ_{a_1}X_f
$$
requires $a_1$ to strictly prefer $b_0$ to $b_1$.
Positive $N$-mass on $e$ and $f$ is therefore strictly worse-assigned mass at the respective endpoints of $g$. The deficit identity yields
$$
d_{b_0}^{N}(a_1)>0,\qquad
d_{a_1}^{N}(b_0)>0,
$$
contradicting stability of $N$.
Thus every $N$-augmenting path has at least five edges.
Theorem 4. For arbitrary binary-rational masses and arbitrary ties, a polynomial-time algorithm returns a rational stable assignment $M$ satisfying
$$
|M|\ge\frac23\mathrm{OPT}.
$$
Proof. Apply the preceding comparison to an optimal stable assignment, whose existence was established in Section 2. The auxiliary instance has $3|E|$ contracts and polynomial encoding length, and Section 1 computes its stable allocation in polynomial time. $\square$
Lemma 5. In a bipartite contract instance with strict rankings and redundant contract capacities, all stable allocations have the same total mass.
Proof. Let $M,N$ be stable and use the alternating decomposition from Section 3, now contract by contract. Suppose it contains an $N$-augmenting path
$$
a_0-b_0-a_1-b_1-\cdots-a_s-b_s.
$$
Write $e_t=a_tb_t$ for its $N$-contracts and $g_t=a_{t+1}b_t$ for its $M$-contracts.
If $s=0$, both endpoints are underfilled in $M$, immediately contradicting its stability.
Otherwise, $a_0$ is underfilled in $M$. Stability of $M$ at $e_0$ forces $b_0$ to allocate its full capacity to contracts at least as good as $e_0$. Since $M_{g_0}>0$ and the rankings are strict,
$$
g_0\succ_{b_0}e_0.
$$
Positive $N_{e_0}$ then gives $D_{b_0}^{N}(g_0)>0$. Stability of $N$ forces $D_{a_1}^{N}(g_0)=0$, and positive $N_{e_1}$ gives
$$
e_1\succ_{a_1}g_0.
$$
Thus positive $M_{g_0}$ gives $D_{a_1}^{M}(e_1)>0$.
Repeating these deductions along the path yields
$$
D_{a_s}^{M}(e_s)>0.
$$
Its terminal position $b_s$ is underfilled in $M$, so $D_{b_s}^{M}(e_s)>0$ as well, contradicting stability.
There is no $N$-augmenting path. Every remaining component contains at most as much $N$-mass as $M$-mass, so $|N|\le|M|$. Interchanging the allocations gives equality. $\square$
When $k=1$, the original rankings are strict. Section 1 computes a stable assignment, and Lemma 5 proves it optimal. This settles the requested guarantee for $k=1$.
Suppose every listed type has the same positive rational mass $c$. Scale by $1/c$ to obtain unit vertex capacities.
Proposition 2, applied to these integral capacities, gives an integral optimal stable assignment. Integral feasibility with unit capacities makes it a matching. Its deficit condition is precisely discrete weak stability: a pair blocks exactly when both endpoints are unmatched or matched to strictly worse partners.
The [Könemann–Pashkovich–Tofigzade theorem](https://arxiv.org/pdf/2005.05228) computes a stable matching whose cardinality is at least
$$
\frac{2k-1}{3k-2}
$$
times the maximum stable cardinality for incomplete lists with ties of size at most $k$. Its hypotheses hold unchanged after scaling. Multiplying the resulting matching by $c$ therefore establishes the requested guarantee for equal masses.
Consider the following unit-mass instance. Parentheses denote ties and specify the within-tie auxiliary order.
| Applicant | Preferences | Position | Preferences |
|---|---|---|---|
| $a_0$ | $b_0$ | $b_0$ | $a_1\succ a_0$ |
| $a_1$ | $(b_0,b_1)$ | $b_1$ | $(a_2,a_1)$ |
| $a_2$ | $b_1\succ b_2$ | $b_2$ | $a_2$ |
The perfect matching
$$
N=\{a_0b_0,a_1b_1,a_2b_2\}
$$
is stable. On the unused edge $a_1b_0$, applicant $a_1$ is assigned to an indifferent partner, so its deficit is zero. On the unused edge $a_2b_1$, position $b_1$ is assigned to an indifferent partner, so its deficit is zero. Every assigned edge has zero deficits at both endpoints. Hence
$$
\mathrm{OPT}=3.
$$
Put
$$
g_0=a_1b_0,\qquad g_1=a_2b_1.
$$
In the auxiliary construction, allocate one unit to each of $Y_{g_0},Y_{g_1}$ and zero elsewhere. This allocation is stable:
At each identified endpoint, the full unit capacity is assigned above the contract being checked, giving zero deficit.
This is a stable auxiliary allocation of mass $2$. The auxiliary rankings are strict and all contract capacities are redundant. Lemma 5 therefore gives the stronger conclusion:
$$
|A|=2
\quad\text{for every stable auxiliary allocation }A
$$
under these fixed auxiliary rankings.
Projection preserves total mass. Thus even optimizing among stable outputs of this auxiliary instance cannot improve its ratio beyond
$$
\frac23.
$$
This is a limitation of the specified construction and rankings; it is not a hardness theorem for the task.
Here is a separate obstruction that does not occur for discrete unit-capacity stable matchings.
Take applicant types $a_1,a_2$, each of mass $2$, and position types $b,c_1,c_2$ with masses
$$
\beta_b=2,\qquad \beta_{c_1}=\beta_{c_2}=1.
$$
The acceptable edges and preferences are
$$
a_t:\ b\succ c_t\quad(t=1,2),\qquad
b:\ (a_1,a_2),\qquad
c_t:\ a_t.
$$
Thus the maximum tie size is $2$.
Assign
$$
x_{a_1b}=x_{a_2b}=x_{a_1c_1}=x_{a_2c_2}=1.
$$
This assignment is feasible and has mass $4$. At $b$, both acceptable applicants are tied and its full capacity is assigned to them, so its deficit is zero on both incident edges. Each $c_t$ is fully assigned to its sole acceptable applicant, so its deficit is also zero. Hence the assignment is stable.
Both sides have total mass $4$, proving
$$
\mathrm{OPT}=4.
$$
Now strictly refine $b$’s tie as $a_1\succ_b a_2$. For the edge $a_1b$, both endpoints rank one another first and have capacity $2$. Consequently,
$$
d_{a_1}(b)=d_b(a_1)=2-x_{a_1b}.
$$
Stability forces $x_{a_1b}=2$. Feasibility then forces
$$
x_{a_1c_1}=0,\qquad x_{a_2b}=0.
$$
On $a_2c_2$, the applicant deficit is
$$
2-x_{a_2c_2}>0,
$$
because $x_{a_2c_2}\le1$. Stability therefore forces the position deficit to vanish, giving $x_{a_2c_2}=1$. Every stable assignment under this refinement has mass $3$.
For the opposite refinement, the same calculation with indices exchanged again gives mass $3$. The indicated allocations are stable: the applicant assigned entirely to $b$ has zero deficit toward its lower-ranked position, and $b$ has zero deficit toward its lower-ranked applicant.
Therefore
$$
\max\{|x|:x\text{ is stable under some strict type-level refinement}\}
=3<4=\mathrm{OPT}.
$$
Moreover, the original mass-$4$ assignment is a vertex of the feasibility polytope. Saturation of $c_1,c_2$ fixes their incident allocations to $1$, and saturation of $a_1,a_2$ then fixes both allocations to $b$ to $1$. These active constraints uniquely determine all four coordinates.
Thus even a grid optimum at a transportation vertex need not survive any strict refinement of the type preferences. Here the refinement ratio is exactly $\frac34$, the requested coefficient for $k=2$, so the example does not refute that coefficient.
For every finite $k\ge2$,
$$
\frac{2k-1}{3k-2}-\frac23
=\frac{1}{3(3k-2)}>0.
$$
The repaired polynomial-time algorithm consequently leaves a positive gap from the target.
The rational-grid result removes irrationality as an obstacle, but does not permit efficient unit expansion. For example, masses $2^B$ have $O(B)$-bit descriptions while cloning produces exponentially many agents. Full indifference among clones also enlarges ties beyond the bound on distinct types.
What remains is an algorithm exploiting the bounded number of types per tie with polynomial dependence on binary capacity descriptions, or a hardness proof for precisely that approximation guarantee.
⟨structured verdict parsed — rendered above⟩
Overall assessment: partial, with sound proved progress. The output establishes a polynomial-time $\frac23$ approximation for arbitrary binary-rational masses, rational optimal witnesses, and the requested guarantee in two special cases. It does not settle the requested guarantee for general unequal masses and $k\ge2$. This limitation is explicitly acknowledged by the prover.
I found no false mathematical step or substantive gap in the results actually proved.
1. Deficit identity and contract model
The identity
$$
d_v(e)=c_v-x(v)+\sum_{f\prec_v e}x_f
$$
is correct: the incident allocations partition into those weakly preferred to the partner on $e$ and those strictly worse. Feasibility makes both the unmatched mass and every summand nonnegative. Consequently, the stated characterization of positive deficit is valid.
In the strict contract model, the same identity applies with contracts replacing partners. Including the requirement $z_e<u_e$ in the definition of a blocking contract is consistent with the subsequent network reduction.
2. Stable-flow theorem and reduction
The cited theorem applies as written. The source defines separate strict rankings of incoming and outgoing arcs, uses exactly the stated blocking-walk conditions, and proves polynomial-time computation in Theorem 2. Its network assumptions include absence of loops and parallel arcs and the presence of both incoming and outgoing arcs at every nonterminal. [Cseh–Matuschke](https://arxiv.org/pdf/1309.3701)
The constructed network satisfies these hypotheses:
The feasible-flow correspondence is bijective. Conservation at each intermediate vertex equates its two contract-arc flows; conservation at applicants and positions determines the terminal-arc flows.
Lemma 1 is correct. The singleton rankings exclude starts at positions or intermediate vertices and exclude ends at applicants or intermediate vertices. Layering then restricts a blocking walk to one contract segment, with optional terminal arcs. Its permissible starts and ends correspond exactly to positive contract deficits, and the two internal arcs are unsaturated exactly when $z_e<u_e$.
The rational-arithmetic argument also stands. Clearing denominators produces integers with polynomial bit length. The cited algorithm starts from zero and augments by residual bottlenecks, preserving integrality after scaling. Its polynomial iteration bound, together with bounded integral flow values, supplies polynomial bit complexity.
3. Redundant capacities and existence
With
$$
u_e=\min(c_i,c_j),
$$
saturation of a contract exhausts at least one endpoint’s entire capacity. That endpoint therefore has zero deficit at the contract. This correctly removes the apparent distinction between unsaturated-contract stability and the deficit disjunction used later.
Strict refinement also works in the stated direction: the refined upper contour is contained in the original weak upper contour. Thus a zero refined deficit forces the corresponding original deficit to vanish. The existence claim covers isolated types and the empty acceptable-edge set through the explicitly stated handling of those cases.
4. Attainment, grid witnesses, and certificate size
Section 2 is correct.
Each deficit is nonnegative on the feasible polytope, so its nonempty zero set is a face. A simultaneous collection of selected zero deficits is also a face, as shown by summing the nonnegative affine functions. The finite union of these faces is exactly the stable set.
Boundedness, closedness, and the previously established nonemptiness imply attainment of the objective.
The total-unimodularity proof is valid. After signing the position rows, every incidence column has opposite signs at its endpoints. The determinant argument covers all square submatrices, and adding nonnegativity rows preserves total unimodularity.
Consequently, vertices of the scaled feasible polytope are integral. Vertices of each stability face are vertices of that polytope and remain stable. The convex-decomposition and optimal-grid-witness conclusions follow.
The encoding bound is sufficient: the product of input denominators has logarithm bounded by the total input length, and scaled coordinates are bounded by scaled capacities. This also justifies the claimed polynomial-size certificates for the threshold decision problem. Membership in $\mathrm{NP}$ does not itself classify the approximation task.
5. Auxiliary projection
The rankings in Section 3.1 define strict orders once within-tie orders are fixed.
Lemma 3 uses the correct inequality direction:
$$
D_i^A(Y_e)\ge d_i^M(e),\qquad
D_j^A(Y_e)\ge d_j^M(e).
$$
Every auxiliary contract above $Y_e$ projects to an originally weakly preferred partner, while the original upper contour can contain additional projected allocations.
Thus positive original deficits at both endpoints would force positive auxiliary deficits at both endpoints of $Y_e$, contradicting auxiliary stability. Feasibility and stability of the projection are established.
6. Weighted decomposition and approximation
Removing common edge mass and orienting the two residual assignments oppositely gives the stated vertex imbalances.
The source-and-sink construction correctly supports a finite decomposition into directed paths and cycles. Removing a bottleneck eliminates at least one positive-weight arc. Bipartiteness and the chosen orientations ensure alternation.
The path classification is correct:
The endpoints of an $N$-augmenting path are underfilled in $M$, by the displayed imbalance inequalities. If each such path has at least five edges, then its edge counts satisfy
$$
q+1\le\frac32q.
$$
Multiplying by component weights and including the common mass proves the claimed comparison.
The exclusion of short augmenting paths is also valid:
Therefore Theorem 4 establishes the polynomial-time $\frac23$ approximation claimed.
7. Strict preferences and equal masses
Lemma 5 is correct. Along an alleged augmenting path, strict rankings and positive residual allocations propagate the displayed strict preference comparisons and positive deficits. At the terminal edge, both deficits become positive, contradicting stability. Reversing the comparison proves mass equality.
For $k=1$, this establishes optimality of the computed stable assignment.
For equal positive masses, scaling produces unit capacities. Proposition 2 supplies an integral optimal stable assignment, which is a matching. Its deficit condition agrees with discrete weak stability.
The cited discrete theorem states the required coefficient for incomplete lists with bounded ties; its running-time analysis is polynomial in the number of agents and the tie bound. Thus its application after scaling is justified. [Könemann–Pashkovich–Tofigzade](https://arxiv.org/pdf/2005.05228)
8. The two limitations
The six-type example checks out. The perfect matching is stable and proves $\mathrm{OPT}=3$. Each listed auxiliary-contract check identifies an endpoint fully allocated to a better contract. The mass-$2$ auxiliary allocation is therefore stable. Lemma 5 then correctly implies that every stable allocation under those fixed auxiliary rankings has mass $2$.
This establishes a limitation of that construction and those rankings, without establishing hardness.
The unequal-mass example also checks out. The mass-$4$ assignment is feasible and stable. Either strict refinement forces the preferred applicant’s entire mass onto $b$ and leaves exactly one unit matched to the other applicant’s private position, giving total mass $3$.
The active constraints listed uniquely determine the four coordinates, so the vertex claim is valid. The ratio is
$$
\frac34=\frac{2\cdot2-1}{3\cdot2-2}.
$$
Accordingly, this example does not refute the requested guarantee.
9. Blocking issue and minimum required continuation
The target coefficient exceeds the proved general coefficient:
$$
\frac{2k-1}{3k-2}-\frac23
=\frac{1}{3(3k-2)}>0.
$$
Hence the general approximation theorem does not answer USER_TASK.
Major issue — incomplete target resolution: For arbitrary unequal binary-rational masses and $k\ge2$, neither the requested approximation algorithm nor hardness of achieving that coefficient is established. This is an acknowledged incompleteness, not a false claim of success.
No expositional clarification can close this gap. A further submission must establish one of the two requested alternatives with the stated input encoding and type-based tie bound. The proved auxiliary construction and refinement obstruction do not supply that conclusion.
⟨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.