Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

1 Introduction

Consider the following prototypical scenario. The members of a department are organizing a social dinner, and they have to decide whether to go to a restaurant or to a pizzeria. Initially, each of them holds an opinion on her ideal choice. They are neither strategic [Osborne and Rubinstein, 1994; Gottlob et al., 2005] nor inclined to use voting rules or other mechanisms to find an agreement [Brandt et al., 2016; Endriss, 2017]. Rather, we know that, at a certain point, they will exchange their viewpoints and each of them will be affected by a social pressure leading to adapt her opinion to the one manifested by the majority of her friends. So, we ask: Would be they capable to reach a consensus for some/all profiles of their initial opinions? Can a minority have enough social "power" to influence all other agents? Is it any easier for a majority to guide convergence towards consensus?

Our goal is to analyze these questions under the lens of algorithm design and computational complexity, by focusing on the setting where agents (e.g., the members of the department) hold binary opinions (e.g., restaurant vs pizzeria), where at each time instant precisely one agent can change her opinion (asynchronous model), and where social relationships are encoded as a graph. Indeed, while the study of opinion diffusion, originated in [Granovetter, 1978], has attracted much attention in recent literature (e.g., [Grandi et al., 2015; Cholvy, 2016; Brill et al., 2016; Grandi et al., 2017; Bredereck and Elkind, 2017; Acar et al., 2017;

Endriss, 2017; Christoff and Grossi, 2017]), problems related to consensus-in the setting of interest-was basically faced so far only by Mossel et al. [2014] and Feldman et al. [2014], roughly stating that, in expander graphs, a sufficiently large majority will always influence all other agents.

In this paper we fill this gap. In more details, we first analyze in Section 3 the question of whether there exists some profile from which a fraction α of the agents that already agree on some given opinion can spread that opinion to all the remaining agents. We show that the answer is positive on any social graph and for any given value of α≥1/2. In particular, a (rather elaborated) polynomial-time algorithm computing the desired initial configurations is exhibited. The result is not only the main technical achievement of the paper, but it is also conceptually interesting and somehow surprising. Indeed, one might be inclined to believe that the topology of the social graphs (in particular, for values of α close to 1/2) should play some role w.r.t. the possibility of reaching consensus on some given opinion. To the contrary, our result says that there always exists a majority formed by a half of the agents that can annihilate the opposite opinion.

Moreover, we evidence in Section 4 that the value α = 1/2 defines a sharp boundary for the consensus problem. Indeed, we show that a minority (i.e., α<1/2) that can spread its opinion to all the agents exists only in certain graphs. A result of this kind holds for the problem of assessing the existence of a minority that will become a majority [Auletta et al., 2015; 2017a; 2017b]. However, in this setting the graphs enjoying the desired property admit a (computationally) simple characterization, while in our setting the characterization is NPhard. Furthermore, even just deciding whether a minority can double the number of agents with its opinion is NP-hard.

Finally, we address the question of identifying those graphs in which consensus is the only possible stable outcome. In fact, assessing whether the two opinions can/cannot coexist in some stable configuration has been left as an open research issue in [Bredereck and Elkind, 2017]. Moreover, this problem has a natural graph-theoretic interpretation in terms of the existence of non-trivial cuts that are locally stable, whose complexity was, so far, open in the literature [Ferraioli and Ventre, 2017]. In Section 5 we solve this problem, by showing that checking whether a cut of this kind exists is NP-hard.

We envisage a practical interest of our results if positioned in the context of assessing the robustness of social networks w.r.t. external intervention and manipulation. In particular, our results might be interpreted by putting ourselves in the perspective of an external agent who tries to distribute opinions on a network to reach a certain consensus. Indeed, our constructive proof in Section 3 can be immediately interpreted as a manipulation algorithm. Manipulations of this kind are of interest in those scenarios where no outcome can be returned until consensus is reached; examples include the novel privacy policies for publication of shared information in social networks (see, e.g., [Ferraioli and Ventre, 2017]). With this respect, our intractability results (for α < 1/2) come as computational obstructions to such forms of manipulation, when the external agent is not powerful enough.

2 Formal Framework for Opinion Diffusion

Let G = (N, E) be an undirected graph encoding the interactions of a set N of agents. We assume that G is connectedotherwise apply our results on each connected component.

A configuration for G is a function c : N → {1, 0}; its intended meaning is that agent x ∈ N with c(x) = 1 (respectively, c(x) = 0) holds opinion 1 (respectively, 0). For any set S ⊆ N of agents, we define S1/c (shortly S1, if the configuration c is clearly understood) as the set of all agents with opinion 1. The set S0/c (shortly S0) is defined analogously. For each agent x ∈ N, the set {y | {x, y} ∈ E} of her neighbors is denoted by δ(x). Agent x ∈ N is stable in c if her opinion agrees with the opinion held by a (non-strict) majority of her neighbors; that is, either |δ(x)0| ≤ |δ(x)1| and c(x) = 1; or |δ(x)1| ≤ |δ(x)0| and c(x) = 0. A configuration c is stable if all agents in N are stable.

