Year: 2019

Abstract:
Over the last few years deep multi-agent reinforcement learning (DMARL) has become an increasingly active area of research with hundreds of papers submitted to top machine learning conferences every year. However, so far there have been few real world use cases that benefited from the progress in the field. We use DMARL to develop a flexible computational model of fake news on social networks in which agents act according to learned best response functions. We achieve this by extending an information aggregation game to allow for fake news and by representing agents as recurrent deep Q-networks (DQN). In the game, agents repeatedly guess whether a claim is true or false taking into account an informative private signal and observations of actions of their neighbors on the social network in the previous period. We incorporate fake news into the model by adding an adversarial agent, the attacker, that either provides biased private signals to, or takes over, a subset of agents. The attacker can follow either a hand-tuned or trained policy. Our model allows us to tackle questions that are analytically intractable in fully rational models, while ensuring that agents follow reasonable best response functions. Our results highlight the importance of awareness, privacy and social connectivity in curbing the adverse effects of fake news and open an entire new real world application area for DMARL.

heading: 1 INTRODUCTION
text: Problem setting At least since the 2016 US presidential election, fake news on social networks, aimed at manipulating the users’ perception of facts, has been recognized as a major issue in open societies. Yet, to date little is understood about how fake news spread on social networks, when a piece of fake news is effective in swaying public opinion and what interventions might be successful in mitigating the effect of fake news. Our lack of understanding of this important phenomenon is in large part due to the difficulty of modeling complex decision making processes on social networks. To tackle this issue, we extend a standard game of information aggregation on a social network, see Mossel et al. (2015), to accommodate fake news and solve this, analytically intractable, game using deep multi-agent reinforcement learning. This approach is flexible, computationally tractable, and allows us to work towards answering the questions raised above.
Related work Our work relates to two main strands of literature: (i) models of information aggregation in social networks and (ii) deep multi-agent reinforcement learning as a tool to solve games. The standard information aggregation game, outlined in Section 2.1, involves agents (repeatedly) guessing an unknown state of the world taking into account an informative private signal and observations of actions of their neighbors on the social network in the previous period. Note that this model involves no fake news. There are two main approaches to studying this game. In the rational agent approach, agents’ decision are best responses and the analysis focuses on the Nash equilibria of the game. In an important contribution, Mossel et al. (2015) show that under certain conditions on the social network, in the limit T → ∞ (number of periods) and n → ∞ (number of agents), agents will converge and will agree on the correct state of the world. This approach is not tractable for finite T and n and therefore does not allow, for example, the study of transient behavior. An alternative approach to studying the game of information aggregation is heuristic, see Golub & Sadler (2016) for a review of many important contributions. While heuristic approaches are more flexible to changes in the model setup and allow the study of transient behavior, agent strategies can be too
simplistic. For example, agents may treat repeated observations of a neighbor’s guess as conveying additional information, even when this is not the case (this occurs for example when this neighbor’s only information is his private signal). Furthermore, heuristic behavior does not adapt to changing circumstances and would therefore not allow us to study how agent behavior changes in the presence of fake news. Our deep multi-agent reinforcement learning approach combines both worlds. Our approach is flexible since it does not require the model to be analytically tractable and finds near-optimal policies through reinforcement learning.
Our work is also related to studies of competitive information diffusion, see Alon et al. (2010); Etesami & Başar (2014). However, while the literature on competitive information diffusion focuses on the strategic seeding of a pre-determined diffusion process, our work focuses on modeling the information diffusion process itself through the agents’ learned actions.
Deep multi-agent reinforcement learning (DMARL) has been applied to solve games of different structure. Policies or value functions are approximated by deep neural nets and trained via backpropagation. Some recent examples are Letcher et al. (2018); Foerster et al. (2018); Lerer & Peysakhovich (2017); Balduzzi et al. (2018). Often the focus is on methods that allow agents to converge on a particular, socially desirable policy, such as cooperation in social dilemmas without changing the payout structure. Since this is not an issue for most of our analyses, we make use of Independent Q-learning, see Tampuu et al. (2017). However, for some of our more advanced analyses, convergence does become an issue and applying more advanced DMARL methods provides a promising avenue of future research.
Contribution To the best of our knowledge, we are the first to develop a flexible computational model of fake news on social networks in which agents act according to learned best response functions. We achieve this by extending a standard information aggregation model to allow for fake news and by representing agents as recurrent deep Q-networks (DQN). We incorporate fake news into the model by adding an adversarial agent, the attacker, that either provides biased private signals to or takes over a subset of agents. We conduct a number of experiments to answer three main questions. (i) What determines the effectiveness of the attacker in reducing the accuracy of information aggregation? (ii) How well can agents learn adapt to the presence of an attacker? (iii) When attacker and agents learn simultaneously, how do policies evolve over time? Our results suggest three potential interventions to curb the effectiveness of fake news on social networks. First, “vaccinate” users of social networks by making them aware of the presence of fake news. Second, keep private information on social networks private so that attackers cannot target poorly informed or well connected users. Third, encourage the formation of “balanced” rather than clustered or fragmented social networks, so that information can “flow” effectively across the network.
Lastly, we contribute to the MARL literature by providing an important and concrete real-world application of methods that to date have found limited practical application.

