Answer: \(\mathrm{P}\): every valid instance admits a rational weakly stable allocation.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet $k \geq 3$. Then it is NP-complete to determine whether a~$\DSMCYC{k}$ instance has a~weakly stable matching.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For each side \(t\in\{0,1,2\}\), let \(T_t\) be a finite set of types, each with a strict ranking of the types in \(T_{t+1\bmod 3}\), and let \(\mu_t(a)\in\mathbb{Q}_{>0}\) be their masses, summing to \(1\) on each side. Does there exist a rational allocation \(x_{a_0,a_1,a_2}\ge 0\) and unmatched mass \(u_t(a)\ge 0\) satisfying \(\sum_{\mathbf a:a_t=a}x_{\mathbf a}+u_t(a)=\mu_t(a)\), such that no triple \((a_0,a_1,a_2)\) has positive willing mass on all three sides? Here the willing mass of type \(a\in T_t\) for next-side type \(b\) is \(u_t(a)+\sum_{\mathbf c:c_t=a,\ b\succ_a c_{t+1}}x_{\mathbf c}\).
There are \(m=3\) sides, indexed by \(t\in\{0,1,2\}\), with indices interpreted modulo \(3\). Each side has a nonempty finite support \(T_t\). Every type \(a\in T_t\) has a strict complete ranking \(\succ_a\) of \(T_{t+1}\), cares only about its next-side partner, and prefers every partner to being unmatched.
A society is given by its support: the list of the \(\tau=\sum_t|T_t|\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Masses satisfy \(\sum_{a\in T_t}\mu_t(a)=1\) on each side. Let \(L\) be the total input bit length, including rankings and masses; state running times in \(m,\tau,L\), with \(m=3\) fixed.
An allocation consists of \(x_{\mathbf a}\in\mathbb Q_{\ge0}\) for every \(\mathbf a\in T_0\times T_1\times T_2\), and unmatched masses \(u_t(a)\in\mathbb Q_{\ge0}\), satisfying \(\sum_{\mathbf a:a_t=a}x_{\mathbf a}+u_t(a)=\mu_t(a)\) for every \(t,a\).
Define willing mass by \(W_t(a,b)=u_t(a)+\sum_{\mathbf c:c_t=a,\ b\succ_a c_{t+1}}x_{\mathbf c}\). An allocation is weakly stable if every triple \(\mathbf a\) has some side \(t\) with \(W_t(a_t,a_{t+1})=0\).
Is deciding whether a rational weakly stable allocation exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite societies with equally many agents on each side and strict complete cyclic preferences, weakly stable matching existence is NP-complete ([Lam–Plaxton](https://arxiv.org/abs/1905.02844)). No result settling the exact mass-allocation decision problem above was located in the literature search.
The decision problem is polynomial-time solvable. Every valid instance admits a rational weakly stable allocation. This follows from Scarf’s lemma for fractional hypergraph matchings. The proof applies to the exact willing-mass definition in the question.
We use the following form of Scarf’s lemma.
Let \(A\in\mathbb R_{\ge 0}^{n\times N}\) have a nonzero entry in every column, and let \(b\in\mathbb R_{>0}^{n}\). For each row \(i\), specify a strict total order \(\widehat{\succ}_i\) on the columns \(j\) with \(A_{ij}>0\). Then the polytope
\(P=\{x\in\mathbb R_{\ge 0}^{N}:Ax\le b\}\)
has an extreme point \(x\) such that every column \(j\) is dominated at some row \(i\): namely,
\(A_{ij}>0,\qquad (Ax)_i=b_i,\qquad k\widehat{\succeq}_i j\text{ whenever }A_{ik}x_k>0.\)
Here \(\widehat{\succeq}_i\) is the reflexive closure of \(\widehat{\succ}_i\). This statement, including arbitrary nonnegative real capacities, appears as Lemma 1 in [Biró–Csáji–Schlotter, *Stable Hypergraph Matching in Unimodular Hypergraphs*](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html).
Thus domination means that the row is saturated and every positive allocation incident to that row is at least as preferred as the proposed column.
Treat types on different sides as distinct vertices, writing
\(V=\{(t,a):t\in\{0,1,2\},\ a\in T_t\}.\)
For every triple \(\mathbf a=(a_0,a_1,a_2)\), introduce the hyperedge
\(e_{\mathbf a}=\{(0,a_0),(1,a_1),(2,a_2)\}.\)
Let \(E\) be this collection of hyperedges. Its size is
\(N=|T_0||T_1||T_2|\le\tau^3.\)
Let \(A\) be the vertex–hyperedge incidence matrix: \(A_{v,e}=1\) if \(v\in e\), and \(A_{v,e}=0\) otherwise. Give vertex \(v=(t,a)\) capacity \(b_v=\mu_t(a)\).
All capacities are positive, and every column of \(A\) contains exactly three ones. Therefore the matrix and capacity hypotheses of Scarf’s lemma hold. The polytope \(P\) is nonempty because it contains zero, and bounded because each coordinate satisfies \(x_e\le b_v\) for every \(v\in e\).
It remains to define strict preferences over incident hyperedges. At vertex \(v=(t,a)\), first compare hyperedges according to their next-side partners:
\(c_{t+1}\succ_a d_{t+1}\quad\Longrightarrow\quad e_{\mathbf c}\widehat{\succ}_v e_{\mathbf d}.\)
Break ties between hyperedges with the same next-side partner arbitrarily. This produces a strict total order. Crucially,
\(e_{\mathbf c}\widehat{\succeq}_v e_{\mathbf a}\quad\Longrightarrow\quad c_{t+1}=a_{t+1}\text{ or }c_{t+1}\succ_a a_{t+1}.\)
Thus a hyperedge that is at least as good in the refined order never supplies a strictly worse next-side partner.
Apply Scarf’s lemma to obtain an extreme point \(x\in P\) dominating every hyperedge. Define unmatched masses by
\(u_t(a)=\mu_t(a)-\sum_{\mathbf c:c_t=a}x_{e_{\mathbf c}}.\)
These are nonnegative because \(Ax\le b\), and the allocation equations hold by definition.
Fix any triple \(\mathbf a\). Its hyperedge is dominated at some vertex \(v=(t,a_t)\). Saturation gives
\(\sum_{\mathbf c:c_t=a_t}x_{e_{\mathbf c}}=\mu_t(a_t),\)
so \(u_t(a_t)=0\).
Moreover, every incident hyperedge with positive mass is at least as good as \(e_{\mathbf a}\) in the refined order. Consequently,
\(x_{e_{\mathbf c}}>0,\ c_t=a_t\quad\Longrightarrow\quad \neg(a_{t+1}\succ_{a_t}c_{t+1}).\)
Every summand in the willing-mass expression is therefore zero, yielding
\(W_t(a_t,a_{t+1})=u_t(a_t)+\sum_{\mathbf c:c_t=a_t,\ a_{t+1}\succ_{a_t}c_{t+1}}x_{e_{\mathbf c}}=0.\)
Since the triple was arbitrary, the allocation is weakly stable exactly as defined in the question.
The point supplied by Scarf’s lemma is an extreme point of \(P\), whose defining matrix and right-hand side are rational.
For completeness, the active constraint normals at an extreme point must span the ambient space. Otherwise, a nonzero direction orthogonal to all active normals would allow sufficiently small perturbations in both directions: active constraints would remain equalities, and the finitely many inactive constraints would remain satisfied. That would contradict extremality.
Select a full-rank subsystem of active constraints. Its coefficients and right-hand side are rational, and \(x\) is its unique solution. Cramer’s rule therefore gives \(x\in\mathbb Q_{\ge0}^{N}\). The unmatched masses, being differences of rational quantities, are rational as well.
This proves rational existence, rather than merely real existence.
In fact, every weakly stable allocation under the stated normalization has zero unmatched mass.
Let \(X=\sum_{\mathbf a}x_{\mathbf a}\). Summing the allocation equations on each side gives
\(\sum_{a\in T_t}u_t(a)=1-X\qquad\text{for every }t.\)
If \(X<1\), each side contains a type \(a_t\) with \(u_t(a_t)>0\). For the resulting triple,
\(W_t(a_t,a_{t+1})\ge u_t(a_t)>0\qquad\text{for all }t,\)
contradicting weak stability. Hence \(X=1\), and nonnegativity forces every unmatched mass to vanish.
On inputs satisfying the premises, the decision algorithm simply returns YES, taking \(O(1)\) time. Including input reading and validation, a straightforward implementation using elementary integer arithmetic takes \(O(L^3)\) bit operations, with \(m=3\) fixed and \(\tau\le L\).
The [Lam–Plaxton hardness result](https://arxiv.org/abs/1905.02844) concerns integral matchings. It does not contradict the existence proved here: divisible triple masses admit a stable fractional solution even when no integral stable matching exists.
The proof establishes existence and the decision complexity. It does not assert a polynomial-time algorithm for constructing a stable allocation.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes that every valid instance admits a rational weakly stable allocation, so the stated existence decision problem is polynomial-time solvable. No major or minor mathematical issues were found.
I checked Lemma 1 in [Biró–Csáji–Schlotter](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html). It supplies a dominating extreme point under the matrix, capacity, and strict-order hypotheses stated by the prover. Its domination condition uses the reflexive preference relation, exactly as required here. The source permits nonnegative real capacities; restricting to strictly positive capacities is valid.
No integrality, unimodularity, or normality hypothesis is required for this fractional conclusion.
Tagging vertices by their side prevents accidental identification of types on different sides. Each triple corresponds to exactly one hyperedge, and every column of the incidence matrix has exactly three positive entries.
The capacities are positive rational numbers by the support assumption. The polytope contains zero. Each coordinate is bounded by the capacity of any incident vertex, so boundedness is correctly established.
The count \(N=|T_0||T_1||T_2|\le \tau^3\) is valid. The construction does not confuse support size with the number of possible types.
Ordering incident hyperedges first by next-side partner and then breaking ties produces a strict total order on a finite set.
The critical implication is correct: if an incident hyperedge is at least as preferred as the proposed hyperedge in the refined order, its next-side partner is either identical to or strictly preferred to the proposed partner. Arbitrary tie-breaking cannot reverse comparisons between distinct next-side partners.
The proof only needs this implication; it does not assume an equivalence between refined hypergraph stability and the original stability definition.
For every triple, Scarf’s lemma supplies an incident vertex where the capacity is saturated and every positive incident allocation is at least as preferred as that triple.
Saturation makes that type’s unmatched mass zero. Preference refinement ensures that no positive incident allocation supplies a next-side partner strictly worse than the proposed partner. Consequently, every term counted in the relevant willing-mass sum is zero.
Thus the conclusion is precisely \(W_t(a_t,a_{t+1})=0\) for at least one side of every triple. The quantifiers agree with USER_TASK. The argument also covers triples receiving positive allocation.
The prover correctly uses the extreme-point guarantee, rather than merely the existence of a real feasible point.
The active constraints include both capacity inequalities and coordinate nonnegativity inequalities. If their normals failed to span the ambient space, the stated two-sided perturbation would preserve active equalities and, for sufficiently small displacement, all inactive inequalities. This would contradict extremality.
A full-rank subsystem therefore determines the point uniquely. Its coefficients and right-hand side are rational, so Cramer’s rule gives rational allocation coordinates. The unmatched masses are rational differences.
No bound on witness bit length is needed for the claimed constant-answer decision algorithm.
Summing allocation equations on each side gives total unmatched mass \(1-X\), where \(X\) is total allocated triple mass. Nonnegativity implies \(X\le 1\).
If \(X<1\), finiteness ensures that every side contains a type with positive unmatched mass. Selecting one such type from each side produces a triple with positive willing mass on every side, contradicting stability.
Therefore \(X=1\), and every unmatched mass vanishes. This argument correctly uses both equal side totals and the availability of every support triple.
On the promised domain of valid instances, returning YES in \(O(1)\) time is correct because universal rational existence has been proved.
Including validation, the stated \(O(L^3)\) bit-operation bound is a valid coarse polynomial bound for fixed \(m=3\): exact rational summation and ranking checks can be performed within it using elementary arithmetic. The dependence on support size is covered by \(\tau\le L\).
The prover explicitly distinguishes deciding existence from constructing an allocation. There is no unsupported claim of a polynomial-time construction algorithm.
[Lam–Plaxton](https://arxiv.org/abs/1905.02844) establishes NP-completeness for finite cyclic matching existence. The prover’s argument establishes fractional mass allocation existence and does not infer integral existence from it. The distinction is correctly maintained.
Actionable feedback: No repair or additional clarification is required for the claimed decision result.
⟨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.