Diffusion of binary opinions in a growing population with heterogeneous behaviour and external influence

1.   Introduction

Opinion dynamics in social networks is an area that has received significant attention in recent years ^[28,33]. This body of work has applications in the areas of advertising, election campaigns, opinion evolution in online social networks, and public policy.

One widely used approach to study opinion dynamics in networks is to model it as a stochastic process on a network of individuals. The voter model ^[19] is the most popular model used for such studies. Under the voter model, the network is modeled using a bidirectional graph with the set of individuals represented by nodes. There exists an edge between two individuals if they interact with each other. Opinions of individuals are binary. In each time-slot, a node and one of its neighbours are chosen uniformly at random. The node then adopts the opinion of the chosen neighbour. It is well-known that the voter model dynamics on a $d$-dimensional lattice converges almost surely to a state where all individuals have the same opinion ^[7]. The consensus opinion depends on the initial state of the system. This behaviour is similar to that of a Pólya urn process, where a ball is drawn uniformly at random from the urn at every time-step and it is replaced in the urn along with another ball of same colour. Such phenomenon of reinforcement is found is several real-life processes like opinion evolution, disease transmission, modeling ant walks etc. Pólya process has been used to model opinion evolution in ^[20,32]. Numerous other way of modeling evolution of binary opinions and variants of the voter model have been proposed and studied (See recent surveys ^[1,29]). In the majority-rule version of the voter model, instead of sampling a single neighbour, the updating node/individual adopts the majority opinion in its neighbourhood ^[5,8,11]. Voter model on various kinds of fixed and evolving network topology have been studied ^{[4,10,12,27,34]}. The voter model has also been extended to incorporate biased or stubborn behaviour of individuals ^[25,35]. In ^[26] authors combine some of these extensions to study voter model with majority rule in presence of biased and stubborn individuals. The central question is to understand the conditions for asymptotic consensus and the rate of convergence to the consensus. For instance, in ^[26] authors show that the expected time to reach consensus is $\text{\mathcal O}(\log N)$, where $N$ is the size of the population. Most of these models assume Markovian evolution and ideas from Markov Processes, Mean Field Theory and Branching Processes have been used to address these questions.

In this work, we study a generalization of the voter model and analyze its finite time as well as asymptotic behaviour. Our generalization has two key aspects. Firstly, we model three types of behaviours, namely, strong-willed, conformist, and rebel. We say that an individual is strong-willed when their opinion is not affected by the opinion of their neighbours. Further, we say that an individual is conformist/rebellious when their opinion is positively/negatively affected by the opinion of their neighbours. These three types of behaviours have been studied in ^[31] and ^[14]. In the model proposed in this paper, new individuals are added to the population over time and we allow their initial opinions to depend on the state of the system at the time of joining. We study the asymptotic behaviour of the opinion dynamics of this growing population on a complete network as a function of various system parameters.

Although studying asymptotic behaviour has been the main focus of opinion modeling for many years, in various real-life situations like rumour spread in small communities or online opinion polls, it is important to understand how close does the opinion profile get to the limiting behaviour in a given time-period and what happens in presence of an external influencing agent. Opinion evolution over finite horizon has been studied in ^[3,31]. The information about the finite time behaviour is particularly important for opinion shaping by advertising and/or influencing agencies. In this paper, in addition to the asymptotic behaviour, we also study the effect of external influence over finite time horizons. Opinion manipulation or opinion shaping has been studied before (See ^[9,18,30]) but most of the research is focused on determining which nodes of the network should be influenced to have a favourable cascading effect. In this paper, we are interested in understanding whether it is more advantageous to influence closer to the voting deadline or at the beginning, and how does this depend on the three types of behaviour described above. Characterizing optimal influence strategies over finite time horizons in fixed networks is the focus of ^[16,23,31]. In ^[23], the authors show that if individuals only exhibit strong-willed behaviour, the optimal strategy is to influence towards the end of the finite time horizon, while if individuals are conformists, it may be optimal to influence towards the beginning of the time horizon. In ^[31], the authors show that if individuals are predominantly strong-willed/rebel, the optimal strategy is to influence towards the end of the finite time horizon. While ^[23,31] consider a complete graph between individuals in the network, in ^[16], the authors study the effect of the nature of the graph (random/fixed) on the nature of optimal influencing strategies. Unlike ^[16,23,31], where the network of individuals is fixed, in this work we model a system with new individuals entering the network over time. However, we still restrict our analysis to complete graphs, thus when the chosen individuals behave conformist or rebellious they take into account the complete opinion profile of the population at that time.

The main contributions of this work are as follows:

Asymptotic Behaviour: As mentioned above, while the three types of behaviour studied in this paper are similar to that of ^[14], this paper advances the investigation of asymptotic properties of heterogenous populations by incorporating the feature of growing population with arbitrary but fixed number individuals, extending beyond the single-individual addition model. This gives us an opportunity to explore the dependence of the opinion profile on the ratio of number of people added versus the number of people chosen for opinion update at each step. Our analysis of asymptotic behaviour is divided into three parts:

(i) when the probability of an incoming individuals holding opinion $1$ or $0$ is independent of the current state of the system.

(ii) when the probability of an incoming individuals holding opinion $1$ is proportional to the fraction of individuals with opinion $1$ in the system at that time.

(iii) when the probability of an incoming individuals holding opinion $1$ is proportional to the fraction of individuals with opinion $0$ in the system at that time.

Since the individuals can behave strong-willed with positive probability, in all the three cases the limiting fraction of people with either opinion converges almost surely to a deterministic limit, independent of the initial configuration of opinion. The main result on the limiting opinion profile allows us to study the dependence of the limiting fraction of individuals with either opinion on the ratio of number of individuals being chosen for opinion update at every time-step and the number of individuals being added to the population. We also compare the limiting fraction of individuals with opinion $1$ for the three cases and obtain conditions that determine what kind of behaviour of the incoming individuals leads to a higher fraction of people with opinion $1$ asymptotically. Further, we observe that in the Central Limit Theorem (CLT) type results for cases (i) and (iii), the critical and superdiffusive regimes do not exist, while case (ii) exhibits all the three regimes. Explicit conditions on system parameters for transitions from subdiffusive, critical and superdiffusive regimes are obtained.