heading: 2 BACKGROUND

heading: 2.1 AN INFORMATION AGGREGATION GAME ON A SOCIAL NETWORK
text: We consider a sequential game of information aggregation over T periods indexed by t = 1, . . . , T with a set of agents N , see Mossel et al. (2015); Golub & Sadler (2016) for details. Agents interact via a fixed, possibly directed, graph G(N,E), where E denotes the set of edges connecting the nodes N ; see Figure 1 for an illustration of the networks used in this paper. For concreteness, one can think of the agents as users of a social network, such as Twitter. A directed link from agent A to agent B would then imply that A follows B on Twitter.
Agents are presented with a claim that is either true or false. Again, for concreteness, one can think of the claim as a factual statement encountered in a piece of news that has been shared among the agents on the social network.1 True claims are denoted as θ = 1 and false claims as θ = 0. True and false claims occur with equal probability; that is, the unconditional probability of a claim being
1 We restrict our analysis to the case when claims are factual statements that can be objectively verified as true or false. Of course this prevents us from studying the dynamics of opinions. However, since we focus on the effect of fake news on the social network, restricting our analysis to factual statements is natural.
true or false is P(θ = 0) = P(θ = 1) = 1/2. This choice simplifies our analysis without affecting any of our qualitative results. Agents receive private signals si ∼ Fθ once at the beginning of an episode. In the baseline Fθ is such that private signals are always informative but noisy. In each period agents choose a binary action ait ∈ {0, 1}. Agents observe the actions of their neighbors on the graph from the previous period. At the end of the episode, agents are rewarded for actions that matched the veracity of the claim presented. For a given claim θ and sequence of actions {ait}, an agent’s total discounted reward is ri = ∑T t γ
t1{ait = θ}. Note that in this game, for t < T , it is not necessarily optimal to choose the action that matches the maximum of the posterior likelihood of θ. This is because an agent wants to prevent others from simply copying its action, since that reveals no information about the others’ private signal. Injecting noise into actions may therefore be beneficial. Despite these concerns, it can be shown that, under certain conditions on the network, in the limit T →∞ (number of periods) and n→∞ (number of agents), agents will converge and will agree on the correct θ, see Mossel et al. (2015).

heading: 2.2 MULTI-AGENT REINFORCEMENT LEARNING: INDEPENDENT Q-LEARNING
text: In principle, reinforcement learning (RL) can be used to learn the agents’ policy (or response functions) in any game. Many methods have been proposed to learn reasonable best response functions in various multi-agent reinforcement learning (MARL) settings, see Foerster et al. (2016); Letcher et al. (2018); Lerer & Peysakhovich (2017). In this paper, the agents’ response functions will be learned via independent Q-learning (IQL) and Q functions will be approximated by deep recurrent neural networks, see Tampuu et al. (2017); Foerster et al. (2016). We relegate a discussion of the RL and IQL framework to Appendix A.1.

