Mathematical Programming for the Dynamics of Opinion Diffusion

Abstract

The focus of this paper is on analyzing the role and the choice of parameters in sociophysics diffusion models by leveraging the potentialities of sociophysics from a mathematical programming perspective. We first present a generalised version of Galam’s opinion diffusion model. For a given selection of the coefficients in our model, this proposal yields the original Galam’s model. The generalised model suggests guidelines for possible alternative selection of its parameters that allow it to foster diffusion. Examples of the parameters selection process as steered by numerical optimisation, taking into account various objectives, are provided.

1. Introduction

Opinion diffusion is a fundamental aspect of human interaction, playing a pivotal role in the spread of innovations, and the emergence of consensus. Understanding how opinions spread and evolve within social networks is crucial for comprehending the emergence of collective behavior, the formation of public opinion, and the polarisation of societies.

Social sciences provide plenty of applications, where the importance of diffusion dynamics is studied and witnessed, such as marketing (see, e.g., [1,2,3]), agent-based modelling (see, e.g., [4]), and sociophysics, where the papers of Serge Galam serve as a guide for researchers (see, e.g., [5]).

Galam’s opinion diffusion model (see [6]) provides a framework for investigating and understanding the dynamics of opinion formation in social systems. Galam’s model sheds light on the mechanisms that drive opinion dynamics. In particular, Galam’s model describes the formation of collective opinion convergence processes using concepts from statistical physics. To analyse them, along with several generalisations of the model, the authors of the current paper have proposed the alternatives in Ref. [7] (showing some drawbacks when applying Galam’s model with a relatively small number of agents), and in Ref. [8] (where a novel subset of agents, namely the opinion leaders, are introduced, to duly represent a possible communication bias). Furthermore, additional literature covering a number of keynote issues can be found in Refs. [5,9,10] and the references therein.

The standard Galam’s model in Ref. [6] assumes that individuals in a group influence and are influenced by their peers. After several iterations within repeated group discussions, each agent may consequently influence the opinion diffusion. Galam’s stylised model simplifies the complexity of opinions by considering a binary state, where individuals can adopt either of two possible opinions, thus allowing a straightforward mathematical analysis of the diffusion process.

We suggest a generalisation of Galam’s model and then offer evidence in an optimisation framework that some of the diffusion parameters can be successfully adjusted in order to steer the diffusion process. Combining Galam’s model with specific Linear Programming (LP) formulations, we take into account both theoretical and numerical results concerning the role of the model’s parameters in order to better control the dynamics of the diffusion. Namely, we aim at maximising the probability that an opinion can spread among agents.

This paper is organised as follows. The essential characteristics of Galam’s model [6] are recapped in Section 2. Then, in Section 3, we present and discuss a generalisation of Galam’s model. The optimisation of the parameters of the new model via linear programming allows one to speed up opinion diffusion at a fixed step of the process: the optimisation problem is discussed in Section 4, while Section 5 provides numerical examples of its resolution. Section 6 discusses a dynamic programming extension of the optimisation problem that optimises the values of the parameters along the whole diffusion process, till convergence. Section 7 contains final remarks and concludes the paper.

2. Recap of Galam’s Model

This section reviews the foundational elements of Galam’s model [6]. Think of a group of N people (agents), each of whom may hold one of two opposing views (let us say, ‘+’ or ‘−’), regarding a specific issue. These agents meet, for several repeated rounds within subgroups of smaller cardinality, to converse and possibly change one anothers’ minds.

Each agent at round (time) t has a probability $a_k$ of being a member of a subgroup of size k, and L is the maximum allowed size of groups. In the original formulation of Galam’s model, the values $a_1,\dots ,a_L$ are exogenous parameters such that

$$\sum _{k=1}^L{a}_k=1,a_k\ge 0,k=1,\dots ,L.$$

Joining a group discussion at time t, any agent may, at the beginning of the subsequent time $t+1$, modify their position (e.g., ‘+’ becomes ‘−’ or vice versa) in accordance with a unique law: the majority rule. Indeed, all agents in a subgroup take the position of the majority in that group in the end of time t. The rule for reversing opinion is slightly biased in favour of the negative opinion ‘−’, since tie breaks are in favour of ‘−’. This may lead to a substantial bias in the case where the subgroup has an even number of members.

Calling $P_{+}\left(t\right)$ the probability that an agent opinion is ‘+’ at time t, the probability of opinion ‘−’ is then $P_{-}\left(t\right)=1-P_{+}\left(t\right)$. The probability $P_{+}(t+1)$ is estimated in Ref. [6] as

$$P_{+}(t+1)=\sum _{k=1}^L{a}_k\sum _{j=⌊\frac{k}{2}+1⌋}^k{C}_j^k{P}_{+}{\left(t\right)}^j{\{1-P_{+}\left(t\right)\}}^{k-j},$$

(1)

where $\lfloor z\rfloor$ is the largest integer less or equal to z, and $C_j^k$ is the binomial coefficient, $\left(\genfrac{}{}{0pt}{}{k}{j}\right)$.

Let $N_{+}\left(t\right)$ ($N_{-}\left(t\right)=N-N_{+}\left(t\right)$) be the number of agents who at time step t have opinion ‘+’ (‘−’). Observe that for small values of N, setting $P_{+}\left(0\right)=N_{+}\left(0\right)/N$, where $N_{+}\left(0\right)$ is the number of agents thinking ‘+’ at time $t=0$, for any $t\ge 1$ the quantity $P_{+}\left(t\right)$ may possibly differ from the ‘actual’ frequency of ‘+’, i.e., $N_{+}\left(t\right)/N$ (see [7]). Nevertheless, the estimated probability $P_{+}(t+1)$ always lies in the interval $[0,1]$ being