Finite Time Behaviour: We study the system over a time-horizon of $T$ consecutive time-slots out of which external influence is exerted in $bT$ time-slots for some $b \in (0, 1)$. The opinion dynamics of the network under external influence tends to move towards a specific direction preferred by the influencer as compared to its organic evolution in the absence of any external influence. An influence strategy is defined by the time-slots in which external influence is exerted. We show that the optimal influence strategy, i.e., the strategy that maximizes the number of nodes with the opinion supported by the influencer at the end of the time-horizon is a function of the number of new nodes joining the network in each time-slot, and the mechanisms (i)–(iii) via which new nodes form their initial opinion.

The paper is organized as follows. In Section 2 we describe the opinion evolution model. In Section 3 we state the results concerning the asymptotic properties of the system. More precisely, we obtain the limiting fraction of people with opinion $1$ for various cases and state the fluctuation limit theorems for each case. In Section 4, we use Martingale concentration to show that the random process governing the evolution of fraction of people with either opinion can be approximated by trajectories of an ODE. Using this approximation we analyse the finite-time behaviour of the fraction of people with opinion $1$ and its dependence on certain parameters of the system. Further, in Section 4.3, we introduce external influence and obtain optimal influencing strategies to maximize the expected fraction of people with opinion $1$ at time $T$. Finally, Section 5 contains the proofs of the theorems from Sections 3 and 4. We conclude with discussion on the results obtained in this paper and possible future directions in Section 6.

2.   Setting

We consider a growing population with binary opinions: $1$ or $0$ (denoted by $1$ and $0$ respectively). We start with $M_0 > 0$ individuals at time $t = 0$. Let $X_t$ denote the fraction of people with opinion $1$ at time $t$. For $t \geq 1$, at each discrete time step, the system evolves in two steps:

1. A fixed number of individuals, denoted by $R_c (\leq M_0)$, are chosen uniformly at random and they update their opinions.

2. A fixed number of individuals, denoted by $R_a$ having opinion $1$ with probability $\alpha_t$ and $0$ with probability $1-\alpha_t$, are added to the population. We study three cases.

(i) $\alpha_t = \alpha \ \forall t \geq 1$ and some fixed $\alpha \in [0, 1]$. That is, probability of the new individuals having opinion $1$ remains constant throughout the fixed time interval $[0, T]$.

(ii) $\alpha_t = \alpha_C X_t \ \forall t \geq 1$ and some fixed $\alpha_C \in [0, 1]$, that is the probability of the new individuals having opinion $1$ is proportional to the fraction of individuals of opinion $1$ in the population at time $t$.

(iii) $\alpha_t = \alpha_R (1-X_t) \ \forall t \geq 1$ and some fixed $\alpha_R \in [0, 1]$, that is the probability of the new individuals having opinion $1$ is proportional to the fraction of individuals of opinion $0$ in the population at time $t$.

We now describe how the opinions of the chosen individual are updated. Define random variables $\{ I_i(t) \}_{1 \leq i \leq M_t}$, $t \geq 0$ taking values in $\{0, 1\}$, where $I_i(t)$ denotes the opinion of the $i^{th}$ individual at time $t$. Note that the total number of individuals at time $t+1$ is given by $M_{t+1} = M_t + R_a$. Thus, the population increases linearly and deterministically in $t$. Define random variables: $Y_t = \sum\limits_{i = 1}^{M_t} I_i(t)$ and $N_t = M_t - Y_t$ as total number of people with opinion $1$ and the total number of people with opinion $0$ at time $t$ respectively. Then, $X_t = \frac{Y_t}{M_t}$. The opinion of a chosen individual $j$ evolves in time-slot according the following transition probabilities.

We model three types of behaviour in the population.

$–$ Strong-willed: the chosen individuals are not influenced by peers and change their opinions independent of anyone else in the population. In this case, $p_t = p$ and $q_t = q$.

$–$ Conformist: the chosen individuals change their opinion based on the majority opinion at that given time and tend to adopt the "popular" opinion at that time. In this case, $p_t = p (1-X_t)$ and $q_t = q X_t.$

$–$ Rebel: the chosen individuals change their opinion based on the majority opinion at that given time and tend to adopt the "unpopular" opinion at that time. In this case, $p_t = p X_t$ and $q_t = q (1-X_t).$

Let $\lambda, \mu \in [0, 1]$. At each time-step $t$, with probability $\lambda$ the chosen individuals behave as strong-willed, with probability $\mu$ they behave as conformist and with probability $1-\lambda-\mu$ they behave rebellious. Let $O_{t+1}$ be the change in the number of people of opinion $1$ from time $t$ to $t+1$. That is, $Y_{t+1} = Y_t + O_{t+1}$. Then, we have

The random variable $O_{t+1}$ depends on the two independent processes that we can write as

where $O^{R_c}_{t+1}$ is the change due to opinion evolution of the chosen individuals and $O^{R_a}_{t+1}$ is the change due to the newly added individuals. We have

where $r = R_c/R_a$ is the ratio of people chosen and people added at each time step. Note that $\mathbb{E}[O_{t+1}|\mathcal{F}_t]$ is a linear function of $X_t$ provided (1) $\lambda + 2 \mu = 1$ or (2) $p = q$. The first case is that of a mixed population where probability of a chosen individual being conformist is same as that of her being a rebel, and the second case is inspired from the conventional voter model transition rule. Throughout this paper, we assume the following.

Assumption 1. We assume that the probability of a chosen individual behaving as conformist is same as that of her behaving as a rebel. That is, $\lambda + 2 \mu = 1$. Further, we assume that $R_a > 0$.

As we shall see, the results for the case $p = q$ can be obtained as a special case under Assumption 1. The linearity of $\mathbb{E}[O_{t+1}|\mathcal{F}_t]$ as a function of $X_t$ implies that $\mathbb{E}[X_{t+1}|\mathcal{F}_t]$ is linear in $X_t$. This allows us to give an ODE approximation for the recursion with explicit error bounds. In the next section, we investigate the asymptotic properties of the fraction of people with opinion $1$.

3.   Asymptotic behaviour

We use the stochastic approximation theory to analyse the behaviour of fraction of individuals of opinion $1$. Note that the recursion in Eq (5.2) is of the form

