| paper | d4-conf-atal-2008-0312 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(O((m+\tau)L^2+m^3L)\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 15
statement extracted from the paper’s text layer
Given a two-terminal series-parallel network template, rational masses \(\mu_t\) of capacity-agent types \(t\), per-agent capacities \(a_t\), a location \(\ell(t)\) for each type, a rational target flow \(K\), and a queried type \(q\), let \(F(y)\) be the maximum flow when location \(\ell\) has capacity \(\sum_{t:\ell(t)=\ell} a_t y_t\). Decide whether there exist coalition masses \(0\le y_t\le\mu_t\) and \(0<\delta\le y_q\) such that \(F(y)\ge K>F(y-\delta e_q)\).
A society consists of mass \(\mu_t\) of interchangeable capacity agents of each type, where a type specifies a location in a fixed series-parallel network and per-agent capacity \(a_t\). A coalition selects mass \(y_t\) from each type, capacities aggregate at their locations, and the decision is whether some positive tranche of queried type \(q\) is pivotal for reaching target flow \(K\).
The positive-mass tranche question is not formally shown to be the limit of finite-cohort one-agent dummy tests, and it does not define a continuum Shapley or Banzhaf value; the proponent acknowledges the missing limit bridge but does not establish it.
fatal: False
The mirror covers Theorem 15’s non-dummy decision and its pivotality interpretation; it leaves the paper’s MC-net results and its Shapley and Banzhaf algorithms without continuous mirrors.
The strongest case I see is the paper’s series-parallel network-flow result, Theorem 15. It states that, given a network-flow game on a series-parallel network and an edge-agent \(e\), deciding whether \(e\) is not a dummy is NP-hard; consequently, deciding whether that agent’s Shapley value or Banzhaf share is nonzero is NP-hard as well. The paper proves this result here, by reduction from Partition, with capacities and the target flow value encoded in binary.
A credible continuous regime is a large pool of interchangeable capacity modules owned by agents. A module’s type records its position in a fixed series-parallel network and its per-agent capacity. Many agents may own modules of the same type—identical in every respect used by this game—so the population can be large while the number \(\tau\) of types stays modest. This is plausible for standardized backup links or capacity units deployed in large cohorts. It would be a poor fit for a network where every edge has a unique role and capacity.
Here is the mirror I would put to a prover: Positive-Mass Pivotality in Continuum Series-Parallel Flow Games. An instance consists of a two-terminal series-parallel network template; a finite support \(T\) of edge types \(t=(u_t,v_t,a_t)\), where \(a_t\) is per-agent capacity; rational type masses \(\mu_t>0\) with \(\sum_{t\in T}\mu_t=1\); a rational target flow \(K\), normalized per unit of population; and a queried type \(q\). A coalition is a mass vector \(y\) with \(0\le y_t\le\mu_t\). Its arc capacities are \(a_t y_t\), and let \(F(y)\) be the resulting maximum \(s\)-to-\(t\) flow.
The question is whether there exist \(y\) and a positive mass \(\delta\le y_q\) such that
\[
F(y)\ge K > F(y-\delta e_q).
\]
A “yes” solution is such a coalition mass profile and pivotal tranche of type \(q\); a “no” solution says no coalition makes any positive tranche of that type decisive. This keeps the paper’s core question—whether a player’s contribution can change a coalition from losing to winning—while replacing indivisible edge selection with selection of population mass. The fractional aggregate capacities are part of that population relaxation: with many identical edge owners, the network’s capacity contributions scale with the cohort size.
I expect this mirror to be tractable (Class A), probably by exploiting the series-parallel decomposition together with continuous feasibility or parametric-flow methods. The Partition reduction behind Theorem 15 relies on choosing indivisible edges to realize a subset sum. Allowing fractions of each type appears to erase that constraint: capacity can be adjusted continuously instead of selecting a subset. This is a reason to investigate the mirror, not a proof that it is easy; the exact dependence on network size, \(\tau\), and rational bit length remains open.
I would cover Theorem 15 only. I am not claiming a continuous Shapley or Banzhaf formula, or a mirror of the paper’s MC-net results. The relevant anchor is its non-dummy decision problem, for which a type-level pivotality question is direct.
The weakest point is that type-level pivotality changes the granularity of the query: a positive mass tranche is not the same object as one individually pivotal edge. Also, the Partition construction gives each weight a distinct capacity, so its hard instance does not itself establish hardness when \(\tau\) is small relative to the population. A referee could reasonably ask whether the authors regard pivotality of a cohort as their problem. I think they could recognize it as a natural high-multiplicity version: the network, threshold, coalition value, and marginal-contribution question all remain, while the population of edge-agents is what becomes continuous. The main follow-up is to pin down when type-level pivotality agrees with the limit of finite-cohort dummy tests, and whether the resulting decision problem has a polynomial-time algorithm in \((|V|,\tau,L)\).
Theorem 15 is a genuine computational result, so I would not argue that the paper has no anchor or that someone has already answered it continuously. The difficulty is that the result’s player is an edge: its contribution depends on where it sits in the network and on which other edges are present. A complete type therefore has to record at least the edge’s role and capacity. In the paper’s simple graphs, a given endpoint pair occurs at most once, so exact location types are singletons. Grouping edges from different locations by capacity or broad structural role loses information the flow game uses.
The best repair is to imagine many interchangeable agents supplying capacity at the same network location. That gives a coherent continuous capacity model, but it changes the question. The proposed positive-mass test asks whether a whole tranche of a type can move a coalition across the flow threshold. Theorem 15 asks whether one edge has a nonzero Shapley value or Banzhaf share, which is about an individual’s marginal contribution across coalitions. To preserve that query in a cohort of \(N\) agents, one must ask whether a tranche of size \(1/N\) can be pivotal. In the limit, that becomes a boundary-sensitivity question at the target flow, not the paper’s power-index computation. Defining a nonzero continuum power share would require choosing a new value concept and its normalization.
There is also a problem with grouping edges that are interchangeable individually but occupy different positions. For example, take many parallel two-edge paths from \(s\) to \(t\). All first edges have the same role under path permutations, as do all second edges. Yet knowing how many first and second edges a coalition contains does not determine its flow: the selected edges might form complete paths, or leave every path incomplete. Recording enough detail to recover those pairings brings path identity back into the type description. Exact duplicate links avoid that problem, but their total contribution is simply an arc capacity, so the proposed test becomes continuous max-flow sensitivity on a capacity vector.
That is the strongest negative case: either aggregate only exact clones and obtain a capacity-sensitivity problem with no Shapley or Banzhaf question, or preserve the game’s coalition structure and retain identity or correlation information that a small type distribution does not capture. Still, this is not airtight. In a real system with many standardized capacity units at each location, cohort pivotality could be a sensible computational problem in its own right. If the authors count that as a worthwhile mirror, the anchor survives; the case against is strongest as a claim about mirroring Theorem 15, rather than about the value of every continuous flow question.
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.