In this article we study the allocation of a budget to promote an opinion in a group of agents. We assume that their opinion dynamics are based on the well-known voter model. We are interested in finding the most efficient use of a budget over time in order to manipulate a social network. We address the problem using the theory of discounted Markov decision processes. Our contributions can be summarized as follows: (i) we introduce the discounted Markov decision process in our cases, (ii) we present the corresponding Bellman equations, and, (iii) we solve the Bellman equations via backward programming. This work is a step towards providing a solid formulation of the budget allocation in social networks.
During the last decades a lot of research effort has
been devoted to model the underlying process of
opinion formation of agents that interact through a social
network. In this respect, DeGroot’s [
In this work, we are interested in finding the most efficient use over time of a budget in order to manipulate a social network. The idea is to promote an opinion by paying agents to supplant their true opinions. We model opinions as two values, 0 or 1, with 1 (0) representing supportive (non-supportive) opinion.
We frame the problem of designing sequential
payment strategies as a discounted Markov decision
process (DMDP). DMDPs have been widely used to
formulate many decision making problems in science and
engineering (see, e.g., [
First of all, we focus on a fully connected network where agents change their opinion following a voter model. We provide the correspondent Bellman equations to solve this problem and we show through an example how to solve the stated problem in practice. We provide a structural characterization of the associated value function and the optimal payment strategy. Then, we compute the optimal payment using dynamic backward programing. 2
In order to find the optimal budget allocation on binary opinion dynamics, we make extensive use of the theory of DMDPs. First, we adopt the voter model of opinion formation over a social network. Then, we define the DMDP and the corresponding Bellman equations to obtain the optimal strategy of budget allocation.
Consider an undirected social network G = (I; E ), where I stands for the set of agents, indexed from 1 to n, and E ⊆ I × I is the set of edges. Each agent i ∈ I has a binary initial opinion. Opinions take values 0 or 1. If agent i has opinion 0 (analogously, 1) we label it as non-supporter (supporter ). For example, if agents are discussing about politics, 1 could be supporting a particular party and 0 not supporting it.
Moreover, we distinguish two cases, depending on whether the network is fully connected or not.
We start by studying the fully connected case. In each decision epoch, agents update their opinions following a voter model sensitive to external payments. Let ∈ [0; 1) be the discount factor, which represents the loss of reward in the future with respect to the current reward. A discounted Markov decision process (DMDP) is a 5-tuple (S; AS ; P; R; ), where S is a finite set of states, AS is a finite set of actions, P is the set of transition probabilities and R is the set of rewards.
Therefore, the model is defined as follows: 1. Decision epochs: the set of decision epochs is defined as t = 1; 2; : : : ; T . We consider a finite discrete-time system. At each decision epoch t we observe the state s and choose an action a. 2. States: the state space S of the DMDP consists on the possible number of supporters, s ∈ N, s = S{i ∈ I S i is a supporter}S. 3. Actions: the action space As is the set of actions available in state s (without loss of generality, actions are state independent). We consider that the actions a ∈ N are the possible number of payments, a = S{i ∈ I S i receives a payment}S, where the non-supporter agents have a cost cNS for changing their opinion from non-supporter to supporter, and the supporter agents, a cost cS to hold their supporter opinion. We assume that the cost of changing their opinion is higher than the cost of holding it, i.e., cNS > cS . We consider a finite budget b. Notice that, because the actions are constrained by the budget, they are stationary. 4. Transition probabilities: if the DMDP in decision epoch t is at state s1, the probability that it transitions to state s2 taking action a is denoted pt(s1; s2; a). Due to the natural independence of agents transitions, we compute those probabilities as the product of the transition probabilities of the agents. The evolution of one agent i ∈ I will be described by the voter model. Starting from any arbitrary initial labels, supporter (S) or non-supporter (NS), we consider two labeling functions fS (i) and fNS (i), where fS (i) = 1 (fNS (i) = 1) means that agent i is a supporter (non-supporter). At each decision epoch t, each node selects uniformly at random one of its neighbors opinion. For each node j ∈ I, the set of its neighbors is defined as N (j) = {k ∈ I S {j; k} ∈ E }. Therefore, we define for one i ∈ I with zeropayment in decision epoch t the labeling functions,
⎧⎪1 with prob. S{j∈N(i)SfSt (j)=1}S ; fSt+1(i) = ⎪⎨⎪0 with prob. S{j∈N(SiN)S(fiSt)(Sj)=0}S ; ⎪⎩ SN(i)S
f Nt+S1(i) = 1 − fSt+1(i) Analogously, for one agent k ∈ I that receives a payment in decision epoch t we define: ⎧⎪1 with prob. 1; ⎪ fSt+1(k) = ⎨ ⎪0 with prob. 0; ⎪ ⎩ f Nt+S1(k) = 1 − fSt+1(k) As we said, we assume that the graph is fully connected, therefore each agent can communicate with every other agent. We denote the set of nonsupporter agents that receive a payment as L = {i ∈ I S non-supporter & receives a payment} and its cardinality as ` = SLS. Respectively, the set of supporter agents that receive a payment as K = {i ∈ I S supporter & receives a payment} and its cardinality as k = SKS. Notice that a = `+k. Therefore the transition probabilities pt(s1; s2; a) can be computed as: ● If a > s2 then pt(s1; s2; a) = 0: ● If a < s2 then pt(s1; s2; a) = min{s1−k;s2−`}
Q i=max{0;s2−(n−s1)−k}
n − s1 − ` ⋅ s2 − i − (` + k) ⋅
s1 − k i
s1 i n − s1 s1−k−i n n n − s1 n−s1−s2+i+k s1 s2−i−(`+k)
n n 5. Reward: the instant reward in time t and state s is defined as rt(s) = ∑i∈I g ⋅ s, where g denotes the reward provided by one agent.
Let be the value function of the above DMDP, i.e., it is the supreme, over all possible budget allocation strategies, of the expectation of the discounted reward starting from an initial budget b. Under these assumptions, the Bellman equations for all s ∈ S and initial budget b are: (s; b) =
max a ` k∈AS; = + (`⋅cNS+k⋅cS)≤b
E Q∞ trt(s)
t=0 = a ` k∈AS; r0(s) + Q
max (`⋅cN=S++k⋅cS)≤b s′∈S
p1(s; s′; a) ⋅ (s′; b − ` ⋅ cNS − k ⋅ cS + r0(s)); where the budget evolves as b(t + 1) = b(t) + rt(s) − ` ⋅ cNS − k ⋅ cS :
Next, we present the second case where in each decision epoch agents update their opinions following a voter model in a network (not necessarily fully connected) that can be affected by external payments. As before, we design this problem as a DMDP where the set of actions are the possible external payments.
Therefore, let ∈ [0; 1) be the discount factor, we consider, by a slight abuse of notation, the 5-tuple (S; AS ; P; R; ) as before. Concretely, the elements changed from the previous model: 1. Decision epochs: the set of decision epochs is defined as t = 1; 2; : : : ; T . 2. States: the state space S of the DMDP, consists on all possible combinations of agents’ labels, nonsupporter (0) or supporter (1), i.e., s ∈ {0; 1}n. 3. Actions: the action space As is the set of actions available in state s (without loss of generality, actions are state independent). An action means whether or not we give a payment to each of the agents, a ∈ {0; 1}n, where a 0 (respectively 1) in position i means we give no payment (payment) to agent i ∈ I. We also define a vector of costs c ∈ R+n whose element ci > 0 is the cost of changing by one unit the opinion of agent i, in case agent i is nonsupporter, or the cost of holding the opinion of agent i, in case agent i is a supporter. 4. Transition probabilities: as before, if the DMDP in decision epoch t is at state s1, the probability that it transitions to state s2 taking action a is expressed as pt(s1; s2; a) and can be computed as: ● If SaS > Ss2S then pt(s1; s2; a) = 0: ● If SaS < Ss2S then pt(s1; s2; a) is equal to
M I{ si = s′i} I{si = supp} S{j ∈ N (i)~fSt (j) = 1}S n i=1 SN (i)S t + I{si = non-supp} S{j ∈ N (i)~fNS(j) = 1}S
SN (i)S + I{si ≠ s′i} I{si = supp S{j ∈ N (i)~fSt (j) = 0}S SN (i)S t + I{si = non-supp} S{j ∈ N (i)~fNS(j) = 0}S :
SN (i)S 5. Reward: the instant reward in time t and state s is defined as rt(s) = gT ⋅ s, where g is the vector of rewards whose element gi is the reward that agent i ∈ I provides.
Let be the value function of the above DMDP, i.e., it is the supreme, over all possible budget allocations strategies, of the expectation of the discounted reward starting from an initial budget b. Under these assumptions the Bellman equations for all s ∈ S and initial budget b are:
∞ t (s; b) = am∈AaSx; E tQ0 cT ⋅a≤b =
rt(s) = am∈AaSx; r0(s) + Q cT ⋅a≤b s′∈S
p1(s; s′; a) (s′; b − cT ⋅ a + r0(s)); where the budget evolves as b(t+1) = b(t)−cT ⋅a+R(st) and cT denotes the transpose of vector c. 3
We suppose that after a time T we will not obtain rewards for the supporter agents, so we are interested in the distribution of the DMDP in the time interval [0; T ]. We consider an undirected, fully connected social network G = (I; E ) with n = 7 agents that form opinions with a voter model. In time t = 0, we assign at random an initial label to each agent. Solving the Bellman (fixed point) equations, given the model and the set of states and feasible actions, gives us the best strategy for each state to follow in the time interval. We take T = 6, = 0:8, cNS = 10, cS = 5, B = 30 and g = 8.
Some conclusions can be drawn from the simulations. The optimal payment strategy is to invest all our budget paying to the higher number of agents at time t = 0. Obviously, if all the network is nonsupporter (respectively supporter), the budget will be allocated to change opinions (to hold opinions). However, the distribution of the budget differs for the rest of possible initial states as we show on Table 1.
Initial state s = 1 s = 2 s = 3 s = 4 s = 5 s = 6
Budget Allocation Payments to NS Payments to S 2 1 2 2 1 3 1 4 0 5 0 6
Given the budget allocation at time t = 0, we show in Figure 1 the expected reward obtained at time T for each state s ∈ S. 4
In this work, we have introduced the problem of
budget allocation over time to manipulate a social
network. We have developed a formulation of the
discounted Markov decision process as well as the
corresponding Bellman equations for the voter model
of opinion formation. Using backward programming,
we have obtained the optimal payment strategy for
a small example of agents interacting trough a fully
connected network. Many questions still remain to be
answered. Future work would be devoted to improve
the performance of our simulations in order to obtain
the optimal strategy for larger networks and different
topologies. Moreover, we intend to construct the
DMDP model and the Bellman equations for different
models of opinion dynamics. This will lead to the
mathematical characterization of the optimal policy
for different network structures and opinion formation
models. It will lead also to the characterization of
the most important agents (the agents with highest
benefit-cost ratio) which should be related with its
centrality as shown in previous results [