heading: 3 METHODS
text: Graphs We consider three types of undirected graphs, see Figure 1 for an illustration. An instance of a Barabasi-Albert random graph with |N | = 10, see Barabási & Albert (1999); a clustered graph with three clusters (nc = 3) of fully connected nodes with four nodes each (sc = 4) such that |N | = 12; and a balanced graph (|N | = 12) that is obtained by randomly rewiring the clustered graph. Random rewiring involves repeatedly selecting two edges uniformly at random and swapping the terminal nodes of these edges. This preserves the degree sequence, i.e. the number of neighbors of each node, but removes the clusters such that the rewired graph is “balanced”. The BarabasiAlbert random graph is often used to model social networks and is therefore a natural choice for our application. The clustered graph is a stereotypical example of a social network which is comprised of cliques that are weakly connected. It thereby represents a more “fragmented” or “polarized” social network. The balanced graph removes these clusters from the graph while maintaining the degree sequence and can thus help isolate the effect of clusters on information aggregation.
Fake news We extend the model of information aggregation in order to study the effects of fake news on information aggregation. We introduce an adversary, the so called attacker, who wants to reduce the other agents’ total reward ∑ i ri. To disambiguate between the attacker and other agents, we often refer to these other agents as citizens. The attacker wants to persuade citizens to support false claims and dissuade them from supporting true claims. The attacker can achieve this in one of two ways. First, in the biased signal attack, he can distribute a fixed budget of bias β = ∑ i β i across a subset of the agents such that citizen i’s private signal is drawn from si ∼ Fθ(βi).2 We choose si ∼ N (θ + βi(1− 2θ), σ2). We set σ2 = 1 throughout. In this case the choice of {βi}i∈N is hand-tuned, i.e. set by the experimenter and not optimized. Second, in the agent takeover attack, he can directly take over an agent and act on his behalf. In this case the attacker optimizes his attack policy by IQL.
Learning to aggregate information We hold the network fixed across episodes. At the beginning of each episode θ and all private signals are drawn at random according to the distributions given above. For citizens we train a single DQN. In period t, the citizen observes the episode private signal si, his and the actions of his neighbors in the previous period {ajt−1}j∈Bi (Bi is the set of neighbors of agent i augmented by i) and the agent id i which identifies the agent’s network position. To maintain a constant length input vector, unobserved actions are encoded as −1. Thus, the corresponding DQN is a function Q : R× {−1, 0, 1}|N | ×N × {0, 1} 7→ R. In the agent takeover attack, the attacker is represented by a DQN. This DQN is distinct from the citizen DQN. At the beginning of each episode the attacker chooses a citizen uniformly at random from N and acts on his behalf. In period t, the attacker observes θ without noise, his and the actions of his neighbors in the previous period {ajt−1}j∈Bi and the agent id i. Thus, the corresponding DQN is a function Q : {0, 1}×{−1, 0, 1}|N |×N ×{0, 1} 7→ R. In the biased signal attack, the attacker is not represented by a DQN. Instead, the biases are hand-tuned. At the beginning of each episode the attacker chooses a set of citizens uniformly at random from N and delivers biased signals to them as outlined above.
Measuring information aggregation Intuitively, agents should be able learn to extract information from their private signals and their neighbors’ actions, such that at the end of an episode their expected reward (E[riT ]) should be significantly higher than at the beginning of an episode (E[ri0]). That is, agents should aggregate information over time. In the following, we give a formal definition of information aggregation for finite N and T that is useful in our case.
Definition 1 (Information aggregation). Let F = {si}i∈N denote the set of all realized signals in a given episode. Let θ̂ = argmaxθP[θ | F ] denote the maximum-a-posteriori estimator of θ given F . Then information is aggregated if for all i ∈ N , we have aiT = θ̂.
That is, under this definition information is aggregated if agents act as if they had seen all private signals. In reality, it is not reasonable to expect perfect information aggregation with actions learned via independent Q-learning. We therefore define the following measure of information aggregation.
Definition 2 (Accuracy of information aggregation). The accuracy of information aggregation at time step t is At = E[1{ait = θ}].
A useful benchmark to compare At to is of course E[1{θ̂ = θ}]. Another useful benchmark is E[1{θ̃ = θ}], where θ̃ = argmaxθP[θ | si] is the MAP estimator given only a single private signal. AT can never exceed E[1{θ̂ = θ}] and A1 can never exceed E[1{θ̃ = θ}] and of course E[1{θ̂ = θ}] > E[1{θ̃ = θ}] provided |N | > 1. Once we have trained the agents via Q-learning it is easy to estimate At by evaluating a set of batches of games B and computing Ât = 1/|B|1/|N | ∑ b∈B,i∈N 1{ait,b = θ}, where ait,b is the action taken by agent i in batch b ∈ B.
In the following we will simply refer to Ât as the accuracy.
2 Biased signals can be thought of as targeted ads to users of the social network. Indeed, it been shown that fake news attacks have taken exactly this form, see Chiou & Tucker (2018). A fixed bias budget corresponds roughly to an attacker with a fixed budget for targeted social media ads.
Heuristic benchmark We compare the accuracy of the DQN against the DeGroot heuristic, DeGroot (1974). Under this heuristic information aggregation rule at t = 0, we set ai0 = θ̃(s
i). In each subsequent period actions are set to at = Uat−1, where at is the vector of actions taken by citizens and U = D−1(I +M), where I is the identity matrix, M is the graph adjacency matrix and D is a diagonal matrix with entries Dii being the number of neighbors of node i plus one (i.e. a self loop). Information is therefore aggregated through repeated averaging of past actions.

