{'fraction_non_alphanumeric': 0.032683304586574674, 'fraction_numerical': 0.008571227427927769, 'mean_word_length': 3.986309784993418, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Good versus Evil: A Framework for Optimal Investment Strategies for Competing Camps in a Social Network

We study the problem of optimally investing in nodes of a social network in a competitive setting, wherein two camps attempt to maximize adoption of their opinions by the population. Using a natural model of opinion dynamics, we formulate the problem as a zero-sum game with the players being the two camps. We first study optimal strategies of both camps in the fundamental setting where each camp aims to drive the average opinion of the population in its favor. We consider several settings of the problem, namely, when one of the camps has uncertain information about the values of the model parameters, when a camp aims at maximizing competitor's investment required to drive the average opinion in its favor, and when the influence of a camp on a node is a concave function of its investment on that node. We also study the problem under common coupled constraints on the combined investments by the camps and derive optimal strategies of the two camps, and hence show an interesting relation between the maxmin and minmax values. For a quantitative and illustrative study, we conduct simulations on real-world datasets and provide results and insights.


I. INTRODUCTION
Opinion dynamics is a natural phenomenon in a system of cognitive agents, and is a well-studied topic across several disciplines. It is highly relevant to applications such as elections, viral marketing, propagation of ideas or behaviors, etc. Opinion adoption by a population can be quantified in different ways based on the application at hand. We study two natural ways of quantification in this paper, namely, (a) the average opinion value (or equivalently the sum of individual opinion values), and (b) the expected number (or equivalently fraction) of individuals that are more likely to adopt our opinion than that of the competitor. Both of these ways can be motivated with a number of real-world examples.
In a fund collection scenario, for instance, the opinion value of an individual can be looked at as the amount of funds he or she is willing to contribute. Here our objective would be to gather maximum funds by convincing the population to contribute for a particular cause, with a competitor also attempting to convince the same for an opposing cause. This where a group of sensors or reporting agents are assigned the job of reporting their individual measurements of a particular parameter or event, and the resulting measurement would be obtained by averaging the individual values. If for some reason, two competitors aim to manipulate the resulting average (one perhaps for a good cause of avoiding panic, and another for elevating it), one would want to maximize the average value while the other would want to minimize it. In these examples, the opinion values can generally be unbounded.
On the other hand, there are scenarios which can be modeled aptly by bounded opinion values. For instance, in elections, a voter can vote at most once. Elections can be modeled by quantifying opinion adoption as the number of individuals preferring a camp's opinion over the competitor's. Here a particular camp would want as many individuals to adopt its opinion with high probability so that it gets as many votes so as to maximize its probability of winning. Product adoption in presence of two competing products is another example where this way of quantifying opinion adoption is well justified. In these examples, one could view the opinion value as a proxy for the probability with which an individual would vote for a camp or adopt its product, and hence a camp would want to maximize the expected number of individuals who would adopt its opinion.
It is well known that social networks play a prime role in determining the opinions, preferences, behaviors, etc. of the constituent individuals [1]. There have been efforts to develop models which could determine how the individuals update their opinions based on the opinions of their connections, and hence study the dynamics of opinions in the network [2]. With such an underlying model of opinion dynamics, a camp would aim at maximizing the adoption of its opinion in a social network, in presence of a competitor acting as a hostile camp. A camp could act on achieving this objective by strategically investing on selected individuals in a social network who could adopt its opinion. This investment could be in the form of money, free products or discounts, attention, convincing discussions, etc. Thus given a budget constraint, the strategy of a camp comprises of how much to invest on a given node in a social network, in presence of a competing camp who also would invest strategically, so as to maximize its opinion adoption.

A. Organization of the Paper
A primary goal of this work is to provide a framework for optimal investment strategies for competing camps in a arXiv:1706.09297v1 [cs.SI] 28 Jun 2017 social network, and propose and explore several aspects of the problem. The paper is organized as follows.
Section II We present the model we use in this paper and explain the underlying game and its variants that we study.
Section III We formulate the fundamental problem of maximizing opinion adoption in presence of competing camps and look at two interesting special cases, namely, overall budget constraint and that with bounded investment per node. We then investigate the maxmin and minmax properties. We look at the setting where one of the camps would need to make decision under uncertainty. We also look at the complementary problem where a camp acts as an adversary to the competing camp by aiming to maximize the latter's investment. We further investigate when the influence of a camp on a node is a concave function of its investment on that node.
Section IV We study the problem under common coupled constraints that the total investment by the good and bad camps on any given node cannot exceed a certain limit, which can be viewed as the total attention capacity of a node. We study the maxmin and minmax values in this setting and present some interesting implications.
Section V Using simulations, we illustrate our analytically derived results on real-world social networks and present more insights based on the observations.

B. Related Work
A principal part of opinion dynamics in a population is how each agent updates its opinion over time. One of the most well accepted and well studied approaches of updating an agent's opinion is based on imitation where each agent adopts the opinion of some of its neighbors with a certain probability. An example of imitation is the DeGroot model [3] where each agent updates its opinion using a weighted convex combination of its neighbors' opinions. The model developed by Friedkin and Johnsen [4], [5] considers that, in addition to its neighbors' opinions, an agent would give a certain weightage to its initial opinion while updating its opinion. A more sophisticated model based on the concept of 'bounded confidence' is proposed by Krause [6] allowing an agent to pay more attention to beliefs that do not differ too much from its own opinion.
Lorenz [7] surveys several modeling frameworks concerning continuous opinion dynamics under bounded confidence. Acemoglu and Ozdaglar [2] review several other models of opinion dynamics. Xia, Wang, and Xuan [8] give a multidisciplinary review of the field of opinion dynamics as a combination of the social processes, which are conventionally studied in social sciences, and the analytical and computational tools developed in mathematics, physics and complex system studies.
Ghaderi and Srikant [9] consider a setting where an agent iteratively updates its opinion as a myopic best response to the opinions of its own and its neighbors, and hence study how the equilibrium and convergence to it depend on the network structure, initial opinions of the agents, the location of stubborn agents and the extent of their stubbornness. Ben-Ameur, Bianchi, and Jakubowicz [10] analyze the convergence of some widespread gossip algorithms in the presence of stubborn agents and show that the network is driven to a state which exclusively depends on the stubborn agents. Jia et al. [11] propose an empirical model that combines the averaging rule of the DeGroot model and the reflected appraisal mechanism of the Friedkin model. They hence study the evolution of self-appraisal, social power, and interpersonal influences for a group of individuals who discuss and form opinions. Mirtabatabaei and Bullo [12] analyze a model proposed as a parallel to the bounded confidence model, in which an agent's influencing neighbors are those agents whose 'influence range' contain the agent's opinion (instead of those agents whose opinions are in the agent's 'confidence range').
Altafini [13] propose a model of opinion dynamics with not only attractive, but also repulsive couplings. Proskurnikov, Matveev, and Cao [14] extend this model to time-varying networks. Halu et al. [15] consider the case of two interacting social networks, and hence study the case of political elections using simulations.
Another popular model, the Voter model [16], [17], studies discrete opinions on a strongly connected directed graph. In this model, at each step, a randomly selected node chooses one of its neighbors uniformly at random including itself, and adopts that opinion as its own. Das, Gollapudi, and Munagala [18] show that existing and widely studied theoretical models of updating an agent's opinion, based on its neighbors' opinions, do not explain their experimental observations. The authors hence propose a new model, Biased Voter Model, as a combination of the DeGroot model and the Voter model. Sobehy et al. [19] propose strategies to win an election using a Mixed Integer Linear Programming approach and present their results on various families of networks.
Yildiz, Ozdaglar, and Acemoglu [20] study the problem of optimal placement of stubborn agents in the discrete binary opinions setting, so as to have maximum influence on the bias of the society, assuming the location of the competing stubborn agents to be given. Gionis, Terzi, and Tsaparas [21] study the problem of identifying a set of target individuals whose positive opinions about an information item will maximize the overall positive opinion for the item in the social network, from an algorithmic and experimental perspective.
The problem of maximizing information diffusion in social networks has been extensively studied in the literature [1], [22], [23]. The competitive setting has resulted in several game theoretic studies of this problem (for example, [24], [25], [26]). There have been preliminary studies addressing interaction among different informations, where the spread of one information influences the spread of the others (for example, [27], [28]).
There have been studies considering games with constraints. A notable study by Rosen [29] shows existence of equilibrium in a constrained game, and its uniqueness in a strictly concave game. Altman and Solan [30] study constrained games, where the strategy set available to a player depends on the choice of strategies made by other players. The authors show that, in constrained zero-sum games, the value of the game need not exist (that is, maxmin and minmax values need not be the same) and contrary to general functions, the maxmin value can be larger than the minmax.
The topic of decision under uncertainty has been of interest to the game theory and optimization communities. One possible way of analyzing decision under uncertainty is using robust optimization tools. Ben-Tal, El Ghaoui, and Nemirovski [31] present a thorough review of these tools.

II. MODEL
Consider a social network with N as its set of nodes and E as its set of weighted and directed edges. Two competing camps, say good and bad, aim at maximizing the adoption of their respective opinions in the social network. Consider a strict competition setting where the opinion value of the good camp is denoted by +1 and that of the bad camp by −1.
The examples mentioned earlier can be transformed into this setting with suitable mapping. We now present the parameters of the considered model of opinion dynamics, the update rule, and the underlying game and relevant settings that we study in this paper.

A. Parameters
Prior to the process of opinion dynamics, every node holds a bias in opinion which could have been formed owing to various factors such as similarities of the opinion with its fundamental opinion, concretized opinion owing to any information obtained from news and other sources, opinion dynamics in the past, etc. We denote this opinion bias of a node i by v 0 i and the weightage that the node attributes to it by w 0 ii . The good and bad camps attempt to directly influence the nodes so that their opinions are pulled towards +1 and −1 respectively. This direct influence depends on the investment or effort made by the camps, and also on how much a node weighs these opinions. For instance, a given amount of investment may have different influence on different nodes based on how much these nodes weigh the camps' recommendations. We denote the investment made by the good and bad camps on node i by x i and y i respectively, and the weightage that the node attributes to them by w ig and w ib respectively. Since the influence of good camp (holding the opinion of +1) on node i should be an increasing function of both x i and w ig , we assume the influence to be w ig x i for simplicity. Similarly, w ib y i is the influence of bad camp on node i. Also note that since the good and bad camps hold the opinions +1 and −1 respectively, the net influence owing to the direct recommendations from these camps is (w ig x i − w ib y i ).
Furthermore, both the camps have budget constraints stating that the good camp can invest a total amount of k g across all the nodes, while the bad camp can invest a total amount of k b .
The network effect is captured by how much a node is influenced by each of its friends or connections, that is, how much weightage is attributed by a node to the opinion of each of its connections. Let v j be the opinion held by node j and w ij be the weightage attributed by node i to the opinion of node j. Consistent with the DeGroot and Friedkin models, we assume the influence on node i owing to node j, to be w ij v j , thus the net influence owing to all of its connections being We denote the weightage attributed by node i to its own opinion v i , by w ii . It is to be noted that we do not make any assumption regarding the sign of the edge weights, that is, they could be negative as well. A negative edge weight w ij can be interpreted as some form of distrust that node i holds on node j, that is, i would be driven towards adopting an opinion that is opposite to that held or suggested by j.
Table I presents the required notation. Consistent with the standard opinion dynamics models, we have the condition on the influence weights on any node i that they sum to at maximum 1.
A standard assumption for guaranteeing convergence of the dynamics is that This natural assumption is actually well suited for our model where we generally would have non-zero weights allotted to the influence outside of the network, namely, the influence due to bias (w 0 ii ) and campaigning (w ig , w ib ).

B. Opinion Update Rule
Let the nodes update their opinions in discrete time steps starting with time step 0. Let v τ i be the opinion of node i at time step τ , and v 0 i = v 0 i . With the aforementioned factors into consideration, we consider that each node i updates its opinion at each step, using the update rule For any given node i, the static components are x i , y i , v 0 i (which are weighted by w ig , w ib , w 0 ii ), while the dynamic components are v j 's (weighted by w ij 's). The static components remain unchanged while the dynamic ones get updated in every time step.
Let w be the matrix consisting of the elements w ij for each pair (i, j) (note that w contains only the network weights and not w ig , w ib , w 0 ii ). Let v be the vector consisting of the opinions v i , v 0 and w 0 be the vectors consisting of the elements v 0 i and w 0 ii respectively, x and y be the vectors consisting of the investments x i and y i respectively, w g and w b be the vectors consisting of the weights w ig and w ib respectively. Let the operation • denote Hadamard product (elementwise product) of vectors, that is, Let Hadamard power be expressed as (a •p ) i = a p i . Assuming v τ to be the vector consisting of the opinions v τ i , the update rule given by (1) can be written in matrix form as We now analyze if the dynamics converges, and if yes, to what opinion values. Proposition 1. The dynamics defined by the update rule in (2) Proof. The recursion in (2) can be simplified as When τ → ∞, the procedure can be continued to arrive at Note that w is a strictly substochastic matrix, with the sum of each of its rows being strictly less than 1. Hence the spectral radius of w is less than 1, implying that which is a constant row vector, that is, the dynamics converge to this steady state of the opinion values.

C. Underlying Game and Relevant Settings
Owing to the strict competition setting, the problems discussed in this paper could be translated into the framework of constrained zero-sum games [32]. The players are the good and the bad camps, and their objective is to strategize about how much to invest on each node so as to maximize a certain objective function which indicates its utility. Owing to the budget constraint, the strategy set of the good camp consists of all investment vectors x, whose each element i is such that x i ≥ 0 and i x i ≤ k g . Similarly, the strategy set of the bad camp consists of all investment vectors y, whose each element i is such that y i ≥ 0 and i y i ≤ k b .
We first study the setting where the utility of the good camp is i v i and that of the bad camp is − i v i . Assuming the good camp plays first, the bad camp would want to minimize the value of i v i and would choose a strategy as a best response to that of the good camp accordingly. Knowing this, the good camp would want to maximize this minimum value.
For the case of bounded opinion values, the opinion value of a node can be viewed as a proxy for the opinion it would adopt, for example, who it would vote for in an election. Let v i be the opinion value of node i. When v i is bounded between −1 and +1, it could be transformed using a function f (·), into a probability that node i would vote for the good camp. So the expected number of votes that the good camp would get As a special simplified case where the value of v i is bounded between −1 and +1, we could consider Hence for the case of opinion values bounded between common limits, this linear transformation gives us the equivalence between optimizing over the expected number of votes and the sum of opinion values of the nodes.
In order for nodes to have opinion values bounded between −1 and +1, from Proposition 1, it is sufficient to have that the amount a camp can invest on any given node is at most 1 unit, that is, ∀i, x i ≤ 1 and y i ≤ 1. In several scenarios, this condition is apt owing to practical factors such as capacity of a node for attention from any camp. It could also be the case that the total attention capacity of any node is bounded, that is, ∀i, x i + y i ≤ 1. This leads us to study the game under these common coupled constraints (CCC), since with such constraints, the constraints of one camp are satisfied if and only if the constraints of the other camp are satisfied for every strategy profile.
Throughout the paper, we refer to a setting as 'unbounded' when the amount that can be invested per node is unbounded, while we call a setting 'bounded' when we have bounding constraints on investments on individual nodes, namely, We now start with the basic problem formulation, while increasing the complexity of the game and exploring its possible variants as we go along.

III. PROBLEM FORMULATION AND SOLUTION APPROACHES
Let us first concentrate on the problem of maximizing the opinion adoption which can be quantified as the sum of the individual opinion values.

A. Fundamental Problem of Maximizing Opinion Adoption
The problem of maximizing opinion adoption can be modeled as an optimization problem. In particular, owing to the perfect competition assumption, this problem can be modeled as the following maxmin problem. Here our objective is to determine our strategy (the values of x i such that they satisfy certain constraints) so that we maximize the average opinion value, knowing that the competitor would play its best response strategy (the values of y i which also need to satisfy certain constraints). Assuming linear constraints for setting the problem in the framework of linear program, we represent these constraints by Ax ≤ b and Cy ≤ d, respectively. As an example, if we have two nodes, and say the constraints on the investment for the good camp are 1/2 ≤ x 1 + x 2 ≤ 1 and Owing to x i and y i being investments, we have the natural constraints that x i , y i ≥ 0, ∀i. We can hence write the maxmin optimization problem in its general form as Instead of solving the above maxmin in its original form, we simplify it to a max-max problem so that it can solved as a single maximization problem. We do this by looking at the inner minimization problem and transforming it into its dual maximization problem. The inner term is Its dual problem can be written as Here the constraint (5) could be written as We have shown while proving Proposition 1 that (I − w) is invertible, which hence results in invertibility of (I − w) T or equivalently (I − w T ). So we have For satisfying Constraint (6), it is required that Expression (4) can be maximized when µ T d is minimized.
For further simplification, we consider the special case that we introduced in Section II.
1) The Special Case of Overall Budget Constraints: The special case in Section II that discusses overall budget constraints k g and k b for the good and bad camps respectively, corresponds to i x i ≤ k g and i y i ≤ k b . That is, we have In this simplifying case, we have C i = 1, ∀i and µ is a scalar. So the condition in (8) (4) is maximized when µ T d is minimized. In this special case, it corresponds to minimizing µk b , or simply minimizing µ since k b is a non-negative constant. This, together with the condition µ ≥ max i r i w ib , This can be done by ensuring that The values of y i 's that minimize this are Equations (11) and (9) lead to the following result.
Proposition 2. In Setting III-A1, it is optimal for the good and bad camps to invest their budgets in node i with maximum value of r i w ig and r i w ib respectively, subject to the value being positive.
Insight 1. The parameter r i could be viewed as the influence power of node i on the network, while w ig and w ib are respectively the influence powers of the good and bad camps on node i. So it is clear why these parameters factor into the result. Furthermore, the decisions of the players are independent which arises from the sum of steady state values of nodes as derived in (10). The linearity of the model and unconstrained investment on nodes allow both good and bad camps to exhaust their budgets by concentrating their entire investments on one node possessing the highest value of r i w ig or r i w ib respectively.
Recall that So if we have w ij ≥ 0 for all pairs of nodes (i, j), we will have that all elements of vector r are at least 1. That is, Insight 2. The strategies adopted by the camps are independent of the initial opinions. That is, the information regarding initial opinions is not required to solve the problem. This is owing to the fact that we try to optimize the sum of the opinion values without looking at the relative values (such as positivity) under a linear model.
It can be noted that r i can be viewed as a variant of Katz centrality [33]. Katz centrality of node i is defined as the i th element of vector I − αA T −1 − I 1 where A is the adjacency matrix and 0 < α < 1 |ρ| where ρ is the largest eigenvalue of A. In our case, A is replaced by the weighted adjacency matrix w, for which |ρ| < 1, and we have α = 1. The subtraction of the vector 1 is common for all nodes, thus its relative effect can be ignored.
We now present a result concerning a class of distribution of edge weights in a network, which includes the popular weighted cascade (WC) model.
Let us assume that r i = γ(α + d i ), where γ is some constant. If this satisfies the above equation, the uniqueness of r i ensures that it is the only solution. Hence the above would be equivalent to The above result implies that models which assign weights for all i such that w ig = w ib = w 0 ii = 1 α+di = w ij , ∀j ∈ N i , are suitable for the use of a random strategy, since the decision parameters for the two camps (r i w ig and r i w ib ) are the same for each node i. That is, in these models, a random strategy that exhausts the entire budget is optimal. These models include the popular weighted cascade model, which would assign the weights this way with α = 3.
2) The Case of Bounded Investment Per Node: This setting, as motivated earlier for applications such as elections and product adoption, includes additional constraints on the amount of investment per node by a camp, namely, x i , y i ≤ 1, ∀i.
From Equation (10), an optimal x can be obtained as follows. Let I riwig>0 = 1 if r i w ig > 0, and 0 otherwise. Let ω 1 , ω 2 , . . . , ω n be the ordering of nodes in decreasing values of r i w ig with any tie-breaking rule. So (10) is maximized with respect to x when . . , ω n Proposition 4. In Setting III-A2, it is optimal for the good camp to invest in nodes one at a time, subject to a maximum investment of 1 per node, in decreasing order of values of r i w ig until either the budget k g is exhausted or we reach a node with a non-positive value of r i w ig . The optimal strategy of the bad camp is analogous.

