What Makes Majority Illusion Easy to Detect?
2026-06-02 • Social and Information Networks
Social and Information NetworksData Structures and AlgorithmsComputer Science and Game TheoryMultiagent Systems
AI summaryⓘ
The authors study a problem called the majority illusion, where people in a social network mistakenly think a less popular opinion is actually the majority. They focus on figuring out if a network setup allows this illusion to happen, based on how people (agents) are connected and labeled with opinions. Their work explores how different shapes and connections in the network affect how hard it is to detect this illusion. They provide a detailed analysis of the computational difficulty involved in solving this detection problem.
majority illusionsocial networksbinary labelingagentsminority opinioncomputational complexitynetwork structuredecision-makingcollective behavioralgorithmic tractability
Authors
Šimon Schierreich, Ildikó Schlotter
Abstract
Majority illusion is an undesirable phenomenon in social networks in which agents incorrectly perceive a minority opinion as dominant. This can severely distort collective behavior and decision-making. We study the fundamental question of detecting whether a social network allows for a majority illusion. Formally, in the $q$-Majority Illusion problem, we ask whether there exists a binary labeling of agents in which at least a $q$-fraction of agents have the majority of neighbors with the minority label. We investigate how various structural properties of the underlying social network influence the tractability of this question, and provide a detailed map of its computational complexity.