Answer: polynomial-time solvable
Theorem 9 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIf G is a forest and k ∈N, there always exists a k-partition that is MMS and EFX, even if the utility functions are monotone. Moreover, if the utilities are additive, we can find such a partition in linear time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite forest templates \(F_q=(V_q,E_q)\), rational component masses \(\lambda_q\), an integer \(k\), and monotone or additive local utilities \(u_{q,v}\), let \(Z=\sum_q \lambda_q|V_q|\). Decide whether there are nonnegative masses \(y_{q,\chi}\) over \(k\)-colourings \(\chi\) of each template such that \(\sum_\chi y_{q,\chi}=\lambda_q\), every group has mass \(Z/k\), and every positive-mass colouring satisfies the limiting EFX inequalities \(u_{q,v}(\chi^{-1}(\chi(v))) \ge u_{q,v}(\chi^{-1}(j) \setminus \{c\})\) for every local agent \(v\), group \(j\), and friend \(c\) in \(\chi^{-1}(j)\).
An instance has a finite type set \(T\), masses \(\mu_u\in\mathbb{Q}_{\ge 0}\), a symmetric kernel \(w:T\times T\to\mathbb{Q}_{\ge 0}\), an integer \(k\), a focal type \(t\) with \(\mu_t>0\), and \(\sigma\in\mathbb{Q}\).
A balanced mass assignment is \(x_{ug}\ge0\) satisfying \(\sum_{g\in[k]}x_{ug}=\mu_u\) and \(\sum_{u\in T}x_{ug}=1/k\). Type \(t\)'s utility from group \(g\) is \(U_t(g)=\sum_{u\in T}w_{tu}x_{ug}\).
Is deciding whether a balanced mass assignment with \(\min_{g\in[k]}U_t(g)\ge\sigma\) exists solvable in polynomial time, or is it NP-hard?
For indivisible agents, deciding whether one agent's MMS-share is at least a threshold is NP-complete, even for \(k=2\) and symmetric utilities.
That result concerns balanced partitions of individual agents, rather than the mass assignments defined above.
Assume \(k\ge 1\). Define
\[ M:=\sum_{u\in T}\mu_u \qquad\text{and}\qquad W:=\sum_{u\in T}w_{tu}\mu_u. \]
A balanced mass assignment satisfying \(\min_{g\in[k]}U_t(g)\ge \sigma\) exists if and only if
\[ M=1 \qquad\text{and}\qquad \frac{W}{k}\ge \sigma. \]
Consequently, the decision problem is polynomial-time solvable.
Suppose \(x\) is a balanced mass assignment. Summing the type constraints over \(u\in T\) gives
\[ \sum_{u\in T}\sum_{g\in[k]}x_{ug} = \sum_{u\in T}\mu_u = M. \]
Summing the group-balance constraints over \(g\in[k]\) gives
\[ \sum_{g\in[k]}\sum_{u\in T}x_{ug} = \sum_{g\in[k]}\frac1k = 1. \]
The two left-hand sides are equal, so necessarily \(M=1\).
For every balanced mass assignment,
\[ \begin{aligned} \sum_{g\in[k]}U_t(g) &= \sum_{g\in[k]}\sum_{u\in T}w_{tu}x_{ug} \\ &= \sum_{u\in T}w_{tu}\sum_{g\in[k]}x_{ug} \\ &= \sum_{u\in T}w_{tu}\mu_u \\ &=W. \end{aligned} \]
The minimum of \(k\) numbers cannot exceed their arithmetic mean. Hence
\[ \min_{g\in[k]}U_t(g) \le \frac1k\sum_{g\in[k]}U_t(g) = \frac{W}{k}. \]
Therefore, if \(\min_g U_t(g)\ge\sigma\), then necessarily \(W/k\ge\sigma\).
Now suppose \(M=1\). For every \(u\in T\) and \(g\in[k]\), set
\[ x_{ug}:=\frac{\mu_u}{k}. \]
These values are nonnegative. For each type \(u\),
\[ \sum_{g\in[k]}x_{ug} = k\frac{\mu_u}{k} = \mu_u. \]
For each group \(g\),
\[ \sum_{u\in T}x_{ug} = \frac1k\sum_{u\in T}\mu_u = \frac{M}{k} = \frac1k. \]
Thus \(x\) is balanced. Moreover, every group gives the focal type exactly the same utility:
\[ U_t(g) = \sum_{u\in T}w_{tu}\frac{\mu_u}{k} = \frac{W}{k}. \]
Consequently, if \(W/k\ge\sigma\), this assignment satisfies
\[ \min_{g\in[k]}U_t(g)=\frac{W}{k}\ge\sigma. \]
This proves the stated equivalence.
The algorithm computes the two rational quantities \(M\) and \(W\), then tests
\[ M=1 \qquad\text{and}\qquad W\ge k\sigma. \]
Exact addition, multiplication, and comparison of binary-encoded rational numbers take polynomial time in the total input length. This remains true even if \(k\) is binary encoded: the algorithm does not enumerate the \(k\) groups.
The symmetry of \(w\) and the condition \(\mu_t>0\) are not needed for the characterization. Divisibility is decisive: uniformly splitting every type among all groups simultaneously attains the averaging upper bound.
Thus the problem belongs to \(\mathrm P\). In particular, it cannot be NP-hard under polynomial-time many-one reductions unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly characterizes feasibility for every positive integer \(k\). The averaging upper bound is valid, and the uniformly divided assignment \(x_{ug}=\mu_u/k\) attains it while satisfying all balance constraints exactly when total mass is \(1\).
The only issue is a minor domain clarification: the original instance description calls \(k\) an integer without explicitly stating \(k\ge 1\), while the prover assumes this. Since both \([k]\) and \(1/k\) presuppose a positive group count, this is almost certainly intended, but it should be stated explicitly.
Summing the type constraints yields total assigned mass \(M\). Summing the group constraints yields total assigned mass \(k(1/k)=1\). These are the same finite double sum, so \(M=1\) is necessary. This is correct.
The calculation
\[
\sum_{g\in[k]}U_t(g)
=
\sum_{u\in T}w_{tu}\mu_u
=
W
\]
follows directly by exchanging finite sums and applying \(\sum_g x_{ug}=\mu_u\). This is correct.
For \(k\ge 1\), the minimum of the \(k\) group utilities is at most their average. Hence
\[
\min_g U_t(g)\le W/k.
\]
Therefore \(W/k\ge\sigma\) is necessary. This remains valid when \(\sigma\) is negative.
Under \(M=1\), setting \(x_{ug}=\mu_u/k\) gives nonnegative rational values, satisfies every type constraint, and gives each group total mass \(M/k=1/k\). Thus it is balanced.
Each group obtains utility
\[
U_t(g)=\sum_u w_{tu}\mu_u/k=W/k.
\]
Therefore the threshold is met exactly when \(W/k\ge\sigma\). This proves sufficiency and matches the necessary conditions.
Computing \(M\) and \(W\) requires polynomially many exact rational additions and multiplications. The bit lengths of intermediate numerators and denominators remain polynomial in the total binary input length. Comparing \(W\) with \(k\sigma\) is polynomial-time even when \(k\) is binary encoded. Since only the decision answer is required, the algorithm need not explicitly output \(k\) group columns. The complexity conclusion is correct.
The observation that symmetry of \(w\) and positivity of \(\mu_t\) are unnecessary for this characterization is correct.
State explicitly that valid instances require \(k\in\mathbb{Z}_{\ge 1}\), or explain that this is implicit in the notation \([k]\) and the constraint \(1/k\). No mathematical repair beyond this domain clarification 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.