B. Maxmin versus Minmax Values
We now investigate the maxmin and minmax values in the unbounded and bounded investment cases. With no bounds on total budget per node, it can be easily seen that the maxmin and minmax values are the same, since the strategies of the good and bad camps are mutually independent. That is, The equality would stay even if there are mutually independent constraints on investment on a node by any given camp. That is, Note that we cannot compare the values obtained in (12) and (13) in general. For instance, if all i's have equal values of r i w ib and only one i has good value of r i w ig , then for k g > 1, the value in (12) would be greater than that in (13). This can be seen using Equation (10); the value of i r i (w 0 ii v 0 i −w ib y i ) would stay the same while the value of i r i w ig x i would be higher in (12) than in (13). On the other hand, if all i's have equal values of r i w ig and only one i has good value of r i w ib , then for k b > 1, the value in (13) would be greater than that in (12).

C. Decision under Uncertainty
We look at the setting which considers the possibility that the good camp, which plays first, may not have complete or exact information regarding the extrinsic weights, namely, w ig , w ib , w 0 ii . The bad camp, however, which plays second, has perfect information regarding the values of these parameters, and hence it is known that it would act optimally. Forecasting the optimal strategy of the bad camp, the good camp aims at choosing a robust strategy which would give it a good payoff even in the worst case.
Let U be a polytope defined by Eu ≤ f (that is, u ∈ U ). It could be seen as the uncertainty set, which in this case, is a convex set. The polytope would be based on the application at hand and could be deduced from observations, predictions, etc. We use the framework of robust optimization [31] for solving this problem.
For the purpose of this specific topic of decision under uncertainty, let us assume that all the elements of u are nonnegative. This is to ensure bounded values of the parameters. For instance, if we have a constraint in the linear program such as ii can be unbounded. So for this specific setting of uncertain parameters, we will assume w ig , w ib , w 0 ii ≥ 0, ∀i. Since the good camp aims to optimize in the worst case of parameter values, while the bad camp has knowledge of these values with certainty, the optimization problem is If max j r j w jb > 0, that is, the bad camp has at least one feasible node to invest on, then we have i r i w ib y i = k b max j r j w jb , else we have i r i w ib y i = 0. For arriving at a concise solution, let d be a dummy node such that r d w db = 0. So now we have i r i w ib y i = k b max j∈N ∪{d} r j w jb . The optimization problem thus is Note that there are in general n + 1 possibilities for max j∈N ∪{d} r j w jb . We could write a linear program for each possibility of i 0 = arg max j∈N ∪{d} r j w jb . For a fixed i 0 ∈ N ∪ {d}, the inner term is For the above problem to be feasible, the constraint set should be non-empty. Let N f be the subset of N ∪ {d} consisting of nodes i 0 such that the constraint set satisfying Eu ≤ f and ∀i : r i w ib ≤ r i0 w i0b is non-empty.
Its dual is the following Now, we need to find a common x for all possibilities of i 0 ∈ N f . So we have a constraint on the value of the dual, say ρ, namely, ρ ≤ −α T i0 f, ∀i 0 . We hence obtain a solution to the optimization problem by solving the following linear program.

