| paper | d4-conf-atal-2008-0278 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-hard}\), even with two primary vertices, no backbone vertices, equal masses, and a guaranteed finite optimum. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite role-network template \(H\), fixed primary and backbone vertices, positive integer role weights \(w_t\) for \(t\in T\), and a target role \(r\), let \(W_H(K)\) indicate whether the primary vertices are connected when exactly the standard roles in \(K\) are available. With \(W=\sum_{t\in T}w_t\) and \(\mu_t=w_t/W\), compute the exact value and a maximizing set for \(\rho_r=1-\max_{K\subseteq T\setminus\{r\}: W_H(K\cup\{r\})=1,\,W_H(K)=0}\sum_{t\in K}\mu_t\), or return \(+\infty\) if no such \(K\) exists. This is the decay rate \(-\lim_{q\to\infty}(qW)^{-1}\log_2\beta_i(G_q)\) for a representative server \(i\) of role \(r\) in the \(q\)-fold replicated template, with independent fair failures.
A fixed connectivity template has standard server roles \(T\) with population masses \(\mu_t\). Each role is available if at least one of its \(q w_t\) servers survives. For a target server in role \(r\), the decision set is a pivotal role set \(K\subseteq T\setminus\{r\}\); maximize its active mass \(\sum_{t\in K}\mu_t\) subject to connectivity holding with \(r\) and failing without it. The complement of that maximum is the target server’s asymptotic Banzhaf decay rate.
The exponent is controlled by rare finite-copy failures, especially the event that every other copy of the target role fails, so it does not give a literal nonatomic Banzhaf index.
fatal: False
The mirror covers the general-graph CG-BANZHAF hardness question behind Theorem 1, but does not transfer its #P-hardness or counting result; it leaves the tree algorithm and core-computation result aside.
The strongest case I can make is an asymptotic mirror for individual Banzhaf influence in a replicated network fabric. It is narrower than the paper’s full problem, but keeps its central question: how often does removing one server change whether the primary vertices are connected?
Take a fixed network template with primary and backbone vertices, plus a finite set \(T\) of standard server roles. Each role has the same wiring wherever it appears. Replicate the template \(q\) times, so role \(t\) has \(q w_t\) interchangeable servers. A type is one of these roles, including its failure behavior and network connections; its mass is \(\mu_t=w_t/W\), where \(W=\sum_{t\in T}w_t\). This describes a large fabric with many redundant servers in a relatively small number of wiring roles: the number of agents is \(N=qW\), while the number of types is \(\tau=|T|\).
For a coalition, let \(x_t\) be the fraction of role \(t\)’s servers that survive. In the replicated template, a role is available if at least one of its servers survives. The question is about the probability that a distinguished server is pivotal when every other server independently survives with probability \(1/2\), as in the paper’s Banzhaf model.
The lead anchor is Theorem 1, proved in this paper. It says that calculating CG-BANZHAF is \(\#P\)-hard even when there are no backbone vertices. Its reduction maps set-cover instances to connectivity games so that set covers correspond one-to-one with coalitions in which the designated agent \(v_a\) is critical. Lemma 1, also proved here, establishes membership in \(\#P\): given a coalition, whether it wins and whether the target agent is critical can be checked in polynomial time. Together, they give the paper’s \(\#P\)-completeness result. The mirror below is motivated by that hardness result; it does not claim to inherit it.
I would hand a prover this problem, Asymptotic Type-Banzhaf:
Given a finite role-network template \(H\), positive integer role multiplicities \(w_t\), and a target role \(r\), compute the exponential decay rate of a representative server’s Banzhaf power as the template is replicated. Return
\[ > \rho_r=-\lim_{q\to\infty}\frac{1}{qW}\log_2\beta_i(G_q), > \]
or \(+\infty\) if the representative is never pivotal. A solution includes the exact value of \(\rho_r\) and a role set attaining it.
Here \(G_q\) is the network with \(q w_t\) interchangeable servers of each role, and \(\beta_i(G_q)\) is the paper’s normalized Banzhaf power for one representative \(i\) of role \(r\). To state the optimization behind the question, let \(W_H(K)\) say whether the primary vertices are connected when precisely the standard roles in \(K\subseteq T\) are available, alongside the fixed primary and backbone vertices. Define
\[
\mathcal K_r=\{K\subseteq T\setminus\{r\}: W_H(K\cup\{r\})=1,\ W_H(K)=0\}.
\]
Then
\[
\rho_r=1-\max_{K\in\mathcal K_r}\sum_{t\in K}\mu_t,
\]
with \(\rho_r=+\infty\) if \(\mathcal K_r\) is empty. The mass profile view is that the surviving fractions \(x_t\) have binary entropy \(h(x_t)\); the pivotal profiles maximize aggregate entropy subject to role \(r\) being pivotal. In an active role, half-survival maximizes that entropy. Thus the problem asks for the heaviest mass of other roles that can be active while the target role remains pivotal.
I expect this optimization to retain substantial graph-structural difficulty, plausibly Class B if a hardness reduction can be shown: the remaining combinatorics lie in the network roles, not in the number of replicas. The paper’s theorem alone does not establish that classification. It counts pivotal coalitions, whereas the mirror maximizes mass over pivotal role sets.
That distinction is the weakest point in the positive case. In the paper’s set-cover reduction, every set role together forms a cover, so the asymptotic rate can be governed by that maximum-mass cover; the number of covers, which carries the \(\#P\)-hardness, need not survive the limit. Also, the mirror applies to symmetric replicated fabrics, not every graph in the paper. Still, at each finite \(q\) it uses the same connectivity condition and individual-server pivotality. The new question is whether that influence has a tractable or hard large-population limit. Its natural follow-ups are whether the rate is computable in polynomial time for trees or bounded-treewidth templates, and whether finer asymptotics can recover information lost when only the exponential rate is retained.
This case covers only the general-graph CG-BANZHAF result. It does not mirror the tree algorithm or the core result.
The strongest objection is that Theorem 1 measures an individual server’s pivotality, an atom-level quantity. Its Banzhaf index fixes a named server as working and asks how often removing it breaks connectivity across coalitions of the other named servers. In a nonatomic population, one server has zero mass, so removing it does not change the population state. In the proposed replicated network, a representative server can be pivotal only when every other copy of its role has failed. With \(q w_r\) copies, this makes its index at most \(2^{-(q w_r-1)}\), which tends to zero. The direct continuous limit therefore loses the influence the theorem measures.
Changing the target to a whole role avoids that vanishing, but changes the failure event: the role now disappears as a block, rather than its servers failing independently. Asking whether an infinitesimal mass of a role is pivotal has a different problem: connectivity depends on whether a role has any positive mass, so the answer turns on a discontinuity at zero. The continuous model offers no natural counterpart to the paper’s random coalition of individual server failures.
The proponent’s rate \(\rho_r\) is a coherent repair: it rescales the vanishing index and yields a weighted optimization over pivotal role sets. That is the strongest version of the mirror, and it may be a worthwhile computational problem for replicated network fabrics. The negative case is that its substantive object is an asymptotic failure exponent for a sequence of discrete networks; the continuum itself supplies role weights, while the pivotal event still depends on finite-copy failures. A careful reader could reasonably accept that as a high-multiplicity mirror, especially given the programme’s interest in limits and computational questions.
So the atomlessness objection defeats a direct continuous Banzhaf index, but it does not defeat the proposed exponent. I can’t honestly make the universal negative case airtight: the exponent is a plausible mirror, and the paper’s tree result or core result need not be mirrored if this one survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.