| paper | d4-conf-aaai-2024-0116 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. A minimum-mass successful campaign selects a minimum-mass cohort from each source strongly connected component, with optimum mass $\sum_{C\in\mathcal C_{\mathrm{src}}}\min_{q\in C}\mu_q$. The associated decision problem belongs to $\mathrm{P}$. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 4
statement extracted from the paper’s text layer
Given a finite directed cohort graph \(H=(Q,E)\) with positive rational masses \(\mu_q\) summing to \(1\), where each cohort has a shared epistemic state and an activated edge updates the receiving cohort together, and a satisfiable non-tautological target formula \(\varphi\), add a campaign source holding \(\varphi\) with edges to a chosen set \(S\subseteq Q\). What set \(S\) of minimum mass \(\sum_{q\in S}\mu_q\) makes \(\varphi\) unanimously accepted in every admissible run, for every BFN with cohort graph \(H\)?
A distribution \(\mu\) over homogeneous cohort types represented as nodes of a finite directed graph; the decision is which whole cohorts to target, and the objective is to minimize targeted population mass. Success is universal unanimous acceptance of \(\varphi\) across admissible runs and BFN instances on that graph.
The paper does not establish cohort-wide synchronized updates as part of its BFN semantics, so the mirror depends on authors accepting cohesive communities as BFN agents; the proponent identifies this assumption but cannot establish how broadly it would be accepted.
fatal: False
Covers Corollary 4’s optimal influence result with cohort-level mass costs; leaves the convergence and stability results, other belief-change properties, and experiments unmirrored.
I think the strongest case is a narrow mirror of the paper’s bribery result, not of its entire theory of belief dynamics. The anchor is Corollary 4, proved here as a consequence of Proposition 8 and the polynomial-time computation of source strongly connected components. It says that, for a given acquaintance graph \(G\), a minimum-cost influence scheme that succeeds for a target formula \(\varphi\) can be computed in time polynomial in \(|G|\). In the paper, cost is the number of agents targeted, and success means that \(\varphi\) is unanimously accepted in every bribed BFN with that graph.
A plausible high-multiplicity setting is a large information network organized into communities: for example, residents grouped by institutions or local communication channels during an emergency. A type \(q\) represents a cohort whose members share the same initial epistemic state, improvement operator, network role, and targeting arrangement. Its mass \(\mu_q\) is its fraction of the population. There may be millions of residents but only \(\tau\) such cohorts. Communication is represented between cohorts, and an activated message updates the receiving cohort together. That last feature is a deliberate community-level version of the paper’s update process.
My lead question is Mass-Minimum BFN Influence. An instance consists of a finite directed cohort graph \(H=(Q,E)\), positive rational masses \((\mu_q)_{q\in Q}\) summing to \(1\), and a satisfiable, non-tautological target formula \(\varphi\). Add a campaign source whose belief is \(\varphi\). Choose a set \(S\subseteq Q\) of cohorts to target, adding an edge from the source to each selected cohort. A solution is a set \(S\) of minimum total mass such that \(\varphi\) is unanimously accepted in every admissible run, for every BFN with cohort graph \(H\). Its cost is
\[ \min_{S\subseteq Q}\ \sum_{q\in S}\mu_q. \]
This retains the paper’s intervention and success criterion while measuring the cost in affected population mass. By Proposition 8, success holds exactly when \(S\) intersects every source SCC of \(H\). So an optimal solution chooses a minimum-mass cohort from each source SCC, with total cost \(\sum_{C\text{ source SCC}}\min_{q\in C}\mu_q\). I expect this mirror to be tractable: compute the source SCCs and compare the rational masses, in time polynomial in \(|Q|\) and their bit length. The underlying question is which communities must receive the campaign so that the target belief becomes universally accepted; the graph characterization supplies the answer.
The scope is just the optimal influence or bribery result. The paper’s convergence and stability results, its general belief-change properties, and its experiments are not anchors for this mirror. The paper provides no named hardness result to anchor a claim about hardness disappearing under continuization.
The weakest point is the community-level update assumption. In the paper, an edge activation changes one named receiver; here it changes a whole cohort. That co-modification makes mass a meaningful intervention cost and keeps the source-SCC argument intact, but it is a real modeling choice. If individual members of a cohort update independently, targeting a negligible fraction may not be enough to influence the whole cohort, and the paper’s characterization does not settle that model. I’d present this as a credible, specific regime for the authors’ bribery question, rather than as a general continuous version of BeliefFlow.
Corollary 4 is a genuine computational result, so the “nothing here to mirror” argument is unavailable. The strongest objection is to the proposed mirror’s unit of intervention. In a BFN, an activated edge sends one agent’s beliefs to one receiver. The proposed cohort graph instead lets one edge activation update an entire positive-mass group. That changes the asynchronous interaction model: its result depends on batch communication between groups, not on scaling up the paper’s individual-to-individual process. The paper’s guarantee also relies on a finite edge set whose edges recur in every B-run; an infinite population of individual interactions cannot retain the same uniform positive lower bound on every edge.
There is a cost mismatch too. Proposition 8 requires targeting one agent in each source SCC. If a large connected network has only a bounded number of source SCCs, the minimum targeted fraction is \(s_n/n\), where \(s_n\) is their number, and tends to zero. Targeting an entire type avoids that collapse only by requiring a group-wide intervention the original bribery model does not require. Allowing an arbitrary fraction of a type to be targeted restores the individual-level action, but may leave some source SCCs untouched—and in an atomless model there may be no minimum positive fraction that reaches every component.
The best repair is a repeated-module regime: take \(k\) copies of the same \(r\)-agent network module, each with a source SCC. The discrete optimum targets one agent per module, so the population share targeted is \(1/r\). Targeting the same role across all modules can represent that share with a small set of types. This is a plausible high-multiplicity setting, and it avoids the zero-cost objection. But an exact continuous account still needs to specify how each module’s separate asynchronous process is represented, and whether success means unanimity in every module or convergence for almost every module. In the infinite-population limit, the paper’s single global B-run does not supply those semantics automatically.
So I can reject the analyst’s cohort-graph formulation as written, but I cannot honestly rule out a worthwhile mirror in every scenario. Repeated network modules are a credible regime, and a careful continuous model of them may preserve the bribery question with a positive mass cost. My negative case is weak at precisely that point: unless the authors would reject such a regime, Corollary 4 remains a live, narrow candidate for a continuous mirror.
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.