heading: 4 EXPERIMENTS
text: Our objective is to improve our understanding of the propagation of fake news in social networks and discover potential interventions to curb its effectiveness. This goal translates into three main questions. (i) What determines the effectiveness of the attacker in reducing the accuracy of information aggregation? In particular, how does the network structure and the choice of the attacked agent affect attack effectiveness? (ii) How well can agents learn adapt to the presence of an attacker? (iii) When attacker and citizen learn simultaneously (agent takeover attack), how do policies change over time? To study these questions we set up a series of training and testing scenarios.
Training scenarios: We implement the following training scenarios. (i) Baseline: We train citizens in the absence of any attack, i.e. all citizens receive unbiased signals and no citizen is taken over by the attacker. We train baseline models for the Barabasi-Albert, clustered and balanced graphs. This scenario establishes a benchmark for the ability of IQL agents to learn to aggregate information in the absence of attack. (ii) Biased signal attack: We train citizens in the presence of a biased signal attack where a single, randomly chosen citizen receives a biased signal (β = 3). We train this model for the Barabasi-Albert graph only. This scenario allows us to evaluate whether citizens can learn to adapt to the presence of a biased signal attack and thereby mitigate the adverse effects of the attack. (iii) Agent takeover attack: We train citizens and attacker simultaneously. We train this model for the Barabasi-Albert graph only. This scenario allows us to understand the effectiveness of attack as it co-evolves with the citizen’s effort to mitigate the attacker’s ability to manipulate citizens. Note that IQL may not converge to stable policies in such a game. It is interesting however, to understand the action dynamics that emerge under IQL as they can help us understand the coevolution of fake news attack and defense in real social networks. (iv) Random action attack: We train citizens in the presence of an attacker that selects a single citizen uniformly at random and then, in each period, picks an action uniformly at random. We train this model for the Barabasi-Albert graph only. This scenario serves as a benchmark for the agent takeover attack. The accuracy under the random action attack should exceed the accuracy under the agent takeover attack.
Testing scenarios: Given the models obtained for these different training scenarios we conduct a number of testing scenarios. First, for each attack training scenario, we evaluate accuracy, as defined above, both in the presence of the corresponding attack (as trained) and in the absence of any attack. For the baseline scenario we consider two testing scenarios in addition to testing in the absence of any attack (as trained). First, we evaluate accuracy in the baseline model for the Barabasi-Albert graph in the presence of a biased signal attack with a single attacked agent and β = 3. Second, we evaluate accuracy in the baseline model for the clustered and balanced graphs under two biased signal attack scenarios. In the focused scenario, a single, randomly chosen citizen receives a biased signal with βi = 3. In the spread scenario, two, randomly chosen citizens receive biased signals with βi = 1.5 each.

