| paper | d4-conf-aaai-2018-0928 |
| 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{-complete}\), already for \(\tau=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 13
statement extracted from the paper’s text layer
Given a finite network template \(G=(V,E)\), its thresholds, product quality \(\phi\), payoffs \(p,q\), and per-market seed cap \(k\), consider a continuum of copies indexed by \(z\in[0,1]\). Each copy follows the paper's cascade and payoff rules. Is there a measurable assignment \(S_z\) of accepting seed nodes, with \(|S_z|\le k\) almost everywhere, such that the population-average normalized payoff \(\int_0^1 \pi_G(S_z)/|V|\,dz\) is positive?
A continuum of repeated local markets, each containing the same finite network template. Network roles carry population mass across markets, while a shared market index preserves the template's within-market edges. The decision variable is a measurable per-market seed set; the objective is average payoff per capita.
The continuous role masses alone do not encode which agents share a market and are connected; the construction needs that additional market-level relational structure.
fatal: False
The mirror covers Theorem 13's budgeted positive-payoff decision. It leaves the unbudgeted algorithms in Theorems 8 and 11 and the simulation results unaddressed.
The strongest honest case is Theorem 13, proved in this paper. It says that, in the initial overexposure model, it is NP-complete to decide whether a seed set of size at most \(k\) can achieve positive payoff. The paper proves this by reducing Clique on a \(d\)-regular graph, with \(d\ge k\): subdivide every edge, make the original vertices accepting and the subdivision vertices rejecting, set \(q=1\), and set \(p=d-(k-1)/2+\epsilon\) for \(0<\epsilon<1/n^2\). The resulting instance has a positive-payoff seed set of size at most \(k\) exactly when the original graph has a \(k\)-clique.
A plausible regime is repeated product launches across many local markets with the same typed social-network template. Each market has the same network roles, thresholds, and neighbor-role pattern, and the firm has at most \(k\) seed slots per market. A type is a role in that template, including its acceptance status and its network position. Mass is the fraction of markets in which that role is occupied by an agent, exposed, or seeded. For a fixed template with \(N\) roles, there are \(N\) types and a continuum of agents overall. This fits the product-marketing setting: many consumers appear across markets, while their relevant behaviors and network roles repeat.
Here is the continuous question. Call it Continuum Budgeted Overexposure Seeding. An instance consists of a finite template \(G=(V,E)\), with thresholds \(\theta_v\), product quality \(\phi\), payoff parameters \(p,q\), and a per-market seed cap \(k\). The society is \(\Omega=V\times[0,1]\), where \(z\in[0,1]\) indexes markets; each role \(v\) has mass \(1/|V|\), so the total population has mass \(1\). Agents \((u,z)\) and \((v,z)\) are connected exactly when \(uv\in E\), and cascades within each market follow the paper’s deterministic rules.
A solution is a measurable seed assignment \(S\subseteq\Omega\) such that, for almost every market \(z\), the fiber \(S_z=\{v:(v,z)\in S\}\) contains only accepting roles and has size at most \(k\). Let \(\pi_G(S_z)\) be that market’s payoff under the paper’s cascade; the continuous problem asks whether some such assignment has positive population-average payoff, \(\int_0^1 \pi_G(S_z)/|V|\,dz>0\).
This is a hardness-transfer mirror: repeating any positive-payoff seed set in every market gives a positive continuous solution. Conversely, a positive average requires some positive-measure set of markets to use a seed set with positive payoff. So the continuous problem is yes exactly when the original Theorem 13 instance is yes. The paper’s authors could plausibly recognize the per-market problem as theirs: each market has precisely their network, budget, cascade, and payoff; the continuum aggregates the audience across repeated launches. The expected classification is therefore Class B, with hardness carried over from the discrete problem.
The weak point is that this continuization aggregates repeated markets rather than relaxing seed choices inside one large network. The per-market quota preserves the original discrete decision, and the template has \(N\) roles for \(N\) agents, so this gives no useful compression as \(N\) grows. It is a defensible continuous-population scenario, but not the programme’s strongest kind of high-multiplicity relaxation. In particular, replacing the per-market cap with one global fractional cap across all markets would be a different question: seed effort could concentrate on a small fraction of markets, and the equivalence to Theorem 13 would no longer follow. That distinction suggests the next questions: does hardness persist when the cap is global and proportional to population mass, and can it persist with a bounded number of network types? Those would test whether the paper’s hardness is tied to per-market combinatorics or survives a more substantive population continuization.
Theorem 13 is a real computational result, so the negative case cannot dismiss it for lack of an anchor. Its hardness comes from the exact overlap pattern of neighborhoods in the subdivided graph: choosing seeds pays off when their rejecting boundaries overlap in just the right way. That makes network position part of an agent’s description. Grouping people only by \(\theta_i\) loses information the payoff depends on; preserving every relevant position in an arbitrary graph can leave essentially one type per node.
The proposed market construction preserves that information by putting a copy of the whole finite graph in every market. But each market still has the original integral seed cap and the original seed-set problem. A measurable assignment across markets amounts to choosing local seed plans in different proportions; the positive-average question is yes exactly when some local plan has positive payoff. So the construction makes the population continuous across markets without relaxing the computational choice inside a network. It is a plausible scenario, but its continuity is external to the part of the model that Theorem 13 makes hard.
A stronger version would use one global seeding-mass budget across the repeated markets, so the firm could allocate seed effort among markets rather than enforce a separate cap in each. That is a coherent continuous question, but its fractional choices are still mixtures of whole-network seed plans. The cascade and neighborhood-overlap structure remain inside each finite copy; the new coupling is an aggregate allocation constraint. This looks more like a portfolio of local campaigns than a high-multiplicity relaxation of seeding within one social network.
The alternative is to model one large network through a continuum of roles and an interaction structure between them. That might be worthwhile, but it exposes the central difficulty: in this paper’s deterministic cascade, reachability depends on paths and boundary overlaps. A coarse role model may not preserve either, while a model that keeps enough topology to preserve them may retain the original graph’s complexity. Dense-network limits can also change reachability, so replacing the graph with a continuum interaction kernel requires substantive modeling choices.
That is the strongest case against: this paper’s hardness appears tied to relational structure that population masses alone do not capture, and the clearest continuous construction leaves the hard decision intact in each finite network. It is not a decisive case for “no worthwhile mirror in any scenario.” Repeated markets are plausible, and a suitable continuum network model could make the question meaningful. The honest negative verdict is therefore limited: Theorem 13 is a weak fit for a population continuization that relaxes the seeding problem itself, rather than merely aggregating many copies of it.
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.