where $1/a_t$ is a linear function of $t$, $h$ is a linear function of $X_t$ (whenever $\lambda+ 2\mu = 1$), $S_t$ is a square integrable zero mean martingale and $x_t$ is bounded. Therefore the limiting point of the recursion is same as that of the stable limit point of the ODE $\dot{x}_t = h(x_t)$ (See Chapter 1 in ^[2]). Thus, the following is immediate.

Theorem 3.1. Under Assumption 1, $X_t \to X^*$ almost surely as $t \to \infty$, where

Note that for large $r$, that is when the number of individuals chosen at every step for opinion update is much larger than the number of people being added to the population at every step, $X^*$ is approximately $\frac{q}{p+q}$ in all cases. That is, when $R_c > > R_a$, the asymptotic composition of the opinion in the population does not depend on the initial inclination of people getting added to the population or on the behaviour of people chosen at each step. For small $r$, in cases $\alpha_t = \alpha$ and $\alpha_R (1-X_t)$, the limiting fraction of of people with opinion $1$ is close to $\alpha$ and $\frac{\alpha_R}{1+\alpha_R}$ respectively, whereas for $\alpha = \alpha_C X_t$, it is close to zero. A similar trend is observed when everyone in the population is conformist with probability $1$.

Remark 1. For the case $p = q$, we get

which turns out to be a special case of Theorem 3.1. This is because the ODE under assumption $p = q$ is same as that obtained under Assumption 1 along with $p = q$. However, as we shall see the fluctuations of $X_t$ around the limit $X^*$ have a different behaviour under $\lambda + 2 \mu = 1$ and $p = q$ and latter cannot be obtained as special case of the former.

In the corollary below we compare the limiting fraction of people with opinion $1$ in the three cases and obtain conditions that lead to a larger fraction of people with opinion $1$ asymptotically.

Corollary 3.2. Let $X_S^*, X^*_C$ and $X^*_R$ denote the limiting fraction of individuals with opinion $1$ asymptotically for cases $\alpha_t = \alpha, \alpha_t = \alpha_C X_t$ and $\alpha_t = \alpha_R (1-X_t)$ respectively. Under Assumption 1,

(i) $X_S^* \geq X_R^*$ if if $\alpha \geq \alpha_R$ or $\alpha \geq 1-X^*_S$. In particular, $X^*_S \geq X^*_R$ when $\alpha_R = \alpha$.

(ii) $X^*_S \geq X^*_C$ if $\alpha \geq \alpha_C$ or $\alpha \geq X^*_S$. In particular, $X^*_S \geq X^*_C$ when $\alpha_C = \alpha$.

(iii) $X^*_C \geq X^*_R$ if $(1-\mu)r \left(q \alpha_C - p \alpha_R \right) - \alpha_R + \alpha_R \alpha_C \geq 0$. In particular, $X^*_C \geq X^*_R$ if $\alpha_C = 1$ and $q \geq p$ or $\alpha_C = \alpha_R = \alpha \geq 1 + (1-\mu)r(p-q)$.

Remark 2. Note that if $\alpha_R = 0$, in case (iii), new people have opinion $0$ with probability $1$ and therefore $X_C^* \geq X_R^*$. This is straightforward from Eq (5.5). Similarly, when $\alpha_C = 0$, $X^*_C \leq X^*_R$. By the argument in the proof above, we also get that $X^*_C \leq X^*_R$ whenever $\alpha_R = 1$ and $p \geq q$.

Finally, we show that a phase transition in the fluctuation around the limit exists only for the case when $\alpha_t = \alpha_C X_t$, that is when the probability of new individuals having opinion $1$ is directly proportional to the fraction of individuals with opinion $1$ at that time. The classification of diffusive, critical and superdiffusive regime is based on the values of parameters $r, p, q, \mu$ and $\alpha_C$. In the other two cases viz. $\alpha_t = \alpha$ and $\alpha_t = \alpha_R(1-X_t)$, we only have the diffusive case with $\sqrt{t}$ scaling.

Theorem 3.3. Let $X_S^*, X^*_C$ and $X^*_R$ be as in Corollary 3.2 and suppose Assumption 1 holds.

1. For $\alpha_t = \alpha$, as $t \to \infty$

where $\sigma = \frac{R_a}{2R_a[r(1-\mu)(p+q)+1]-1} \left[r(1-\mu)(p-q)\left(\frac{r(1-\mu)q+\alpha}{r(1-\mu)(p+q)+1}\right)+r(1-\mu)q+\alpha(1-\alpha)\right]$.

2. For $\alpha_t = \alpha_R (1-X_t)$, as $t \to \infty$

where

3. For $\alpha_t = \alpha_C X_t$, as $t \to \infty$

(a) if $\alpha_C < r(1-\mu)(p+q)+1-\frac{1}{2R_a}$ then

where

(b) if $\alpha_C = r(1-\mu)(p+q)+1-\frac{1}{2R_a}$ then

where $\sigma_C = \left[(r(1-\mu)(p-q)+\alpha_C)\left(\frac{r(1-\mu)q}{r(1-\mu)(p+q)+1-\alpha_C}\right)+r(1-\mu)q\right]$.

(c) if

then as as

almost surely converges to a finite random variable, where

A similar result can be obtained for the case $p = q$. The proofs of the above theorems are in Section 5.

The scaling limits of this nature can also be obtained for general reinforced stochastic processes, including urn models and reinforced random walk. While we have used stochastic approximation theory, such limiting behaviour can also be obtained by exploiting the martingale structure as done in ^[15,24] for urn models or using results from ^[17]. As mentioned before, the random process governing the reinforcement of opinions is similar to the behaviour of a generalized two-colour Pólya urn. The new individuals being added to the population corresponds to adding new balls to the urn independently or based on the composition of the urn at that time. The chosen individuals correspond to multiple drawings of balls from the urn that are then replaced after some re-colouring. In this context, the behaviour of $X_t$ observed here is similar in spirit to that observed in ^[15,21,24] for the fraction of balls of a given colour in generalized two-colour Pólya urns.

In the next section, we study the same model and obtain optimal influencing strategies over a finite time horizon.

4.   Finite time behaviour and optimal influencing strategies

We now analyse the evolution of opinions over a finite time interval $[0, T]$. We are interested in understanding how the parameters of the system affect the final opinion profile at time $T$ and what kind of influencing strategies result in a larger fraction of people with opinion $1$ at time $T$. The key mathematical idea is to approximate the random process of the fraction of people with a given opinion with an ODE.

