Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCHECK-IF-BLOCKED is NP-complete, even when |Ci| = 3 for all i, vi only takes on values in {0, 1} for all i, and all the vi (and thus, by Lemmas 1 and 2, v) are increasing and superadditive.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given types \(T\) with rational masses \(\mu_t>0\), \(\sum_{t\in T}\mu_t=1\), per-unit assigned payoffs \(p_t\), and issue tables \(v_i:\{0,1\}^{C_i}\to\{0,1\}\) with \(|C_i|\le 3\), decide whether there are participation fractions \(q_t\in[0,1]\) such that \(\sum_i\widetilde v_i(q)>\sum_t p_t\mu_tq_t\), where \(\widetilde v_i\) is the multilinear extension of \(v_i\).
A society is given by its support: a list \(T\) of \(\tau\ge1\) types with positive binary rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has an assigned per-unit payoff \(p_t\in\mathbb Q\), of either sign. There are \(m\ge1\) issues, each specified by \(C_i\subseteq T\), \(|C_i|\le3\), and an explicit table \(v_i:\{0,1\}^{C_i}\to\{0,1\}\). No monotonicity or superadditivity promise is imposed.
A coalition selects participation fractions \(q\in[0,1]^T\), retaining mass \(\mu_tq_t\) of type \(t\). Its issue value is \(\widetilde v_i(q)=\sum_{x\in\{0,1\}^{C_i}}v_i(x)\prod_{t\in C_i:x_t=1}q_t\prod_{t\in C_i:x_t=0}(1-q_t)\), and its assigned payoff is \(\sum_{t\in T}p_t\mu_tq_t\).
Payoffs need not be feasible for the grand coalition; neither efficiency nor individual rationality is required. Let \(L\) be the total binary input length, and state running times in \(m,\tau,L\).
Is deciding whether there exists \(q\in[0,1]^T\) with \(\sum_{i=1}^{m}\widetilde v_i(q)>\sum_{t\in T}p_t\mu_tq_t\) solvable in polynomial time, or is it NP-hard?
For finite agents, deciding whether a blocking coalition exists is NP-complete, even with three agents per issue and increasing, superadditive issue tables taking values in \(\{0,1\}\).
That discrete result does not classify the participation-fraction problem defined here.
The problem is NP-complete, even when every issue involves only two types, all masses are equal dyadic rationals, and all per-unit payoffs are nonnegative integers.
Define the surplus by
\( F(q)=\sum_{i=1}^{m}\widetilde v_i(q)-\sum_{t\in T}p_t\mu_tq_t. \)
Fix any \(q\in[0,1]^T\). Let \(X\in\{0,1\}^T\) be a random vector whose coordinates are independent and satisfy \(\Pr(X_t=1)=q_t\).
By independence and the definition of the issue extension,
\( \mathbb E[v_i(X|_{C_i})]=\widetilde v_i(q). \)
Also, \(\mathbb E[X_t]=q_t\). Consequently, linearity of expectation gives
\( F(q)=\mathbb E[F(X)]\le \max_{x\in\{0,1\}^T}F(x). \)
Conversely, every Boolean vector belongs to the participation cube. Therefore,
\( \max_{q\in[0,1]^T}F(q)=\max_{x\in\{0,1\}^T}F(x). \)
In particular, a strictly positive fractional surplus exists if and only if a strictly positive Boolean surplus exists. This argument concerns the extension specified in the question and does not rely on the stated finite-agent hardness result.
A certificate is a Boolean participation vector \(x\), requiring \(\tau\) bits. At such a vector,
\( F(x)=\sum_{i=1}^{m}v_i(x|_{C_i})-\sum_{t\in T}p_t\mu_tx_t. \)
Each issue requires a lookup in a table with at most eight entries.
The strict inequality can be checked using exact integer arithmetic. Let \(H\) be the product of the positive denominators appearing in the input representations of all \(p_t\) and \(\mu_t\). Its binary length is \(O(L)\), and every \(Hp_t\mu_t\) is an integer. Thus the verification reduces to checking
\( H\sum_{i=1}^{m}v_i(x|_{C_i})-\sum_{t\in T}(Hp_t\mu_t)x_t>0. \)
All integers in this calculation have \(O(L)\) bits. Using elementary integer arithmetic, a conservative verification bound is \(O((m+\tau)L^2)\) bit operations. Hence the problem belongs to NP.
The same reasoning gives an exact deterministic algorithm with running time
\( O\!\left(2^\tau(m+\tau)L^2\right), \)
by enumerating all Boolean participation vectors.
We reduce from Independent Set: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether \(G\) has an independent set of size at least \(k\). This problem is NP-complete, since taking graph complements converts the NP-complete CLIQUE problem into Independent Set. See [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(n=|V|\). We may restrict to \(n\ge1\) and \(1\le k\le n\), since excluded thresholds are trivial and can be replaced by fixed yes- or no-instances.
Let \(D\) be the smallest power of two satisfying \(D\ge n+1\). Introduce:
Thus the support size is \(\tau=D<2(n+1)\). Give every type mass \(\mu_t=1/D\). These masses are positive dyadic rationals and sum to one.
Orient every edge arbitrarily. Let \(d_u^+\) denote the number of edges directed out of vertex \(u\).
Create two kinds of issues:
For clarity, the two explicit tables are:
| Input coordinates | First table | Second table |
|---|---:|---:|
| \((0,0)\) | \(0\) | \(0\) |
| \((0,1)\) | \(0\) | \(0\) |
| \((1,0)\) | \(0\) | \(1\) |
| \((1,1)\) | \(1\) | \(0\) |
Their participation extensions are respectively \(q_aq_u\) and \(q_u(1-q_v)\), directly from the definition in the question.
Assign per-unit payoffs
\( p_u=Dd_u^+\quad(u\in V),\qquad p_a=D\left(k-\tfrac12\right),\qquad p_t=0\quad\text{for dummy types}. \)
All these payoffs are nonnegative integers: \(D\) is even because \(n\ge1\). Their retained-payoff coefficients are
\( p_u\mu_u=d_u^+,\qquad p_a\mu_a=k-\tfrac12. \)
The construction has \(m=n+|E|\ge1\) issues, each involving exactly two types. Every issue vanishes at zero participation. Its total binary encoding length is \(O((n+|E|)\log(n+1))\), so the construction is polynomial.
For every participation vector \(q\), the constructed surplus is
\( F(q)=\sum_{u\in V}q_aq_u+\sum_{u\to v}q_u(1-q_v)-\sum_{u\in V}d_u^+q_u-\left(k-\tfrac12\right)q_a. \)
Since \(\sum_{u\to v}q_u=\sum_{u\in V}d_u^+q_u\), the linear terms cancel, yielding
\( F(q)=q_a\sum_{u\in V}q_u-\sum_{u\to v}q_uq_v-\left(k-\tfrac12\right)q_a. \)
Dummy coordinates do not affect this expression.
For Boolean participation, let \(S\subseteq V\) be the participating vertices, and let \(e_G(S)\) count the edges with both endpoints in \(S\). If the additional type does not participate, then
\( F(0,S)=-e_G(S)\le0. \)
If it participates, then
\( F(1,S)=|S|-e_G(S)-k+\tfrac12. \)
Let \(\alpha(G)\) be the maximum independent-set size. Then
\( \max_{S\subseteq V}\bigl(|S|-e_G(S)\bigr)=\alpha(G). \)
Proof. Fix any \(S\). Choose one endpoint of every edge induced by \(S\), and let \(R\) be the set of chosen endpoints. Then \(|R|\le e_G(S)\), and \(S\setminus R\) is independent because every induced edge has an endpoint in \(R\). Therefore,
\( \alpha(G)\ge |S\setminus R|=|S|-|R|\ge |S|-e_G(S). \)
For the reverse inequality, take a maximum independent set \(S\). It satisfies \(|S|=\alpha(G)\) and \(e_G(S)=0\). This proves the equality. \(\square\)
Using the lemma and Section 1, the maximum surplus over all fractional participation vectors is exactly
\( \max_{q\in[0,1]^T}F(q)=\max\left\{0,\alpha(G)-k+\tfrac12\right\}. \)
The zero is achievable by the empty coalition. Since \(\alpha(G)\) and \(k\) are integers, this maximum is strictly positive if and only if \(\alpha(G)\ge k\).
Thus the construction is a polynomial many-one reduction from Independent Set. Together with membership in NP, it proves NP-completeness. A polynomial-time algorithm for the problem would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes NP-completeness for the specified participation-fraction problem, including the claimed restriction to issues involving two types, equal dyadic masses, and nonnegative integer per-unit payoffs. No major or minor mathematical issues were found.
The expectation argument is valid for every \(q\in[0,1]^T\), including boundary coordinates.
Independence gives exactly the product probabilities used in the definition of each \(\widetilde v_i(q)\). Linearity of expectation then applies to both the issue values and the assigned payoff, regardless of payoff signs or overlap between issue supports.
The inequality \(F(q)\le\max_{x\in\{0,1\}^T}F(x)\) follows because an expectation over a finite set cannot exceed its largest value. Conversely, a maximizing Boolean vector exists and belongs to the participation cube. Thus the asserted equality of maxima is justified without an unstated attainment assumption.
The strict-positivity equivalence follows directly. This genuinely classifies the specified continuous problem; it does not assume that finite-agent hardness transfers automatically.
Empty issue supports, which the task permits, do not invalidate the argument: their issue values are constants under both participation models.
The Boolean certificate has length \(\tau\), and each issue table contains at most eight entries. Evaluating its selected entry is therefore sufficient.
The denominator construction is correct. If \(p_t=a_t/b_t\) and \(\mu_t=c_t/d_t\), the product \(H\) includes both denominator factors, so \(b_td_t\) divides \(H\). Consequently, \(Hp_t\mu_t\) is an integer even when the two denominators share factors.
The binary length of \(H\) is bounded by the sum of the input denominator lengths, hence is \(O(L)\). Scaled coefficients and accumulated sums also have \(O(L)\) bits: summation adds at most logarithmic overhead in \(m+\tau\), already covered by the explicit input length.
Multiplication by positive \(H\) preserves the strict inequality. Negative payoff numerators present no difficulty for signed exact arithmetic.
The stated verification bound \(O((m+\tau)L^2)\) is conservative and valid using elementary integer arithmetic. Enumerating all Boolean vectors gives the stated exact deterministic bound \(O(2^\tau(m+\tau)L^2)\).
The source problem is precisely the Independent Set decision problem on simple undirected graphs. The cited NP-completeness foundation is standard; graph complementation preserves the threshold and converts cliques to independent sets. The prover supplies the relevant graph and threshold hypotheses. [Karp’s cited publication](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9)
Restricting to \(n\ge1\) and \(1\le k\le n\) is legitimate: excluded instances have immediately determined answers and can be replaced by fixed instances.
Every constructed input satisfies the target requirements:
The encoding-length bound is valid: type identifiers, masses, and payoffs require \(O(\log(n+1))\) bits each, and every table has constant size. The construction is polynomial under the usual explicit graph encoding.
The edge tables are nonmonotone, which is permitted by the task.
The cancellation is exact. Each oriented edge contributes one positive linear term at its tail, and the assigned coefficient \(d_u^+\) counts precisely those contributions.
At Boolean participation, each graph edge contributes to the remaining quadratic sum exactly when both endpoints participate. Arbitrary orientation therefore causes neither omissions nor double counting.
Both cases are correct:
Dummy coordinates have zero payoff and occur in no issues, so they cannot change these values.
The lemma is fully proved.
Choosing one endpoint from every induced edge produces a set \(R\subseteq S\) with \(|R|\le e_G(S)\). Every induced edge meets \(R\), so \(S\setminus R\) is independent. This establishes the claimed upper bound on \(|S|-e_G(S)\).
A maximum independent set attains equality. The proof also covers empty subsets and edgeless graphs.
The maximum with \(a\) absent is exactly zero, attained by the empty participating vertex set. The graph lemma gives the maximum with \(a\) present. Section 1 then justifies the asserted fractional maximum.
The half-integer threshold correctly handles strict positivity. If \(\alpha(G)\ge k\), the second maximum is at least \(\tfrac12\). Otherwise, integrality gives \(\alpha(G)\le k-1\), making it at most \(-\tfrac12\); the overall maximum is then zero.
Thus the reduction preserves both yes- and no-instances. Together with NP membership, it establishes NP-completeness.
Repair feedback: None required.
⟨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.