D. The Effect of Concave Influence Function
The linear influence function (1) in the fundamental setting without any explicit bounds on investment per node leads to a solution which suggests concentrating the investment on a single node (Proposition 2). A concave influence function can be incorporated to account for diminishing influence of a camp with increasing investment on a node, which would advise against such concentrated investment. We now analytically show this claim by generalizing the linear influence function to a class of concave function. For the purpose of our analysis so as to arrive at more specific results, we consider functions of the form x 1/t as the influence when the investment is x. It is to be noted, however, that it can be extended to other concave functions since we use a common framework of convex optimization.
1) The Case of Unbounded Investment per Node: In Setting III-D1, for t > 1, it is optimal for the good and bad camps to invest in node i proportional to (r i w ig ) t t−1 and (r i w ib ) t t−1 , subject to the positivity of r i w ig and r i w ib , respectively.
A proof of Proposition 5 is provided in the supplemental file.
Remark 1 (A Note on Fairness). When we compare the results for lower and higher values of t, the investment made by the good camp has an exaggerated correlation with the value of r i w ig for lower values of t. In particular, the investment made is very skewed towards nodes with high values of r i w ig when t is very low, while it is proportional to r i w ig when t is very high. Note that t = 1 corresponds to the linear case in Setting III-A1 where the investment is extremely skewed with each camp investing its entire budget on only one node. If we define fairness to be how close the investment on a node i by a camp is, to being proportional to its worth to that camp (r i w ig or r i w ib ), we can see that a higher value of t results in a more fair model.
2) The Case of Bounded Investment Per Node: With the additional constraints x i ≤ 1 and y i ≤ 1, ∀i, the optimal investment strategies are given by Proposition 6. We provide its proof in the supplemental file.  (It can be shown thatγ exists and is unique). Then in Setting III-D2, it is optimal for the good camp to follow the following investment strategy If there does not exist aγ > 0 (because the number of nodes with r i w ig > 0 is less than k g ), we invest 1 on all nodes with r i w ig > 0 and 0 on all other nodes. The optimal strategy of the bad camp is analogous.
Note that for r i w ig ∈ (0, tγ], we can alternatively write , which would be between 0 and 1. So the nodes with positive values of r i w ig should be classified into two sets, that containing nodes with r i w ig ∈ (0, tγ] (for which x * i ∈ (0, 1]) and that containing nodes with r i w ig > tγ (x * i forcefully limited to 1). So we can effectively start with all nodes in the former set (meaning tγ ≥ max i r i w ig ) and then transfer nodes to the latter set as per descending values of r i w ig (as we reduce tγ), until we have two sets, one with ≤ 1 and the other with x * i forcefully limited to 1. Insight 3. The solution suggests that the optimal solution can be obtained using a trial-and-error iterative process. A camp could use the optimal strategy for the unbounded case suggested in Proposition 5. If for any i, we get x * i > 1, we assign x * i = 1 to node i with the highest value of r i w ig , and use Proposition 5 again by excluding node i and decrementing the available budget by 1. This process would be repeated until x * i ≤ 1, ∀i.

