key: cord-0509067-7ncqlrb3 authors: Bouveret, Geraldine; Mandel, Antoine title: Prophylaxis of Epidemic Spreading with Transient Dynamics date: 2020-07-15 journal: nan DOI: nan sha: 76c1a979cb4e8ad734b5664393aa8ef4b36e8cdf doc_id: 509067 cord_uid: 7ncqlrb3 We investigate the containment of epidemic spreading in networks from a normative point of view. We consider a susceptible/infected model in which agents can invest in order to reduce the contagiousness of network links. In this setting, we study the relationships between social efficiency, individual behaviours and network structure. First, we exhibit an upper bound on the Price of Anarchy and prove that the level of inefficiency can scale up to linearly with the number of agents. Second, we prove that policies of uniform reduction of interactions satisfy some optimality conditions in a vast range of networks. In setting where no central authority can enforce such stringent policies, we consider as a type of second-best policy the shift from a local to a global game by allowing agents to subsidise investments in contagiousness reduction in the global rather than in the local network. We then characterise the scope for Pareto improvement opened by such policies through a notion of Price of Autarky, measuring the ratio between social welfare at a global and a local equilibrium. Overall, our results show that individual behaviours can be extremely inefficient in the face of epidemic propagation but that policy can take advantage of the network structure to design efficient containment policies. game corresponds to a more complex setting where agents are usually organisations (regions, countries) that are involved in a scheme that allows one agent to subsidise, directly or indirectly, the investment of other agents in the reduction of contagiousness. Our main results characterise the relationships between social efficiency, individual behaviours and network structure. First, we derive an upper bound on the Price of Anarchy (PoA). We show that in worst cases the level of inefficiency can scale up to linearly with the number of agents. This strongly calls for public policy interventions. In this respect, we study the optimality of a policy of uniform reduction of interactions, akin to social distancing measures put in place during the COVID-19 pandemic, in a wide range of networks. This latter result provides normative foundations for the social distancing policies implemented during the COVID-19 pandemic. The implementation of such policies nevertheless requires the existence of an authority with sufficient legitimacy to implement such coercive measures. It can be thus implemented in a domestic context but is much harder to implement at the global scale, unless all agents/countries have individual incentives to do so. If this is not the case, we regard the shift from a local to a global game as a type of second-best policy. In the latter game, agents can subsidise investments towards contagiousness diminution in the global rather than in the local network. The scope for Pareto improvement generated by such policies is then characterised through a notion of Price of Autarky (PoK), which assesses the ratio between social welfare at a global and a local equilibrium. We derive a lower bound on this PoK as a function of the network structure and thus give sufficient conditions under which a shift to the global game actually induces a Pareto improvement. Overall, the results derived not only underline the possible extreme inefficiency of individual behaviours to limit epidemic propagation, but also the potential for policies to benefit from the network structure to design efficient containment policies. The remaining of this paper is organised as follows. Section 2 reviews the related literature. Section 3 introduces epidemic dynamics as well as our behavioural model of the containment of epidemic spreading. Section 4 provides our main results on the relationship between individual behaviours, social efficiency and network structure. Section 5 introduces the notion of PoK and applies it to our setting. Section 6 concludes. An appendix with the proofs of the main results is provided. The paper builds on the very large literature on the optimal design and defense of networks (see, e.g., Bravard et al. (2017) ) and on epidemic spreading in networks. The latter literature has been extensively reviewed in Pastor-Satorras et al. (2015) and generally combines an epidemiological model with a diffusion model. The epidemiological model describes the characteristics of the disease via the set of states each agent can assume, e.g., susceptible/infected (SI), susceptible/infected/susceptible (SIS), susceptible/infected/removed (SIR), and the probabilities of transition between these. The diffusion model considers that the set of agents is embedded in a network structure through which the disease spreads in a stochastic manner. Overall, the micro-level epidemic diffusion model is a continuous-time Markov chain model whose state space corresponds to the complete epidemiological status of the population. This state space is however too large for the full model to be computationally or analytically tractable. A large strand of the literature has thus focused on the development of good approximations of the dynamics, see, e.g., Chakrabarti et al. (2008) ; Draief et al. (2006) ; Ganesh et al. (2005) ; Mei et al. (2017) ; Prakash et al. (2012) ; Ruhi et al. (2016) ; Van Mieghem et al. (2009) ; Wang et al. (2003) . To the best of our knowledge, the most precise approximation of the dynamics in the SIS/SIR setting is the N´intertwined model of Van Mieghem et al. (2009) . This model uses one (mean-field) approximation in the exact SIS model to convert the exact model into a set of N non-linear differential equations. This transformation allows analytic computations that remain impossible with other more precise SIS models and renders the model relevant for any arbitrary graph. The N´intertwined model upper bounds the exact model for finite networks of size N and its accuracy improves with N . Van Mieghem and Omic (2008) have extended the model to the heterogeneous case where the infection and curing rates depend on the node. Later, Van Mieghem (2013) has analytically derived the decay rate of SIS epidemics on a complete graph, while Van Mieghem (2014) has proposed an exact Markovian SIS and SIR epidemics on networks together with an upper bound for the epidemic threshold. Most of this literature has focused on SIS/SIR models in which there exists an epidemic threshold above which the disease spreads exponentially. A key concern has thus been the approximation of the epidemic threshold as a function of the characteristics of the network, and subsequently the determination of immunisation policies that allow to reach the below-the-threshold regime (see, e.g., Chen et al. (2016 Chen et al. ( , 2015 ; Holme et al. (2002) ; Preciado et al. (2013 Preciado et al. ( , 2014 ; Saha et al. (2015) ; Schneider et al. (2011); Van Mieghem et al. (2011)) . A handful of studies has adopted a normative approach to the issue using a gametheoretic setting. Omic et al. (2009) consider a N´intertwined SIS epidemic model, in which agents can invest in their curing rate. They prove the existence of a Nash Equilibrium and derive its characteristics as a function of the network structure. They provide a measure of social efficiency through the PoA. They also investigate two types of policies to reduce contagiousness. The first one plays with the influence of the relative prices of protection while the second one relies on the enforcement of an upper bound on infection probabilities. Hayel et al. (2014) have also analysed decentralised optimal protection strategies in a SIS epidemic model. However, in their case, the curing and infection rates are fixed and each node can either invest in an antivirus to be fully protected or invest in a recovery software once infected. They show that the game is a potential one, expressed the pure Nash Equilibrium for a single community/fullymesh network in a closed form, and establish the existence and uniqueness of a mixed Nash Equilibrium. They also provide a characterisation of the PoA. Finally, Goyal and Vigier (2015) examine, in a two-period model, the trade-off faced by individuals between reducing interaction and buying protection, and its impacts on infection rates. They analyse the equilibrium levels of interaction and protection as well as the infection rate of the population, and show the existence of a unique equilibrium. They highlight that individuals investing in protection are more willing to interact than those who do not invest, and establish the non-monotonic effects of changes in the contagiousness of a disease. Yet, most of these contributions focus on situations where (i) some form of vaccine or treatment is available and (ii) dynamics are of the SIS/SIR type. Our attention is rather on situations where there is no known cure to the epidemic and where the objective is to delay its propagation through investments in the reduction of contagiousness. Therefore, we focus on the transient dynamics of the SI model. In this respect, we build on the recent contribution of Lee et al. (2019) who provide an analytical framework to represent the transient dynamics of the SI epidemic dynamics on an arbitrary network. In particular, they derive a tight approximation in closed-form of the solution to the SI epidemic dynamics over all time t. The latter overcomes the shortfalls of the existing linearised approximation (see Canright and Engø-Monsen (2006) ; Mei et al. (2017); Newman (2010) ) by means of a thorough mathematical transformation of the system governing the SI dynamics. Lee et al. (2019) have also derived vaccination policies to mitigate the risks of potential attacks or minimise the consequences of an existing epidemic spread with a limited number of available patches or vaccines over the network. From an economic perspective, our contribution relates to the growing literature on the private provision of public goods on network. This literature mostly focuses on the relationship between the network structure and the individual provision of public goods. It generally considers a fixed network and that the public good/effort provision of an agent only affects its neighbors. In particular, Allouch (2015) shows the existence of a Nash Equilibrium in this setting under very general conditions. Bramoullé and Kranton (2007) prove, in a more specific setting, that Nash Equilibria generically have a specialised structure in which some individuals contribute and others free ride. A more recent contribution by Kinateder and Merlino (2017) extends the models of private provision of public goods to a setting with an endogenous network formation process. Yet, the network is formed in view of the benefits provided by the public good/effort offered by connections. Hence, although related, our focus differs from this strand of literature as, in our setting, the process of link formation per se is the source of external effects, and effects propagate throughout the network. Another related contribution is Elliott and Golub (2019) , which provides a more conceptual view on the relationship between the network structure and public goods. It focuses on the network of external effects per se and characterises efficient cooperation/bargaining institutions in this framework. Our model could be subsumed into an extended version of their model which considers multi-dimensional actions. However, their framework abstracts away from the process underlying the interactions, which is one of our key focus. We consider N the set of natural numbers and N P N. The notation M N (resp. M N pR`q) denotes the set of N´dimensional square matrices with coefficients in R (resp. R`). For a given M P M N , we write pM q i,j or m i,j , 1 ď i, j ď N , to refer to its element in the i th´r ow and j th´c olumn. Moreover, for any M P M N , ||M || denotes its Frobenius norm and for any matrix M and K in M NˆMN , we write M ď K if m i,j ď k i,j , @i, j " 1, ..., N . Additionally, the matrix I (resp. O) stands for the N´dimensional square identity (resp. null) matrix. Similarly, for a N´dimensional column vector u P R N , u i , 1 ď i ď N, refers to its element in the i th´r ow while u J denotes its transpose and ||u|| its Euclidean norm. Additionally, for any u and v in R NˆRN , we let u ĺ v if u i ď v i , @i " 1, ..., N . We define similarly u ă v . For a function f : R Þ Ñ R and a vector u P R N , f puq denotes the N´dimensional column vector with f pu i q, 1 ď i ď N, as entries. Moreover, 1 is the N´dimensional column vector with one as entries. We also consider diagpuq, the N´dimensional square diagonal matrix with u i , 1 ď i ď N, as diagonal entries. Additionally, for the i th´v ector of the canonical basis of We define S N (resp. S N pR`q) as the subset of elements of M N (resp. M N pR`q) that are symmetric. We observe that S N is a real vector-space of dimension N pN`1q{2 and we consider the basis formed by the matrices pB ti,ju q 1ďiďjďN such that b ti,ju i,j " b ti,ju j,i " 1 and b ti,ju k, " 0 for tk, u " ti, ju. Accordingly, given a matrix D P S N , we let d tj,ku :" d j,k`dk,j . Moreover, given U Ď S N , a differentiable function φ : U Ñ R, andD P U, we denote by Bφ Bd ti,ju pDq the partial derivative in the direction of B ti,ju , that is where Bφ Bd i,j pDq and Bφ Bd j,i pDq denote the partial derivatives in the directions induced by the canonical basis of M N . Finally, for a set B, we note CardpBq its cardinal and pBq c the complementary set. We consider a finite set of agents, N " t1, 2, ..., N u, N ě 2, connected through a weighted and undirected network. The set of links is given by E Ď tti, ju | i, j P N u and their weights by the weighted adjacency matrix A P S N pR`q. In particular, for all i P E, a ii " 0. The agents face the risk of shifting from a good/susceptible state to a bad/infected state. This transition occurs in continuous time through an epidemic process over the network. At time zero, a subset of agents idiosyncratically shifts to the infected state. Following this initial shock, infected agents contaminate their neighbours in the network with a probability that is proportional to the weight of the corresponding link. Infected agents remain so permanently and cannot revert to the susceptible state. As intimated in Section 2, this model is known as the SI model in the epidemiological literature (see, e.g., Pastor-Satorras et al. (2015)). It provides an accurate description of epidemic dynamics at short time scale and/or when no vaccine or treatment is available against the epidemic. We consider a socio-economic setting in which strategic agents can invest in the network in order to reduce contagion rates. We are concerned with the characterisation of the equilibrium behaviour in this context, its relation to social efficiency, and the potential impacts of policy on these features. Such setting captures the behaviour of countries facing the global propagation of an epidemic as well as that of individuals facing its local propagation. It can also be applied to other socio-economic context such as the propagation of computer viruses (see, e.g., Pastor-Satorras and Vespignani (2001)) or financial distress (see, e.g., Battiston et al. (2012) ). In order to formally define the model, we first provide a detailed description of the epidemic dynamics and its approximation (see Section 3.3) and then introduce a representation of agents' prophylactic behaviours (see Section 3.4). Formally, an exact model of the dynamics of epidemic spreading in the SI framework is given by a continuous-time Markov chain pXptqq tě0 with state space X :" t0, 1u N . A state Xptq P X is defined by the combination of states of all the N agents at time t and is thus described by the set of susceptible agents ti P N | X i ptq " 0u and the set of infected agents ti P N | X i ptq " 1u. The key specificity of the dynamics of the Markov chain pXptqq tě0 is the stochastic rate of contagion for a susceptible node i P N , characterising its transition probability as follows where β is a unit contagion rate, a i,j , i, j P N , is the contagiousness of the network link ti, ju, and P denotes the probability on the underlying probability space. Equation (3.1) characterises completely the dynamics, as infected nodes remain so permanently. It highlights the role of the network in the contagion process and the possible heterogeneous contagiousness of different network links. In this respect, we make the following assumption about the network structure throughout the paper. Assumption 3.3.1. The adjacency matrix A P S N pR`q is irreducible and aperiodic. The irreducibility assumption amounts to considering that every agent faces a risk of contagion as soon as at least one agent in the network is infected. Indeed, the network is then necessarily connected and the asymptotic behaviour of the Markov chain is trivial: there is an unstable steady state where none of the agent is infected and a unique stable steady state where all agents are contaminated 1 . In the following, we shall actually consider that agents are concerned by the time at which they are likely to be infected rather than by their asymptotic infection status. Accordingly, we are concerned with the transient behaviour of the Markov chain. However, as intimated above, the infection rate defined by the right-hand side of Equation (3.1) is a random variable, making the process doubly stochastic. The random nature of the infection rate could then be offset by conditioning with respect to all the possible combinations of the neighbouring states, i.e. X j ptq, j ‰ i. Yet, such conditioning of every node would lead to a Markov chain with 2 N states, i.e. with a number of states increasing exponentially with the number of nodes, and thus being neither analytically nor computationally tractable. Therefore, the conventional practice in epidemiological modelling is to consider a mean-field approximation of the infection rate. In particular, the Nintertwined model of Van Mieghem et al. (2009) considers the average behaviour, i.e. the expectation, over states for the infection rate. Therefrom, the latter model derives an approximate dynamics of the probability for an agent i P N to be in the infected state at time t given by x i ptq :" PrX i ptq " 1s 2 . More precisely, using the fact that PrX i ptq " 1s`PrX i ptq " 0s " 1 and the total law of probability, one gets from Equa-1 Stability must be understood in the sense that, for any initial non-null probability distribution, the limiting distribution of the Markov chain has full support on the full contamination state. 2 Let Ti :" inftt ě 0 : Xiptq " 1u valued in R`. We observe that for t ě 0, xiptq " PrTi ď ts. tion (3.1) that for all i P N , 2) thus provides a deterministic approximation of the dynamics of the contagion probability that takes into account the full network structure. It nevertheless disregards the positive correlation between the infection status of neighbouring nodes. This implies that Equation (3.2) over-estimates the probability of contagion (see Van Mieghem et al. (2009)). Remark 3.1. Alternative mean-field approximations used in the literature are generally much coarser that the N -intertwined model considered here. Two common approaches are (i) to average over agents and focus on the (approximate) dynamics of the average probability of contagion or (ii) to average over agents with equal degree and focus on the (approximate) dynamics of the average probability of contagion for an agent of a given degree (see Pastor-Satorras et al. (2015) for an extensive review). The non-linear Equation (3.2) does not have an analytical solution. A common approach in the literature, used in particular to analyse the outbreak of an epidemic, is to assume x i ptq small enough to discard the factor p1´x i ptqq and thus focus on the following linear equation However, this approximation grows exponentially towards`8, whereas it is assumed to approximate a probability. In a recent contribution, Lee et al. (2019) provide a much better approximation of the solution of Equation (3.2). More precisely, they define for all i P N and t P R`, y i ptq :"´logp1´x i ptqq, and observe thatx :" rx 1 , ...,x N s J is a solution of the system defined by Equation (3.2) with initial condition x p0q :" rx 1 p0q, ..., x N p0qs J ": x 0 , with at least one non-null element to avoid triviality, if and only ifȳ :" rȳ 1 , ...,ȳ N s J is a solution of the system of equations defined for all i P N by with the corresponding initial condition. They then show that a tight upper bound to the solution of the system defined by Equation (3.4) when x p0q " x 0 ă 1 is provided byy and accordingly thatx ptq :" 1´exp p´y ptqq is a tight upper bound to the solutionx of the system defined by Equation (3.2) with initial condition x p0q " x 0 in the sense that one has (see Lee et al. (2019, Theorem 5 .1 and Corollary 5.2)) • lim tÑ`8 ||x ptq´x ptq|| " 0, • for any t ě 0,x ptq ĺx ptq ĺx ptq wherex :" rx 1 , ...,x N s J is the solution of the system defined by Equation (3.3) with initial condition x p0q " x 0 . Hence,x provides an approximation of the probability of contagion that is asymptotically exact and more accurate than the standard linear approximation, even at short time scale. From now on, we shall consider that agents base their assessment of the dynamics of contagion on the approximated contagion probabilitiesx associated to a given and fixed initial condition x p0q " x 0 ă 1, having at least one non-null element. In this sense, they make decisions on the basis of approximate information. This approach provides a consistent representation of the decision-making situation of actual agents which ought to base their decisions on similar approximations. In this respect, we recall that in our SI setting, all agents eventually become infected. Thus, agents cannot base their decisions on their asymptotic infection status. Rather, they shall aim at delaying the growth rate of the epidemic. This is notably the strategy pursued by most countries during the recent COVID-19 pandemic. More precisely, we consider that agents consider a target datet, which can be interpreted as the planning horizon or the expected date of availability of a treatment, and aim at minimising the probability of contagion up to that date. We further assume, for sake of analytical tractability, that they have a logarithmic utility of the form wherex i ptq is the approximate contagion probability given by Equation (3.5) and δ i ě 0 is a subjective measure of the value of avoided contagion, or equivalently of the cost of contagion, for the agent i. One should note that the utility is non-positive and equal to a benchmark of zero if and only if there is no risk of contagion. In our setting, x 0 , β, andt being fixed, Equation (3.5) implies that the contagion probability is completely determined by the adjacency matrix A. The utility of agent i P N can thus be expressed directly as where the constant term lnp1´x 0 q`diagp1´x 0 q´1x 0 has been discarded to simplify the notations. Equation (3.6) highlights that, for a given admissible initial probability of contagion x 0 , the only lever that agents can use to reduce their contagion probability is the decrease of the contagiousness of the network, i.e. the decrease of the value of the coefficients of the adjacency matrix A. This is exactly the strategy put in place during the COVID-19 pandemic, at the local scale through social distancing measures, and at the global scale through travel restrictions and border shutdowns (see Colizza et al. (2006) for an analysis of the role of the global transport network in epidemic propagation). Formally, we consider a strategic game in which each agent can invest in the reduction of contagiousness of network links. We distinguish two alternative settings to account for potential constraints on agents' actions: • In the global game, we assume that each agent can invest in the reduction of contagiousness of every network link. Therefore, the set of admissible strategy profiles is given by SpAq :" tpD i q iPN P pS N pR`qq N : A´ř iPN D i ě 0u. • In the local game, we assume that each agent can only invest in the links through which it is connected. Therefore, the set of admissible strategy profiles is given by Local games correspond to a setting where agents are individuals that limit their social interactions through individual and costly measures. On the other hand, global games apply to a more involved setting where agents are organisations (regions, countries) that have the ability to subsidise the investment of other agents in the reduction of contagiousness, either directly or indirectly. Remark 3.2. Both SpAq and KpAq are non-empty, convex and compact sets. The payoff function is defined in a similar fashion in both settings: • First, a strategy profile pD i q iPN turns the adjacency matrix into A´ř iPN D i and thus yields to agent i P N a utility where D´i :" pD j q jPN , j‰i is the strategy profile of all agents but i. • Second, we consider that agents face a linear cost for their investment in the reduction of contagion. More precisely, one has for all i P N , where ρ ą 0 is the cost parameter. • Overall, the payoff of agent i P N given a strategy profile pD i q iPN is given by A few remarks are in order about the characteristics of the game. First, agents' strategy sets are constrained by the choices of other players. Namely, given a strategy profile for the other players D´i P pS N pR`qq N´1 , the set of admissible strategies for player i is S i pA, D´iq :" tD i P S N pR`q | pD i , D´iq P SpAqu (resp. K i pA, D´iq :" tD i P S N pR`q | pD i , D´iq P KpAqu) in the global (resp. local) game. Although, it is not the most standard, this setting is comprehensively analysed in the literature (see, e.g., Rosen (1965) ). Second, linear cost is a natural assumption in our framework. Indeed, the marginal cost paid to decrease the contagiousness of a link should not depend on the identity of the player investing. Third, the payoff function is always non-positive as it is the combination of both a utility and a cost that are always non-positive. Finally, for larget and homogeneous initial contagion probabilities, the utility can be approximated through the eigenvector centrality of the contagion network, as detailed in the following lemma. Definition 3.1 (pαq-Homogeneous Game). A game is pαq-homogeneous if it involves an homogeneous initial probability of contagion, i.e. such that for all i P N , x 0 i " α for some α P p0, 1q. Lemma 3.1. Consider an pαq-Homogeneous Game, and let D P SpAq be such that A´ř iPN D i is irreducible and aperiodic. Let then µ 1 denote the Perron-Frobenius eigenvalue of pA´ř iPN D i q, |µ 1´µ2 | the spectral gap and v the normalised eigenvector associated to µ 1 , corresponding to the eigenvector centrality of the network. One has Remark 3.3. As A is irreducible and aperiodic, the condition ř iPN d i j,k ă a j,k for all j, k P N such that a j,k ą 0, is sufficient for getting the irreducibility and aperiodicity of A´ř iPN D i . We now state some properties on the marginal utility and the payoff function (recall the notations for the partial derivatives of a symmetric matrix in Section 3.1). Lemma 3.2. For every i P N , for any strategy profile pD i , D´iq P SpAq, and for all k, P N , and the marginal utility is non-negative. Moreover, the map Π i p¨, D´iq is concave on S i pA, D´iq. From the previous lemma derives the following result relating the marginal utility of every agent to the utility itself, when the initial probability of infection is constant among agents. Lemma 3.3. Consider an pαq-Homogeneous Game, and let M Ď N . For every i P N , and for any strategy profile pD i , D´iq P SpAq, (3.8) In the following, unless otherwise specified, we consider as implicitly given the utility weights δ :" rδ 1 , ..., δ N s J , the time-horizont, the unit contagion rate β, the initial contagion matrix A, the initial contagion probabilities x 0 , and the investment cost ρ. We then define the "local game" Lpδ, A, β,t, x 0 , ρq as the game with strategy profiles in KpAq and payoff function Π and the "global game" Gpδ, A, β,t, x 0 , ρq as the one with strategy profiles in SpAq and payoff function Π. In this setting, a Nash Equilibrium is defined as follows. Definition 3.2 (Nash Equilibrium). • An admissible set of strategiesĎ :" pĎ i q iPN P SpAq is a Nash Equilibrium for the global game if • An admissible set of strategiesD :" pD i q iPN P KpAq is a Nash Equilibrium for the local game if The existence of a Nash Equilibrium follows from standard arguments. Theorem 3.1. There exists a Nash Equilibrium in both the local and global games. Remark 3.4. In our setting, equilibrium is in general not unique as there might be indeterminacy on the identity of the players/neighbours which ought to invest in reducing the contagion of a link (see the discussions in Section 4.1 below). The key concern, in the remaining of this paper, is the study of the efficiency of Nash Equilibrium. As commonly done in N -agent games, and in particular in network games, we define as Social Optimum, the outcome that maximises the equally-weighted sum of individual utilities. ). An admissible set of strategiesD :" pD i q iPN P SpAq is a Social Optimum ifD Note that ř iPN Π i pD i , D´iq only depends on the value of ř iPN D i . First, this implies that the notion of Social Optimum is the same in the local and global game. Indeed, it is straightforward to check that for every pD i q iPN P SpAq, there exists pD i q iPN P KpAq such that ř iPND i " ř iPN D i . Second, given a matrix D P S N pR`q such that D ď A, we shall letΠ pDq :" wherev i : D Þ Ñ v i pA´Dq, and, with a slight abuse of notation, state thatD is a Social Optimum if it is such thatΠpDq is maximal over DpAq :" tD P S N pR`q : D ď Au. The existence of a Social Optimum directly follows from the continuity ofΠ and the compactness of DpAq . Theorem 3.2. There exists a Social Optimum in both the local and global games. We end this section with two lemmas that are the counterparts of Lemma 3.2-3.3 above for the Social Optimum D P DpAq and whose proofs are a straightforward adaptation of the proofs of the latter lemmas. Lemma 3.4. For every i P N , for any Social Optimum D P DpAq, and for all k, P N , Moreover, the mapv i p¨q is concave on DpAq. Lemma 3.5. Consider an pαq-Homogeneous Game, and let M Ď N . For every i P N , and for any Social Optimum D P DpAq, In this section, we provide a characterisation of equilibrium behaviours as a function of the network structure. We then measure, through the PoA, potential inefficiencies induced by individual behaviours, giving insight on how to restore optimality in the local game. Let i P N . Individual prophylactic efforts are characterised by the investment in contagion reduction D i P S N pR`q that the individual performs in the links it has access to (SpAq or KpAq). As emphasised above, the network of contagion is assumed undirected and thus investments in the link tk, u P E induce an equal reduction of the contagion weights a k, and a ,k . More precisely, the marginal impact of the investment made by player i is characterised by Equation (3.7) above. This equation highlights the bilateral impact of agents' investments on contagion from to k on the one hand and from k to on the other hand. The impact on agent i of reduced contagiousness through d i k, (from to k) depends on (i) the utility weight δ i , (ii) the initial contagiousness of node , x 0 , and (iii) the connectivity between k and i measured, for D : Hence, the connectivity from k to i, C i,k pA, D, β,t, x 0 q, depends on the initial structure of the contagion network A, the strategic investments in the reduction of contagiousness D, the unit contagion rate β, the time-horizont, and the initial contagion probabilities x 0 . It corresponds to the discounted sum of paths from k to i where each path is assigned a weight corresponding to the probability that it propagates a genuine contagion sequence. The weight of each link across the path is thus obtained as the product of (i) the probability that the link propagates the contagion, which is measured through the corresponding coefficient pA´ř jPN D j q, and (ii) the probability that the end node is not initially infected, which is measured through the corresponding coefficient of diagp1´x 0 q. Overall, the marginal impact of agents' actions on contagiousness depends on the characteristics of the disease, measured through the initial contagion probability, and on the structure of the contagion network modified by the agents' investments. Equation (3.7) offers a differential characterisation of Nash Equilibria in both the local and global games, as reported in the following two propositions. Proposition 4.1. A strategy profileD P KpAq is a Nash Equilibrium of the local game Lpδ, A, β,t, x 0 , ρq if and only if for all tk, u P E, the following two conditions hold: (1) One of the following alternative holds: (a) ρ ă max iPtk, u δ i`Ci,k pA,D, β,t, x 0 qx 0 `C i, pA,D, β,t, x 0 qx 0 k˘a ndd k tk, u`d tk, u " a tk, u , (b) ρ ą max iPtk, u δ i`Ci,k pA,D, β,t, x 0 qx 0 `C i, pA,D, β,t, x 0 qx 0 k˘a ndd k tk, u "d tk, u " 0, (c) ρ " max iPtk, u δ i`Ci,k pA,D, β,t, x 0 qx 0 `C i, pA,D, β,t, x 0 qx 0 k˘a ndd k tk, u`d tk, u P r0, a tk, u s. (2) For any i P N , one hasd i tk, u ą 0 only if Proposition 4.2. A strategy profileĎ P SpAq is a Nash Equilibrium of the global game Gpδ, A, β,t, x 0 , ρq if and only if for all tk, u P E, the following two conditions hold: (1) One of the following alternative holds: tk, u P r0, a tk, u s. (2) For any i P N , one hasď i tk, u ą 0 only if The difference between Proposition 4.1 and 4.2 stems from the fact that different sets of agents can invest in a given link: the agents at the nodes corresponding to that link in the local case and all agents in the global case. Otherwise, their interpretation is similar. If the investment cost is large with respect to the marginal utility of players at equilibrium, there is no investment in the link. If the investment cost is smaller than the marginal utility of at least one player at equilibrium, there is full investment in the link, i.e. it is completely suppressed. Finally, there is the "interior" case in which only the agents with the largest marginal utility invest in the link. They do so up to the point where their individual marginal utility equals the investment cost. The following definition summarises the different characterisations of equilibria. • A local (resp. global) Full Investment Equilibrium is an equilibrium that satisfies, for all tk, u P E, case (a) of Proposition 4.1 (resp. 4.2). • A local (resp. global) No Investment Equilibrium is an equilibrium that satisfies, for all tk, u P E, case (b) of Proposition 4.1 (resp. 4.2). • A local (resp. global) Interior Equilibrium is an equilibrium that satisfies, for all tk, u P E, case (c) of Proposition 4.1 (resp. 4.2). • A local (resp. global) Homogeneous Interior Equilibrium is a special case of local (resp. global) Interior Equilibrium where, for each tk, u P E, the marginal utilities of agents k, (resp. all agents) are equal. We observe that in the case of a Full Investment Equilibrium or an Interior Equilibrium, there can be an indeterminacy on the identities of the agents that invest. Namely, let E G tk, u pDq :" ti P N | δ i pC i,k pA, D, β,t, x 0 qx 0 `C i, pA, D, β,t, x 0 qx 0 k q ě ρu, be the set of players susceptible to invest in the link tk, u P E at an equilibrium D of the global game and E L tk, u pDq :" ti P tk, u | δ i pC i,k pA, D, β,t, x 0 qx 0 `C i, pA, D, β,t, x 0 qx 0 k q ě ρu, be the set of players susceptible to invest in the link tk, u P E at an equilibrium D of the local game. Proposition 4.3 below, resulting from Proposition 4.1-4.2, highlights a form of substitutability of investments that arises at equilibrium. Proposition 4.3. Let D be an equilibrium of the global game Gpδ, A, β,t, x 0 , ρq (resp. local game Lpδ, A, β,t, x 0 , ρq). Assume thatD P SpAq (resp.D P KpAq) is such that for all tk, u P E, one has: ThenD is an equilibrium of the global (resp. local) game. Hence, each player that has a large enough marginal utility is willing to invest in a link up to the equilibrium level independently of the actions of other players. This leads to indeterminacy on the allocation of investments (and thus of the related costs) among players that have a large enough marginal utility. Remark 4.1. Consider the game Gpδ, A, β,t, x 0 , ρq (resp. Lpδ, A, β,t, x 0 , ρqq and its equilibrium D. We observe that, whenever for some i, j, k, P N , Moreover, Proposition 4.1-4.3 imply that Full Investment Equilibria and Interior Equilibria have a notable property: they induce equilibria in each network that is more strongly connected than the equilibrium network (i.e. with a weight on each link higher than the one of the corresponding link in the equilibrium network). This property is formally stated in the following proposition. Proposition 4.4. Let D be a Full Investment Equilibrium or an Interior Equilibrium of the global game Gpδ, A, β,t, x 0 , ρq (resp. local game Lpδ, A, β,t, x 0 , ρq). Then for allà ě A´ř iPN D i , any strategy profileD P SpÃq (resp.D P KpÃq) such that ř iPND i :" ř iPN D i`ôA is a Full Investment Equilibrium or an Interior Equilibrium of Gpδ,Ã, β,t, x 0 , ρq (resp. Lpδ,Ã, β,t, x 0 , ρq). Finally, both equilibria induce the same equilibrium network. We end this section discussing a salient example of existence of global equilibria in local strategies, that of a symmetric game and an almost fully-connected network. • A game is pα, δq-symmetric if for all i P N , δ i " δ for some δ ą 0 and x 0 i " α for some α P p0, 1q. • A network is complete if for all k, P N , k ‰ , a k, ą 0. In particular, the network is paq-complete if for all k, P N , k ‰ , a k, " a for some a ą 0. Example 4.1. Consider an pα, δq-Symmetric Game and an paq-Complete Network. The game is then symmetric and, using the non-emptiness, convexity and compactness properties of the strategy space as well as the continuity and concavity properties of the payoff, there exists a symmetric equilibrium in both the local and global games (see Cheng et al. (2004, Theorem 3) ). We shall show that both equilibria coincide and that, for ρ in an appropriate range, they are interior. Indeed, letĎ P SpAq, be a symmetric equilibrium of the global game. According to Equation (3.7), one has for all i, k, P N , where χphq :" 1`ř kě1 u k {k!, with pu k q kPNzt0u satisfying the following recursive system 3 As χphq ą χphq´expp´hq, it follows from Equation (4.1) that for all distinct elements i, k, P N , one has Using Proposition 4.2, this yields the following characterisation: (1) The symmetric equilibrium is such that h " 0, or equivalently ř In the third case, the equilibrium is a local Homogeneous Interior Equilibrium, while, in the first two cases, there exists an equilibrium in local strategies that is equivalent toĎ in the sense of Proposition 4.3. Equilibrium or an Interior Equilibrium in each network that is sufficiently connected. Proposition 4.5. Consider an pα, δq-Symmetric Game where there exists ε ą 0 such that for all k, P N , k ‰ , a k, ě ε. Then, one has in both the local and global games: (1) If ρ{pδβtαq ăχpβtp1´αqεq, there exists a Full Investment Equilibrium or an Interior Equilibrium. (2) If, moreover ρ{pδβtαq ą 1, there exists an Interior Equilibrium. Using Lemma 3.4, one can provide a differential characterisation of Social Optima, as reported in the following proposition. Proposition 4.6. A strategy profileD P DpAq is a Social Optimum if and only if for all tk, u P E, one of the following alternative holds: Hence at a Social Optimum, there is investment in a link only if the sum of marginal utilities induced by the investment is larger than or equal to the investment cost. If the cost is smaller than the sum of marginal utilities, then the link is completely suppressed (case (a)). On the other hand, if the solution is interior, then the level of investment is such that the sum of marginal utilities is exactly equal to the investment cost (case (c)). By analogy with the case of Nash Equilibria, we introduce the following definition. • A Full Investment Optimum is an optimum that satisfies, for all tk, u P E, case (a) of Proposition 4.6. • A No Investment Optimum is an optimum that satisfies, for all tk, u P E, case (b) of Proposition 4.6. • An Interior Optimum is an optimum that satisfies, for all tk, u P E, case (c) of Proposition 4.6. The comparison between Proposition 4.6 and Proposition 4.1 and 4.2 underlines the fact that investment in contagion reduction has all the features of a public good problem. At equilibrium, the investment level is determined by the marginal utility of a single agent (the one with the largest willingness to pay) while social efficiency requires the investment level to be determined by the sum of all marginal utilities. To quantify more precisely this inefficiency and its dependence on the network structure, we shall use as a metric the PoA (see, e.g., Papadimitriou (2001) ; Nisan et al. (2007) ; Omic et al. (2009); Hayel et al. (2014) ). In our setting, where social welfare is always negative, the PoA is defined as the ratio between the social welfare at a Nash Equilibrium and the welfare at a Social Optimum. Accordingly, the PoA in the local and global games are respectively defined as follows |Worst social welfare at a local Nash Equilibrium| |Social welfare at a Social Optimum| , (4.3) PoA Glo :" |Worst social welfare at a global Nash Equilibrium| |Social welfare at a Social Optimum| . (4.4) By construction, the PoA is greater or equal to 1 and equal to 1 only when all Nash Equilibria of the game are socially optimal. An increasing PoA corresponds to an increasing social inefficiency of individual behaviours at a Nash Equilibrium. Theorem 4.1 and 4.2 below provide a partial characterisation of the PoA in the case of an pαq-Homogeneous Game and Complete Network. Theorem 4.1. Consider an pαq-Homogeneous Game and a Complete Network. Assume that the global game Gpδ, A, β,t, x 0 , ρq is such that: the worst Nash EquilibriumĎ is not a Full Investment Equilibrium and one of the corresponding Social OptimaD is not a Null Investment Optimum. Then The upper bound for PoA Loc has a stronger dependence on the structure of the network. Theorem 4.2. Consider an pαq-Homogeneous Game and a Complete Network with N ě 3. Assume that the local game Lpδ, A, β,t, x 0 , ρq is such that: the worst Nash EquilibriumD is not a Full Investment Equilibrium and one of the corresponding Social OptimaD is not a Null Investment Optimum. Then where for any adjacency matrix B and strategy profiles D, D 1 , K i pδ i , B, D, D 1 , β,t, x 0 q :" ř kPN k‰i δ i pC i,k pB, D, β,t, x 0 q´C i,i pB, D 1 , β,t, x 0 qq. In particular, for all i, k P N , k ‰ i, Theorem 4.1 and 4.2 imply that the PoA grows at most linearly with the number of agents. As highlighted in the proposition below (that recalls the notations of Example 4.1), the case of a Symmetric Game shows that one cannot improve this linear bound. Proposition 4.7. Consider an pα, δq-Symmetric Game and an paq-Complete Network with N ě 3. Assume that ρ{pδβtαq P p2,χpβtp1´αqaqq , and letĎ (resp.D) be the worst Nash Equilibrium (resp. one of the corresponding Social Optima). Then where h :" βtp1´αqpa´ř iPNď i k, q ą 0, for any k, P N , k ‰ . In particular, ρ´δβtα expp´hq ě 0. Our previous results highlight the fact that individual strategic behaviours can lead to major inefficiencies in the containment of epidemic spreading. In particular, there can be complete free-riding of other players on the investment of the agent that is the most affected by the epidemic (Proposition 4.1 and 4.2) and the inefficiency can scale up to linearly with the number of agents (Theorem 4.1 and 4.2 and Proposition 4.7). In other words, individual strategic behaviours can be highly inefficient in terms of social welfare as soon as there is a large number of agents involved. This is the case in real-world applications whether one considers epidemic spreading between individuals at the domestic scale or between countries at the global scale. Against this backdrop, it is natural to search for a public policy response for the prevention of epidemic spreading. During the recent COVID-19 outbreak, a widespread policy response has been the implementation of social distancing measures that have reduced, in a uniform way, the scale of social interactions. Formally, we can define the social distancing policy at level κ P R`as restricting social interactions to CpA, κq :" pc i,j q i,jPN such that for all i, j P N , c i,j :" κa i,j { ř kPN a i,k (or equivalently c i,j :" κa i,j { ř kPN a k,i as A is symmetric). The level κ P R`must be such that A´CpA, κq ě O. Hence, the social distancing policy amounts to bounding the level of social interactions of each agent to a fixed level. In practice, this has been implemented by massive restrictions on socio-economic activities such as interdiction of public gatherings, closing of schools and businesses, and travel restrictions. A formal analysis of this policy in our framework shows it can be socially efficient, at least if the initial contagion probability and the disutility are assumed to be uniform. Namely, it is optimal in the following sense. Proposition 4.8. Consider a pα, δq-Symmetric Game and assume that ř kPN a i,k ą 0 for all i P N . 1. If 2δβtα ě ρ, then κ " 0 is optimal and the optimal social distancing measure involves the suppression of every link. 2. If 2δβtα ă ρ, then for every ε ą 0, there existsT ą 0 such that fort ěT , one can find 2δβtα ă ρ ď 2δβtα exppβtp1´αqˆmin iPN ř kPN a i,k q for which there exists an admissible κ ą 0 satisfyinĝ ΠpA´CpA, κqq ě max DPDpAqΠ pDq´ε . In this case, for every ε ą 0 and fort large enough, there is an ε´optimal social distancing measure which does not involve any suppression of link. Hence, uniform reduction of social interactions appears as being an extremely efficient policy in our framework. This appears as a natural counterpart to existing results in the literature that emphasise the role of highly connected nodes, e.g.,"super spreaders", in epidemic propagation (see, e.g., Pastor-Satorras and Vespignani (2001); Pastor-Satorras et al. (2015)). Our result would benefit from further research on the extent to which one could relax the assumption that the "implicit" costs of connectivity reduction are homogeneous. This assumption indeed neglects the fact that certain actors might value more social interactions because of their economic, psychological, or social characteristics. Moreover, results on the determination of the optimal level of social distancing would also be welcome. In practice, the level of social distancing has been determined according to policy decisions about the socially/economically acceptable rate of contagion, rather than inferred from individual preferences. Social distancing measures can be implemented at the domestic scale in order to reduce the propagation of epidemics between individuals. However, at the international scale, there is no authority entitled to implement such coercive measures. Furthermore, individual countries can take measures to reduce their interactions with other countries, e.g., border closures, but cannot directly reduce interactions between two other countries. They are thus, by default, in the framework of a local game. One could nevertheless consider schemes in which countries with a higher disutility from infection subsidise investments in other parts of the network to reduce global contagiousness. This would turn the problem into a global game. In order to compare outcomes in these two situations, we introduce the notion of PoK, which corresponds to the ratio between the social welfare at the worst equilibrium of the local game and at the best equilibrium of the global game. |Worst social welfare at a Nash Equilibrium of the local game| |Best social welfare at a Nash Equilibrium of the global game| . In particular, if PoK ą 1, then global equilibria are better than local ones. On the contrary if global and local equilibria coincide (as in Example 4.1), PoK " 1. The latter implies in particular that an increase in the set of admissible strategies does not necessarily induce an increase in individual welfare. Sometimes it could even lead to more free riding. In general, the value of the PoK is determined by the network structure and the individual disutilities associated to contagion, measured by the coefficients δ i , i P N . In particular, following the lines of the proofs of Theorem 4.1-4.2, one can provide an explicit lower bound on the PoK, as detailed in the theorem below. Theorem 5.1. Consider an pαq-Homogeneous Game and a Complete Network with N ě 3. Assume that the local game Lpδ, A, β,t, x 0 , ρq and global game Gpδ, A, β,t, x 0 , ρq are such that: the worst local Nash EquilibriumD is an Homogeneous Interior Equilibrium and the best global Nash EquilibriumĎ is not a Full Investment Equilibrium. In particular, for all i, k P N , k ‰ i, As hinted above, in the case of a Complete Network, under the assumptions of Proposition 4.7, the conditions of Theorem 5.1 are satisfied and PoK " 1. Moreover, Equation (5.1)-(5.2) above highlight the fact that the PoK increases when there exists agents i P N with a large disutility of contagion δ i that are highly connected to other nodes in the network, as measured by C i,k p¨q, i, k P N , k ‰ i. A salient example of such case is that of an paq-Complete Network where one of the agents has a much higher disutility of contagion than its peers. We thus intend to study this example and more specifically to consider the limit case where δ " δe i for some i P N , i.e. where the disutility of all other agents is negligible with respect to that of agent i. In this setting there is no indeterminacy on the agent that is playing and we can give a necessary condition for global strategies to dominate local ones. This is the aim of the following proposition. Proposition 5.1. Fix i P N . Consider the local game Lpδe i , A, β,t, x 0 , ρq for an pαq-Homogeneous Game and an paq-Complete Network with N ě 3. If then one has: (1) Any local equilibriumD is an Homogeneous Interior Equilibrium and is such that D j " O, for all j P N , j ‰ i, andd i i,k "d i k,i " h for all ti, ku P E for some h P r0, as. (2) Global strategies dominate local ones if and only if the parameters β,t, α, and a are such that N´1βtp1´αqpa´hqq . In this paper, we have investigated the prophylaxis of epidemic spreading from a normative point of view in a game-theoretic setting. Agents have the common objective to reduce the speed of propagation of an epidemic of the SI type through investments in the reduction of the contagiousness of network links. Despite this common objective, strategic behaviours and free-riding can lead to major inefficiencies. We have shown that the PoA can scale up to linearly in our setting. This strongly calls for public intervention to reduce the speed of diffusion. In this respect, we have shown that a policy of uniform reduction of social interactions, akin to the social distancing measures enforced during the COVID-19 pandemic, can be ε-optimal in a wide range of networks. Such policies thus have strong normative foundations. Our results however assume that the cost of reducing interactions is uniform among agents. The validity of this assumption strongly depends on the scope of the analysis: it is a much more benign approximation when the focus is on public health than in the case where economic and financial considerations ought to be taken into account. We have partly accounted for heterogeneity as far as the benefits of prophylaxis are concerned. In this setting, we have shown that allowing agents to subsidise investments in the reduction of contagiousness in distant parts of the network can be Pareto improving. This result calls for further research on the design of mechanisms to improve the efficiency of cooperation against epidemic spreading. k, P N , one has where for any k, j P N ,Î k,j is the N´dimensional square matrix with null entries except on the k th´r ow and j th´c olumn for which the entry is equal to one. This leads to Equation (3.7). Moreover, for all k, , p, q P N , we compute Applying the Karush-Kuhn-Tucker conditions, we obtain thatD i P K i pA,D´iq is a solution if and only if, for any tk, u P E, one of the following cases holds, assuming without loss of generality that BU k p¨,D´kq{Bd k tk, u pD k q ď BU p¨,D´ q{Bd tk, u pD q: (a) (i) ρ ă BU k p¨,D´kq{Bd k tk, u pD k q andd k tk, u`d tk, u " a tk, u , (ii) BU k p¨,D´kq{Bd k tk, u pD k q ă ρ ă BU p¨,D´ q{Bd tk, u pD q andd k tk, u " 0,d tk, u " a tk, u , (iii) BU k p¨,D´kq{Bd k tk, u pD k q " ρ ă BU p¨,D´ q{Bd tk, u pD q andd k tk, u P r0, a tk, u s,d tk, u " a tk, u´d k tk, u , (b) ρ ą BU p¨,D´ q{Bd tk, u pD q andd k tk, u "d tk, u " 0, (c) (i) BU k p¨,D´kq{Bd k tk, u pD k q ă ρ " BU p¨,D´ q{Bd tk, u pD q andd k tk, u " 0,d tk, u P r0, a tk, u s, (ii) BU k p¨,D´kq{Bd k tk, u pD k q " ρ " BU p¨,D´ q{Bd tk, u pD q and 0 ďd k tk, u`d tk, u ď a tk, u . Proof. [of Proposition 4.2] For 1 ď i ď N , the optimisation programme for characterising the Nash Equilibria writes subject to: Applying the Karush-Kuhn-Tucker conditions, we obtain thatĎ i P S i pA,Ď´iq is a solution if and only if, for any tk, u P E, one of the following cases holds: (a) (i) ρ ă min iPN´B U i p¨,Ď´iq{Bd i tk, u pĎ i q¯and ř qPNď q tk, u " a tk, u , (ii) there exists i, j P N , such that BU i p¨,Ď´iq{Bd i tk, u pĎ i q ă ρ ă BU j p¨,Ď´jq{Bd j tk, u pĎ j q anď d q tk, u " 0 for all q P A i pĎq, ř qPĀ j pĎqď q tk, u " a tk, u , where for a given h ě 1, there exists i, j P N , such that BU i p¨,Ď´iq{Bd i tk, u pĎ i q " ρ ă BU j p¨,Ď´jq{Bd j tk, u pĎ j q and 0 ď ř qP i pĎqď q tk, u ď a tk, u ,ď q tk, u " 0 for all q P`Ā i pĎq˘c, there exists j P N , such that ρ " BU j p¨,Ď´jq{Bd j tk, u pĎ j q andď q tk, u " 0 for all q P`Ā j pĎq˘c, 0 ď ř qP j pĎqď q tk, u ď a tk, u . Proof. [of Proposition 4.6] For 1 ď i ď N , the optimisation programme for characterising the Social Optima writes max DPM NΠ pDq subject to: The proof is then a straightforward adaptation of the proof of Proposition 4.1 and 4.2. Proof. [of Theorem 4.1] It follows from the assumption onĎ that for all i P N , Therefore appealing to Equation (3.8) and Equation (A-3), we obtain Similarly, it follows from the assumption onD that it is such that for all k, P N , k ‰ , We deduce from Equation (3.9) and Equation (A-5), ΠpDq " Combining Equation (A-4) and (A-6) and using Equation ( Therefore, it follows from the assumption onD that for all i, P N , i ‰ , ď 2pN´1qrpN´1qρ´pN´2qαδ i C i,i pA,D, β,t, x 0 qs . In particular, we observe from the non-decreasing property of marginal utilities (recall Lemma 3.2), that for all i P N , ρ`αδ i rC i,k p¨q´C i,i p¨qspA,D, β,t, x 0 q ě 0 @ k P N , k ‰ i, and ρ´αδ i C i,i pA,D, β,t, x 0 q ě 0 . Finally, after appealing to Equation (3.8) and Equation (A-11), we obtain In particular, it follows from the non-decreasing property of marginal utilities (recall Lemma 3.2) that ρ´δβtα expp´hq ě 0. It is then straightforward to check that On the other hand, one can assume without loss of generality thatD is of the form Indeed, by concavity ofΠ, we know the set of Social Optima is convex. Moreover, given the symmetry of the game, the set of Social Optima shall be invariant by permutation. Thus, the average of all socially optimal profiles is socially optimal and must be symmetric, i.e. of the formD. The proof is thus concluded proceeding as in the proof of Theorem 4.1 to prove Equation (A-6), and recalling Equation (4.4). Proof. [of Proposition 4.8] Let us first remark that in the case where 2δβtα ě ρ, one can check thatD " A is a Social Optimum. This amounts to saying that CpA, 0q is optimal and thus allows to conclude. We now consider the case where 2δβtα ă ρ. One can easily check that for everyt ą 0 one can find 2δβtα ă ρ ď 2δβtα exppβtp1ά qˆmin iPN ř kPN a i,k q such that there exists 0 ăκ ď min iPN ř kPN a i,k satisfying 2δβtα exppβtp1´αqκq " ρ . (A-12) Let us then recall that for any κ ě 0, and k, P N , Now, it is straightforward to check that, for κ ą 0, the largest eigenvalue of βtp1ά qCpA, κq is µ 1 :" βtp1´αqκ. According to the Perron-Frobenius theorem, this largest eigenvalue is simple. Furthermore, the associated normalised eigenvector is v " p1{ ? N q1. Thus, applying Lemma 3.1, one gets exp pβtp1´αqCpA, κqq " exppβtp1´αqκqV p1`O pexpp´|µ 1´µ2 |qqq , where V :" v v J and µ 2 denotes the second largest eigenvalue in module. One shall then notice that for all i, j P N , pV q i,j " 1{N, so that BΠ Bd tk, u pA´CpA, κqq " 2δβtα exppβtp1´αqκq p1`O pexpp´|µ 1´µ2 |qqq´ρ . Noting that, all the other parameters being fixed, the spectral gap |µ 1´µ2 | is increasing with respect tot and κ, one can assume that for every ε ą 0, there existsT ą 0 such that fort ěT , 2δβtα exppβtp1´αqκq p1`O pexpp´|µ 1´µ2 |qqq ď 2δβtα exppβtp1´αqκq`ε{}A} , for all κ ą 0. Combining the latter with Equation (A-12), one concludes that CpA,κq is an approximate critical point in the sense that for all tk, u P E,ˇˇˇˇBΠ Now,Π being continuous and differentiable, one gets through the mean value theorem |ΠpA´CpA,κqq´ΠpDq| ˇˇBΠ Bd tk, u pA´CpA,κqqˇˇˇˇˆ}A´CpA,κq´D} , leading, using Equations (A-13) and (A-14) , to the required result |ΠpA´CpA,κqq´ΠpDq| ď ε . Proof. [of Proposition 5.1] We assume without loss of generality that i " 1. By concavity of Π 1 the set of local optima is convex. Moreover, given the asymmetry of the game (involving only player 1), the set of local optima shall be invariant by the permutation of nodes leaving node 1 invariant. Thus, the average of all locally optimal profiles is locally optimal. We letD be such optimum. It is, in particular, such that there exists h P r0, as such that for all 1 ă j ď N,d 1,j "d j,1 " h. For 1 ď j ď N, C 1,j pA,D, β,t, x 0 q is of the form Using a Taylor expansion, we obtain that pexppHqq 1,1 " ÿ kě0 1 2k! pN´1q k µ 2k " coshp ? N´1µq , while for 1 ă j ď N, Hence, in view of the assumption on ρ,D is an Homogeneous Interior Equilibrium. Moreover, global strategies dominate local ones if and only if for some 1 ă j ď N, C 1,j pA,D, β,t, x 0 q ą C 1,1 pA,D, β,t, x 0 q and thus if sinhp ? N´1µq ą ? N´1 coshp ? N´1µq . On the private provision of public goods on networks Debtrank: Too central to fail? Financial networks, the Fed and systemic risk Public goods in networks Optimal design and defense of networks under link attacks Spreading on networks: a topographic view Epidemic thresholds in real networks Node immunization on large graphs: Theory and algorithms Notes on equilibria in symmetric games The role of the airline transportation network in the prediction and predictability of global epidemics Thresholds for virus spread on networks A network approach to public goods The effect of network topology on the spread of epidemics Interaction, protection and epidemics Complete gametheoretic characterization of SIS epidemics protection strategies Attack vulnerability of complex networks Public goods in endogenous networks Transient dynamics of epidemic spreading and its mitigation on large networks On the dynamics of deterministic epidemic propagation over networks Networks: an introduction Algorithmic game theory Protecting against network infections: A game theoretic perspective Algorithms, games, and the internet Epidemic processes in complex networks Epidemic spreading in scale-free networks Threshold conditions for arbitrary cascade models on arbitrary networks. Knowledge and Information Systems Optimal vaccine allocation to control epidemic outbreaks in arbitrary networks Optimal resource allocation for network protection against spreading processes Existence and uniqueness of equilibrium points for concave N-person games Analysis of exact and approximated epidemic models over complex networks Approximation algorithms for reducing the spectral radius to control epidemic spread Suppressing epidemics with a limited amount of immunization units Decay towards the overall-healthy state in SIS epidemics on networks Exact Markovian SIR and SIS epidemics on networks and an upper bound for the epidemic threshold In-homogeneous virus spread in networks Virus spread in networks Decreasing the spectral radius of a graph by link removals Epidemic spreading in real networks: An eigenvalue viewpoint