When the Order of Updates Creates the Illusion

A majority illusion occurs on a network when many people see an opinion as the majority among their neighbors even though it is a minority overall. The usual cause is that a few well-connected people hold the minority view. Existing theory treats the illusion as a property of a frozen snapshot. It asks whether some labeling of the nodes makes at least a $q$-fraction of them misperceive the majority, and it shows this question is NP-complete, meaning no efficient general algorithm is expected. Real agents do not stand still, though. They revise their views one at a time, in some order. Separate theory shows that this order matters a great deal: when everyone updates at once, noisy networks lock into wrong consensus, and when agents update one by one, highly connected hubs filter the noise instead.

This note proposes to study the illusion as something an update order can produce. The central question is whether there exists an ordering of single-agent updates, under majority dynamics, that drives a network from a given starting state into a stable state where a large fraction of agents misperceive the global majority. We conjecture three things. Under synchronous updating the question is easy, because the process is deterministic and can simply be simulated. Under asynchronous updating it becomes NP-complete. It becomes tractable again on networks that are tree-like and where each agent changes its mind only a bounded number of times. We test this on synthetic graph families and on interaction graphs built from real multi-vehicle driving scenes. In those scenes, "who commits first" is exactly the ordering that interactive trajectory predictors already have to choose.

Core Claim

Fix an undirected graph $G=(V,E)$ and an initial binary opinion vector $x_0 \in \{0,1\}^V$. Under asynchronous majority dynamics, a single chosen agent switches to the strict majority of its neighbors, and nothing happens on ties. A schedule is any sequence of such updates. A configuration $x$ is a $q$-illusion if at least $q|V|$ nodes have a local majority opposite to the global majority of $x$.

Define the decision problem SCHEDULED-ILLUSION: does some schedule reach a stable configuration, one in which no agent wants to flip, that is a $q$-illusion? The problem is in NP. The standard potential argument for symmetric majority dynamics shows that every improving flip reduces the number of disagreeing edges, so any schedule has length at most $|E|$ and serves as a short certificate.

The claim has three parts. The first is hardness: SCHEDULED-ILLUSION is NP-complete for $q>1/2$ even on bounded-degree graphs. The synchronous analogue, by contrast, is decidable in polynomial time by simulation, because single-layer threshold systems settle into cycles of length at most 2, as recalled in On Some Fundamental Problems for Multi-Agent Systems Over Multilayer Networks. The second is tractability: an algorithm parameterized by treewidth $k$ and a per-node flip bound $f$ runs in time $g(k,f)\,|V|^{O(1)}$. The third is a resolution of the hub tension. The same hubs that Asynchronous Majority Dynamics in Preferential Attachment Trees shows to be protective "roadblocks" under random orders are the ones an adversarial order exploits to manufacture the illusion. On loopy graphs, we predict, the gap between random-order and worst-order illusion rates grows with the network's degree skew.

If the claim holds, the synchronous update assumption is not merely a modelling convenience. Whether illusion analysis is easy or hard depends on it.

Relation to Prior Work

Three papers establish the static complexity picture, and this proposal reuses their gadgets and decompositions. Identifying and Eliminating Majority Illusion in Social Networks proves that deciding whether a network admits a $q$-majority illusion is NP-complete for $q>1/2$, including on planar, bipartite and bounded-degree graphs. It reduces from 2P2N-3-SAT and gives fixed-parameter algorithms, which run in time exponential only in a structural parameter. A Complexity-Theoretic Analysis of Majority Illusion in Social Networks sharpens these to an $O(\Delta^k |N|^{O(1)})$ treewidth algorithm and a neighborhood-diversity algorithm. Eliminating Majority Illusion Is Easy shows that complete elimination at threshold $1/2$ is polynomial through a totally dual integral integer program, while most other thresholds are NP-hard.

All three treat labels as given and fixed. Our problem fixes the starting labels and asks what the dynamics can reach. It is neither the static existence question nor a centralized rewiring question. The first paper names the link to opinion diffusion as future work, which motivates this proposal.

