Answer: Polynomial-time solvable: for \(m=2\), exact classification uses \(O(\tau+m)\) integer arithmetic operations and \(O((\tau+m)L^2)=O(\tau L^2)\) bit operations.
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn WVGs, the problems of determining whether a given pair of agents is synergistic, whether it is antagonis- tic, and whether it is indifferent are NP-hard, NP-hard, and coNP-hard, respectively.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), per-capita weights \(w_t\), two indivisible blocs of weights \(a,b>0\), and quota \(Q\), take finite approximants with \(N\mu_t\) background agents of type \(t\), each of weight \(w_t/N\), along values of \(N\) for which all counts are integral. Let \(W=\sum_{t\in T}\mu_t w_t\) and \(F_W(z)=\min\{1,\max\{0,z/W\}\}\). What is the sign of the limiting difference between the Shapley value of the second bloc when the first commits IN and when it commits OUT? The limit is \(\Delta=F_W(Q-a)-F_W(Q-a-b)-F_W(Q)+F_W(Q-b)\); classify it as positive, negative, or zero.
A society is given by its support \(T\): the list of its \(\tau\geq 1\) positive-mass types, each with a binary rational mass \(\mu_t>0\), with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Each type has a positive binary rational per-capita weight \(w_t\). There are \(m=2\) indivisible blocs, of positive binary rational weights \(a,b\), and a positive binary rational quota \(Q\), with no upper restriction on \(Q\). Let \(L\) be the total input bit length.
For each positive integer \(N\) with all \(N\mu_t\) integral, form a weighted voting game with these two blocs and \(N\mu_t\) background agents of weight \(w_t/N\) for each type. A coalition has value one exactly when its total weight is at least \(Q\), and zero otherwise.
Committing the first bloc IN removes it from the player set and changes the quota to \(Q-a\); committing it OUT removes it and leaves quota \(Q\). No weights or quotas are renormalized; a nonpositive reduced quota makes every coalition winning.
Let \(\Delta\) be the limit, as admissible \(N\to\infty\), of the second bloc's Shapley value after IN minus its Shapley value after OUT. Equivalently, with \(W=\sum_{t\in T}\mu_t w_t\) and \(F_W(z)=\min\{1,\max\{0,z/W\}\}\), the specified limit is \(\Delta=F_W(Q-a)-F_W(Q-a-b)-F_W(Q)+F_W(Q-b)\). The output is positive, negative, or zero according to its exact sign.
Is this continuous sign-classification problem solvable in polynomial time, or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\), with \(m=2\) fixed.
For finite weighted voting games, deciding positive or negative IN-minus-OUT Shapley difference is \(\mathrm{NP}\)-hard, and deciding zero difference is \(\mathrm{coNP}\)-hard. [Source](https://www.cs.toronto.edu/~nisarg/papers/synergies.aaai14.pdf)
A value theory for voting games with finitely many major players and a continuum of insignificant minor players is established, but the verified source does not state the complexity of this exact classification problem. [Source](https://pubsonline.informs.org/doi/10.1287/moor.3.4.290)
The continuous sign-classification problem is solvable in deterministic polynomial time. For the promised case \(m=2\), an exact algorithm uses \(O(\tau+m)\) integer arithmetic operations and \(O((\tau+m)L^2)=O(\tau L^2)\) bit operations with elementary arithmetic.
Proof: reducing classification to an integer sign. By positivity of the masses and per-capita weights, \(W=\sum_{t\in T}\mu_t w_t>0\). Define the clipped function \(H_W(z)=\min\{W,\max\{0,z\}\}\). Then \(F_W(z)=H_W(z)/W\), so the formula supplied in the question gives
\(\displaystyle W\Delta=H_W(Q-a)-H_W(Q-a-b)-H_W(Q)+H_W(Q-b).\)
Thus it suffices to compute the sign of this expression exactly. The following construction performs that computation using integers.
Write every input rational as an integer numerator divided by a positive integer denominator. Let \(D\) be the product of all these denominators, including those of the masses, per-capita weights, bloc weights, and quota. Each denominator divides \(D\); consequently all the following quantities are integers:
\(\displaystyle x_t=D\mu_t,\qquad y_t=Dw_t,\qquad S=\sum_{t\in T}x_ty_t=D^2W,\)
\(\displaystyle A=D^2a,\qquad B=D^2b,\qquad R=D^2Q.\)
Moreover, \(S>0\). Define the integer clipping function \(h(z)=\min\{S,\max\{0,z\}\}\). Since multiplication by a positive constant commutes with clipping,
\(\displaystyle h(D^2z)=D^2H_W(z)\)
for every real \(z\). Therefore the integer
\(\displaystyle K=h(R-A)-h(R-A-B)-h(R)+h(R-B)\)
satisfies \(K=D^2W\Delta=S\Delta\). Because \(S>0\), the signs of \(K\) and \(\Delta\) agree. The algorithm returns positive, negative, or zero according to the exact integer comparison of \(K\) with zero.
This computation handles every boundary case in the question. In particular, when \(Q-a\leq0\), both terms corresponding to the IN Shapley value vanish. When \(Q\geq a+b+W\), all four clipped terms equal \(W\), giving \(\Delta=0\). Equality at a clipping boundary requires no approximation or special numerical convention.
Proof of the running-time bound. The total binary length of all input numerators and denominators is at most \(L\). Hence
\(\displaystyle \log_2D=\sum_d\log_2d=O(L),\)
where the sum counts each input denominator once. Thus \(D\) has \(O(L)\) bits.
For an input rational \(n/d\), compute its integer multiple \(D(n/d)\) as \(n(D/d)\), using exact integer division. Constructing \(D\) and scaling all input rationals require \(O(\tau+m)\) multiplications and divisions. Computing \(S\) requires \(\tau\) multiplications and \(O(\tau)\) additions. Constructing \(A,B,R\) and evaluating \(K\) require only a constant number of further operations when \(m=2\).
Every intermediate integer has \(O(L)\) bits. Indeed, the scaled numerators and their products have \(O(L)\) bits, and summing \(\tau\) such products increases the length by at most \(O(\log\tau)\). Since the input explicitly lists its \(\tau\) positive-mass types, \(\tau=O(L)\), so this increase is also \(O(L)\).
Elementary multiplication and division on \(O(L)\)-bit integers take \(O(L^2)\) bit operations; addition and comparison take \(O(L)\). The resulting upper bound is therefore \(O((\tau+m)L^2)\), or \(O(\tau L^2)\) for \(m=2\). In particular, it is \(O(L^3)\) solely in terms of total input length. These bounds concern the promised two-bloc problem; they assert no extension to arbitrary numbers of blocs.
Relation to the cited results. The finite-game hardness statements are precisely the results of Theorem 2 in [Procaccia, Shah, and Tucker](https://www.cs.toronto.edu/~nisarg/papers/synergies.aaai14.pdf). They do not establish hardness for this limit problem: under the supplied limit formula, all background-type information enters through the single rational aggregate \(W\), which the algorithm computes directly.
[Milnor and Shapley](https://pubsonline.informs.org/doi/10.1287/moor.3.4.290) establish the oceanic-game value-theory setting. The complexity conclusion here follows from the explicit integer algorithm above and does not require attributing a complexity theorem to that paper.
Thus all three sign decisions belong to \(\mathrm{P}\). An \(\mathrm{NP}\)-hardness result under polynomial-time many-one reductions would consequently imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s output fully resolves the assigned problem. The exact sign computation and the claimed polynomial running time are correct. No major or minor issues were found.
The task explicitly supplies the formula for \(\Delta\) as an equivalent definition of the classification target. The prover may therefore use that formula without independently establishing convergence of the finite-game Shapley values. No limit argument is missing.
The proof concerns exactly the promised case \(m=2\), with the support explicitly listed.
Since \(\tau\geq1\), \(\mu_t>0\), and \(w_t>0\), the assertion
\[
W=\sum_{t\in T}\mu_t w_t>0
\]
is correct.
With \(H_W(z)=\min\{W,\max\{0,z\}\}\), the identity \(F_W(z)=H_W(z)/W\) holds for every real \(z\). Multiplying the supplied formula by \(W\) gives exactly the displayed expression for \(W\Delta\). Because \(W>0\), this multiplication preserves the sign.
Every rational input has an integer numerator and positive integer denominator. Their denominator product \(D\) is positive, and every input denominator divides it. Thus \(x_t=D\mu_t\) and \(y_t=Dw_t\) are integers.
The identity
\[
S=\sum_{t\in T}x_ty_t=D^2W
\]
is correct, and \(S>0\). The quantities \(A=D^2a\), \(B=D^2b\), and \(R=D^2Q\) are also integers. Reduced fractional representations are unnecessary: divisibility by \(D\) suffices.
The identity \(h(D^2z)=D^2H_W(z)\) holds for every real \(z\): multiplication by the positive number \(D^2\) preserves order and scales the clipping endpoints from \(0,W\) to \(0,S\).
Applying this identity to the four arguments yields
\[
K=D^2W\Delta=S\Delta.
\]
All signs and arguments in the definition of \(K\) match the task’s formula. Since \(S>0\), comparing \(K\) with zero returns the exact sign of \(\Delta\), including exact equality.
The construction accepts negative clipping arguments and arbitrarily large positive quotas.
If \(Q-a\leq0\), then \(Q-a-b<0\), so both IN terms vanish as claimed. If \(Q\geq a+b+W\), all four arguments of \(H_W\) are at least \(W\), so all four terms equal \(W\) and cancel.
Equality at either clipping endpoint is handled by the definitions. The case \(\tau=1\) also satisfies every step. No additional assumptions about the quota or normalization are introduced.
There are \(2\tau+m+1\) numerical rational inputs. Forming their denominator product and scaling them takes \(O(\tau+m)\) integer operations. Forming \(S\) requires \(\tau\) multiplications and \(O(\tau)\) additions.
Once the scaled inputs are available, constructing \(A,B,R\) and evaluating the four clipping terms takes a constant number of operations for \(m=2\). The total \(O(\tau+m)\) arithmetic-operation bound is justified. The prover explicitly limits this claim to the promised two-bloc problem.
The sum of the binary lengths of the denominators is at most \(L\), so \(D\) has \(O(L)\) bits. Scaled numerators, their products, and the twice-scaled quantities \(A,B,R\) also have \(O(L)\) bits.
Summing \(\tau\) products adds at most \(O(\log\tau)\) bits. Because the support is explicitly listed, \(\tau=O(L)\), and every intermediate integer still has \(O(L)\) bits. Signed differences in the clipping arguments satisfy the same bound.
Elementary multiplication and division consequently cost \(O(L^2)\) per operation; additions and comparisons cost \(O(L)\). The stated bounds
\[
O((\tau+m)L^2)=O(\tau L^2)
\]
for fixed \(m=2\), and \(O(L^3)\) in total input length alone, follow. They are valid upper bounds; optimality is not claimed.
The finite-game attribution matches Theorem 2 of [Procaccia, Shah, and Tucker](https://www.cs.toronto.edu/~nisarg/papers/synergies.aaai14.pdf), with their IN/OUT definitions matching the task. The description of the oceanic-game setting agrees with the abstract of [Milnor and Shapley](https://pubsonline.informs.org/doi/10.1287/moor.3.4.290). Neither citation supplies an unverified premise needed by the algorithm.
The exact polynomial-time algorithm establishes that each of the three sign decision problems belongs to \(\mathrm{P}\). The concluding implication concerning \(\mathrm{NP}\)-hardness under polynomial-time many-one reductions is correct.
No repair or additional clarification is 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.