# eliminating_majority_illusion_is_easy__8f3e9e92.pdf Eliminating Majority Illusion is Easy Jack Dippel1, Max Dupr e la Tour1, April Niu1, Sanjukta Roy2, Adrian Vetta1 1Mc Gill University 2Indian Statistical Institute, Kolkata jack.dippel@mail.mcgill.ca max.duprelatour@mail.mcgill.ca yuexing.niu@mail.mcgill.ca, sanjukta@isical.ac.in adrian.vetta@mcgill.ca Majority illusion is a phenomenon in social networks wherein the decision by the majority of the network is not the same as one s personal social circle s majority, leading to an incorrect perception of the majority in a large network. 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. Extended version https://arxiv.org/html/2407.20187v1 Introduction Perceptions are liable to become distorted on a social network. An example of this is the friendship paradox (Feld 1991): on average, a person has fewer friends than their friends do.1 Similarly, on average, a researcher is less productive than their co-authors (Eom and Jo 2014; Benevenuto, Laender, and Alves 2006). This network characteristic, whereby local observations can lead to erroneous conclusions regarding a global state, was dubbed majority illusion by Lerman et al. (Lerman, Yan, and Wu 2016). The nomenclature relates to situations where a minority viewpoint is perceived to be the majority viewpoint (Stewart et al. 2019). One of the simplest manifestation of majority illusion concerns elections. Let s model a two-party election by a graph G = (V, E) where each node represents a voter and each edge connects two voters that are neighbours (or friends). Furthermore, imagine party preference is given by a colouring function f : V {B, R}. If there are more blue nodes than red nodes then we say blue is the majority. A node v V is then under (majority) illusion if it has strictly more red neighbours than blue neighbours. There exist instances where every node is under illusion; see Figure 1. Network topology can have a big impact on misinformation. Indeed, electoral networks are very susceptible to Copyright 2025, Association for the Advancement of Artificial Figure 1: A network in which every node suffers illusion. majority illusion because their underlying network topology has a social determinant. For example, homophily, the tendency for humans to connect with similar people, contributes to the creation of information bubbles and polarization (Mc Pherson, Smith-Lovin, and Cook 2001). Another topical example of majority illusion concerns vaccinations (Johnson et al. 2020). Here node colours may indicate vaccinated or unvaccinated. If a personal decision to vaccinate oneself is influenced by the actions of people in your local social network, then misinformation may have significant consequences. Moreover, a smaller number of influential high degree nodes may suffice to cause major distortions. An illusion can occur even when there are more than two alternatives and each node selects one alternative. If alternative blue is the majority winner, then a node under illusion has strictly less blue neighbors compared to red neighbors (neighbors selecting any of the nonwinning alternatives). Indeed, this observation indicates the relevance of illusion to advertising, campaigning, and influence maximization (Becker, D Angelo, and Ghobadi 2023; Zhou and Zhang 2021). Moreover, the effects of illusion have been studied in many disparate areas, including voting theory (Bara, Lev, and Turrini 2021; Castiglioni, Ferraioli, and Gatti 2020; Doucette et al. 2019; Wilder and Vorobeychik 2018), participatory budgeting and the alloca- Intelligence (www.aaai.org). All rights reserved. 1This is a simple consequence of the fact that a higher degree node appears in more neighbourhoods than a lower degree node. The Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI-25) tion of public goods (Kempe, Yu, and Vorobeychik 2020; Yu, Kempe, and Vorobeychik 2021). These applications highlight the importance of creating social networks that give everyone fair and unbiased information (Johnson et al. 2020). That is the focus of this paper. Specifically, to determine whether or not majority illusion can be eliminated in a network. If so, can we do this optimally in polynomial time? The Illusion Elimination Problem To answer these questions we first study a class of majority illusion elimination problems. We are given a social network G = (V, E), a non-negative integer k, and a voting function f : V {B, R}, where B (resp. R) denotes blue (resp. red) nodes and blue is the strict majority. Can we eliminate (majority) illusion, for every node, by altering (adding and/or deleting) at most k edges? That is, after the alteration, no node can have a strict majority of red nodes in its neighbourhood. Observe that, since we may remove edges of G or add non-edges of G, there are three variants of the majority illusion elimination problems where we can only add edges, only remove edges, or both add and remove edges. Formally, this gives the following three decision problems, due to Grandi et al. (Grandi et al. 2023). Problem 1. Majority Illusion Addition Elimination (MIAE): Given a graph G = (V, E), f : V {B, R} where blue is strict majority, and a non-negative integer k, determine if the addition of at most k edges can ensure each node has at least a 1 2-fraction of blue nodes in its neighbourhood. Problem 2. Majority Illusion Removal Elimination (MIRE): Given a graph G = (V, E), f : V {B, R} where blue is strict majority, and a non-negative integer k, determine if the subtraction of at most k edges can ensure each node has at least a 1 2-fraction of blue nodes in its neighbourhood. Problem 3. Majority Illusion Elimination (MIE): Given a graph G = (V, E), f : V {B, R} where blue is strict majority, and a non-negative integer k, determine if the addition/subtraction of at most k edges can ensure each node has at least a 1 2-fraction of blue nodes in its neighbourhood. An instance of a problem is denoted as (V, E, f, k). Note that we can analogously define optimization version for each problem where the goal is to minimize the number of edges added and/or removed. We illustrate these three problems using the example we encountered in Figure 1. Figure 2 presents the three corresponding optimal solutions to eliminate majority illusion. The assumption that the blue party is a strict majority is not necessary. However the assumption of strictness ensures that, for all three problems, it is always feasible to alter the graph to eliminate majority illusion. We remark that (Grandi et al. 2023) left unresolved the computational complexity of these three problems. Instead, rather than completely eliminating illusion at every node, they showed it to be NP-complete to partially eliminate illusion for a fraction of the nodes. In particular, they studied the following q-partial (majority) illusion elimination problem: Can at Figure 2: In (a) every node is under majority illusion. An optimal solution to the MIAE problem, adding 11 edges, is shown in (b); an optimal solution to the MIRE problem, requiring the removal of all 12 edges, is shown in (c); an optimal solution to the MIE problem, adding 3 edges and removing 3 edges, is shown in (d). most q-fraction of the nodes be under illusion after altering (adding and/or deleting) at most k edges in G? They proved this problem is NP-complete for q (0, 1). Observe that the MIAE, MIRE, and MIE problems correspond to the case q = 0, that is, where no nodes are allowed to be left under illusion. Therefore, the computational complexity of the main problems of interest remained open and motivated our work. Our Contributions We make two contributions regarding illusion elimination in social networks. First, we prove that the majority illusion elimination problem is solvable in polynomial time for all three variants (MIAE, MIRE and MIE). Thus, completely eliminating majority illusion in a social network is easy. The result is surprising given, as stated before, that the problem of partially eliminating illusion is hard (Grandi et al. 2023). In our second contribution, we generalize the problem of eliminating majority illusion and consider the problem of pillusion. The majority illusion elimination problems assume the blue party has at least 1 2 the votes. In contrast, suppose we make no assumption on the number of blue voters and instead ask if it is possible to ensure that every voter believes that the blue party has at least a p-fraction of the ballots, where p [0, 1] is a rational number. Thus, we define the p-Illusion problem: Given a graph G = (V, E), a colouring function f : V {B, R}, and a rational number p [0, 1], can we modify at most k edges such that every node has at least p-fraction of blue nodes in its neighbourhood? This question induces three problems for p-Illusion 2 (analogous to majority illusion elimination), namely, p-IA, p-IR, and p- 2We emphasize the distinction between the p-I problem and the q-partial MIE problem (called q-majority illusion by (Grandi et al. 2023)). In p-I (and p-IA/p-IR) every node must have at least a pfraction of blue neighbors. In contrast, q-partial MIE only requires the elimination of illusion for a (1 q)-fraction of the nodes. I, which as we prove are all polynomial time solvable for p = 1 2. However, the majority case p = 1 2 is very special. We prove that p-IA, p-IR, and p-I problems are all NP-complete for any rational p [0, 1] except for p {0, 1 3, 1}. An overview of the rest of the paper is as follows. In Section we discuss related works. In Section , we present preliminary results and observations concerning illusion elimination. Our three polynomial time algorithms for MIAE, MIRE, and MIE are then given in Sections , , and , respectively. Finally, in Section we prove the NP-completeness of the p-IA, p-IR and p-I problems, for p / {0, 1 3, 1}. (Due to space restrictions, missing proofs are deferred to the full version (Dippel et al. 2024).) Related Work Several studies have delved into the dynamics of decisionmaking within social networks and the manipulation of these networks. The article by Grandi et al. (Grandi et al. 2023) is most relevant to us as it directly addresses the phenomenon of majority illusion in social networks. The authors show that identifying the possibility of majority illusion by assigning colors to vertices is NP-hard in restricted graphs and present FPT algorithms with respect to the parameters maximum degree and tree width and a XP algorithm for maximum degree and clique width. Moreover, they show that q-partial majority illusion elimination is in fact W[1]-hard with respect to the number of edge modifications k. In a recent work Fioravantes et al. (2024) study the problem of eliminating majority illusion by altering the color of at most k vertices and show that, unlike our edge editing problem, it is NP-hard and W[2]-hard with respect to k. They present FPT algorithm parameterized by treewidth of the input graph and PTAS for planar graphs. The effect of adding and/or deleting edges in a social network has been investigated in several settings. In voting theory, for example, Castiglioni et al. (Castiglioni, Ferraioli, and Gatti 2020) study election control in social networks through the addition or removal of connections between individuals. Their study proposes methods for strategically manipulating network connections to influence election outcomes. Liu et al. (Liu et al. 2023) introduce a metric called influence assortment to quantify the phenomenon information gerrymandering in elections, where the strategic distribution of individuals within social networks can influence voting outcomes. Faliszewski et al. (Faliszewski et al. 2022) examine techniques for controlling elections through social influence. By manipulating the spread of information and opinions within social networks, they consider strategies for influencing voter behavior and election outcomes and provide insights into the potential for social influence to shape electoral processes. In information diffusion, by analyzing the impact of link additions on information diffusion and exposure diversity, Becker et al. (Becker, D Angelo, and Ghobadi 2023) show approximation algorithms to achieve maximum fairness in reaching all nodes or communities. Empirically, they show that adding few edges greedily to maximize spread surpasses all fairness-tailored algorithms in terms of ex-post fairness. Wilder and Vorobeychik (Wilder and Vorobeychik 2018) in- vestigate opinion diffusion and campaigning strategies on society graphs, how opinions spread through networks, and its effectiveness. They focus on the dynamics of opinion formation and diffusion in social networks, with the aim of understanding influence dynamics and designing effective communication strategies. Kempe et al. (Kempe, Yu, and Vorobeychik 2020) explore methods for inducing equilibria in networked public goods games by modifying the structure of the network. Through mathematical modeling and simulations, their research investigates strategies for promoting cooperation and achieving desirable outcomes in public goods dilemmas. Their work also proffers insights into the role of network topology in shaping collective behavior. Preliminaries We begin by defining some basic notations. Given a graph G = (V, E), let B denote the set of blue nodes and R the set of red nodes in G such that the node set V (G) = B R. The edge set E(R, B) denotes the edges in E(G) with one endpoint in R and other in B. For any node v V , let NE(v) denote the neighbourhood of v in G. Let r(v) = |{u R : u NE(v)}| be the number of red nodes in the neighbourhood of v, and b(v) = |{u B : u NE(v)}| be the number of blue nodes in its neighbourhood. Definition 1 (p-Illusion). Let G = (V, E) be a graph such that |B| |V | > p. Then, a node v V is under p-illusion if it has strictly less than p-fraction of blue neighbors, i.e., b(v) |NE(v)| < p. When p = 1/2, this is known as majority illusion. Next, we describe basic properties that optimal solutions to our three majority illusion elimination problems must possess. For the algorithms, we assume blue denotes the majority, i.e., |B| 2. For a node v V , if r(v) > b(v) then we say v is in deficit; if r(v) < b(v) then we say v is in surplus. So the task is to add/remove as few edges as possible so that no node is in deficit. The solution E V V is the set of edges that are modified. That is, the edges E \ E are added to G and the edges E E are removed from G. Structural Properties First we make the trivial observation that it is never of benefit to add an edge between two red nodes. Observation 1. In an optimal solution E to an instance (V, E, f, k) of MIE or MIAE, there are no edges of E \ E between two red nodes. Analogously, it is never of benefit to remove an edge between two blue nodes. Observation 2. In an optimal solution E to an instance (V, E, f, k) of MIE or MIRE, there are no edges of E E between two blue nodes. We conclude this section with three more observations for the three problems. The first, for the addition variant, states that for any red node, it is never beneficial to connect it to more new blue neighbours than is absolutely necessary. Lemma 1. In an optimal solution E to an instance (V, E, f, k) of MIAE, there are exactly max(r(v) b(v), 0) edges of E incident to any red node v. Similarly, for the removal variant, for any blue node, it is never beneficial to disconnect it from more red neighbours than is absolutely necessary. Lemma 2. In an optimal solution E to an instance (V, E, f, k) of MIRE, there are exactly max(r(v) b(v), 0) edges of E incident to any blue node v. Finally, for the general majority illusion elimination problem, the following extends the previous observations. Lemma 3. There exists an optimal solution E to an instance (V, E, f, k) of MIE with no edges of E \ E incident to any red node, and no edges of E E incident to any blue node. Majority Illusion Addition Elimination We begin by presenting an integer programming formulation of the Majority Illusion Elimination Problem (MIE) restricted to adding edges (MIAE). A First Attempt Given a graph G = (V, E) where V = B R, we define an auxiliary graph G = (V, E ), called the availability graph. Motivated by Observation 1, its edges are the edges in the complement of G excluding those between two red nodes. That is, E = E(R, B) E(G[B]) where E(G) denotes the non-edges of G. Thus, any optimal solution for MIAE adds edges from E . Now let b (v) = max(r(v) b(v), 0) if v R b(v) r(v) if v B Next consider the following integer program. e E (G ) ye (IP-1a) u NE (v) B yuv = b (v) v R (1a-1) u NE (v) B yuv + X u NE (v) R yuv b (v) v B (1a-2) ye {0, 1} e E (1a-3) Theorem 4. The integer program (IP-1a) is the MIAE problem. Proof sketch. The variable ye is set to 1 if and only if the edge e is added to the solution. Since, we want to minimize the number edges added, the objective function is correct. The left hand side (LHS) of Equation (1a-1) encodes the number of edges added between a red node v and blue nodes B. By Lemma 1 and definition of b (v), the equality in (1a-1) holds true for an optimal solution. Next, in the LHS of Equation (1a-2), the first summand is the number of blue neighbours added to the blue node v and the second summand is the number of red neighbours added to a blue Figure 3: Left: the input graph G. Right: depicts a nonintegral optimal solution to the LP relaxation of (IP-1a). node v. Any feasible solution to the MIAE problem must satisfy the property that the number of red nodes does not exceed the number of blue nodes in the neighbourhood of any blue node. Thus, simple calculations show that (1a-2) is valid. Finally, (1a-3) is valid due to Observation 1. Therefore to solve the MIAE problem, we can simply solve the integer program (IP-1a). But running an integer programming solver is not polynomial time in the worst case, so we need a more efficient method. Observe that (IP-1a) has size polynomial in the size of the graph. Thus, its linear program relaxation can be solved in polynomial time. So, if the optimal solution to the LP relaxation is always integral then, by Theorem 4, we would have an efficient algorithm for the MIAE problem. Unfortunately, this property is not guaranteed: setting X = B and F = violates the constraint 1 yv3v4+1 yv3v2+1 yv2v4 3 2 for a non-integral y for the vertices v2, v3, and v4 in Figure 3. A Second Attempt We desire an integer program that (i) exactly models the MIAE problem, (ii) has an integral LP relaxation, and (iii) the LP relaxation is solvable in polynomial time. Towards this goal we make two alterations to the integer program (IP-1a). The first is we alter the constraint (1a2) for each blue node v by adding |NE (v) B| to both sides. This transformation is evidently innocuous. For ease of exposition, we define a new function b (v) to account for this modification as follows: b (v) = max(r(v) b(v), 0) if v R |NE (v) B| + b(v) r(v) if v B Thus, the RHS of Equations (1a-1) and (1a-2) change to b (v) and LHS of (1a-2) changes. Critically, we also add the following new set of constraints to the integer program. For each X B R and for each F δE (X) where δE (X) is the set of edges in E that have one endpoint in X: X e:e E (G [B]) e E (G [X]) F e:e E (R,B) e E (G [X]) F v X b (v) + |F| k (1b-4) We will show in Theorem 5 that these new constraints are satisfied by any feasible solution to the MIAE problem. Moreover, we will prove that adding this set of new constraints will eliminate all non-integral solutions. Putting all this together our new integer program is e E (G ) ye (IP-1b) u NE (v) B yuv = b (v) v R u NE (v) B 1 yuv + X u NE (v) R yuv b (v) v B e:e E (G [B]) e E (G [X]) F e:e E (R,B) e E (G [X]) F v X b (v) + |F| k X B R F δE (X) ye {0, 1} e E Our first step now is to verify that (IP-1b) solves the MIAE problem. Theorem 5. The integer program (IP-1b) is the MIAE problem. Again, Theorem 5 implies that we can solve the MIAE problem by solving the integer program (IP-1b). We will do this efficiently by solving its linear program relaxation. To achieve this successfully, we must show that the LP relaxation is integral and also that it can be solved in polynomial time despite the fact that there are an exponential number of constraints of type (1b-4). Towards this, we modify (IP-1b) to show it is total dual integral. A TDI System For ease of exposition, we begin by imposing a change of variables. Specifically, let xe = ye if e E (R, B) 1 ye if e E (G [B]) Then LP relaxation of (IP-1b) simplifies to e E (G[B]) xe X e E (R,B) xe |E (G[B])| e:e δE (v) xe = b (v) v R e:e δE (v) xe b (v) v B e:e E (G [X]) xe + X e:e F xe j1 v X b (v)+|F| k X B R, F δE (X) 0 xe 1 e E Our goal now is to prove that (LP-1c) produces an integral solution.To prove that the system of linear equations is integral, we use the concept of total dual integrality (TDI). Definition 2. Let Ax b be a linear system where A, b have rational entries. The linear system is Total Dual Integral (TDI) if for any integer valued c such that the linear program max{c T x: Ax b} has an optimal solution, there is an integer optimal solution to the dual. A proof that a linear program is TDI allows us to use the following result to show that it is integral. Theorem 6. (Edmonds and Giles 1977) If a linear system Ax b is TDI, and b is integral, then Ax b is integral. We will prove that (LP-1c) is total dual integral (TDI) to show its integrality. To do this, we turn our attention to simple b-matchings. Theorem 7. (Schrijver 2003) The following linear system (representing a simple b -matching polytope in the graph G ) is TDI: (b -matching LP) X e:e δ(v) xe b (v) v B R e:e E (G [X]) xe + X e:e F xe j1 v X b (v) + |F| k X B R, F δE (X) 0 xe 1 e E (G ) This TDI system is very similar to our system. We require one more result. Theorem 8. (Cook 1983) Let a linear system Ax b be TDI and let A x b denote a linear system obtained by adding inequality a T x β to Ax b, where a T x β is an inequality in Ax b. Then A x b is TDI. Corollary 9. The linear system of (LP-1b) is TDI. Thus, using Theorem 6 we get the following. Corollary 10. The linear program (LP-1b) is integral. A Polynomial Time Algorithm We showed that (LP-1b) is integral. However, it has exponentially many constraints. Thus, to show it can be solved in polynomial time, we apply a separation oracle. Definition 3 (SEPARATION PROBLEM). Given a convex set P Rn and a vector y Qn, either determine that y P or find a vector d Qn such that d T x < d T y for all x P. The separation problem for the b-matching polytope can be solved in polynomial time. Theorem 11. (Padberg and Rao 1982; Letchford, Reinelt, and Theis 2008) For undirected graphs G, w : E(G) N { } and b : V (G) N, the SEPARATION PROBLEM for the b-matching polytope of (G, w) can be solved in time O(n4) where n is the number of nodes in G. We show analogous result for (LP-1b). Theorem 12. The SEPARATION PROBLEM for (LP-1b) can be solved in time O(n4) where n is number of nodes. Using the next result, we can finally show a polynomial time algorithm for MIAE and consequently, for 1 2-IA. Theorem 13. (Gr otschel, Lov asz, and Schrijver 1988) Let n N and c Qn. Let P Rn be a rational polytope, and let x0 Qn be a point in the interior of P. Let T N such that size(x0) log T and size(x) log T for all vertices x of P. Given n, c, x0, T, and a polynomial-time oracle for the SEPARATION PROBLEM for P, a node x of P attaining max{c T x : x P} can be found in time polynomial in n, log T, and size(c). Corollary 14. MIAE and the 1 2-ILLUSION ADDITION problem can be solved in polynomial time. Remark 1. If there are more than two color of nodes and blue has strict majority, then we can identify all the other colors as red. Thus, our algorithms will work in such cases. Majority Illusion Removal Elimination The Majority Illusion Removal Elimination (MIRE) Problem is the Majority Illusion Elimination (MIE) Problem restricted to removing edges. Given G = (V, E) where V = B R, we define an auxiliary graph G = (V, E ), called the removable graph. Its edges are the edges in G excluding those between two blue nodes. That is, E = E(R, B) E(G[R]). Now let b (v) = max(r(v) b(v), 0) if v B b(v) r(v) if v R Consider the following integer program analogous to MIAE. e E (G ) ye (IP-2) u NE (v) R yuv = b (v) v B (2-1) u NE (v) R yuv + X u NE (v) B yuv b (v) v R (2-2) ye {0, 1} e E (2-3) Theorem 15. The integer program (IP-2) is the MIRE problem. As one might expect, our strategy for solving the MIRE problem will mirror the approach for the MIAE problem. We will modify (IP-2) to create a linear program (LP-2) which is symmetric to (LP-1b). In this case, we define function b (v) to account for adding |NE (v) R|: b (v) = max(r(v) b(v), 0) if v B |NE (v) R| + b(v) r(v) if v R Finally, we add an analogous set of new constraints to the integer program. X e:e E (G [R]) e E (G [X]) F e:e E (R,B) e E (G [X]) F v X b (v) + |F| k X B R F δE (X) Finally, we get the following LP relaxation. e E (G ) ye (LP-2) u NE (v) R yuv = b (v) v B u NE (v) R (1 yuv) + X u NE (v) B yuv b (v) v R e:e E (G [R]) e E (G [X]) F e:e E (R,B) e E (G [X]) F v X b (v) + |F| k X B R F δE (X) Corollary 16. The linear program (LP-2) is integral. Corollary 17. The SEPARATION PROBLEM for linear program (LP-2) can be solved in O(n4) time. Corollary 18. MIRE and the 1 2-ILLUSION REMOVAL problem can be solved in polynomial time. Majority Illusion Elimination Finally, we arrive at the general Majority Illusion Elimination (MIE) problem. Given G = (V, E), to solve the general problem, we will create new graphs Ga = (R B, Ea) and Gr = (R B, Er). Specifically: Create Ga from G by removing all edges of G[R]. Create Gr from G by adding all edges of the complement of G[B]. The remarkable fact now is that an optimal solution to the general problem on G = (V, E) can be reduced to an optimal solution to the MIAE problem on Ga plus an optimal solution to the MIRE problem on Gr. Theorem 19. There is an optimal solution E to the MIE problem on G composed of the union of the optimal solution Ea to the MIAE problem on Ga and the optimal solution Er to the MIRE problem on Gr Proof idea. Observe that in Gr the blue nodes from a clique. Consequently, no blue node is under illusion, and only red nodes can be under illusion. Therefore, any optimal solution Er to MIRE of Gr will be a subset of the edges removed in some optimal solution E to MIE on G. Similarly, in Ga the red nodes from an independent set. Consequently, no red node is under illusion, and only blue nodes can be under illusion. Therefore, the only edges added in an optimal solution Ea to the MIAE problem will be between two blue nodes. Furthermore, all the red (or blue) nodes in Gr (resp. in Ga) are under exactly the same illusion as the red (resp. blue) nodes in G. It can be shown that majority illusion in G can be eliminated using these two solutions Ea and Er, and it is optimal. Theorem 19 implies we can solve the MIE problem in polynomial time. We reduce it to a MIAE problem and a MIRE problem, both of which can be solved in polynomial time by the methods developed in Sections and . However, we can exploit Theorem 19 to solve the MIE directly using a single linear program. This is because the proof works by essentially reducing the problem to two independent b-matching problems within the same graph! In particular, take G = (B R, E) and define functions ba(v) = |NE (v) B| + b(v) r(v) v B br(v) = |NE (v) R| + b(v) r(v) v R Our linear program is then e E (G ) ye (LP-3) u NE (v) B (1 yuv) ba(v) v B(G ) (3-1) e:e E (G [B]) e E (G [X]) F v X ba(v) + |F| k X B, F δE (X) (3-2) X u NE (v) R (1 yuv) br(v) v R(G ) (3-3) e:e E (G [R]) e E (G [X]) F v X br(v) + |F| k X R, F δE (X) (3-4) 0 ye 1 e E (G ) We show the following to finally obtain our desired result. Corollary 20. The linear program (LP-3) is integral. Corollary 21. The SEPARATION PROBLEM for linear program (LP-3) can be solved in O(n4) time. Corollary 22. MIE and the 1 2-ILLUSION problem can be solved in polynomial time. Hardness In this section we present variants of the MIE, MIAE and MIRE problems. Problem 4. Let p [0, 1], p Q. We define the p-IA problem as follows: Given a graph G = (V, E), f : V {B, R}, and integer k, determine if the addition of at most k edges can ensure each node has at least a p-fraction of blue nodes in its neighbourhood. Problem 5. Let p [0, 1], p Q. We define the p-IR problem as follows: Given a graph G = (V, E), f : V {B, R}, and integer k, determine if the subtraction of at most k edges can ensure each node has at least a p-fraction of blue nodes in its neighbourhood. Problem 6. Let p [0, 1], p Q. We define the p-I problem as follows: Given a graph G = (V, E), f : V {B, R}, and integer k, determine if the addition/subtraction of at most k edges can ensure each node has at least a p-fraction of blue nodes in its neighbourhood. 2, if we add the requirement that blue be the strict majority, these extended problems correspond to the original MIAE, MIRE and MIE problems for which we have provided polynomial-time algorithms in the previous sections of this paper. Our algorithms can be extended to handle the case when blue is not the true majority, showing that the problems are solvable in polynomial time when p = 1 2. Regardless, to show NP-hardness for other values of p, we provide a polynomial time reduction from the following NPcomplete, satisfiability problem. Definition 4. XSAT for l-CNFl + is the problem of determining whether a boolean formula in conjunctive normal form composed of n variables appearing exactly l times as positive literals within clauses of size exactly l has an assignment which evaluates to TRUE such that each clause has exactly one variable assigned TRUE. Theorem 23. (Schmidt 2011) XSAT for l-CNFl + is NPcomplete for any l 3 Theorem 24. The p-IA problem and p-I problem are NPhard for p Q, 0 < p < 1 3. Theorem 25. The p-IR problem and p-I problem is NP-hard for p Q, 1 2 < p < 1, p = 2 Theorem 26. The p-IA problem is NP-hard for p Q, 1 2 < p < 1, p = 2 3. Theorem 27. The p-IR problem is NP-hard for p Q, 0 < p < 1 Conclusion We ve settled the q-ILLUSION ELIMINATION problems studied in (Grandi et al. 2023) for the special q = 0 case. While the previous paper showed hardness for q = (0, 1) and a trivial solution for q = 1, we present here the surprising result that fully determining and eliminating illusion can be solved in polynomial time. The three problems, MIAE, MIRE, and MIE, have simple linear programs with integer solutions. We also define a natural extension to all three problems. For any p [0, 1], the p-IA, p-IR, and p-I problems ask if it is possible to alter a network to ensure the neighbourhood of every node has a p-fraction of blue nodes by adding edges, removing edges, or both respectively. These problems reduce to MIAE, MIRE and MIE when p = 1 2, and just as in those problems, we ask that the total number of blue nodes be such that the problems are solvable regardless of the initial network given. We show that these problems are hard for p (0, 1 3, 1). In terms of future work, our p-IA, p-IR, and p-I problems have two p-values for which there is no polynomial time algorithm nor a hardness result: p = 1 3 and p = 2 3. Interestingly, if we add edge weights to the linear programs used to solve MIAE, MIRE and MIE, we can create linear programs to solve the p-IA, p-IR, and p-I problems. All values of p except for p {0, 1 2, 1} result in a program that is no longer totally dual integral. However, p { 1 3} are the only other values for which the program is half integral. Therefore, it is entirely possible that these problems are solvable in polynomial time for p { 1 3}; this would be an intriguing result. Acknowledgments AV is supported by grant number NSERC 2022-04191. References Bara, J.; Lev, O.; and Turrini, P. 2021. Predicting voting outcomes in presence of communities. In Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2021), 151 159. Becker, R.; D Angelo, G.; and Ghobadi, S. 2023. Improving fairness in information exposure by adding links. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 14119 14126. Benevenuto, F.; Laender, A.; and Alves, B. 2006. The hindex paradox: your coauthors have a higher h-index than you do. Scientometrics, 106: 469 474. Castiglioni, M.; Ferraioli, D.; and Gatti, N. 2020. Election control in social networks via edge addition or removal. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 1878 1885. Cook, W. 1983. Operations that preserve total dual integrality. Operations Research Letters, 2(1): 31 35. Dippel, J.; la Tour, M. D.; Niu, A.; Roy, S.; and Vetta, A. 2024. Eliminating Majority Illusion is Easy. Co RR, abs/2407.20187. Doucette, J.; Tsang, A.; Hosseini, H.; Larson, K.; and Cohen, R. 2019. Inferring true voting outcomes in homophilic social networks. Autonomous Agents and Multi-Agent Systems, 33: 298 329. Edmonds, J.; and Giles, R. 1977. A Min-Max Relation for Submodular Functions on Graphs. In Hammer, P.; Johnson, E.; Korte, B.; and Nemhauser, G., eds., Studies in Integer Programming, volume 1 of Annals of Discrete Mathematics, 185 204. Elsevier. Eom, Y.; and Jo, H. 2014. Generalized friendship paradox in complex networks: The case of scientific collaboration. Scientoific Reports, 4: 4603. Faliszewski, P.; Gonen, R.; Kouteck y, M.; and Talmon, N. 2022. Opinion diffusion and campaigning on society graphs*. Journal of Logic and Computation, 32(6): 1162 1194. Feld, S. 1991. Why your friends have more friends than you do. Am. J. Sociol, 96: 1464 1477. Fioravantes, F.; Lahiri, A.; Lauerbach, A.; Sieper, M. D.; and Wolf, S. 2024. Eliminating Majority Illusion. HAL, hal04574647. Grandi, U.; Kanesh, L.; Lisowski, G.; Sridharan, R.; and Turrini, P. 2023. Identifying and Eliminating Majority Illusion in Social Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 37(4): 5062 5069. Gr otschel, M.; Lov asz, L.; and Schrijver, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer Verlag. Johnson, N.; Vel asquez, N.; Restrepo, N.; Leahy, R.; Gabriel, N.; El Oud, S.; Zheng, M.; Manrique, P.; Wuchty, S.; and Lupu, Y. 2020. The online competition between proand anti-vaccination views. Nature, 582(7811): 230 233. Kempe, D.; Yu, S.; and Vorobeychik, Y. 2020. Inducing Equilibria in Networked Public Goods Games through Network Structure Modification. In Proceedings of the 19th International Conference on Autonomous Agents and Multi Agent Systems, 611 619. Lerman, K.; Yan, X.; and Wu, X.-Z. 2016. The Majority Illusion in Social Networks. PLOS ONE, 11(2): 1 13. Letchford, A.; Reinelt, G.; and Theis, D. 2008. Odd Minimum Cut Sets and b-Matchings Revisited. SIAM Journal on Discrete Mathematics, 22(4): 1480 1487. Liu, X.; Kato, S.; Ren, F.; Su, G.; Zhang, M.; and Gu, W. 2023. Information Gerrymandering in Elections. In Wu, S.; Yang, W.; Amin, M.; Kang, B.-H.; and Xu, G., eds., Knowledge Management and Acquisition for Intelligent Systems, 83 97. Springer Singapore. Mc Pherson, M.; Smith-Lovin, L.; and Cook, J. 2001. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology, 27(1): 415 444. Padberg, M.; and Rao, M. 1982. Odd Minimum Cut-Sets and b-Matchings. Mathematics of Operations Research, 7(1): 67 80. Schmidt, T. 2011. Computational complexity of SAT, XSAT and NAE-sat for linear and mixed horn CNF formulas. S udwestdeutscher Verlag f ur Hochschulschriften. Schrijver, A. 2003. Combinatorial Optimization: Polyhedra and Efficiency, volume B. Springer-Verlag. Stewart, A.; Mosleh, M.; Diakonova, M.; Arechar, A.; Rand, D.; and Plotkin, J. 2019. Information gerrymandering and undemocratic decisions. Nature, 573(7772): 117 121. Wilder, B.; and Vorobeychik, Y. 2018. Controlling Elections through Social Influence. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), 265 273. International Foundation for Autonomous Agents and Multiagent Systems. Yu, S.; Kempe, D.; and Vorobeychik, Y. 2021. Altruism design in networked public goods games. ar Xiv:2105.00505. Zhou, X.; and Zhang, Z. 2021. Maximizing influence of leaders in social networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, 2400 2408.