E. Maximizing Competitor's Investment
Another problem could be that of forcing the competitor to invest as much as possible in order to make the sum of values negative, while the competitor aims at minimizing this investment.
1) The Case of Unbounded Investment per Node: In Setting III-E1, it is optimal for the good camp to invest its budget in node i with maximum value of r i w ig , subject to it being positive. For the bad camp, it is optimal to invest the minimum amount in node i with maximum value of r i w ib , subject to its positivity, required to draw the average opinion value in its favor. (If there does not exist any node i with positive value of r i w ib , it is optimal for the bad camp to not invest at all). The investment made by the bad camp is A proof of Proposition 7 is provided in the supplemental file.
Then it is optimal for the good camp to follow the following investment strategy If there does not exist aγ > 0 (because i:riwig<0 (x i ) 2 < k g and no node with r i w ig > 0), we invest 0 on any node with r i w ig < 0 andx i on any node with r i w ig = 0.
This can be proved on similar lines as Proposition 6; here we obtain   and the optimal square root is determined by sgn (r i w ig ) (since a positive r i w ig would mean a higher optimal investment as opposed to a negative r i w ig ). Here, it is possible that a node i is invested on even if it has negative value of r i w ig , in order to have the investment close tox i .
2) The Case of Bounded Investment per Node: The optimal strategies of the camps can be easily obtained for this setting on similar lines as Proposition 4.
Proposition 8. In Setting III-E2, it is optimal for the good camp to invest in nodes one at a time, subject to a maximum investment of 1 per node, in decreasing order of values of r i w ig until either the budget k g is exhausted or we reach a node with a non-positive value of r i w ig . Say the so derived optimal investment on node i is x * i . The optimal strategy of the bad camp is to invest in nodes one at a time, subject to a maximum investment of 1 per node, in decreasing order of values of

