An application of Linear Programming to Sociophysics Models Andrea Elleroa , Giovanni Fasanoa and Daniela Favarettoa a University Ca’ Foscari of Venice, Department of Management, Venice, Italy Abstract In this paper we consider a renowned stochastic model from sociophysics reported in [1, 2], which describes the diffusion of information by word-of-mouth processes. This general model has a terrific impact to capture both social dynamics among agents and information percolation, in case interaction among individuals plays a keynote role. Here we generalize this model, by means of Linear Programming (LP) formulations, which exploit to some extent the potentialities of sociophysics from a mathematical programming perspective. Our overall approach aims to formally combine a stochastic model with a Linear Programming framework. Keywords Stochastic models, Agents’ interaction, Galam’s model, Linear Programming, Marketing 1. Introduction Social sciences provide plenty of applications, where the importance of diffusion dynamics is studied in a number of papers and books, covering marketing (see e.g. [3, 4, 5]), agent-based modeling (see e.g. [6]) and sociophysics (see e.g. [2, 7]). Dating back to the seminal paper [8], in a social network people might tend to influence other persons in their neighborhood, so enhancing diffusion processes. As a matter of fact, in a consumers market the interaction among individuals may fruitfully affect the spreading of information, along with the adoption of new products exploiting different communication channels [9]. Hence, assessing accurate models of such diffusion processes may have a considerable impact on practical applications. In this regard, the correct setting of models parameters becomes crucial. The diffusion process we consider in this paper relies on a stochastic model, which was first pro- posed by Galam in [1]. In this model each member (agent) of a given population can have one of two opposite opinions, and may change opinion after discussing with other individuals in the population. As a consequence, each agent may affect the opinion diffusion after a number of repeated discussions in groups. We consider both theoretical and numerical results, when pairing Galam’s model with specific Linear Programming (LP) formulations, and focusing on the role of certain parameters in order to route/speed up the diffusion process. More specifically, we first show that Galam’s model can be easily generalized; then, we give evidence that some of the parameters which govern its behaviour can be fruitfully determined exogenously, by coupling the model with a LP framework. The paper is organized as follows: Section 2 reviews some basics of Galam’s model [1]. In Section 3 we describe a possible generalization for Galam’s model. Section 4 analyzes an LP formulation paired Modeling and Analysis of Complex Systems and Processes - MACSPro’2020, October 22–24, 2020, Venice, Italy & Moscow, Russia " ellero@unive.it (A. Ellero); fasano@unive.it (G. Fasano); favaret@unive.it (D. Favaretto)  0000-0002-0389-7998 (A. Ellero); 0000-0003-4721-8114 (G. Fasano) © 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings http://ceur-ws.org ISSN 1613-0073 CEUR Workshop Proceedings (CEUR-WS.org) with Galam’s model, and includes some theoretical properties. Finally, in Section 4.1 we report a numerical experience and Section 5 completes the paper. 2. Basics on Galam’s Model This section recalls some basics of Galam’s model in [1]. Let us consider a set of 𝑁 individuals (agents), who may have one of two different opinions (say ‘+’ or ‘−’) about a certain topic. These agents periodically meet in subgroups of individuals, in order to join a discussion and possibly change their respective opinion. Assume at each time step 𝑡 ≥ 0 the 𝑁 agents meet to discuss, and let 𝑁+ (𝑡) (𝑁− (𝑡)) be the number of agents that at time 𝑡 have opinion ‘+’ (‘−’). Clearly 𝑁 = 𝑁+ (𝑡) + 𝑁− (𝑡) for any time step 𝑡. More specifically, at time 𝑡, each agent can belong to a 𝑘-sized group with probability 𝑎𝑘 , being 𝑘 the cardinality of the group, 𝑘 = 1, ..., 𝐿 and 𝐿 ≤ 𝑁 . In Galam’s model (see [1]) the values 𝑎1 , … , 𝑎𝐿 are exogenous parameters which satisfy 𝐿 ∑ 𝑎𝑘 = 1, 𝑎𝑘 ≥ 0, 𝑘 = 1, … , 𝐿. 𝑘=1 After a discussion in the group, at the outset of the next period 𝑡 + 1, any agent can possibly change their opinion (e.g. ‘+’ becomes ‘−’ or viceversa) according to a majority rule; i.e. all agents in a group take the view of the majority in that group. We highlight that in [1], the rule for reversing opinion is assumed to be slightly biased in favor of the negative opinion ‘−’, since tie breaks in favor of ‘−’. Clearly, indicating with 𝑃+ (𝑡) the ‘estimated’ probability that an agent thinks ‘+’ at time 𝑡, the probability to think ‘−’ at step 𝑡 must be given by 𝑃− (𝑡) = 1 − 𝑃+ (𝑡). Hence, based on the above description, Galam in [1] estimates the probability 𝑃+ (𝑡) using the recursive formula 𝐿 𝑘 𝑃+ (𝑡 + 1) = ∑ 𝑎𝑘 ∑ 𝐶𝑗𝑘 𝑃+ (𝑡)𝑗 {1 − 𝑃+ (𝑡)}𝑘−𝑗 , (1) 𝑘=1 𝑗=⌊ 𝑘2 +1⌋ where ⌊𝑧⌋ the largest integer less or equal to 𝑧, and 𝐶𝑗𝑘 represents the binomial coefficient (𝑘𝑗 ). Setting the initial condition 𝑃+ (0) = 𝑁+ (0)/𝑁 , where 𝑁+ (0) is the number of agents thinking ‘+’ at 𝑡 = 0, for any 𝑡 ≥ 1 the quantity 𝑃+ (𝑡) may possibly differ from the ‘actual’ frequency of ‘+’, i.e. 𝑁+ (𝑡)/𝑁 (see [10]). Note that for any choice of 𝑎1 , … , 𝑎𝐿 we have 0 ≤ 𝑃+ (𝑡 + 1) ≤ 1, being 𝑘 𝑘 ∑ 𝐶𝑗𝑘 𝑃+ (𝑡)𝑗 {1 − 𝑃+ (𝑡)}𝑘−𝑗 < ∑ 𝐶𝑗𝑘 𝑃+ (𝑡)𝑗 {1 − 𝑃+ (𝑡)}𝑘−𝑗 = [𝑃+ (𝑡) + (1 − 𝑃+ (𝑡))]𝑘 = 1𝑘 = 1. 𝑗=⌊ 𝑘2 +1⌋ 𝑗=0 Finally (see [1]), we define the killing point as the threshold value 𝑃̂ + satisfying when 𝑃+ (0) > 𝑃̂ + then lim 𝑃+ (𝑡) = 1, 𝑡→∞ when 𝑃+ (0) < 𝑃̂ + then lim 𝑃+ (𝑡) = 0, 𝑡→∞ when 𝑃+ (0) = 𝑃̂ + then 𝑃+ (𝑡) = 𝑃+ (0), ∀ 𝑡 > 0. According with the last definition, the killing point is a threshold value such that when 𝑁+ (0)/𝑁 lies above 𝑃̂ + , then all agents will eventually have opinion ‘+’. Conversely, when 𝑡 → ∞ all the agents will definitely think ‘−’ if 𝑁+ (0)/𝑁 < 𝑃̂ + . 3. A Possible Generalization of Galam’s Model According to model (1), a strict majority of the members in a subgroup with positive opinion is the necessary and sufficient condition to have opinion ‘+’ for all the members of the subgroup. This simple rule may unlikely be representative of a real behaviour in many opinion dynamics applications. Indeed, the final decision in a group is often the result of a discussion, rather than a mere count of the two opposite opinions in the group. Consider for example the process of market penetration of a product. Social media meetings, word- of-mouth, influentials and rumours drive people’s opinion [11]. Similarly, (1) is likely reliable in political contexts, where decisions are taken on the base of polling, i.e. by simply counting voters in a group, but the diffusion of information relies on the sensitivity of the members in a group, as well as on outstanding credibility of some of them. This suggests that a reliable model should encompass exogenous parameters that influence its performance, depending on the particular situation at hand. Acting on those parameters could allow to increase the reliability of the model. On the other hand, communication often requires to reach a sufficient level of penetration of the message in a group of people: consider for example the marketing requirement to reach an appreciable penetration of a product in the market [12], a critical mass of consumers, etc. The related literature suggests that, by creating a strong influence on the consumer in the early life of a product, we may determine the success of sales. The latter result can be predicted by possibly modifying the models in (1) and in [10], so that consumers are forced to: 1. recognize the product and become more akin on consumption, 2. trust the product, 3. improve and advertise its diffusion. We propose to generalize Galam’s model (1) considering a smoother dynamics, i.e., without consid- ering strict majority as a necessary and sufficient condition to move the whole subgroup to the same opinion. We assume that after discussions, all agents in a subgroup will assume opinion ‘+’ with a probability 𝛼𝑗𝑘 , being 0 < 𝛼𝑗𝑘 < 1, which depends on the size 𝑘 of the group, as well as on the number 𝑗 of agents having opinion ‘+’ before discussion. To model this new dynamics we may consider to replace (1) by 𝐿 𝑘 𝑃+ (𝑡 + 1) = ∑ 𝑎𝑘 ∑ 𝛼𝑗𝑘 𝐶𝑗𝑘 𝑃+ (𝑡)𝑗 {1 − 𝑃+ (𝑡)}𝑘−𝑗 , (2) 𝑘=1 𝑗=0 where 𝛼𝑗𝑘 , 𝑘 = 1, … , 𝐿, 𝑗 = 0, … , 𝑘, represent probabilities. To understand the idea behind model (2), let us first observe that choosing the coefficients 𝛼𝑗𝑘 in the following way (see Figure 1) ⎧ ⎪ 𝑘 ⎪ ⎪ 0 𝑖𝑓 𝑗 < ⌊ + 1⌋ ⎪ 2 𝛼𝑗𝑘 = ⎨ (3) ⎪ ⎪ 𝑘 ⎪ ⎪ 1 𝑖𝑓 𝑗 ≥ ⌊ + 1⌋ ⎩ 2 we have, once again, Galam’s model (1): therefore (2) generalizes Galam’s model. More in general, probabilities 𝛼𝑗𝑘 should likely be defined so as to be increasing with respect to 𝑗, while decreasing with respect to 𝑘. In this regard it makes sense to set the probability 𝛼𝑗𝑘 as equal to zero, when the number 𝑗 of ‘+’ in a group is rather low (e.g., lower than strict majority). Conversely, it may approach 1 in case the number of ‘+’ becomes significantly high (higher than strict majority). On the contrary, when the number of positive opinions in a subgroup has an intermediate value, the probability 𝛼𝑗𝑘 Figure 1: For a given 1 ≤ 𝑘 ≤ 𝐿 the model (3) considers the above step-shaped choice for the coefficients {𝛼𝑗𝑘 }. In particular, if 𝑗 < ⌊𝑘/2 + 1⌋ then 𝛼𝑗𝑘 = 0, otherwise 𝛼𝑗𝑘 = 1, so that this choice corresponds exactly to obtain the original Galam’s model (1). can be reasonably considered as a function increasing from zero to 1 as 𝑗 increases. If the increasing function of 𝑗 is assumed to be linear, then we can define the coefficients (probabilities) 𝛼𝑗𝑘 as ⎧ ⎪ ⎪ ⎪ 0, 𝑖𝑓 𝑗 ≤ ⌊ 𝑘2 + 1⌋ − 𝑧𝑗𝑘 , ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 𝑗 − 𝑘 + 1 − 𝑧𝑗𝑘 𝑘 𝛼𝑗 = ⎨ (⌊ 2 ⌋ ) (4) ⎪ , 𝑖𝑓 ⌊ 𝑘2 + 1⌋ − 𝑧𝑗𝑘 < 𝑗 < ⌊ 𝑘2 + 1⌋ − 𝑧𝑗𝑘 + 2ℎ, ⎪ ⎪ 2ℎ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1, 𝑖𝑓 𝑗 ≥ ⌊ 𝑘2 + 1⌋ − 𝑧𝑗𝑘 + 2ℎ. ⎩ The probabilities defined in (4) generalize (3) (it suffices to set 𝑧𝑗𝑘 and ℎ equal to zero -see Figure 2). We remark that 𝑧𝑗𝑘 in (4) represents a shift (either positive or negative) with respect to the value ⌊ 𝑘2 + 1⌋, while 1/(2ℎ) is the slope of the ramp in Figure 2. To understand the implications of the choice in (4), we consider a numerical example. Let us start with the scenario reported in [1], where 𝐿 = 4, 𝑎1 = 0, 𝑎2 = 𝑎3 = 𝑎4 = 1/3 (and 𝑧𝑗𝑘 = 0 for all 𝑗 and 𝑘). The killing point (𝐾 𝑃) lies between 0.84 and 0.87. We first plotted 𝑃+ (𝑡 + 1) vs. 𝑃+ (𝑡) as in (1), choosing both 𝑃+ (1) = 0.84 (asterisks ‘∗’ in Figure 3) and 𝑃+ (1) = 0.87 (circles ‘𝑜’ in Figure 3); the overall results are depicted in Figure 3. Then, we also reported in Figure 3 the model (2) with the choice (4). As we can easily deduce, the dynamics of Galam’s model in [1] is completely upset when the coefficients {𝛼𝑗𝑘 } in (3) are replaced by (4). This reveals that the existence of a killing point in a generalized Galam’s model is not invariant under a modification of the coefficients in {𝛼𝑗𝑘 }. The model performance seems to be intrinsically affected by the underlying hypothesis on the coefficients {𝛼𝑗𝑘 }, i.e., when the majority rule is not satisfied then the dynamics of the model may strongly change. Anyway, the generalized model (2) can be used to provide fruitful results, not only to study the process of diffusion of information, but also to suggest ways to control it. For example, we can deter- mine values of {𝛼𝑗𝑘 } that, starting at time 𝑡 with 𝑃+ (𝑡) = 𝑃̄ + (𝑡), allow to maximize 𝑃+ (𝑡 + 1). The values of the coefficients {𝛼𝑗𝑘 } can be considered as a cost (say an effort) to be faced when trying to foster the diffusion of a positive opinion: high (expensive) values of probability convey a group to opinion Figure 2: For a given 1 ≤ 𝑘 ≤ 𝐿 the model (4) considers the above piecewise-linear choice for the coefficients {𝛼𝑗𝑘 }, where 𝑧𝑗𝑘 represents a shift with respect to the abscissa ⌊𝑘/2 + 1⌋, and 1/(2ℎ) is the slope of the ramp. 1 Galam model (below the KP) 0.9 (2)+(4) model (below the KP) Galam model (above the KP) 0.8 (2)+(4) model (above the KP) 0.7 0.6 P + (t+1) 0.5 0.4 0.3 0.2 0.1 0 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 P + (t) Figure 3: Setting {𝛼𝑗𝑘 } as in (4), the resulting dynamics of 𝑃+ (𝑡 + 1) vs. 𝑃+ (𝑡) is completely upset with respect to the original Galam’s model (1). Here the parameters used in (1) and (2) are: 𝐿 = 4, 𝑎1 = 0, 𝑎𝑘 = 1/3, 𝑘 = 2, 3, 4, so that 𝐾 𝑃 ≈ 0.846. Moreover, we set 𝑧𝑗𝑘 = 0 and ℎ = 10−5 in (4). ‘+’. In other words, we wonder how to set the coefficients {𝛼𝑗𝑘 } to pursue our maximization goal on 𝑃+ (𝑡 + 1), starting from 𝑃̄ + (𝑡), with the minimum effort. In the context of production and Marketing, where the agents are replaced by consumers, the latter conclusion might read as follows: an extra effort in terms of advertising campaign has to be carried on, in order to promote a certain spread of the products. In particular, the coefficients {𝛼𝑗𝑘 } summarise the resulting effort and consequently represent unknowns to be determined. 4. A LP Model for a Single Period Analysis On the guideline of the analysis in Section 3, we propose to embed the dynamics in (2) within the following LP scheme: 𝐿 𝑘 max ∑ 𝑎𝑘 ∑ 𝛼𝑗𝑘 𝐶𝑗𝑘 𝑃+ (𝑡)𝑗 {1 − 𝑃+ (𝑡)}𝑘−𝑗 , (5) 𝛼 𝑘=1 𝑗=0 𝛼𝑗𝑘 ≤ 𝛼𝑗+1 𝑘 𝑗 = 0, 1, … , 𝑘 − 1; 𝑘 = 1, … , 𝐿, (6) 𝛼𝑗𝑘 ≥ 𝛼𝑗𝑘+1 𝑗 = 0, 1, … , 𝑘; 𝑘 = 1, … , 𝐿 − 1, (7) 𝐿 ∑ 𝛼𝑗𝑘 ≤ 𝑏𝑗 (𝑡) 𝑗 = 0, 1, … , 𝑘, (8) 𝑘=1 0 ≤ 𝛼𝑗𝑘 ≤ 1 𝑗 = 0, 1, … , 𝑘; 𝑘 = 1, … , 𝐿. (9) Observe that by solving the above LP, with respect to the unknowns 𝛼𝑗𝑘 , 𝑘 = 1, … , 𝐿, 𝑗 = 0, 1, … , 𝑘, we aim to determine a set of decision variables in order to improve the diffusion of information, i.e. to increase 𝑃+ (𝑡 + 1) with respect to 𝑃+ (𝑡). The constraints in (6)-(9) may be motivated as follows: (6) implies that in two subgroups of cardinality 𝑘, the larger the number of individuals thinking ‘+’, the larger the probability 𝛼𝑗𝑘 ; (7) implies that when two subgroups of agents include the same number of individuals thinking ‘+’, then to the subgroup of smaller cardinality it corresponds a larger value of 𝛼𝑗𝑘 ; (8) represent budget constraints, i.e. we allow that at the current time step 𝑡, for any given value of 𝑗, not all the unknowns {𝛼𝑗𝑘 } can be possibly set to 1, so limiting the freedom when selecting the unknowns; (9) specify that each unknown 𝛼𝑗𝑘 represents a probability value. A solution (not necessarily unique) of (5)-(9) can dramatically increase the probability 𝑃+ (𝑡 + 1) of information spreading with respect to 𝑃+ (𝑡). We also remark that (5)-(9) is a concave problem, so that its solutions are vertices of the feasible set (6)-(9). In addition, here local maxima are also global maxima so that they can be detected by basic packages. We show now that to a large extent the model (5)-(9) generalizes (1), in accordance with the next proposition. Proposition 4.1. Consider the linear program (5)-(9). Let the following choice (1 ≤ 𝑘 ≤ 𝐿 and 0 ≤ 𝑗 ≤ 𝑘) ⎧ ⎪ 0, 𝑓 𝑜𝑟 𝑎𝑛𝑦 𝑗 < ⌊ 𝑘2 + 1⌋ , ⎪ 𝑘 𝛼𝑗 = ⎨ (10) ⎪ ⎪ ⎩ 1, 𝑓 𝑜𝑟 𝑎𝑛𝑦 𝑗 ≥ ⌊ 𝑘2 + 1⌋ , satisfy the budget constraints (8). Then (10) is a feasible point of (5)-(9) and the objective function in (5) coincides with 𝑃+ (𝑡 + 1) in (1). Proof. By (9) the feasible set 𝔽 of problem (5)-(9) is compact, so that the continuity of the function in (5) ensures the existence of a finite solution, provided that 𝔽 ≠ ∅. Now, observe that with the posi- tions (10) the objective function (5) coincides with the model (1). Moreover, the choice in (10) surely satisfies the constraints (6), since for a given value 1 ≤ 𝑘̄ ≤ 𝐿 relations (10) describe the monotone ̄ nondecreasing sequence {𝛼𝑗𝑘 }. Similarly, for a given value 0 ≤ 𝚥̂ ≤ 𝑘, we see from (10) that ⎧ ⎪ ⎪ 𝑖𝑓 𝛼𝚥̂𝑘 = 0 𝑡ℎ𝑒𝑛 𝛼𝚥̂𝑘+1 = 0 ⎪ ⎨ ⎪ ⎪ ⎪ 𝑖𝑓 𝛼𝚥̂𝑘 = 1 𝑡ℎ𝑒𝑛 𝑒𝑖𝑡ℎ𝑒𝑟 𝛼𝚥̂𝑘+1 = 0 𝑜𝑟 𝛼𝚥̂𝑘+1 = 1, ⎩ which trivially ensures that also the constraints (7) are satisfied. Finally, the positions (10) immedi- ately satisfy (9), which completes the proof. Q.E.D. In order to make Proposition 4.1 useful in applications, it is therefore necessary to provide an estimation for the values of the budget 𝑏𝑗 (𝑡) in (8), so that the satisfaction of constraints (8) can be guaranteed. Proposition 4.2. Consider the linear program (5)-(9) and let 𝛼𝑗𝑘 be assigned as in (10), with 1 ≤ 𝑘 ≤ 𝐿 and 0 ≤ 𝑗 ≤ 𝑘. Then ⎧ 2 ⎪ 𝐿 𝐿 ⎪ ⎪ + , 𝑤ℎ𝑒𝑛 𝐿 𝑖𝑠 𝑒𝑣𝑒𝑛, 𝐿 𝑘 ⎪ (2) 2 ⎪ ∑ ∑ 𝛼𝑗𝑘 = ⎨ (11) 𝑘=1 𝑗=0 ⎪ ⎪ 2 ⎪ 𝐿−1 ⎪ ⎪ + 𝐿, 𝑤ℎ𝑒𝑛 𝐿 𝑖𝑠 𝑜𝑑𝑑. ⎩ ( 2 ) Proof. Since ⌊ 𝑘2 + 1⌋ = ⌊ 𝑘2 ⌋ + 1, by (10) we have 𝐿 𝑘 𝐿 𝑘 ∑ ∑ 𝛼𝑗𝑘 = ∑ ∑ 1. 𝑘=1 𝑗=0 𝑘=1 𝑗=⌊ 𝑘 ⌋+1 2 Thus, for 𝐿 even and setting 𝑝 = ⌊ 𝑘2 ⌋ we have 𝐿 𝑘 1 𝐿/2 2𝑝 2𝑝+1 𝐿+1 ∑ ∑ 1 = ∑ 1 + ∑ ∑ 1 + ∑ 1 − ∑ 1. 𝑘=1 𝑗=⌊ 𝑘 ⌋+1 𝑗=1 𝑝=1 [𝑗=𝑝+1 𝑗=𝑝+1 ] 𝑗=⌊ 𝐿 ⌋+1 2 2 Now, since 𝐿/2 2𝑝 2𝑝+1 𝐿/2 ∑ ∑ 1 + ∑ 1 = ∑ [(2𝑝 − (𝑝 + 1) + 1) + (2𝑝 + 1 − (𝑝 + 1) + 1)] 𝑝=1 [𝑗=𝑝+1 𝑗=𝑝+1 ] 𝑝=1 𝐿/2 𝐿/2 𝐿 = ∑ [𝑝 + (𝑝 + 1)] = 2 ∑ 𝑝 + −1+1 𝑝=1 𝑝=1 (2 ) 𝐿 𝐿 2 ( 2 + 1) 𝐿 𝐿 𝐿 = 2⋅ + = +2 , 2 2 2 (2 ) when 𝐿 is even we finally obtain 𝐿 𝑘 𝐿+1 𝐿 𝐿 ∑ ∑ 1 = 1+ +2 − ∑ 1 𝑘=1 𝑗=⌊ 𝑘 ⌋+1 2 (2 ) 𝐿 2 𝑗=⌊ 2 ⌋+1 2 𝐿 𝐿 𝐿 𝐿 𝐿 = +2 − = + . (12) 2 (2 ) 2 (2) 2 On the other hand, when 𝐿 is odd we have 𝐿 𝑘 1 (𝐿−1)/2 2𝑝 2𝑝+1 ∑ ∑ 1 = ∑1 + ∑ ∑ 1+ ∑ 1 , 𝑘=1 𝑗=⌊ 𝑘 ⌋+1 𝑗=1 𝑝=1 [𝑗=𝑝+1 𝑗=𝑝+1 ] 2 and since (𝐿−1)/2 2𝑝 2𝑝+1 (𝐿−1)/2 (𝐿−1)/2 (𝐿−1)/2 ∑ ∑ 1+ ∑ 1 = ∑ [2𝑝 + 1] = 2 ∑ 𝑝 + ∑ 1 𝑝=1 [𝑗=𝑝+1 𝑗=𝑝+1 ] 𝑝=1 𝑝=1 𝑝=1 𝐿−1 𝐿−1 1 𝐿−1 = 2 +1 + 2 ( 2 ) 2 2 𝐿−1 𝐿−1 = +2 , 2 ( 2 ) we finally have for 𝐿 odd 𝐿 𝑘 2 𝐿−1 𝐿−1 𝐿−1 ∑ ∑ 1 = 1+ +2 = + 𝐿. (13) 𝑘=1 𝑗=⌊ 𝑘 ⌋+1 2 ( 2 ) ( 2 ) 2 Relations (12) and (13) yield (11). Q.E.D. Proposition 4.2 allows both the easy assessment of reliable values for the parameters {𝑏𝑗 (𝑡)}, and a possible generalization of constraints (8). Indeed, replacing the 𝑘 + 1 constraints in (8) by the unique constraint 𝐿 𝑘 𝑘 ∑ ∑ 𝛼𝑗𝑘 ≤ ∑ 𝑏𝑗 (𝑡) = 𝑏(𝑡), 𝑘=1 𝑗=0 𝑗=0 the last proposition suggests to set ⎧ 2 ⎪ 𝐿 𝐿 ⎪ ⎪ + , 𝑤ℎ𝑒𝑛 𝐿 𝑖𝑠 𝑒𝑣𝑒𝑛, ⎪ (2) 2 ⎪ 0 < 𝑏(𝑡) ≤ ⎨ ⎪ ⎪ 2 ⎪ 𝐿−1 ⎪ ⎪ + 𝐿, 𝑤ℎ𝑒𝑛 𝐿 𝑖𝑠 𝑜𝑑𝑑, ⎩ ( 2 ) in order to generalize the idea behind (1). 4.1. A Numerical Example To avoid reporting a lengthy numerical experience, which is out of the scopes of the current paper, we first experienced the LP program (5)-(9) over the following small-scale setting of parameters ⎧ ⎪ 𝐿=7 ⎪ ⎨ 𝑎 = (0.1 0.2 0.3 0.0 0.0 0.4 0.0)𝑇 ⎪ ⎪ ⎩ 𝑃+ (𝑡) = 0.65. This choice of the parameters corresponds to the case in which the population meets in subgroups of dimension 1, 2, 3 and 6, with probabilities 0.1, 0.2, 0.3 and 0.4 respectively, with an initial 65% of the population thinking ‘+’. In addition, we replaced the constraints (8) by the unique constraint 𝐿 𝑘 ∑ ∑ 𝛼𝑗𝑘 ≤ 𝑏(𝑡) 𝑘=1 𝑗=0 and chose the value of the budget parameter 𝑏(𝑡) = 10.1 (see also Proposition 4.2), in order to allow a nonempty feasible set. The resulting LP yielded the solution (we used the solver MINOS [13]) ⎛ 𝑘=1 𝑘=2 𝑘=3 𝑘=4 𝑘=5 𝑘=6 𝑘=7 ⎞ ⎜ ⎟ ⎜ 𝑗=0 0 0 0 0 0 0 0 ⎟ ⎜ 𝑗=1 1 1 1 0 0 0 0 ⎟ ⎜ 𝑗=2 ∗ 1 1 0 0 0 0 ⎟ 𝑘 ⎜ ⎟ [𝛼𝑗 ] = ⎜ 𝑗 = 3 ∗ ∗ 1 0 0 0 0 ⎟ ⎜ 𝑗=4 ∗ ∗ ∗ 0.683̄ 0.683̄ 0.683̄ 0 ⎟ ⎜ ̄ 0.683̄ ⎟ ⎜ 𝑗 = 5 ∗ ∗ ∗ ∗ 0.683 0 ⎟ ⎜ 𝑗=6 ∗ ∗ ∗ ∗ ∗ 0.683̄ 0 ⎟ ⎜ 𝑗=7 ∗ ∗ ∗ ∗ ∗ ∗ 0 ⎟ ⎝ ⎠ and the corresponding final value of the objective function 𝑃+ (𝑡 + 1) ≈ 0.7045, showing an increase with respect to the initial value 𝑃+ (𝑡) = 0.65. Moreover, as expected the value 0.7045 is larger than the value 7 𝑘 𝑃+ (𝑡 + 1) = ∑ 𝑎𝑘 ∑ 𝐶𝑗𝑘 0.65𝑗 (1 − 0.65)𝑘−𝑗 ≈ 0.2620 𝑘=1 𝑗=⌊ 𝑘2 +1⌋ predicted by Galam’s model. The above example suggests that we identified the best way to distribute the budget 𝑏(𝑡) in order to increase the spreading of opinion ‘+’. As a further experiment, now we consider the numerical example proposed in [1], where 𝐿 = 4, 𝑎1 = 0, 𝑎𝑘 = 1/3, 𝑘 = 2, 3, 4. The killing point 𝐾 𝑃 corresponding to the latter parameters satisfies 0.84 < 𝐾 𝑃 < 0.87. In particular, we analyzed two scenarios for the LP (5)-(9), by respectively setting Scenario I Scenario II ⎧ ⎪ ⎧ ⎪ ⎪ 𝐿=4 ⎪ 𝐿=4 ⎪ ⎪ 𝑎 = (0.0 1/3 1/3 1/3) 𝑇 ⎪ ⎪ 𝑎 = (0.0 1/3 1/3 1/3)𝑇 ⎨ ⎪ 𝑃+ (𝑡) = 0.8 ⎨ ⎪ 𝑃+ (𝑡) = 0.9 ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ 𝑏(𝑡) = 5.5 ⎪ ⎩ 𝑏(𝑡) = 5.5 According with the setting of Scenario I, considering that 𝑃+ (𝑡) = 0.8 (i.e. 𝑃+ (𝑡) is below the 𝐾 𝑃), we want to verify, allowing the budget 𝑏(𝑡) = 5.5, the maximum value for 𝑃+ (𝑡 + 1) by solving (5)-(9). We obtain in particular 𝑃+ (𝑡 + 1) ≈ 0.81173 > 𝐾 𝑃, corresponding to the set of unknowns ⎛ 𝑘=1 𝑘=2 𝑘=3 𝑘=4 ⎞ ⎜ 𝑗=0 0 0 0 0 ⎟ ⎜ ⎟ 𝑗 = 1 0.25 0.25 0 0 ⎟ 𝛼 𝑘 = ⎜ [ 𝑗] ⎜ 𝑗=2 . (14) ∗ 1 1 0 ⎟ ⎜ 𝑗=3 ∗ ∗ 1 1 ⎟ ⎜ ⎟ ⎝ 𝑗=4 ∗ ∗ ∗ 1 ⎠ Also observe that simply setting for instance 𝑏(𝑡) = 2.5 (i.e. insufficient budget) in Scenario I, in place of 𝑏(𝑡) = 5.5, we obtain 𝑃+ (𝑡 + 1) ≈ 0.45226 < 𝐾 𝑃, corresponding to the new set of unknowns ⎛ 𝑘=1 𝑘=2 𝑘=3 𝑘=4 ⎞ ⎜ 𝑗=0 0 0 0 0 ⎟ ⎜ ⎟ 𝑗=1 0 0 0 0 ⎟ [𝛼𝑗 ] = ⎜⎜ 𝑗 = 2 𝑘 . (15) ∗ 1 0 0 ⎟ ⎜ 𝑗=3 ∗ ∗ 1 0 ⎟ ⎜ ⎟ ⎝ 𝑗=4 ∗ ∗ ∗ 0.5 ⎠ The above experiment proves that the choice of the budget 𝑏(𝑡) might have a dramatic effect in order to increase the value of probability, from 𝑃+ (𝑡) to 𝑃+ (𝑡 + 1). Indeed, starting from 𝑃+ (𝑡), suitably tuning of quantities [𝛼𝑗𝑘 ] can yield a value for the probability 𝑃+ (𝑡 + 1) either below or above the 𝐾 𝑃, simply depending on 𝑏(𝑡). In this regard the value of 𝑃+ (𝑡), though important, seems to be less relevant, and is often exogenously set by the application in hand. Similarly, considering the Scenario II, observing that now 𝑃+ (𝑡) = 0.9 (i.e. 𝑃+ (𝑡) is above the 𝐾 𝑃), again we want to verify, allowing the budget 𝑏(𝑡) = 5.5, the maximum value for 𝑃+ (𝑡 +1) solving (5)-(9). We obtain in particular 𝑃+ (𝑡 + 1) ≈ 0.9249 > 𝐾 𝑃, corresponding to the same set of unknowns in (14). On the other hand, simply setting again 𝑏(𝑡) = 2.5 (i.e. budget insufficient) in Scenario II, in place of 𝑏(𝑡) = 5.5, we obtain 𝑃+ (𝑡 + 1) ≈ 0.62235 < 𝐾 𝑃, corresponding to the set of unknowns in (15). Again, the latter numerical results prove that the choice of the quantity 𝑏(𝑡) has a dramatic effect in order to increase the value of probability, from 𝑃+ (𝑡) to 𝑃+ (𝑡 + 1). Moreover, a suitable choice of the quantities can move the value 𝑃+ (𝑡 + 1) above 𝐾 𝑃, even though the value 𝑃+ (𝑡 + 1) predicted by the model (1) possibly does not exceed 𝐾 𝑃. On the overall, the above results indicate that our LP-based approach is definitely more general than the approach described in [1], since it gives explicit indications on the effort necessary to influence opinions in those subgroups of cardinality 𝑘. 5. Conclusions We studied the problem of possibly enhancing the sociophysics model (1), using a mathematical pro- gramming perspective. We combined the model in (1) with a LP scheme, in order to possibly control the spreading of information through the assessment of the unknowns 𝛼𝑗𝑘 in (2). The value of these variables indicates the effort which is necessary in order to convince people in subgroups of cardi- nality 𝑘, with the aim of maximizing 𝑃+ (𝑡 + 1) from a given 𝑃+ (𝑡). As a next step of research, we are going to generalize the single-period formulation (5)-(9) to a multi-period scheme, with the final goal to maximize 𝑃+ (𝑇 ), being 𝑡 = 1, … , 𝑇 the time periods. Acknowledgments G. Fasano thanks GNCS group of IN𝛿AM (Istituto Nazionale di Alta Matematica, Italy) for the support he received. References [1] S. Galam, Modelling rumors: the no plane pentagon french hoax case, Physica A: Statis- tical Mechanics and its Applications 320 (2003) 571–580. doi:https://doi.org/10.1016/ S0378-4371(02)01582-0. [2] S. Galam, Sociophysics: a review of Galam models, International Journal of Modern Physics C 19 (2008) 509–440. doi:https://doi.org/10.1142/S0129183108012297. [3] F. M. Bass, A new product growth for model consumer durables, Management Science 50 (2004) 1833–1840. doi:https://10.1287/mnsc.1040.0264. [4] G. A. Moore, Crossing the chasm, Harper Collins, New York, NY, 1991. [5] E. M. Rogers, Diffusion of Innovations, 5th edn ed., The Free Press, New York, NY, 2003. [6] T. C. Schelling, Dynamic models of segregation, The Journal of Mathematical Sociology 1 (1971) 143–186. doi:https://10.1080/0022250X.1971.9989794. [7] A. Ellero, G. Fasano, A. Sorato, Stochastic model for agents interaction with opinion-leaders, Physical Review E 87 (2013). doi:https://doi.org/10.1103/PhysRevE.87.042806. [8] E. Katz, P. F. Lazarsfeld, Personal influence - The part played by people in the flow of mass communication, The Free Press, Glencoe, IL, 1955. [9] J. Goldenberg, S. Han, D. R. Lehmann, J. W. Hong, The role of hubs in the adoption processes, Journal of Marketing 73 (2009) 1–13. doi:https://doi.org/10.1509/jmkg.73.2.1. [10] A. Ellero, G. Fasano, A. Sorato, A modified Galam’s model for word-of-mouth information ex- change, Physica A: Statistical Mechanics and its Applications 388 (2009) 3901–3910. doi:https: //doi.org/10.1016/j.physa.2009.06.002. [11] C. V. den Bulte, Y. V. Joshi, New product diffusion with influentials and imitators, Marketing Science 26 (2007) 400–421. doi:https://10.1287/mksc.1060.0224. [12] A. J. Glass, Product cycle and market penetration, International Economic Review 38 (1997) 865–891. doi:https://doi.org/10.2307/2527220. [13] NEOS solvers, 2020. Https://neos-server.org/neos/solvers/nco:MINOS/AMPL.html.