| paper | d4-conf-ecai-2020-0218 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given a finite connected role graph \(H=(R,E)\) in the paper’s augmented quasi-path or augmented-cycle classes, rational role masses \(\mu_r>0\) summing to \(1\), and initial product masses \(x^0_{r,p}\), determine whether a finite schedule of rational mass updates can end at a stable state whose white mass equals the supremum over all feasible schedules; if so, return such an SPMS schedule. Each member of role \(r\) sees the product masses in the adjacent roles and follows the paper’s majority rule and tie-breaking, while white recommendations have priority whenever eligible mass exists.
A role graph \(H=(R,E)\) describes complete mixing between adjacent cohorts. The input is the rational distribution \(\mu\) over roles and initial product masses \(x^0_{r,p}\); updates transfer rational mass between products within a role. The objective is to reach a stable state maximizing total white mass, with an optimal SPMS schedule as the desired output.
The model requires every member of a role to mix uniformly with every adjacent role, so its relevance is limited to markets with that block structure.
fatal: False
The mirror covers majority-behaviour optimal SPMS scheduling on augmented quasi-paths and augmented cycles, including the existence guarantee of Theorem 2. It leaves aside the broader topology characterizations and the absolute-majority results.
The strongest mirror I see is Continuum Optimal Social-Proof Scheduling. Its anchor is Theorem 3, proved in this paper by a reduction from 3-SAT: for majority-behaviour customers, computing a social-proof marketing strategy (SPMS) evolution that is also optimal is NP-hard, even when the network is an augmented quasi-path or an augmented cycle. Those are the paper’s restricted graph classes in which every vertex of degree 3 or at least 5 has at most one neighbor that is not a leaf. The paper’s Theorem 2 establishes that an optimal SPMS evolution exists on these classes, so Theorem 3 is about finding the right schedule.
Here is a continuous version of that underlying scheduling problem. Let \(H=(R,E)\) be a connected, undirected interaction template in one of those graph classes, with \(|R|=\tau\). A role \(r\in R\) represents a large cohort of otherwise interchangeable customers: each member has the same majority behaviour and is connected to the population in every role adjacent to \(r\). The society is a distribution \(\mu\) over roles, with \(\mu_r\in\mathbb{Q}_{>0}\) and \(\sum_r\mu_r=1\). A large platform launch could have millions of customers but only \(\tau\) recurring community roles; a role records the customer’s interaction pattern, not their identity.
Write \(x_{r,p}\) for the mass in role \(r\) currently using product \(p\in\{\text{black},\text{gray},\text{white}\}\), with \(\sum_p x_{r,p}=\mu_r\). The initial state \(x^0\) is part of the input and records the seeded fractions. A customer in role \(r\) sees neighbor mass \(N_{r,p}=\sum_{s:rs\in E}x_{s,p}\) for product \(p\), then follows the paper’s majority rule and tie-breaking convention. Each update moves a positive rational mass of one role-and-product group to the product its members currently prefer. An SPMS update may move mass to white only when those customers would adopt white; while any such mass is eligible, white recommendations take priority. When none is eligible, an unstable mass may update autonomously. A schedule is a finite list of these updates ending in a stable state.
The problem is: does there exist an SPMS schedule whose final white mass attains the supremum of final white mass over all feasible schedules from \(x^0\)? A yes solution is the finite update list and its final state; a no answer means no SPMS schedule attains that best feasible terminal mass. The input masses and update amounts are binary rationals. For a direct high-multiplicity analogue of the theorem’s instances, one can restrict to equal role masses, \(\mu_r=1/\tau\), and initial states that are pure within each role.
I expect hardness to transfer (Class B). The SAT choices in Theorem 3 are encoded by the interaction template and its role gadgets, so increasing the population represented by each role does not remove the graph structure carrying the reduction. The open part is substantial: the paper’s proof does not establish hardness for this continuous problem. Allowing a role’s mass to split between products can give schedules unavailable to a single-vertex graph, so the reduction would need to show that fractional schedules cannot bypass its gadgets. That is also the main question the mirror generates: can one force all-or-nothing role choices, or can mass splitting yield a tractable formulation? The answer may depend on whether Theorem 2’s existence guarantee survives fractional updates.
The authors would, I think, recognize the mirror: it retains their three-product market, local majority behaviour, fixed initial seeding, white-only recommendations, schedule choice, and goal of maximizing final white adoption. Replacing each individual by a population role changes the neighborhood model to a block interaction template, which is the co-modification needed for a high-multiplicity regime. It does not turn the task into seed selection or into an outcome-space continuity question.
The soft spot is that block neighborhoods erase individual wiring: every person in a role sees the same *distribution* of neighbors rather than the same finite set of named neighbors. The mirror is most credible for large, repeated communities whose members have stable interaction patterns of this kind. Whether the authors accept that regime is the key plausibility test. I would scope the case to Theorem 3’s majority-behaviour scheduling problem; the paper’s other topology classifications and its absolute-majority results need not be mirrored to make this a substantive question.
Theorem 3 is a real computational anchor: it proves NP-hardness for choosing an optimal SPMS evolution, and the paper explicitly fixes the seeds while asking how to schedule recommendations. I can’t dismiss it as seed selection or as a result about continuous outcomes.
The strongest case against the proposed mirror is that Theorem 3’s hard instances encode 3-SAT in a sparse graph’s exact wiring. The variable and clause gadgets depend on particular vertices seeing particular neighbors, and on individual vertices updating one at a time. For an arbitrary input graph, a vertex’s neighborhood may be part of its complete type. Then there may be no repeated types to aggregate: \(\tau\) can be \(n\), and the population description has not compressed the instance.
The proposed role graph sidesteps that problem by making every member of a role see the mass of every adjacent role. That is a coherent model, but an edge between roles now represents a complete bipartite interaction between their populations. It changes the paper’s local, unweighted neighbor counts into votes over growing cohorts. Alternatively, cloning each vertex while preserving its exact neighbors requires matching clones across adjacent roles; a distribution over role masses alone does not record those pairings or the correlations between their states. Either choice makes it hard to claim that the SAT gadgets, and thus Theorem 3’s problem, have carried over.
That objection does not eliminate the best version of the mirror. A repeated, role-structured market can be modeled by blowing up each vertex into many clones and connecting the clone cohorts across the original edges. With a suitable state description, fractional updates then give a continuous scheduling problem over a plausible high-multiplicity regime. The resulting question may differ from scheduling in one sparse network, but the programme allows a natural co-modification when population continuity requires it.
So the negative case is about reach and relevance: Theorem 3’s hardness comes from individualized wiring, while the clean continuous model covers highly symmetrized networks. That makes the mirror’s connection to the paper debatable, but not untenable. I can’t honestly conclude that no scenario makes it worth studying; this anchor survives the strongest objection I can support.
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.