IV. COMMON COUPLED CONSTRAINTS RELATING BOUNDS ON COMBINED INVESTMENT PER NODE
Consider a setting in which the combined or total investment on a node by both camps is bounded by a certain limit. Without loss of generality, assume that this combined investment is bounded by 1. This leads to the introduction of common coupled constraints (CCC), The problem of maximizing the opinion adoption now becomes The inner term is Its dual problem can be written as s.t. ∀i : As earlier, from (15), we have z i = (I − w T ) −1 1 i = r i . For satisfying Constraint (16), it is required that Now, to maximize the objective function (14), it is required that γ i should be as low as possible (knowing that 1−x i ≥ 0). So the above condition γ i ≥ r i w ib −α along with γ i ≥ 0 gives So we need to maximize the objective function with respect to γ i , x i , ∀i and α. For this purpose, let us define a set with respect to α, namely, So the objective function to be maximized is which is equal to Claim 1. It is sufficient to search the values of α ∈ {r j w jb } j:rj w jb >0 ∪ {0} to find an optimal solution.
Proof. Since α ≥ 0, we have α = r j w jb for any r j w jb < 0. Consider a range [r l w lb , r u w ub ] for a consecutive pair of values of r j w jb , which can be assumed to be distinct without loss of generality. We will determine the optimal value of α in this restricted range, for a given x. Case 1: If α = r l w lb : We have J α = {j : r j w jb ≥ r l w lb }. The value of the objective function (18) becomes Case 2: If α ∈ (r l w lb , r u w ub ]: we have optimal α = r l w lb . Note here that if r l w lb < 0 and r u w ub ≥ 0, we would have optimal α = 0. Case 3: If r l w lb = max i r i w ib , that is, when we are looking for α ≥ max i r i w ib . For α = max i r i w ib , we have J α = {arg max i r i w ib } and so the term j∈Jα (r j w jb − α)(1 − x j ) in (18) vanishes. For α > max i r i w ib , we have J α = {} and so the term j∈Jα (r j w jb −α)(1−x j ) in (18) vanishes in this case too. So the objective function to be maximized becomes for which the optimal α = max i r i w ib (the lowest value of α such that α ≥ max i r i w ib ). Now that we have established that the only possible values of optimal α are {r j w jb } j:rj w jb >0 ∪ {0}, we can assume optimal α = rĵwĵ b forĵ ∈ {j : r j w jb > 0} ∪ {d}, where the dummy node d is such that r d w db = 0.
So the objective function (18) can be rewritten as The term i r i w 0 ii v 0 i being a constant, and substituting α = rĵwĵ b , we have Now, for a givenĵ, the optimal x can be obtained as follows. Let βĵ i = (r i w ig + max{r i w ib − rĵwĵ b , 0}). Let I βĵ i >0 = 1 if βĵ i > 0, and 0 otherwise. Let ω 1 , ω 2 , . . . , ω n be the ordering of nodes in decreasing values of βĵ i with any tie-breaking rule. So the above term is maximized when Hence an optimal strategy of the good camp for a given j is to invest in nodes one at a time (subject to a maximum investment of 1 per node) in decreasing order of values of (r i w ig + max{r i w ib − rĵwĵ b , 0}) until either the budget k g is exhausted or we reach a node with a non-positive value of (r i w ig + max{r i w ib − rĵ, 0}). Hence let x * j = x * ji be an optimal x for a givenĵ.
The absolute optimal strategy of the good camp can now be computed by iterating over allĵ's ∈ {j : r j w jb > 0} ∪ {d} and taking the one that maximizes (from Expression (20)) Recall that Note that y i 's have the constraints that 0 ≤ y i ≤ 1 − x i . Since the bad camp aims to minimize the above term, the optimal strategy of the bad camp is to invest in nodes one at a time (subject to a maximum investment of 1 − x i per node) in decreasing order of values of r i w ib until either the budget k b is exhausted or we reach a node with a non-positive value of r i w ib .
Note that if k g is an integer, it is an optimal investment strategy of the good camp to invest one unit or not invest at all in a node. If k b is also an integer, an optimal investment strategy of the bad camp is also to invest one unit or not invest at all in a node. Insight 4. Assuming aĵ, the strategy of the good camp is to choose nodes with good values of (r i w ig + max{r i w ib − rĵwĵ b , 0}). That is, it chooses nodes with not only good values of r i w ig , but also good values of r i w ib . This is expected since the budget constraint per node allows the good camp (which plays first) to block those nodes on which the bad camp would have preferred to invest. Furthermore, there is an inherent preference ordering on nodes by the bad camp based on the values of r i w ib , given the investment of the good camp. Nodê j can be viewed as the node beyond which the bad camp does not invest on, as per this preference ordering. If the good camp does not invest on node i (that precedesĵ in the preference ordering of the bad camp), the bad camp would get a chance to invest on i rather than onĵ and so would benefit r i w ib −rĵwĵ b . Hence to account for the benefit of investing on node i for the good camp, there exists a term max{r i w ib − rĵwĵ b , 0}, in addition to the regular term r i w ig .
With the interpretation ofĵ as in Insight 4, Expression (21) can be understood as follows. The contribution of purely the good camp in The contribution of purely the bad camp due to its investment on a node i (that is, −r i w ib y i ) is −(1 − x * ji )r i w ib if i precedesĵ in the preference ordering, and 0 otherwise. So the total contribution of purely the bad camp in i v i over all nodes can be writ- where the extra term rĵwĵ b k b is to compensate for the k b amount of subtraction in the term r i w ib −rĵwĵ b over all nodes precedingĵ. This extra term can be easily visualized when k g and k b are integers, where an optimal x * ji is either 0 or 1. So combining the contributions from the good and bad camps and the bias component, we get For maximizing i v i , we could ignore the constant term i r i w 0 ii v 0 i and maximize the above expression over all possibilities ofĵ, hence leading to Expression (21).