We consider an asynchronous model where, at each time instant, precisely one agent which is not stable changes her opinion. Accordingly, a dynamics for G is modeled as a sequence of configurations c0, ..., ck such that ch+1, for each h ∈ {0, ..., k - 1}, is obtained from ch by flipping the opinion of an agent that is not stable in ch. The dynamics will be also shortly denoted as c0 ⇝ ck, whenever we are just interested in the initial and final configurations only.

Let op ∈ {1, 0} be an opinion. Given an initial configuration c, let us denote by maxop(c) the configuration resulting from the dynamics c ⇝ maxop(c) defined as follows: First, as long as there is an agent x ∈ N that is not stable and whose opinion is not op, then flip her opinion. Second, as long as there is an agent x ∈ N that is not stable and whose opinion is op, then flip her opinion. It is known that maxop(c) is stable and that |Nop/maxop(c)| ≥ |Nop/c′ | for each dynamics c ⇝ c′ with c′ ̸= maxop(c) [Bredereck and Elkind, 2017].

3 FromMajority to Consensus

Let op ∈ {1, 0} be an opinion. Define ∀op as the "consensus" configuration where all agents hold opinion op, and consider the following problem defined on graphs and parameterized w.r.t. a fixed rational number α such that 0 < α < 1:

CONSENSUS[α]: Given an undirected graph G = (N,E), compute a configuration c for G such that (i) |Nop/c| ≤ ⌈α|N|⌉ and (ii) maxop(c) = ∀op, or check that there is no configuration enjoying (i) and (ii).

In words, CONSENSUS[α] asks whether consensus on op can be reached in G from a configuration where the fraction of agents that initially holds opinion op is at most α. In the following, for simplicity, we assume that G is given and we omit it in our notation; moreover (and w.l.o.g), we fix op = 1.

Our main result is that, for each undirected graph G, whenever the fraction α covers a majority of the agents, i.e., α≥1/2, a configuration enjoying (i) and (ii) always exist and can be computed in polynomial-time. In particular, we propose (in Section 3.4) a polynomial time algorithm to solve CONSENSUS[1/2]. The algorithm explores the space of binary partitions P of the agent set N, that are pairs P = (A,B) where A,B ⊆ N are such that A ∩ B = ∅ and A ∪ B = N. In the following, the fact that a set X ⊆ N belongs to {A, B} is shortly denoted byX ∈ P; moreover, we define ¯X = N \X.

Our approach is founded on the observation (see Section 3.1) that there are certain "nice" partitions from which solutions to CONSENSUS[1/2] can be easily computed. However, it is not obvious how to single out these partitions. In fact, we propose an algorithm that proceeds as follows: it starts from an arbitrary balanced partition P = (A,B), i.e., such that -1 ≤ |A| - |B| ≤ 1, and incrementally modifies the current partition via update procedures (described in Section 3.2 and Section 3.3) until a "nice" partition is found.

3.1 Nice Partitions

We next introduce three kinds of "nice" partitions from which solutions to CONSENSUS[1/2] can be easily computed.

To this aim, let P be a partition of N. For any agent x ∈ N, let Px (resp., ¯ Px) denote the set of P to which x belongs (resp., does not belong), and let us define the utility of x in P as the value u(x, P) = |δ(x) ∩ Px| - |δ(x) ∩ ¯ Px|. Moreover, for any two disjoint sets of agents A′ and B′ , not necessarily forming a partition, we define E(A′ ,B′ ) as the set of edges e ∈ E such that e ∩ A′ ̸= ∅ and e ∩ B′ ̸= ∅.

Observe that, whenever each "side" of P consists of all the agents that have the same specific opinion, then u(x∗ , P) > 0 holds if, and only if, agent x∗ is stable (with her opinion associated) with the side Px∗ . The first kind of "nice" partition we consider assumes the existence of a stable agent x∗ and, in addition, it relates the utility of all pairs of agents x and y from "opposite" sides with the cardinality of E({x}, {y}).

Definition 1. P is a P1-partition if there is a set X ∈ P such that |X| ≤ ⌈ N2 ⌉ and the following conditions hold:

• u(x,P) + u(y,P) ≤ -2|E({x}, {y})| holds for each pair of agents x ∈ X and y ∈ ¯X;
• there is x⋆ ∈ X with u(x⋆ , P) > 0. ✷

