| paper | Majority-based Preference Diffusion on Social Networks |
| authors | — |
| venue | AAMAS 2024 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has named convergence and probabilistic theorems, but none asserts the complexity, solvability, hardness, or approximation of a computational input problem. The proponent expressly concedes this, and a plausible continuous analogue cannot create the missing computational anchor. The Random-PD high-multiplicity law is recognizable, but insufficient under the stated rule.
fails bit a — no named computational result to mirror
The proposed mirrors cover Theorem 3.5's expander convergence statement and Theorem 4.1(1)–(2)'s consensus law; they leave the other convergence, cost, solution-count, countermeasure, and experimental results untouched.
The strongest honest positive case is conditional. Strictly speaking, this paper contains no numbered theorem asserting NP-hardness, membership in \( \mathrm P \), FPT, W[1]-hardness, approximation, or a runtime algorithm for a formally stated input problem. The only NP-hardness statement is an unnumbered remark in the experiments section about other models. Thus, under ChoCo’s narrow named-computational-anchor rule, the paper has no qualifying anchor.
If named exact and quantitative algorithmic results are admitted, however, two recognizable mirrors are defensible. I would not stretch to claim more.
The natural regime is a large online society partitioned into finitely many repeated network roles: for example, community, degree class, and interaction pattern. Let \(R\) be the finite set of roles, \(A\) the alternatives, and \(\mathcal L(A)\) the rankings. A complete continuous type is \(t=(r,\sigma)\), where \(r\in R\) specifies the agent’s degree and neighbour-type distribution and \(\sigma\in\mathcal L(A)\) specifies its ranking. The population is given by rational masses \(\mu_{r,\sigma}\), with \(\rho_r=\sum_\sigma\mu_{r,\sigma}\). A mixing matrix \(K\) specifies the fraction of neighbours of role \(r\) lying in role \(s\). For an undirected network limit it should satisfy detailed balance
\[
\rho_r d_rK_{rs}=\rho_s d_sK_{sr}.
\]
The intended regime has \(N\gg |R|\lvert A\rvert!\): many exchangeable users per structural/preference type, with graph sequences or block-regular networks realizing the same type data.
My lead is Expander-SPD\(_\infty\), mirroring Theorem 3.5, proved by the authors here with some details deferred to the full version [36].
An instance consists of \(A\), \(R\), rational \(\mu_0\), a rational reversible kernel \(K\), a target order \(\succ^\star\), constants \(\epsilon,\delta>0\), and a horizon \(B\). The normalized nontrivial eigenvalue of \(K\) is promised to satisfy \(\lambda(K)\le\beta\), for the sufficiently small constant \(\beta\) required by Theorem 3.5.
For each role \(r\), define the neighbour-level frequency
\[
H_{r}(a,b)=
\sum_s K_{rs}
\sum_{\sigma:a\succ_\sigma b}
\frac{\mu_{r,\sigma}}{\rho_r}.
\]
The synchronous continuous diffusion map \(F\) is defined exactly as follows. Every mass element of type \((r,\sigma)\) chooses an unordered pair of alternatives uniformly. If that pair is adjacent in \(\sigma\), and its current relative order disagrees with the strict majority indicated by \(H_r(a,b)\), it swaps; otherwise it stays unchanged. Since the population is continuous, the fraction choosing each pair is deterministic, so \(F(\mu)\) is a finite-dimensional mass update.
The problem asks for
\[
t_\delta=\min\left\{t:
\sum_{r}\mu^t_{r,\succ^\star}\ge 1-\delta
\right\},
\qquad \mu^t=F^t(\mu_0),
\]
or, equivalently, whether \(t_\delta\le B\). The solution is the exact trajectory certificate up to time \(t_\delta\), or a NO answer.
The continuous \(\epsilon\)-Condorcet premise is
\[
\sum_{r,\sigma:a\succ_\sigma b}\mu_{r,\sigma}
>
\sum_{r,\sigma:b\succ_\sigma a}\mu_{r,\sigma}
+\epsilon
\]
for every \(a\succ^\star b\). The expected result is Class A under the explicit finite-type representation: evaluating one update is polynomial in \(|R|\lvert A\rvert!\), and Theorem 3.5 predicts
\[
t_\delta=O(\log(1/\delta)).
\]
For a finite rational lift with denominator \(N\), taking \(\delta=1/N\) recovers the paper’s \(O(\log N)\) convergence statement up to the usual high-probability sampling error.
This is recognizable to the authors because it preserves both ingredients of Theorem 3.5: a population-level Condorcet margin and an expander-like interaction structure. It is not merely “opinions become fractional.” The network kernel remains part of the instance, and the computational question is winner convergence in a repeated-agent society.
The main follow-up questions are whether the spectral promise can be checked efficiently for succinct kernels, whether the \(O(\log(1/\delta))\) bound is tight for all typed expanders, and what happens when \(\lambda(K)\) is close to the threshold. A campaign version would add intervention variables \(z_{r,k}\) specifying what mass is initially forced to place a desired alternative in position \(k\), and would minimize \(\sum_{r,k}(\lvert A\rvert-k)z_{r,k}\) subject to reaching a prescribed \(\delta\)-consensus level.
The second, and in some ways more exact, mirror is Random-PD Winner Law\(_\infty\), anchored in Theorem 4.1(1)–(2), proved in the paper. I would regard this as a supporting anchor because its continuous stochastic interpretation needs more care.
For a type \((r,\sigma)\), let \(p_{r,\sigma}=\mu_{r,\sigma}/\rho_r\). In the continuum random-copy process, an agent of role \(r\) copies a neighbour’s ranking with probability \(q\), and otherwise keeps its ranking. The aggregate update is
\[
p^{t+1}_{r,\sigma}
=
(1-q)p^t_{r,\sigma}
+
q\sum_sK_{rs}p^t_{s,\sigma}.
\]
Let
\[
\pi_r=\frac{\rho_rd_r}{\sum_s\rho_sd_s}
\]
be the stationary degree-weighted role distribution. The problem is: given rational \((\rho,d,K,\mu_0)\), compute the terminal law \(Q\) of the consensus order, or decide whether a specified order \(\sigma^\star\) has probability at least \(\theta\). The exact solution is
\[
Q_{\sigma}
=
\sum_r\pi_rp^0_{r,\sigma}
=
\frac{\sum_r d_r\mu_{r,\sigma}}
{\sum_r d_r\rho_r}.
\]
For the pairwise query appearing explicitly in Theorem 4.1,
\[
Q_{a\succ b}
=
\sum_{\sigma:a\succ_\sigma b}Q_\sigma
=
\frac{\sum_{r,\sigma:a\succ_\sigma b}d_r\mu_{r,\sigma}}
{\sum_r d_r\rho_r}.
\]
This is plainly Class A: it is a weighted sum followed by exact rational comparison. It directly replaces the paper’s
\[
\frac{Z^0_{ab}}{2m}
\]
by its mass analogue. The authors should recognize it as their theorem in high-multiplicity notation, since the degree-weighted initial mass is already the invariant quantity in their proof.
The important qualification is that an atomless random-copy process does not literally reach one global order in finite time. The correct interpretation is the limiting consensus law of finite high-multiplicity lifts, or equivalently the deterministic aggregate law whose value is \(Q\). Claiming that every continuum agent eventually adopts one order would be false. Further questions concern finite-\(N\) concentration around \(Q\), rates of approach to the role-homogeneous state, and what survives if the kernel is reducible.
I would not use Theorem 3.1 as an anchor: its lower bound is \(\sqrt n(\lvert A\rvert-1)\), which becomes only \(O(n^{-1/2})\) after normalizing population mass. Nor would I use the \(NS(C_n)\) part of Theorem 3.6: the number of fractional mass placements is generally uncountable, so “number of solutions” has no direct continuum meaning. A cyclic repeated-community campaign model could mirror the \(MC(C_n)\) formula, but that would be a weaker extension rather than a clean direct mirror.
The weakest point is therefore decisive: these are structurally natural continuous extensions, but the paper does not itself supply a qualifying complexity theorem. Moreover, exact graph topology and finite-population fixation are not determined by population marginals alone. The positive case survives only in the explicit repeated-role/block-network regime above. In that regime, Theorems 3.5 and 4.1 support a credible Class-A continuous diffusion programme; outside it, claiming a general continuous mirror of this paper would overstate the evidence.
The negative case is strongest before any modelling begins: this paper has no qualifying ChoCo anchor. Theorem 2.2, Theorems 3.1, 3.5, and 3.6, and Theorem 4.1 are asymptotic convergence, graph-structural, or probabilistic statements. None gives the complexity of a formally specified input problem, an exact or approximation algorithm, or a hardness result. The only NP-hardness claim is an unnumbered remark about other models. Thus, under the programme’s stated anchor rule, there is no computational result here to continuize.
The proposed Expander-SPD mirror does not repair that gap. Theorem 3.5 depends on the actual graph spectrum and on the geometry of every set of vertices whose rankings disagree with the target order. A role kernel \(K\) records only aggregate neighbour-type frequencies. Its eigenvalues are not the eigenvalues of the graph’s normalized adjacency matrix: graph modes orthogonal to the role partition are invisible to \(K\). Two graph sequences can have the same \((\rho,K)\), while one has strong expansion and the other has weakly communicating internal clusters. Detailed balance does not prevent this.
The same problem affects the update rule itself. Two vertices with the same degree, ranking, and neighbour-type distribution can have different neighbours’ interconnections, and hence different future local majorities. To make a type complete for this process, one must include its rooted neighbourhood, and generally arbitrarily deep neighbourhood information. For a generic graph sequence this produces \(n\) essentially distinct types, not a fixed finite type space with high multiplicity. The “continuous society” then merely stores the original graph as a spatial or graph-limit object.
There are only two apparent escapes. One can impose an equitable block structure strong enough that finitely many roles really are dynamically sufficient; but then the resulting \(F\) is a new lumped or mean-field process, not the process analysed in Theorem 3.5. Or one can replace exact neighbourhoods by independently sampled neighbours; that produces the displayed role-level recurrence, but changes the local-majority process into an annealed model. Neither construction is a continuous mirror of the theorem’s graph problem.
Nor does the proposed horizon problem supply the missing computational content. “Iterate the finite-dimensional map until \(1-\delta\) mass agrees” is an invented simulation problem, not an algorithmic result from the paper. The claimed \(O(\log(1/\delta))\) behaviour would require a new theorem for the chosen quotient model. The paper’s \(O(\log n)\) result concerns fixed finite graphs, actual local neighbourhoods, and high-probability random updates; it does not provide a high-multiplicity algorithm or a limit theorem from which that problem follows.
The Random-PD mirror has a more fundamental failure. In the finite process, Theorem 4.1 concerns the probability of a single absorbing consensus order. In an atomless population, random copying yields a deterministic mass evolution. At every finite time, multiple orders generally retain positive mass; the process does not reach one global order. The limits \(N\to\infty\) and \(t\to\infty\) do not commute: finite populations eventually choose one random order, whereas the continuum process retains a mixture and converges to a role-homogeneous mixture.
The quantity
\[
Q_\sigma=\frac{\sum_r d_r\mu_{r,\sigma}}{\sum_r d_r\rho_r}
\]
is therefore not the terminal consensus law of the continuum process. It is the conserved degree-weighted initial mass, or the law of a separately introduced global random variable. Calling that variable the final order moves the randomness from individual population dynamics into the outcome space, which is outside ChoCo’s population-continuization scope. Correlating all continuum agents’ randomness so that they collapse together would likewise add a new global coupling absent from the paper.
The campaign variant is not a better rescue. The minimum-cost problem controls particular vertices and relies on graph geometry. A controlled set of a given mass can be a dense influential core or a scattered collection with almost no influence. Those placements are indistinguishable to \(\mu\) but behave differently under the diffusion rule. The paper’s tight \(\sqrt n(\alpha-1)\) construction makes this especially clear: the influential clique has vanishing population mass, so its normalized cost tends to zero. Retaining its effect requires finite-size scaling and spatial graph information, not a mass-transfer model.
The resulting dichotomy is unavoidable. If topology is retained, agents are individuated by their network position and the high-multiplicity reduction disappears. If topology is quotiented out, the model becomes a new mean-field process whose theorems must be developed independently. If the finite consensus law is retained, the “continuum” is really a distribution over outcomes rather than a continuous society.
A graph-limit or mean-field paper inspired by this work could certainly be worthwhile elsewhere. But it would be a new analytic programme, not a computational continuous mirror of this paper. The only honest weakness in the negative case is that one could engineer a special block model and ask new algorithmic questions about it. That possibility does not rescue the present paper: it demonstrates that a related model can be invented, not that this paper supplies a worthwhile ChoCo continuization.
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.