heading: 5 RESULTS
text: Our experiments yield four main results, which we will discuss in turn.
Baseline information aggregation: In the absence of attack, citizens learn to aggregate information with an accuracy close to the optimal benchmarks E[1{θ̂ = θ}] as t → T and E[1{θ̃ = θ}] for t = 0. Our method’s accuracy also substantially outperforms the accuracy achieved by DeGroot information aggregation heuristic. This highlights the appropriateness of IQL to solve the standard information aggregation game. In the presence of an attack, information aggregation is severely disrupted. These results are illustrated in Figure 2 (A).
Determinants of effectiveness of attack: Our experiments allow us to study the following determinants of attack effectiveness: network position of the attacked agent, signal strength of the attacked agent, network structure (clustered vs balanced) and distribution of bias across agents (focus vs spread). Let us consider each in turn.
To study the effect of network position, we compute the accuracy in the final time step (t = T ) conditional on the network position of the attacked agent when evaluating the baseline model under the biased signal attack in the Barabasi-Albert network. Denote this conditional accuracy by ÂT (i), where i is the attacked agent. Let ÂT denote the baseline accuracy in the absence of attack. We then define the decline in accuracy relative to baseline as ∆A(i) = ÂT − ÂT (i). We plot ∆A(i) as a function of i in Figure 2 (C). It is clear that there is substantial heterogeneity in the attack effectiveness. As the tight correlation between ∆A(i) and the degree of i in Figure 2 (C) shows, the heterogeneity in ∆A(i) arises from the network structure which implicitly gives more influence to those nodes with more neighbors (higher degree). If an attacker is able to target the biased signal to such highly connected nodes, his attack will be more effective.
Next we study the effect of the signal strength of attacked agent. Again, we restrict ourselves to evaluating the baseline model under the biased signal attack in the Barabasi-Albert network. A natural measure of a signal’s strength, or informativeness, is the absolute value of the log likelihood ratio of the two states of θ conditional on the signal. Let f(θ | s) denote the posterior distribution over θ given the signal s. Then, the signal strength is given by L(s) = | log[f(θ = 1 | s)/f(θ = 0 | s)]|. Let Lk denote the kth decile of the empirical distribution of signal strengths for a particular experiment. We define the conditional accuracy Â(Lk) as the average accuracy in the final time step conditional on the attacked agent’s signal strength lying in [Lk, Lk+1]. ∆A(Lk) is defined analogously to ∆A(i). We plot ∆A(Lk) against Lk in Figure 2 (D). There exists a strong negative correlation between attack effectiveness as measured by ∆A(Lk) and the attacked agent’s signal strength. This is intuitive. If an agent has received a strong private signal in support of some value of θ, a larger bias will be required to convince him of the contrary. Thus, if an attacker can target the biased signal to agents with weak private signals, his attack will be more effective.
Lastly, we consider the case of clustered vs rewired/balanced networks and spread our vs focused attacks. This analysis is done evaluating the baseline model under the biased signal attack in the clustered and balanced networks. A number of results are worth noting. As can be seen in Figure 2 (E), for each scenario (baseline/no attack, focus and spread attacks) accuracy in the balanced network exceeds accuracy in the clustered network. This suggests that information aggregation is more effective in the balanced network. This is intuitive as the balanced networks has a shorter maximum path length between any two nodes thereby allowing information to “propagate” faster between nodes. In Figure 2 (E), we can also see that variation in the accuracy between training runs with different seeds (each run corresponds to one marker for a particular scenario) is smaller for the balanced network. This suggests that in the balanced network learning good policies is an easier task than in the clustered network. We can also see from Figure 2 (E) that spread attacks are more effective both in the clustered and balanced networks.
To summarize, targeting highly connected agents in the network or those with weak private signals, makes biased signal attacks more effective. Clustered networks are more susceptible to attack than balanced networks and spread attacks are more effective than focused ones.
Adapting to attacks: So far we have evaluated models trained in the absence of attack. However, one can expect that users of social networks will adapt over time to the presence of fake news. We therefore investigate to what extent citizens can learn to mitigate the effect of an attacker. For this purpose we train citizens in the presence of a biased signal attacker, a random attacker and an agent takeover attacker for the Barabasi-Albert network. We then evaluate the accuracy of each of these models in the absence of an attack and in the presence of the attack under which they were trained. We summarize our results in Table 1.
Let us first contrast the accuracy of the baseline model (trained without attack) under a biased signal attacker with the accuracy of a model trained under this attack scenario. When trained in the presence of an attacker the test accuracy under attack increases from 0.78 to 0.84 relative to the baseline. This can also be seen in Figure 2 (B). We conclude that agents can indeed learn to adapt to the presence of fake news. However, this adaptation comes at a cost. When trained in the presence of an attacker the test accuracy without attack decreases from 0.92 to 0.88 relative to the baseline. We conjecture that this is because agents learn to trust strong private signals less and are less likely to follow their neighbors’ actions. A similar picture can be seen for the random attacker and the agent takeover attacker. To summarize, agents can learn to adapt to the presence of an attacker which reduces attack effectiveness. However, adaptation comes at a cost. If trained under attack and tested in the absence of attack, accuracy is lower than in the baseline which is trained without attack.
Dynamics of attack and defense: We now take a closer look at the agent takeover attack. Recall that in this scenario, a separate DQN agent is trained to minimize the total reward of the citizens by acting on behalf of a randomly chosen agent. This attacker knows θ and must then choose an action to convince the citizens of the opposite. Simply choosing the opposite action would be a naive strategy that is likely to be detected quickly by the citizens as they learn in the presence of this strategy. Always choosing a random action in every period, as the random attacker does, is also
quite easily detectable by the citizens. This intuition is confirmed by results reported in Table 1 and Figure 3.
From Table 1 we see that the trained attacker clearly “outperforms” (i.e. more effective attack) the random action attack benchmark. The bottom panel of Figure 3 (B) shows the accuracy of the attacker in the first time step as a simple summary statistic of its strategy. The accuracy is either 0.5 indicating that the attacker “randomizes” or 0 indicating that the attacker “lies”. While Q-learning only allows for deterministic policies the attacker can learn to lie if the attacked agent is in one partition of N and be truthful if the attacked agent is in another partition. Since the attacked agent is chosen at random, this strategy amounts to a randomized attack strategy.
Note further, that neither the attacker’s nor the citizens’ policy converges as can been seen in the highly variable reward and unstable TD-error in Figure 3 (A) . Indeed, as can be seen in the bottom panel of Figure 3 (B) , the attacker’s policy fluctuates between randomization and lying between episodes. These fluctuations can be seen as irregular “cycles” in the policy space of the attacker and the citizen. One such cycle in Figure 3 (B) shows the attacker switching to a lying strategy, while the citizens lose “trust” in their private signal (they nearly ignore it in the first time step). The result of these two events coming together can lead to substantial, temporary declines in accuracy.
We don’t claim that these dynamics are accurate representations of the learning dynamics between users of social networks and pushers of fake news. However, we consider the failure of IQL to converge and the irregular dynamics that emerge more of a feature than a bug. Indeed these dynamics suggest two interesting, qualitative take aways. First, attackers and citizens are unlikely to converge to stable policies in real life. We should expect a continuing cycle of adaptation with periods of a high prevalence of fake news followed by periods of low prevalence. Second, the co-evolution of attackers and citizens can have unexpected effects on the citizens’ ability to aggregate information in the social network. As we observe in Figure 3 (B) , the presence of neighbors that do not act in accordance with their private signals (i.e. the attacked agents) can lead citizens to learn to mistrust their own private signals.