4.1.   ODE approximation

It can be shown that under Assumption 1, the iterates of the recursion for $X_t$ remain close to the trajectories of the ODEs given by

Thus it is enough to analyse ODE of the form

where

The solution for ODE in Eq (4.1) is given by:

The following theorem asserts that the recursion $X_t$ remains close to the trajectories of the ODE in Eq (4.1).

Theorem 4.1 (Martingale concentration). Suppose Assumption 1 holds. Let $x_T$ denote the solution at time $T$ of the ODE in Eq (4.1). Then for $D_{M_0} = {{\mathcal O}}\left(\frac{1}{M_0}\right)$,

for some constant $C > 0$.

The constant $C$ depends on various parameters of the system, including the initial population. Figures 1 and 2 illustrate how well the ODE solution tracks the simulated trajectories of the recursion for $X_t$. In the rest of the paper, we use this approximation to analyse the recursion by studying the ODE solution. We refer to the random process by $X_t$ and the ODE solution by $x_t$.

4.2.   Effect of $r$ on the final opinion profile

We first put the above ODE approximation to use for analysing the dependence of the final $x_T$ (which approximates the fraction of individuals with opinion $1$ at the time of voting) on $r$, that is the ratio of number of people who may change their opinion at time $t$ and the number of people added to the population at each time-step $t$. Clearly, the behaviour of $x_T$ depends of $p, q, x_0$ and $\alpha_t$. Differentiating the solution of Eq (4.1) at $T$ with respect to $r$ we get

where $\tau_k = k+M_0/R_a$. We consider the $\alpha_t = \alpha$ case first. In this case,

Clearly, for $\alpha = \frac{q}{q+p}$, we get that $x_T^\prime$ is positive for $x_0 > \frac{q}{p+q}$, negative for $x_0 < \frac{q}{p+q}$ and zero for $x_0 = \frac{q}{p+q}$. For $\alpha > \frac{q}{q+p}$, it is immediate that $x_T^\prime < 0$ for

For,

Observe that for $T$ not very small,

where

Therefore, $x_T^\prime < 0$ for all $r$ provided $\alpha > \frac{q}{q+p}$. A similar argument for $\alpha < \frac{q}{q+p}$ shows that $x_T$ is a non-decreasing function of $r$. For $\alpha = \frac{q}{q+p}$, we get

Therefore,

● for $x_0 > \frac{q}{p+q}$, $x_T$ is a non-increasing function of $r$.

● for $x_0 = \frac{q}{p+q}$, $x_T$ is a constant function of $r$.

● for $x_0 < \frac{q}{p+q}$, $x_T$ is a non-decreasing function of $r$.

Using similar arguments we characterize the behaviour of $x_T$ as a function of $r$ for the rest of the cases as well. Table 1 details the behaviour of the final fraction of individuals with opinion $1$ as a function of $r$.

In the next section, we state and discuss the main result for the finite time opinion evolution under external influence and optimal strategies for influencing the dynamics to obtain higher number of individuals with opinion $1$ at the end of the finite time horizon.

4.3.   Optimal influencing strategies over finite time horizon

In this section, we study the opinion evolution over a finite time interval $[0, T]$. We assume that there is an external influencing agency with a limited budget that tries to skew the opinion of the population in their favour at the end of time $T$. Due to budgetary constraints, the advertising agency can influence the opinion in exactly $bT$ of the $T$ time-slots, where $b \in [0, 1]$ is such that $bT \in \mathbb{N}$. The influence is exerted by manipulating the transition probabilities of the Markov process defined in Eq (2.1). That is, if the chosen individuals are being externally influenced in time-slot $t$, $p_t = \tilde{p}$ and $q_t = \tilde{q}$, else, their opinion evolves as described before. Without loss of generality, we assume that the aim of the advertising agency is to maximise the number of individuals with the opinion $1$ at the end of the $T$ time-slots. Similar model of opinion evolution in presence of external influence has been studied for fixed population in ^[31]. Our aim is to obtain optimal influencing strategies in different regimes depending on the model parameters. In particular, we want to study the dependence on $R_c$ and $R_a$. We begin by defining influencing strategy and what we mean by optimality here.

Definition 4.2 (Influencing strategy). An influencing strategy $\mathcal{S} \in [0, 1]^T$ is defined as binary string of length $T$ that has exactly $bT$ number of $1$s. For all $i \in \{0, \dots, T-1 \}$ such that $\mathcal{S}_i = 1$, the transition parameters are $p_i = \tilde{p}$ and $q_i = \tilde{q}$. The strategies to influence in the first $bT$ and the last $bT$ time-slots are denoted by $\mathcal{S}_F$ and $\mathcal{S}_L$ respectively.

For two strategies $\mathcal{S}_1$ and $\mathcal{S}_2$, we write $\mathcal{S}_1 \gg \mathcal{S}_2$ if influence according to $\mathcal{S}_1$ leads to a higher expected number of $1$ at the end of time $T$ than the expected number of $1$ at the end of time $T$ under $\mathcal{S}_2$.

Definition 4.3 (Optimal strategy). A strategy is called optimal if the influence according to that strategy results in a higher expected number of $1$ at the end of time $T$ than the expected number of $1$ at the end of time $T$ using any other influence strategy.

Thus, an optimal strategy $\mathcal{S}^*$ is such that $\mathcal{S}^* \gg \mathcal{S}$, where $\mathcal{S}$ is any other collection of $bT$ time-slots to be influenced. As we shall see, due to monotonicity, in most cases, influencing the first or the last $bT$ slots is optimal. We assume that the influencing strategy is rational. That is, during influence, the probability of switching from $0$ to $1$ increases from what it is when the individuals behave strong-willed. Similarly, under rational influence the probability of switching from $1$ to $0$ decreases. More, precisely, we have the following assumption.

Assumption 2 (Rational influence). We assume that the external influence is such that ${ \tilde{p} } < { \tilde{q} }$, ${ \tilde{p} } < p$ and $q < { \tilde{q} }$.

We now state our results for optimal strategies for the cases $\alpha_t = \alpha$, $\alpha_t = \alpha_CX_t$ and $\alpha_t = \alpha_R(1- X_t)$. Again, a transition in optimality of influencing strategy is observed in the case $\alpha_t = \alpha_C X_t$ at the critical value $\alpha_C = r({ \tilde{p} }+ { \tilde{q} })$.