To define the second kind of "nice" partition, for each side X of a partition P, we denote by G[X] the subgraph of G induced by X. Let Zc(X, P) be the set of all connected components of G[X] such that u(y,P) = 0 for each component C ∈ Zc(X,P) and each agent y of C. That is, Zc(X,P) is the set of connected components of G[X] such that all agents within these components have the same number of neighbors within the component and on the other side of the partition.

Definition 2. P is a P2-partition if there is a set X ∈ P such that |X| ≤ ⌈ N2 ⌉ and the following hold:

• every x ∈ ¯X such that u(x,P) = k > 0 has at least ⌊(k + 2)/2⌋ neighbors y ∈ ¯X with u(y, P) < 0;
• Zc( ¯X,P) = ∅. ✷

Let ¯c(P) be the configuration that, for a P1 or a P2 partition P, assigns opinion 1 (resp., 0) to all the agents in X (resp., ¯X). We show that ¯c(P) leads to consensus (see Figure 1).

Lemma 1. If P is a P1-partition, then max1(¯c(P)) = ∀1. Proof. For each y ∈ ¯X, it holds that u(y,P) ≤ -u(x⋆ ,P)- 2|E({x⋆ }, {y})| < 0, where x⋆ and X are as in Definition 1. Hence, in the configuration ¯c(P) all agents in ¯X are not stable and they will change their opinion. Indeed, note that, while the dynamics is running, |δ(y)0| - |δ(y)1| ≤ u(y,P) holds, for each y ∈ ¯X that has not yet changed her opinion.

Lemma 2. If P is a P2-partition, then max1(¯c(P)) = ∀1. Proof Sketch. Let X ∈ P be as in Definition 2. Note that agents in S = {y ∈ ¯X | u(y,P) < 0} are not stable in ¯c(P) and they flip their opinion. Let c∗ be the configuration reached from ¯c(P) after all agents in S flipped their opinion, and let P ⋆ = (A⋆ , B⋆ ), with A⋆ = X ∪ S and B⋆ = ¯X \ S.

Now, observe that u(x,P ⋆ ) ≤ u(x,P) for each x ∈ B⋆ . Moreover, if u(x,P) > 0 or u(x,P) = 0, then x has neighbors in S, and u(x,P ⋆ ) < 0. Hence, Zc(B⋆ ,P ⋆ ) = ∅ and u(x, P ⋆ ) ≤ 0 for each x ∈ B⋆ . Thus, for each y0 ∈ B⋆ there is a path y0, . . . , yh in B⋆ , with h ≥ 0, where u(yh, P ⋆ ) < 0 and u(yi, P ⋆ ) = 0 for i = 0, . . . , h-1. Such agents flip their opinion if selected in the reverse order yh, . . . , y0.

We can also define a third kind of "nice" partition. For any x ∈ N, let toZc(x, P) be the set of all components C ∈ Zc( ¯ Px, Px) containing an agent adjacent to x.

Definition 3. P is a P3-partition if it is balanced and there is a set X ∈ P such that the following hold:

• u(x,P) + u(y,P) ≤ -2|E({x}, {y})| holds for each pair of agents x ∈ X and y ∈ ¯X;
• u(x, P) ≤ 0 holds for each x ∈ N;
• |Zc( ¯X,P)| ≥ |Zc(X,P)| > 0;
• for each D ∈ Zc( ¯X,P) there is x ∈ X with D ∈ toZc(x, P) and u(x, P) < -2|toZc(x, P)|. ✷

Assume that P is a P3-partition. In this case, we cannot reach consensus by starting from ¯c(P) but we need a more complex construction. Let Xnz (resp., ¯Xnz) denote the set of agents that do not belong to any component in Zc(X,P) (resp., Zc( ¯X, P)). Consider the configuration ˜c(P) shown in Figure 1 and built as follows. All agents in ¯Xnz (resp., Xnz) hold opinion 1 (resp., 0). Moreover, for each component C ∈ Zc(X,P), precisely one arbitrarily chosen agent xC ∈ C holds opinion 1 and all the remaining agents of C hold opinion 0. For each component D ∈ Zc( ¯X,P), precisely one agent yD ∈ D holds opinion 0 and all the remaining agents of D hold opinion 1, where yD ∈ ¯X is an agent connected to some xD ∈ X such that u(xD,P) < -2|toZc(xD,P)|. Note that, by definition of P3-partition, yD is well-defined.