Maxmin versus Minmax Values
Here, we compare the maxmin and minmax values of the game in the introductory setting with that in the common coupled constrained setting.
The introduction of the total budget constraints per node disturbs the equality between maxmin and minmax, as we show now. Let (x , y ) be an optimal maxmin strategy profile in (13). Adding the constraint 0 ≤ y ≤ 1 − x restricts the set of feasible strategies for the bad camp, and this set of feasible strategies and hence its optimal strategy now depends on x. So we have These two inequalities, along with (13), result in the following inequality, This surprising result, which is contrary to general functions (for which maxmin is less than or equal to maxmin), has also been derived in [30]. In our problem, this is a direct consequence of the first mover advantage, which restricts the strategy set of the second mover. In the maxmin case as analyzed earlier, the good camp invests in nodes with good values of (r i w ig + max{r i w ib − rĵwĵ b , 0}) (assuming aĵ). That is, it is likely to invest in nodes with good values of r i w ib which are the preferred investees of the bad camp. Owing to total investment limit per node, the bad camp may not be able to make the desired investment. It can be shown on similar lines that, in the minmax case where the bad camp plays first, it would play symmetrically opposite, thus limiting the ability of good camp to invest in nodes with good values of r i w ig .

V. SIMULATIONS AND RESULTS
Throughout this paper, we analytically derived the optimal investment strategies of competing camps in a social network for driving the opinion of the population in their favor. We hence presented closed-form expressions for most settings, and algorithms with polynomial running time for others. With the aim of determining implications of the analytically derived results on real-world networks and obtaining further insights, we conducted a simulation study on two popular network datasets. In this section, we present the setup and observed results, and provide insights behind them.