Figures 3 and 4 compare the strategies $\mathcal{S}_L, \mathcal{S}_F$ and a strategy $\mathcal{S}$ where the slots in the interval $[0.4T, 0.7T]$ are influenced. In Figure 5, we compare $\mathcal{S}_L, \mathcal{S}_F$ and a split strategy $\mathcal{S}$ where the influence is over time-slots in the intervals $[0.3T, 0.5T]$ and $[0.8T, T]$. The figures illustrate that $\mathcal{S}_L$ is optimal for the cases $\alpha_t = \alpha$ and $\alpha_R(1-X_t)$ whereas there is a transition in optimality of the strategies for a certain threshold value of $\alpha_C$ in the case when $\alpha = \alpha_C X_t$.

Theorem 4.4. Suppose $\delta = r[({ \tilde{p} }+ { \tilde{q} })-(1-\mu)(p+q)] = 0$. Then, under Assumptions 1 and 2,

1. For $\alpha_t = \alpha$, it is optimal to influence in the last $bT$ slots.

2. For $\alpha_t = \alpha_CX_t$,

(a) if $r({ \tilde{p} }+ { \tilde{q} }) > \alpha_C$, it is optimal to influence in the last $bT$ slots.

(b) If $r({ \tilde{p} }+ { \tilde{q} }) < \alpha_C$, it is optimal to influence in the first $bT$ slots.

(c) If $r({ \tilde{p} }+ { \tilde{q} }) = \alpha_C$, all strategies perform equally well.

3. For $\alpha_t = \alpha_R(1-X_t)$, it is optimal to influence in the last $bT$ slots.

The main idea is to compare the strategies $\mathcal{S}_L$ and $\mathcal{S}_F$ and then get optimality using monotonicity of the ODE solution with respect to the initial conditions. Suppose $X_{T}^{L}$ and $X_{T}^{F}$ denote the corresponding ODE solutions for the influencing strategies $\mathcal{S}_L$ and $\mathcal{S}_F$, respectively. Then, we have

where $\Delta = \frac{r { \tilde{q} }+B}{r({ \tilde{p} }+ { \tilde{q} })+1+A} - \frac{r(1-\mu)q+B}{r(1-\mu)(p+q)+1+A}$. Similarly,

Define $\widetilde{T} = \frac{T}{1+ \frac{M_{0}}{R_{a}}}$ and $D_T = X_{T}^{L} - X_{T}^{F}$ to be the difference between fraction of people with opinion $1$ at time $T$ when under influencing strategies $\mathcal{S}_L$ and $\mathcal{S}_F$. We get

To compare $\mathcal{S}_L$ and $\mathcal{S}_F$, it is enough to analyse whether $D_T$ is positive or negative. The detailed proof is in Section 5.

We need the assumption $\delta = 0$ to ensure the mathematical tractability of the expression for $D_T$. In general, when $b$ is bounded away from $0$ and $1$ (which is reasonable since we would like to study scenarios where influence is over a non-trivial subset of $[0, T]$) and $T$ is large, we have

Using these approximations, we get

For large ${ \widetilde{T} }$, the second and the third term are very small. Since for $\alpha_t = \alpha$ or $\alpha_R$, $r(p+q)+1+A > 1$, we have

which along with $\Delta > 0$, implies $D_T \geq 0$. Combining this with the optimality argument, we get that if the voting happens after a large time $T$, in case $\alpha_t = \alpha$ or $\alpha_R$, it is better to influence towards the end. Also, if $r < < 1$ and $\alpha_t = \alpha$, $D_T \approx 0$, making all strategies more or less comparable in terms of effectiveness for getting more $1$'s at the end of time $T$.

5.   Proofs

In this section, we prove the results from previous sections. The main tool to prove the results from Section 3 is the stochastic approximation theory. For the results in Section 4, we first prove Theorem 4.1 to show that the discrete dynamics can be approximated well by an O.D.E. and then use the corresponding O.D.E. to show the transition in optimal influence strategy as stated in Theorem 4.4.

5.1.   Proofs: asymptotic results

We first prove the results establishing asymptotic behaviour of $X_t$. From Eq (2.2) we have

where $S_{t+1} = O_{t+1} - \mathbb{E}[O_{t+1}|\mathcal{F}_t]$ is a zero-mean martingale with respect to $\{ \text{\mathcal F}_t = \sigma (O_s; 0 \leq s \leq t) \}_{t \geq 1}$. We have,

Using this in Eq (5.1) and substituting $p_t = \lambda p + \mu p(1-X_t) + (1-\lambda-\mu) p X_t$ and $q_t = \lambda q + \mu qX_t + (1-\lambda - \mu) q (1-X_t)$, we get the following recursion.

where from Eq (2.3) we get that

The recursion for $X_t$ can thus be written as a stochastic approximation scheme (See ^[2]) and the corresponding ODE is given by

where $A$ and $B$ are as in Eq (4.1). It is easy to verify that Eq (5.2) satisfies the conditions of a stochastic approximation scheme since the martingale difference is bounded, $X_t \leq 1 \forall t \geq 0$, $h(\cdot)$ is Lipschitz in $X_t$ and the step-size $1/M_{t}$ is inverse of a linear function of $t$. From the stochastic approximation theory, we know that the recursion for $X_t$ converges almost surely to the stable limit points of the ODE, which are given by $h(x_t) = 0$. Define

Proof of Theorem 3.1. Under Assumption 1, the corresponding ODE is given by

where $r = \frac{R_c}{R_a}$. Clearly, $x_t = \frac{rq(1-\mu) + B }{r(1-\mu)(p+q)+1+A}$ is a limit point. Further, it is easy to verify that for $\lambda+2\mu = 1$ or $p = q$, $\mathcal{D}(x) < 0$ for all $x$. Thus, $\frac{rq(1-\mu) + B }{r(1-\mu)(p+q)+1+A}$ is a stable fixed point. Thus, as $t \to \infty$, $X_t \to X^*$ almost surely where

The $p = q$ case mentioned in the remark 1 is obtained in the same way or by simply putting $p = q$ in Eq (5.4) above since the ODE for $p = q$ is a special case of the ODE under Assumption 1. In general, $h(x_t)$ is a polynomial of degree $2$ in $x_t$. Let $\rho_1$ and $\rho_2$ be the roots $h(x_t) = 0$ with $\rho_1 > \rho_2$. Note that

