| paper | d4-conf-ijcai-2020-0040 |
| 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}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Corollary 2
statement extracted from the paper’s text layer
Given finitely many roles \(R\), rational masses \(p_r\) summing to \(1\), an initial distribution \(x_{r,a}\) over \(a\in\{b,w,g\}\), a symmetric rational interaction matrix \(W\), and a rational target \(q>0\), does there exist a finite legal mass-transfer schedule ending in a stable state with total black mass at least \(q\)? A transfer of mass \(\delta\) from opinion \(a\) to \(a'\) in role \(r\) is legal when \(a'\)'s exposure \(E_{r,a'}(x)=\sum_s W_{rs}x_{s,a'}\) exceeds half the total exposure \(D_r=\sum_s W_{rs}p_s\) throughout the transfer; stability requires no occupied role-opinion cell to have another opinion above that threshold.
A block mean-field network with discrete opinions and a continuous population: roles encode shared interaction profiles, \(p_r\) is each role’s mass, \(x_{r,a}\) is its mass holding opinion \(a\), and legal schedules transfer mass only to a strict-majority opinion. The objective is to maximize stable final black mass, or test whether it reaches \(q\).
Corollary 2’s threshold of one black node can shrink to mass \(1/n\), so its reduction does not establish hardness for retaining a fixed positive fraction; the role-level exposure rule also replaces individual neighborhoods with aggregate interactions.
fatal: False
The mirror covers stable spread reachability and maximizing final black mass, anchored by Corollary 2. It leaves the sequence-length bounds in Propositions 1 and 2 and Theorems 1 and 2, and the bounded-degree hardness result in Theorem 4, unmirrored.
My lead mirror is Positive-Mass Optimistic Spread in a Block Mean-Field Network. It continuizes the population while keeping opinions discrete and the paper’s central question intact: how much black opinion can a chosen update order preserve in a stable outcome?
The anchor is Corollary 2, proved in this paper by adapting the reduction behind Theorem 3. In the three-opinion setting, it says that finding a stable update sequence whose final outcome has at least one black node is NP-hard and W[2]-hard when parameterized by the sequence length \(|\sigma|\). The underlying task is to choose a legal update order that reaches stability while retaining black opinion.
Here is a continuous version. An instance has a finite set \(R\) of social roles, rational role masses \(p_r>0\) summing to \(1\), and a symmetric rational interaction matrix \(W\). Each agent has one of the three opinions \(a\in\{b,w,g\}\). The state is \(x_{r,a}\in\mathbb Q_{\ge 0}\), the mass of role \(r\) holding opinion \(a\), with \(\sum_a x_{r,a}=p_r\). An agent in role \(r\) sees opinion \(a\) with weighted mass
\[
E_{r,a}(x)=\sum_{s\in R}W_{rs}x_{s,a},
\]
and has total weighted neighborhood mass \(D_r=\sum_s W_{rs}p_s\). A different opinion is a strict majority for that role when its exposure exceeds \(D_r/2\).
A legal schedule is a finite sequence of phases. A phase chooses a role \(r\), a current opinion \(a\), a different opinion \(a'\), and a rational mass \(\delta>0\) to move from \(x_{r,a}\) to \(x_{r,a'}\). It is legal only if \(a'\) remains a strict majority for role \(r\) throughout the move: at every intermediate state \(x^\lambda=x+\lambda(e_{r,a'}-e_{r,a})\), for \(0\le\lambda<\delta\), \(E_{r,a'}(x^\lambda)>D_r/2\). This represents the fluid limit of agents updating sequentially within a homogeneous role; each agent still holds a single, discrete opinion. The schedule must end in a stable state, meaning no occupied role-opinion cell has another opinion with exposure greater than half. Given a rational target \(q>0\), ask whether such a schedule can end with \(\sum_r x_{r,b}\ge q\). Equivalently, maximize final black mass over legal schedules ending in stability. A solution is the finite phase list and its resulting stable state.
A plausible regime is a large online community divided into cohorts with the same interaction profile—for example, users whose feeds expose them to the same proportions of a handful of communities. There may be millions of users but only tens of roles, so the support of the role-opinion state is small compared with the population. A role is complete for this model: its members share the same contact profile and update rule. If those differ, they belong to different roles. Related work on continuous opinion values does not already supply this mirror: here the opinions remain discrete, and the population itself is the continuous object.
I expect the general problem, as the number of roles varies, to be continuum-specifically hard. The schedule still has to choose which role-opinion transitions to trigger and in what order; fractional masses do not obviously remove that reachability structure. But Corollary 2 does not prove this. A finite graph can be represented with one role per vertex and mass \(1/n\), so each discrete update sequence has a corresponding mass-flow schedule. The converse need not hold: the continuous model can move a fraction of a role’s mass, creating paths unavailable to a single discrete vertex. Whether that fractional freedom yields an LP-like algorithm in the moderate-support regime, or whether hardness survives, is a central follow-up question. In particular, one should test fixed-\(\tau\) tractability and whether the W[2]-hardness phenomenon in sequence length has a meaningful mass-based analogue.
This case covers the paper’s spread-reachability result in Corollary 2. It does not claim to mirror the paper’s sequence-length bounds or its bounded-degree hardness result.
The weakest point is the mean-field network assumption. The paper’s agents have specific neighborhoods; in this mirror, agents in a role respond to the role-level exposure distribution. That is a credible model for large dense or feed-mediated populations, but it can erase important local effects in sparse networks. The mirror is strongest when the authors’ question is understood as strategic ordering of majority updates over large homogeneous cohorts, rather than as an exact limit of every finite graph.
The mirror anchored on Corollary 2 loses its target under population normalization. The corollary asks whether some stable sequence can retain at least one black node. In a society of \(n\) agents, that node has mass \(1/n\), which tends to zero. A fixed target \(q>0\) instead asks whether a positive fraction can remain black; the reduction behind Theorem 3, with only two black nodes to preserve, does not establish that question. Taking \(q=0\) makes the target vacuous. The corollary’s one-black-node hardness therefore does not transfer to a nontrivial mass threshold.
A stronger mirror would maximize the final black mass, as the paper’s broader spread question suggests. But its fidelity depends on how the network becomes a small set of roles. In the original model, each agent’s eligibility to update depends on the opinions of its particular neighbors. To preserve that information, agents generally need distinct types, giving support size \(\tau\) comparable to \(n\); allowing fractions of each such type to move then creates partial agents the finite graph did not have. A small role space works when agents have interchangeable interaction profiles, but the proposed exposure rule based on \(W\) replaces individual neighborhoods with role-level weighted exposure. That is a coherent mean-field network model, but it is a substantial change to the object whose update schedules the paper studies.
The best case for the mirror is a large, feed-mediated community with a few cohorts whose members see similar proportions of each other. There, role-level exposures and mass transfers are plausible, and maximizing stable black mass is a well-posed computational question. That scenario keeps opinions discrete and the population continuous. It also leaves the negative case with a real weakness: it is hard to rule out that the authors would recognize this as their problem in a dense, cohort-based regime.
So I would reject Corollary 2 as the anchor: its one-node threshold collapses, and the more meaningful mass objective requires a mean-field interaction model rather than a faithful continuization of the arbitrary-graph instances. But I cannot honestly defend the universal claim that no worthwhile continuous mirror exists in any scenario. The dense-cohort version remains plausible; the case against it is a model-fidelity concern, not a decisive obstruction.
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.