$$\sum _{j=⌊\frac{k}{2}+1⌋}^k{C}_j^k{P}_{+}{\left(t\right)}^j{\{1-P_{+}\left(t\right)\}}^{k-j}<\sum _{j=0}^k{C}_j^k{P}_{+}{\left(t\right)}^j{\{1-P_{+}\left(t\right)\}}^{k-j}=1.$$

A relevant role in the model is taken by the value ${\widehat{P}}_{+}$ such that

•      when $P_{+}\left(0\right)>{\widehat{P}}_{+}$ then ${\displaystyle \underset{t\to \infty }{lim}{P}_{+}\left(t\right)=1}$,
•      when $P_{+}\left(0\right)<{\widehat{P}}_{+}$ then ${\displaystyle \underset{t\to \infty }{lim}{P}_{+}\left(t\right)=0}$,
•      when $P_{+}\left(0\right)={\widehat{P}}_{+}$ then $P_{+}\left(t\right)=P_{+}\left(0\right),$∀$t>0$.

${\widehat{P}}_{+}$ constitutes the threshold value such that when $N_{+}\left(0\right)/N$ is greater than ${\widehat{P}}_{+}$, then all agents will eventually have opinion ‘+’. Conversely, when $t\to \infty$ all the agents will definitely think ‘−’ if $N_{+}\left(0\right)/N<{\widehat{P}}_{+}$. The value ${\widehat{P}}_{+}$ is the fixed point of Equation (1) and is called the killing point or tipping point of the model. In Figure 1, one can observe the dynamics described by relation (1), when the largest cardinality L of the subgroups takes integer values in the interval $[3,20]$ and $a_k=1/L$, for any k: for each of the 18 curves, the killing point is identified by the intersection with the bisector line other than the extreme points $(0,0)$ and $(1,1)$. Observe that for small values of L no killing point appears (or equivalently, it coincides with the extreme point $(1,1)$). Figure 2 shows a zoomed in perspective of Figure 1.

3. Capturing Additional Dynamics Using a Generalised Galam’s Model

According to model (1), a strict majority of members with positive opinion is a necessary and sufficient condition to have opinion ‘+’ for all the subgroup members.

Since the ultimate choice in a group is frequently the product of a discussion, rather than a simple tally of the two opposing viewpoints in the group, a rule that is so rigorous yet so straightforward could not correctly reflect the actual opinion dynamics in practice. As an illustration, think about the propagation of political opinions. The probability that everyone in the group would share the same view (e.g., +) at the close of a conversation may rise smoothly with the number of members who had that opinion prior to the meeting. As a second application, the reader may consider the audience of social networks, where the dynamics of information spreading was widely investigated in the dedicated literature (see, e.g., [11]).

Accordingly, we suggest to generalise Galam’s model (1) taking into account a softer dynamics of opinion change, i.e., without using rigid majority as a necessary and sufficient condition to shift the entire group to the same view. In particular, we assume that after the conversations, all agents in a group will have opinion ‘+’ with a probability ${\alpha }_j^k$ that is dependent on the size k of the group and the number j of agents that had opinion ‘+’ before the discussion. We use the following definition to model the relationship between the probabilities of having an opinion ‘+’ before (i.e., $P_{+}\left(t\right)$) and after (i.e., $P_{+}(t+1)$) discussion (see [12] for a preliminary version of the model):

$$P_{+}(t+1)=\sum _{k=1}^L{a}_k\sum _{j=0}^k{\alpha }_j^k{C}_j^k{P}_{+}{\left(t\right)}^j{\{1-P_{+}\left(t\right)\}}^{k-j}.$$

(2)

Model (2) generalises model (1), since it is possible to select indeed the probabilities $\left\{{\alpha }_j^k\right\}$ that exactly replicate model (1) (see also Figure 3):