and

Thus, $\mathcal{D}(x) : = R_a(1-\lambda-2\mu)(q-p)[2x-(\rho_1+\rho_2)]$ and we get the following.

1. for the case $\lambda+2\mu > 1$ and $q > p$ or $\lambda+2\mu < 1$ and $q < p$, $\rho_1 > 0$ and $\rho_2 < 0$ as $\rho_1\rho_2 < 0$. Also, $\mathcal{D}(\rho_1) < 0$ and $\mathcal{D}(\rho_2) > 0$. So, in these cases, $\rho_1$ is a stable limit point.

2. For the case $\lambda+2\mu > 1$ and $q < p$ or $\lambda+2\mu < 1$ and $q > p$, $\rho_1 > 0$ and $\rho_2 > 0$ as $\rho_1\rho_2 > 0$ and $\rho_1+\rho_2 > 0$. Also, $\mathcal{D}(\rho_1) > 0$ and $\mathcal{D}(\rho_2) < 0$. Hence, in these cases, $\rho_2$ is a stable limit point.

While the asymptotic analysis is possible, a martingale argument for ODE approximation as done in Section 4 is not possible when $h$ is non-linear. Further, the ODE $\dot{x}(t) = h(x_t)$ yields fairly complicated solutions and obtaining optimal strategies is non-tractable.

Proof of Corollary 3.2. We first compare $X_S^*, X_R^*$.

Thus, $X_S^* - X_R^* \geq 0$ iff $\alpha - \alpha_R(1-X_S^*) \geq 0$. Therefore, $\alpha \geq \alpha_R$ or $\alpha \geq 1-X^*_S$ implies $X_S^* \geq X_R^*$. Next we compare $X_S^*, X_C^*$.

Clearly, $X_S^* - X_C^* \geq 0$ iff $\alpha \geq \alpha_C X^*_S$. Thus, $\alpha \geq \alpha_C$ or $\alpha \geq X_S^*$ implies $X_S^* - X_C^* \geq 0$. Further, when $\alpha_C = \alpha_R = \alpha$, $X_S^* \geq X^*_C$ for all $\alpha \in [0, 1]$.

For the case $\alpha_t = \alpha_R(1-X_t)$ and $\alpha_t = \alpha_C X_t$ we get that

which holds if and only if

Clearly, this holds for $\alpha_C = 1$ and $q \geq p$ since $p \geq p \alpha_R$. Further, for $\alpha_C = \alpha_R = \alpha$, we have $X^*_C \geq X^*_R$ iff $\alpha \geq 1 + (1-\mu)r(p-q)$.

We now prove the fluctuation limit theorem.

Proof of Theorem 3.3. We use results from ^[36]. We first compute $\Gamma = \lim\limits_{t \to \infty} E[S^2_{t+1}|\mathcal{F}_t]$. Note that $E[S^2_{t+1}|\mathcal{F}_t] = E[(O_{t+1}-E[O_{t+1}|\mathcal{F}_t])^2|\mathcal{F}_t]$. We have

The term $\frac{R^2_c}{M_t}\left((1-X_t)q_t-X_tp_t\right)^2$ goes to zero as $t\xrightarrow{}\infty$. For $p_t = \lambda p + \mu p(1-X_t) + (1-\lambda-\mu) p X_t$ and $q_t = \lambda q + \mu qX_t + (1-\lambda - \mu) q (1-X_t)$ we get that $\lim\limits_{t \to \infty}E[S^2_{t+1}|\mathcal{F}_t]$ is same as

where $A_1 = \begin{cases} 0 \ & \text{ for }~~ \alpha_t = \alpha \\ -\alpha^2_C \ & \text{ for }~~ \alpha_t = \alpha_C X_t \\ -\alpha^2_R\ & \text{ for }~~ \alpha_t = \alpha_R (1-X_t) \end{cases}, \qquad A_2 = \begin{cases} 0 \ & \text{ for }~~ \alpha_t = \alpha \\ \alpha_C \ & \text{ for }~~ \alpha_t = \alpha_C X_t \\ 2{\alpha_R}^{2}-\alpha_R \ & \text{ for }~~ \alpha_t = \alpha_R (1-X_t) \end{cases}$

and, $A_3 = \begin{cases} \alpha(1-\alpha) \ & \text{ for }~~ \alpha_t = \alpha \\ 0 \ & \text{ for }~~ \alpha_t = \alpha_C X_t \\ \alpha_R(1-\alpha_R) \ & \text{ for }~~ \alpha_t = \alpha_R (1-X_t). \end{cases}$

Under Assumption 1, we get

We now compute the limiting variance $\sigma$. Thus using Theorems 2.1–2.3 from ^[36] we have:

● For $-\mathcal{D}h(X^*) > \frac{1}{2}$, $\sigma = \int_{0}^{\infty}e^{-(-\mathcal{D}h(X^*) - \frac{1}{2})u}\Gamma e^{-(-\mathcal{D}h(X^*) - \frac{1}{2})u}du$.

● For $-\mathcal{D}h(X^*) = \frac{1}{2}$, $\sigma = \lim\limits_{t \to \infty} \frac{1}{\log t} \int_{0}^{\log t}e^{-(-\mathcal{D}h(X^*) - \frac{1}{2})u}\Gamma e^{-(-\mathcal{D}h(X^*) - \frac{1}{2})u}du$.

Therefore, whenever $-\mathcal{D}h(X^*) = R_a(r(1-\mu)(p+q)+1+A) > \frac{1}{2}$ we have,

Thus, with Assumption 1, we get the following.

(a) For $\alpha_t = \alpha$ and $X^* = \frac{r(1-\mu)q+\alpha}{r(1-\mu)(p+q)+1}$, we get $\mathcal{D}h(X^*) = -R_a(r(1-\mu)(p+q)+1)$. Therefore,

where $\sigma = \frac{R_a}{2R_a[r(1-\mu)(p+q)+1]-1} \left[r(1-\mu)(p-q) \left(\frac{r(1-\mu)q+\alpha}{r(1-\mu)(p+q)+1}\right)+r(1-\mu)q+\alpha(1-\alpha)\right]$.

