Answer: \(\mathrm{NP}\)-hard under polynomial-time many-one reductions
Theorem 3.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet G be a graph game, and x be an imputation of G. Then, deciding whether x belongs to B(G) is ΠP 2 -hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\), a symmetric rational interaction matrix \(W\), and a per-capita imputation \(x_t\), where \(v(q)=\frac12\sum_{t,u}W_{tu}q_tq_u\) and \(\sum_t\mu_tx_t=v(\mu)\), decide whether the imputation belongs to the type-mass bargaining set. An objection by type \(a\) against type \(b\) chooses \(q\in[0,\mu]\) with \(q_a>0\) and \(q_b<\mu_b\), and per-capita rates \(y_t>x_t\) for included mass, summing to \(v(q)\). A counterobjection chooses \(r\) with \(r_b>0\) and \(r_a<\mu_a\), specifies feasible overlap masses \(h_t\), and allocates exactly \(v(r)\) while meeting the original objection’s lower bounds on overlap and the imputation’s lower bounds outside it. The decision is whether every such objection has a feasible counterobjection; complexity is measured in \(\tau\) and the binary input length \(L\).
A society is atomless and given by its support: \(\tau\) types with positive binary rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types. Input also includes a symmetric matrix \(W\in\mathbb Q^{\tau\times\tau}\) with unrestricted signs and diagonal, and rational per-capita payoffs \(x_t\geq0\). Let \(L\) be the total binary input length; running times are measured in \(\tau,L\), with no separate candidate parameter \(m\).
For every real coalition mass vector \(q\in\prod_t[0,\mu_t]\), define \(v(q)=\frac12\sum_{t,u}W_{tu}q_tq_u\). The input imputation satisfies \(\sum_t\mu_tx_t=v(\mu)\); individual agents have zero singleton worth.
For distinct types \(a,b\), an objection consists of real masses \(q\) with \(q_a>0\), \(q_b<\mu_b\), and real rates \(y_t\) satisfying \(y_t>x_t\) whenever \(q_t>0\) and \(\sum_tq_ty_t=v(q)\).
A counterobjection consists of real masses \(r\in\prod_t[0,\mu_t]\) with \(r_b>0\), \(r_a<\mu_a\), and overlap masses satisfying \(\max\{0,q_t+r_t-\mu_t\}\leq h_t\leq\min\{q_t,r_t\}\) for every type.
It assigns real rates \(z_t^{\mathrm{in}}\) on overlap and \(z_t^{\mathrm{out}}\) outside the objection, satisfying \(z_t^{\mathrm{in}}\geq y_t\) when \(h_t>0\), \(z_t^{\mathrm{out}}\geq x_t\) when \(r_t-h_t>0\), and \(\sum_t[h_tz_t^{\mathrm{in}}+(r_t-h_t)z_t^{\mathrm{out}}]=v(r)\). Rates on zero-mass pieces are irrelevant.
The type-mass bargaining set consists of imputations for which every objection has a counterobjection.
Is membership in this type-mass bargaining set solvable in polynomial time in \(\tau,L\), or is it NP-hard?
For finite graph games with signed edge weights, bargaining-set membership is \(\Pi_2^P\)-hard and, together with the matching upper bound, \(\Pi_2^P\)-complete. [Verified full version](https://arxiv.org/pdf/0810.3136).
No result settling membership for the exact type-mass model defined here was located in the literature search.
Membership in the stated type-mass bargaining set is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. This holds even when all masses are equal dyadic rationals, all payoffs are strictly positive, and every diagonal entry of \(W\) is positive.
The proof below accounts for arbitrary real objection rates and arbitrary real countercoalition masses.
Fix an objection \((q,y)\) by type \(a\) against type \(b\). Define \(d_t=y_t-x_t>0\) when \(q_t>0\), and set \(d_t=0\) otherwise. For any prospective countercoalition \(r\), define
\[ F_{q,y}(r)=v(r)-\sum_t x_t r_t-\sum_t d_t\max\{0,q_t+r_t-\mu_t\}. \]
Here and below, the displayed formulas use the same mathematical notation as the inline formulas.
Counterobjection criterion. An admissible mass vector \(r\), meaning \(r_b>0\) and \(r_a<\mu_a\), supports a counterobjection if and only if \(F_{q,y}(r)\geq0\).
Indeed, for any allowed overlap \(h\), the minimum required payment is
\[ \sum_t\bigl[h_ty_t+(r_t-h_t)x_t\bigr] =\sum_t x_tr_t+\sum_t d_th_t. \]
Because every relevant \(d_t\) is positive, this payment is minimized by choosing \(h_t=\max\{0,q_t+r_t-\mu_t\}\). Thus \(F_{q,y}(r)\geq0\) is necessary. It is sufficient because the minimum rates can be assigned first, and any remaining surplus can be added to a positive-mass piece. Such a piece exists because \(r_b>0\).
We will use two consequences.
Positive surplus anywhere suffices. If \(F_{q,y}(r^0)>0\) at any point of the mass box, the objection has a counterobjection. To see this, choose \(s\) in the box with \(s_a=0\) and \(s_b=\mu_b\), and put \(r^\varepsilon=(1-\varepsilon)r^0+\varepsilon s\). For every \(0<\varepsilon<1\), this vector satisfies the countercoalition restrictions. Continuity gives \(F_{q,y}(r^\varepsilon)>0\) for sufficiently small \(\varepsilon\).
Every fractional objection has a counterobjection. The objection budget gives \(v(q)-\sum_t x_tq_t=\sum_t d_tq_t\). Consequently,
\[ F_{q,y}(q) =\sum_t d_t\bigl[q_t-\max\{0,2q_t-\mu_t\}\bigr] =\sum_t d_t\min\{q_t,\mu_t-q_t\}. \]
If \(0<q_t<\mu_t\) for any type, its summand is strictly positive, and all other summands are nonnegative. The preceding consequence therefore applies.
Thus every objection without a counterobjection must use either zero or the entire mass of each type.
We reduce from Independent Set: given a simple undirected graph \(G\) with \(n\geq1\) vertices and an integer \(1\leq k\leq n\), decide whether \(G\) has an independent set of size at least \(k\). This is the standard \(\mathrm{NP}\)-complete problem, equivalently Clique on the complement graph; see [Karp’s theorem](https://doi.org/10.1007/978-1-4684-2001-2_9).
To make the masses dyadic, first add isolated vertices until \(n+2\) is a power of two, increasing \(k\) by the number added. This preserves the answer because each added vertex increases the independence number by one. It increases the graph size by only a constant factor. Rename the resulting parameters \(n,k\).
Introduce one type for each graph vertex, together with two additional types \(\alpha,\beta\). Set
\[ N=n+2,\qquad \mu_t=\frac1N,\qquad M=n+1,\qquad A=k+M|E(G)|+1. \]
Define a symmetric integer matrix \(H\) by the following entries; unspecified off-diagonal entries are zero:
Set \(W=N^2H\), and choose per-capita payoffs
\[ x_\alpha=N,\qquad x_\beta=N(A+1+k),\qquad x_i=N(A+1). \]
All payoffs are strictly positive.
For normalized masses \(u_t=Nq_t\), the worth is
\[ v(q)=(A+1)\sum_tu_t^2-Mu_\alpha u_\beta +u_\beta\sum_i u_i-M\sum_{\{i,j\}\in E(G)}u_i u_j. \]
The proposed imputation is efficient. At the grand coalition,
\[ v(\mu)=N(A+1)-M+n-M|E(G)|. \]
On the other hand,
\[ \sum_t\mu_tx_t=N(A+1)-A+k. \]
These are equal because \(A-k=M|E(G)|+1\) and \(M=n+1\).
For a coalition consisting of entire types, let \(U\) denote its graph-vertex types and let \(e(U)\) be the number of graph edges induced by \(U\). Its excess over the imputation is
\[ A\mathbf1_{\{\alpha\in S\}}-k\mathbf1_{\{\beta\in S\}} +\mathbf1_{\{\beta\in S\}}|U|-Me(U) -M\mathbf1_{\{\alpha,\beta\in S\}}. \]
By Section 1, every fractional objection already has a counterobjection. Consider an objection consisting of entire types, with support \(S\). Its target type is outside \(S\).
If the target is a graph-vertex type \(i\), use all agents of that type as the countercoalition. Its worth and imputation payment are both \(A+1\).
If the target is \(\alpha\), use all agents of type \(\alpha\). Its worth is \(A+1\), whereas its imputation payment is \(1\).
In either case, this countercoalition has zero overlap with the objection, includes the target, and excludes the objecting type. Its surplus is nonnegative, so the counterobjection criterion applies.
Now \(\beta\notin S\), so the objection’s excess is
\[ A\mathbf1_{\{\alpha\in S\}}-Me(U). \]
An objection requires strictly positive excess. Hence \(\alpha\in S\).
Suppose \(U\neq\varnothing\). Define the positive total payment increments \(\delta_t=\mu_t(y_t-x_t)\) for \(t\in S\). The objection budget implies
\[ \delta_\alpha+\sum_{i\in U}\delta_i=A-Me(U). \]
Because \(U\neq\varnothing\) and each \(\delta_i>0\), we have \(\delta_\alpha<A\). At the mass vector consisting only of all agents of type \(\alpha\),
\[ F_{q,y}(\mu_\alpha e_\alpha) =(A+1)-(1+\delta_\alpha)=A-\delta_\alpha>0. \]
Positive surplus anywhere suffices, so this objection also has a counterobjection, regardless of which type in \(S\) objects.
The sole remaining possibility is therefore the objection by \(\alpha\) against \(\beta\) consisting of all agents of type \(\alpha\). Its budget uniquely determines
\[ q_\alpha=\frac1N,\qquad q_t=0\ (t\neq\alpha),\qquad y_\alpha=N(A+1). \]
It is a valid objection because \(y_\alpha>x_\alpha=N\).
Fix that objection. Write \(s_t=Nr_t\), so \(s\in[0,1]^N\). All countercoalition agents of type \(\alpha\) necessarily overlap the objection, and every other type has zero overlap.
Its surplus after minimum required payments is therefore
\[ F(s)=(A+1)\sum_t(s_t^2-s_t)-ks_\beta +s_\beta\sum_i s_i -M\sum_{\{i,j\}\in E(G)}s_i s_j -Ms_\alpha s_\beta. \]
The countercoalition restrictions are \(s_\beta>0\) and \(s_\alpha<1\).
If \(U\) is independent and \(|U|\geq k\), take \(s_\alpha=0\), \(s_\beta=1\), and include exactly the vertex types in \(U\), each with full mass. Then
\[ F(s)=|U|-k\geq0. \]
This vector satisfies both countercoalition restrictions, so it supports a counterobjection.
Suppose the independence number of \(G\) is smaller than \(k\).
First evaluate \(F\) at every Boolean vector \(\eta\in\{0,1\}^N\), and put \(U=\{i:\eta_i=1\}\).
If \(\eta_\beta=0\), then \(F(\eta)=-Me(U)\leq0\).
If \(\eta_\beta=1\), then
\[ F(\eta)=|U|-k-Me(U)-M\eta_\alpha. \]
When \(U\) is independent, \(|U|\leq k-1\), so this expression is at most \(-1\). When \(U\) is not independent, \(e(U)\geq1\), and
\[ |U|-k-Me(U)\leq n-k-(n+1)=-k-1<-1. \]
Thus every Boolean vector satisfies \(F(\eta)\leq-\eta_\beta\).
Now fix an arbitrary real vector \(s\in[0,1]^N\). Let the coordinates of a random Boolean vector \(\eta\) be independent, with \(\Pr(\eta_t=1)=s_t\). Independence gives \(\mathbb E[\eta_t\eta_u]=s_ts_u\) for distinct types. Also, \(\eta_t^2=\eta_t\). Substitution into the formula for \(F\) yields
\[ F(s)=\mathbb E[F(\eta)]-(A+1)\sum_t s_t(1-s_t). \]
The Boolean bound therefore implies
\[ F(s)\leq-s_\beta-(A+1)\sum_t s_t(1-s_t)\leq-s_\beta. \]
Every admissible countercoalition has \(s_\beta>0\), so its surplus is strictly negative. By the counterobjection criterion, none can work.
This rules out all real countercoalitions.
If \(G\) has an independent set of size at least \(k\), Section 4 supplies a counterobjection to the sole remaining objection; Section 3 handles all others. Hence the constructed imputation belongs to the bargaining set.
If \(G\) has no such independent set, the objection consisting of all agents of type \(\alpha\), directed against \(\beta\), has no counterobjection. Hence the imputation does not belong to the bargaining set.
We have proved
\[ G\text{ has an independent set of size at least }k \quad\Longleftrightarrow\quad x\text{ belongs to the constructed bargaining set}. \]
The support size is \(\tau=N=O(n)\). Since \(A=O(n^3)\), every integer coefficient has \(O(\log n)\) bits, and the dense output has length \(O(n^2\log n)\). The construction takes polynomial time and uses no additional candidate parameter.
Thus membership is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated task: membership is \(\mathrm{NP}\)-hard under polynomial-time many-one reductions. I found no major or minor mathematical issues. The argument covers arbitrary real objection rates and arbitrary real countercoalition masses.
For each type with \(q_t>0\), the increment \(d_t=y_t-x_t\) is strictly positive. When \(q_t=0\), every feasible overlap has \(h_t=0\), so assigning \(d_t=0\) introduces no error.
The minimum required payment for fixed \(r,h\) is exactly
\( \sum_t x_tr_t+\sum_t d_th_t \).
Since all \(d_t\geq0\), choosing each overlap at its lower bound minimizes payment. These lower bounds are feasible: for masses in the prescribed box,
\( \max\{0,q_t+r_t-\mu_t\}\leq\min\{q_t,r_t\} \).
Consequently, the criterion \(F_{q,y}(r)\geq0\) is necessary. Its sufficiency also holds: assign the minimum rates and distribute any remaining surplus to a positive-mass piece. The requirement \(r_b>0\) guarantees that such a piece exists. Zero-mass pieces cause no difficulty.
The perturbation \(r^\varepsilon=(1-\varepsilon)r^0+\varepsilon s\) remains in the mass box. Because \(s_a=0\), \(s_b=\mu_b\), and all masses are positive, every \(0<\varepsilon<1\) gives \(r^\varepsilon_a<\mu_a\) and \(r^\varepsilon_b>0\).
The function \(F_{q,y}\) is continuous. Thus strictly positive surplus at any point of the closed box persists at sufficiently small admissible perturbations. The proof correctly uses strictly positive surplus here; it does not incorrectly extend this argument to zero surplus.
The objection budget gives
\(v(q)-\sum_t x_tq_t=\sum_t d_tq_t\).
Substitution into \(F_{q,y}(q)\) yields the stated identity
\(F_{q,y}(q)=\sum_t d_t\min\{q_t,\mu_t-q_t\}\).
All summands are nonnegative. A coordinate satisfying \(0<q_t<\mu_t\) has both \(d_t>0\) and \(\min\{q_t,\mu_t-q_t\}>0\), making the total strictly positive. The preceding perturbation argument therefore applies.
This establishes the exact reduction claimed: any objection without a counterobjection must consist of entire types.
The source is the decision problem asking whether a simple graph contains an independent set of size at least \(k\). Its equivalence to Clique on the complement is valid, and the cited NP-completeness theorem applies to explicitly represented finite graphs. [Karp’s paper](https://doi.org/10.1007/978-1-4684-2001-2_9) supplies the standard source hardness.
Adding \(p\) isolated vertices increases the independence number by exactly \(p\), so replacing \(k\) by \(k+p\) preserves both yes and no instances. Padding to the next power of two enlarges the graph by only a constant factor and preserves \(1\leq k\leq n\).
The support size is \(N=n+2\), and every mass is the positive dyadic rational \(1/N\). Their sum is one. The matrix \(W=N^2H\) is symmetric and rational, with positive diagonal entries. Every specified payoff is strictly positive.
The normalization \(u_t=Nq_t\) correctly cancels the factor \(N^2\) in \(W\). The diagonal and off-diagonal contributions to the displayed worth formula have the correct coefficients, including the factor \(1/2\) in the original definition.
The efficiency calculation checks out:
\(v(\mu)=N(A+1)-M+n-M|E(G)|\) and
\(\sum_t\mu_tx_t=N(A+1)-A+k\).
Their difference is zero because \(M=n+1\) and \(A-k=M|E(G)|+1\).
The formula for the excess of a coalition consisting of entire types also follows correctly from these coefficients and payoffs.
Once an objection consists of entire types, its target is outside its support and its objecting type is inside.
For a graph-vertex target, the coalition consisting of that entire target type has worth and required payment both \(A+1\). For target \(\alpha\), these amounts are \(A+1\) and \(1\). Each coalition has zero overlap, includes the target, and excludes the objecting type. Therefore each is an admissible countercoalition.
For target \(\beta\), an objection must have strictly positive excess. If \(\alpha\) were absent, its excess would be \(-Me(U)\leq0\), which excludes an objection.
If \(\alpha\) is present and \(U\neq\varnothing\), the budget identity and strictly positive increments give \(\delta_\alpha<A\). The surplus at the coalition consisting only of type \(\alpha\) is then \(A-\delta_\alpha>0\). The perturbation argument applies even when \(\alpha\) itself is the objecting type, so no countercoalition restriction is being overlooked.
The only remaining support is therefore \(\{\alpha\}\), with objecting type \(\alpha\) and target \(\beta\). Its budget fixes the relevant rate to \(y_\alpha=N(A+1)>x_\alpha\). Rates on absent types are irrelevant.
The formula for \(F(s)\) correctly charges type \(\alpha\) at the objection rate and all other types at their imputation rates.
When an independent set \(U\) satisfies \(|U|\geq k\), the specified Boolean countercoalition has \(s_\beta=1\), \(s_\alpha=0\), and surplus \(|U|-k\geq0\). It satisfies both strict countercoalition restrictions, including the equality case \(|U|=k\).
When the independence number is smaller than \(k\), the Boolean-vector bounds are correct:
Hence \(F(\eta)\leq-\eta_\beta\) at every Boolean vector.
The independent Bernoulli calculation is exact: distinct-coordinate products have expectations \(s_ts_u\), while Boolean diagonal terms satisfy \(\eta_t^2-\eta_t=0\). This gives precisely
\(F(s)=\mathbb E[F(\eta)]-(A+1)\sum_t s_t(1-s_t)\).
Since \(A+1>0\), it follows that \(F(s)\leq-s_\beta<0\) for every admissible countercoalition. This excludes all real countercoalitions, including those arbitrarily close to the boundary \(s_\beta=0\).
The proof establishes a yes-to-yes equivalence: an independent set of size at least \(k\) exists exactly when the constructed imputation belongs to the bargaining set. Thus it proves hardness of membership itself.
After padding, \(\tau=N=O(n)\). The bound \(A=O(n^3)\) is correct, and multiplying matrix entries by \(N^2\) still leaves every coefficient with \(O(\log n)\) bits. The dense output length \(O(n^2\log n)\) and polynomial construction time are valid. No separate candidate parameter is used.
The claimed NP-hardness follows. The proof does not claim an NP upper bound or NP-completeness, so no additional membership certificate argument is required.
No repair or additional 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.