Proof of Theorem 2
The opinion dynamic in a complete network is deterministic since the probability of a transition from one state to another is either 1 or 0. Note also that the state space is finite, which means that the elements of absorbing states can only be absorbing states or cycles. It remains to prove the correspondence between fixed points of G(x) and absorbing states.
\( \Rightarrow ) \) If \(x^*\) is a fixed point of G(x), then assign actions to players according to the following rule: assign to the conformists whose tipping values are smaller than \(x^*\) the action 1 while to those whose tipping values are greater than \(x^*\) the action 0; assign to the anti-conformists whose tipping values are smaller than \(x^*\) the action 0 while to those whose tipping values are greater than \(x^*\) the action 1. Obviously this action profile corresponds to one absorbing state since nobody would like to change actions next period.
\( \Leftarrow \)) If \(x^*=(x_1,x_2,\ldots ,x_n)\) is an absorbing state, then \(\overline{x}=1/n\displaystyle \sum _{i=1}^p x_i\) is a fixed point of G(x). By contradiction, if \(\overline{x}>G(\overline{x})\), there will be some players playing action 0 at the present period who would like to play action 1 in the next period ( e.g., conformists \(i \in N_c\) with \(\mu _i<\overline{x}\) or anti-conformists \(j \in N_a\) with \(\mu _j>\overline{x}\)). It is similar for the case \(\overline{x}<G(\overline{x})\). Thus \(\overline{x}=G(\overline{x}).\)
Proof of Proposition 1
Note that \(x \in \{0,1/n,\ldots ,n-1/n,1\}\).
Fix \(x \ge \mu _a\). All conformist agents with threshold less than or equal to x would like to take action “1” when observing x (with proportion x). The anti-conformist agents with threshold \(\mu _a\) as well as all conformist agents with threshold strictly greater than x would like to take action “0” when observing x. Thus \(G(x)=x\).
Fix
\(x < \mu _a\). All conformist agents with threshold less than or equal to
x as well as the anti-conformist agents with threshold
\(\mu _a > x\) would like to take action “1” when observing
x (with proportion
\(x+2/n\)). All conformist agents with threshold strictly greater than
x would like to take action “0” when observing
x. Thus
\(G(x)=x+2/n > x\). As a conclusion,
\(\mathcal {F}=\{k/n,\ldots ,n-1/n\}\) is the set of fixed points of the function
G. By Theorem
2, it is also the set of absorbing states of the opinion dynamics. Obviously,
\(|\mathcal {F}|= n(1-\mu _a)=n-k\).
Starting from any initial state with the group opinion \(x^*=k^*/n\), if \(xk^* \ge k\) and \(k^* \ne n\), then \(k^* \in \mathcal {F}\). Thus \(x^*\) is a reachable absorbing state. If \(k^* < k\), then \(G(x)=x+2/n\). It means that two more conformist agents will be activated at the next stage. This “domino” effect stops till \(x\ge \mu _a\) with \(x=k/n\) or \(x=k+1/n\) depending on which one has the same parity as \(k^*\).
Proof of Proposition 2
Fix \(x\in \{0,1/n,\ldots ,n-1/n,1\}\). If \(x < \mu _a^1\), only the conformist agents with threshold less than or equal to x as well as the two anti-conformist agents would take action “1” at the next stage (with proportion \(x+3/n\) in total). Thus \(G(x)=x+3/n>x\). Similarly, if \(x \in [\mu _a^1,\mu _a^2[\), \(G(x)=x+1/n>x\); if \(x \in [\mu _a^2,1[\), \(G(x)=x-1/n<x\).
Obviously,
\(G(1)=n-2/n <1\) . Therefore,
\(\forall x \in S\),
\(G(x)\ne x\). By Theorem
2, there is no absorbing state.
To show that this dynamic end up with a cycle regardless of the initial state, let us distinguish the following cases.
Assume that the dynamic start with the state \(x=k_2/n\). Then all conformist agents with threshold less than x (with proportion \(k_2-1/n\)) would take action “1”. All conformist agents with threshold greater than x as well as the two anti-conformist agents would take action “0” at the next stage (\(v_2\) with \(x=k_2-1/n\)). Then, observing \(x<\mu _a^2\), the anti-conformist agents with threshold \(\mu _a^2\) would change her action into “1” at the following stage (\(v_1\) with \(x=k_2/n\)). Similar analysis is applied to the initial state \(x=k_2-1/n\).
Assume the initial state satisfies \(x<k_2-1/n\). If \(x<\mu _a^1\), then \(G(x)=x+3/n\). After every stage, there will be 3 more types of conformist agents would like to take action “1”. This activation process stops till \(x\in [\mu _a^1,\mu _a^2]\), then \(G(x)=x+1/n\). After every stage, there will be one more types of conformist agents would like to take action “1”. This activation process stops till \(x=\mu _a^2=k_2/n\). Then it goes back to the first case and forms a cycle \(v_2 \rightarrow v_1 \rightarrow v_2\).
Assume the initial state satisfies \(x \in [k_2/n,1[\), then \(G(x)=x-1/n\). This deactivation process stops till \(x=k_2/n\). Then it goes back to the first case and forms a cycle \(v_2 \rightarrow v_1 \rightarrow v_2\).
Proof of Theorem 3
Fix \(x \in \{0,1/n,\ldots ,n-1/n,1\}\).
(i) If \(k_1\ne 0\), and if \(s\in [0,k_1/n[\), \(G(x)=x+2\ell +2/n>s\). If \(x\in [k_{2\ell +1}/n,1[\), \(G(x)=x-2\ell /n<x\).
In general, if \(x\in [k_i/n,k_{i+1}/n [\) (\(i=1,\ldots ,2\ell \)), only the anti-conformist agents with threshold strictly greater than \(k_i/n\) (with proportion \(2\ell +1-i/n\)) and the conformist agents with threshold less than or equal to x (with proportion \(x+1/n-i/n\)) would like to take action 1. That is, \(G(x)=x+2\ell +2-2i/n\).
By
\(G(x)=x\), we get
\(i=k+1\). Therefore,
\(\forall x\in [k_{k+1}/n,k_{k+2}/n[\),
\(G(x)=x\). Thus the set of fixed points of
G(
x) is
\(\mathcal {F}=\{k_{k+1}/n,\ldots ,k_{k+2}-1/n\}\). By Theorem
2, the absorbing states are the action profiles associated to
\(\mathcal {F}\).
(ii) If \(k_1\ne 0\), and if \(x\in [0,k_1/n[\), \(G(x)=x+2\ell +1/n>s\). If \(x\in [k_{2\ell }/n,1[\), \(G(x)=x-2\ell -1/n<x\).
In general, if \(x\in [k_i/n,k_{i+1}/n [\) (\(i=1,\ldots ,2\ell -1\)), only the anti-conformist agents with threshold strictly greater than \(k_i/n\) (with proportion \(2\ell -i/n\)) and the conformist agents with threshold less than or equal to x (with proportion \(x+1/n-i/n\)) would like to take action 1. That is, \(G(x)=x+2\ell +1-2i/n\).
By
\(G(x)=x\), we get
\(i=k+1/2\). But
i should be an integer. Thus
G(
x) has no fixed point (i.e.,
\(\mathcal {F}=\emptyset \)). By Theorem
2, there is no absorbing state but cycles.
It remains to prove the statement on cycles. For this, we observe the following property of the function G(x): when x changes from \(i/n\) to \((i+1)/n\), the value of G is increased or decreased by one unit, depending whether agent i is conformist or anti-conformist. Hence for G the variation in ordinate cannot be greater than the variation in abscissa. We proceed in three steps.
1. The sequence of points (x, (Gx)), (y, G(y)), (x, G(x)) is a cycle iff it corresponds to a sequence of transitions, i.e., \(y=G(x)\), \(x=G(y)=G^{(2)}(x)\).
2. We show that a cycle of length 3 cannot exist. Let \((x,G(x))\rightarrow (G(x),G^{(2)}(x))\rightarrow (G^{(2)}(x),G^{(3)}(x))\rightarrow (x,G(x))\) be a cycle. This implies \(G^{(3)}(x)=x\). As the origin of the cycle is unimportant, suppose that (x, G(x)) is the leftmost point, i.e., \(x<\min (G(x),G^{(2)}(x))\). Observe that this entails that this point is above the diagonal (\(x<G(x)\)). We may suppose that the second point \((G(x),G^{(2)}(x))\) is also above the diagonal, so that we have \(x<G(x)<G^{(2)}(x)\), which entails that the 3d point is below the diagonal since its ordinate is x. By the above observation on the function G, the jump in ordinate cannot exceed the jump in abscissa. In particular, concerning the jump between the 2nd and 3d point, we obtain \(G^{(2)}(x)-x\le G^{(2)}(x)-G(x)\), which cannot be true as \(x<G(x)\). Suppose now that the second point is below the diagonal. As the 1st point is the leftmost point, we necessarily have \(x<G^{(2)}(x)<G(x)\). The condition on the jump between the 1st point and the 3d point yields \(G(x)-x\le G^{(2)}(x)-x\), a contradiction with \(G^{(2)}(x)<G(x)\). The case where the first point is under the diagonal works similarly.
3. We show that no cycle of length greater than 3 can exist. Simply observe that selecting the leftmost point and 2 other points in a sequence of more than 3 points amounts to the case of a cycle of length 3 as the jump conditions will impose the same contradictions.
Proof of Proposition 4
(1) Consider the case that \(\not \exists i \in N\text { s.t. }\mu _i=\mu _a\).
This is equivalent to show that there is no absorbing state if and only if all the inequalities in (
9) are satisfied.
\( \Leftarrow \) (Sufficiency) Fix \(x \in \{0,1/n,\cdots ,n-1/n,1\}\).
If
\(x\in [0,\mu _1[\), only anti-conformist agents would like to take action 1. That is,
\(G(x)=\delta _a\). But by the first inequality of (
9),
\(G(x)>x\).
If
\(x\in [\mu _{i_0},\mu _{i_0+1}[\),
\((i_0=1,\ldots ,k-1\)), only anti-conformist agents and the conformists agents with threshold less than or equal to
\(\mu _{i_0}\) would like to take action 1. That is,
\(G(x)=\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0} q_i\). By the second inequality of (
9),
\(G(x)>x\).
Similarly, if \(x\in [\mu _k,\mu _a[\), \(G(x)=\delta _a + \displaystyle \sum \nolimits _{i=1}^{k} q_i>x\); if \(x\in [\mu _a,\mu _{k+1}[\), \(G(x)=\displaystyle \sum \nolimits _{i=1}^{k} q_i<x\); if \(x\in [\mu _{i_0},\mu _{i_0+1}[\), (\(i_0=k+1,\ldots ,p-1\)), \(G(x)=\displaystyle \sum \nolimits _{i=1}^{i_0} q_i<x\); if \(x\in [\mu _p,1[\), \(G(x)=\displaystyle \sum \nolimits _{i=1}^{p} q_i<x\).
As a conclusion, there is no absorbing state.
\( \Rightarrow \) (
Necessity) We provide a
reduction ad absurdum proof. Suppose the thresholds and corresponding fractions do not satisfy inequalities (
9). Then distinguish the following cases.
\(\delta _a < \mu _1\)
In this case, \(x=\delta _a\) is a fixed point of G(x) since given the group opinion \(\delta _a\), only the anti-conformist agent with threshold strictly greater than \(\mu _1\) would take action 1 (with proportion \(\delta _a\)). Then the group opinion at the next stage is still \(\delta _a\).
\(\exists \) some \( i_0 \in \{1,2,\cdots ,k-1 \}\), such that \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0} q_i < \mu _{i_0+1}\).
Assume that \(i_0^*\) is the smallest number satisfying this condition. That is, \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i < \mu _{i_0^*+1}\) and \(\forall i_0 <i_0^*\), \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0} q_i \ge \mu _{i_0+1}\). Thus \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i< \mu _{i_0^*+1}< \mu _a<\mu _{k+1}< \cdots < \mu _p\) and \(\mu _1< \cdots< \mu _{i_o^*} < \delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i\). In this case, given the group opinion \(s=\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i\), only the conformist agent \(i \le i_0^*\) as well as the anti-conformist agent will take action “1” (with proportion \(\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i + \delta _a\) in total) at the next stage. So \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0^*} q_i\) is a fixed point of G(x).
\(\delta _a + \displaystyle \sum _{i=1}^{k} q_i < \mu _a\)
Then \(\delta _a + \displaystyle \sum \nolimits _{i=1}^{k} q_i< \mu _a<\mu _{k+1}< \cdots < \mu _p\). On the other hand, \(\forall i_0=1,\ldots ,k-1\), \(\delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0} q_i \ge \mu _{i_0+1}\) (Otherwise it coincides with the previous case), then \(\forall i_0=1,\ldots ,k-1\), \(\mu _{i_0+1} \le \delta _a+\displaystyle \sum \nolimits _{i=1}^{i_0} q_i < \delta _a+\displaystyle \sum \nolimits _{i=1}^{k} q_i\) (since \(i_0 < k\)). In this case, given the group opinion \(x=\delta _a + \displaystyle \sum \nolimits _{i=1}^{k} q_i\), only the anti-conformist agent and the conformist agent \(i=1,\ldots ,k\) will take action 1 at the next stage with proportion \(\delta _a + \displaystyle \sum \nolimits _{i=1}^{k} q_i\) in total. Thus \(\delta _a + \displaystyle \sum \nolimits _{i=1}^{k} q_i\) is a fixed point of G(x).
\(\exists \) some \(i_0 \in \{k+1,k+2,\cdots ,p\}\), such that \(\displaystyle \sum \nolimits _{i=1}^{i_0} q_i \ge \mu _{i_0}\).
Assume that \(i_0^{**}\) is the largest number satisfying this condition. That is, \(\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i \ge \mu _{i_0^{**}}\) and \(\forall i_0 > i_0^{**}\), \(\displaystyle \sum \nolimits _{i=1}^{i_0} q_i < \mu _{i_0}\). Thus \(\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i \ge \mu _{i_0^{**}}> \mu _{i_0^{**}-1}> \cdots>\mu _a>\cdots > \mu _1\) and \(\forall i_0 > i_0^{**}\), \(\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i< \displaystyle \sum \nolimits _{i=1}^{i_0} q_i < \mu _{i_0}\). In this case, given the group opinion \(x=\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i\), only the conformist agent \(i<i_0^{**}\) will take the action 1 at the next stage with proportion \(\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i\) in total. So \(\displaystyle \sum \nolimits _{i=1}^{i_0^{**}} q_i\) is a fixed point of G(x).
\(\displaystyle \sum _{i=1}^{k} q_i \ge \mu _a\)
Then \(\displaystyle \sum \nolimits _{i=1}^{k} q_i \ge \mu _a> \mu _k>\mu _{k-1} >\cdots , \mu _1\). On the other hand, \( \forall i_0 \in \{k+1,k+2,\cdots ,p\}\), \(\mu _{i_0}> \displaystyle \sum \nolimits _{i=1}^{i_0} q_i > \displaystyle \sum \nolimits _{i=1}^{k} q_i\). In this case, given the group opinion \(x=\displaystyle \sum \nolimits _{i=1}^{k} q_i\), only the conformist agent \(i=1,\ldots ,k\) will take action 1 at the next stage with proportion \(\displaystyle \sum \nolimits _{i=1}^{k} q_i\). Thus \(s=\displaystyle \sum \nolimits _{i=1}^{k} q_i\) is a fixed point of G(x).
As a conclusion, the fixed point of
G(
x) always exists. By Theorem
2, the absorbing state always exists which leads to a contradiction.
(2) It is analogous for the case that \(\exists i \in N \text { s.t. }\mu _i=\mu _a\).
Proof of Theorem 4
Suppose that there is no absorbing state, hence we are under the conditions of the system of inequalities (
9) or (
10). It remains to prove the statement on the cycle. The transition function
G has the following behavior: considering that
x grows from 0 to 1, it starts from the value
\(G(0)=\delta _a\), then increases at each point
\(x=\mu _i\) by the quantity
\(q_i\), and decreases by the quantity
\(\delta _a\) at point
\(\mu _a\). Therefore,
\(G(\mu _k)=\delta _a+\sum _{i=1}^kq_i\) and
\(G(\mu _a)=\sum _{i=1}^k q_i\). Then
G(
x) continues to increase at each value
\(\mu _i\) when
x goes from
\(\mu _a\) to 1. It follows that the inequalities (
9) (or (
10)) imply the following properties of the transition function:
(i)The three first inequalities imply that \(G(x)>x\) for all \(x< \mu _a\). Hence the part of the transition function to the left of \(\mu _a\) is strictly above the diagonal and nondecreasing;
(ii)The 4th inequality implies that \(G(\mu _a)<\mu _a\);
(iii)The last inequality implies that \(G(x)<x\) for all \(x>\mu _a\), hence the part of the transition function to the right of \(\mu _a\) including this point is strictly below the diagonal and nondecreasing.
We consider the square delimited by the diagonal points
\((\sum _{i=1}^kq_i,\sum _{i=1}^kq_i)\) and
\((\sum _{i=1}^kq_i+\delta _a,\sum _{i=1}^kq_i+\delta _a)\). We claim that if any point (
x,
G(
x)) is chosen inside this square, the “next” point (
G(
x),
G(
G(
x))) is still inside the square. First observe that
\(\sum _{i=1}^kq_i\) and
\(\sum _{i=1}^kq_i+\delta _a\) are, respectively, the minimum value and the maximum value achieved by
G in the interval
\([\sum _{i=1}^kq_i,\sum _{i=1}^kq_i+\delta _a]\), hence if
x lies in this interval, (
x,
G(
x)) is in the square. Now, taking
x to the right of
\(\mu _a\), we have that
\(\sum _{i=1}^kq_i\le G(x)<x\le \sum _{i=1}^kq_i+\delta _a\), so by the previous observation (
G(
x),
G(
G(
x))) lies in the square. Similarly, if
x is on the left of
\(\mu _a\), then
\(\sum _{i=1}^kq_i\le x<G(x)\le \sum _{i=1}^kq_i+\delta _a\), so that again the image of the point by
G is still in the square.
The number of different values (levels) of G in the square is the number of values \(\mu _i\) in the interval \(]\sum _{i=1}^k q_i,\sum _{i=1}^k q_i+\delta _a]\) plus one (taking into account right-continuity) and plus one corresponding to \(\mu _a\). As this number is finite, the successive points (x, G(x)), \((G(x),G(G(x))),\ldots \) must from some step form a cycle.
We prove the claim on the upper bound. The number of levels of G is maximal when the gap \(q_i\) at each \(\mu _i\) is minimal. The minimal value of \(q_i\) is 1 / n, which yields a total number of levels to be \(n\delta _a+1\) because the total gap is \(\delta _a\).
Proof of Theorem 5
1. Suppose that the state is T with \(t\ge d \) and \(n-t\ge d\). This is possible because by the assumptions \(n_a\ge d\), \(n_c\ge d\), we have \(d\le n/2\). We claim that a transition to any \(Q\in 2^N\) is possible. Indeed, we can have any type of neighborhood, so that the average opinion \(\overline{a}(T)\) in a neighborhood can be any value in \(\{0,1/d,\ldots , 1\}\). It follows that \(p_i^0(T)\) and \(p_i^1(T)\) can be positive for all conformists and all anti-conformists.
2. Consider that either \(t<d\) or \(n-t<d\). It suffices to prove that a transition to some set Q such that \(q\ge d\) and \(n-q\ge d\) is possible to conclude the proof. Suppose \(t<d\) (the other case is similar). Then \(n-t>d\), so that the 0-neighborhood has a positive probability. Supposing that all players take the 0-neighborhood, the next action will be 0 for the conformists and 1 for the anti-conformists. Hence \(Q=N_a\), which does the job as \(|N_a|\ge d\) and \(|N\setminus N_a|=|N_c|\ge d\).
Proof of Theorem 6
Recall that at each time step, a random neighborhood of random size is drawn, for each agent. Each agent has a different threshold but it is fixed (distribution is known)
1. Consider a state T. In order to have for every conformist and anti-conformist a possibility of choosing action 1 and 0, we must have for conformist choosing action 1 \(P(\overline{a}_i\ge \mu _i\,:\,S;d)>0\) for at least one d and choosing action 0 \(P(\overline{a}_i\ge \mu _i\,:\,S;d)<1\) for at least one d in the support. For action 1 we must have T with \(t\ge {\overline{\mu }}{\underline{d}}\) (must work for all agents) and for action 0 we must have \(N\setminus T\) with \(n-t> {\underline{d}}(1-{\underline{\mu }})\). The conditions are inverted for anti-conformists. Then a transition to any Q is possible at next step.
2. Suppose now that
T is such that
\(t<{\overline{\mu }}{\underline{d}}\). Suppose
\(n_a\ge {\overline{\mu }}{\underline{d}}\) and
\(n_a<n- {\underline{d}}(1-{\underline{\mu }})\). (same conditions for
\(n_c\))(hence equivalently,
\(n_a>{\underline{d}}(1-{\underline{\mu }})\) and idem for
\(n_c\)). It follows that
\({\overline{\mu }}{\underline{d}}\le n/2\) and
\({\underline{d}}(1-{\underline{\mu }})<n/2\). Observe that we have then
$$\begin{aligned} t<{\overline{\mu }}{\underline{d}}\le n/2<n-{\underline{d}}(1-{\underline{\mu }}). \end{aligned}$$
Therefore, every conformist can choose action 0 and every anti-conformist can choose action 1, so that a transition to
\(N_a\) is possible. As by assumption
\(n_a\ge {\overline{\mu }}{\underline{d}}\) and
\(n_a<n-{\underline{d}}(1-{\underline{\mu }})\), we are back to Step 1 and a transition to any state
Q is possible.
The case where
\(t\ge n-{\underline{d}}(1-{\underline{\mu }})\) works similarly as we have
$$\begin{aligned} t\ge n-{\underline{d}}(1-{\underline{\mu }})\ge n/2\ge {\overline{\mu }}{\underline{d}}. \end{aligned}$$
Then a transition to
\(N_c\) is possible, which allows then a transition to any state
Q.