Answer: Blocking-coalition existence is \(\mathrm{NP}\)-complete, and deciding that \(\Pi\) has no blocking coalition is \(\mathrm{coNP}\)-complete, even at interaction-graph treewidth at most \(2\) with \(k=2\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateChecking CORE MEMBERSHIP for hedonic coali- tion nets is coNP-complete, even if the treewidth of the agent graph is at most 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types \(T\), rational masses \(\mu_t>0\) summing to \(1\), type-level Boolean hedonic nets, and a proposed partition \(\Pi\) represented by block masses \(z_t^r\), decide whether \(\Pi\) has no blocking coalition. A coalition has support \(S\subseteq T\); type \(t\)’s utility \(u_t(S)\) depends on which types have positive mass in it. Define \(A_t^\Pi(S)=\sum_{r:\,u_t(S)>u_t(S_r)}z_t^r\), where \(S_r=\{t:z_t^r>0\}\). A blocking coalition with support \(S\) exists exactly when \(A_t^\Pi(S)>0\) for every \(t\in S\), since it can recruit positive mass from each eligible block.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types.
Each type \(t\) has a finite rule set \(R_t\) of pairs \((\varphi,\beta)\), where \(\varphi\) is a propositional formula over type-presence variables and \(\beta\) is a signed binary rational. For \(t\in S\), define \(u_t(S)=\sum_{(\varphi,\beta)\in R_t:S\models\varphi}\beta\), interpreting precisely the types in \(S\) as true; an empty rule set gives zero utility.
The type interaction graph has vertex set \(T\): each rule belonging to \(t\) makes \(\{t\}\cup\operatorname{vars}(\varphi)\) a clique. Require this graph to have treewidth at most \(2\).
The proposed partition \(\Pi\) consists of \(k\geq1\) nonempty blocks, represented by binary rational entries \(z_t^r\geq0\) with \(\sum_{r=1}^k z_t^r=\mu_t\); put \(S_r=\{t:z_t^r>0\}\).
Mass is divisible. A blocking coalition recruits positive mass of every type in a nonempty support \(S\subseteq T\), and every recruited member must strictly prefer \(S\) to its current block. Equivalently, it exists with support \(S\) precisely when \(A_t^\Pi(S)=\sum_{r:u_t(S)>u_t(S_r)}z_t^r>0\) for every \(t\in S\). Ties do not permit blocking.
Let \(m=\sum_t|R_t|\) and let \(L\) be the total input bit length, including formulas, weights, masses, and block entries. State running times in \(m,\tau,k,L\).
Is deciding whether \(\Pi\) has no blocking coalition in \(\mathrm{P}\), or is the complementary problem of finding whether a blocking coalition exists \(\mathrm{NP}\)-hard?
For finite agents, core membership is \(\mathrm{coNP}\)-complete even at interaction-graph treewidth \(2\); blocking-coalition existence is \(\mathrm{NP}\)-complete. With bounded treewidth and unary integer rule weights, discrete core membership is polynomial-time solvable. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2009c.pdf)
No result settling exactly this divisible-mass, support-dependent problem was located in the literature search.
Blocking-coalition existence is \(\mathrm{NP}\)-complete, and deciding that \(\Pi\) has no blocking coalition is \(\mathrm{coNP}\)-complete, even when the interaction graph has treewidth at most \(2\), \(k=2\), all masses are equal, and each type places its entire mass in one proposed block.
Consequently, a polynomial-time algorithm for either decision problem would imply \(\mathrm{P}=\mathrm{NP}\).
The cited [Elkind–Wooldridge paper, Theorem 4](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2009c.pdf) establishes the finite-agent hardness result. Below is a direct reduction for the specified divisible-mass model.
For each type \(t\), define
\[ b_t=\min_{r:z_t^r>0}u_t(S_r). \]
This minimum exists because \(\sum_r z_t^r=\mu_t>0\).
For every support \(S\) containing \(t\), the summands defining \(A_t^\Pi(S)\) are nonnegative. Therefore,
\[ A_t^\Pi(S)>0 \quad\Longleftrightarrow\quad \exists r:\ z_t^r>0\ \text{and}\ u_t(S)>u_t(S_r) \quad\Longleftrightarrow\quad u_t(S)>b_t. \]
Thus a blocking coalition exists exactly when there is a nonempty \(S\subseteq T\) satisfying \(u_t(S)>b_t\) for every \(t\in S\).
For sufficiency, choose for each \(t\in S\) a block witnessing the strict inequality and recruit half its positive entry \(z_t^r\). Every recruited member strictly improves, and the recruited support is exactly \(S\). Hence no additional certificate describing recruited masses is necessary.
A certificate is the \(\tau\)-bit characteristic vector of a nonempty support \(S\). Compute the thresholds \(b_t\), evaluate all rules on \(S\), and check \(u_t(S)>b_t\) for every selected type.
These computations use exact rational arithmetic of polynomial bit complexity. Explicitly, let \(D\) be the product of the denominators of all rule weights, with \(D=1\) when there are no rules. Its bit length is \(O(L)\). Multiplying every utility by \(D>0\) preserves all strict comparisons. The resulting integer weights and their sums also have \(O(L)\) bits: their numerators, denominator products, and the number of summands are bounded by the input encoding.
Using schoolbook arithmetic gives the following conservative bounds:
Formula evaluation is included: evaluating every formula once takes time linear in their total encoded length. The verification bound proves membership in \(\mathrm{NP}\).
Take positive integers \(a_1,\ldots,a_n\), encoded in binary, with \(\sum_{i=1}^n a_i=2B\). The question is whether some index set \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=B\).
This even-total restriction remains \(\mathrm{NP}\)-complete: odd-total instances are automatically negative and can be replaced by the fixed negative instance consisting of \(1,3\). Positivity and nonemptiness give \(B\geq1\).
Introduce \(T=\{x_1,\ldots,x_n,p,q\}\), so \(\tau=n+2\), and set \(\mu_t=1/(n+2)\) for every type.
The rules are
\[ R_{x_i}=\{(p,1)\}, \]
\[ R_p=\{(q,1-B)\}\cup\{(q\land x_i,a_i):1\leq i\leq n\}, \]
\[ R_q=\{(p,B+1)\}\cup\{(p\land x_i,-a_i):1\leq i\leq n\}. \]
Use two proposed blocks with supports \(S_1=\{p\}\) and \(S_2=\{q,x_1,\ldots,x_n\}\). Assign each type its entire mass in its indicated block and zero in the other.
Both blocks are nonempty, and every row of block entries sums to its positive prescribed mass.
Every type’s current utility is zero:
Consequently, \(b_t=0\) for every type \(t\).
Each rule contributes edges only within some triple \(\{p,q,x_i\}\). In particular, the rules involving \(q\land x_i\) or \(p\land x_i\), together with their owners, make precisely these triples cliques.
Arrange the bags \(B_i=\{p,q,x_i\}\), for \(1\leq i\leq n\), along a path.
Every vertex and edge is covered. The bags containing either \(p\) or \(q\) form the entire path, and each \(x_i\) occurs in exactly one bag. Thus the running-intersection condition holds. Every bag has size \(3\), proving treewidth at most \(2\).
If \(p\notin S\), every selected item type \(x_i\) has utility zero, and \(q\), if selected, also has utility zero. Since \(S\) is nonempty, at least one selected type fails to strictly improve. Therefore every blocking support contains \(p\).
If \(p\in S\) but \(q\notin S\), no rule of \(p\) fires, so \(u_p(S)=0=b_p\). Therefore every blocking support also contains \(q\).
It follows that every possible blocking support has the form \(S=\{p,q\}\cup\{x_i:i\in I\}\).
Write \(s=\sum_{i\in I}a_i\). On this support,
\[ u_p(S)=1-B+s, \qquad u_q(S)=B+1-s. \]
Each selected item type has utility \(1\), so it strictly improves.
Type \(p\) strictly improves exactly when \(s>B-1\), which, because \(s\) and \(B\) are integers, is equivalent to \(s\geq B\).
Type \(q\) strictly improves exactly when \(s<B+1\), equivalently \(s\leq B\).
Both inequalities hold exactly when \(s=B\). Thus a blocking support exists if and only if the original \(\mathrm{PARTITION}\) instance is positive.
Divisibility cannot bypass this equality: the values above depend on which item types have positive recruited mass, regardless of the amount recruited from each.
The construction has \(\tau=n+2\), \(k=2\), and \(m=3n+2\). All weights are binary integers, all formulas have at most two variables, and all masses and block entries have polynomial-length rational encodings.
If the source instance has bit length \(h\), the constructed input has \(L=O\bigl(h+n\log(n+2)\bigr)\). Computing \(B\) and writing the instance take polynomial time. This is therefore a polynomial-time many-one reduction.
Sections 3–4 prove \(\mathrm{NP}\)-hardness under the required treewidth restriction. Section 2 proves membership in \(\mathrm{NP}\). Blocking-coalition existence is therefore \(\mathrm{NP}\)-complete, and its complement is \(\mathrm{coNP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem. The direct reduction is correct, respects the treewidth restriction, and establishes \(\mathrm{NP}\)-completeness of blocking-coalition existence and \(\mathrm{coNP}\)-completeness of its complement. I found no major or minor mathematical issues.
For each type \(t\), the set of blocks with \(z_t^r>0\) is nonempty because its entries sum to \(\mu_t>0\). Thus \(b_t\) is well-defined and attained.
The sum defining \(A_t^\Pi(S)\) consists of nonnegative block entries. It is positive exactly when at least one positive entry belongs to a block whose utility is strictly below \(u_t(S)\). Taking the minimum over occupied blocks therefore gives exactly the claimed equivalence
\[
A_t^\Pi(S)>0\quad\Longleftrightarrow\quad u_t(S)>b_t.
\]
The recruitment argument is also valid. Half of each selected positive entry is available positive mass, and all members recruited from that entry have the same current-block utility. Recruitment choices for distinct types do not compete for the same mass. The recruited support is precisely \(S\), so the utility calculations remain applicable.
Strict inequalities are preserved throughout; ties never qualify.
A nonempty support has a certificate of length \(\tau\). Formula evaluation under that support determines every relevant utility without needing recruited masses.
The denominator product \(D\) has bit length bounded by the total encoded denominator length, hence \(O(L)\). Each scaled weight is an integer with \(O(L)\) bits. Summing at most \(m\) such integers adds at most \(O(\log(m+1))\) bits, which is absorbed into \(O(L)\).
Threshold computation evaluates rules on each proposed block and then takes minima only over blocks occupied by the corresponding type. The stated preprocessing bound covers these operations, construction of block supports, and common-denominator arithmetic. The verification and exhaustive-search bounds likewise cover their stated computations:
\[
O\bigl(k(L+m+\tau)L^2\bigr),\qquad
O\bigl((L+m+\tau)L^2\bigr),
\]
and
\[
O\bigl((k+2^\tau)(L+m+\tau)L^2\bigr).
\]
These are conservative polynomial bit-operation bounds where claimed. The empty-rule case is handled by \(D=1\) and zero utilities. Membership in \(\mathrm{NP}\) follows.
The reduction uses the standard binary-encoded, positive-integer \(\mathrm{PARTITION}\) problem. The restriction to even total is justified: odd-total instances are negative, and the replacement instance \(1,3\) is also negative because no subset sums to \(2\).
The constructed society satisfies all required input conditions:
The rule count \(m=3n+2\) is correct.
Each rule’s owner together with its formula variables lies within a bag \(\{p,q,x_i\}\). Consequently, every induced edge is covered by the proposed bags.
The bags form a path. Both \(p\) and \(q\) occur throughout that path, while each \(x_i\) occurs in one bag. Vertex coverage, edge coverage, and the running-intersection property all hold. The bags have size \(3\), so the decomposition has width \(2\).
Nonemptiness of the source list ensures at least one bag exists.
The exclusion of blocking supports without \(p\) is valid: every selected type then has utility zero. If \(p\) is selected but \(q\) is absent, \(p\) has utility zero. Neither situation permits strict improvement for every selected type.
Thus every blocking support must have the stated form. On such a support, direct rule evaluation gives
\[
u_p(S)=1-B+s,\qquad u_q(S)=B+1-s,
\]
where \(s=\sum_{i\in I}a_i\). Every selected item type has utility \(1\).
Because \(s\) and \(B\) are integers, the two strict improvement conditions are equivalent to \(s\geq B\) and \(s\leq B\), respectively. They therefore hold together exactly when \(s=B\). This establishes both directions of the reduction.
Divisibility creates no exception: utilities depend solely on the recruited support. The empty item subset is also accounted for; since \(B\geq1\), it cannot satisfy the required equality.
The weights \(a_i\) occur a constant number of times, and the two weights involving \(B\) have polynomial bit length. Type identifiers and rational masses account for the stated additional \(O(n\log(n+2))\) encoding cost. The construction is polynomial-time.
The cited finite-agent theorem is accurately described: Theorem 4 establishes core-membership \(\mathrm{coNP}\)-completeness at agent-graph treewidth at most \(2\). It serves as background; the divisible-mass conclusion follows independently from the audited reduction. [Elkind–Wooldridge, Theorem 4](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2009c.pdf)
No additional clarification or repair 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.