Two dynamics papers supply the process model and constrain the hardness argument. Reasoning about Consensus when Opinions Diffuse through Majority Dynamics studies the same one-at-a-time majority updates. It shows a global majority can always force consensus, while deciding whether a minority can do so is NP-hard. Its hardness concerns choosing initial placements, whereas ours concerns choosing the order from a fixed start. Its constructive "nice partition" argument also warns that some illusion-reaching orders may be impossible on certain graph classes. Asynchronous Majority Dynamics in Preferential Attachment Trees proves that random orders reach the correct majority with probability $1-o(1)$ on preferential attachment trees. That is an average-case, tree-only statement. We ask the worst-case question on graphs with cycles, which that paper leaves open. On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications shows asynchrony preserves community-level disagreement. That is the mechanism we expect an adversarial order to amplify into an illusion.

The multi-agent interaction literature supplies the application regime rather than the method. M2I: From Factored Marginal Trajectory Prediction to Interactive Prediction factors joint driving prediction into an influencer that acts first and a reactor that responds. This amounts to fixing an update order. JFP: Joint Future Prediction with Interactive Multi-Agent Modeling for Autonomous Driving instead reconciles agents through simultaneous message-passing rounds, which is effectively synchronous. Neither asks whether the chosen ordering can make a cluster of agents misread the group's intent. We use their setting, the Waymo interaction scenes, as a source of realistic interaction graphs. We do not propose a new trajectory predictor.

Research Program

The theoretical work has three parts.

The first is the hardness reduction. We adapt the variable and clause gadgets of Grandi et al. so that each variable gadget contains a pair of agents whose relative update order encodes a truth value. Whichever agent flips first blocks the other through the strict-majority rule. Clause gadgets become stable illusion nodes only if at least one incoming literal ordering is "true." The delicate step is ensuring that no unintended schedule reaches an illusion. We plan to handle this with padding hubs whose high degree makes them immovable, the same roadblock property Bahrani et al. prove. Because the problem is in NP and polynomial under synchrony, success yields a clean separation between the two update rules.

The second is a parameterized algorithm. We propose dynamic programming over a nice tree decomposition. Each bag records, for each of its at most $k+1$ nodes, the sequence of up to $f$ flips, the relative interleaving of those flips with flips of bag neighbors, and the count of illusion nodes already forgotten. The interleaving is what the static algorithm of Lisowski et al. does not need to track. It costs roughly $((k+1)f)!$ per bag, giving an algorithm that is fixed-parameter in $k+f$. We will also try to show that dropping $f$ makes the problem W[1]-hard by treewidth alone, which would mirror the edge-budget hardness for elimination.

The third is the random-versus-adversarial gap. For uniformly random orders we estimate the probability of ending in a $q$-illusion and compare it with the adversarial optimum. Our prediction is that on preferential attachment trees both are near zero, consistent with Bahrani et al., while on loopy, degree-skewed graphs the adversarial value stays high even when the random value is near zero. This is the precise sense in which hubs act both as buffers and as amplifiers.

The empirical work runs on three instance families. The first is synthetic: preferential attachment trees, preferential attachment graphs with cycles, planted-partition clustered graphs as in Cruciani et al., and the planar, bipartite and bounded-degree families from the hardness papers. The second comes from the Waymo Open Motion Dataset interactive split, introduced in Large Scale Interactive Motion Forecasting for Autonomous Driving : The Waymo Open Motion Dataset. There we build per-scene graphs whose edges join agents with intersecting future paths. The binary label marks whether an agent yields, meaning it decelerates before a conflict point in the ground truth. The third comes from NGSIM ramp merges, built the same way with a yield/merge label as in Towards a Fatality-Aware Benchmark of Probabilistic Reaction Prediction in Highly Interactive Driving Scenarios. For the driving graphs we report treewidth, degree skew, and the observed frequency of static illusions about yielding. That frequency tells us whether the phenomenon is real in physical interaction or only a curiosity of social graphs.

Baselines