heading: 6 CONCLUSION AND DISCUSSION
text: The deliberate manipulation of the public’s perception of facts via fake news, in particular on social networks, has become a growing concern for policy makers and technology companies alike. Despite its importance, little is understood about the spread of fake news on social networks. This is in large part due to the technical difficulties involved in studying complex decision making behavior on social networks. We seek to close this gap by developing the (to the best of our knowledge) first framework for the study fake news on social networks that is theoretically grounded yet com-
putationally tractable and flexible. We achieve this by (i) extending a standard game of information aggregation to accommodate fake news and (ii) applying state-of-the-art deep multi-agent reinforcement learning to solve the game.
Our findings suggest a number of interventions that could contribute to making fake news attacks less effective. First, if agents are made aware of the presence of fake news, they can learn to adapt and mitigate its effect. However, this adaptation is likely to be accompanied by evolving attack strategies, so any adaptation will not be lead to permanent mitigation. In addition, the adaptation is likely to harm information aggregation in the absence of fake news. Second, keeping private information on social networks private, can make it harder for attackers to condition their attacks on network position and general informedness (as the real world analogue of signal strength). This should reduce attack effectiveness. Third, encouraging well balanced social networks can improve information aggregation in general and make fake news attacks less effective in particular.
Our current approach has two main shortcomings. First, it does not scale well to larger populations of agents since it requires the entire social network to be trained simultaneously. One way forward is to train agents in sub-graphs feeding them an embedding of the graph, see for example Gilmer et al. (2017), and then composing larger graphs at test time. The second shortcoming is the use of IQL in the agent takeover attack scenario. While the lack of convergence leads to interesting qualitative insights, MARL methods that encourage convergence of policies would be desirable here, at least as benchmarks. One possible way to achieve this would be to apply stable opponent shaping to citizen and attacker, see Letcher et al. (2018).

