Answer: \(\mathrm{NP}\)-complete, even with hyperedges of size at most three
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a family of hypergraph games with dependency degree~7 and supermodular degree~1 for which the separation problem for $\LP_0$ is {\em NP}-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many role types \(T\) with rational masses \(\mu_t>0\) summing to \(1\), a weighted hypergraph on \(T\) of rank at most four defining \(V(y)=\sum_{E\in\mathcal E}w_E\prod_{t\in E}y_t\), nonnegative rational payoff rates \(a_t\) satisfying \(\sum_t\mu_ta_t=V(\mathbf 1)\), and a positive rational threshold \(\varepsilon\), decide whether some participation vector \(y\in[0,1]^T\) has excess \(V(y)-\sum_t\mu_ta_ty_t\ge\varepsilon\).
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
The input includes an explicitly listed hypergraph \(\mathcal E\) with \(m\) nonempty edges, each satisfying \(1\leq |E|\leq4\), and signed binary rational weights \(w_E\). Define \(V(y)=\sum_{E\in\mathcal E}w_E\prod_{t\in E}y_t\).
A participation vector \(y\in[0,1]^T\) selects mass \(\mu_ty_t\) of type \(t\). The input payoff rates \(a_t\) are nonnegative binary rationals satisfying \(\sum_t\mu_ta_t=V(\mathbf1)\) and \(\mu_ta_t\geq V(\mathbf e_t)\) for every type, where \(\mathbf e_t\) is its unit vector.
Given a positive binary rational \(\varepsilon\), decide whether some participation vector has \(V(y)-\sum_t\mu_ta_ty_t\geq\varepsilon\). Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous excess-threshold decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For discrete hypergraph games, deciding whether a coalition exceeds a given excess threshold at an imputation is \(\mathrm{NP}\)-hard even with rank at most four, dependency degree seven, and supermodular degree one. Dependency counts players whose presence can change another player's marginal contribution; supermodular dependency counts those whose presence can increase it.
The supplied discrete results do not establish a complexity classification for the fractional participation problem stated here.
The problem is \(\mathrm{NP}\)-complete, even with hyperedges of size at most three, uniform dyadic masses, and identical positive payoff rates. Consequently, it is not in \(\mathrm P\) unless \(\mathrm P=\mathrm{NP}\).
Define the excess function
\(F(y)=V(y)-\sum_{t\in T}\mu_ta_ty_t\).
Every hyperedge is a set, so each variable occurs with exponent at most one in every monomial. Thus \(F\) is affine in each coordinate separately.
Fix \(y\in[0,1]^T\) and a type \(t\). Let \(y^{t,0}\) and \(y^{t,1}\) be obtained by setting coordinate \(t\) to zero and one, respectively. Affineness gives
\[
F(y)=(1-y_t)F(y^{t,0})+y_tF(y^{t,1}).
\]
Since \(0\leq y_t\leq1\), at least one of these endpoint values is at least \(F(y)\).
Apply this argument successively to every coordinate, retaining an endpoint that does not decrease the excess. After \(\tau\) steps, the resulting vector \(b\in\{0,1\}^T\) satisfies \(F(b)\geq F(y)\). Therefore
\[
\max_{y\in[0,1]^T}F(y)
=
\max_{b\in\{0,1\}^T}F(b).
\]
In particular, the continuous instance is a yes-instance exactly when it has a Boolean witness. This proves the bridge from fractional participation to discrete coalitions.
A certificate consists of \(\tau\) bits specifying \(b\in\{0,1\}^T\). Its excess is
\[
F(b)=
\sum_{\substack{E\in\mathcal E\\b_t=1\text{ for every }t\in E}}w_E
-
\sum_{\substack{t\in T\\b_t=1}}\mu_ta_t.
\]
This expression can be compared with \(\varepsilon\) using exact rational arithmetic. To bound its bit complexity, take a common denominator equal to the product of all denominators appearing in the input. This denominator has \(O(L)\) bits and clears both the weights and the products \(\mu_ta_t\). The resulting integer coefficients and accumulated sums also have \(O(L)\) bits.
Using classical integer arithmetic, certificate verification takes
\[
O((m+\tau)L^2)
\]
bit operations. Hence the problem belongs to \(\mathrm{NP}\).
Enumerating all Boolean vectors gives a deterministic decision algorithm taking
\[
O\!\left(2^\tau(m+\tau)L^2\right)
\]
bit operations. The exponential factor depends on the actual support size \(\tau\).
We reduce from unweighted Max Cut: given a simple graph \(G=(U,A)\) and a positive integer \(k\), decide whether a cut contains at least \(k\) edges. This problem is \(\mathrm{NP}\)-complete. [Garey, Johnson, and Stockmeyer, *Some simplified NP-complete graph problems*](https://doi.org/10.1016/0304-3975(76)90059-1).
Write \(n=|U|\), \(p=|A|\), and \(d_v=\deg_G(v)\). Choose the smallest power of two \(q\) satisfying \(q\geq n+1\). Introduce a gate type \(z\) and a set \(D\) of \(q-n-1\) additional types. Set
\[
T=U\cup\{z\}\cup D,\qquad
\tau=q,\qquad
\mu_t=\frac1q,\qquad
a_t=q
\quad(t\in T).
\]
Thus every mass is positive and dyadic, the masses sum to one, every rate is positive, and \(\mu_ta_t=1\).
Define
\[
V(y)=
\sum_{t\in T}y_t
+
\sum_{\substack{v\in U\\d_v>0}}d_vy_zy_v
-
2\sum_{\{u,v\}\in A}y_zy_uy_v.
\]
This is an explicitly listed hypergraph polynomial consisting of:
Every edge has size at most three. Set \(\varepsilon=k>0\).
The handshake identity \(\sum_{v\in U}d_v=2p\) gives
\[
V(\mathbf1)=q+2p-2p=q.
\]
Meanwhile,
\[
\sum_{t\in T}\mu_ta_t=q.
\]
Thus efficiency holds.
For any type \(t\), all nonsingleton monomials vanish at \(\mathbf e_t\), so
\[
V(\mathbf e_t)=1=\mu_ta_t.
\]
Thus every individual-rationality inequality holds, with equality.
The singleton terms cancel the payoff terms. Hence
\[
F(y)=
y_z\left(
\sum_{v\in U}d_vy_v
-
2\sum_{\{u,v\}\in A}y_uy_v
\right).
\]
Consider a Boolean vector \(b\), and put \(S=\{v\in U:b_v=1\}\).
If \(b_z=0\), then \(F(b)=0\). If \(b_z=1\), then
\[
F(b)=
\sum_{\{u,v\}\in A}
\left(b_u+b_v-2b_ub_v\right).
\]
For each graph edge, the summand is one precisely when exactly one endpoint belongs to \(S\), and zero otherwise. Therefore
\[
F(b)=|\delta_G(S)|,
\]
where \(\delta_G(S)\) denotes the edges crossing the cut.
The additional types in \(D\) have no effect on excess. It follows that
\[
\max_{b\in\{0,1\}^T}F(b)
=
\max_{S\subseteq U}|\delta_G(S)|.
\]
By the rounding result,
\[
\exists y\in[0,1]^T:\ F(y)\geq k
\quad\Longleftrightarrow\quad
\exists S\subseteq U:\ |\delta_G(S)|\geq k.
\]
This establishes both directions of the reduction.
If \(n_+\) is the number of nonisolated graph vertices, the constructed instance has
\[
\tau=q<2(n+1),\qquad m=q+n_++p.
\]
All indices, weights, masses, and rates require \(O(\log(n+2))\) bits each. Consequently,
\[
L=O((n+p)\log(n+2)+\log(k+1)).
\]
The graph degrees and the explicit output can be constructed in time polynomial in the graph input length; a direct implementation takes
\[
O((n+p)\log(n+2)+\log(k+1))
\]
bit operations under the usual explicit graph encoding.
Thus the reduction is polynomial and produces valid instances. Together with membership in \(\mathrm{NP}\), it proves the claimed classification.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the task. It proves that the continuous excess-threshold decision problem is \(\mathrm{NP}\)-complete, including the claimed restriction to hyperedges of size at most three, uniform dyadic masses, and identical positive payoff rates.
No major or minor mathematical issues were found. No repair or additional clarification is needed.
Every hyperedge is a set, so its monomial contains each variable at most once. Subtracting the linear payoff terms preserves separate affineness in every coordinate.
The identity
\[
F(y)=(1-y_t)F(y^{t,0})+y_tF(y^{t,1})
\]
is correct. Since the coefficients are nonnegative and sum to one, one endpoint has value at least \(F(y)\).
Successive rounding is valid: each operation fixes one coordinate without changing previously fixed coordinates or decreasing the current value. After exactly \(\tau\) operations, the resulting Boolean vector satisfies the stated inequality.
Consequently, every fractional threshold witness yields a Boolean threshold witness. The reverse implication follows because Boolean vectors belong to the participation domain. The equality of maxima is also justified: the Boolean domain is finite, and the rounding argument bounds every fractional value by a Boolean value.
Assessment: Correct, with all required quantifiers and domain restrictions respected.
The proposed certificate has \(\tau\) bits. The displayed expression for its excess correctly includes precisely the hyperedges whose coordinates are all selected and the payoff terms for selected types.
The common-denominator argument is valid when “all denominators appearing in the input” counts their input occurrences. In particular, the denominator factors for both \(\mu_t\) and \(a_t\) are included, so their product denominator is cleared. Repeated numerical denominator values cause no problem.
The product denominator has \(O(L)\) bits. Scaled numerators, products, and accumulated sums also have \(O(L)\) bits; the additional growth from summing explicitly listed terms is absorbed by \(L\). Including the denominator of \(\varepsilon\) allows an exact threshold comparison.
Because each edge has at most four members, the claimed certificate-verification bound
\[
O((m+\tau)L^2)
\]
is sufficient under classical integer arithmetic. The exhaustive-search bound
\[
O(2^\tau(m+\tau)L^2)
\]
therefore follows.
Assessment: Correct. The running times use the actual support size, as required.
The reduction uses the decision version of unweighted Max Cut on simple graphs. Its cited source establishes NP-completeness of Simple Max Cut with unit edge weights. The citation is appropriate. Restricting to positive thresholds excludes only automatically affirmative nonpositive-threshold instances and does not undermine the hardness premise. [Garey, Johnson, and Stockmeyer](https://www.sciencedirect.com/science/article/pii/0304397576900591)
Assessment: The cited hardness result matches the source problem used.
The padding count is nonnegative because \(q\geq n+1\). There are exactly \(q\) types, each with positive dyadic mass \(1/q\), and their masses sum to one.
All payoff rates equal the positive integer \(q\), giving \(\mu_ta_t=1\).
The listed singleton, pair, and triple edges are nonempty and have rank at most three. Simplicity of the source graph and the distinct gate type ensure that the listed triples have three distinct members. All coefficients have valid signed binary rational encodings.
The efficiency calculation is correct:
\[
V(\mathbf1)=q+2p-2p=q=\sum_t\mu_ta_t.
\]
At each unit vector, every nonsingleton monomial vanishes, leaving exactly the singleton contribution. Thus every individual-rationality inequality holds with equality.
The threshold \(k\) is a positive binary rational as required.
Assessment: Every input constraint is satisfied.
The singleton contributions cancel the payoff terms exactly, yielding the stated gated excess expression.
For Boolean participation with the gate selected, the degree sum converts correctly into the displayed sum over graph edges. Each edge contribution is zero when its endpoints have equal Boolean values and one when they differ. Hence the excess equals the cut size.
With the gate unselected, the excess is zero. Padding types have no effect on excess. Since cut sizes are nonnegative, these observations justify the claimed equality of Boolean maxima.
The earlier rounding result then gives both directions of the continuous decision equivalence. No assertion that fractional participation itself represents an ordinary cut is needed.
Assessment: Correct; the reduction establishes hardness for the continuous problem.
The bounds on \(q\), \(\tau\), and \(m\) are correct. Degrees, indices, masses, and rates have the stated logarithmic encoding sizes. The threshold contributes its binary encoding length separately.
The resulting bound on \(L\) and the claimed polynomial construction time are valid under the explicitly stated usual explicit graph encoding.
Assessment: Correct. The reduction is polynomial.
The argument establishes the claimed complexity classification independently of the supplied discrete-game hardness results. It does not establish the additional dependency-degree restrictions mentioned in the task, but it does not claim them, and they are not required.
There are no blocking issues or requested repairs.
⟨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.