The naive reference point is static detection on the starting snapshot. It applies the treewidth algorithm of A Complexity-Theoretic Analysis of Majority Illusion in Social Networks to $x_0$ and ignores dynamics. This baseline shows how often the dynamic answer differs from the static one. If they almost always agree, the dynamic question adds nothing. A second reference is synchronous simulation, which runs the parallel majority map to its fixed point or 2-cycle and checks for an illusion.

The strongest practical competitor is a general-purpose exact solver on the unrolled problem. We encode the schedule as an integer program, or as a SAT formula, with one time-indexed flip variable per node and step up to the $|E|$ bound. This baseline needs no new theory, and on small graphs it may well match our dynamic program. A second competitor is Monte Carlo search: sample many random orders and keep the one with the most illusion nodes, augmented with a greedy rule that always flips the node whose flip most increases the illusion count. All methods get the same instances, the same wall-clock budget per instance (the solver and the dynamic program on one core, Monte Carlo with an equal number of evaluated schedules), and the same stability check.

The key ablation removes the interleaving information from our dynamic program, keeping only per-node final labels as in the static algorithm. Any accuracy loss isolates how much the ordering contributes. Beating the baselines means two things. The dynamic program must solve exactly a set of instances, characterized by treewidth and flip bound, that the solver times out on. Greedy and Monte Carlo search must fall measurably below the exact optimum on loopy degree-skewed graphs.

No empirical result is reported in the file for any of these methods on this problem, because the majority-illusion papers there are purely theoretical. We found no reported result on Lacuna for scheduled majority illusion. The only published quantities to compare against are theoretical: the $O(\Delta^k|N|^{O(1)})$ static treewidth bound and the $1-o(1)$ correct-consensus guarantee for random orders on preferential attachment trees.

Why not just…?

Why not just sample many random update orders? Random sampling estimates the typical outcome, and Bahrani et al. prove that on trees the typical outcome is benign. The question here is about the worst order, which may be exponentially rare. An auditor needs this: an adversary, or a structured protocol such as "leaders commit first," does not draw orders uniformly. The random-versus-adversarial gap experiment directly measures how badly sampling underestimates the illusion. If the gap turns out negligible on all realistic graphs, that is a real negative result and we will report it.

Why not just simulate synchronous dynamics and check the end state? Synchronous simulation answers a different question, and the dynamics literature shows it gives qualitatively different answers. Asynchronous Majority Dynamics in Preferential Attachment Trees shows synchronous updates cascade into wrong consensus where asynchronous ones do not. On the Metastability of Quadratic Majority Dynamics on Clustered Graphs and its Biological Implications shows synchrony erases the community-level disagreement on which illusions live. The synchronous baseline is included so we can count instances where it says "no illusion" but some asynchronous order produces one.

Why not just hand the unrolled problem to an integer-programming or SAT solver? This is the real threat. If off-the-shelf solvers handle every Waymo- and NGSIM-scale graph in seconds, the practical case for a specialized algorithm weakens, and the contribution narrows to the complexity classification and the hub characterization. We include the solver as the primary baseline under equal budgets and scale instance size until it fails. The proposal stands on two things: the hardness result explains where the solver must eventually fail, and the treewidth-and-flip measurements on driving graphs show whether real instances lie on the tractable side.

Decisive Checks

Four outcomes decide the proposal. The first is the reduction itself. If no gadget family can stop unintended orders from reaching illusions, the hardness claim fails. We would then look for a polynomial algorithm instead, which would itself be surprising given Auletta et al.'s minority-consensus hardness.

The second is the static-versus-dynamic disagreement rate on synthetic loopy graphs. If static detection on $x_0$ predicts the reachable outcome on nearly all instances, the dynamic framing is superfluous.

The third is the adversarial-minus-random illusion fraction, plotted against the degree-skew exponent. We predict it is near zero on trees and grows on graphs with cycles. A flat curve would refute the hub-duality claim.

The fourth applies to the driving graphs. If their measured treewidth and per-agent flip counts are small, the parameterized algorithm is the right tool for auditing ordering assumptions in interactive predictors like M2I. If static yield-illusions essentially never occur in these scenes, the multi-agent application is unsupported, and the work reduces to a clean theoretical result about social networks.