Answer: Deciding existence is \(\mathrm{NP}\)-hard already for \(q=3\), with equal dyadic masses and quadratic \(V\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor partitioning the pairwise similarity graph on a set N of agents (n = |N|) into two groups of agents C1, C2 with min-cut flow ζ, meaning that: X i∈C1,j∈C2 M2({i}, {j}) = ζ, then we have: |Sh(N, i) − 2 X k=1 Shvk(Ck, i)| ≤2ζ, where v1(S) = v(S ∩C1) and v2(S) = v(S ∩C2) for all S ⊆N with corresponding complexity: O(2max(|C1|,|C2|) + n3). To further reduce the running time of computing Shapley we can proceed by recursively sub-dividing the partitions, and accumulate the error from the partitioning.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of contributor types \(T\), rational masses \(\mu_t\), a differentiable aggregate value function \(V(x)\) on \(0\leq x_t\leq\mu_t\), cross-type curvature bounds \(\kappa_{tu}\), a maximum issue size \(q\), and tolerance \(\varepsilon\), determine whether \(T\) has a partition \(\mathcal C\) into issues of size at most \(q\) with \(F(\mathcal C)=\sum_{t<u:\,C(t)\ne C(u)}\mu_t\mu_u\kappa_{tu}\leq\varepsilon\). Return such a partition and the issue-based type allocations \(\widehat a_t=\mu_t\int_0^1\partial_tV(s\mu^{C(t)})\,ds\), with the stated aggregate allocation-error certificate.
A society is given by its support: a list \(T\) of \(\tau\geq1\) contributor types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The real-valued function \(V\), normalized by \(V(0)=0\), is represented by a rational arithmetic circuit with \(m\) gates, defined and twice continuously differentiable on a neighborhood of \(B=\prod_t[0,\mu_t]\). All function assumptions below are promises.
Assume \(V\geq0\) on \(B\), and, for nonnegative vectors \(x,y,z\) with pairwise disjoint supports and \(x+y+z\in B\), assume \(V(x+y)\leq V(x)+V(y)\) and \(V(x+y+z)\geq V(x+y)+V(x+z)+V(y+z)-V(x)-V(y)-V(z)\).
Input also includes symmetric binary-rational bounds \(\kappa_{tu}\geq0\), promised to satisfy \(|\partial_t\partial_uV(x)|\leq\kappa_{tu}\) throughout \(B\) for distinct types, an integer \(1\leq q\leq\tau\), and binary-rational \(\varepsilon\geq0\). Let \(L\) be the total input bit length.
An issue partition \(\mathcal C\) consists of nonempty, disjoint subsets covering \(T\), each containing at most \(q\) types; a type's mass cannot be split. Write \(C(t)\) for its issue and \(\mu^C_u=\mu_u\) for \(u\in C\), and \(0\) otherwise. Define \(F(\mathcal C)=\sum_{t<u:\,C(t)\ne C(u)}\mu_t\mu_u\kappa_{tu}\), counting each unordered pair once.
The approximation problem asks whether such a partition has \(F(\mathcal C)\leq\varepsilon\), and, when one exists, asks for its issue allocations \(\widehat a_t=\mu_t\int_0^1\partial_tV(s\mu^{C(t)})\,ds\), with aggregate certificate \(\sum_t|a_t-\widehat a_t|\leq2F(\mathcal C)\leq2\varepsilon\), where \(a_t=\mu_t\int_0^1\partial_tV(s\mu)\,ds\). Allocations are exact definite-integral expressions, so numerical integration precision is not an additional input.
Is this tolerance-constrained issue approximation problem solvable in polynomial time in \(m,\tau,q,L\), or is deciding the existence of a qualifying partition NP-hard?
For finite strongly subadditive games, a two-group decomposition with pairwise cut weight \(\zeta\) gives per-agent Shapley error at most \(2\zeta\), with stated running time \(O(2^{\max(|C_1|,|C_2|)}+n^3)\); this does not establish feasibility under a prescribed issue-size bound. [Soufiani et al.](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p1209.pdf)
The continuous diagonal allocation is the Aumann–Shapley attribution; its attribution theory does not settle this bounded-issue approximation problem, for which no exact matching complexity result was located. [Sun and Sundararajan](https://arxiv.org/html/1102.0989)
Deciding whether a qualifying partition exists is \(\mathrm{NP}\)-hard already for \(q=3\). This holds with equal dyadic masses, a quadratic polynomial \(V\), and exact mixed-derivative bounds. Thus a polynomial-time algorithm in \(m,\tau,q,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
On promised inputs, feasibility also has a polynomial-time verifier. Moreover, every partition satisfies the stronger allocation certificate
\(\displaystyle \sum_t|a_t-\widehat a_t|\leq F(\mathcal C).\)
The cases \(q=1\) and \(q=\tau\) are immediate: the former forces singleton issues; the latter permits one issue with zero cut weight. The hardness concerns the prescribed intermediate size bound.
Fix any issue partition \(\mathcal C\). For a type \(t\), put \(C=C(t)\). For \(s,r\in[0,1]\), define
\(\displaystyle z_s(r)=s\mu^C+rs(\mu-\mu^C).\)
Every coordinate of this vector lies between zero and its corresponding mass, so \(z_s(r)\in B\). Its endpoints are \(s\mu^C\) and \(s\mu\).
Because \(V\) is twice continuously differentiable on a neighborhood of \(B\), the chain rule and the fundamental theorem of calculus give
\(\displaystyle \partial_tV(s\mu)-\partial_tV(s\mu^C) =\int_0^1s\sum_{u\notin C}\mu_u\,\partial_u\partial_tV(z_s(r))\,dr. \)
Here \(u\notin C\) implies \(u\ne t\), so the promised mixed-derivative bounds apply. Consequently,
\(\displaystyle |\partial_tV(s\mu)-\partial_tV(s\mu^C)| \leq s\sum_{u\notin C}\mu_u\kappa_{tu}. \)
Integrating and multiplying by \(\mu_t\) yields
\(\displaystyle |a_t-\widehat a_t| \leq \frac{\mu_t}{2}\sum_{u\notin C(t)}\mu_u\kappa_{tu}. \)
Upon summing over \(t\), every unordered pair separated by the partition appears twice. Symmetry of \(\kappa\) therefore gives
\(\displaystyle \sum_t|a_t-\widehat a_t| \leq \frac12\sum_t\sum_{u\notin C(t)}\mu_t\mu_u\kappa_{tu} =F(\mathcal C). \)
Thus a qualifying partition automatically satisfies the requested certificate, since
\(\displaystyle \sum_t|a_t-\widehat a_t| \leq F(\mathcal C)\leq\varepsilon\leq2\varepsilon. \)
This argument uses only smoothness and the derivative bounds.
We use Partition Into Triangles: given a simple graph \(G=(U,E)\), decide whether its vertices can be partitioned into triples, each inducing a triangle. This problem is \(\mathrm{NP}\)-complete even for graphs of maximum degree four, by Theorem 10 of [van Rooij, van Kooten Niekerk, and Bodlaender](https://link.springer.com/article/10.1007/s00224-012-9412-5).
Take a nonempty such graph. Write \(n=|U|\) and \(M=|E|\).
If \(3\nmid n\) or \(M<n\), a triangle partition is impossible: a triangle partition has \(n/3\) triangles containing altogether \(n\) distinct edges. These cases are mapped to a fixed promised no-instance described below. Otherwise, \(n\geq3\) and \(M\geq n\).
Let \(D\) be the least power of two satisfying \(D\geq n\). Construct the society as follows:
\(\displaystyle V(x)=A\sum_{t\in T}x_t-D^2\sum_{\{u,v\}\in E}x_ux_v.\)
All masses are positive dyadic rationals and sum to one. All bounds are nonnegative integers, symmetric in their indices, and \(\varepsilon\geq0\).
The constructed \(V\) is a polynomial, hence is defined and twice continuously differentiable everywhere. Also \(V(0)=0\).
For every type \(t\),
\(\displaystyle \partial_tV(x)=A-D^2\sum_{u:\{t,u\}\in E}x_u. \)
The graph has maximum degree four, and every coordinate in \(B\) is at most \(1/D\). Therefore
\(\displaystyle \partial_tV(x)\geq A-D^2\frac4D=1. \)
The same bound holds for additional types, whose neighbor sums are empty. For \(x\in B\), the segment from zero to \(x\) lies in \(B\), and hence
\(\displaystyle V(x)=\int_0^1\sum_t x_t\partial_tV(sx)\,ds \geq\sum_t x_t\geq0. \)
For distinct types,
\(\displaystyle \partial_t\partial_uV(x) =-D^2\mathbf1_{\{\{t,u\}\in E\}} =-\kappa_{tu}. \)
Thus every supplied mixed-derivative bound is exact.
To check the remaining inequalities, define
\(\displaystyle \beta(x,y)=D^2\sum_{\{u,v\}\in E}(x_uy_v+x_vy_u). \)
Expansion of the quadratic polynomial gives
\(\displaystyle V(x+y)=V(x)+V(y)-\beta(x,y). \)
For nonnegative vectors, \(\beta(x,y)\geq0\), proving the required subadditivity.
A second expansion gives
\(\displaystyle V(x+y+z) =V(x)+V(y)+V(z)-\beta(x,y)-\beta(x,z)-\beta(y,z). \)
Using the two-vector identity, the right-hand side is exactly
\(\displaystyle V(x+y)+V(x+z)+V(y+z)-V(x)-V(y)-V(z). \)
The required three-vector inequality therefore holds with equality. These identities hold in particular for every disjoint-support triple specified in the promises.
For completeness, the fixed no-instance uses four types of mass \(1/4\), \(q=3\), \(\varepsilon=0\), and the construction above with the complete graph on four vertices: \(D=4\), \(A=17\), and \(\kappa_{tu}=16\) for every distinct pair. The preceding promise checks apply. Every admissible partition separates some pair because no issue can contain all four types; that pair contributes one to \(F\). Thus this is a promised no-instance.
For each graph edge, its cut weight is
\(\displaystyle \mu_u\mu_v\kappa_{uv} =\frac1D\frac1D D^2=1. \)
Every other pair has weight zero. Therefore \(F(\mathcal C)\) equals the number of graph edges whose endpoints belong to different issues.
Let
\(\displaystyle I(\mathcal C)=\sum_{C\in\mathcal C}|E(G[C\cap U])| \)
be the number of graph edges internal to issues. Every edge is either internal or cut, so
\(\displaystyle F(\mathcal C)=M-I(\mathcal C).\)
Consider an issue \(C\), and put \(k=|C\cap U|\). Since \(|C|\leq3\), we have \(k\in\{0,1,2,3\}\), and
\(\displaystyle |E(G[C\cap U])|\leq\binom{k}{2}\leq k. \)
Equality between the edge count and \(k\) holds precisely when either \(k=0\), or \(k=3\) and the three vertices form a triangle. Indeed, for \(k=1\) and \(k=2\), the maximum edge counts are respectively zero and one, strictly below \(k\).
Because the issues partition all graph vertices,
\(\displaystyle I(\mathcal C)\leq\sum_{C\in\mathcal C}|C\cap U|=n.\)
Now suppose \(\mathcal C\) qualifies. Then
\(\displaystyle M-I(\mathcal C)=F(\mathcal C)\leq\varepsilon=M-n, \)
so \(I(\mathcal C)\geq n\). Combining the two bounds gives \(I(\mathcal C)=n\). Each issue’s nonnegative deficit
\(\displaystyle |C\cap U|-|E(G[C\cap U])|\)
must consequently vanish. Thus every issue containing graph vertices contains exactly three of them, forming a triangle. Such an issue cannot contain an additional type because its size is already three. These issues give a triangle partition of \(G\).
Conversely, if \(G\) has a triangle partition, take those triangles as issues and place every additional type in a singleton issue. Exactly \(n\) graph edges are internal, so
\(\displaystyle F(\mathcal C)=M-n=\varepsilon.\)
We have proved the equivalence
\(\displaystyle G\text{ has a triangle partition} \quad\Longleftrightarrow\quad \text{the constructed society has a qualifying partition}. \)
Since \(D<2n\), the support has size \(\tau=O(n)\). Maximum degree four implies \(M\leq2n\), so the polynomial \(V\) has an arithmetic circuit with \(m=O(n)\) gates.
The constants \(D,D^2,A\), the masses, and the tolerance have \(O(\log n)\) bits each. Even listing the entire matrix of bounds takes only \(O(n^2\log n)\) bits. The reduction is therefore polynomial-time and produces only promised inputs.
On promised inputs, a feasibility witness assigns each type an issue label. It requires \(O(\tau\log\tau)\) bits. A verifier counts issue sizes and computes \(F(\mathcal C)\) exactly using polynomially many rational operations of polynomial bit length. No evaluation of \(V\), integration, or verification of the analytic promises is needed.
Thus the combinatorial feasibility predicate is \(\mathrm{NP}\)-complete, with hardness witnessed entirely within the promised class.
Given a partition, its requested integral expressions can be produced in polynomial time: differentiate the arithmetic circuit, substitute \(s\mu^{C(t)}\), and retain the definite-integral notation. Circuit sharing keeps the expression representation polynomial in size.
In the reduction, even integration is elementary. Let \(d_G(t)\) be the number of graph neighbors of \(t\), and let \(d_C(t)\) count those neighbors in the same issue. Both are zero for additional types. Direct integration gives
\(\displaystyle a_t=\frac AD-\frac{d_G(t)}2, \qquad \widehat a_t=\frac AD-\frac{d_C(t)}2. \)
Consequently,
\(\displaystyle \sum_t|a_t-\widehat a_t| =\frac12\sum_t(d_G(t)-d_C(t)) =F(\mathcal C), \)
because every cut edge contributes at both endpoints. The stronger certificate from Section 1 is therefore sharp.
The existence question is already \(\mathrm{NP}\)-hard under these elementary allocation formulas. Hence the requested approximation problem has no polynomial-time algorithm in the stated parameters unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly. The reduction proves \(\mathrm{NP}\)-hardness already for \(q=3\), satisfies every analytic promise, and establishes the stronger aggregate allocation bound \(\sum_t|a_t-\widehat a_t|\leq F(\mathcal C)\). I found no mathematical error or gap requiring repair.
The path \(z_s(r)=s\mu^C+rs(\mu-\mu^C)\) stays in \(B\) for every \(s,r\in[0,1]\). Its endpoints are correctly identified.
The assumed continuous second derivatives justify applying the chain rule and the fundamental theorem of calculus to \(\partial_tV(z_s(r))\). Only coordinates outside \(C(t)\) vary along this path, so every derivative being bounded is a mixed derivative with distinct indices. The promised bounds therefore apply.
Integrating the resulting inequality over \(s\) gives the stated factor \(1/2\). Summation over types counts every separated unordered pair twice; symmetry of \(\kappa\) then yields precisely \(F(\mathcal C)\).
This verifies the stronger certificate for every admissible partition, including zero tolerance and zero cut weight. It also implies the requested bound \(\sum_t|a_t-\widehat a_t|\leq2F(\mathcal C)\leq2\varepsilon\) whenever the partition qualifies.
The cited theorem is accurate. Theorem 10 states that Partition Into Triangles on graphs of maximum degree four is \(\mathrm{NP}\)-complete, and the paper defines the problem using a partition into three-element sets forming triangles. These are exactly the source problem and hypotheses used in the reduction. [Original article](https://link.springer.com/article/10.1007/s00224-012-9412-5)
Both preprocessing tests are valid:
Restricting attention to nonempty source graphs does not affect hardness. After preprocessing, \(n\geq3\), so the constructed choice \(q=3\) satisfies \(q\leq\tau\).
The padding to a power of two ensures that all masses \(1/D\) are positive dyadic rationals and that their sum is one. The additional types have no incident edges, as required by subsequent calculations.
Every function promise is verified correctly:
The expansions hold even without disjoint supports, so they certainly cover all triples specified by the task.
The fixed no-instance also satisfies the promises. Its complete graph has degree three, within the bound used above. With four types and issue size at most three, some pair must be separated, giving positive cut weight and violating its zero tolerance.
The edge-weight calculation is correct: every graph edge has weight one, and all other pairs have weight zero. Consequently, \(F(\mathcal C)=M-I(\mathcal C)\).
For an issue containing \(k\) original graph vertices, the possibilities are \(k\in\{0,1,2,3\}\). The bound \(|E(G[C\cap U])|\leq\binom{k}{2}\leq k\) and its stated equality conditions are correct in all four cases.
Summing gives \(I(\mathcal C)\leq n\). A qualifying partition forces \(I(\mathcal C)\geq n\), hence equality. Since every issue’s deficit is nonnegative, equality of the total forces every deficit to vanish. Therefore every issue containing original vertices consists of three original vertices forming a triangle. The issue-size bound excludes additional types from those issues.
Conversely, a triangle partition, together with singleton issues for additional types, has exactly \(n\) internal graph edges and therefore cut weight \(M-n=\varepsilon\).
Both directions are established, and the preprocessing branches map to valid no-instances.
The size bounds are correct. For the main construction, \(D<2n\), and maximum degree four gives \(M\leq2n\). The polynomial therefore admits an arithmetic circuit with \(O(n)\) gates. All listed constants have \(O(\log n)\) bits, and explicitly listing the bounds remains polynomial in size.
The feasibility verifier is also valid: issue labels have polynomial length, issue sizes can be checked directly, and the rational cut sum can be computed and compared exactly with polynomial bit complexity.
The statement about \(\mathrm{NP}\)-completeness is appropriately scoped to the combinatorial feasibility predicate. The verifier does not establish that analytic promise validity is efficiently decidable, and the output does not claim that it does.
Thus the reduction establishes the hardness requested for promised inputs.
Producing derivative circuits, substituting the prescribed path, and retaining definite-integral notation is compatible with the task’s exact-expression output convention. Circuit sharing prevents expression expansion from causing exponential output size.
For the constructed quadratic function, the stated formulas for \(a_t\) and \(\widehat a_t\) have the correct scaling and integration factor. Since \(d_C(t)\leq d_G(t)\), the absolute differences sum to one-half the total number of cut-edge incidences, which equals \(F(\mathcal C)\). This verifies the claimed sharpness.
No repair is required. The proof establishes the requested hardness conclusion and the allocation certificate. The endpoint observations for \(q=1\) and \(q=\tau\) are also correct.
⟨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.