Lemma 3. If P is a P3-partition, then max1(˜c(P)) = ∀1. Proof Sketch. Let X ∈ P be as in Definition 3. Let x be an agent in some C ∈ Zc(X,P). Note that all neighbors of x are either confined in the component C or they occur in ¯Xnz, since (by Definition 3) we have u(y, P) < 0 if y is adjacent to x. Now, in ˜c(P) if x ̸= xC, then x has |δ(x) ∩ ¯X| + 1 neighbors with opinion 1 and |δ(x) ∩ X| - 1 neighbors with opinion 0. Since u(x, P) = 0, |δ(x)∩ ¯X|+1 > |δ(x)∩X|- 1. Hence, x can flip her opinion. Moreover, for each D ∈ Zc( ¯X,P), consider the agent xD ∈ X. Note that xD has in ˜c(P) at least |δ(x) ∩ ¯X| - |toZc(xD,P)| neighbors having opinion 1 and at most |δ(x)∩X)| +|toZc(xD, P)| neighbors with opinion 0. Therefore, u(xD,P) < -2|toZc(xD,P)| implies that |δ(x) ∩ ¯X| - |toZc(xD,P)| > |δ(x) ∩ X| + |toZc(xD, P)|, and xD can flip her opinion.

Now, let c∗ be the profile derived from˜c(P) after all agents x ̸= xC occurring in C ∈ Zc(X,P) and all agents xD with D ∈ Zc( ¯X,P) have changed their opinion. For each D ∈ Zc( ¯X, P), yD can change her opinion, because yD has at least |δ(yD)∩ ¯X|+1 neighbors with opinion 1 in c∗ and at most |δ(yD) ∩X| - 1 neighbors with opinion 0 (and we have u(yD,P) = 0). Finally, consider the configuration derived from c∗ after all agents yD with D ∈ Zc( ¯X, P) have changed their opinion. In this configuration, the only agents with opinion 0 are agents x in Xnz with x ̸= xD. For these agents, the fact that they can change their opinion can be shown with the arguments used in the proof of Lemma 2.

These lemmas imply that if P is a P1 or P2 (resp., P3) partition, then |N1/¯c(P)|≤⌈1/2|N|⌉ (resp., |N1/˜c(P)|≤⌈1/2|N|⌉) and consensus is reached from these configurations. This is formalized in the following corollary. Hereinafter, we say that a partition is nice (for G) if it is a P1, P2 or P3 partition.

Corollary 1. Assume that, for any graph G, a nice partition exists and can be computed in polynomial time. Then, CONSENSUS[1/2] can be solved in polynomial time, too.

3.2 Step 1: Remove Pivotal Agents

In the light of Corollary 1, our goal is to design an algorithm that, given as input a graph G, is able to compute (in polynomial time) a nice partition of G. To this end, a crucial role is played by the identification of certain agents, called pivotal.

Definition 4. An agent x ∈ N is pivotal in the partition P if there is an agent y ∈ ¯ Px, called a witness of x, such that u(x, P) + u(y, P) > -2|E({x}, {y})|. ✷

Intuitively, pivotal agents are obstructions to the current partition P to being a P1 and P3 partitions. To remove these obstructions we exploit the property that, if we swap a pivotal agent with her witness, then the number of edges crossing the two sides of the partition increases. Hence, by successive swaps, we eventually remove all pivotal agents. To formalize this property, if x ∈ N is pivotal and y is its witness, define SWAP(x,P) as the function returning the partition P ′ such that P ′x = ¯ Px ∪ {x} \ {y}. When a pivotal agent has multiple witnesses, the one to be swapped can be chosen arbitrarily.

Lemma 4. Let x be a pivotal agent in the partition P, and let P ′ = SWAP(x,P). Then, |E(P ′x , ¯ P ′x )| > |E(Px, ¯ Px)|. Moreover, if P is balanced, then P ′ is balanced, too.

Proof. Consider the witness y of x. Let ∆ = |E(Px \ {x}, ¯ Px\{y})| and note that: |E(Px, ¯ Px)| = ∆+|δ(x)∩ ¯ Px|+ |δ(y) ∩ Px| - |E({x}, {y})| and |E(P ′x, ¯ P ′x)| = ∆ + |δ(x) ∩ Px| + |δ(y) ∩ ¯ Px| + |E({x}, {y})| . Hence, |E(P ′x , ¯ P ′x )| - |E(Px, ¯ Px)| coincides with the value u(x,P) + u(y,P) + 2|E({x}, {y})| > 0. To conclude, note that balancedness of P ′ is immediate whenever P is balanced.

However, removing all pivotal agents (by swapping them with their witnesses till none exists) is not yet sufficient to end up with a nice partition. Indeed, further obstructions can exist. In particular, the following result straightforwardly derives by inspecting Definitions 1-4.

Hereinafter, let #Zc(P) = | ∪X∈P Zc(X, P)|.

Fact 1. Let P be a balanced partition with no pivotal agents and which is not nice. Then,

• (i) u(x,P) ≤ 0, for each x ∈ N;
• (ii) for each X ∈ P, it holds that |Zc(X,P)| > 0;
• (iii) for each X ∈ P with |Zc(X,P)| ≥ #Zc(P)/2, there is D ∈ Zc(X, P) such that u(x, P) ≥ -2|toZc(x, P)|, for each x ∈ ¯X with D ∈ toZc(x, P). ✷