A. Simulation Setup
For conducting study on a real-world network dataset, we consider an academic collaboration network obtained from coauthorships in the "High Energy Physics -Theory" papers published on the e-print arXiv from 1991 to 2003. It contains 15,233 nodes and 31,376 links among them, and is popularly denoted as NetHEPT. This network exhibits many structural features of large-scale social networks and is widely used for experimental justifications, for example, in [22], [34], [35]. For the purpose of graphical illustration, we use the popular Zachary's Karate club dataset consisting of 34 nodes and 78 links among them [36].
We have shown in Proposition 3 that some of the popular models of distributing edge weight in a graph are suitable for random strategy, and hence may not be suited for simulations for making any useful observations. So alternatively, in order to transform an undirected unweighted network dataset into a weighted directed one for our simulations, we consider that for any node i, the tuple (w 0 ii , w ig , w ib ) is randomly generated such that ∀i : w 0 ii + w ig + w ib = 0.5, and if there is an edge between i and j. Figure 1 presents the values of the parameters used for experimentation on the Karate club dataset. The size and color saturation of a node i represent the value of the parameter mentioned in the corresponding caption (bigger size and higher saturation implies higher value). Unless otherwise specified, we consider k g = k b = 5 for this dataset. Also, unless otherwise specified, we consider v 0 i = 0, ∀i.

B. Simulation Results
Table II presents the quantitative results of our simulations on Karate club and NetHEPT datasets. For both the datasets, the overall opinion value is positive in the fundamental unbounded setting (III-A1). The results of the good camp doubling its budget can also be seen. The effect of bounded investment (Setting III-A2) can be seen; for these particular datasets, the maxmin value decreases implying that the value of r i w ig is probably concentrated on one node, while that of r i w ib is well distributed, thus giving the bad camp an advantage in bounded (and hence distributed) investment. Figure 3 (a) presents an illustration to the fundamental setting of unbounded investment per node for the Karate club dataset. Here, the good and bad camps invest their entire budget on nodes labeled 'g' and 'b' respectively. Figure 3 (b) illustrates the case with bounded investment per node (x i , y i ≤ 1, ∀i). The label 'c' means that that node is invested on by both the camps with 1 unit, while 'g' and 'b' mean that the node is invested on by the good and bad camp, respectively.
Considering the complementary setting of maximizing the competitor's (bad camp's) investment, we could see how much budget the bad camp required to draw the overall opinion in its favor. As expected from the results of previous setting, the investment required in the unbounded setting (III-E1) is more than the budget available in Setting III-A1. In the bounded setting (III-E2), for Karate club dataset, we can see that the bad camp could have driven the overall opinion in its favor without expending its entire budget. For NetHEPT dataset, as expected from the previous setting, the investment required by the bad camp in the bounded setting (III-E2) is less than that required in the unbounded setting (III-E1).
The results under the concave influence function setting are presented for both the unbounded (III-D1) and bounded (III-D2) cases for t = 2 and t = 10. Figure 2 shows the effect of the value of t in the concave influence function unbounded setting (III-D1) on the distribution of investment and the final opinion values for the Karate club dataset. In Figure 2    The nodes are labeled 'g/b/c' to signify if invested on by good/bad/both camps respectively. The sign of the opinion value of a node is signified by its shape and color (circle and blue for good, square and red for bad), while the absolute value of its opinion is signified by its size and color saturation.
seen that for t = 2, the investments are more skewed, while for t = 10, the investments by the good and bad camps are close to being proportional to the values of r i w ig and r i w ib , respectively. In Figure 2 (e-f), the shape and color of a node i represent its opinion (circle and blue implies positive, square and red implies negative), while the size and color saturation represent the magnitude of its opinion value.
For the unbounded case, in some scenarios (some values of budgets), there exist nodes for which either x i or y i or both exceed value 1. So for the bounded case, the camps are directed to have different investment strategies than in the unbounded case; the effects can be seen in Table II where the values are different in Settings III-D1 and III-D2 for the same values of budgets. In some scenarios, however, the investment strategies inadvertently assured x i , y i ≤ 1, ∀i even for the unbounded case; so the investment strategies remain the same in both settings if the budgets remain unchanged. A careful analysis of the values would indicate that the constraints x i , y i ≤ 1 are likely to come into picture for some nodes, for lower values of t and higher values of budgets. Lower values of t lead to skewed investment and so a higher likelihood of some nodes having investment more than 1 on them in the unbounded case. Similarly, higher values of budgets scale up the investments on the nodes, resulting in a higher likelihood of some nodes having investment more than 1 on them in the unbounded case. This can also be inferred from the analytically derived investment strategies of the camps. Figures 3 (c-d) illustrate the effect of common coupled constraints x i + y i ≤ 1, ∀i, for the Karate club dataset. The advantage of playing first is clearly visible from the overall opinion value as well as the distribution of opinion values in the figures. Specifically, the value is the highest in Figure 3 (c) with a healthy distribution of positive opinion values, followed by the value in Figure 3 (b), followed by that in Figure 3 (d) which is predominated by negative opinion values.
For studying the effects of decision under uncertainty as analyzed in Section III-C, we consider that the good camp (first mover) is uncertain about the parameters w ig and w ib up to a certain limit. In particular, there is a fractional uncertainty of l regarding the values of these parameters, while there is a fractional uncertainty of o regarding the values of the sums of these parameters over the entire network. l can be hence viewed as local uncertainty and o as global uncertainty. Let w ig andŵ ib be the underlying ground truth values for a node i (the actual values destined to be realized).
It is clear that the latter two constraints would come into picture only if o < l (this would usually be the case since, though there may be significant relative deviation for the individual parameters, the relative deviation of their sum is usually low owing to significant balancing of positive and negative deviations of the individual parameters). For different values of l and o , Figure 4 presents the maxmin values: (a) as computed by the good camp (first mover) as its worst case value using our robust optimization approach and (b) as realized based on the ground truth. We assume the ground truth values as depicted in Figure 1. It can be seen that for a large enough range of values of l and o , though the good camp computes the worst case maxmin value to be very low, the corresponding realized value is the same as when the good camp is certain about the parameter values. The uncertainty factor starts affecting the good camp only for very high values of l and o .

