Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

The strongest positive case is a high-multiplicity version of the paper’s minority-seeding problem. I would use Theorem 2 as the lead anchor and Theorem 3 as a secondary one.

Consider a large social platform organized into finitely many repeated interaction roles: communities, departments, or cohorts. Let \(H=(T,F)\) be a finite connected “role graph”. Every role \(t\in T\) contains a large mass \(\mu_t\) of agents, with \(\sum_t\mu_t=1\). Agents in role \(t\) are connected to every agent in an adjacent role \(u\), and to no agents in nonadjacent roles. Thus all agents of a role have the same interaction environment. The intended regime is \(N\gg |T|\): millions of agents but only a moderate number of repeated roles.

This is a genuine high-multiplicity model, not merely a probability distribution pasted onto an unrelated graph. If each \(\mu_t\) is rational, choose \(q\) clearing all denominators and replace role \(t\) by \(q\mu_t\) twin agents. The resulting finite graph is a blow-up of \(H\). A mass \(x_t\) of role \(t\) holding opinion \(1\) corresponds to \(qx_t\) ordinary agents holding opinion \(1\). One-agent flips become mass transfers of size \(1/q\), and the limit \(q\to\infty\) gives the continuous process.

For \(x\in[0,\mu]\), define

\[ p_t^1(x)=\sum_{u:\{t,u\}\in F}x_u, \qquad p_t^0(x)=\sum_{u:\{t,u\}\in F}(\mu_u-x_u). \]

A mass of opinion \(0\) in role \(t\) is unstable when \(p_t^1(x)>p_t^0(x)\); a mass of opinion \(1\) is unstable when the reverse strict inequality holds. A legal \(0\to1\) move transfers some rational amount \(\lambda>0\) from \(\mu_t-x_t\) to \(x_t\) whenever \(p_t^1(x)>p_t^0(x)\). The analogous \(1\to0\) move is defined symmetrically. Applying the paper’s two-phase \(\max_1\) convention gives a continuous majority-diffusion closure: first perform legal \(0\to1\) moves until none is available, then perform legal \(1\to0\) moves until stability.

The type is therefore the complete interaction role, not merely the current opinion. Opinion remains a binary state that can differ among members of the same role. This is exactly what makes the model a population continuization rather than a finite graph with renamed vertices.

The lead anchor is Theorem 2, proved in this paper. Its full content is:

For every fixed rational \(0<\alpha<\frac12\), \(\mathrm{CONSENSUS}[\alpha]\) is NP-hard.

Here \(\mathrm{CONSENSUS}[\alpha]\) takes an undirected graph \(G=(N,E)\) and asks for a configuration \(c\) with at most \(\lceil\alpha |N|\rceil\) agents initially holding opinion \(1\), such that \(\max_1(c)\) is the all-\(1\) consensus configuration. The paper proves this by reducing from Vertex Cover, first using a cubic graph and two pendant vertices per original vertex, then adding gadgets to handle every fixed value of \(\alpha<\frac12\).

I would mirror it with the following precise problem.

Call it Continuous Minority Consensus, \(\mathrm{CMC}_\infty[\alpha]\). An instance consists of a finite role graph \(H=(T,F)\), rational masses \(\mu_t>0\) summing to \(1\), and a fixed rational \(0<\alpha<\frac12\). The task is to decide whether there is an initial state \(x^0\in[0,\mu]\) satisfying

\[ \sum_{t\in T}x_t^0\le \alpha \]

and a legal continuous majority-diffusion trajectory whose \(\max_1\)-closure is the all-\(1\) state \(x_t=\mu_t\) for every \(t\). A yes-solution consists of the initial mass vector and a finite sequence of legal mass transfers witnessing consensus; a no-instance has no such initial state. Equivalently, one can minimize the initial opinion-\(1\) mass and ask whether the optimum is at most \(\alpha\).

This is recognizably the authors’ problem. It preserves binary opinions, the same local-majority rule, asynchronous updating, the same target consensus, and the same minority resource constraint. The only substantive change is that repeated agents are represented by masses and individual flips by infinitesimal or fractional cohort updates. An external manipulator is still asking exactly the paper’s question: what is the smallest minority that can force consensus?

I would expect \(\mathrm{CMC}_\infty[\alpha]\) to be either Class A or Class C, with Class C my current preference. The paper’s Vertex Cover reduction does not automatically transfer: in the continuous model, a role can contribute a fractional amount of initial opinion \(1\), so the integral choice of whether a vertex belongs to the cover disappears. That is precisely the kind of population-multiplicity hardness that continuization may dissolve. On the other hand, activation order and strict majority conditions produce a finite-dimensional threshold-flow problem with disjunctive constraints, so hardness could survive for continuum-specific reasons even after fractional seeding is allowed. The first serious algorithmic question is whether the minimum seed mass admits an LP, flow, or separation formulation.

My secondary anchor is Theorem 3, also proved in the paper. It states:

For every \(\delta\in(0,1)\) and every \(\varepsilon\le \frac12-\frac{\delta}{4}\), it is NP-hard to decide whether there is a configuration \(c\) such that
\[ > |N_{1/c}|=\lceil\varepsilon n\rceil > \]
and
\[ > \max_1(c)\ge (2+\delta)\lceil\varepsilon n\rceil. > \]

Thus the question is not necessarily full consensus. It asks whether an initially small minority can at least more than double its support under majority diffusion. The paper proves this by a separate reduction from \(\textsc{2P3N-3SAT}\), rather than by extending the Vertex Cover reduction used for Theorem 2.

The corresponding continuous problem is Continuous Minority Amplification, \(\mathrm{CMA}_\infty(\varepsilon,\delta)\). Its instance is \(H=(T,F)\) together with rational masses \(\mu\). It asks whether there exists \(x^0\in[0,\mu]\) with

\[ \sum_{t\in T}x_t^0=\varepsilon \]

and a legal \(\max_1\)-diffusion trajectory ending at a stable state \(y\) satisfying

\[ \sum_{t\in T}y_t\ge (2+\delta)\varepsilon. \]

A solution is the initial mass assignment together with the mass-transfer trajectory and its terminal state. The parameter condition ensures that the requested amplified mass remains below \(1\).

This is a distinct mirror rather than a restatement of the first one: it studies amplification to a prescribed threshold, not the special endpoint of all-\(1\) consensus. I would again expect Class C, though Class A is plausible. The original \(\textsc{2P3N-3SAT}\) encoding relies on discrete gadget choices, so hardness transfer is not automatic once role masses can split. But the continuous process still has to coordinate activation across several interacting roles, and that coordination may itself be continuum-specific hard.

The mirror deliberately does not claim to cover every result in the paper. In particular, I would not use Theorem 4 as a primary anchor without changing the question substantially. Its naive continuous stable-state analogue collapses: setting \(x_t=\mu_t/2\) for every role makes every role see a tie, so a non-consensus stable state exists for essentially every instance. That is a useful warning about why the minority budget in Theorems 2 and 3 matters.

The weakest point is therefore clear: the paper’s hardness reductions manipulate named, indivisible vertices, while a true continuum permits fractional masses within a type. If the reduction’s combinatorics disappear under that relaxation, then these mirrors may become tractable—or even degenerate under a careless definition. But that is not a reason to reject the mirror. It is exactly the central ChoCo question: does the computational obstruction come from population multiplicity, or from the interaction topology and activation logic themselves? These two problems preserve enough of the authors’ original diffusion problem to make that question precise.