A component D satisfying condition (iii) is termed critical, and the set of all critical components is denoted by cr(P). Fact 1 suggests that, to obtain a nice partition, we must modify a given balanced partition by removing all critical components while keeping it balanced and with no pivotal agents.

3.3 Step 2: Remove Critical Components

Let P be a balanced partition without pivotal agents and which is not nice. An agent x ∈ N is critical if there is a component in toZc(x,P) that is critical. We distinguish two kinds of critical agents as follows.

Definition 5. A critical agent x ∈ N is of kind

We remove critical components involving agents x of kind C1 by swapping certain agents between the two sides of P-see Figure 2. Formally, let us define REMOVEC1(x,P) as the function returning the partition P ′ such that P ′x = ¯ Px ∪ base(x, P) ∪ {x} \ dual (x, P), where dual (x, P) is the set including an arbitrarily chosen agent y of C connected to x, for each C ∈ toZc(x,P), and where base(x,P) is a set containing up to |toZc(x, P)| - 1 nodes, each one being chosen from a distinct component of Zc(Px, P).

The crucial observation is now that the application of REMOVEC1 can be related with the monotonic behavior of certain values, analogously to what we did in Lemma 4 (for pivotal agents and considering the number of crossing edges).

Lemma 5. Let P be a balanced partition with no pivotal agents and which is not nice. Let x ∈ N be a critical agent in P of kind C1. Then, either P ′ = REMOVEC1(x,P) is nice, or it is balanced and one of the following conditions holds:

• |E(P ′x , ¯ P ′ x)| > |E(Px, ¯ Px)|;
• |E(P ′x , ¯ P ′ x)| = |E(Px, ¯ Px)| and #Zc(P ′ ) < #Zc(P).

Proof Sketch. For each z ∈ N, if y ∈ ¯ Pz is connected to z, then u(z,P) + u(y,P) ≤ -2|E({z}, {y})| = -2. Since the utility of each agent in base(x, P) ∪ dual (x, P) equals to 0, we get E(base(x, P), dual (x, P))=∅, u(x, P) ̸= 0, agents in base(x, P) are not connected with each other, as they belong to different components, and, by the definition of Zc(Px, P), x is not connected to any of the agents in base(x,P). By these observations and by using arguments similar to those in Lemma 4, we can state that |E(P ′x, ¯ P ′x)| - |E(Px, ¯ Px)| = u(x,P) + ∑y∈dual(x,P) u(y,P) + 2|toZc(x,P)|. In particular, since u(y, P) = 0 holds for each y ∈ dual (x, P), we derive |E(P ′x, ¯ P ′x)| - |E(Px, ¯ Px)| = u(x, P) + 2|toZc(x, P)|.

Assume now that P ′ is a balanced but not nice. If u(x, P) > -2|toZc(x,P)|, then |E(P ′x , ¯ P ′x )| > |E(Px, ¯ Px)|. Instead, if u(x,P) = -2|toZc(x,P)|, then |E(P ′x, ¯ P ′x)| = |E(Px, ¯ Px)| and |toZc(x, P)| > 1. For the latter case, |∪X∈P′ Zc(X, P ′ )| < | ∪X∈P Zc(X, P)| holds. Indeed, moving agents in base(x, P) to the other side destroys |base(x,P)| components in Px, while creating at most the same number of components in the other side. Moreover, swapping x with agents in dual (x, P) causes replacing |dual(x,P)| = |toZc(x,P)| > 1 components in ¯ Px with at most one component including x.

Suppose now that P ′ is not balanced. Then |Zc(Px, P)| < |toZc(x,P)| - 1, so that ¯ P ′x has no zero component. Then, P ′ is a P2 partition; indeed, nodes in ¯ P ′x with positive utility must be neighbors of agents from dual (x, P).

Critical agents x of kind C2 are processed via the function REMOVEC2(x,P) described in Figure 3. Its salient properties are formalized below-as for Lemma 4 and Lemma 5, note the relationship we established between the application of the function and the monotonic behavior of certain values.

Lemma 6. Let P = (A,B) be a balanced partition with no pivotal agents, and no critical agents of kind C1, and which is not nice. Let x ∈ N be critical of kind C2. Then, either P ′ = REMOVEC2(x,P) is nice, or it is balanced, |E(P ′x , ¯ P ′ x)| = |E(Px, ¯ Px)| and one of the following conditions holds:

• #Zc(P ′ ) < #Zc(P);

