Answer: \(\mathrm{NP}\text{-hard}\)
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn every multi-graph with $n$ additive agents there exists an orientation which is MMS and also PMMS.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite agent types \(A\) with masses \(\lambda_a\), finite item types \(R\) with endpoint sets \(\partial r\subseteq A\), regular high-multiplicity incidence data with the \(\Theta(N)\)-per-agent scaling needed for nondegenerate \(N\)-way MMS, and additive valuations \(v_a\), find masses \(x_{a,B}\) over integral bundle patterns \(B\) satisfying agent-mass and item-density conservation, such that every supported \(B\) has \(v_a(B)\ge\mu_a^\infty\) and every positive-mass pair \(B,D\) satisfies \(v_a(B)\ge\mu_a^2(B\uplus D)\). Here \(\mu_a^\infty\) is the maximin value obtained from distributions over integral bundle patterns with the appropriate normalized per-agent incident supply.
A society is given by its support: the list of \(\tau\) agent types \(A\) with positive binary rational masses \(\lambda_a\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m\) item types \(R\), positive binary rational item densities \(q_r\), and a binary integer population scale \(N\ge2\). Each item type has one or two endpoint types, allowing repeated types; write \(\kappa_{ar}\) for their multiplicity, counting a genuine self-loop once.
Regular incidence data consist of binary rational \(d_{ar}\ge0\), with \(N\lambda_a d_{ar}=\kappa_{ar}q_r\). Promise that these data are realizable by a multigraph having \(N\lambda_a\) agents of type \(a\), \(Nq_r\) items of type \(r\), and exactly \(Nd_{ar}\) incident items of type \(r\) at each type-\(a\) agent; these counts are integers. Thus \(d_{ar}\) is incident supply divided by \(N\).
Values \(w_{ar}\ge0\) are binary rationals, zero outside the endpoint types, and \(v_a(B)=\sum_r w_{ar}B_r\). The implicit set of integral bundle patterns for type \(a\) is \(\mathcal B_a=\{B\in\mathbb Z_{\ge0}^{m}:B_r\le Nd_{ar}\}\), including the empty pattern.
Define \(\mu_a^\infty=\max\{t:\exists(p_B)_{B\in\mathcal B_a},\ p_B\ge0,\ \sum_Bp_B=1,\ \sum_Bp_BB_r=d_{ar}\ \forall r,\ p_B>0\Rightarrow v_a(B)\ge t\}\).
For any integral multiset \(S\), let \(\mu_a^2(S)\) be its standard two-way MMS value, with empty parts allowed; \(B\uplus D\) adds multiplicities and retains distinct item copies.
A mass allocation is a finitely supported family of nonnegative rational \(x_{a,B}\), satisfying \(\sum_Bx_{a,B}=\lambda_a\) and \(\sum_{a,B}x_{a,B}B_r=q_r\). Every supported pattern must satisfy \(v_a(B)\ge\mu_a^\infty\), and every ordered pair with \(x_{a,B}x_{b,D}>0\) must satisfy \(v_a(B)\ge\mu_a^2(B\uplus D)\), including pairs from the same type or pattern.
Is feasibility of such a mass allocation in \(\mathrm P\), with running time polynomial in \(m,\tau,L,\log N\), or is it NP-hard, where \(L\) is the total input bit length?
For finite multigraphs with nonnegative additive valuations, an orientation satisfying both exact MMS and exact PMMS always exists; the constructive result uses exact two-way MMS partitions and states no polynomial running-time bound ([source](https://arxiv.org/html/2506.20317v2)).
No result settling this precise mass-allocation feasibility problem was identified in the literature search.
Feasibility is \(\mathrm{NP}\)-hard, even when \(\tau=1\), \(N=2\), every bundle coordinate has upper bound \(1\), and all item values are positive integers.
We prove this by a polynomial-time many-one reduction from PARTITION.
A PARTITION instance consists of positive binary integers \(s_1,\ldots,s_k\). Write \(S=\sum_{i=1}^k s_i\). The question is whether some subset has sum \(S/2\).
Construct one agent type \(a\), with \(\lambda_a=1\), and set \(N=2\). Introduce the following \(m=k+1\) item types:
| Item type | Endpoints | \(\kappa_{ar}\) | \(q_r\) | \(d_{ar}\) | \(w_{ar}\) |
|---|---|---|---|---|---|
| \(\ell\) | Genuine self-loop at type \(a\) | \(1\) | \(1\) | \(1/2\) | \(S\) |
| \(r_i\), for each \(i\) | Two distinct agents, both of type \(a\) | \(2\) | \(1/2\) | \(1/2\) | \(2s_i\) |
The incidence equations hold: for the loop type, \(N\lambda_a d_{a\ell}=1=\kappa_{a\ell}q_\ell\); for each other type, \(N\lambda_a d_{ar_i}=1=\kappa_{ar_i}q_{r_i}\).
The realizability promise is satisfied explicitly. Take two agents of type \(a\), place one loop of type \(\ell\) at each agent, and place one edge of type \(r_i\) between the agents for each \(i\). There are exactly \(Nq_\ell=2\) loop items and \(Nq_{r_i}=1\) item of each other type. Each agent has exactly \(Nd_{ar}=1\) incident item of every type.
Consequently, \(\mathcal B_a=\{0,1\}^{k+1}\). The construction has polynomial encoding length: summing the input integers to obtain \(S\), and doubling each \(s_i\), increase bit lengths only polynomially.
For any distribution witnessing a feasible threshold \(t\) in the definition of \(\mu_a^\infty\), additivity and the prescribed marginals give
\(\displaystyle t\leq \sum_B p_Bv_a(B)=\sum_r w_{ar}d_{ar}=\frac{S}{2}+\sum_{i=1}^k s_i=\frac{3S}{2}.\)
Thus \(\mu_a^\infty\leq 3S/2\). We will not need to compute its exact value.
Suppose a feasible mass allocation exists. Since there is only one type, write its masses as \(x_B\), with \(\sum_Bx_B=1\).
Loop conservation requires \(\sum_Bx_BB_\ell=q_\ell=1\). Every pattern has \(B_\ell\leq1\), so every supported pattern must have \(B_\ell=1\).
Define the value of the remaining items in a pattern by
\(\displaystyle z(B)=\sum_{i=1}^k2s_iB_{r_i}.\)
Every supported pattern therefore has value \(v_a(B)=S+z(B)\). Conservation of the other item types gives
\(\displaystyle \sum_Bx_Bz(B)=\sum_{i=1}^k2s_iq_{r_i}=S.\)
We claim that every supported pattern has \(z(B)=S\). Otherwise, because their weighted average is \(S\), there must be supported patterns \(B,D\) with \(z(B)<S<z(D)\).
Consider the following two-way partition of \(B\uplus D\):
These are valid parts for standard two-way MMS; its partition parts are not restricted to \(\mathcal B_a\). In particular, the first part may contain both loop copies.
Both part values strictly exceed \(v_a(B)\), because
\(\displaystyle 2S>S+z(B),\qquad z(B)+z(D)>S+z(B).\)
It follows that
\(\displaystyle \mu_a^2(B\uplus D)\geq\min\{2S,z(B)+z(D)\}>v_a(B),\)
contradicting the required PMMS inequality for the ordered pair \(B,D\). This proves the claim.
At least one supported pattern exists. Selecting any such pattern gives
\(\displaystyle \sum_{i:B_{r_i}=1}s_i=\frac{z(B)}2=\frac S2.\)
Hence the original PARTITION instance is a YES-instance.
Conversely, suppose a subset \(I\) satisfies \(\sum_{i\in I}s_i=S/2\).
Let \(B\) contain one loop and exactly the items indexed by \(I\). Let \(D\) contain one loop and exactly the complementary items. Assign mass \(1/2\) to each pattern.
Both patterns belong to \(\mathcal B_a\). Their masses sum to \(1\); the loop consumption is \(1\); and each other item type has consumption \(1/2\). Thus every conservation equality holds.
Both supported patterns have value
\(\displaystyle v_a(B)=v_a(D)=S+2\cdot\frac S2=2S\geq\mu_a^\infty.\)
For any ordered pair \(E,F\) of supported patterns—including repeated patterns—the multiset \(E\uplus F\) has total value \(4S\). Every two-way partition has a part of value at most half its total value. Therefore
\(\displaystyle \mu_a^2(E\uplus F)\leq2S=v_a(E).\)
All PMMS constraints hold, completing the converse.
We have proved that the constructed mass-allocation instance is feasible exactly when the PARTITION instance is a YES-instance. Since PARTITION with positive binary integers is \(\mathrm{NP}\)-complete, this establishes the claimed \(\mathrm{NP}\)-hardness.
This is compatible with the [cited finite multigraph theorem](https://arxiv.org/html/2506.20317v2). Under graphical valuations, another vertex’s self-loop has zero value to the first vertex. In the mass model, the type valuation assigns value \(S\) to both loop copies in \(B\uplus D\). That difference enables the decisive PMMS comparison above.
⟨structured verdict parsed — rendered above⟩
The reduction is correct and resolves the requested feasibility problem as \(\mathrm{NP}\)-hard. No major or minor issues were found.
The construction uses one supported agent type with positive mass \(\lambda_a=1\), population scale \(N=2\), and positive rational densities. All values are positive integers because the PARTITION inputs are positive integers.
The incidence equations are correct:
The explicit realization satisfies every promised count. There are two agents, two loop items in total, and one edge item of each type \(r_i\). Each agent has exactly one incident item of every type. Counting each genuine loop once agrees with the task.
Consequently, every coordinate bound is \(Nd_{ar}=1\), so the asserted pattern space \(\mathcal B_a=\{0,1\}^{k+1}\) is correct.
The output encoding is polynomial in the PARTITION input length. In particular, summation and multiplication by two have polynomial bit complexity, and the construction creates only \(k+1\) item types.
For any distribution witnessing threshold \(t\), every pattern with positive probability has value at least \(t\). Since the probabilities sum to one, the displayed expected-value inequality follows.
Using the prescribed marginals gives exactly
\[ \sum_r w_{ar}d_{ar} =S\cdot\frac12+\sum_i(2s_i)\cdot\frac12 =\frac{3S}{2}. \]
Thus \(\mu_a^\infty\leq 3S/2\) is justified. The proof correctly needs only this upper bound; it does not assume that the bound is attained.
Loop conservation forces every supported pattern to contain its loop: the weighted average of coordinates bounded above by one equals one, with total mass one.
The calculation for the remaining value is also correct:
\[ \sum_Bx_Bz(B) =\sum_i2s_i\sum_Bx_BB_{r_i} =\sum_i2s_i\cdot\frac12 =S. \]
If any supported value \(z(B)\) differs from \(S\), the average equality and positive supported masses force supported patterns on both sides of \(S\). Finite support makes this argument immediate.
For such \(B,D\), the proposed partition of \(B\uplus D\) is valid. The two loop copies remain distinct items, and standard two-way MMS imposes no coordinate bounds on its partition parts. Its part values are \(2S\) and \(z(B)+z(D)\).
Both strict comparisons are correct:
\[ 2S-(S+z(B))=S-z(B)>0, \]
\[ z(B)+z(D)-(S+z(B))=z(D)-S>0. \]
Therefore this partition certifies \(\mu_a^2(B\uplus D)>v_a(B)\), contradicting the required inequality for the ordered pair \(B,D\).
Every supported pattern consequently satisfies \(z(B)=S\). Since total mass is one, a supported pattern exists, and its ordinary-item coordinates identify a subset summing to \(S/2\). This direction also covers odd \(S\): the resulting equality would be impossible for an integer subset sum.
The two proposed patterns belong to the prescribed pattern space. Their rational masses satisfy all conservation constraints:
Both patterns have value \(2S\), which exceeds the proved benchmark bound \(3S/2\).
For every ordered pair of supported patterns, including identical patterns, the union has total value \(4S\). Any two-way partition has minimum part value at most \(2S\). Taking the maximum over partitions preserves this upper bound, proving every required PMMS inequality. Distinct copies in repeated-pattern unions are handled correctly.
The two directions establish a polynomial-time many-one reduction from positive binary-integer PARTITION. The invoked complexity fact is precisely that this version of PARTITION is \(\mathrm{NP}\)-complete. Its binary encoding matches the construction, so the conclusion is \(\mathrm{NP}\)-hardness, without any claim of membership in \(\mathrm{NP}\) or strong hardness.
The finite-theorem comparison is consistent with the source’s graphical valuation restriction: an item can have positive value only for its incident vertices. Thus another vertex’s loop has zero value to the evaluating vertex, whereas the task’s type valuation values both loop copies in the union. [Cited source](https://arxiv.org/html/2506.20317v2)
The finite theorem is explanatory context, not an inference used by the reduction. No theorem application or missing hypothesis blocks the hardness conclusion.
No additional clarification or repair is needed.
⟨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.