Answer: \(\mathrm{NP}\)-hard, even for \(\tau=2\); decidable in \(2^{O(m)}\operatorname{poly}(\tau,L)\) time.
Theorem 2 — class: hardness
Given \(m\) resource kinds, a finite set of utility types \(\mathcal T\) with binary-rational masses \(\mu_t\) summing to \(1\), rational utility functions \(u_t\), per-capita supplies \(q_r\), and feasible initial and target configurations \(x^0,x^1\), decide whether a finite sequence of IR mass O-contracts reaches \(x^1\) from \(x^0\). A configuration \(x_{t,S}\) gives the mass of type \(t\) holding integral bundle \(S\subseteq R\), with \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:r\in S}x_{t,S}=q_r\). Each stage transfers some \(\delta>0\) mass from \((t,S)\) and \((t',S')\) to \((t,S\cup\{r\})\) and \((t',S'\setminus\{r\})\), where \(r\notin S\), \(r\in S'\), and both source cohorts have at least mass \(\delta\); the stage is IR when it strictly increases utilitarian welfare.
Let \(R\) contain \(m\geq1\) resource kinds; each individual holds an integral bundle \(S\subseteq R\), possibly empty.
A society is given by its support: the list of its \(\tau\geq1\) utility types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a monotone utility \(u_t:2^R\to\mathbb Q\), possibly negative, represented by a Boolean circuit taking the bundle's characteristic vector and outputting a signed binary numerator and a positive binary denominator.
Supplies \(q_r\in\mathbb Q\cap(0,1]\) are per capita. A configuration has real coordinates \(x_{t,S}\geq0\) satisfying \(\sum_{S\subseteq R}x_{t,S}=\mu_t\) and \(\sum_{t,S:r\in S}x_{t,S}=q_r\).
The input gives feasible \(x^0,x^1\) as lists of their positive binary-rational coordinates, with omitted coordinates zero, and promises \(W(x^1)>W(x^0)\), where \(W(x)=\sum_{t,S}x_{t,S}u_t(S)\). Let \(L\) be the total binary input length, including circuits and configuration lists.
A mass O-contract chooses \(t,t',S,S',r\) with \(r\notin S\), \(r\in S'\), and a real \(0<\delta\leq\min\{x_{t,S},x_{t',S'}\}\); it subtracts \(\delta\) from both source coordinates and adds \(\delta\) to \((t,S\cup\{r\})\) and \((t',S'\setminus\{r\})\), adding coincident coordinate changes algebraically. The two cohorts may have the same type.
The contract is individually rational (IR) precisely when it strictly increases \(W\); compensatory payments have no budget restriction.
Is deciding whether a finite sequence of IR mass O-contracts reaches \(x^1\) exactly from \(x^0\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m,\tau,L\).
Discrete IR O-contract reachability is NP-hard even for two agents and monotone utilities with succinct circuit representations. [The Complexity of Contract Negotiation](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aij2005b.pdf).
Reachability for explicitly represented continuous Petri nets is polynomial-time decidable. [Logics for Continuous Reachability](https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/bh-17/bh-17.pdf). No result for the exact mass problem specified here was located.
Result
The problem is \(\mathrm{NP}\)-hard, even for \(\tau=2\), equal masses, supplies \(q_r=\tfrac12\), and nonnegative, strictly monotone, integer-valued utilities. Both endpoint configurations can have just two positive coordinates.
There is also a deterministic algorithm with running time
\[
2^{O(m)}\operatorname{poly}(\tau,L).
\]
Thus fixed \(m\) gives polynomial-time decidability, whereas unrestricted \(m\) gives \(\mathrm{NP}\)-hardness.
1. A polynomial-time reduction from satisfiability
Let \(\varphi\) be a Boolean formula on \(n\geq1\) variables. Satisfiability remains \(\mathrm{NP}\)-hard under this restriction: an unused variable can always be added.
Introduce the resource set
\[
R=\{g,a_1,b_1,\ldots,a_n,b_n\},\qquad m=2n+1.
\]
The resources \(a_i,b_i\) represent the two truth values of variable \(i\).
Define \(G(S)\) to hold precisely when:
Every bundle satisfying \(G\) has size \(n+1\).
Define an auxiliary function \(f:2^R\to\mathbb Z_{\geq0}\) by
\[
f(S)=
\begin{cases}
0,& |S|=n+1\text{ and }G(S)\text{ is false},\\
|S|,&\text{otherwise}.
\end{cases}
\]
There are two utility types, \(A\) and \(B\), with masses \(\mu_A=\mu_B=\tfrac12\). Put \(M=n+1\) and define
\[
u_A(S)=M|S|+f(S),\qquad u_B(S)=M|S|.
\]
For every resource, set \(q_r=\tfrac12\). The initial and target configurations are
\[
x^0_{A,\varnothing}=x^0_{B,R}=\tfrac12,\qquad
x^1_{A,R}=x^1_{B,\varnothing}=\tfrac12,
\]
with all other coordinates zero.
These configurations satisfy every type-mass and resource-supply constraint.
2. Monotonicity, encoding, and the welfare promise
We verify strict monotonicity, despite the drop in \(f\).
For \(r\notin S\), let \(k=|S|\). The possible increments of \(f\) are:
Consequently,
\[
u_A(S\cup\{r\})-u_A(S)
=M+f(S\cup\{r\})-f(S)\geq M-n=1.
\]
Also, \(u_B(S\cup\{r\})-u_B(S)=M>0\). Chaining single-resource additions proves strict monotonicity under every proper inclusion.
The utility circuits have polynomial size in the formula encoding length and \(n\): they count the bundle’s resources, check the literal-pair conditions, evaluate \(\varphi\), and perform binary arithmetic. They output denominator \(1\). Their values are at most \((n+2)m\), so their output bit lengths are \(O(\log m)\). The whole reduction takes polynomial time.
Since \(n\geq1\), we have \(m\geq n+2\), and therefore \(f(R)=m\). Thus
\[
W(x^0)=\frac{Mm}{2},\qquad
W(x^1)=\frac{Mm+m}{2},
\]
giving
\[
W(x^1)-W(x^0)=\frac m2>0.
\]
The welfare promise holds regardless of whether \(\varphi\) is satisfiable.
3. Satisfiability implies exact reachability
Suppose \(\varphi\) has a satisfying assignment. Let \(T\) contain its \(n\) selected literal resources, exactly one from each pair.
Order the resources by listing:
Let \(P_j\) be the prefix bundle after the first \(j\) resources. For every \(0\leq j\leq m\),
\[
f(P_j)=j.
\]
Indeed, the only exceptional cardinality is \(n+1\), and \(P_{n+1}=T\cup\{g\}\) satisfies \(G\).
Starting from \(x^0\), transfer each resource in this order from type \(B\) to type \(A\), always using \(\delta=\tfrac12\). Before step \(j\), the two occupied coordinates are
\[
x_{A,P_{j-1}}=x_{B,R\setminus P_{j-1}}=\tfrac12.
\]
Hence the selected resource is absent from the recipient bundle and present in the donor bundle, and the contract is enabled.
The common \(M|S|\) terms cancel between recipient and donor. The welfare increase is therefore
\[
\frac12\bigl(f(P_j)-f(P_{j-1})\bigr)=\frac12>0.
\]
Every contract is IR. After exactly \(m\) contracts, the configuration is \(x^1\).
4. Unsatisfiability prevents even fractional crossing
Suppose \(\varphi\) is unsatisfiable. Then \(G(S)\) is false for every bundle, so
\[
f(S)=|S|\quad\text{for }|S|\leq n,\qquad
f(S)=0\quad\text{for }|S|=n+1.
\]
We prove the invariant:
Every configuration reachable from \(x^0\) by finitely many IR contracts has \(x_{A,S}=0\) whenever \(|S|>n\).
The invariant holds initially. Assume it holds immediately before a contract.
A contract changes bundles only by adding or removing one resource. Therefore, to create a positive type-\(A\) coordinate of size greater than \(n\), its recipient must have type \(A\) and source bundle \(S\) of size exactly \(n\). Removing a resource from a type-\(A\) source cannot violate the invariant.
For such a recipient,
\[
f(S\cup\{r\})-f(S)=-n.
\]
There are two possible donor types.
If the donor has type \(B\), its utility contribution beyond the common linear term is zero. The total welfare change is
\[
\Delta W=-n\delta<0.
\]
If the donor has type \(A\), its positive source coordinate has bundle \(S'\) with \(1\leq|S'|\leq n\), by the induction hypothesis and \(r\in S'\). Hence
\[
f(S'\setminus\{r\})-f(S')=-1,
\]
and the total welfare change is
\[
\Delta W=-(n+1)\delta<0.
\]
In both cases, the contract fails IR. These calculations use the algebraic coordinate changes and remain valid when destinations coincide with other coordinates.
Thus an IR contract cannot violate the invariant. Induction proves it for every finite sequence, with arbitrary positive real transfer amounts.
But \(x^1_{A,R}=\tfrac12\) and \(|R|=2n+1>n\). Therefore \(x^1\) is unreachable when \(\varphi\) is unsatisfiable.
We have established the equivalence
\[
\varphi\text{ is satisfiable}
\quad\Longleftrightarrow\quad
x^1\text{ is reachable from }x^0.
\]
This proves \(\mathrm{NP}\)-hardness for the exact mass problem.
5. Running time via explicit continuous Petri nets
For completeness, the succinct problem admits an exponential-in-\(m\) upper bound.
Create one Petri-net place for each coordinate \((t,S)\). There are
\[
N=\tau2^m
\]
places.
For every admissible tuple \((t,t',S,S',r)\), compute
\[
d=u_t(S\cup\{r\})+u_{t'}(S'\setminus\{r\})-u_t(S)-u_{t'}(S').
\]
Keep a transition precisely when \(d>0\). It consumes one unit from each source place and produces one unit at each destination place, retaining any input/output overlap.
The two source places are distinct because their bundles have different membership of \(r\). Firing this transition by amount \(\delta\) is therefore enabled exactly when
\[
0<\delta\leq\min\{x_{t,S},x_{t',S'}\},
\]
and it has precisely the required coordinate effect. Its welfare increase is \(\delta d>0\). Every transition preserves type masses and resource supplies.
The number of candidate transitions is
\[
E=m\tau^2\,2^{m-1}2^{m-1}
=m\tau^2\,4^{m-1}.
\]
Circuit evaluations and rational sign comparisons take polynomial time in \(L\), so the explicit net can be constructed in \((N+E)\operatorname{poly}(L)\) time.
For explicitly encoded continuous Petri nets with integral incidence data and rational endpoint markings, finite rational reachability is polynomial-time decidable. This follows from Theorems 3.3 and 3.6 of [Blondin and Haase, *Logics for Continuous Reachability in Petri Nets*](https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/bh-17/bh-17.pdf).
Here rational and real finite reachability agree. To verify this, fix the transition sequence of any finite real execution. Its transfer amounts satisfy finitely many rational linear equalities and weak inequalities, together with strict positivity constraints. At the real solution, impose every tight weak inequality as an additional equality. Gaussian elimination gives a rational parametrization of this affine solution space, whose rational points are dense. A sufficiently close rational point preserves all remaining strict inequalities, yielding a rational execution of the same sequence. The reverse implication is immediate.
Applying the explicit-net algorithm therefore gives total running time
\[
\bigl(L+m\tau^2 4^m\bigr)^{O(1)}
=2^{O(m)}\operatorname{poly}(\tau,L).
\]
The polynomial-time result for explicit continuous nets is consequently consistent with the hardness result: the bundle representation here is succinct.
⟨structured verdict parsed — rendered above⟩
Assessment: proved. The reduction establishes \(\mathrm{NP}\)-hardness for the exact continuous mass problem, including the stated restrictions. The upper bound \(2^{O(m)}\operatorname{poly}(\tau,L)\) is also justified. I found no mathematical errors or gaps requiring repair.
The construction uses \(m=2n+1\) resources and exactly two supported utility types, each of mass \(\tfrac12\).
Both endpoint configurations are feasible: each type has its prescribed mass, and each resource occurs in exactly one occupied bundle of mass \(\tfrac12\). Thus every resource has supply \(\tfrac12\).
The restriction \(n\geq1\) is legitimate for satisfiability hardness. It also ensures that the exceptional layer of cardinality \(n+1\) differs from the full bundle, since \(2n+1\geq n+2\).
The predicates and arithmetic defining the utilities have polynomial-size circuits. The stated integer output bound \((n+2)m\) is valid, and denominator \(1\) meets the representation requirements. The endpoint lists contain only two positive coordinates each. Consequently, this is a polynomial-time reduction to the specified input format.
All four cases for the increment of \(f\) are correct:
Therefore the smallest single-resource increment of \(u_A\) is \(M-n=1\). The increment of \(u_B\) is \(M=n+1>0\). The argument by chaining additions establishes strict monotonicity for every proper inclusion. Both utilities are nonnegative and integer-valued.
The endpoint welfare calculations are correct. In particular, \(f(\varnothing)=0\) and \(f(R)=m\), so the welfare difference is \(\tfrac m2>0\). The reduction satisfies the welfare promise on both satisfiable and unsatisfiable inputs.
The selected resource order has exactly one prefix at the exceptional cardinality \(n+1\). That prefix contains \(g\) and the literal resources of a satisfying assignment, so it satisfies \(G\). Hence the assertion \(f(P_j)=j\) holds for every prefix, including both endpoints.
At each step, the two source coordinates have mass \(\tfrac12\), and the transferred resource has the required membership in both source bundles. Thus the proposed transfer amount is enabled.
The common linear utility terms cancel because one resource is added and one removed. The remaining welfare increase is exactly \(\tfrac12\). Every contract is strictly IR, and the sequence ends at the prescribed target after \(m\) contracts.
This proves the forward implication without fractional approximation or a limiting execution.
Under unsatisfiability, every bundle at cardinality \(n+1\) has auxiliary value zero. The proposed invariant holds initially.
The induction step correctly identifies every possible first violation: a positive type-\(A\) coordinate above cardinality \(n\) can only be created by adding a resource to an occupied type-\(A\) bundle of cardinality \(n\). Removal cannot create such a coordinate.
For this recipient, the auxiliary increment is \(-n\).
The linear terms cancel in both cases. These calculations remain valid with coincident coordinates because welfare is linear and coordinate changes are combined algebraically.
Thus no IR contract can break the invariant, regardless of its positive real transfer amount. Finite induction applies to every allowed execution. Since the target assigns positive type-\(A\) mass to \(R\), whose cardinality exceeds \(n\), it is unreachable.
The satisfiability–reachability equivalence and the claimed \(\mathrm{NP}\)-hardness follow.
The place count \(N=\tau2^m\) is correct. For each resource, there are \(2^{m-1}\) possible recipient bundles and \(2^{m-1}\) possible donor bundles, giving the stated candidate count \(E=m\tau^2 4^{m-1}\).
The two source places are distinct because their bundles differ in membership of the transferred resource, even when the types coincide. Retaining input/output overlap correctly preserves the original enabling condition.
For every retained transition, its welfare effect is \(\delta d>0\). Conversely, every allowed IR contract corresponds to a retained transition. Preservation of type masses and supplies ensures that intermediate markings remain feasible configurations.
Circuit evaluation and comparison of the four rational utility values require polynomial time in their input and output bit lengths, which are bounded by the original encoding length. The construction-time bound is therefore justified.
The cited theorem application is valid. Theorem 3.6 gives a logarithmic-space construction of a constraint instance characterizing finite rational executions and their Parikh vectors; Theorem 3.3 gives polynomial-time satisfiability for that constraint class. Together they support the stated polynomial-time decision result for explicitly encoded continuous Petri nets. The constructed net has nonnegative integral input/output matrices and nonnegative rational endpoint markings, satisfying the hypotheses. [Blondin and Haase, Theorems 3.3 and 3.6](https://www.cs.ox.ac.uk/people/christoph.haase/home/publication/bh-17/bh-17.pdf).
The paper restricts individual firing factors to at most \(1\). This causes no mismatch here: every enabled contract amount is at most a source coordinate, hence at most the corresponding type mass, which is at most \(1\).
The supplied rationalization argument is sound. For a fixed finite execution, enabling conditions and the exact endpoint condition form rational linear constraints on transfer amounts. Imposing the weak inequalities tight at the real solution produces a nonempty rational affine space. Its rational points are dense, and sufficiently close points preserve all other inequalities and strict positivity. Thus the same transition sequence admits a rational execution with the exact prescribed endpoint.
The argument concerns finite exact reachability, as required.
Polynomial-time reachability in the expanded net gives the stated bound \(\bigl(L+m\tau^2 4^m\bigr)^{O(1)}=2^{O(m)}\operatorname{poly}(\tau,L)\). Any explicit matrix storage overhead remains polynomial in the expanded dimensions and does not change this bound.
The output resolves the requested classification: unrestricted \(m\) gives \(\mathrm{NP}\)-hardness, while fixed \(m\) gives polynomial-time decidability. It does not claim \(\mathrm{NP}\)-membership or \(\mathrm{NP}\)-completeness.
Actionable feedback: none required.
⟨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.