heading: A APPENDIX
text: A.1 MULTI-AGENT REINFORCEMENT LEARNING
Single-Agent Reinforcement Learning Consider an MDP specified by the following tuple: 〈S,A, P, r, γ〉. In the fully observable case the environment has an observed true state, s ∈ S, and at each time step the agent chooses an action a ∈ A, which induces a probabilistic transition to the next state via the state transition function P (s′|s, a) : S ×A× S → [0, 1]. The reward function assigns an instantaneous reward to each state-action pair, r(s, a) : S × A → R, and γ ∈ [0, 1) is a discount factor. In single agent RL the task of the agent is to maximize the discounted reward per episode, Rt =∑∞ l=0 γ
lrt+l. The agent’s policy, π(a|s) : S×A→ [0, 1], induces a state-action-value function (Qfunction), Qπ(st, at) = Est+1:∞,at+1:∞ [Rt|st, at]. Q-learning aims to estimate the optimal actionvalue function, Q∗(x, a) = maxπ Qπ(x, a), via an estimated Q-function, Q(s, a).
Training is carried out by collecting samples from the environment in order to obtain MonteCarlo-Estimates of the expected return. For any sampled transition, the current estimate, Q(s, a), is compared to a greedy one-step lookahead using the Bellman optimality operator, T Q(s, a) = Es′ [r + γmaxa′ Q(s′, a′)]. We can use samples to evaluate the Bellman update:
Q(s, a)k+1 = Q(s, a)k + α ( r + γmax
a′ Q(s′, a′)k −Q(s, a)k ) Here k is the iteration number, α is the learning rate and r + γmaxa′ Q(s′, a′)k − Q(s, a)k is commonly referred to as the temporal-difference or TD-error. In the tabular case the Q-values for each state-action pair are maintained separately and the Bellman update is a contraction mapping. As a consequence at convergence this iterative process results in the optimal Q-function, Q(s, a)∞ = Q∗(s, a). Finally, Q∗(s, a) trivially defines the optimal policy π∗(x, a) = δ(arg maxa′ Q∗(x, a′)− a), where δ(·) is the Dirac-delta function. In contrast to the tabular case, DQN (Mnih et al., 2015) uses a neural network parametrized by a large number of weights, φ, to represent the Q-function.
In order to reduce the variance of the update process the average square of the TD-error across a large number of transitions (the batch) is used as the DQN-loss. Using backpropagation the parameters of the neural network are updated to minimize the magnitude of the DQN error L(φ) = ∑b j=1[(y DQN j −Q(xj , aj ;φ))2]. Here y DQN j = uj + γmaxa′j Q(x ′ j , a ′ j ;φ −), is the target
function and φ− is the target network, which contains a stale copy of the parameters. This target network helps to stabilize the training.
So far we have assumed that the agent has access to the Markov state, s, of the system. In a partially observable settings we augment the MDP with an observation space, Z, and observation function O(s). In particular the observation z ∈ Z is produced by the observation function O(s) : S → Z. We further define an action-observation history τ ∈ T ≡ (Z × U)∗, which is used to condition a stochastic policy π(a|τ) : T × U → [0, 1]. In recurrent deep RL (Hausknecht & Stone, 2015), this can be achieved using recurrent neural networks, such as LSTM (Hochreiter & Schmidhuber, 1997) or GRU (Cho et al., 2014) which we use here.
Independent Q-Learning In multi-agent reinforcement learning, each agent i ∈ N receives a private observation O(x, i), where i is the agent index and O is the observation function. The agents also receive individual reward rit and take actions a i t. Furthermore the state-transition conditions on the joined action a ∈ A ≡ An. In independent Q-learning each agent further estimates a Q-function Qi(τ i, ai), treating the other agents and their policies as part of a non-stationary environment. A combination DQN with IQL commonly uses parameter-sharing across agents combined with an agents specific index in the observation function in order to accelerate learning while still allowing for specialization of policies.
A.2 IMPLEMENTATION DETAILS
Our code has been submitted. Our neural network architecture implements the IQL architecture in Foerster et al. (2016).

Review summaries:
This paper proposes a model under which to study social networks under attacks attempting to propagate misinformation. It proposes a theoretical model based on assumptions on what kinds of graphs are common in social media and what kinds of attacks take place. While this could be interesting, the work presented falls short of what it promises, i.e. to develop a practical model of fake news on social networks,  because many of the assumptions made about the phenomena under study are unrealistic. In more detail