(b) For $\alpha_t = \alpha_R (1-X_t)$ and $X^* = \frac{r(1-\mu)q+\alpha_R}{r(1-\mu)(p+q)+1+\alpha_R}$, we get $\mathcal{D}h(X^*) = -R_a[r(1-\mu)(p+q)+1+\alpha_R]$. Therefore,

where

(c) For $\alpha_t = \alpha_C X_t$ and $X^* = \frac{r(1-\mu)q}{r(1-\mu)(p+q)+1-\alpha_C}$

(i) if $-\mathcal{D}h(X^*) = R_a[r(1-\mu)(p+q)+1-\alpha_C] > \frac{1}{2}$ that is $\alpha_C < r(1-\mu)(p+q)+1-\frac{1}{2R_a}$ then

with $\sigma_C = \frac{R_a}{2R_a[r(1-\mu)(p+q)+1-\alpha_C]-1} \left[(r(1-\mu)(p-q)+\alpha_C)\left(\frac{r(1-\mu)q}{r(1-\mu)(p+q)+1-\alpha_C}\right)+ r(1-\mu)q\right].$

(ii) if $-\mathcal{D}h(X^*) = R_a[r(1-\mu)(p+q)+1-\alpha_C] = \frac{1}{2}$ that is $\alpha_C = r(1-\mu)(p+q)+1-\frac{1}{2R_a}$ then

with $\sigma_C = \left[(r(1-\mu)(p-q)+\alpha_C)\left(\frac{r(1-\mu)q}{r(1-\mu)(p+q)+1-\alpha_C}\right)+r(1-\mu)q\right]$.

(iii) if $-\mathcal{D}h(X^*) = R_a(r(1-\mu)(p+q)+1-\alpha_C) < \frac{1}{2}$ that is $\alpha_C > r(1-\mu)(p+q)+1-\frac{1}{2R_a}$ then as $t \to \infty$, $t^{-\mathcal{D}h(X^*))}(X_t-X^*)$ almost surely converges to a finite random variable.

This completes the proof.

A similar argument can be used to obtain scaling limits for the case $p = q$ as well. We get

Following the same argument as above yields the following.

(a) For $\alpha_t = \alpha$ and $X^* = \frac{r(1-\mu)q+\alpha}{2r(1-\mu)q+1}$ we get $\mathcal{D}h(X^*) = -R_a[2r(1-\mu)q+1]$ and Eq (5.7) holds with

(b) For $\alpha_t = \alpha_R (1-X_t)$ and $X^* = \frac{r(1-\mu)q+\alpha_R}{2r(1-\mu)q+1+\alpha_R}$, we get $\mathcal{D}h(X^*) = -R_a[2r(1-\mu)q+1+\alpha_R]$ and Eq (5.8) holds with

(c) For $\alpha_t = \alpha_C X_t$ and $X^* = \frac{r(1-\mu)q}{2r(1-\mu)q+1-\alpha_C}$. If $-\mathcal{D}h(X^*) = R_a(r(1-\mu)(p+q)+1-\alpha_C) = \frac{1}{2}$ then Eq (5.9) holds with

Thus, unlike for the limiting fraction $X^*$, the limiting second moment or the variance for the case $p = q$ cannot be obtained as a special case of $\lambda+2\mu = 1$.

5.2.   Proofs: ODE approximation and optimal influencing strategy

In this section, we prove results from Section 4. We use a Martingale Concentration Inequality to prove the ODE approximation (from Section 4.1) of the recursion of $X_t$ and then use the approximation to prove Theorem 4.4 for optimal influencing strategy.

Proof of Theorem 4.1. Under Assumption 1, the recurrence is given by

This gives,

where $M'_{t+1} = \frac{M_{t+1}}{R_a}$. Thus,