VI. CONCLUSION
We used a variant of DeGroot-Friedkin model for opinion dynamics and proposed a zero-sum game framework for optimal investment strategies for two competing camps in a social network. We arrived at closed form expressions and algorithms for a number of important settings. We studied the cases of bounded and unbounded investments per node in all settings that maintain the analytical tractability of the problem.
In our analysis, we arrived at a decision parameter analogous to the Katz centrality measure. We also showed that for some of the popular models of weighing edges similar to weighted cascade, a random strategy is indeed optimal. We derived a linear program for obtaining optimal strategy for a camp to whom the parameters values are uncertain, while playing against a camp who has exact knowledge about the parameter values. In our simulations, we observed that a camp is likely to get affected due to uncertainty only for considerable amount of uncertainty.
We studied the complementary problem where a camp aims to maximize its competitor's investment required to drive the average opinion value of the population in its favor, and saw that the optimal strategies fundamentally remain the same, albeit with different forms of the exact optimal strategies. We further looked at a setting where the influence of a camp on a node is a concave function of the amount of investment, and derived that a more concave function results in a more fair strategy, considering fairness to be investment on a node being proportional to its worth. We show all the results quantitatively as well as illustratively using simulations on network datasets.
We also studied the formulated game under common coupled constraints, where the constraints of one player are satisfied if and only if the constraints of the other player are satisfied for every strategy profile. We analytically derived the optimal strategies of both the camps, and deduced that the introduction of common coupled constraints results in maxmin value to be greater than or equal to the minmax value, an opposite inequality to the case of general functions. For the specific game under study, this can be perceived as a direct consequence of the first mover advantage.
This work has several interesting directions for future work, of which we mention a few. It would be interesting to study other models of opinion dynamics in literature with respect to optimal investment strategies of competing camps and investigate if it is possible to arrive at closed form expressions under them. The two camps setting can be extended to multiple camps where each camp would attempt to drive the opinion of the population towards its own, which would act as a generalization of the two opinion classes as was in our case, positive and negative. It would be interesting to extend the setting of common coupled constraints to account for more complex constraints, while maintaining the analytical tractability of the problem.
where I riwig>0 = 1 if r i w ig > 0, and 0 otherwise. Similarly, it can be shown that From the optimization problem, it can be directly seen that, if ∀i, r i w ig ≤ 0, then x * i = 0, ∀i. Similarly, if ∀i, r i w ib ≤ 0, then y * i = 0, ∀i.

PROOF OF PROPOSITION 6
Proof. This proof goes as an extension to the proof of Proposition 5, with the additional constraint ∀i : Equation ( and Equation (29) changes to The complementary slackness conditions for the additional constraints are ∀i : ξ i (X i − 1) = 0 Further note that the constraints X i ≥ 0 and X i ≤ 1 cannot both be tight, and so at least one of β i or ξ i must be 0. That is, When γ = 0, Equation (35) transforms into β i −ξ i +r i w ig = 0, ∀i. Now if r i w ig = 0, we must have β i − ξ i = 0 and hence β i = ξ i = 0 (from Equation (38)). It is further clear from the objective function that if r i w ig = 0, it is optimal to have X i = 0 and hence x * i = 0. If r i w ig < 0, we must have β i > 0 (since β i − ξ i + r i w ig = 0) and so X i = x * i = 0 (from Equation (28)). If r i w ig > 0, we must have ξ i > 0 and so X i = x * i = 1 (from Equation (37)). That is, when γ = 0, we invest an amount of 1 on all nodes i with positive values of r i w ig and 0 on all other nodes.
1 < k g even for the lowest value of γ > 0, we have J γ = {} and hence i:riwig>0 1 < k g . Here, the number of nodes with r i w ig > 0 is less than k g , meaning that the budget constraint is not tight and so γ = 0 (from Equation (27)). The investment is thus as per Equation (39).
The inner term of this optimization problem is It is clear that if i r i (w ig x i + w 0 ii v 0 i ) ≤ 0, it is optimal for the bad camp to have y i = 0, ∀i, that is, i y i = 0. So we need to only consider the case where i r i (w ig x i + w 0 ii v 0 i ) > 0. In this case, for the constraint i v i ≤ 0 to be satisfied, it is necessary that there exists a node j with positive value of r j w jb .
The dual problem of the above optimization problem can be written as From the dual constraints, we have π ≤ 1 maxj rj w jb (recall that max j r j w jb > 0 in this considered case). Since we aim to maximize the dual objective function, we have π = 1 maxj w jb rj The optimization problem now becomes The above expression thus gives the total investment made by the bad camp in the case where (k g max{max i r i w ig , 0} + i r i w 0 ii v 0 i ) > 0. Accounting for the case that it optimal for the bad camp to have y i = 0, ∀i when (k g max{max i r i w ig , 0} + i r i w 0 ii v 0 i ) ≤ 0, the total investment made by the bad camp is