An application of Linear Programming to Sociophysics Models

Abstract

In this paper we consider a renowned stochastic model from sociophysics reported in [1, 2], which describes the difusion 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

• eol>Stochastic models
• Agents' interaction
• Galam's model
• Linear Programming
• Marketing

1. Introduction

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

step .

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 diferent 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 exogenous parameters which satisfy

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 ∑ = 1, =1

≥ 0, = 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 description, Galam in [1] estimates the probability +( ) using the recursive formula 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 +( ) {1 − +( )} [10]). Note that for any choice of 1, … , we have 0 ≤ +( + 1) ≤ 1, being where ⌊ ⌋ the largest integer less or equal to , and represents the binomial coeficient the initial condition +(0) = +(0)/ , where +(0) is the number of agents thinking ‘+’ at = 0, for . Setting ( ) any ≥ 1 the quantity +( ) may possibly difer from the ‘actual’ frequency of ‘ +’, i.e. +( )/ (see +( ) {1 − +( )} − < ∑ +( ) {1 − +( )} − = [ +( ) + (1 − +( ))] = 1 = 1.

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 . will definitely think ‘ −’ if +(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

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 suficient 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, wordof-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 difusion 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 suficient 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 difusion. ( 2 ) ( 3 ) replace ( 1 ) by

We propose to generalize Galam’s model ( 1 ) considering a smoother dynamics, i.e., without considering strict majority as a necessary and suficient 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 =1 =0 let us first observe that choosing the coeficients in the following way (see Figure 1) where , = 1, … , , = 0, … , , represent probabilities. To understand the idea behind model ( 2 ),

⎧ ⎪ ⎪ ⎪ ⎪⎪⎪ 0 < ⎪⎪ 1 ≥ ⌊ 2 ⎩

⌊ 2 + 1⌋ + 1⌋ we have, once again, Galam’s model ( 1 ): therefore ( 2 ) generalizes Galam’s model. More in general, with respect to . In this regard it makes sense to set the probability

probabilities should likely be defined so as to be increasing with respect to 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 as equal to zero, when the , while decreasing ⎪⎪⎪ 0, ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎪⎪ 1, ⎩ ≤ ⌊ 2 + 1⌋ − ,

≥ ⌊ 2 + 1⌋ − + 2ℎ. the original Galam’s model ( 1 ). In particular, if < ⌊ /2 + 1⌋ then = 0, otherwise = 1, so that this choice corresponds exactly to obtain function of is assumed to be linear, then we can define the coeficients (probabilities) can be reasonably considered as a function increasing from zero to 1 as increases. If the increasing as The probabilities defined in ( 4 ) generalize ( 3 ) (it sufices 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 ( both +( 1 ) = 0.84

) lies between 0.84 and 0.87. We first plotted +( + 1) vs. +( ) as in ( 1 ), choosing (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 coeficients ( 3 ) are replaced by ( 4 ). This reveals that the existence of a killing point in a generalized Galam’s model { } in is not invariant under a modification of the coeficients in intrinsically afected by the underlying hypothesis on the coeficients rule is not satisfied then the dynamics of the model may strongly change. { }. The model performance seems to be { }, i.e., when the majority

Anyway, the generalized model ( 2 ) can be used to provide fruitful results, not only to study the process of difusion of information, but also to suggest ways to control it. For example, we can determine values of { } that, starting at time with +( ) = ̄ +( ), allow to maximize +( + 1). The values of the coeficients the difusion of a positive opinion: high (expensive) values of probability convey a group to opinion { } can be considered as a cost (say an efort) to be faced when trying to foster

≤ the model ( 4 ) considers the above piecewise-linear choice for the coeficients { }, where represents a shift with respect to the abscissa ⌊ /2 + 1⌋, and 1/(2ℎ) is the slope of the ramp. 1 0.9 0.8 0.7 0.6 0.4 0.3 0.2 0.1 ) t(1++0.5 P 0 0

Galammodel(belowtheKP) ( 2 )+( 4 )model(belowtheKP) Galammodel(abovetheKP) ( 2 )+( 4 )model(abovetheKP) 0.5

P+(t) 0.1 0.2 0.3 0.4 0.6 0.7 0.8 0.9 1 so that

≈ 0.846. Moreover, we set = 0 and ℎ = 10−5 in ( 4 ). the original Galam’s model ( 1 ). Here the parameters used in ( 1 ) and ( 2 ) are: = 4, 1 = 0, = 1/3, = 2, 3, 4, ‘+’. In other words, we wonder how to set the coeficients +( + 1), starting from ̄ +( ), with the minimum efort.

In the context of production and Marketing, where the agents are replaced by consumers, the latter conclusion might read as follows: an extra efort in terms of advertising campaign has to be carried on, in order to promote a certain spread of the products. In particular, the coeficients the resulting efort and consequently represent unknowns to be determined.

{ } summarise { } to pursue our maximization goal on

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

Observe that by solving the above LP, with respect to the unknowns , = 1, … , , aim to determine a set of decision variables in order to improve the difusion of information, i.e. to = 0, 1, … , , we increase +( + 1) with respect to +( ). The constraints in ( 6 )-( 9 ) may be motivated as follows: ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 10 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) implies that in two subgroups of cardinality , the larger the number of individuals thinking ‘+’, the larger the probability ; 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 ; represent budget constraints, i.e. we allow that at the current time step set to 1, so limiting the freedom when selecting the unknowns; , for any given value of , not all the unknowns { } can be possibly 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, ⎪ ⎪⎩ 1, <

⌊ 2 + 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 ). ( 5 ) ensures the existence of a finite solution, provided that ≠ ∅ Proof. By ( 9 ) the feasible set of problem ( 5 )-( 9 ) is compact, so that the continuity of the function in . Now, observe that with the positions ( 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 nondecreasing sequence { ̄ }. Similarly, for a given value 0 ≤ ̂ ≤ , we see from ( 10 ) that 1 ≤ ̄ ≤ relations ( 10 ) describe the monotone ⎧ ⎪ ⎨ ⎪ ⎩ ⎪⎪ ̂ = 0 ℎ ⎪⎪ ̂ = 1 ℎ ℎ which trivially ensures that also the constraints ( 7 ) are satisfied. Finally, the positions ( 10 ) immediately 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. and 0 ≤ ≤ . Then Proposition 4.2. Consider the linear program ( 5 )-( 9 ) and let be assigned as in ( 10 ), with 1 ≤ ≤ ∑ Thus, for even and setting = ⌊ 2 ⌋ we have Now, since ∑ ∑ ∑ ) when is even we finally obtain

On the other hand, when is odd we have and since we finally have for odd =

+ 2 − + . 2 ∑ ∑ 2 +1 ( 13 ) ∑ ∑

− 1 ( 2 ) + .

Relations ( 12 ) and ( 13 ) yield ( 11 ). Q.E.D. constraint

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 ∑ the last proposition suggests to set 0 < ( ) ≤ ⎨

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) 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 ∑ nonempty feasible set. The resulting LP yielded the solution (we used the solver MINOS [13]) and chose the value of the budget parameter ( ) = 10.1 (see also Proposition 4.2), in order to allow a [ ] = ⎜ = 3 ⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ 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 7 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 0.84 < < 0.87. In particular, we analyzed two scenarios for the LP ( 5 )-( 9 ), by respectively setting corresponding to the latter parameters satisfies Scenario I ⎧ ⎪ ⎪⎪ = 4 ⎩ ⎨⎪⎪ +( ) = 0.8 ⎪⎪ ( ) = 5.5 obtain in particular +( + 1) ≈ 0.81173 >

, corresponding to the set of unknowns According with the setting of Scenario I, considering that +( ) = 0.8 (i.e. +( ) is below the want to verify, allowing the budget ( ) = 5.5, the maximum value for +( + 1) by solving ( 5 )-( 9 ). We ), we of ( ) = 5.5, we obtain +( + 1) ≈ 0.45226 < Also observe that simply setting for instance ( ) = 2.5 (i.e. insuficient budget) in Scenario I, in place , corresponding to the new set of unknowns The above experiment proves that the choice of the budget ( ) might have a dramatic efect in order to increase the value of probability, from of quantities [ ] can yield a value for the probability +( ) to +( + 1). Indeed, starting from

+( ), suitably tuning +( + 1) either below or above the , simply is often exogenously set by the application in hand. depending on ( ). In this regard the value of +( ), though important, seems to be less relevant, and

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 > On the other hand, simply setting again ( ) = 5.5, we obtain +( + 1) ≈ 0.62235 <

, corresponding to the same set of unknowns in (14). ( ) = 2.5 (i.e. budget insuficient ) in Scenario II, in place of

, corresponding to the set of unknowns in (15). Again, the latter numerical results prove that the choice of the quantity ( ) has a dramatic efect in order to +( ) to +( + 1). Moreover, a suitable choice of the quantities , even though the value +( + 1) predicted by the model ( 1 ) increase the value of probability, from possibly does not exceed can move the value +( + 1) above

. opinions in those subgroups of cardinality .

5. Conclusions

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 efort necessary to influence We studied the problem of possibly enhancing the sociophysics model ( 1 ), using a mathematical programming 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 efort which is necessary in order to convince people in subgroups of cardinality , 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

he received.

G. Fasano thanks GNCS group of IN AM (Istituto Nazionale di Alta Matematica, Italy) for the support

References

[1] S. Galam , Modelling rumors: the no plane pentagon french hoax case , Physica A: Statistical 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 , Difusion 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 exchange , 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 difusion 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.