Eliminating Majority Illusions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10512161" target="_blank" >RIV/00216208:11320/25:10512161 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/25:00389817
Result on the web
<a href="https://dl.acm.org/doi/10.5555/3709347.3743592" target="_blank" >https://dl.acm.org/doi/10.5555/3709347.3743592</a>
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Eliminating Majority Illusions
Original language description
An opinion illusion refers to a phenomenon in social networks where agents may witness distributions of opinions among their neighbours that do not accurately reflect the true distribution of opinions in the population as a whole. A specific case of this occurs when there are only two possible choices, such as whether to receive the COVID-19 vaccine or vote on EU membership, which is commonly referred to as a majority illusion. In this work, we study the topological properties of social networks that lead to opinion illusions and focus on minimizing the number of agents that need to be influenced to eliminate these illusions. To do so, we propose an initial, but systematic study of the algorithmic behaviour of this problem. We show that the problem is NP-hard even for underlying topologies that are rather restrictive, being planar and of bounded diameter. We then look for exact algorithms that scale well as the input grows (FPT). We argue the in-existence of such algorithms even when the number of vertices that must be influenced is bounded, or when the social network is arranged in a "path-like" fashion (has bounded pathwidth). On the positive side, we present an FPT algorithm for networks with "star-like" structure (bounded vertex cover number). Finally, we construct an FPT algorithm for "treelike" networks (bounded treewidth) when the number of vertices that must be influenced is bounded. This algorithm is then used to provide a PTAS for planar graphs.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Aamas
ISBN
979-8-4007-1426-9
ISSN
1548-8403
e-ISSN
1558-2914
Number of pages
9
Pages from-to
749-757
Publisher name
International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Place of publication
Richland, SC (USA)
Event location
Detroit, Michigan, USA
Event date
May 19, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001532048100085