| paper | d4-conf-sagt-2011-0026 |
| 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: NP-hard to approximate within \(o(\tau)\), already for \(m=3\). Even a polynomial-time multiplicative \(\tau\)-approximation would imply \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8(i)
statement extracted from the paper’s text layer
Given a finite product set \(P\), cohort types \(i\in\{1,\ldots,\tau\}\) with rational masses \(\mu_i\), thresholds \(\theta_i\), initial adopted products or available-product sets \(S_i\), and rational influence coefficients \(q_{ji}\), let \(x_{j,p}\) be the fraction of type \(j\) that has adopted product \(p\), with exposure \(E_{i,p}=\sum_j q_{ji}x_{j,p}\). A legal move transfers any positive fraction of a type's undecided mass to an available product \(p\) when \(E_{i,p}\ge\theta_i\), and adopted mass cannot switch. Find the minimum \(\sum_i\mu_i x_{i,\mathrm{top}}\) over finite legal sequences ending in a state where no undecided mass can adopt any available product.
A block-structured continuous population: each type shares its threshold, available products, and influence on every other type; each unit of mass adopts one product, while type-level adoption fractions may be fractional.
The mirror covers Theorem 8(i)'s MIN-ADOPTION objective for block-structured populations; it leaves the paper's other adoption, uniqueness, and graph-characterization results untouched.
I would anchor the case in Theorem 8(i), proved in this paper. It says that for an \(n\)-node network, MIN-ADOPTION—given an initial social network and a product \(top\), find the minimum number of nodes that adopt \(top\) in any reachable final network—is NP-hard to approximate within a ratio better than \(\Omega(n)\). The authors prove this using a reduction from PARTITION.
A concrete mirror is Cohort-Minimum-Adoption. Consider a large platform where people fall into \(\tau\) cohorts. Members of a cohort have the same available products, threshold, and pattern of influence on every other cohort. The number of people \(N\) is much larger than \(\tau\), so cohort size is naturally measured as a fraction of the population. This is plausible, for example, for users grouped by region and broad preference or usage profile. A sequence of larger block-structured networks gives finer and finer adoption fractions. The paper itself includes equitable networks, where adoption depends on the fraction of neighbours holding a product, so aggregate cohort exposure fits a model family the authors already consider.
An instance has a finite product set \(P\), types \(i\in\{1,\ldots,\tau\}\) with positive rational masses \(\mu_i\) summing to \(1\), and rational thresholds \(\theta_i\in(0,1]\). Each type is initially either committed to one product or undecided among a nonempty set \(S_i\subseteq P\). For each pair \(j,i\), a rational coefficient \(q_{ji}\geq 0\) gives the influence on a member of type \(i\) when all of type \(j\) has adopted one product; require \(\sum_j q_{ji}\leq 1\). If \(x_{j,p}\) is the fraction of type \(j\) that has adopted product \(p\), type \(i\)'s exposure to \(p\) is
\[
E_{i,p}=\sum_j q_{ji}x_{j,p}.
\]
A legal move transfers any positive fraction of a type’s still-undecided mass to a product \(p\in S_i\), provided \(E_{i,p}\geq\theta_i\). Adopted mass cannot switch products. A state is final when no undecided mass can legally adopt any available product. The question is to find, over all finite legal sequences ending in a final state, the minimum possible total population mass adopting \(top\), namely \(\sum_i\mu_i x_{i,top}\). A solution gives the minimum and a sequence reaching a final state that attains it. This keeps the products, threshold rule, and notion of a final outcome discrete; it is the population whose representation changes from individual nodes to mass.
I tentatively expect this mirror to be tractable, making it a Class A candidate. Influence is linear in the adopted fractions, and an eligible cohort can contribute any amount of mass rather than forcing an all-or-nothing choice for a person. That gives continuous optimization a real foothold. The key open step is to encode which activations can occur, and in what order, without reintroducing an unwieldy discrete search. The questions it generates include whether reachable final states admit a compact LP or separation formulation, whether exact optimization is polynomial in \(m,\tau,L\), and whether hardness survives when \(\tau\) is small.
The weakest point is that Theorem 8(i)’s PARTITION reduction relies on individually selectable nodes. Its item nodes have different influence weights, and their discrete choices create the partition. In the mirror, a cohort can split between products, so that particular partition obstruction may disappear; the theorem’s \(\Omega(n)\) lower bound does not transfer just by replacing counts with masses. Nor does this model preserve arbitrary graph topology. I would limit the claim to the block-structured, high-multiplicity regime: it is a credible continuous version of the paper’s threshold adoption problem, but the paper’s hardness result is a motivation for asking the question, not an answer to it.
The only computational anchor is Theorem 8(i), and it is a real one: minimizing a product’s spread across final networks is NP-hard to approximate. The strongest objection is that a node’s position in the influence graph is part of what makes it distinct. To preserve the paper’s general model, a type would need to capture its thresholds, available products, and influence relations. In arbitrary networks, that may leave almost every node in its own type. The PARTITION reduction illustrates the problem: each item node’s influence weights encode its particular \(a_i\). Replacing neighborhoods with average cohort exposure can change which adoptions meet a threshold, and so need not preserve the reachable final outcomes.
That objection does not dispose of the strongest mirror. In a large, genuinely block-structured network, members of a cohort could share thresholds, available products, and influence on every other cohort. Then the adoption fraction is meaningful, and minimizing the mass adopting \(top\) asks a recognizable question about the paper’s diffusion process. The paper’s equitable networks, where adoption depends on a fraction of neighbors, give this version some footing in its own model. Fractional adoption may erase the PARTITION gadget, but that is an answer the continuous problem might produce, not a reason the question is unworthy.
I found no basis for an “already done” objection: a nearby large-network study derives mean-field approximations for threshold-cascade dynamics, rather than this minimum-over-final-outcomes optimization ([Como, Rossi, and Fagnani](https://arxiv.org/abs/1604.05490)). The honest negative case is therefore narrow: the mirror is faithful mainly in symmetric block networks, not across the paper’s general networks. I can’t turn that into the universal claim that no plausible scenario makes the question worthwhile. The cohort mirror survives that test; whether its optimization is tractable remains open.
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.