Answer: \(\mathrm{NP}\text{-complete}\), even with equal dyadic masses, \(p\equiv 0\), and only length-\(2\) patterns.
Theorem 4.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet (G,w, ℓ) be an instance of Stable Barter. It is NP-hard to test whether there is a stable transaction involving all the agents, even when ℓ= 3 and ∆(G) = 6.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), an acceptable-trade relation \(E\), and Model B pay and gain values \(p\) and \(g\), decide whether nonnegative masses \(x_Q\) on directed cycle patterns \(Q\) of length \(2\) or \(3\) satisfy \(\sum_Q \operatorname{occ}_t(Q)x_Q=\mu_t\) for every \(t\in T\), while admitting no blocking cycle. A blocking cycle uses arcs in \(E\) and distinct agents drawn from positive-mass status cohorts \((t_i,b_i)\), with \(g(t_{i-1},t_i)-p(t_i,t_{i+1})>b_i\) at every position, with indices taken cyclically.
A society is an atomless population given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also lists acceptable directed trades \(E\subseteq T\times T\) and binary-encoded functions \(p,g:E\to\mathbb Z_{\ge0}\). An arc \((s,t)\) means that an agent of type \(s\) gives to one of type \(t\), paying value \(p(s,t)\), while the recipient gains value \(g(s,t)\). Diagonal arcs allow trades between distinct agents of the same type; self-trades are excluded.
A cycle pattern \(Q=(t_1,\ldots,t_r)\), considered up to cyclic rotation, has \(r\in\{2,3\}\) and \((t_i,t_{i+1})\in E\), with cyclic indices. Types may repeat, but its agent positions are distinct. Define \(\operatorname{occ}_t(Q)=|\{i:t_i=t\}|\) and \(b_i(Q)=g(t_{i-1},t_i)-p(t_i,t_{i+1})\); balances may be negative.
A full transaction assigns real masses \(x_Q\ge0\) with \(\sum_Q\operatorname{occ}_t(Q)x_Q=\mu_t\) for every \(t\). Its status cohort \((t,b)\) has mass \(h_{t,b}=\sum_Q x_Q|\{i:t_i=t,\ b_i(Q)=b\}|\).
A blocking cycle has length \(r\in\{2,3\}\), uses arcs in \(E\), and draws distinct agents from cohorts \((t_i,b_i)\) with \(h_{t_i,b_i}>0\), such that \(g(t_{i-1},t_i)-p(t_i,t_{i+1})>b_i\) at every position. A positive-mass cohort may supply multiple distinct agents. A transaction is stable if no such cycle exists; ties do not block.
Is deciding whether a full stable transaction exists solvable in polynomial time, or is it NP-hard? State running times in \(m=|E|\), \(\tau\), and the total input bit length \(L\).
For finite agents, existence of a stable transaction covering every agent is NP-hard even with maximum cycle length \(3\), maximum total degree \(6\), and a shared nonnegative arc valuation \(p=g\). [Gupta et al.](https://www.ifaamas.org/Proceedings/aamas2018/pdfs/p1371.pdf)
No prior result settling this exact atomless cohort-based decision problem was identified in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when all masses are equal dyadic rationals, \(p\equiv 0\), and the trade graph is bipartite, so that only length-\(2\) cycle patterns exist.
Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). A deterministic exact algorithm runs in \(2^{O(\tau\log(\tau+1))}\operatorname{poly}(m,\tau,L)\) time.
Let \(\mathcal Q\) denote the finite set of allowed cycle patterns. For a full transaction \(x\), define
\[
\]
\(z_t(x)=\min\{b:h_{t,b}>0\}\).
This minimum exists: there are finitely many patterns, and fullness together with \(\mu_t>0\) guarantees an occupied cohort of every type.
Lemma 1. A full transaction \(x\) is stable if and only if every \(Q=(t_1,\ldots,t_r)\in\mathcal Q\) has a position \(i\) satisfying \(b_i(Q)\leq z_{t_i}(x)\).
Proof. If \(Q\) blocks using current balances \(c_i\), then \(c_i\geq z_{t_i}(x)\), so \(b_i(Q)>z_{t_i}(x)\) at every position.
Conversely, if these strict inequalities hold at every position, choose agents from the cohorts \((t_i,z_{t_i}(x))\). Each cohort has positive mass. As the problem explicitly permits a positive-mass cohort to supply multiple distinct agents, repeated types cause no obstruction. These agents form a blocking cycle. \(\square\)
We will also use the following consequence of the cohort definition.
Lemma 2. Suppose \(x\) and \(y\) are full transactions and every pattern used positively by \(y\) is used positively by \(x\). If \(x\) is stable, then \(y\) is stable.
Proof. Every positive cohort of \(y\) is also a positive cohort of \(x\). Therefore any blocking cycle for \(y\), with its specified current cohort balances, would also block \(x\). \(\square\)
We use the following known theorem: deciding whether a stable marriage instance with ties and incomplete lists has a perfect weakly stable matching is \(\mathrm{NP}\)-complete. Weak stability means that a pair blocks only when both participants strictly prefer each other to their assigned partners. This is Theorem 1 of [Iwama, Manlove, Miyazaki and Morita, *Stable Marriage with Incomplete Lists and Ties*](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf); their definition of matching covers every participant.
Let such an instance have sides \(U,V\), each containing \(n\geq 1\) participants, and let \(F\subseteq U\times V\) be its mutually acceptable pairs.
To ensure dyadic masses, let \(N\) be the smallest power of two satisfying \(N\geq n\). Add \(N-n\) private pairs: each added participant accepts only its designated partner, and original participants have no acceptable relationships with added participants. The padded instance has a perfect weakly stable matching exactly when the original instance does.
For each participant \(t\), encode their preference groups by integers \(u_t(s)\in\{1,\ldots,N\}\), with
\(u_t(s)>u_t(s')\) exactly when \(t\) strictly prefers \(s\) to \(s'\).
Tied partners receive equal values.
Create one type for each participant of the padded instance. Thus \(\tau=2N\), and assign every type mass \(\mu_t=1/(2N)\).
For each acceptable pair \((a,b)\), with \(a\in U\) and \(b\in V\), include both directed arcs and set
\(p(a,b)=p(b,a)=0\),
\(g(a,b)=u_b(a)\), and
\(g(b,a)=u_a(b)\).
There are no other arcs. All valuations are nonnegative integers.
Every arc switches between the two sides. Hence no closed walk of odd length exists, even with repeated types. There are no diagonal arcs, and the only allowed patterns are the pairs \(Q_{ab}=(a,b)\). Their balances are
\(b_a(Q_{ab})=u_a(b)\) and \(b_b(Q_{ab})=u_b(a)\).
Given a perfect weakly stable matching \(M\), assign \(x_{Q_{ab}}=1/(2N)\) to its matched pairs and zero to all other patterns.
Every type is covered exactly once, so the transaction is full. Each type has just one occupied balance, namely the utility of its matched partner. A blocking cycle would therefore be an acceptable pair whose participants both strictly prefer each other to their partners in \(M\). Weak stability excludes such a pair.
Conversely, suppose the constructed society has a full stable transaction \(x\). Write \(x_{ab}=x_{Q_{ab}}\) and \(y_{ab}=2N x_{ab}\). Fullness gives
\(\sum_b y_{ab}=1\) for every \(a\in U\), and
\(\sum_a y_{ab}=1\) for every \(b\in V\).
Consider the bipartite support graph containing exactly the pairs with \(y_{ab}>0\). For any \(S\subseteq U\), let \(N(S)\) denote its neighbors in this graph. Then
\[
\]
\(|S|=\sum_{a\in S}\sum_{b\in N(S)}y_{ab}
\leq\sum_{b\in N(S)}\sum_{a\in U}y_{ab}=|N(S)|\).
Thus Hall’s condition holds. Since the two sides have equal size, the support graph has a perfect matching \(M\).
Assigning mass \(1/(2N)\) to the edges of \(M\) produces a full transaction whose pattern support is contained in that of \(x\). By Lemma 2, this transaction is stable. Because its only patterns are pairs and its balances encode preferences exactly, \(M\) is weakly stable.
This proves the required equivalence.
If the original instance has \(q\) acceptable pairs, the construction has
\(\tau=2N\leq 4n\),
\(m=2(q+N-n)=O(q+n)\), and
\(L=O((q+n)\log(n+2))\).
Its preference-group encodings and output can be constructed in polynomial time. The reduction therefore proves \(\mathrm{NP}\)-hardness.
Membership in \(\mathrm{NP}\) requires showing that real-valued feasible transactions admit short rational certificates.
Suppose a stable full transaction exists, and let \(S\subseteq\mathcal Q\) be its positive pattern support. Define the incidence matrix \(A_S\) by
\((A_S)_{t,Q}=\operatorname{occ}_t(Q)\).
The polytope
\(P_S=\{y\geq 0:A_Sy=\mu\}\)
is nonempty. It is bounded: each pattern contains some type, so its coordinate is bounded by that type’s mass. Consequently \(P_S\) has an extreme point \(y\).
The columns corresponding to positive coordinates of \(y\) are linearly independent. Otherwise, a nonzero dependence supported on those coordinates would permit sufficiently small perturbations in both directions while preserving nonnegativity and the equations, contradicting extremality. Hence \(y\) uses at most \(\tau\) patterns. Lemma 2 shows that \(y\) remains stable.
To bound its bit length, let \(k\leq\tau\) be its positive support size and choose \(k\) rows giving an invertible square submatrix \(B\). Let \(D\) be the product of the input mass denominators. Its bit length is at most \(L\), and \(D\mu\) is integral.
Every column of \(B\) has nonnegative entries summing to at most \(3\), so its Euclidean norm is at most \(3\). Hadamard’s inequality gives \(|\det B|\leq 3^k\). Cramer’s rule expresses each positive coordinate as an integer divided by \(D\det B\). Since \(0<\mu_t\leq 1\), the corresponding numerator has absolute value at most \(D\sqrt{k}\,3^{k-1}\).
Thus each mass has bit length \(O(L+\tau+\log(\tau+1))\). Listing at most \(\tau\) patterns and their rational masses gives a polynomial-size certificate.
A verifier checks nonnegativity and fullness by exact rational arithmetic, computes the minimum occupied balance of every type, and applies Lemma 1 to every allowed pattern. These checks take \(\operatorname{poly}(m,\tau,L)\) bit time. Therefore the problem belongs to \(\mathrm{NP}\).
All patterns can be enumerated in \(O(\tau^2+m\tau)\) combinatorial operations. For triples, enumerate directed paths of two arcs and test the closing arc; the number of such paths is at most
\(\sum_t d^-(t)d^+(t)\leq \tau m\).
Cyclic duplicates can be removed by choosing a canonical rotation.
For each type \(t\), let \(B_t\) be the set of balances occurring at its positions in these patterns. If \(B_t\) is empty, fullness is impossible. Otherwise \(|B_t|\leq\tau^2\): a balance is determined by the predecessor and successor types.
Enumerate every threshold vector \(z\in\prod_t B_t\). For each vector:
Each iteration takes \(\operatorname{poly}(m,\tau,L)\) time.
If the linear program is feasible, every occupied balance is at least its threshold. Step 1 then excludes every blocking cycle. Conversely, the minimum occupied balances of any stable full transaction form an enumerated vector; Lemma 1 ensures that it passes Step 1, and that transaction witnesses feasibility in Step 3.
There are at most \(\tau^{2\tau}\) threshold vectors. The resulting exact running time is
\(2^{O(\tau\log(\tau+1))}\operatorname{poly}(m,\tau,L)\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction establishes NP-hardness for the stated atomless, cohort-based problem, and the certificate argument establishes membership in \(\mathrm{NP}\). The deterministic running-time bound is also justified. I found no mathematical errors or gaps requiring clarification.
The definition of \(z_t(x)\) is valid for every full transaction:
Both directions of Lemma 1 are correct. If a cycle blocks using balances \(c_i\), then \(c_i\geq z_{t_i}(x)\), so strict improvement over \(c_i\) implies strict improvement over \(z_{t_i}(x)\). Conversely, strict improvement over every indicated minimum permits the blocking agents to be drawn from those minimum-balance cohorts.
The repeated-type case is explicitly addressed using the task’s permission for a positive-mass cohort to supply multiple distinct agents. The argument therefore respects the distinction between repeated types and distinct agent positions.
The non-strict inequality in the lemma’s stability condition correctly implements the requirement that ties do not block.
Lemma 2 is also correct. Because all contributions to cohort masses are nonnegative, every positive cohort of \(y\) must arise from a positive pattern of \(y\). Support containment makes that pattern positive in \(x\), so the same cohort is positive in \(x\). Every blocking cycle for \(y\) would consequently also block \(x\). Fullness of \(y\) remains an explicit hypothesis.
The external theorem is accurately stated and applied. The cited paper defines matchings to cover all participants, defines stability with ties using strict improvement by both participants, and states in Theorem 1 that the problem with incomplete lists and ties is NP-complete. Thus its decision problem is precisely existence of a perfect weakly stable matching, rather than existence of a possibly incomplete matching. [Iwama, Manlove, Miyazaki and Morita, *Stable Marriage with Incomplete Lists and Ties*](https://eprints.gla.ac.uk/1066/1/ICALP99.pdf).
The reduction uses equal-sized sides, mutually acceptable pairs, and exactly the same strict blocking convention. The theorem’s relevant hypotheses are satisfied.
Padding with isolated private pairs preserves the source decision problem. A perfect matching must match each added participant to its designated partner, and no added participant can create a blocking pair involving an original participant.
Choosing \(N\) as the smallest power of two at least \(n\) makes \(1/(2N)\) dyadic. The constructed society has \(2N\) positive masses summing to one.
Each participant has at most \(N\) acceptable partners, so integer values in \(\{1,\ldots,N\}\) suffice to encode all preference groups. Equal values preserve ties, and the specified order of values preserves strict preferences.
The arc gains are assigned to the correct recipients. In the pair pattern \((a,b)\), the balance at \(a\) is \(g(b,a)=u_a(b)\), and the balance at \(b\) is \(g(a,b)=u_b(a)\), since all payments vanish.
Every arc switches sides. Consequently there are no length-\(3\) closed walks, including walks with repeated types. There are no diagonal arcs, so the allowed length-\(2\) patterns correspond exactly to acceptable pairs.
This verifies the claimed restriction of the hard instances to bipartite pair trades.
Assigning mass \(1/(2N)\) to each edge of a perfect matching satisfies every coverage equation.
Each type then has one occupied balance, equal to its matched-partner utility. A blocking cycle is exactly an acceptable pair whose two participants strictly prefer each other to their assigned partners. Weak stability excludes it.
Scaling by \(2N\) gives nonnegative edge weights with every row sum and column sum equal to one.
The displayed Hall calculation is correct: all positive weight incident to a subset \(S\) lies in its support neighborhood, and the total column capacity of that neighborhood is its cardinality. Hence \(|S|\leq |N(S)|\) for every \(S\subseteq U\).
Hall’s theorem applies to this finite bipartite support graph. Since both sides have size \(N\), the resulting matching covers both sides.
The transaction supported on this perfect matching is full and has support contained in the original stable transaction. Lemma 2 therefore applies. Its stability translates back to weak stability under the utility encoding.
This establishes the required equivalence even when the initial transaction uses arbitrary real masses.
The bounds \(\tau=2N\leq4n\) and \(m=2(q+N-n)=O(q+n)\) are correct. Type indices, utilities, and dyadic masses require \(O(\log(n+2))\) bits per relevant entry, giving the stated output-size bound under the usual explicit encoding.
The reduction is polynomial time.
The certificate argument correctly handles real-valued transactions.
The polytope \(P_S\) is nonempty because it contains the assumed transaction. It is bounded because every pattern contains some type, and its positive occurrence coefficient bounds the corresponding coordinate through that type’s coverage equation.
A nonempty bounded polytope has an extreme point. The argument that its positive-support columns must be linearly independent is valid: a dependence supported on strictly positive coordinates permits sufficiently small perturbations in both directions. Therefore the extreme point uses at most \(\tau\) patterns.
Its support is contained in \(S\), so Lemma 2 preserves stability.
The bit-length calculation is correct:
Thus the stated numerator bound and polynomial bit-length bound follow. Negative balances do not affect this reasoning.
The proposed verifier can check pattern legality, rational masses, fullness, occupied minima, and every potential blocking pattern in polynomial bit time. Membership in \(\mathrm{NP}\) is established.
The pattern-enumeration bound is valid. Length-\(2\) patterns can be checked over ordered type pairs. For triples, the number of directed two-arc paths is at most \(\sum_t d^-(t)d^+(t)\leq\tau m\). Closing-arc tests can use a precomputed adjacency table. Canonical rotation preserves the task’s identification of patterns and handles repeated types.
For a fixed type, a balance is determined by its ordered predecessor and successor types. Therefore \(|B_t|\leq\tau^2\). If \(B_t\) is empty, that positive-mass type cannot be covered.
The threshold procedure is correct in both directions:
Rational linear programming has polynomial running time in the size and bit length of these explicitly constructed systems. With at most \(\tau^{2\tau}\) threshold vectors, the claimed bound
\(2^{O(\tau\log(\tau+1))}\operatorname{poly}(m,\tau,L)\)
follows.
The case \(\tau=1\), diagonal arcs, repeated positions, and negative balances introduce no exception to this argument.
No substantive repair or additional clarification is required. The empty display delimiters in two places are harmless formatting artifacts and do not obscure the mathematical statements.
⟨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.