Answer: Every \(R_t\) exists. The equality \(R_t=I_t\) holds for positive-weight targets but fails in general for zero-weight targets, including cases with finite rates. Computing all rates while distinguishing \(+\infty\) is \(\mathrm{NP}\)-hard; deciding whether a designated rate is finite is \(\mathrm{NP}\)-complete.
Proposition 1 — class: hardness
Given a finite type graph \(H=(T,F)\), rational masses \(\mu_t>0\), weights \(w_t\), and quota \(q\), determine for each type \(t\) the exponential rate of its normalized Banzhaf index in the denominator-compatible finite blow-ups, where type \(s\) has \(k\mu_s\) agents and the quota is \(\lceil kq\rceil\). In particular, establish whether the rate equals the infimum of \(\sum_{s\in T}\mu_s D(x_s/\mu_s\|1/2)\), with \(D(p\|1/2)=p\ln(2p)+(1-p)\ln(2(1-p))\), over masses \(0\le x_s\le\mu_s\) and active supports \(A\subseteq T\), such that each component \(D\) of \(H[A]\) has \(\sum_{s\in D}w_sx_s\le q\), while the component containing \(t\) after adding the target type reaches quota. Allow \(A\) to include zero-mass bridge types, and report infinity when no pivotal configuration is feasible.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_s\), normalized by \(\sum_s\mu_s=1\). Here \(\tau\) is the support size, not the number of possible types. Input also includes a simple undirected graph \(H=(T,F)\), binary-encoded integer weights \(w_s\ge0\), and a rational quota satisfying \(\frac12\sum_s\mu_sw_s<q\le\sum_s\mu_sw_s\).
For each positive integer \(k\) with all \(k\mu_s\) integral, replace type \(s\) by a clique of \(k\mu_s\) agents, each of weight \(w_s\); join two distinct type cliques completely exactly when their types are adjacent in \(H\). Set the quota to \(Q_k=\lceil kq\rceil\). A coalition wins exactly when one of its induced connected components has weight at least \(Q_k\).
For one designated agent of type \(t\), let \(B_t(k)\) be its probability of changing a losing coalition into a winning one when every other agent is included independently with probability \(1/2\). This is the normalized Banzhaf index used here. Its proposed rate is \(R_t=\lim_{k\to\infty}-k^{-1}\ln B_t(k)\), along the admissible integers, with \(-\ln0=+\infty\).
Define \(I_t\) as the infimum of \(\sum_s\mu_sD(x_s/\mu_s\|1/2)\), where \(D(p\|1/2)=p\ln(2p)+(1-p)\ln(2(1-p))\), with \(0\ln0=0\). The infimum ranges over \(A\subseteq T\) and \(0\le x_s\le\mu_s\), with \(x_s=0\) outside \(A\), every component \(C\) of \(H[A]\) satisfying \(\sum_{s\in C}w_sx_s\le q\), and the component \(C_t\) containing \(t\) in \(H[A\cup\{t\}]\) satisfying \(\sum_{s\in C_t}w_sx_s\ge q\). Types in \(A\) may have zero selected mass; the added target agent contributes zero mass in these constraints. An empty feasible set gives \(I_t=+\infty\).
Do the rates \(R_t\) exist for every input, and do they equal \(I_t\)?
Is computing all rates to additive error \(\varepsilon\), while distinguishing \(+\infty\), possible in polynomial time in \(m=|F|\), \(\tau\), the input bit length \(L\), and \(\log(1/\varepsilon)\), or is this problem \(\mathrm{NP}\)-hard?
For finite graph-restricted weighted voting games, computing the Banzhaf and Shapley–Shubik indices is \(\#\mathrm{P}\)-complete after their respective counting normalizations; bounded-treewidth instances admit a pseudo-polynomial algorithm. [Source](https://www.ijcai.org/Proceedings/15/Papers/095.pdf)
No result settling this specific blow-up rate problem was identified in the literature search.
For the stated input class:
The zero-weight case is essential to the hardness result below.
Write \(W(S)=\sum_{s\in S}\mu_sw_s\), \(\mu(S)=\sum_{s\in S}\mu_s\), and \(W=W(T)\). The quota hypothesis gives \(0<W/2<q\le W\).
For a coalition, let its occupied support be the set of types represented by at least one selected agent. Because type cliques and cross-type joins are complete, its connected components correspond exactly to the components of the graph induced by its occupied support.
For any \(S\subseteq T\), define
\( J(S)=\inf\left\{\sum_{s\in S}\mu_sD(x_s/\mu_s\|1/2):0\le x_s\le\mu_s,\ \sum_{s\in S}w_sx_s\ge q\right\}. \)
We use the convention \(J(S)=+\infty\) when the constraint is infeasible.
If \(W(S)<q\), then \(J(S)=+\infty\).
Suppose \(q<W(S)\). There is a unique \(\lambda>0\) satisfying
\( \sum_{s\in S}\mu_sw_s\frac{e^{\lambda w_s}}{1+e^{\lambda w_s}}=q. \)
Indeed, the left side is continuous and strictly increasing: its derivative is
\( \sum_{s\in S}\mu_sw_s^2\frac{e^{\lambda w_s}}{(1+e^{\lambda w_s})^2}>0. \)
Its value at zero is \(W(S)/2<q\), and its limit is \(W(S)>q\).
Set \(p_s^\ast=e^{\lambda w_s}/(1+e^{\lambda w_s})\) and \(x_s^\ast=\mu_sp_s^\ast\). Convexity of binary relative entropy gives, for every \(p\in[0,1]\),
\( D(p\|1/2)\ge \lambda w_sp-\ln\!\left(\frac{1+e^{\lambda w_s}}2\right), \)
with equality at \(p=p_s^\ast\). This follows by minimizing the difference: its derivative on the interior is \(\ln(p/(1-p))-\lambda w_s\), and its second derivative is positive.
Consequently,
\( J(S)=\lambda q-\sum_{s\in S}\mu_s\ln\!\left(\frac{1+e^{\lambda w_s}}2\right), \)
and \(x^\ast\) is a minimizer. Every coordinate is strictly between zero and its upper bound.
If \(q=W(S)\), feasibility forces \(x_s=\mu_s\) for every positive-weight type. Zero-weight coordinates minimize their entropy at \(\mu_s/2\). Hence
\( J(S)=\sum_{\substack{s\in S\\w_s>0}}\mu_s\ln2. \)
In both finite cases, the specified minimizer has positive coordinates and weighted sum exactly \(q\).
Let \(N_s(k)=k\mu_s-\mathbf1_{\{s=t\}}\) be the number of available agents of type \(s\). For selected counts \(n_s(k)\), their joint probability is
\( P_k(n)=\prod_{s\in T}2^{-N_s(k)}\binom{N_s(k)}{n_s(k)}. \)
If \(n_s(k)/k\to x_s\), then
\( -\frac1k\ln P_k(n)\longrightarrow \Phi(x):=\sum_{s\in T}\mu_sD(x_s/\mu_s\|1/2). \)
To justify this, for \(0\le j\le N\) the elementary binomial bounds give
\( \frac{e^{-ND(j/N\|1/2)}}{N+1} \le 2^{-N}\binom Nj \le e^{-ND(j/N\|1/2)}. \)
The logarithmic prefactors divided by \(k\) vanish, and continuity of \(D\), including at its endpoints, gives the asserted limit.
We also need a tail bound with no designated-agent deletion. For independent \(Z_s\sim\operatorname{Bin}(k\mu_s,1/2)\), whenever \(J(S)\) is finite,
\( \Pr\!\left(\sum_{s\in S}w_sZ_s\ge Q_k\right)\le e^{-kJ(S)}. \)
For \(q<W(S)\), apply the exponential Markov inequality with the \(\lambda\) above and use \(Q_k\ge kq\). If \(q=W(S)\), then \(kq\) is integral, and reaching quota requires selecting every positive-weight agent in \(S\). Its probability is exactly \(e^{-kJ(S)}\).
Let \(U_t\) be the connected component of \(H\) containing \(t\). Then, for every target, including zero-weight targets,
\( \boxed{I_t=J(U_t).} \)
Proof. For any feasible pair in the definition of \(I_t\), the component \(C_t\) is contained in \(U_t\). Nonnegative weights therefore imply
\( \sum_{s\in U_t}w_sx_s\ge \sum_{s\in C_t}w_sx_s\ge q. \)
The entropy contribution on \(U_t\) is at least \(J(U_t)\), and all remaining contributions are nonnegative. Thus \(I_t\ge J(U_t)\).
If \(W(U_t)<q\), feasibility is impossible.
Otherwise, take \(A=T\), use the minimizer of \(J(U_t)\) on \(U_t\), and set \(x_s=\mu_s/2\) outside \(U_t\). The component \(U_t\) has selected weight exactly \(q\). Every other component \(V\) has selected weight \(W(V)/2\le W/2<q\). This is feasible and has entropy \(J(U_t)\), proving equality. \(\square\)
Thus the proposed quantity depends on the graph only through the full component containing the target.
Suppose \(w_t>0\). Then
\( \boxed{R_t=J(U_t)=I_t.} \)
We prove existence as well as equality.
If \(W(U_t)<q\), even the full component containing the added target has weight below \(Q_k\). Adding that agent cannot create a winning component, so \(B_t(k)=0\) for every admissible \(k\).
Now suppose \(W(U_t)\ge q\).
If the target is pivotal, the total selected weight in \(U_t\), before its addition, is at least \(Q_k-w_t\).
When \(q<W(U_t)\), use the optimizing \(\lambda\) from Section 1. Put \(a_s=\ln((1+e^{\lambda w_s})/2)\). The exponential Markov inequality gives
\( B_t(k)\le \exp\!\left(-\lambda(Q_k-w_t)+k\sum_{s\in U_t}\mu_sa_s-a_t\right) \le e^{-kJ(U_t)}e^{\lambda w_t-a_t} \le 2e^{-kJ(U_t)}. \)
The final inequality follows from \(e^{\lambda w_t-a_t}=2e^{\lambda w_t}/(1+e^{\lambda w_t})\le2\).
When \(q=W(U_t)\), the maximum available weight before adding the target is \(kq-w_t\). The necessary threshold condition forces every available positive-weight agent in \(U_t\) to be selected. Its probability is \(2e^{-kJ(U_t)}\).
Therefore,
\( \liminf_k-\frac1k\ln B_t(k)\ge J(U_t). \)
First suppose \(q<W(U_t)\), and let \(x^\ast\) be its entropy minimizer. For \(s\in U_t\setminus\{t\}\), choose counts \(n_s(k)\) with \(n_s(k)/k\to x_s^\ast\). Write \(b_k=\sum_{s\in U_t\setminus\{t\}}w_sn_s(k)\), and choose
\( n_t(k)=\left\lceil\frac{Q_k-b_k}{w_t}\right\rceil-1. \)
This ensures
\( b_k+w_tn_t(k)<Q_k\le b_k+w_t(n_t(k)+1). \)
Moreover, \(n_t(k)/k\to x_t^\ast\). Since \(0<x_t^\ast<\mu_t\), this count lies between zero and \(k\mu_t-1\) for all sufficiently large admissible \(k\).
Every type in \(U_t\) is occupied for sufficiently large \(k\). Its selected agents therefore form one connected component, which loses before the addition and wins afterward.
Outside \(U_t\), choose counts approaching \(\mu_s/2\). Every other full graph component \(V\) has capacity
\( W(V)\le W-W(U_t)\le W-q<q, \)
so it cannot win, regardless of its selected counts. The constructed count vector is pivotal, and its probability exponent tends to \(J(U_t)\).
Finally, suppose \(q=W(U_t)\). Select every available positive-weight agent in \(U_t\), and select approximately half of each zero-weight type. For sufficiently large \(k\), all types in \(U_t\) are occupied. Its weights before and after addition are respectively \(kq-w_t\) and \(kq=Q_k\). Choose approximately half of every outside type. This is again pivotal, with probability exponent \(J(U_t)\).
Thus the matching upper limit holds. These constructions work for every sufficiently large admissible \(k\), so they also rule out any lattice-induced failure of convergence.
Suppose \(w_t=0\).
If another agent of type \(t\) is selected, adding the target changes neither connectivity nor component weights: the existing type-\(t\) clique already supplies all its connections. Therefore a pivotal coalition must contain no other type-\(t\) agent.
For \(A\subseteq T\setminus\{t\}\), let \(\mathcal C_t(A)\) be the components of \(H[A]\) containing a neighbor of \(t\), and put
\( S_t(A)=\bigcup_{C\in\mathcal C_t(A)}C. \)
These are precisely the components merged when the target is added.
Call \(A\) admissible for merging if:
Let \(\mathcal G_t\) denote this finite family. The correct formula is
\( \boxed{ R_t=\min_{A\in\mathcal G_t} \left[\mu(T\setminus A)\ln2+J(S_t(A))\right], } \)
where an empty minimum is \(+\infty\).
Consider a pivotal coalition with occupied support \(A\). The merged components have total selected weight at least \(Q_k\), so their capacity is at least \(q\).
At least two of these components must have positive selected weight. Otherwise one component already carries the entire post-addition weight and would already win. Hence \(A\in\mathcal G_t\).
For a fixed such support \(A\), the probability that every available agent outside \(A\) is absent is
\( 2^{-(k\mu(T\setminus A)-1)} =2e^{-k\mu(T\setminus A)\ln2}. \)
The subtraction of one accounts for the designated agent, which is not sampled. Independently, the selected weight in \(S_t(A)\) must reach quota. Section 1 consequently gives
\( \Pr(\text{pivotal with support }A) \le 2e^{-k[\mu(T\setminus A)\ln2+J(S_t(A))]}. \)
If \(\mathcal G_t\) is empty, no pivotal coalition exists for any \(k\).
Otherwise, writing the claimed minimum as \(\rho_t\) and summing over at most \(2^{\tau-1}\) supports gives
\( B_t(k)\le2^\tau e^{-k\rho_t}, \qquad \liminf_k-\frac1k\ln B_t(k)\ge\rho_t. \)
Fix \(A\in\mathcal G_t\), and abbreviate \(S=S_t(A)\).
On \(S\), use the entropy minimizer of \(J(S)\); on \(A\setminus S\), set \(x_s=\mu_s/2\); outside \(A\), set \(x_s=0\). Every coordinate in \(A\) is positive.
The total selected weight on \(S\) is \(q\). Each joined component has selected weight strictly below \(q\): there are at least two positive-capacity components, and the minimizer assigns positive selected weight to each of them.
Every nonjoined component \(C\) satisfies
\( W(C)\le W-W(S)\le W-q<q. \)
Now choose \(n_s(k)=\lceil kx_s\rceil\) for \(s\in A\), and zero counts outside \(A\). These counts respect their capacities because \(k\mu_s\) is integral and \(x_s\le\mu_s\). For sufficiently large \(k\), their occupied support is exactly \(A\).
Rounding upward ensures that the merged weight is at least \(kq\), hence at least \(Q_k\). Each pre-addition component remains below quota for sufficiently large \(k\), because its limiting selected weight is strictly below \(q\). Thus the count vector is pivotal.
Its probability exponent tends to
\( \Phi(x)=\mu(T\setminus A)\ln2+J(S_t(A)). \)
Choosing a minimizing support proves the matching upper limit. This proves the formula and existence of every zero-weight target’s rate, including the boundary case \(q=W(S)\).
There is an immediate dummy counterexample: in a complete type graph, a zero-weight target cannot change connectivity or weight, although \(I_t\) can be finite.
More substantially, take the three-type path \(a-t-b\), with
\( \mu_a=\mu_b=\frac14,\qquad \mu_t=\frac12,\qquad w_a=w_b=1,\qquad w_t=0,\qquad q=\frac38. \)
Here \(W=1/2\), so the quota hypothesis holds.
Section 2 gives
\( I_t=\frac12D(3/4\|1/2). \)
For the target to be pivotal, every other type-\(t\) agent must be absent. Without type \(t\), the two endpoint cliques are separate, and neither can reach quota because each has capacity \(1/4<3/8\). Adding the target makes their combined weight decisive. Hence, exactly,
\( B_t(k)= 2^{-(k/2-1)} \Pr\!\left(\operatorname{Bin}(k/2,1/2)\ge\lceil3k/8\rceil\right). \)
The zero-target formula yields
\( R_t=\frac12\ln2+\frac12D(3/4\|1/2)>I_t. \)
Thus both quantities are finite, and the target is genuinely pivotal.
In fact, whenever \(w_t=0\) and \(I_t\) is finite, the compulsory absence of the other type-\(t\) agents gives the general bound
\( R_t\ge \mu_t\ln2+I_t>I_t. \)
To verify it directly, pivotality implies both their absence and total selected weight at least \(Q_k\) in \(U_t\). These events are independent because type \(t\) has weight zero. Their probability is at most \(2e^{-k[\mu_t\ln2+J(U_t)]}\).
Consequently, equality holds precisely when \(w_t>0\) or \(W(U_t)<q\); in the latter case both quantities are \(+\infty\).
We prove hardness already for distinguishing finite rates from \(+\infty\), with:
Use monotone satisfiability: each clause consists either entirely of positive literals or entirely of negative literals. Monotone three-literal satisfiability is \(\mathrm{NP}\)-complete even when each clause uses three distinct variables and every variable occurs twice positively and twice negatively. These stronger restrictions are established in [Döcker’s paper](https://arxiv.org/abs/1912.08032). The construction below accepts every instance of that restricted class.
Let the formula have \(n\) variables and \(c\) clauses.
Create the following types:
Add edges \(ta,tb\), and, for every variable, add the path edges
\( au_i,\quad u_iv_i,\quad v_ib. \)
For a positive clause, join its clause type to the \(u_i\) corresponding to its variables. For a negative clause, join its clause type to the corresponding \(v_i\). Add no other edges.
Assign weight one to \(a,b\) and all clause types; assign weight zero to all other types. Let \(h=c+2\), so \(\tau=h+2n+1\).
Choose a power of two \(D\) with \(\tau\le D<2\tau\), and assign
\( \mu_s=\frac1D\quad(s\ne t), \qquad \mu_t=1-\frac{h+2n}{D}. \)
All masses are positive dyadic rationals and sum to one. Set
\( q=W=\frac hD. \)
The quota hypothesis holds. The graph, masses, weights, and quota have polynomial encoding length.
Suppose a pivotal coalition exists.
Since \(Q_k=kq\) equals the entire society’s weight, winning requires every positive-weight agent to belong to one connected component. Thus every agent of types \(a,b,d_j\) must be selected.
No other type-\(t\) agent can be selected. Since the target’s only neighbors are \(a,b\), these roots must lie in different pre-addition components; otherwise adding the zero-weight target changes nothing. Every clause type must belong to one of those two components.
Both \(u_i\) and \(v_i\) cannot be occupied, because the path \(a-u_i-v_i-b\) would connect the roots.
Define a truth assignment by setting a variable true when \(u_i\) is occupied and false when \(v_i\) is occupied. If neither is occupied, assign it arbitrarily. This is consistent.
A positive clause type can connect to a root only through an occupied \(u_i\), so that clause has a true variable. A negative clause type similarly requires an occupied \(v_i\), so it has a false variable. Every clause is satisfied.
If the formula is unsatisfiable, therefore, \(B_t(k)=0\) for every admissible \(k\), and \(R_t=+\infty\).
Conversely, take a satisfying assignment.
Select every positive-weight agent. For each variable, occupy \(u_i\) when it is true and \(v_i\) when it is false, leaving the opposite type empty. Leave every other type-\(t\) agent absent.
Every positive clause connects to \(a\), and every negative clause connects to \(b\). The roots remain disconnected because each variable path has an absent internal type.
Both root components lose: each omits the other root’s positive weight. Adding the target joins them and collects all positive weight, reaching quota. This construction works for every admissible \(k\).
It also supplies a merging-admissible support, so Section 4 proves that the rate is finite.
Indeed, its value is explicit. Any merging-admissible support must retain all \(h\) positive-weight types and delete at least one type from every variable pair. A satisfying assignment achieves exactly those \(n\) deletions. Therefore
\( R_t= \left(\mu_t+\frac{h+n}{D}\right)\ln2 = \left(1-\frac nD\right)\ln2 \)
for satisfiable formulas.
The reduction establishes
\( \text{formula satisfiable} \quad\Longleftrightarrow\quad R_t<+\infty. \)
The finiteness decision is also in \(\mathrm{NP}\). For positive-weight targets, Section 3 reduces it to checking \(W(U_t)\ge q\). For zero-weight targets, a support \(A\in\mathcal G_t\) is a certificate: its components, capacities, and adjacency to \(t\) can all be checked in polynomial time.
Hence deciding whether a designated rate is finite is \(\mathrm{NP}\)-complete. An algorithm computing all rates with the required infinity distinction would solve this decision problem even with fixed \(\varepsilon\). Thus the requested computational problem is \(\mathrm{NP}\)-hard and cannot have the proposed polynomial running time unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claims are correct, and the argument resolves the task. Every rate exists; the proposed equality fails for zero-weight targets with finite \(I_t\); and computing all rates with the required infinity distinction is \(\mathrm{NP}\)-hard. I found no major or minor mathematical issues requiring repair.
The quota hypothesis implies \(W>0\) and \(W/2<q\le W\). The correspondence between coalition components and components of the occupied type support is correct: each occupied type induces a connected clique, and adjacency between occupied types is exactly adjacency in \(H\).
The calculation of \(J(S)\) is valid in all three cases:
The entropy inequality and its equality condition are correct, including zero weights and endpoint values of \(p\). Summing it establishes the claimed minimum because \(\lambda>0\) and the weighted-sum constraint is a lower bound.
The binomial probability bounds give the asserted exponent for individual count vectors. The designated-agent deletion changes each normalized population size by at most \(1/k\), which vanishes in the limit. The finitely many initial instances in which an available population is zero do not affect this argument.
The tail estimate is also correct. For the interior case, exponential Markov bounds apply with the stated optimizer. At the boundary \(q=W(S)\), admissibility makes \(kq\) integral, and reaching quota forces selection of all positive-weight agents in \(S\).
Both inequalities proving \(I_t=J(U_t)\) hold.
For the lower bound, the component containing \(t\) lies inside \(U_t\). Nonnegative weights therefore make the restriction of any feasible vector to \(U_t\) feasible for \(J(U_t)\). Entropy contributions outside \(U_t\) are nonnegative.
For the upper bound, the proposed choice \(A=T\) is permitted by the task. The optimizer gives selected weight exactly \(q\) in \(U_t\), while every other full component has selected weight at most \(W/2<q\). Thus all feasibility constraints hold.
If \(W(U_t)<q\), both the asserted infeasibility and the resulting infinite value are correct.
The probability upper bounds establish the required lower bound on the rate.
When \(q<W(U_t)\), pivotality requires pre-addition selected weight at least \(Q_k-w_t\) within \(U_t\). The moment-generating-function calculation correctly accounts for the omitted target through the term \(-a_t\). The remaining multiplicative factor is at most \(2\).
When \(q=W(U_t)\), this necessary threshold forces selection of every available positive-weight agent in \(U_t\). Their probability is exactly \(2e^{-kJ(U_t)}\).
The matching count constructions are valid:
The boundary construction likewise reaches \(Q_k=kq\) exactly after adding the target. Its entropy cost includes full selection of positive-weight types and half selection of zero-weight types.
These constructions work along every sufficiently large admissible integer, so they establish convergence rather than merely a subsequential bound.
The compulsory absence of all other type-\(t\) agents is correctly justified. If type \(t\) is already occupied, adding another zero-weight member supplies neither new connections nor additional weight.
The characterization by merging-admissible supports is sound.
For necessity, the merged selected weight must reach quota. If only one merged component had positive selected weight, that component would already reach quota before addition, contradicting pivotality. Consequently, at least two merged components have positive capacity.
For a fixed support, the absence probability correctly subtracts the unsampled designated agent. The tail event on \(S_t(A)\) is independent of those absences. Summing the resulting bounds over finitely many supports gives the claimed exponent bound with factor \(2^\tau\).
The matching construction checks all necessary conditions:
The resulting count-vector exponent is exactly the stated objective. The finite minimum is attained because the support family is finite. If that family is empty, the necessity argument excludes pivotal coalitions at every admissible \(k\).
Thus the formula establishes every zero-weight target’s extended-real rate, including the boundary case.
The three-type example satisfies all input restrictions. Its total weight is \(1/2\), and its quota \(3/8\) lies strictly above half that total.
The exact pivotal-probability formula is correct. The other type-\(t\) agents must all be absent; each endpoint clique individually has capacity below quota; and the combined endpoint count has the stated binomial distribution. Reaching quota also ensures both endpoints are occupied.
The reported values of \(I_t\) and \(R_t\) follow from the already established formulas and differ by \((1/2)\ln2>0\).
The general inequality for zero-weight targets is valid: compulsory absence contributes \(\mu_t\ln2\), independently of the necessary selected-weight event in \(U_t\). Since \(\mu_t>0\), equality fails whenever \(I_t\) is finite. Together with the positive-weight result and the infeasible-component case, this verifies the final characterization of equality.
The cited source theorem is accurately stated. Döcker proves the required monotone satisfiability restriction is \(\mathrm{NP}\)-complete, including three distinct variables per clause and exactly two occurrences of each sign per variable. The source additionally restricts duplicate clauses, which does not invalidate its use here. [Döcker’s paper](https://arxiv.org/abs/1912.08032)
The constructed instance satisfies the task’s restrictions:
Both reduction directions hold.
A pivotal coalition at full-total quota must select every positive-weight agent, and all such agents must lie in one component after addition. Since the target has only neighbors \(a,b\), those roots must occupy different pre-addition components, and every clause type must belong to one of them. Occupying both members of a variable pair would connect the roots. An occupied neighbor of each clause therefore supplies the required satisfying literal.
Conversely, a satisfying assignment gives the stated two root components. Clause edges remain on their corresponding side, and no variable-pair edge joins occupied endpoints. Each component loses because it omits the other root’s positive weight; adding the target joins all positive weight.
The explicit finite rate also checks out. Full-total quota forces retention of all positive-weight types, and merging admissibility forces deletion of at least one type from every variable pair. A satisfying assignment achieves exactly that minimum number of deletions.
Finally, the certificate for zero-weight finiteness consists of a support whose components and rational capacities are polynomially checkable. Positive-weight finiteness is directly decidable by the component-capacity test. This establishes \(\mathrm{NP}\)-completeness of designated-rate finiteness and the claimed hardness of the requested all-rates computation.
None. No missing lemma, unsupported theorem application, failed edge case, or incorrect computation blocks the conclusions.
⟨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.