function REMOVEC2: (x,P) ↦→P ′ let C be the unique component in toZc(x, P) let D be an arbitrary component in Zc(Px, P) let x0, . . . , xn be a path s.t. x0 ∈ C, xn ∈ D, and x1 = x P 0 ← P and i ← 0 repeat if xi+1 ∈ P ixi then P i+1 ←P i else let P i+1 be such that P i+1 xi = ¯ P ixi ∪ {xi} \ {xi+1} i ← i + 1 until either P i is nice, or P i has a pivotal or critical agent of kind C1, or #Zc(P i ) <#Zc(P 0 ), or |cr(P i )| < |cr(P 0 )| return P i end function

• ·#Zc(P ′ ) =#Zc(P) and |cr(P ′ )| < |cr(P)|;
• #Zc(P ′ ) = #Zc(P), |cr(P ′ )| = |cr(P)| and P ′ has either a pivotal agent or a critical agent of kind C1.

Moreover, REMOVEC2 converges in at most |N| iterations.

Proof Sketch. W.l.o.g., assume that x0∈A and x1∈B. Note that u(x0,P 0 ) = 0 while u(x1,P 0 ) = -2, since x1 is critical of kind C2. Hence, swapping x0 with x1 does not modify the size of the cut. Moreover, the swap produces a balanced partition P 1 . Note also that moving x0 to B destroys one component of Zc(A,P 0 ) and does not add components to the other side; to this end, in particular, observe that u(x0,P 1 ) = -2. Instead, moving x1 to A might create one fresh component at most (precisely including x1). So, | ∪X∈P 1 Zc(X,P 1 )| ≤ | ∪X∈P ′ Zc(X,P 0 )|. In fact, existing components are not affected by the swap and we clearly have |cr(P 1 )| ≤ |cr(P 0 )|. Therefore, if no exit condition is satisfied for i = 0, then the above relationships are actually equalities, and there are no pivotal agents and no critical agents of kind C1. In fact, in this case, the fresh component where x1 occurs, say D1, is critical. Now, observe that not in every iteration the current partition is changed. Let i be the first index such that P i ̸= P 1 . Then, xi still occurs in the critical component D1 (as we are traversing a path) and xi+1 is therefore a critical agent of kind C2.

At this point, it is easily seen that the arguments used for the pair x0, x1 can be used for xi, xi+1, too. And the reasoning can be repeated (formally by induction) till some step i∗ where one exit condition is satisfied. To conclude, we claim that this step exists. Indeed, xn ∈ D, where D is a component of P 0 . In particular, if no exit condition were satisfied before the n-th step, then D would be not affected by any swap, and thus it would be a component in P n-1 . In this case, however, xn-1 would belong to a critical component of A. But this is impossible, since xn-1 and xn are neighbors: indeed, in P n-1 , we have that u(xn-1,P n-1 ) + u(xn,P n-1 ) = 0 > -2E(xn-1, xn), and thus xn-1 is a pivotal agent.

Concerning the complexity, note that |N| iterations are required to go through the entire path between x0 and xn.

3.4 Putting It All Together

All ingredients are now in place to illustrate Algorithm 1, which we designed to solve CONSENSUS[1/2].

compute a balanced partition P of N done ← false while not done do while there is a pivotal agent x in P do P ← SWAP(x, P) if there is a critical agent x of kind C1 in P then P ← REMOVEC1(x, P) else if there is a critical agent x of kind C2 in P then P ← REMOVEC2(x, P) end if if P is nice then done ← true end while if P is a P1 or P2-partition then return ¯c(P) else return ˜c(P)

The algorithms takes in input the graph G and starts by computing a balanced partition. At each iteration, it first removes all pivotal agents-via the repeated application of SWAP-and, subsequently, it removes a critical agent (if any exists). Observe that the application of functions REMOVEC1 and REMOVEC2 is potentially creating nice distributions or pivotal agents. This is why Algorithm 1 removes only one critical agent in the main loop. Eventually, the main loop terminates when the current partition is nice, and then the algorithm returns the configuration associated to that partition as we discussed in Section 3.1.

Theorem 1. After at most poly(|N|) iterations Algorithm 1 returns a solution to CONSENSUS[1/2].

Proof. For a partition P = (A,B), let Φ1(P) = |E(A,B)|, Φ2(P) = | ∪X∈P Zc(X, P)|, and Φ3(P) = |cr(P)|. Observe that Φ1(P) ≤ |N|2 and Φ3(P) ≤ Φ2(P) ≤ |N|/2. Moreover, by Lemma 4, Lemma 5, and Lemma 6, after every two iterations, at least one of these functions decreases and, if Φk decreases, k = 2, 3, then Φk′ for k′ < k does not increase. Finally, if these functions cannot be further minimized (after at most |N|4 /2 iterations), then a nice partition is obtained.

Correctness then follows from Corollary 1.

4 FromMinority to Consensus

In this section we address the question of whether a consensus on some opinion op ∈ {1, 0} can be reached starting from a configuration where op is supported by a minority.

