| paper | Eliminating Majority Illusion |
| authors | — |
| venue | AAMAS 2025 |
| 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 1
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational society masses \( \mu_t \), initial labels \(b_t \in \{0,1\}\), a rational row-stochastic interaction matrix \(A=(a_{ut})\), and a budget \(K\), decide whether there exist \(p_t \in [0,1]\) such that \( \sum_t a_{ut}p_t \le \frac{1}{2} \) for every \(u\), and \( \sum_t \mu_t |p_t-b_t| \le K \), with \( \sum_t \mu_t b_t < \frac{1}{2} \).
A block-regular high-multiplicity network with types \(t\), mass \( \mu_t \), initial opinion \(b_t\), and fixed neighbourhood proportions \(a_{ut}\); decision variables \(p_t\) give final opinion-1 mass within each type, and the objective minimizes \( \sum_t \mu_t |p_t-b_t| \).
The constraints \( \sum_t a_{ut}p_t \le \frac{1}{2} \) are not implied by high multiplicity alone: bounded-degree lifts can have local fluctuations, so exact feasibility requires an additional block-regular or balanced-exposure assumption.
fatal: False
The mirror covers the static minimum-relabeling EI problem and the intervention hardness anchor in Theorem 1, but leaves the paper's arbitrary-graph reductions, structural-parameter results, TVD equivalence, and planar PTAS untreated.
The strongest positive case is a mirror of the paper’s central static problem, EI, with population multiplicity and intervention mass made continuous. My lead anchor is Theorem 1, proved in this paper: EI is NP-hard and W[2]-hard when parameterised by the solution size, even on bipartite graphs of bounded diameter.
Call the mirror Continuous Eliminating Illusion, \( \mathrm{CEI}_{\infty} \). A type \(t\in T\) is a complete network role: its initial opinion \(b_t\in\{0,1\}\), and its neighbourhood profile. The society is a rational mass vector \(\mu\), where \(\mu_t\) is the fraction of agents of type \(t\), with \(\sum_t\mu_t=1\) and \(\sum_t\mu_tb_t<1/2\). The intended regime is \(N\gg\tau=|T|\): for example, a large online or organisational network built from a fixed number of recurring communities, roles, or cohorts. Every member of a type has the same proportions of contacts with the other types.
Formally, the instance also contains a rational matrix \(A=(a_{ut})\), where \(a_{ut}\) is the fraction of a type-\(u\) agent’s neighbourhood occupied by type \(t\), with \(\sum_ta_{ut}=1\). For an undirected regular lift, one may additionally impose the usual edge-balance constraints. An intervention chooses \(p_t\in[0,1]\), the final fraction of type \(t\) holding opinion \(1\). Its cost is the mass relabelled, \( \sum_t\mu_t|p_t-b_t| \). The question is whether there is a feasible \(p\) of cost at most a given rational \(K\), where no type experiences an illusion:
\[ \sum_{t\in T} a_{ut}p_t\le \frac12 \qquad\text{for every }u\in T. \]
Equivalently, \( \sum_t a_{ut}(2p_t-1)\le0 \). A solution is the vector \(p\), or equivalently the mass relabelled in every type. As in the discrete problem, an optimum never needs to change a \(0\) into a \(1\): doing so only worsens the constraints and increases cost.
This is recognisably the authors’ problem. Opinion remains binary; the local-majority condition is unchanged; the action is still relabelling agents; and the objective is still minimum intervention. Only the granularity of the population has changed. A finite regular lift with \(N\mu_t\) agents of type \(t\) gives the discrete version, while rational \(p_t\) values can be implemented by relabelling the corresponding fraction of each cohort, up to the usual rounding error. This is a genuine population continuization, not continuity of opinions, time, outcomes, or diffusion dynamics.
The continuous problem is an LP: introduce variables for the absolute-value costs and retain the linear local-majority constraints. Hence \( \mathrm{CEI}_{\infty} \) is solvable in polynomial time in \( \tau \) and the encoding length of \(A,\mu,b,K\). Theorem 1’s Set Cover reduction explains why this is not merely an arbitrary simplification. Its hard choices are whether to relabel an entire set vertex. In the mirror, those choices become fractional masses \(x_s\), and the reduction becomes a fractional-cover LP: each universe type requires sufficient relabelled mass among its neighbouring set types. The combinatorics driven by indivisible agents disappear, while the paper’s local influence objective remains.
Thus I expect this anchor to be Class A. The paper’s NP-hardness and W[2]-hardness do not transfer because their essential integrality lies in population multiplicity. This is exactly the kind of boundary the continuization programme is meant to expose: the discrete network intervention problem is hard, while its high-multiplicity mass version is a linear optimization problem. The paper’s own Theorem 3, whose proof aggregates twin vertices and solves a bounded-variable integer program, is further evidence that type aggregation is structurally native to EI, although I would not use it as a separate anchor.
The main further questions are whether every rational LP solution has an exact or \(O(1/N)\)-additive realization in a finite regular network; how the result changes with type-dependent intervention prices or eligibility restrictions; and whether hardness returns when one requires whole types to be relabelled rather than allowing mass within a type to be split. Sequential majority cascades would produce a different, dynamic problem and are outside this particular mirror.
The weakest point is that the mirror replaces an arbitrary sparse graph by a type-regular, weighted neighbourhood structure. In a real sparse social network, two agents with the same broad role may still have different named neighbours, and balanced fractional relabelling may not be implementable exactly. The case survives because the paper’s static feasibility condition depends only on neighbourhood opinion counts, and large recurring cohorts with regularised exposure are a plausible regime for campaigns, platforms, and organisational networks. But this should be presented as a mirror for EI on high-multiplicity role-structured networks—not as a claim that every arbitrary graph instance has a faithful atomless limit.
The strongest objection is that \( \mathrm{CEI}_{\infty} \) is not quite a continuization of EI; it is a mean-field fractional relaxation of a different, highly regular network problem.
In EI, the graph is not merely a distribution of agent roles. Its incidence pattern is the computational object. A vertex \(v\) appears simultaneously in the constraints of every neighbour, and changing \(v\)'s label is paid for once but affects all those constraints. If a type \(t\) contains many agents, the fraction \(p_t\) of relabelled agents does not determine what every neighbouring agent sees. It determines only an average. In a finite-degree lift, different neighbourhoods can contain different numbers of relabelled type-\(t\) agents, and EI requires every vertex to lose its illusion. Even as the number of copies tends to infinity, local fluctuations do not disappear when degrees remain bounded.
Thus the displayed constraint
\[ \sum_t a_{ut}p_t\le \frac12 \]
is exact only after imposing an additional balancing assumption: every type-\(u\) neighbourhood must see precisely the same relabelled fraction from every type \(t\). That is not a consequence of high multiplicity. It is a dense, block-regular or perfectly coordinated network model. The proposed LP therefore solves fractional domination on a quotient interaction matrix, not the high-multiplicity form of the paper’s arbitrary graph problem.
The more faithful repair is to retain the incidence information. One could describe the society by a graphon or interaction kernel \(W\), with a pointwise condition such as
\[ \frac{\int W(x,y)p(y)\,d\mu(y)} {\int W(x,y)\,d\mu(y)} \le \frac12 \]
for every agent location \(x\). But then the network relation itself, rather than just the population, has become the continuous object. With arbitrary local incidence patterns, the required type description is effectively a rooted neighbourhood or position in the graph; the number of types grows with the instance, or the model becomes infinite-dimensional. That is no longer the finite-type population mirror proposed by the proponent.
Theorem 1 illustrates the loss particularly clearly. Its Set Cover reduction uses each set vertex as a distinct incidence pattern. Allowing a fraction of that type to be relabelled turns Set Cover into fractional Set Cover. That may be a sensible new optimization problem, but it is precisely a change from choosing vertices in a graph to assigning mass in a weighted covering system. The bounded-diameter and bipartite graph structure survive only as superficial properties of the quotient; the overlapping individual neighbourhoods that make EI EI have been removed.
Nor does Theorem 3 establish a general mirror. Its aggregation of twin vertices works inside a graph with a bounded vertex cover, while the remaining core vertices and their exact incidences stay explicit. That is a special structural algorithm, not evidence that arbitrary social-network vertices naturally form interchangeable population types.
This is a credible case against the proposed mirror as a faithful model of the paper. It does not, however, support the universal claim very strongly. A dense platform, organisation, or community network with recurring roles and deliberately balanced exposure is a plausible high-multiplicity regime, and on that restricted regime the LP is a legitimate Class A result. The honest conclusion is therefore that the negative case is conditional: it rejects the claim that Theorem 1 automatically yields a meaningful continuous mirror, but it cannot show that no worthwhile block-regular or mean-field version exists.
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.