| paper | Biased Majority Opinion Dynamics: Exploiting Graph k-domination |
| authors | Hicham Lesfari, Frédéric Giroire, Stéphane Pérennes |
| venue | IJCAI 2022 |
| filed under | frontier · opinion-networks |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | no |
The numbered Theorems 2 and 3 prove asymptotic bounds on stochastic-process rounds, not complexity results for named computational problems. The unnumbered NP-hardness remark is not an admissible anchor. The repeated-copy master equation is a coherent ensemble model, but it changes the continuized object and cannot repair the missing computational result.
fails bit a — no named computational result to mirror
The proposed construction targets Theorems 2 and 3 through repeated-network stabilization, while the unproved domination claim, experiments, and other structural results remain outside the mirror.
The strongest honest case is a topology-preserving high-multiplicity mirror. It is an extension of the programme’s basic \(\mu\)-model, because network relations must be retained; a distribution of opinions alone would erase the very feature this paper studies. The paper contains no numbered NP-hardness or polynomial-time algorithm theorem. Its unnumbered NP-hardness sentence in Section 4 is therefore not an anchor. The two usable anchors are Theorems 3 and 2, both proved in this paper.
The common mirror is a population of \(K\) repeated copies of a finite social-network template \(H\), with \(K\gg |V(H)|\). A type is a role \(v\in V(H)\), including its degree and its neighbours’ roles. Each role has mass \(\mu_v=1/|V(H)|\); equivalently, there are \(K\) indistinguishable agents of each role across the repeated copies. The action is still exactly the paper’s action: an agent holds opinion \(0\) or \(1\), and on update adopts \(1\) with probability \(\alpha\), otherwise adopting the neighbourhood majority. To preserve correlations created by shared neighbourhoods, the continuous state records \(\nu_z(s)\), the fraction of copies whose current configuration is \(z\in\{0,1\}^{V(H)}\). This is the necessary relational extension of a type-mass model, not a fractionalisation of opinions.
A precise common computational problem is therefore:
\[ \textsc{Continuum-Majority-Time}(H,\alpha,B,\eta): \]
given \(H\), rational \(\alpha\in(0,1]\), a bound \(B\), and accuracy \(\eta\), approximate the expected absorption time of a uniformly selected copy, \(\bar\tau_H(\alpha)\), within additive error \(\eta\), or decide whether \(\bar\tau_H(\alpha)\le B\). The distribution \(\nu(s)\) evolves by the finite-state master equation induced by the paper’s asynchronous updates. Thus
\[ \bar\tau_H(\alpha) = \int_0^\infty \bigl(1-\nu_{\mathbf 1}(s)\bigr)\,ds, \]
where \(\nu_{\mathbf 1}(s)\) is the mass of fully stabilized copies. For finite \(K\), this is the expected stabilization time of a uniformly sampled network copy; the \(K\to\infty\) limit replaces individual randomness by mass evolution. One may also ask for the \(\varepsilon\)-consensus time
\[ \Theta_{\varepsilon,H}(\alpha) = \inf\{s:\nu_{\mathbf 1}(s)\ge 1-\varepsilon\}. \]
This avoids the meaningless requirement that an atomless population become literally unanimous.
My lead anchor is Theorem 3, proved here: for a random regular graph of odd degree \(\Delta\), there is \(\alpha_\Delta>0\) such that, for \(\alpha<\alpha_\Delta\), the expected stabilization time is exponential. Its continuous mirror is Continuum Random-Regular Metastability: take \(H\) from the paper’s random \(\Delta\)-regular configuration model, repeat that network type with arbitrarily large multiplicity \(K\), and compute or decide whether
\[ \bar\tau_H(\alpha)\ge \exp(r|V(H)|) \]
for a given \(r>0\). The solution is a mass-level metastability certificate: a positive fraction of network copies remains outside the all-\(1\) configuration for exponentially long expected time.
This is recognisably the authors’ problem. The type mass does not replace majority influence by an average opinion, and the graph topology is not discarded. The many agents are repeated cohorts with the same contact roles: for example, many online communities, departments, or local social modules with an identical bipartite communication architecture. The number of people is \(K|V(H)|\), while the number of distinct roles is only \(|V(H)|\). The paper’s decreasing-set argument becomes a statement about a positive mass interval in which every active configuration has strictly smaller majority-dominated mass. The exponential barrier is therefore not caused by naming individuals; it is caused by the network’s expansion and majority geometry.
I expect the exact general version to be hard for topology-preserving reasons—Class B-like rather than continuum-specific. Concentrating the mass on one network template and taking many clones recovers the original dynamics, so any future computational hardness in the graph structure survives continuization. For the highly symmetric random-regular family, however, the qualitative question “is the exponent positive?” may be Class A: the paper already reduces the relevant calculation to entropy expressions such as \(F(\sigma,\tau)\) and \(G_\beta(\sigma)\). Natural follow-up questions are to compute the exact metastable exponent, close the gap between \(\alpha_\Delta\) and the empirical transition, and determine whether typed or nonhomogeneous network populations produce a genuinely Class C problem.
The second anchor is Theorem 2, also proved here: for every cubic graph \(G\),
\[ \mathbb E[\tau_\alpha(G)] = O\!\left(n^{3-O(\log\alpha)}\log^2 n\right). \]
Its mirror is Continuum Cubic-Cohort Stabilization: given a cubic template \(H\), a rational bias \(\alpha\), and rational \(\varepsilon\), compute or approximate \(\Theta_{\varepsilon,H}(\alpha)\), the time by which at least \(1-\varepsilon\) of repeated cubic-network cohorts have reached all-\(1\) consensus. Here the roles are the cubic vertices, mass is the fraction of repeated copies occupying each role/configuration, and the objective is exactly the paper’s stabilization objective at population scale.
The stable cycles and paths used in the proof give a credible Class A direction for polynomial upper bounds on this continuous problem: the same stable-cover certificate can be applied to the role template, and Theorem 2 supplies the polynomial dependence on \(|V(H)|\) and \(\alpha\). I would not claim that exact computation of \(\bar\tau_H(\alpha)\) is already in P—the configuration space has size \(2^{|V(H)|}\), and Theorem 2 proves a bound, not an evaluation algorithm. The honest claim is that the mass-level polynomial-stabilization question has a strong tractability prospect, while exact expected-time computation remains open.
My weakest point is that this is not a pure \(\mu\)-only mirror. Shared network topology creates correlations, so a referee who insists that a society must be represented solely by marginal type masses could reject the construction. But removing the relational state would also remove the paper’s question: cubic stability and random-regular decrease are properties of neighbourhood structure, not of opinion proportions. The repeated-network/cohort model keeps the population genuinely high-multiplicity while retaining precisely the topology that the authors’ Theorems 2 and 3 analyse.
The strongest negative case is that this paper does not actually contain a computational result in ChoCo’s sense. Theorems 2 and 3 are asymptotic statements about the absorption time of a stochastic process on a given finite graph. They provide no input/output problem, algorithm, complexity bound, reduction, or approximation task. The one NP-hardness statement in Section 4 is an unproved aside about a static domination problem, not a result about the opinion dynamics. Thus the proposed continuous problems have to be invented rather than obtained by continuizing a computational result of the paper.
The proposed repeated-copy construction does not repair that gap. Let \(H\) be a finite graph and take \(K\) independent copies of it. As \(K\to\infty\), the empirical distribution \(\nu\) over configurations of \(H\) converges to the law of the finite Markov chain on \(H\). This is a perfectly well-defined master equation, but it is not a continuous population version of the paper’s society. It is an ensemble of repeated finite experiments. The continuous parameter is the number of copies, whereas the paper’s relevant parameter \(n\)—the number of interacting agents in one graph—remains \(|V(H)|\).
That distinction matters computationally and structurally. If \(H\) is fixed, the exponential dependence in Theorem 3 disappears because \(\exp(r|V(H)|)\) is just a constant; increasing \(K\) does not create the paper’s metastable barrier. If \(H\) grows, then the exact state \(\nu\) has \(2^{|V(H)|}\) coordinates, so the continuous limit has not compressed the relevant population at all. It has merely replaced repeated simulation by the exact distribution of the same exponentially large finite chain. Any finite Markov chain could be “continuized” in this way by taking infinitely many replicas. That makes the construction a generic law-of-large-numbers transformation, not a meaningful population continuization.
Theorem 3 is especially resistant to a genuine mass formulation. Its lower bound is driven by global properties of a sparse random regular graph: every sufficiently small linear active set is decreasing. Those properties live in the graph’s extensive connectivity and expansion, not in the marginal mass of vertex roles. A role distribution \(\mu\) cannot determine whether two agents sharing a role belong to the same copy or whether their neighbours have correlated opinions. To recover that information one must retain the distribution over whole graph configurations, which is precisely the exponential \(\nu\)-state above.
The obvious stronger repair also fails to preserve the theorem. Connecting \(K\) copies through complete role classes makes role masses close under a mean-field description, but degrees grow with \(K\), so the fixed-degree random-regular model and its decreasing-set argument disappear. Connecting clones through fixed-degree matchings gives a graph lift; then local correlations and copy-specific neighbourhoods reappear, and marginal masses no longer close. Taking an infinite sparse limit yields a graphing or infinite random regular tree, on which “all agents have reached opinion \(1\)” is not the finite-graph absorption event at all. Replacing it by an \(\varepsilon\)-density criterion is legitimate as a new opinion-dynamics question, but it is not a mirror of Theorem 3’s global stabilization time.
Theorem 2 has the same problem in a different form. Its proof relies on cycles and paths of length \(O(\log n)\) covering a finite cubic graph. In a genuine \(n\to\infty\) population limit, each such stable structure has vanishing mass. It cannot itself serve as a positive-mass stabilization certificate. Asking when \(1-\varepsilon\) of the population has stabilized requires tracking many overlapping structures and their dependencies, which returns us to the original finite graph rather than producing a closed continuous model. Repeating a fixed cubic template only yields the distribution of the template’s finite Markov chain; taking larger connected cubic lifts restores the original discrete problem.
There is a coherent neighbouring project here: study a population of repeated social-network instances, or develop graphing and sparse-network limits for biased majority dynamics. But that continuizes the number of networks or the probability law over finite configurations, not the population of agents whose interactions Theorems 2 and 3 analyse. If that broader object is admitted, the proponent has identified a valid new model. Under ChoCo’s population-continuization criterion, however, neither anchor supplies a worthwhile mirror: Theorem 3 becomes an ensemble restatement, and Theorem 2 loses its finite structural witness in the limit.
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.