Eliminating Majority Illusion Is Easy
Authors: Jack Dippel, Max Dupré la Tour, April Niu, Sanjukta Roy, Adrian Vetta
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present polynomial-time algorithms which completely eliminate majority illusion by altering as few connections in the network as possible. Eliminating majority illusion ensures each neighbourhood in the network has at least a 1/2-fraction of the majority winner. This result is surprising as partially eliminating majority illusion is NP-hard. We generalize the majority illusion problem to an arbitrary fraction p and show that the problem of ensuring all neighbourhoods in the network contain at least a p-fraction of nodes consistent with a given preference is NP-hard, for nearly all values of p. The paper extensively uses integer programming formulations, linear program relaxation, and concepts like total dual integrality (TDI) to prove theoretical results regarding the complexity and solvability of the problems. |
| Researcher Affiliation | Academia | Jack Dippel1, Max Dupr e la Tour1, April Niu1, Sanjukta Roy2, Adrian Vetta1 1Mc Gill University 2Indian Statistical Institute, Kolkata EMAIL EMAIL EMAIL, EMAIL EMAIL |
| Pseudocode | No | The paper describes algorithms through mathematical formulations (e.g., Integer Programs, Linear Programs) and theoretical proofs but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code or provide links to a code repository. The 'Extended version' link points to an arXiv HTML version of the paper itself. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and complexity analysis for social networks, rather than conducting empirical studies on specific datasets. Therefore, it does not provide access information for any open datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with datasets, therefore, it does not specify any dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs, rather than implementation details. Therefore, it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and complexity, and therefore does not describe any experimental setup, hyperparameters, or training configurations. |