We show that the answer to the question depends on the structure of the social graph and, more interestingly, recognizing such graphs is NP-hard. Inspired by similar results in earlier literature [Kempe et al., 2005; Chen, 2008], the following proof exhibits a reduction from the well-known VERTEX COVER problem [Garey and Johnson, 1979].

Theorem2. For every 0<α< 12 , CONSENSUS[α] is NP-hard.

Proof Sketch. Let G = (N,E) be a graph and k > 0 be a natural number. Consider the problem of deciding whether G admits a vertex cover of cardinality at most k, that is a set S ⊆ N of nodes with |S| ≤ k and such that {i, j} ∩ S ̸= ∅, for each {i, j} ∈ E. This is NP-hard even if |{j | {i, j} ∈ E| = 3 for each i ∈ N [Greenlaw and Petreschi, 1995].

Define ¯G = ( ¯N, ¯E) as the graph obtained by including into G, for each i ∈ N, 2 fresh nodes each of them connected to i only. Note that G has a vertex cover S with

|S| ≤ k if, and only if, there exists a dynamics c ⇝ ∀1 such that | ¯N1/c| ≤ k. Since | ¯N| = 3|N|, this immediately shows that consensus[α] is NP-hard, for every α such that ⌈α|N|⌉ = ⌈¯α|N|⌉where ¯α = k (3|N|) ≤ 13 . We now adapt

the reduction to show that hardness holds for each 0<α<1/2. We distinguish two cases. If ⌈α|N|⌉ > ⌈¯α|N|⌉, then we build a graph ¯G+ = ( ¯N +, ¯E+) as follows: arbitrarily pick u ∈ ¯N\N, and add to ¯G vertices u′ and u′′ both connected to u and to each other and m ≥ 1 copies of a gadget consisting of a four nodes clique with each gadget node connected to u′ . Note that G has a vertex cover S with |S| ≤ k iff there is a dynamics c ⇝ ∀1 s.t. | ¯N + 1/c | ≤ k+2m+1. The result follows by choosing m such that ⌈α(3|N|+4m+2)⌉ = k + 2m + 1. Assume finally that ⌈α|N|⌉ < ⌈¯α|N|⌉. In this case, we build a graph ¯G- = ( ¯N -, ¯E-) as follows: arbitrarily pick u ∈ ¯N \ N, and add to ¯G vertex u′ connected to u, m + 3 - (m mod 2) nodes arranged in a ring and connected with u′ and with a new node u′′ . Then, G has a vertex cover S with |S| ≤ k iff there is a dynamics c ⇝ ∀1 with | ¯N - 1/c | ≤ k + 3. The result eventually follows by setting m such that ⌈α(3|N | + m + 4 + (m mod 2))⌉ = k + 3.

An interesting generalization of the above result is that it is still NP-hard to decide whether there is a dynamics leading to a stable configuration where the opinion initially held by a minority of α|N| agents, with α < 12 , is spread over (just) 2α|N| agents. The precise formulation is given in Theorem 3. Its proof is not an extension of Theorem 2 and, in fact, it is inspired by the reduction in [Auletta et al., 2015, Theorem 4] to the NP-hard problem 2P3N-3SAT [Yoshinaka, 2005].

Theorem 3. For every δ ∈ (0, 1) and for every ε ≤ 1 2 - δ4 , it is NP-hard to decide whether there is a configuration c such that |N1/c| = ⌈εn⌉ and max1(c) ≥ (2 + δ) ⌈εn⌉.

5 Stable Configurations without Consensus

For any graph G, consensus configurations (∀1 and ∀0) are clearly stable. An interesting question, addressed in this section, is then whether G admits further stable configurations, in which case we would say that G is plural.

Note that G is plural if it admits a non-trivial partition P, i.e., a partition P = (A, B) with A ̸= ∅ and B ̸= ∅, which has moreover local minimum cut-size, that is, |E(A′ ,B′ )| ≥ |E(A, B)| holds for each partition P ′ = (A′ , B′ ) obtained by moving one node from one side to the other (formally, either A′ ⊆ A and |A′ | = |A| - 1, or B′ ⊆ B and |B′ | = |B| - 1). The complexity of recognizing whether a graph admits a partition of this kind was, so far, an open problem [Ferraioli and Ventre, 2017]. The result below answers that question, by exhibiting an involved NP-hardness reduction.

Theorem 4. Deciding if a graph is plural is NP-complete.

Proof Sketch. Membership in NP is trivial. For the hardness, let φ = c1 ∧ · · · ∧ cm be a Boolean formula such that, for each i ∈ {1, ...,m}, the clause ci is the disjunction of 3 literals, i.e., ci = ℓ1,i ∨ ℓ2,i ∨ ℓ3,i. Based on φ, we define the graph ˆG = ( ˆN, ˆE) over nodes ˆN = {p1, ..., p6m+2, q1, q2} ∪ ⋃mi=1 {σ1,i, ..., σ8,i}, where σ1,i, ..., σ8,i are the satisfying truth assignments (viewed as nodes) for ci. Moreover, for each pair σj,i and σj ′ ,i′ , there is an edge connecting them in ˆE if, and only if, the assignments are compatible; finally, each node {p1, ..., p6m+2} is connected with all the other nodes in ˆN but q1 and q2. Let n = m+ 6m+ 2 and note that any clique in ˆG has size n at most. In particular, a maximum clique of size n exists if, and only if, φ is satisfiable. Moreover, note that | ˆN| = 8m+6m+2+2 = 2n and that each node in ˆG has at most 2n - 2 neighbors.

Having the graph ˆG, we now build the social graph G = (N,E) over N = ˆN∪A∪B∪C∪ ¯ A∪ ¯B∪ ¯ C∪R∪{γ, ¯ γ, ¯ γ◦}. Edges include those in ˆE plus those illustrated, according to an intuitive notation, in Figure 4. Note, in particular, that for each x ∈ ˆN and each h ∈ {1, ..., 2n}, R contains the agent rxj which is connected to the agents ¯ax,j,1 and ¯ax,j,2 in ¯ A. Moreover, x is connected (in addition to the edges in E) to all agents in N \ R and to the agents rx1 , ..., rxh(x) , where h(x) is defined in a way that x is adjacent to 2n - 2 nodes of ˆN ∪ R. On this graph, we claim that a stable configuration c with N0 ̸= ∅ and N0 ̸= N exists iff ˆG has a clique of size n.

("only-if"). Assume, w.l.o.g., that c(γ) = 1. If | ˆN1| ̸= n, then the dominant opinion in ˆN spreads to all agents outside ˆN. Fromplurality of ˆN and c(γ) = 1, we derive (A∪B∪C∪ {γ})0 = ∅ and ( ¯ A∪ ¯B∪ ¯ C ∪{¯ γ, ¯ γ◦}∪R)1 = ∅. Now, let x be a node in ˆN1. Note that |δ(x)1| ≤ |A∪B∪C|+n-1, since | ˆN1| = n. Moreover, |δ(x)0| ≥ | ¯ A∪ ¯B∪ ¯ C|+(2n-2)-(n1), since x is adjacent to 2n-2 nodes in ˆN ∪R. By stability of c, |δ(x)1| ≥ |δ(x)0| implies |δ(x)1| = |A∪B∪C|+n-1. So, agents in ˆN1 form a clique in ˆG.

("if") Assume that ˆG has a clique, say C, of size n. Consider the configuration c such that: (A∪B ∪C ∪ {γ})0 = ∅, ( ¯ A∪ ¯B∪ ¯ C ∪ {¯ γ, ¯ γ◦}∪R)1 = ∅, ˆN1 = C and ˆN0 = ˆN \C. Each agent x ∈ N \ ˆN is clearly stable. Consider x ∈ ˆN1. Since ˆN1 is a clique, we have |δ(x)1| = |A∪B∪C|+n-1. However, |δ(x)| = |A ∪ B ∪ C| + | ¯ A ∪ ¯B ∪ ¯ C| + 2n - 2 which means that |δ(x)0| = | ¯ A ∪ ¯B ∪ ¯ C| + n - 1. Hence,

|δ(x)1| = |δ(x)0| and x is stable. Finally, consider x ∈ ˆN0. Since ˆNb is a clique with | ˆN1| = n and since we know that is no larger clique in ˆG, we have |δ(x) ∩ ˆN1| ≤ n - 1. So, |δ(x)0| ≥ | ¯ A ∪ ¯B ∪ ¯ C| + n - 1, while |δ(x)1| ≤ |A∪B ∪C| +n-1. It follows that x is stable, too.

The following is an immediate consequence.

Corollary 2. Deciding whether ∀1 and ∀0 are the only stable configurations is coNP-complete.

6 Discussion and Conclusion

In the paper we addressed a number of questions related to whether consensus can be achieved in settings where opinions of the agents are affected by social influence phenomena. We have shown that a configuration always exists (and can be computed in polynomial-time) for which the opinion of the majority diffuse to all the agents. Moreover, we exhibited hardness results for spreading the opinion of the minority and for checking the existence of "plural" configurations.

An interesting avenue for further research is to identify special classes of graphs where it is easy to answer similar questions, by looking at structural and topological restrictions.

Acknowledgements

Vincenzo Auletta and Diodato Ferraioli were supported by "GNCS-INdAM". Gianluigi Greco was partially supported by Regione Calabria under POR project "Explora Process".