Define $\alpha_t = \left(1 - \frac{r(p + q)(1-\mu) + 1+A}{M'_{t+1}} \right), \beta_t = \frac{r(1-\mu)q+B }{M'_{t+1}}$ and

Note that $Z_t$ is an $\{\mathcal{F}_t\}_{t\geq 0}$-martingale by definition. For a fixed $T$, define $Y_t = \left(\prod_{k = 0}^{T-1} \alpha_k \right) Z_t$ is also an $\{\mathcal{F}_t\}_{t\geq 0}$-martingale. Using Azuma-Hoeffding inequality, we get

where $|Y_{t}-Y_{t-1}| \leq c_t$ for all $1 \leq t \leq T$. We first obtain a reasonable bound on $|Y_{t}-Y_{t-1}|$. We have

From Lemma 2 in ^[6], we get $\Big \vert \prod_{k = t}^{T-1} \alpha_k \Big \vert \leq K \left(\frac{T}{t}\right)^{- { C^\prime }}$, where ${ C^\prime } = r(p+q)(1-\mu)+1+A$ and $K = K({ C^\prime }, M_0/R_a)$ is a positive constant. Further, $\vert X_t - X_{t-1} \alpha_{t-1} - \beta_{t-1} \vert \leq \frac{B}{t}$ for some constant $B > 0$. Then, $\sum\limits_{t = 0}^T c^2_t = T^{-2 { C^\prime }} \sum\limits_{t = 1}^T K^2 B^2 t^{2 { C^\prime }-2} \leq \frac{K^2B^2}{(2 { C^\prime }-1)T}$. This implies,

Note $2 { C^\prime }-1 > 0$. Equivalently, we have

Next, we show that $\sum\limits_{i = 0}^{t-1} \beta_i \prod_{j = i+1}^{T-1}\alpha_j - \prod_{k = 0}^{T-1}\alpha_k X_0$ is close to the ODE solution. We have,

and,

To be precise, the approximations in Eqs (5.11) and (5.12) give

where $D_{M_0} = \mathcal{O} \left(\frac{1}{M_0} \right)$. We have

We are now ready to prove Theorem 4.4. In addition to the ODE approximation, we need the following Lemma.

Lemma 5.1 ($x_t$ as a function of $x_0$). The ODE solution obtained by solving Eq (4.1) is an increasing function of the initial configuration $x_0$.

Proof. Note that the solution (4.2) of the ODE (4.1) is of the form

where $a_{1}, b_{1} > 0 \text{ and }~~ c_{1} \geq 0$ $\forall \ A \text{ and }~~ B$. Let $x_{1} < x_{2}$ then

Thus, the ODE solution is an increasing function of the initial configuration $x_0$.

Before we prove Theorem 4.4, note that restriction of a strategy to any subset of $[0, T]$ defines an influencing strategy on that subset. For any strategy $\mathcal{S}$, we denote the strategy on $[T_1, T_2] \subset [0, T]$ given by the substring of $\mathcal{S}$ on $[T_1, T_2]$ by $\mathcal{S} \vert_{[T_1, T_2]}$.

Proof of Theorem 4.4. We first compare $\mathcal{S}_F$ and $\mathcal{S}_L$. For ${ \tilde{p} }+ { \tilde{q} } = (1-\mu)(p+q)$ we get

and

Due to rational influence, $\Delta > 0$. Define $F: [0, 1] \to [0, 1]$ such that

Differentiating with respect to $b$ once and twice we get

Clearly, $F'(b) = 0$ for $b = 1/2$. For the case $\alpha_t = \alpha \text{ or } \alpha_R(1-X_t)$, $A\geq 0$. Thus, $F$ is increasing in $b \in [0, 1/2)$ as $F'(b) > 0$ and $F$ is decreasing in $b \in (1/2, 1]$. Since, $A\geq 0$ we also have for any $b \in [0, 1]$, $F''(1/2) < 0$. Thus, $b = \frac{1}{2}$ is a point of maxima for $F(b)$. Since, $F(0) = F(1) = 0$, we get that $F(b)\geq 0$ for $b \in [0, 1]$. This implies, $D_T \geq 0$. Hence, $\mathcal{S}_L \gg \mathcal{S}_F$ for the case $\alpha_t = \alpha \text{ or } \alpha_R(1-X_t)$.

We now address the case $\alpha_t = \alpha_CX_t$, $A = -\alpha_C$. If $r({ \tilde{p} }+ { \tilde{q} }) > \alpha_C$ the same argument as above works and we get $\mathcal{S}_L > > \mathcal{S}_F$. If $r({ \tilde{p} }+ { \tilde{q} }) < \alpha_C$, we get that $F$ is decreasing in $b \in [0, 1/2)$ and $F$ is increasing in $b \in (1/2, 1]$. It is also easy to check that $F''(1/2) > 0$. Thus, $b = 1/2$ is a point of minima for $F(\cdot)$. Again, using $F(0) = F(1) = 0$, we conclude that $F(b)\leq 0$ for $b \in [0, 1]$ and therefore $D_T \leq 0$. Hence, $\mathcal{S}_L < < \mathcal{S}_F$ for the case $r({ \tilde{p} }+ { \tilde{q} }) < \alpha_C$. Finally, for the case $r({ \tilde{p} }+ { \tilde{q} }) = \alpha_C$, it can be easily verified that $D_T = 0$ and therefore $\mathcal{S}_L = \mathcal{S}_F$.

We now prove the optimality using Lemma 5.1. We give the argument for optimality of $\mathcal{S}_L$ when $\mathcal{S}_L \gg \mathcal{S}_F$. A similar argument works for the rest of the cases. Let $\mathcal{S}$ be an influencing strategy. Scanning from the left (from the first coordinate), let $t_1, t_1+1$ be the first time we encounter a '10' subsequence in $\mathcal{S}$. Since $\mathcal{S}_L \gg \mathcal{S}_F$, $\mathcal{S} \vert_{[0, t_1 + 1]} < < \mathcal{S}^\prime$, where $\mathcal{S}^\prime$ is a strategy on $[0, t_1 + 1]$ with $\mathcal{S}^\prime_i = \mathcal{S}_i$ for all $i \leq t_1-1$ and $\mathcal{S}^\prime_{t_1} = 0, \mathcal{S}^\prime_{t_1+1} = 1$. In other words, a local swap of $10$ to $01$ improves the strategy. This combined with the Lemma 5.1 shows that $\mathcal{S}_L$ is optimal.

6.   Concluding remarks

We consider a population of $M_0$ individuals on a complete graph, each holding an opinion $1$ or $0$ at time $t = 0$. At every time-step a fixed number of individuals are added to the population and a fixed number of uniformly chosen individuals update their opinion. New individuals can have opinion $1$ with probability that may or may not depend on the current state of the system. Similarly, chosen individuals may update their opinion independently of the state of the system or depending on the fraction of individuals of opinion $1$ or $0$ at that time. We observed that the limiting fraction of individuals with opinion $1$ depends crucially on various parameters that can be adjusted in order to obtain a higher fraction of individuals with opinion $1$ in the long run. Further, we demonstrate that the case when the incoming individuals have opinion $1$ with probability proportional to the number of individuals with opinion $1$ in the population, the fluctuations exhibit all three regimes (diffusive, critical and superdiffusive) of scaling, which is not the case otherwise. On the finite horizon version of the problem, we study optimal influencing strategies to obtain maximum expected fraction of people with opinion $1$ at the end of the finite time $T$. Again, a transition in the type of the influencing strategy is observed only in the case when the incoming individuals have opinion $1$ with probability proportional to the number of individuals with opinion $1$ in the population. We also remark that we consider a particular method of influencing the population that works by tweaking the transition probabilities of the underlying Markov chain. Another possible way to influence such a system is to add a certain number of bots or stubborn individuals to the system. Further, while modeling evolution of binary opinion for a growing population is an important direction of extension of the existing body of work, the same methods could be employed to study a similar multi-opinion model. One of the important future directions to explore would be to study the transitions in scaling of fluctuations around the limit as well as the transitions in optimality of the influencing strategies of such growing population models on a fixed or random graphs with nearest-neighbour interaction. It would also be interesting to study the same model without the restrictions of Assumption 1. It is clear from Eq (2.3), that this leads to a non-linear structure in the expression for $E[X_{t+1} \vert \mathcal{F}_t]$, thereby making the problem more challenging. Finally, we remark that similar phase transition for asymptotic behaviour has been observed in reinforced random walks with non-trivial memory effects (for instance, see ^[13,22]). This would be a very interesting aspect to incorporate in this opinion dynamics model as dropping the Markovian update and introducing some memory would bring these models closer to reality.

Acknowledgments

The work of Neeraja Sahasrabudhe was supported by the DST-INSPIRE fellowship and SERB-MATRICS MTR/2019/001072 grant.

Conflict of interest

The authors declare that there is no conflict of interest.