| paper | Node Conversion Optimization in Multi-hop Influence Networks |
| authors | — |
| venue | AAMAS 2023 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 5.1
statement extracted from the paper’s text layer
Given a finite role set \(Q\), a role-level relational template \(H\) for measured dense blow-ups, rational masses \(\mu\in\mathbb{Q}_{\ge 0}^{Q}\) with \(\sum_{q\in Q}\mu_q=1\), normalized thresholds \(\theta:Q\to[0,1]\), and root-specific weighted \(k\)-hop views \(\Gamma_k(q)\) with local incidence measures \(\nu_q\), find a local \(r/s\) rule \(F\) maximizing \(\sum_{q\in Q}\mu_q\mathbf{1}[F(\Gamma_k(q))=r]\), subject to \(F(\Gamma_k(q))=r \Rightarrow\ \nu_q(\{p:F(\Gamma_k(p))=r\})\ge\theta(q)\) for every root role and every admissible measured blow-up in the template class. The bounded-template version additionally requires \(\max_q|N_k(q)|\le w\) for fixed \(w\).
A dense repeated-role influence system in which \(\mu_q\) is the mass of indistinguishable agents of role \(q\), \(H\) and \(\nu_q\) encode local block incidence, \(F\) maps weighted rooted views to \(r/s\), the objective is converted mass, and feasibility is local threshold safety.
The proponent does not fully reconcile the paper's universal safety quantifier with safety over an admissible typed-template class, and its displayed constraint uses global \(\mu_p\) where root-specific neighborhood mass is required.
fatal: False
The mirror covers the heterogeneous-threshold optimality result Theorem 5.1 and its uniform-threshold specialization Theorem 4.2, but leaves the unnumbered factorial running-time bound, synchronized multi-round variants, and future directions untouched.
The strongest honest case is a narrow but genuine mirror of Theorem 5.1. A caveat first: the paper contains no numbered theorem stating a complexity classification such as membership in P or NP-hardness. Its named computational results are optimality theorems. Theorem 5.1, “\(F_G^*\) is optimal in the General Threshold model,” is proved in this paper, not cited from elsewhere. Theorem 4.2, “\(F_U^*\) is optimal when the nodes have the same threshold value,” is a proved uniform-threshold special case. Theorem 5.1 is my lead anchor.
The natural regime is a large influence system built from repeated network roles: for example, a product-adoption or conference-attendance system with many repeated departments, communities, or shareholder groups. Agents in one role have the same threshold, the same \(k\)-hop structural position, and the same observable relationships to other roles. There may be \(n\) agents but only \(\tau\) distinct rooted role types, with \(\tau\ll n\). This is not a claim that arbitrary social networks are high-multiplicity; it is a claim about repeated organizational or community architectures.
The continuous population should not be represented merely by a distribution of isolated node descriptions. Local safety depends on how views overlap, so the instance must retain a typed network. Let \(Q\) be a finite set of role types, \(H\) a finite symmetric type-level network template, and \(\mu\in\mathbb{Q}^{Q}\) the mass distribution, where \(\mu_q\) is the fraction of agents of type \(q\). The corresponding society is a measured blow-up of \(H\): type \(q\) is a population block of mass \(\mu_q\), and type-level edges describe which blocks influence one another. A type contains the complete information relevant to the protocol: its threshold, rooted \(k\)-hop role structure, and all threshold labels visible in that structure.
Let \(\theta(q)\) be the normalized threshold of type \(q\). If the finite replicated system has threshold \(\Phi_n(q)\), the natural high-multiplicity scaling is \(\theta(q)=\lim \Phi_n(q)/n\). For \(A\subseteq Q\), write \(\mu(A)=\sum_{q\in A}\mu_q\). The weighted rooted \(k\)-hop view of \(q\) is denoted \(\Gamma_k(q)\), and \(N_k(q)\) is the set of types occurring in that view.
The lead problem is Continuous General-Threshold Multi-hop Protocol Optimization:
\[ \operatorname{CGTPO}_\infty(H,\mu,\theta,k) = \max_{F\in\mathcal{P}_{\mathrm{safe}}} \sum_{q\in Q}\mu_q\, \mathbf{1}\!\left[F(\Gamma_k(q))=r\right]. \]
Here \(F\) is a local decision rule mapping a rooted weighted \(k\)-hop view to \(r\) or \(s\). It must be protocol-safe on every admissible typed measured network, meaning
\[ F(\Gamma_k(q))=r \;\Longrightarrow\; \sum_{\substack{p\in N_k(q)\\F(\Gamma_k(p))=r}}\mu_p \geq \theta(q). \]
The solution is a universally protocol-safe local rule, or equivalently its induced \(r/s\) decision for every type in the given instance, together with the maximum converted mass. This preserves the paper’s essential question: agents make a one-shot decision from local information, cannot communicate, and the objective is to maximize conversion subject to safety. The centralized object is not an arbitrary selected subset of agents.
This is recognizably the same problem to the authors. The \(k\)-hop view, recursive visualizations, heterogeneous thresholds, and asynchronous local protocol remain. Only the multiplicity of indistinguishable nodes is compressed into mass. For rational \(\mu_q=n_q/n\), the problem is exactly the normalized version of a finite repeated-role blow-up. The weighted analogue of Algorithm 2 would replace cardinalities by masses, replace the integer counting loop by a scan over distinct threshold breakpoints, and replace the critical value \(\Phi^{F_G^*}\) by a critical convertible mass. Lemmas 5.1–5.3 suggest that the relevant monotonicity argument is order-theoretic and may survive this replacement.
I expect \(\operatorname{CGTPO}_\infty\) to be tractable in the bounded-template regime where each \(k\)-hop view contains at most \(w\) distinct role blocks for fixed \(w\). The recursion can then be evaluated over weighted view types, with arithmetic polynomial in \(\tau\) and the encoding length of \(\mu\) and \(\theta\). The continuous gain is precisely that the algorithm need not process \(n\) replicated agents individually. With unbounded view width, I would not claim a polynomial result: the paper’s \(O(E_{\max}!N_{\max}^2)\) evaluation bound indicates that the recursive topology may remain difficult. That unrestricted version is a natural place to test for continuum-specific hardness.
Theorem 4.2 gives a second, cleaner anchor: Continuous Uniform-Threshold Multi-hop Protocol Optimization is the same problem with \(\theta(q)=\theta\) for every \(q\). Its solution and safety condition are exactly the formula above under that restriction. I expect this version to be tractable in the same bounded-template regime, and it is a particularly credible mirror because Algorithm 1’s central test becomes simply a comparison between converted mass and the common threshold. I regard it as supporting evidence rather than an independent claim about the whole paper.
The weakest point is that the mirror needs a genuinely dense or group-level influence regime. If one merely replicates a sparse bounded-degree graph while keeping thresholds fixed, every finite \(k\)-hop neighborhood has vanishing population mass, and the continuum limit degenerates. The scenario therefore needs large communities or influence blocks whose thresholds scale with population mass. Also, a distribution over local views without the typed network structure \(H\) would be inadequate: it could destroy the correlations on which recursive safety depends. These are real restrictions, but they describe a plausible high-multiplicity instance regime rather than changing the question into a different one.
The main follow-up questions are whether the proofs of Lemmas 5.2 and 5.3 extend to weighted critical masses, whether the unrestricted typed version is polynomial, fixed-parameter tractable, or continuum-specifically hard, and how accurately finite replicated networks approximate the continuous optimum near threshold ties. This mirror covers the paper’s central optimality result, Theorem 5.1, and its uniform-threshold specialization, Theorem 4.2; it does not claim to continuize the paper’s separate future work on synchronized rounds or historical information.
The negative case starts with a scope problem. Theorem 4.2 and Theorem 5.1 are correctness and optimality theorems for local protocols, not complexity classifications. The paper gives a factorial-time evaluation bound and leaves polynomial-time solvability open, but it does not identify a numbered \(P\)/\(NP\)-type result for continuization to sharpen. The proposed \(\operatorname{CGTPO}_\infty\) therefore has to earn its place by becoming a genuine high-multiplicity computational problem, not merely by replacing a cardinality in an already-known protocol.
The central obstruction is that the paper’s safety condition is relational, not additive over agent types. For a node \(v\), safety is
\[ F(v,\Gamma_k(v))=r \;\Longrightarrow\; \sum_{u\in V_k(v)} \mathbf{1}\!\left[F(u,\Gamma_k(u))=r\right] \geq \Phi(v). \]
The quantity on the left is determined by the incidence structure of a rooted graph: which particular nodes lie in \(v\)’s \(k\)-hop neighbourhood, and what views those nodes have. It is not determined by the global distribution of node types. Two networks can have the same proportions of local-view types while arranging those types differently around one another, producing different safety constraints.
The proponent’s additional template \(H\) is therefore necessary, but it changes the nature of the object. If \(H\) records enough incidence information to recover all relevant overlaps, then the “society” is no longer a distribution over types. It is a finite relational network template together with weights. If \(H\) does not record that information, the proposed condition
\[ \sum_{p\in N_k(q)}\mu_p\geq\theta(q) \]
is simply not the original safety condition: \(\mu_p\) is the mass of an entire role class, whereas \(v\)’s neighbourhood contains particular members of that class, usually only a tiny subset.
There is also a quantifier mismatch. Theorem 5.1 concerns a protocol safe on every influence network. The candidate mirror instead makes safety relative to an “admissible typed measured network.” A protocol may exploit the fact that it is operating on a known block template, and the minimal-counterexample constructions used in the paper may no longer be admissible. If safety is retained over all finite graphs, the template cannot be used to certify decisions. If safety is restricted to the template class, the result is a new protocol problem, not a continuization of Theorem 5.1. The same issue arises if masses are included in a node’s weighted view: the original agent observes its local topology, not the global population proportions.
The usual high-multiplicity escape routes do not repair this cleanly. In a sparse repeated network, if the degree is \(o(n)\), then a \(k\)-hop neighbourhood has vanishing global mass. Scaling \(\Phi\) by \(n\) makes every positive-threshold conversion impossible in the limit; keeping \(\Phi\) integral preserves atomic finite-neighbourhood reasoning rather than producing a population-continuum problem. One can normalize by local neighbourhood size instead, but that changes the paper’s “at least \(\Phi(v)\) nodes” condition into a fractional-threshold model.
Alternatively, one can use dense graphs so that a local neighbourhood has positive population mass. But with finitely many repeated types, this essentially forces a block model in which nodes see whole role blocks or complete bipartite blocks. The arbitrary local topologies and recursive visualizations central to the paper disappear into a finite template. If one allows genuinely irregular dense networks, the appropriate object is a graphon or another infinite relational structure; then a finite type distribution \(\mu\) is insufficient, and agents generally have distinct structural positions rather than repeated complete types.
A distribution over repeated finite motifs is another possible construction. It preserves the paper’s finite local graphs, but then mass is only averaging over independent copies of finite instances. The safety constraints remain atomic inside each motif; the continuous population never enters the protocol. That is a mixture of finite network problems, not a continuous society in the sense ChoCo is trying to study, and it creates no new high-multiplicity optimization or pricing problem.
Theorem 5.1 has a further problem: its proof is built on finite combinatorial well-foundedness. The recursive calls strictly reduce the view by nodes or edges, and the proofs use minimal counterexamples and induction over \(|V|\) and \(|E|\). Replacing \(|S|\) by a measure does not preserve that structure. Removing one agent from a nonatomic block changes neither its mass nor its weighted view, so strict subviews can become measure-equivalent and the induction underlying Lemmas 5.2 and 5.3 disappears. A valid measurable fixed-point theorem might be developed, but it would be a new theory of protocols on measured relational structures, not the claimed weighted lifting of Algorithm 2.
Theorem 4.2 is not an escape. Making the threshold uniform removes heterogeneous labels but leaves intact the dependence on neighbourhood incidence, the sparse-versus-dense dichotomy, the information mismatch, and the finite-view induction. Its continuous version is either a passive mixture of finite motifs, a restricted finite block model, or a different fractional-neighbourhood model.
The honest weakness in this negative case is that one can deliberately define a finite catalogue of dense typed blow-ups and obtain a defensible weighted protocol problem. That would be mathematically legitimate. But it would either make mass passive, as in a mixture of finite networks, or replace the paper’s general influence networks by a finite block-template model. Neither supplies the intended continuous mirror of the paper’s computational content. The proponent has shown a possible weighted reformulation under strong extra structure, not a worthwhile population continuization of Theorems 4.2 or 5.1.
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.