$${\alpha }_j^k=\left\{\begin{array}{c}{\displaystyle 0\mathrm{if}j<⌊\frac{k}{2}+1⌋,}\hfill \\ \hfill \\ {\displaystyle 1\mathrm{if}j\ge ⌊\frac{k}{2}+1⌋.}\hfill \end{array}\right.$$

(3)

As mentioned, probabilities $\left\{{\alpha }_j^k\right\}$ should reasonably increase with the number j of ‘+’ in a subgroup, and decrease with respect to the size of the group k. In this regard, it is reasonable to expect for the probability ${\alpha }_j^k$ to become negligible when the number j of ‘+’ in a subgroup is relatively small (i.e., much lower than the strict majority), and to become close to 1 as the number of ‘+’ noticeably increases (i.e., higher than strict majority). In general, the probability that all agents in the subgroup will adopt the opinion ‘+’ is conceivably a function rising from zero to one as j increases. If one assumes that this function of j is linear, one may precisely define the probabilities ${\alpha }_j^k$ as (see Figure 4)

$${\alpha }_j^k=\left\{\begin{array}{c}{\displaystyle 0,\mathrm{if}j<⌊\frac{k}{2}+1⌋+z_j^k-h,}\hfill \\ \hfill \\ {\displaystyle \frac{1}{2}+\frac{\left[j-\left(⌊\frac{k}{2}+1⌋+z_j^k\right)\right]}{2h},\mathrm{if}⌊\frac{k}{2}+1⌋+z_j^k-h\le j<⌊\frac{k}{2}+1⌋+z_j^k+h,}\hfill \\ {\displaystyle 1,\mathrm{if}j\ge ⌊\frac{k}{2}+1⌋+z_j^k+h.}\hfill \end{array}\right.$$

(4)

When $z_j^k=h=0$, the probabilities defined in Equation (4) are exactly the same as in Equation (3). The value of $z_j^k$ in (4) represents a shift (either positive or negative) from the value $\lfloor k/2+1\rfloor$, while the slope of the ramp in Figure 4 is $1/\left(2h\right)$.

To better grasp the geometric insight behind the choice of the parameters in (4), let us consider the simple numerical example reported in Ref. [6], where $L=4$, $a_1=0$, and $a_2=a_3=a_4=1/3$ (and $h=z_j^k=0$ for all j and k). As reported in Ref. [6], the killing point ($KP$) lies in between $0.84$ and $0.87$ (see Figure 5). Then, in Figure 6, there is also the model (2) with the choice (4), after setting $h=z_j^k=0.5$ for any j and k. One can immediately infer that the dynamics of Galam’s model [6] is definitely spoiled when the choice for the coefficients $\left\{{\alpha }_j^k\right\}$ in Equation (3) is replaced by Equation (4). Equivalently, even in case $P_{+}\left(t\right)=1$ (complete consensus among agents to think +) then the choice (4) imposes a regression towards the stable point given by the origin.

Hence, the presence of a killing point for Galam’s model seems to be strictly related to the expression (1), and introducing the coefficients $\left\{{\alpha }_j^k\right\}$ definitely also spoils the killing point. Moreover, one observes that, in case the majority rule is not explicitly applied in Equation (1), then the dynamics of the model is strongly altered.

Nevertheless, the model (2) retains a number of properties and can suggest fruitful results, following both of the next guidelines:

• it provides clues on the perspective for studying the process of diffusion of information;
• it may suggest proper ways to control information spreading among agents.

At least a couple of intriguing issues in applications can steer the choice of the coefficients $\left\{{\alpha }_j^k\right\}$, ranging from small–medium- to large-scale (number of agents) applications:

• One Period Analysis. One may assess values for $\left\{{\alpha }_j^k\right\}$ so that, considering at time t the probability $P_{+}\left(t\right)$, one miximizes the probability $P_{+}(t+1)$ at time $t+1$. In this regard, the values $\left\{{\alpha }_j^k\right\}$ represent costs for steering the information among agents and fostering the positive opinion: the larger $\left\{{\alpha }_j^k\right\}$ (i.e., higher costs) the larger the probability to convey a group to opinion ‘+’. Certainly, the combination of the proper values for each of the coefficients $\left\{{\alpha }_j^k\right\}$ is strongly related to the value $P_{+}\left(t\right)$, the probabilities $\left\{a_k\right\}$, and the binomial coefficients $C_j^k$;
• Multi-Period Analysis. Similarly to the previous item, one may decide to select $\left\{{\alpha }_j^k\right\}$ such that, considering again at time t the probability $P_{+}\left(t\right)$, one miximizes the probability $P_{+}\left(T\right)$ at time $T>t$, and compute the entire sequence $P_{+}(t+1),P_{+}(t+2),\dots ,P_{+}\left(T\right)$ of intermediate probabilities.

The last two scenarios can be declined in a variety of contexts, including production and marketing, where consumers play the role of agents and the aforementioned perspectives may be the answer to the question: what is (if any) the necessary extra effort in terms of advertising campaign, in order to promote a certain spread of the products or customers’ expectations on items? In this regard, the quantities $\left\{{\alpha }_j^k\right\}$ summarise the resulting effort, while from a mathematical programming perspective they represent unknowns to be assessed. This also suggests that a number of additional questions may arise adopting the model (2), mapping relevant practical instances where a tentative forecast is sought in order to plan the use of (possibly scarce) resources to control the process of diffusion of the information. For the sake of brevity, we itemise below some proposals that are representative but not exhaustive:

• Feasibility Problem. Given the value of $P_{+}\left(t\right)$ and the target value $\overline{P}$, one may determine a set of values for the coefficients $\left\{{\alpha }_j^k\right\}$ such that, starting at t from $P_{+}\left(t\right)$, at time $T>t$, $P_{+}\left(T\right)\ge \overline{P}$;
• Focus Group Problem. Given the value of $P_{+}\left(t\right)$ and the target value $\overline{P}$ and the time $T>t$, one may be interested to determine a set of values for the coefficients $\left\{{\alpha }_j^k\right\}$ such that ${\alpha }_m^{\left(k\right)}\le {\alpha }_j^k\le {\alpha }_M^{\left(k\right)}$, where ${\alpha }_m,{\alpha }_M$ are possible bounds, and $P_{+}\left(T\right)\ge \overline{P}$. This scenario models a specific interest on those subgroups of cardinality k.

4. Single Period Maximisation of Diffusion

As from the analysis in Section 3, one of the possible proposals to couple the dynamics described through the model (2) with a single period optimisation framework, is given by the following LP scheme:

$$\underset{\alpha }{max} \sum _{k=1}^L{a}_k\sum _{j=0}^k{\alpha }_j^k{C}_j^k{P}_{+}{\left(t\right)}^j{\{1-P_{+}\left(t\right)\}}^{k-j},$$

(5)

$${\alpha }_j^k\le {\alpha }_{j+1}^{k}j=0,1,\dots ,k-1;k=1,\dots ,L,$$

(6)

$${\alpha }_j^k\ge {\alpha }_j^{k+1}j=0,1,\dots ,k;k=1,\dots ,L-1,$$

(7)

$$\sum _{k=1}^L\sum _{j=0}^k{\alpha }_j^k\le b\left(t\right),$$

(8)

$$0\le {\alpha }_j^k\le 1j=0,1,\dots ,k;k=1,\dots ,L.$$

(9)

The last optimisation problem assumes that the value $P_{+}\left(t\right)$ is given, so that both the objective function and the constraints are linear in the set $\left\{{\alpha }_j^k\right\}$. Though the meaning associated with the objective function is relatively clear, for the constraints some clarifications seem necessary:

• the constraints in Equation (6) state that for a given dimension k of a subset, larger values of the number of agents thinking ‘+’ imply a larger probability ${\alpha }_j^k$;
• similarly, in the constraints in Equation (7), when the number of agents thinking ‘+’ remains constant, the larger the set cardinality (i.e., k), the smaller the probability ${\alpha }_j^k$;
• the constraint in Equation (8) expresses the overall cost (i.e., it is a budget constraint) allowed to assess the probabilities $\left\{{\alpha }_j^k\right\}$, at time t;
• since the quantities $\left\{{\alpha }_j^k\right\}$ need to represent probabilities, they are required to fulfill also the constraint (9).

In order to avoid either infeasible or straightforward solutions for the optimisation Problems (5)–(9), the following lemmas gives some indications on the choice of the parameter $b\left(t\right)$, for any t (for a proof, see [12]).

Lemma 1.

Let one be given the linear Programs (5)–(9) with the choice ($1\le k\le L$ and $0\le j\le k$)

$${\alpha }_j^k=\left\{\begin{array}{ccc}0,\hfill & & foranyj<⌊\frac{k}{2}+1⌋,\hfill \\ & & \\ 1,\hfill & & foranyj\ge ⌊\frac{k}{2}+1⌋.\hfill \end{array}\right.$$

(10)

Then, relations (10) satisfy the constraints (6), (7) and (9). Moreover, if Equation (10) also satisfies Equation (8), then the value of the objective function in Equation (5) coincides with $P_{+}(t+1)$ in Equation (1).

Note that Lemma 1 gives a straightforward idea of the fact that the solution of the linear Programs (5)–(9) is substantially nothing else but a generalisation of Equation (1). Furthermore, the next result will give a precise indication on the possible values for the budget $b\left(t\right)$ in Equation (8).

Lemma 2.

Let one be given the optimisation problems (5)–(9) and let $\left\{{\alpha }_j^k\right\}$ be assigned as in Equation (10), for any $1\le k\le L$ and $0\le j\le k$. Then,

$$\sum _{k=1}^L\sum _{j=0}^k{\alpha }_j^k=\left\{\begin{array}{ccc}{\displaystyle {\left(\frac{L}{2}\right)}^2+\frac{L}{2},}\hfill & & whenLiseven,\hfill \\ \hfill & & \\ {\displaystyle {\left(\frac{L-1}{2}\right)}^2+L,}\hfill & & whenLisodd.\hfill \end{array}\right.$$

(11)

Note that the right sides of Equation (11) explicitly give some hints for the selection of the parameter $b\left(t\right)$ in Equation (8), both whether in case L it is even or it is odd.

Regarding some technicalities associated with the solution of the optimisation problems (5)–(9), one observes that it is a continuously differentiable problem, where all the functions are linear. Hence, it is a convex problem, so that the set of all its solutions (possibly an empty set or a singleton) is a convex set. This implies that for any given pair of its solutions, all the points in the segment joining them will be solutions, too. Moreover, being a linear program, all its (possible) solutions will lie on vertices of the feasible set, and not in the interior of the feasible set. As is known, this makes its solution relatively simple (throughout any solver based on the simplex method) and achievable in polynomial time. Hence, large-scale instances are well tractable and allow for a scalable solution in a number of applications with a great number of agents (e.g., problems involving social media or large social groups).

We complete this section highlighting that one further generalisation of the linear programs (5)–(9) suggests to disaggregate the budget constraint and to replace the inequality (8) by the set of constraints,

$$\sum _{j=0}^k{\alpha }_j^k\le b_k\left(t\right),k=1,\dots ,L.$$

Observe that the value $b_k\left(t\right)$, for any k, represents a budget devoted to possibly affect the solution after working uniquely on the subsets of cardinality k. This increases the flexibility of the model without compromising its overall complexity (being the resulting model yet a linear program).

5. Preliminary Numerical Experience

This Section is devoted to provide a numerical experience where the potentialities of the formulations (5)–(9) are exploited. In this regard, the investigation here is limited to a couple of meaningful instances. The first one is a small-scale (number of unknowns) problem, while the second one attempts to scale the first’s by 100.

5.1. Small-Scale Instance

Regarding the value of the coefficients in (5)–(9), we consider for the small-scale instance the following setting:

$$\left\{\begin{array}{c}L=10,\hfill \\ \left\{a_k\right\}=\{0.1,0,0.15,0,0.3,0,0.3,0,0.15,0\},\hfill \\ P_{+}\left(t\right)=0.65.\hfill \end{array}\right.$$

The above choice corresponds to possibly allow only subgroups of dimensions 1, 3, 5, 7, and 9, with probabilities that include null values and possibly repeated values. Furthermore, we set the initial percentage of the population thinking ‘+’ to $P_{+}\left(t\right)=65\%$. Finally, in order to avoid an empty feasible set in Equations (5)–(9) we also selected, respectively, the values $b\left(t\right)=5$ and $b\left(t\right)=10$, based on Lemma 2. The outcomes of our numerical experience are obtained using the solver CPLEX 20.1.0.0 available on the NEOS Server platform [13]. Let us remark that CPLEX is definitely among the best and faster solvers for LP, along with the alternative solver BARON. Our numerical experience on the above two instances is summarised as follows:

• $b\left(t\right)=5$: the problems (5)–(9) is coded using AMPL (A Mathematical Programming Language; see [14,15]). The presolve tool in CPLEX eliminated 65 constraints from the formulation, so that the simplified problem was reduced to 65 variables and 110 linear inequality constraints. Regarding the final solution, CPLEX performed 13 dual simplex iterations (i.e., iterations of a method for LP which represents the counterpart of the simplex method, after exploiting the duality theory), with an overall time for the solution not larger than a couple of seconds. Finally, the value of $P_{+}(t+1)$ found by the solver is

  $$P_{+}(t+1)=0.245428625$$

  with the set of variables ${\left({\alpha }_j^k\right)}^{\ast }$ given by

  	k = 1	k = 2	k = 3	k = 4	k = 5	k = 6	k = 7	k = 8	k = 9	k = 10
  j = 0	0	0	0	0	0	0	0	0	0	0
  j = 1	1	0	0	0	0	0	0	0	0	0
  j = 2	.	0	0	0	0	0	0	0	0	0
  j = 3	.	.	2/3	2/3	2/3	0	0	0	0	0
  j = 4	.	.	.	2/3	2/3	0	0	0	0	0
  j = 5	.	.	.	.	2/3	0	0	0	0	0
  j = 6	.	.	.	.	.	0	0	0	0	0
  j = 7	.	.	.	.	.	.	0	0	0	0
  j = 8	.	.	.	.	.	.	.	0	0	0
  j = 9	.	.	.	.	.	.	.	.	0	0
  j = 10	.	.	.	.	.	.	.	.	.	0

• $b\left(t\right)=10$: again the problem (5)–(9) is coded using AMPL and the presolve tool in CPLEX eliminated 65 constraints from the formulation, so that again the simplified problem was reduced to 65 variables and 110 linear inequality constraints. CPLEX performed 18 dual simplex iterations with an overall time for computation similar to the case where it is $b\left(t\right)=5$. Finally, the value of $P_{+}(t+1)$ found by the solver is

  $$P_{+}(t+1)=0.4392275888$$

  with the set of variables ${\left({\alpha }_j^k\right)}^{\ast }$ given by the matrix,

  	k = 1	k = 2	k = 3	k = 4	k = 5	k = 6	k = 7	k = 8	k = 9	k = 10
  j = 0	1	0	0	0	0	0	0	0	0	0
  j = 1	1	0	0	0	0	0	0	0	0	0
  j = 2	.	0	0	0	0	0	0	0	0	0
  j = 3	.	.	1	1	1	0	0	0	0	0
  j = 4	.	.	.	1	1	0.285714	0.285714	0	0	0
  j = 5	.	.	.	.	1	0.285714	0.285714	0	0	0
  j = 6	.	.	.	.	.	0.285714	0.285714	0	0	0
  j = 7	.	.	.	.	.	.	0.285714	0	0	0
  j = 8	.	.	.	.	.	.	.	0	0	0
  j = 9	.	.	.	.	.	.	.	.	0	0
  j = 10	.	.	.	.	.	.	.	.	.	0

  Note that while allowing a larger value of the budget (for example, $b\left(t\right)=10$), the solver is able to select a larger number of nonzero unknowns, so that the final value of $P_{+}(t+1)$ is almost doubled with respect to the case $b\left(t\right)=5$. In actual applications, this implies that, in order to obtain almost twice the effect of the previous case, on this instance twice the value of the budget must be allowed.

5.2. Large-Scale Instance

Here, we focus on the same instance of Section 5.1, where conversely, a larger number of unknowns is considered. The novel setting of the parameters for the solver are given as follows:

$$\left\{\begin{array}{c}L=1000\hfill \\ a_k=1/L,k=1,\dots ,L,\hfill \\ P_{+}\left(t\right)=0.65.\hfill \end{array}\right.$$

The above choice corresponds to possibly allow all the subgroups with the same probability, and again the initial percentage of the population thinking ‘+’ is equal to $P_{+}\left(t\right)=65\%$. Similarly to the small-scale instance, we consider two values for the budget, $b\left(t\right)=50$ and $b\left(t\right)=100$. The computation is again performed adopting the solver CPLEX 20.1.0.0 on the NEOS Server [13]. The outcomes of the resulting two instances are summarised as follows:

• $b\left(t\right)=50$: the problems (5)–(9) is coded using AMPL and the presolve tool in CPLEX eliminated 501,500 constraints from the formulation. The overall simplified problem contained 501,500 variables and 1,001,000 linear inequality constraints. CPLEX performed 192 dual simplex iterations with a time of computation smaller than 20 s, showing that the linear model can well scale the time of computation. The final value of $P_{+}(t+1)$ found by the solver is

  $$P_{+}(t+1)=0.01061571566$$

  with the set of variables ${\left({\alpha }_j^k\right)}^{\ast }$ given by

  	k = 1	k = 2	k = 3	k = 4	k = 5	k = 6	k = 7	k = 8	k = 9	k = 10	k = 11	k = 12	k ≥ 13
  j = 0	1	0	0	0	0	0	0	0	0	0	0	0	0
  j = 1	1	1	1	0	0	0	0	0	0	0	0	0	0
  j = 2	.	1	1	1	1	0	0	0	0	0	0	0	0
  j = 3	.	.	1	1	1	1	1	0	0	0	0	0	0
  j = 4	.	.	.	1	1	1	1	1	0	0	0	0	0
  j = 5	.	.	.	.	1	1	1	1	1	1	0	0	0
  j = 6	.	.	.	.	.	1	1	1	1	1	1	0	0
  j = 7	.	.	.	.	.	.	1	1	1	1	1	0.8333	0
  j = 8	.	.	.	.	.	.	.	1	1	1	1	0.8333	0
  j = 9	.	.	.	.	.	.	.	.	1	1	1	0.8333	0
  j = 10	.	.	.	.	.	.	.	.	.	1	1	0.8333	0
  j = 11	.	.	.	.	.	.	.	.	.	.	1	0.8333	0
  j = 12	.	.	.	.	.	.	.	.	.	.	.	0.8333	0
  j = 13	.	.	.	.	.	.	.	.	.	.	.	.	0
  j = 14	.	.	.	.	.	.	.	.	.	.	.	.	0
  j > 14	.	.	.	.	.	.	.	.	.	.	.	.	0

• $b\left(t\right)=200$: the outcomes are quite similar to the case where $b\left(t\right)=50$, with 501,500 indicating the overall number of variables and 1,001,000 the linear inequality constraints. CPLEX performed 30,854 simplex iterations with a time of computation smaller than 20 s, showing again that the linear model can well scale the time of computation. The final value of $P_{+}(t+1)$ found by the solver was now

  $$P_{+}(t+1)=0.0242061448$$

  and we do not report the value of the unknowns for the sake of simplicity.

Observe that in both the last two examples, given that subgroups are allowed to be quite large, despite relatively high budget values, the levels reached by the probabilities $P_{+}(t+1)$ are quite low.

As a general achievement, we can immediately describe the pattern of the nonzero unknowns which was respected in all four numerical tests reported above. In particular, we can prove that the solution of the formulations (5)–(9) only fills the principal submatrix of unknowns of order $h\times h$, depending h on the value of the budget parameter along with the number of possible subgroups L. Finally, this also allows one to straightforwardly assess a number of null unknowns and possibly reduce the complexity of the overall formulation.

6. A Multi-Period Model

This Section considers a multi-period reformulation of the LP (5)–(9), in order to further generalise the model (2). In particular, in place of the single-period model (5)–(9), where at time step t the quantity $P_{+}(t+1)$ is maximised starting from $P_{+}\left(t\right)$, we can consider a multi-period approach with the ultimate goal of maximising $P_{+}(T+1)$, where T is the time horizon. The latter approach is summarised in the following Nonlinear Program (NLP):

$$\underset{\alpha }{max} P_{+}(T+1),$$

(12)

$$P_{+}(t+1)=\sum _{k=1}^L{a}_k\sum _{j=0}^k{\alpha }_j^k\left(t\right)C_j^k{P}_{+}{\left(t\right)}^j{(1-P_{+}\left(t\right))}^{k-j},t=1,\dots ,T,$$

(13)

$${\alpha }_j^k\left(t\right)\le {\alpha }_{j+1}^k\left(t\right)t=1,\dots ,T;j=0,1,\dots ,k-1;k=1,\dots ,L,$$

(14)

$${\alpha }_j^k\left(t\right)\ge {\alpha }_j^{k+1}\left(t\right)t=1,\dots ,T;j=0,1,\dots ,k;k=1,\dots ,L-1,$$

(15)

$$\sum _{k=1}^L{\alpha }_j^k\left(t\right)\le b_j\left(t\right)t=1,\dots ,T;j=0,1,\dots ,k,$$

(16)

$$0\le {\alpha }_j^k\left(t\right)\le 1t=1,\dots ,T;j=0,1,\dots ,k;k=1,\dots ,L.$$

(17)

The above NLP includes the unknowns

$${\alpha }_j^k\left(t\right),t=1,\dots ,T;j=0,1,\dots ,k;k=1,\dots ,L,$$

which represent a larger number of variables with respect to Equations (5)–(9). This implies that the larger the time horizon T, the larger the number of unknowns of the resulting problem formulation. Moreover, as already remarked, Equations (12)–(17) represents an NLP, which in general increases the difficulty of its solution. In particular, the nonlinearities in Equation (13) might yield a nonconcave overall maximisation problem, which implies that a certain number of local maxima (which are not global) might arise. In addition, unlike Equations (5)–(9), the feasible set of Equations (12)–(17) is no longer a polyhedron, so that the final solutions are not necessarily located on the boundary of the feasible set. As a consequence, the choice of the starting value $P_{+}\left(1\right)$ in Equation (13) becomes a key factor for at least a couple of reasons:

• the sequence $\left\{P_{+}\left(t\right)\right\}$ strongly depends on $P_{+}\left(1\right)$, in a similar fashion of the single-period formulation (5)–(9);
• the choice of $\left\{P_{+}\left(t\right)\right\}$ strongly affects the local maximum provided by the solver adopted for Equations (12)–(17).

Regarding the constraints in Equation (13), observe that the constraints just state a recursion for the function in Equation (2), at each time step. Moreover, the constraints in Equations (14), (15), and (17) have a similar meaning of the constraints in Equations (6), (7), and (9), for the single-period formulation. Finally, the budget constraints in Equation (16) have a possible double formulation, due to the multi-period scheme.

Proposition 1.

Let the sequence $\left\{{\alpha }_j^k\left(t\right)\right\}$ be a global solution of Equations (5)–(9), for any $t=1,\dots ,T$. Then, ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{t=1,\dots ,T}$ is a global solution of Equations (12)–(17).

Proof. 

Observe that from relation (2), one has the following equalities:

$$\begin{array}{ccc}& & P_{+}(t+1)-P_{+}\left(t\right)=\hfill \\ & & {\displaystyle \sum _{t=2}^{T+1}}\left[{\displaystyle \sum _{k=1}^L}{a}_k{\displaystyle \sum _{j=0}^k}{\alpha }_j^k\left(t\right)C_j^k{P}_{+}{\left(t\right)}^j{(1-P_{+}\left(t\right))}^{k-j}-{\displaystyle \sum _{k=1}^L}{a}_k{\displaystyle \sum _{j=0}^k}{\alpha }_j^k(t-1)C_j^k{P}_{+}{(t-1)}^j{(1-P_{+}(t-1))}^{k-j}\right]=\hfill \\ & & {\displaystyle \sum _{t=2}^{T+1}}\Delta P_{+}\left(t\right).\hfill \end{array}$$

Thus, considering that $P_{+}\left(1\right)\in \Re$ is a constant value, the maximisation in Equation (12) is equivalent to the maximisation,

$$max\sum _{t=2}^{T+1}\Delta P_{+}\left(t\right).$$

(18)

Moreover, observe that if $P_{+}\left(t\right)$ is given, $\Delta P_{+}(t+1)$ depends only on the unknowns,

$${\alpha }_j^k\left(t\right),j=0,\dots ,k;k=1,\dots ,L,$$

and the maximisation in Equation (5) is equivalent to

$$\underset{\alpha }{max}\Delta P_{+}(t+1).$$

Now, suppose the sequence ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{j=0,\dots ,k;k=1,\dots ,L}$ is a solution of Equations (5)–(9); then, it also satisfies Equation (13) for t, as well as Equation (14)–(17). Thus, if the sequences,

$${\left\{{\alpha }_j^k\left(t\right)\right\}}_{j=0,\dots ,k;k=1,\dots ,L}t=1,\dots ,T$$

(19)

solve the problem (5)–(9), for $t=1,\dots ,T$, then by Equation (18), the values in Equation (19) are a feasible point of Equations (12)–(17), satisfying also Equation (18), i.e., Equation (19) is a solution of Equations (12)–(17).  □

Lemma 3.

Let $\left\{{\alpha }_j^k\left(t\right)\right\}$ be a global solution of Equations (5)–(9), for any $t\in \{1,2,\dots ,T\}$, where the inequality (8) is replaced by the nonlinear inequality,

$${\varphi }_t\left[\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le b_j\left(t\right),{\varphi }_t:{\Re }^{\frac{(L+1)(L+2)}{2}-1}\to \Re .$$

Then, ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{t=1,\dots ,T}$ is also a global solution of Equations (12)–(17), with Equation (16) replaced by

$${\varphi }_t\left[\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le b_j\left(t\right),t=1,\dots ,T;j=0,\dots ,k.$$

(20)

Proof. 

The proof trivially follows the guidelines of the proof for Proposition 1. □

Lemma 4.

Let $\left\{{\alpha }_j^k\left(t\right)\right\}$ be a global solution of Equations (5)–(9), for any $t\in \{1,2,\dots ,T\}$, where the inequality (8) is replaced by the nonlinear inequality,

$$\Phi \left[\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le b_j\left(t\right),\Phi :{\Re }^{\frac{(L+1)(L+2)}{2}-1}\to \Re ,$$

and Φ is any convex function. Then, ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{t=1,\dots ,T}$ is also a feasible solution of Equations (12)–(17), with Equation (16) replaced by

$$\Phi \left[\sum _{t=1}^T{\lambda }_t\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le b_j\left(t\right),j=0,\dots ,k;0\le {\lambda }_t\le 1;\sum _{t=1}^T{\lambda }_t=1,$$

(21)

being $b_j\ge {\sum }_{t=1}^T{\lambda }_t{b}_j\left(t\right)$.

Proof. 

The convexity of $\Phi$ and the hypotheses imply

$$\Phi \left[\sum _{t=1}^T{\lambda }_t\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le \sum _{t=1}^T{\lambda }_t\Phi \left[\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le \sum _{t=1}^T{\lambda }_t{b}_j\left(t\right)\le b_j,$$

so that ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{t=1,\dots ,T}$ also satisfy Equation (21). The rest of the proof follows the guidelines of the proof for Proposition 1. □

Remark 1.

Note that from Lemma 4, if the sequences $\left\{{\alpha }_j^k\left(t\right)\right\}$, $t=1,\dots ,T$, are global solutions of Equations (5)–(9) for $t=1,\dots ,T$, then the sequence ${\left\{{\alpha }_j^k\left(t\right)\right\}}_{t=1,\dots ,T}$ is a feasible solution but possibly not a global solution of Equations (12)–(17), with Equation (16) replaced by

$$\Phi \left[\sum _{t=1}^T{\lambda }_t\sum _{k=1}^L{\alpha }_j^k\left(t\right)\right]\le b_j\left(t\right),j=0,\dots ,k;0\le {\lambda }_t\le 1;\sum _{t=1}^T{\lambda }_t=1,$$

and $b_j\ge {\sum }_{t=1}^T{\lambda }_t{b}_j\left(t\right)$.

A Numerical Example

We provide here a preliminary numerical example, where the solution of the formulation (12)–(17) is considered, and the budget constraints (16) are replaced by the unique one (which aggregates possible different budgets at the epoches $1,\dots ,T$):

$$\sum _{k=1}^L\sum _{j=0}^k\sum _{t=1}^T{\alpha }_j^k\left(t\right)\le \mathrm{budget}.$$

Since the multi-period formulation is indeed nonlinear and possibly nonconvex, we preferred to preliminarily investigate its solutions through a renowned nonlinear (NLP) solver from the literature. In particular, we adopted Knitro 13.2.0 from the NEOS Server [13]. Nevertheless, we are aware that since the problem might be nonconvex (unless the last property is explicitly proved to hold for Equations (12)–(17)), the choice of the starting point by the NLP solver may be crucial, to both outreach an accurate final solution and to reduce the overall computational burden. The parameters of the two instances considered are summarised as follows (respectively):

$$\left\{\begin{array}{c}L=10\hfill \\ a_k=1/L,k=1,\dots ,L,\hfill \\ P_{+}\left(t\right)=0.65,\hfill \\ T=6,\hfill \\ \mathrm{budget}=20,\hfill \end{array}\right.$$

and

$$\left\{\begin{array}{c}L=10,\hfill \\ a_k=1/L,k=1,\dots ,L,\hfill \\ P_{+}\left(t\right)=0.65,\hfill \\ T=6,\hfill \\ \mathrm{budget}=100.\hfill \end{array}\right.$$

In what follows, we briefly show that, due to the smaller budget (i.e., $20<100$) in the first scenario, it yields worse results (i.e., a smaller value of $P_{+}\left(T\right)$) with respect to the second scenario. Indeed, adopting the first set of parameters for our multi-period formulation, Knitro presolver was able to eliminate 403 constraints and 1 variable, so that the final formulation included 395 variables and 660 constraints. Moreover, for the probabilities $\left\{P_{+}\left(t\right)\right\}$, we obtain the following nonmonotone sequence (due to the nonlinearity of the multi-period model)

$$\begin{array}{ccc}{P}_{+}\left(1\right)\hfill & =& 0.65,\hfill \\ P_{+}\left(2\right)\hfill & =& 9.21406\times {10}^{-5},\hfill \\ P_{+}\left(3\right)\hfill & =& 1.51607\times {10}^{-5},\hfill \\ P_{+}\left(4\right)\hfill & =& 2.37203\times {10}^{-5},\hfill \\ P_{+}\left(5\right)\hfill & =& 2.06585\times {10}^{-5},\hfill \\ P_{+}\left(6\right)\hfill & =& 0.499547.\hfill \end{array}$$

Conversely, adopting the second set of parameters for our multi-period formulation, Knitro presolver was again able to eliminate 403 constraints and 1 variable, yielding for the probabilities the values

$$\begin{array}{ccc}{P}_{+}\left(1\right)\hfill & =& 0.65,\hfill \\ P_{+}\left(2\right)\hfill & =& 0.140855,\hfill \\ P_{+}\left(3\right)\hfill & =& 0.0613564,\hfill \\ P_{+}\left(4\right)\hfill & =& 0.0521609,\hfill \\ P_{+}\left(5\right)\hfill & =& 0.0573217,\hfill \\ P_{+}\left(6\right)\hfill & =& 1.\hfill \end{array}$$

Again, one observes a nonmonotone behaviour for the sequence $\left\{P_{+}\left(t\right)\right\}$, due to nonlinearities of the multi-period model. For the sake of completeness let us remark that the solution of the last two nonlinear instances by Knitro required no more than 10 s each.

7. Conclusions

In this paper, we studied the problem of possibly enhancing standard dynamics from sociophysics (namely the model (1)), using a mathematical programming perspective. We were interested about following a couple of lines of research. First, we coupled the model (1) with an LP scheme in order to possibly control the probability $P_{+}(t+1)$ for a given probability $P_{+}\left(t\right)$, after leveraging the unknowns ${\alpha }_j^k$ in Equation (2). The final value of these variables gives a measure of the effort which is required to steer the diffusion process of the opinion ‘+’ for the subgroups of cardinality k. The dynamics are strongly based on the idea of possibly maximising $P_{+}(t+1)$. A numerical experience is also reported in this regard, showing that the computational effort for solving LPs associated with this first proposal is definitely modest, even in the case where the solution of large instances is sought.

As a second task, we also extended the (one period) LP formulations to a more general multi-period formulation, and in this case it was necessary to compute the sequence $\{P_{+}(t+1),P_{+}(t+2),\dots ,P_{+}\left(T\right)\}$ for a given value of $P_{+}\left(t\right)$ and for a given time horizon, T. Some theoretical properties showing a connection between the solutions of both our proposals have been given, though much work yet is required, including a broad numerical experience also in the multi-period case.