Answer: NP-hard, even with \(r=\tau=2\), nonnegative integer-valued valuations, and \(K=\tfrac14\).
Theorem 2 (Complexity) — class: hardness
Given a finite-support distribution μ over role-level agent types ρ, bundles \(B\), and payment balances π, a role graph \(H\), per-capita copies of the indivisible goods, encoded valuations, and a rational threshold \(K\), decide whether nonnegative rational masses \(x_d\) of finitely encoded deal templates fit within each source type’s mass and induce a distribution μ' with \(E(μ)-E(μ')\ge K\). Each template involves a clique of roles, conserves its participants’ goods, balances payments, and makes every participant strictly better off; \(E(ν)=∑_{z,z':(ρ(z),ρ(z'))\in E_H}ν_zν_{z'}e(z,z')\), using the paper’s pairwise envy notion.
Let \(H\) be a simple undirected graph on \(r\) roles and let \(m\) be the number of good kinds. A type is \(z=(\rho,B,\pi)\), where \(\rho\) is a role, \(B\subseteq[m]\), and \(\pi\in\mathbb Q\) is cumulative money paid. Each role has a valuation \(v_\rho:2^{[m]}\to\mathbb Q\), with \(v_\rho(\varnothing)=0\); negative values are allowed. Valuations are encoded by Boolean circuits taking bundle indicators and outputting binary signed rational values with nonzero denominators.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here \(\tau\) is the support size, not the number of possible types. Require \(\sum_z\mu_z=1\) and \(\sum_z\mu_z\pi(z)=0\). The per-capita inventory is \(q_g=\sum_{z:g\in B(z)}\mu_z\); copies of each kind are interchangeable, but each individual holds at most one copy of each kind.
A deal template chooses source types \(z_i=(\rho_i,B_i,\pi_i)\) from the initial support, with distinct roles forming a clique, and specifies destination bundles \(B'_i\subseteq[m]\) and rational payments \(p_i\). Require \(\sum_i\mathbf1_{g\in B_i}=\sum_i\mathbf1_{g\in B'_i}\) for every good kind, \(\sum_i p_i=0\), at least one changed bundle, and \(v_{\rho_i}(B'_i)-v_{\rho_i}(B_i)>p_i\) for every participant. Its destination types are \(z'_i=(\rho_i,B'_i,\pi_i+p_i)\); nonparticipants remain unchanged.
Choose any finite collection of such templates and rational masses \(x_d\ge0\), with \(\sum_d x_d>0\) and \(\sum_{d,i:z_i=z}x_d\le\mu_z\) for every source type. Apply them simultaneously, without reusing destination mass: \(\mu'=\mu+\sum_d x_d\sum_i(\delta_{z'_i}-\delta_{z_i})\), where \(\delta_z\) is unit mass at \(z\). Templates and their payments are existentially chosen, not supplied as an input catalogue.
For \(z=(\rho,B,\pi)\) and \(w=(\sigma,C,\eta)\), define \(e(z,w)=\max\{v_\rho(C)-\eta-v_\rho(B)+\pi,0\}\). Set \(E(\nu)=\sum_{z,w:\{\rho(z),\rho(w)\}\in E(H)}\nu_z\nu_w e(z,w)\), counting both directions of every role edge.
Given these data and \(K\in\mathbb Q\), the decision problem asks whether such masses induce \(E(\mu)-E(\mu')\ge K\). Let \(L\) be the total binary input length; state running times in \(m,\tau,r,L\).
Is this continuous envy-reducing deal problem solvable in polynomial time, or is it NP-hard?
The discrete threshold problem is NP-complete for valuation languages for which welfare improvement is NP-complete ([2007 result](https://cdn.aaai.org/AAAI/2007/AAAI07-111.pdf)). A later result establishes NP-completeness of discrete strict envy reduction even for single-minded valuations ([full version](https://eprints.illc.uva.nl/id/eprint/571/1/PP-2016-35.text.pdf)).
No result settling exactly the mass-distribution problem defined above was located.
The problem is NP-hard, even when \(r=\tau=2\), the role graph consists of a single edge, all valuations are nonnegative integer-valued, and \(K=\tfrac14\).
The proof uses a direct reduction from Boolean satisfiability and handles arbitrary finite collections of simultaneous fractional deals.
Let \(\varphi\) be a Boolean formula on variables \(x_1,\ldots,x_n\). Introduce the goods
\(G=\{g_1,\ldots,g_n,h,d\}\),
so \(m=n+2\). For a bundle \(B\), interpret the indicators of \(g_1,\ldots,g_n\) as a Boolean assignment, denoted \(a_B\).
There are two roles, \(A\) and \(B\), joined by an edge. Define their valuations as follows:
The first two rules cannot overlap because the second excludes \(d\). Both valuations satisfy \(v_A(\varnothing)=v_B(\varnothing)=0\).
These valuations have Boolean circuits of polynomial size: evaluate \(\varphi\) on the relevant bundle indicators, test the marker conditions and whether the bundle is \(G\), and output one of the constants \(0,1,4\), with denominator \(1\).
The initial support consists of
\(z_A=(A,\varnothing,0)\), \(\qquad z_B=(B,G,0)\),
each with mass \(\tfrac12\). Set \(K=\tfrac14\).
The masses sum to \(1\), cumulative money sums to \(0\), and every good has per-capita inventory \(\tfrac12\). Thus the instance satisfies all input requirements.
The only ordered pairs counted by the role graph are the two directions between the support types. Their envy values are
\(e(z_A,z_B)=\max\{v_A(G)-v_A(\varnothing),0\}=1\),
\(e(z_B,z_A)=\max\{v_B(\varnothing)-v_B(G),0\}=0\).
Consequently,
\(E(\mu)=\tfrac12\cdot\tfrac12\cdot(1+0)=\tfrac14\).
Since every summand defining \(E\) is nonnegative, meeting the chosen threshold requires \(E(\mu')=0\).
Suppose \(a\) satisfies \(\varphi\). Define
\(S=\{h\}\cup\{g_j:a(x_j)=1\}\), \(\qquad T=G\setminus S\).
The bundle \(S\) contains \(h\) and excludes \(d\), while \(T\) excludes \(h\). Hence
\(v_A(S)=4,\quad v_A(T)=0,\quad v_B(S)=v_B(T)=0\).
Here \(S\) and \(T\) are both proper subsets of \(G\): \(h\in S\) and \(d\in T\).
Choose the two-participant template
\(B'_A=S,\quad B'_B=T,\quad p_A=\tfrac32,\quad p_B=-\tfrac32\).
The roles form a clique. The destination bundles partition \(G\), so every good is conserved. Payments sum to zero, and both bundles change. Strict individual improvement holds because
\(v_A(S)-v_A(\varnothing)=4>\tfrac32=p_A\),
\(v_B(T)-v_B(G)=-1>-\tfrac32=p_B\).
Apply this single template with mass \(\tfrac12\). This uses exactly the available mass of each source. The final society has mass \(\tfrac12\) at each of
\(z'_A=(A,S,\tfrac32)\), \(\qquad z'_B=(B,T,-\tfrac32)\).
Its two directed envy values are
\(e(z'_A,z'_B)=\max\{0+\tfrac32-4+\tfrac32,0\}=0\),
\(e(z'_B,z'_A)=\max\{0-\tfrac32-0-\tfrac32,0\}=0\).
Therefore \(E(\mu')=0\), and the reduction equals \(K=\tfrac14\). All payments and masses are rational.
Suppose \(\varphi\) is unsatisfiable. Then both roles have the same valuation:
\(v_A(U)=v_B(U)=1\) when \(U=G\), and \(0\) otherwise.
A singleton template is impossible. Goods conservation forces its destination bundle to equal its source bundle, and payment balance forces its payment to be \(0\); its strict improvement inequality would therefore be \(0>0\).
Every possible template must consequently involve both roles. Because each role has exactly one initial support type, its sources must be \(z_A,z_B\).
Let its destination bundles be \(S,T\). Initially, the two participants jointly hold exactly one copy of every good. Conservation therefore implies that \(S,T\) partition \(G\).
For every such partition,
\(v_A(S)+v_B(T)\le 1\).
Indeed, if either bundle equals \(G\), the other is empty and the total value is \(1\). Otherwise neither bundle equals \(G\), and the total value is \(0\).
On the other hand, summing the two required strict improvement inequalities gives
\(v_A(S)+v_B(T)-v_A(\varnothing)-v_B(G)>p_A+p_B=0\).
Since the initial total valuation is \(1\), this requires
\(v_A(S)+v_B(T)>1\),
a contradiction.
Thus an unsatisfiable instance has no admissible template at all. In particular, arbitrary mixtures, fractional masses, and existentially chosen rational payments cannot produce a feasible collection with positive total mass.
The construction proves the equivalence
\(\varphi\text{ is satisfiable}\ \Longleftrightarrow\ \text{the constructed continuous instance is a yes-instance}\).
If the formula encoding has length \(s\), the reduction takes \(\operatorname{poly}(s+n)\) time and produces \(m=n+2\), \(\tau=r=2\), and \(L=\operatorname{poly}(s+n)\).
Consequently, an algorithm running in \(\operatorname{poly}(m,\tau,r,L)\) time would decide Boolean satisfiability in polynomial time. The continuous problem is therefore NP-hard, and has no polynomial-time algorithm unless \(\mathrm P=\mathrm{NP}\).
This settles the requested hardness question. It does not assert membership of the general problem in \(\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction is correct and resolves the requested NP-hardness question. No major or minor mathematical issues were found. It establishes hardness even with \(r=\tau=2\), nonnegative integer-valued circuit valuations, and fixed threshold \(K=\tfrac14\). It does not establish membership in \(\mathrm{NP}\), and explicitly avoids claiming that.
The valuation definitions are exhaustive and consistent. The exceptional rule \(v_A(G)=1\) cannot overlap with the rule assigning value \(4\), since the latter excludes \(d\), whereas \(G\) contains \(d\). Every remaining bundle receives value \(0\).
Both empty-bundle valuations are \(0\), since \(\varnothing\ne G\) and \(\varnothing\) does not contain \(h\). All outputs are nonnegative integers, representable as signed rationals with denominator \(1\).
The circuit construction is polynomial in the formula size and number of variables: it evaluates the supplied formula, checks the marker indicators, tests equality with \(G\), and selects a constant output. This conforms to the required circuit representation.
The two support types are distinct and have positive rational masses. Their masses sum to \(1\), their cumulative payments sum to \(0\), and each good appears only in the second source bundle, giving inventory \(\tfrac12\). The role graph is simple and consists of the required single edge.
Assessment: All input requirements are satisfied.
There are exactly two ordered support pairs whose roles are adjacent. The stated calculations are correct:
\[ e(z_A,z_B)=1,\qquad e(z_B,z_A)=0. \]
Each pair has mass product \(\tfrac14\), so \(E(\mu)=\tfrac14\).
Every term in \(E(\mu')\) is nonnegative. Therefore the threshold condition with \(K=\tfrac14\) holds exactly when \(E(\mu')=0\).
Assessment: The initial envy and threshold interpretation are correct.
For a satisfying assignment, the defined bundles \(S\) and \(T\) partition \(G\). The markers ensure that \(S\) contains \(h\) and excludes \(d\), while \(T\) contains \(d\) and excludes \(h\). Consequently, both bundles are proper subsets of \(G\), and the four claimed destination valuations are correct.
The two roles form a clique. Partitioning \(G\) preserves the count of every good, and the payments sum to \(0\). Both participants change bundles.
The strict improvement inequalities are correctly checked:
\[ 4>\tfrac32,\qquad -1>-\tfrac32. \]
The second participant loses valuation but receives sufficient money, as permitted by the task.
Applying mass \(\tfrac12\) consumes exactly the available mass of each source type. The collection has positive total mass and obeys every source-capacity constraint.
Assessment: The proposed template and its application are admissible.
The final cumulative payments are correctly obtained by adding each payment to its source payment \(0\).
For the direction from role \(A\) to role \(B\), the expression inside the maximum is
\[ v_A(T)-(-\tfrac32)-v_A(S)+\tfrac32 =0+\tfrac32-4+\tfrac32=-1. \]
For the reverse direction, it is
\[ v_B(S)-\tfrac32-v_B(T)-\tfrac32 =0-\tfrac32-0-\tfrac32=-3. \]
Both envy values therefore vanish. These are the only adjacent-role pairs in the final support, so \(E(\mu')=0\), giving reduction exactly \(K=\tfrac14\).
Assessment: The constructed instance is a yes-instance whenever the formula is satisfiable.
If the formula is unsatisfiable, neither valuation ever takes value \(4\). Both roles consequently value only the full bundle \(G\), at value \(1\).
A singleton template cannot satisfy strict improvement: conservation fixes its bundle, and payment balance fixes its payment at \(0\). An empty template also cannot satisfy the required changed-bundle condition.
Since there are only two roles and template roles must be distinct, every remaining candidate template has exactly two participants. Each role has only one source type in the initial support, so the sources must be \(z_A,z_B\).
Good conservation forces the destination bundles to partition \(G\): each good initially has count \(1\), and destination bundles have binary membership indicators. For any such partition, total destination valuation is at most \(1\), exactly as argued.
Summing the strict improvement inequalities is legitimate and gives
\[ v_A(S)+v_B(T)-1>p_A+p_B=0. \]
This contradicts the upper bound of \(1\) on destination welfare.
Assessment: There is no admissible template in the unsatisfiable case. This rules out every permitted finite collection, regardless of fractional masses or rational payments. The proof fully addresses the simultaneous-deal semantics.
The construction gives a polynomial-time many-one reduction from Boolean satisfiability, with
\[ m=n+2,\qquad \tau=r=2,\qquad L=\operatorname{poly}(s+n). \]
Thus an algorithm polynomial in \(m,\tau,r,L\) would yield a polynomial-time algorithm for satisfiability. The NP-hardness conclusion follows.
No bound on certificate size or membership in \(\mathrm{NP}\) is needed for this conclusion. The cited discrete results are not used as premises.
Required clarification or repair: None.
⟨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.