key: cord-0712466-0ueo3z2m
authors: Bouveret, Géraldine; Mandel, Antoine
title: Social interactions and the prophylaxis of SI epidemics on networks()
date: 2021-02-05
journal: J Math Econ
DOI: 10.1016/j.jmateco.2021.102486
sha: aab92b75084c24541d4c2f36c355805bc32adfe5
doc_id: 712466
cord_uid: 0ueo3z2m

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 characterise individual and socially efficient behaviour using the notions of communicability and exponential centrality. Second we show, by computing the Price of Anarchy, that the level of inefficiency can scale up to linearly with the number of agents. Third, 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 implementation of cooperation frameworks that allow agents to subsidise prophylactic investments 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 welfare improving containment policies.

1 Introduction behaviours to limit epidemic propagation, but also the possibility to design efficient containment policies taking into account the network structure.

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 investigates the social efficiency of policy measures aiming at reducing epidemic diffusion. Section 6 concludes. All proofs are given in the appendix.

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 to minimise the consequences of an existing epidemic spread with a limited number of available patches or vaccines over the network.

From an economic perspective, a number of contributions have investigated the integration of epidemiological models into dynamic general equilibrium models, including: Geoffard and Philipson (1996) ; Gersovitz and Hammer (2004) ; Goenka and Liu (2012) ; Goenka et al. (2014) ; Goenka and Liu (2019) and, more recently, Eichenbaum et al. (2020) ; Jones et al. (2020); Farboodi et al. (2020) . These "epi macro" contributions generally consider a representative agent and focus on the negative externality induced on economic dynamics by individual reaction to epidemic processes. We rather focus on the containment of epidemic spreading per se and the role of social interactions in this setting. In this respect, our contribution relates to the recent work of Acemoglu et al. (2020) on targeted lockdown and to that of Garibaldi et al. (2020) on individual vs social incentives for prophylactic measures. In line with the latter analysis as well as ours, Bayham et al. (2015) provides empirical evidences on behavioural changes during epidemics.

Our contribution also 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 neighbours. In particular, Allouch (2015) shows the existence of a Nash Equilibrium 6 J o u r n a l P r e -p r o o f 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 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 M N , we write pMq i,j or m i,j , 1 ¤ i, j ¤ N , to refer to its element in the i th ¡row and j th ¡column. Moreover, for any M M N , ||M|| denotes its Frobenius norm and for any matrix M and K in M N ¢ M N , we write M ¤ K if m i,j ¤ k i,j , di, 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 R N , u i , 1 ¤ i ¤ N, refers to its element in the i th ¡row while u t denotes its transpose and ||u|| its Euclidean norm. Additionally, for any u and v in

For a function f : R Þ Ñ R and a vector u 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 ¡vector of the canonical basis of R N , e i , 1 ¤ i ¤ N, and any matrix M M N , we define the product operator

a N ¡dimensional row vector. 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 S N , we let d tj,ku : d j,k d k,j . Moreover, given U S N , a differentiable function φ : U Ñ R, andD U, we denote by fφ fd ti,ju pDq the partial derivative in the direction of B ti,ju , that is fφ fd ti,ju pDq : fφ

where fφ fd i,j pDq and fφ fd 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 N u and their weights by the weighted adjacency matrix A S N pR q. In particular, for all i 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) ). This model is simpler to analyse than more elaborate versions such as the SIS or SIR models. It nevertheless provides a 8 J o u r n a l P r e -p r o o f relevant approximation of epidemic dynamics to analyse prophylactic behaviours "exante" (before contagion) as the network contagion paths are not modified, at short time-scales, by the possibility to revert to a susceptible/removed state. Furthermore, the SI model can be straightforwardly extended from the individual to an aggregate level (region or country). Indeed the transition from susceptible to infected can be defined as the first occurrence of contagion or the crossing of an epidemic threshold in the area under consideration whereas the transition from infected to susceptible or from infected to removed cannot be univocally defined at the aggregate level. 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 the diffusion of innovation (see, e.g., Young (2009) ).

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 ξ X gives the infection status of all agents. The main variable of interest is the probability of contagion whose dynamics in the time interval rt, t hs is given by

It is further assumed that the probability for node i to be infected by his (infected) neighbour j can be approximated for h small enough by βa j,i h where β is a unit contagion rate, and a i,j is the contagiousness of the network link ti, ju E. Thus, one 9 J o u r n a l P r e -p r o o f has PpX i pt hq 1q PpX i ptq 1q ţ ξX |ξ i 0u r1 ¡ ¹ jN p1 ¡ βa j,i hξ j ophqqsPpXptq ξq , and equivalently

where ophq is a generic term such that lim hÑ0 |ophq| {h 0. In turn, this yields

Equation (3.1) characterises completely the evolution of the infection probability, 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 S N pR q is irreducible and aperiodic.

The irreducibility assumption amounts to consider 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. Yet, the number of states of the Markov chain increases exponentially with the number of nodes, and is 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 N -intertwined model of Van Mieghem et al. (2009) considers the average behaviour over states for the infection probability. More precisely, the Nintertwined model assumes that the events tX i ptq 0u and tX j ptq 1u are independent for all i, j N and thus approximates Equation (3.1) by

Using the fact that PrX i ptq 1s PrX i ptq 0s 1, one gets

Letting x i ptq : PrX i ptq 1s one gets as h tends toward 0, 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).

following linear equation

However, this approximation grows exponentially towards V, 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 N and t R , y i ptq : ¡ logp1 ¡ x i ptqq, and observe thatx : rx 1 , ...,x N s t is a solution of the system defined by Equation (3.2) with initial condition x p0q : rx 1 p0q, ..., x N p0qs t : x 0 , with at least one non-null element to avoid triviality, if and only ifȳ : rȳ 1 , ...,ȳ N s t is a solution of the system of equations defined for all i N by fy i ptq ft βj N a i,j p1 ¡ expp¡y j ptqqq , lim tÑ V ||xptq ¡ x ptq|| 0, for any t ¥ 0,x ptq¨xptq¨xptq wherex : rx 1 , ...,x N s t 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.

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 N can thus be expressed directly as

where the constant term lnp1 ¡ x 0 q diagp1 ¡ x 0 q ¡1 x 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 :

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

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 iN turns the adjacency matrix into A ¡°i N D i and thus yields to agent i N a utility

where D ¡i : pD j q jN , 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, for all i N , the cost associated to a strategy D i is given by

where ρ ¡ 0 is the cost parameter.

Overall, the payoff of agent i N given a strategy profile pD i q iN 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 pS N pR qq N ¡1 , the set of admissible strategies for player

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.

In the following, unless otherwise specified, we consider as implicitly given the utility weights δ : rδ 1 , ..., δ N s t , 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 Π. As emphasised above, the game is defined on the basis of the approximated probability of contagion not on the "actual" one, which is not computable. In this setting, a Nash Equilibrium is defined as follows.

Definition 3.1 (Nash Equilibrium).

An admissible set of strategiesĎ : pĎ i q iN SpAq is a Nash Equilibrium for

An admissible set of strategiesD : pD i q iN KpAq is a Nash Equilibrium for

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.3. 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 discussion in Section 4.5 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.

Definition 3.2 (Social Optimum). An admissible set of strategiesD :

Note that°i N Π i pD i , D ¡i q only depends on the value of°i N 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 iN SpAq, there exists pD i q iN KpAq

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 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.

Since the 2020 COVID-19 pandemic, stringent policy measures have been enforced to contain epidemic spreading. In particular, the state of emergency has been proclaimed and we have witnessed a suspension of some of the civil liberties (e.g. freedom of assembly). A normative assessment of such policies requires a quantitative estimate of the inefficiency induced by individual behaviours. The PoA provides precisely such a metric (see, e.g., Papadimitriou (2001); Nisan et al. (2007)). It is defined as the ratio between the social welfare at the worst Nash Equilibrium and the one at the Social Optimum. Hence, in our setting, the PoA in the local and global games is defined as follows PoA Loc : |Worst social welfare at a local Nash Equilibrium| |Social welfare at a Social Optimum| , (3.7)

PoA Glo : |Worst social welfare at a global Nash Equilibrium| |Social welfare at a Social Optimum| .

(3.8)

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. The PoA is standardly used in the computer science literature to assess the efficiency of network structures and protocols. Notably, Roughgarden and Tardos (2002) show that the PoA in routing games with linear congestion costs is bounded above by 4 {3, while Fabrikant et al. (2003) show that the PoA is bounded independently of the number of players in network creation games. These and other related results indicate the relative efficiency of decentralised process in computer networks (see also Anshelevich et al. (2008) in this respect). The PoA has also been used in the epidemiological literature (see e.g. Hayel et al. (2014) ; Omic et al. (2009) ). In particular, Omic et al. (2009) consider a game where agents individually choose their curing strategy in an SIS epidemic context. They show that the PoA can be arbitrarily large and therefore argue for policy interventions in order to steer agents towards more socially efficient behaviours.

In this section, we provide a characterisation of equilibrium and social optimum as a function of network structure. To ease the exposition, we focus in the main text on the case where the initial contagion probability is equal across agents (whenever possible, the characterisation for arbitrary initial contagion probabilities x 0 is provided in the J o u r n a l P r e -p r o o f appendix and proofs in the appendix are given for the general case). More precisely, we focus, unless otherwise specified on α-homogeneous games defined as follows:

Definition 4.1 (α-Homogeneous Game). A game is pαq-homogeneous if it is such that for all i N , x 0 i α for some α p0, 1q. We will abusively write x 0 α.

As hinted by the dependency of the utility function on the exponential of the adjacency matrix (see Equation 3.6), the characterisation of optimal behaviours will be closely related to the notions of communicability and exponential centrality defined as follows.

Definition 4.2 (Communicability). Let X be the adjacency matrix of an undirected network over the set of nodes N .

The communicability between i N and j N is defined as

The exponential centrality, or total communicability, of i N is defined as

The subgraph centrality of i N is defined as

The notion of exponential centrality is widely used for the analysis of complex networks in natural sciences (see e.g. Estrada and Hatano (2008) ; Benzi and Klymko (2013) and references therein) and is very similar to that of Katz-Bonacich centrality (Katz, 1953; Bonacich, 1987) , which is widely used in economics (see e.g. Ballester et al. (2006) ). In both cases, centrality is defined as a weighted sum of network paths leading to a node. Yet, while the Katz-Bonacich centrality is based on "exponential" discounting of the length of paths for a parametric discount factor, exponential centrality uses a discounting scheme that increases more rapidly with path length and that is parameter J o u r n a l P r e -p r o o f Journal Pre-proof free. It is also worth pointing out that for adjacency matrices of the form tX with t R , i.e. adjacency matrices whose connectivity increases linearly in time (such as the ones considered here), it is known that for asymptotically large t, exponential centrality produces the same rankings as eigenvector centrality (see Theorem 5.1 in Benzi and Klymko (2015) ) . The marginal utility induced by investments in the reduction of the contagiousness of a link can then be directly expressed in terms of communicability. Namely, one has 2 . 

Furthermore, the marginal utility is non-negative and the map Π i p¤, D ¡i q is concave on S i pA, D ¡i q.

Let us first remark that, as the network of contagion is assumed undirected, investments in the link tk, u E induce, from the point of view of agent i, a reduction of contagiousness from k to i on the one hand and from to i on the other hand. More precisely, the marginal utility of investment in link tk, u for agent i is equal, up to the factor δ i αβt, to the sum of communicability between i and k and between i and . In turn, the communicability 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 α. Overall, the marginal impact of agents' actions on contagiousness depends on the characteristics of the disease, measured through the initial contagion probability α and the diffusion rate β, the time horizont and the structure of the contagion network modified by the agents'

Proposition 4.2. A strategy profileĎ SpAq is a Nash Equilibrium of the global game Gpδ, A, β,t, α, ρq if and only if for all tk, u E, the following two conditions hold:

(1) One of the following alternative holds:

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 edges of the link in the local case and all agents in the global case. Otherwise, their interpretation is similar.

J o u r n a l P r e -p r o o f Equilibrium investment in a link is determined by the relationship between cost and communicability ( or equivalently marginal utility). If the investment cost is large with respect to the communicability of the edges, there is no investment in the link. If the investment cost is smaller than the communicability from the edges to a player, 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 communicability to the edges invest in the link. They do so up to the point where the communicability is exactly proportional to the investment cost. The following definition highlights specific classes of equilibria in which investment behaviour is qualitatively similar across links.

A Full Investment Equilibrium is an equilibrium that satisfies, for all tk, u E, case (a) of Proposition 4.1 (resp. 4.2).

A No Investment Equilibrium is an equilibrium that satisfies, for all tk, u E, case (b) of Proposition 4.1 (resp. 4.2).

An Interior Equilibrium is an equilibrium that satisfies, for all tk, u 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 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 :

be the set of players susceptible to invest in the link tk, u E at an equilibrium D of the global game and E L tk, u pDq :

be the set of players susceptible to invest in the link tk, u 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.

J o u r n a l P r e -p r o o f Proposition 4.3. Let D be an equilibrium of the global game Gpδ, A, β,t, α, ρq (resp. local game Lpδ, A, β,t, α, ρq). Assume thatD SpAq (resp.D KpAq) is such that for all tk, u 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, α, ρq (resp. Lpδ, A, β,t, α, ρqq and its equilibrium D. We observe that, whenever for some i, j, k, N ,

Finally, 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, α, ρq (resp. local game Lpδ, A, β,t, α, ρq). Then for allà ¥ A ¡°i N D i , any strategy profileD SpÃq (resp.D KpÃq) such that°i ND i :°i N D i à ¡ A is a Full Investment Equilibrium or an Interior Equilibrium of Gpδ,Ã, β,t, α, ρq (resp. Lpδ,Ã, β,t, α, ρq). Moreover, both equilibria induce the same equilibrium network.

Journal Pre-proof

Using Lemma 4.1, one can provide a differential characterisation of social optima, as reported in the following proposition.

Proposition 4.5. A strategy profileD DpAq is a social optimum if and only if for all tk, u 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 can then introduce the following specific classes of social optima. between investment cost and total communicability/exponential centrality. Links between nodes that have high exponential centrality ought to be completely severed (case a). Links between nodes that have low exponential centrality do not need to be altered (case b). Finally, at an interior optimum, investment in each link tk, u must be such that the sum of the exponential centrality of nodes k and is equal to ρ {2δαβt.

The comparison between Proposition 4.5 on the one hand and Proposition 4.1 and 4.2 on the other hand underlines the fact that investment in contagion reduction has all the features of a public good problem. At a Nash 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, theorems 4.1 and 4.2 below provide a partial characterisation of the PoA in our setting.

In this section, we restrict our attention to complete networks in the following sense (for technical reasons related to the proofs).

Definition 4.6 (Complete Network). A network is complete if for all k, N , k $ , a k, ¡ 0.

To characterise the PoA, we build on the following relationships between utility and marginal utility that are straightforward consequences of Lemma 4.1 (and Lemma A.2 in the appendix). Namely, the exponential form of the utility function induces the following relationships between marginal utility and utility. These relationships between marginal utility and utility allow to characterise the utility level prevailing at an equilibrium or at a social optimum using first-order conditions and therefrom to infer the following bounds on the price of anarchy.

Theorem 4.1. Consider a global α-Homogeneous Game Gpδ, A, β,t, α, ρq with a complete network such that the worst Nash equilibriumĎ is not a Full Investment Equilibrium and a social optimumD 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. Assume N ¥ 3 and consider a local α-Homogeneous Game Lpδ, A, β,t, α, ρq with a complete network such that the worst Nash EquilibriumD is not a Full Investment Equilibrium and a Social OptimumD is not a Null Investment Optimum. Then 

In particular, for all i, k N , k $ i,

Theorem 4.1 and 4.2 imply that the PoA grows at most linearly with the number of agents. Furthermore, Proposition 4.7 below will show that one cannot improve upon this linear bound. There results are in strong contrast with these recalled in Subsection 3.7 for network and routing games in which the PoA is bounded independently of the number of agents. This emphasises the fact that in our setting, Nash equilibrium, can become extremely inefficient as the number of agents grow. In other words, an unbounded PoA strongly calls for policy interventions. These are investigated in details in Section 5.

In this subsection, we highlight the impact of network structure on epidemic containment strategies by characterising equilibrium and social optimum for a set of stylised network structures.

Example 4.1. We first focus on a completely homogeneous network such that for all pi, jq N ¢ N , a i,j a for some a ¡ 0. We further consider that the game is α and δ homogeneous and that N ¥ 3. 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, one can ensure there exists a symmetric equilibrium in both the local and global games (see Cheng et al. (2004, Theorem 3) ). We shall show that equilibria for both games coincide and that, for ρ in an appropriate range, they are interior. Indeed, letĎ SpAq, be a symmetric equilibrium of the global game. According to Equation (4.1), one has for all i, k, N ,

where H is of the form where χphq : 1 °k ¥1 u k {k!, with pu k q kNzt0u satisfying the following recursive system 3 6 8 7 u 1 0 and v 1 h u k hpN ¡ 1qv k¡1 and v k h rpN ¡ 2qv k¡1 u k¡1 s for k ¥ 2 .

As χphq ¡ χphq ¡ expp¡hq, it follows from Equation (4.4) that for all distinct elements i, k, N , one has fU i p¤,Ď ¡i q fd i ti, u pĎ i q ¡ fU k p¤,Ď ¡k q fd k ti, u pĎ k q .

Using Proposition 4.2, this yields the following characterisation:

(1) The symmetric equilibrium is such that h 0, or equivalently°i NĎ i A, leading to χp0q 1, if only if ρ ¤ δβtα.

Journal Pre-proof

(2) The symmetric equilibrium is such that h βtp1¡αqa, or equivalently°i NĎ i 0 if and only if ρ ¥ δβtαζpβtp1 ¡ αqaq where ζpβtp1 ¡ αqaq : 2χpβtp1 ¡ αqaq ¡ expp¡βtp1 ¡ αqaq.

(3) The symmetric equilibrium is interior if and only if ρ{pδβtαq p1, ζpβtp1 ¡ αqaqq.

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.

In view of Proposition 4.4, the equilibria put forward in Example 4.1 are also equilibria in games where the network is more strongly connected than in the example, even if the level of connectivity is not uniform among nodes. This defines a broader class of networks in which one can partially characterise equilibrium as follows.

Proposition 4.6. Consider an α and δ homogeneous game where there exists γ ¡ 0 such that for all k, 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.

Example 4.1 also implies that one cannot improve upon the linear upper bound on the PoA. 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 such that:

The sum of utilities at such an optimum can be computed as above and one can then derive the following analytical expression for the price of anarchy.

J o u r n a l P r e -p r o o f Proposition 4.7. Consider the game given in Example 4.1 and assume that ρ{pδβtαq p2, ζpβtp1 ¡ αqaqq , and letĎ (resp.D) be the worst Nash Equilibrium (resp. a Social Optima). Then

where h : βtp1 ¡ αqpa ¡°i Nď i k, q ¡ 0, for any k, N , k $ . In particular, ρ ¡ δβtα expp¡hq ¥ 0.

Games) is that where the network consists in a series of fully connected clusters weakly linked to each other. More precisely, we consider a network with N M ¢ L nodes in which nodes in L : tp ¡ 1qM 1, ¤ ¤ ¤ , M u form the lth cluster in the sense that the adjacency matrix A is such that:

For all 0, ¤ ¤ ¤ L ¡ 1 and all i, j L one has a i,j a, For all k, t0, ¤ ¤ ¤ L ¡ 1u, one has a M 1,kM 1 a, a i,j 0 otherwise.

Hence each cluster L is fully connected and is connected to other clusters through its "bridge" node b : M 1. We denote by B tb 1 , ¤ ¤ ¤ , b L u the set of bridge nodes.

Remark 4.2. In this setting, one can show (see proof in the appendix) that there exists local equilibriaD that are ''symmetric" in the sense that:

Each non-bridge node i N {B uses the same strategy which consists in investing δ nn ¥ 0 in its links towards non-bridge nodes in its cluster and δ nb ¥ 0 in its links towards the bridge node in its cluster (it is not connected to any other node).

Each bridge node j B uses the same strategy which consists in investing δ bn ¥ 0 in its links towards non-bridge nodes in its cluster and δ bb ¥ 0 in its links towards other bridge nodes.

In other words,D is such that for all pi, jq N , one has d i,j 6 9 9 9 9 8 9 9 9 9 7

The equilibrium network H A ¡°i ND i then is of the form

Let us then show that, if M ¥ 3 and βtp1 ¡ αq is sufficiently small, one must have h bb ¥ h bn . If h bn 0, this is trivial. Let us then consider the case where h bn ¡ 0.

Assume, by contradiction, that h bb h bn . This implies in particular h bb a and thus using Proposition 4.1 that ρ

where, with a slight abuse of notation, C b,b rp1¡αqβtHs denotes the subgraph centrality of an arbitrary bridge node and C b,b Irp1 ¡αqβtHs denotes the communicability between two arbitrary bridge nodes. These two quantities are independent of the bridge nodes under consideration given the symmetry properties of H.

Moreover h bb h bn implies h bn ¡ 0 and thus using Proposition 4.1 one has

where, with a slight abuse of notation, C b,n rp1 ¡ αqβtHs denotes the communicability between an arbitrary bridge node and a non-bridge node in its cluster, which is independent of the non-bridge node under consideration given the symmetry properties of H.

Combining Equations (4.6) and (4.7) one gets

and thus For βtp1 ¡ αq sufficiently small one can discard paths of length 3 or more in the computation of C b,b Irp1 ¡ αqβtHs and C b,n rp1 ¡ αqβtHs. Using h bb h bn , the preceding then shows that there are strictly more paths of length 1 and 2 between b and n than between b and b I . Thus, one has C b,n rp1¡αqβtHs ¡ C b,b Irp1¡αqβtHs, which contradicts Equation (4.8). Thus, one has shown by contradiction that h bb ¥ h bn . Hence, if the clusters are sufficiently large, i.e. M ¥ 3, at a symmetric Nash equilbrium, there is more investment in the intra-cluster link than in the inter-cluster link. In other words, there is little investment made to prevent epidemic transmission across clusters. With respect to social optimum, using the concavity of the payoff function and the symmetry properties of the game, it is straightforward to show that there exists a social optimumD with the same symmetry properties as the Nash EquilibriumD above. Accordingly, there exists k nn , k nb , k bb r0, as such that the socially optimal network is of the form k i,j 6 9 8 9 7

Let us then show that, if M ¥ 3, L is sufficiently large, and βtp1 ¡ αq is sufficiently small, one has k bb ¤ k bn . If k bb 0, this is trivial. Otherwise, assume k bb ¡ k bn . This implies in particular k bb ¡ 0 and thus using Corollary 4.1 that

where, with a slight abuse of notation, C b rp1 ¡ αqβtHs denotes the exponential centrality of an arbitrary bridge node, which is independent of the bridge nodes under consideration.

Moreover, k bb ¡ k bn implies k bn a and thus using Corollary 4.1 that ρ ¤ δαβt pC b rp1 ¡ αqβtKs C n rp1 ¡ αqβtKsq , where, with a slight abuse of notation, C n rp1¡αqβtHs denotes the exponential centrality of an arbitrary non-bridge node, which is independent of the non-bridge node under consideration. Combining Equations (4.9) and (4.10) one gets

and thus C n rp1 ¡ αqβtKs ¥ C b rp1 ¡ αqβtKs .

(4.11)

Now:

The sum of paths of length 1 to b is pL ¡ 1qk bb pM ¡ 1qk nb . Indeed there are L ¡ 1 path coming from other bridge nodes, M ¡ 1 paths coming from its cluster. The sum of paths of length 1 to n is k nb pM ¡ 2qk nn . Indeed there is one path coming from the bridge node and M ¡ 2 paths coming from the non-bridge nodes in the cluster.

For βtp1 ¡ αq sufficiently small one can discard paths of length 2 or more in the computation of C n rp1 ¡ αqβtHs and C b rp1 ¡ αqβtHs. Using k bb ¡ k bn , the preceding then shows that, if L is sufficiently large, the sum of paths of length 1 to b is strictly greater than the sum of paths of length 1 to n. In turn, this implies that 5 Policy response

Our previous results highlight the fact that individual strategic behaviours can lead to major inefficiencies in the containment of epidemic spreading. In particular, there may be complete free-riding of other players on the investment of the agent that is the most affected by the epidemic (Propositions 4.1 and 4 .2) and the inefficiency can scale up to linearly with the number of agents (Theorems 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 κ R as restricting social interactions to QpA, κq : pc i,j q i,jN such that for all i, j N , c i,j : κa i,j {°k N a i,k and thus°j N c i,j κ. This amounts to use the strategy A ¡QpA, κq. The level κ R must be such that A ¡ QpA, κ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 5.1. Consider an α and δ homogeneous game and assume that°k N a i,k ¡ 0 for all i 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α 

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)). Indeed uniform restriction of interactions necessarily leads to the fading of super-spreaders.

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.

PoK : |Worst social welfare at a Nash Equilibrium of the local game| |Best social welfare at a Nash Equilibrium of the global game| .

The PoK measures the welfare gains that can be induced by a policy that allows agents to invest in the reduction of contagiousness across the network. Such policies can notably be implemented through international cooperation frameworks. The policy induces welfare gains if PoK ¡ 1, i.e. if global equilibria are better than local ones. The policy is useless if PoK 1, i.e. if global and local equilibria coincide as in Example 4.1. The latter implies in particular that an increase in the set of admissible strategies 34 J o u r n a l P r e -p r o o f does not necessarily induce an increase in social 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 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 α-Homogeneous Game and a complete network with N ¥ 3.

Assume that the local game Lpδ, A, β,t, α, ρq and global game Gpδ, A, β,t, α, ρ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. Then

In particular, for all i, k N , k $ i,

(5.2)

In the case of Example 4.1, the conditions of Theorem 5.1 are satisfied and PoK 1.

More broadly, Equation (5.1)-(5.2) highlight that the PoK increases when there exists agents i N with a large disutility of contagion δ i that are highly connected to other nodes in the network, as measured by the communicability C i,k p¤q, i, k N , k $ i. A salient example is that 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 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 investing and we can give a necessary condition for global strategies to dominate local ones. This is the aim of the following proposition.

Proposition 5.2. Consider an α-Homogeneous Game with a completely homogeneous network such that for all pi, jq N ¢N, a i,j a for some a ¡ 0. Assume that N ¥ 3 and J o u r n a l P r e -p r o o f Journal Pre-proof that there is a single i N such that δ i ¡ 0. We denote this game by Lpδe i , A, β,t, α, ρq.

If

then one has:

(1) Any local equilibriumD is an Homogeneous Interior Equilibrium and is such that

(2) Global strategies dominate local ones if and only if the parameters β,t, α, and a are such that

Hence, Proposition 5.2 provides a characterisation of network/contagion structure for which a policy/agreement that allows agents to invest in links across the network is welfare improving. In contrast with Example 4.1, it shows that such policy measures are particularly relevant when agents have heterogeneous disutilies from contagion. Hence, such policies of "subsidised containment" can be seen as a second-best alternative to the "uniform containment" policies considered in Proposition 5.1 when the latter are not socially acceptable because of the heterogeneity of preferences.

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 36 J o u r n a l P r e -p r o o f cost of reducing interactions is uniform among agents. Further research is required to investigate to which extent one could relax this assumption. Indeed, it neglects the fact that certain actors might value more social interactions because of their economic, psychological, or social characteristics. Hence, 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. Additional 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. We have partly accounted for heterogeneity as far as the benefits of prophylaxis are concerned. In this respect, 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.

Finally, this preliminary paper does not account for the possibility of local virus elimination, through natural immunisation or vaccination. Individual strategies in this respect might strongly interact with network-based prophylactic strategies considered in this paper. This is of particular relevance in a context such as the one of the current COVID-19 pandemic, where availability of vaccines is likely to differ across locations. Further research is thus required to gain a broader understanding of individual and collective strategies when both social distancing and virus eradication can be, partially, implemented.

J o u r n a l P r e -p r o o f Journal Pre-proof (ii) there exists i, j N , such that fU i p¤,Ď ¡i q{fd i tk, u pĎ i q ρ fU j p¤,Ď ¡j q{fd j tk, u pĎ j q anď d q tk, u 0 for all q A i pĎq,°q Ā j pĎqď q tk, u a tk, u , where for a given h ¥ 1, A h pĎq : 5 1 ¤ r ¤ N : fU r p¤,Ď ¡r q fd r tk, u pĎ r q ¤ fU h p¤,Ď ¡h q fd h tk, u pĎ h q C , and A h pĎq : 5 1 ¤ r ¤ N : fU r p¤,Ď ¡r q fd r tk, u pĎ r q ¥ fU h p¤,Ď ¡h q fd h tk, u pĎ h q C , (iii) there exists i, j N , such that fU i p¤,Ď ¡i q{fd i tk, u pĎ i q ρ fU j p¤,Ď ¡j q{fd j tk, u pĎ j q and 0 ¤°q  i pĎqď q tk, u ¤ a tk, u ,ď q tk, u 0 for all q Ā i pĎq¨c,°q Ā j pĎqď q tk, u a tk, u ¡°q  i pĎqď q tk, u , where for a given h ¥ 1,

and°q Nď q tk, u 0, (c) there exists j N , such that ρ fU j p¤,Ď ¡j q{fd j tk, u pĎ j q andď q tk, u 0 for all q Ā j pĎq¨c, 0 ¤°q  j pĎqď q tk, u ¤ a tk, u . Proof. [of Proposition 4.5] For 1 ¤ i ¤ N , the optimisation programme for characterising the Social Optima writes max DM NΠ pDq subject to:

The proof is then a straightforward adaptation of the proof of Proposition 4.1 and 4.2.

A.6 Proofs for subsection 4.4

We first note that we have an exact counterpart of Lemma 4.1 for the auxiliary utility function v i used in the definiton of the social optimum. Namely, one has: Lemma A.2. For every i N , for any Social Optimum D DpAq, and for all k, N , one has:

Moreover, the mapv i p¤q is concave on DpAq.

We then proceed with the proofs of Theorems 4.1 and 4.1

Proof.

[of Theorem 4.1] It follows from the assumption onĎ that for all i N ,

Therefore appealing to Equation (4.2) and Equation (A-4), we obtaiņ

Similarly, it follows from the assumption onD that it is such that for all k, N , k $ , iN fv i pDq fd tk, u ¥ ρ .

(A-6)

We deduce from Equation (4.3) and Equation (A-6),

Combining Equation (A-5) and (A-7) and using Equation (3.8), we obtain the result.

Proof.

[of Theorem 4.2] We know from Equation (A-1) that for all i, k, N , fU i p¤,D ¡i q fd i tk, u pD i q αβtδ i rC i,k pA,D, β,t, x 0 q C i, pA,D, β,t, x 0 qs .

Therefore, it follows from the assumption onD that for all i, N , i $ , fU i p¤,D ¡i q fd i ti, u pD i q αδ i βtrC i,i pA,D, β,t, x 0 q C i, pA,D, β,t, x 0 qs ¤ ρ . 

We deduce from Equation (A-10)-(A-11) that for all i N ,

In particular, we observe from the non-decreasing property of marginal utilities (recall Lemma 4.1), that for all i N ,

Finally, after appealing to Equation (4.2) and Equation (A-12), we obtaiņ

Appealing to Equation (A-7) and Equation (3.7), the result follows.

A.7 Proofs for subsection 4.5

Proof.

[of Proposition 4.7] According to Example 4.1, under the holding assumptions,Ď is a local Homogeneous Interior Equilibrium which yields an equilibrium network of the form given by Identity (4.5). More precisely, for all distinct i, k, N , fU i p¤,Ď ¡i q fd i ti, u pĎ i q δβtα p2χphq ¡ expp¡hqq ρ and fU i p¤,Ď ¡i q fd i tk, u pĎ i q ρ ¡ δβtα expp¡hq .

J o u r n a l P r e -p r o o f

In particular, it follows from the non-decreasing property of marginal utilities (recall Lemma 4.1) that ρ ¡ δβtα expp¡hq ¥ 0. It is then straightforward to check thaţ

On the other hand, one can assume without loss of generality thatD is of the form (recall the discussion after Proposition 4.6) D : The proof is thus concluded proceeding as in the proof of Theorem 4.1 to prove Equation (A-7), and recalling Equation (3.8).

Proof.

[of Remark 4.2] We first restrict our attention to the setting where each agent is constrained to use the same action on each link to a neighbour of a given type (i.e. bridge or non-bridge). We denote the corresponding strategy space as S b for a bridge node and S n for a non-bridge node. Then, following Hefti (2017), we consider the mapping φ pφ b , φ n qq : S b ¢ S n Ñ S b ¢ S n , which associates to a pair of strategy ps b , s n q the best-response of bridge φ b ps b , s n q and non-bridge φ n ps b , s n q players, assuming that all bridge players play s b and all non-bridge players play s n . It is straightforward to check that one can apply Kakutani fixedpoint theorem in this setting and thus find that φ has a fixed point ps ¦ b , s ¦ n q. For a bridge player, s ¦ b is a best-response to the strategy profile induced by ps ¦ b , s ¦ n q in the game where its strategy space is S b . Assume it is not a best-response in the original strategy space. Then, using the convexity of the best-response and the symmetry properties of the game, one can construct, via an appropriate convex-combination, a best-response that actually is in S b . This yields a contradiction. Thus s ¦ b is a best-response in the original game. We show accordingly that the symmetric strategy profile induced by ps ¦ b , s ¦ n q is an equilibrium of the original game.

The proof of Proposition 5.1 relies on the following Lemma that states that for larget and homogeneous initial contagion probabilities, the utility can be approximated through the eigenvector centrality of the contagion network. pA ¡°i N 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

The proof of Lemma A.3 follows from the spectral decomposition of A¡°i N D i and a direct application of the Perron-Frobenius theorem (see Lee et al. (2019, Appendix C) for details). We furthermore have the following remark.

Remark A.1. As A is irreducible and aperiodic, the condition°i N d i j,k a j,k for all j, k N such that a j,k ¡ 0, is sufficient for getting the irreducibility and aperiodicity of A ¡°i N D i .

The proof of Proposition 5.1 follows.

Proof.

[of Proposition 5.1] 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 QpA, 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 iN°k N a i,k q such that there exists 0 κ ¤ min iN°k N a i,k satisfying 2δβtα exppβtp1 ¡ αqκq ρ .

(A-13)

Let us then recall that for any κ ¥ 0, and k, N , fΠ fd tk, u pA¡QpA, κqq i N δβtα exp pβtp1 ¡ αqQpA, κqq i,k i N δβtα exp pβtp1 ¡ αqQpA, κqq i, ¡ρ . Now, it is straightforward to check that, for κ ¡ 0, the largest eigenvalue of QpA, κq is µ 1 : κ. According to the Perron-Frobenius theorem, this largest eigenvalue is simple.

Furthermore, the associated normalised eigenvector is v p1{ c N q1. Thus, applying

Noting that, all the other parameters being fixed, the spectral gap |µ 1 ¡µ 2 |t 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¡βp1 ¡ αq|µ 1 ¡ µ 2 |tqqq ¤ 2δβtα exppβtp1¡αqκqp1 ε {ρ}A}q , for all κ ¡ 0. Combining the latter with Equation ( Proof.

[of Proposition 5.2] 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 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 

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

Who's who in networks. wanted: The key player

Measured voluntary avoidance behaviour during the 2009 a/h1n1 epidemic

Total communicability as a centrality measure

On the limiting behavior of parameter-dependent network centrality measures

Power and centrality: A family of measures

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

The macroeconomics of epidemics

A network approach to public goods

Communicability in complex networks

Network properties revealed through matrix functions

On a network creation game

Internal and external effects of social distancing in a pandemic

The effect of network topology on the spread of epidemics

Modelling contacts and transitions in the SIR epidemics model. Covid Economics Vetted and Real-Time Papers

Rational epidemics and their public control. International economic review

The economical control of infectious diseases

Infectious diseases and endogenous fluctuations

Infectious diseases, human capital and economic growth. Economic Theory

Infectious diseases and economic growth

Interaction, protection and epidemics

Complete gametheoretic characterization of SIS epidemics protection strategies

Equilibria in symmetric games: Theory and applications

Attack vulnerability of complex networks

Optimal mitigation policies in a pandemic: Social distancing and working from home

A new status index derived from sociometric analysis

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

How bad is selfish routing

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

Innovation diffusion in heterogeneous populations: Contagion, social influence, and social learning

In the following to simplify notations, we use the contracted notation C i,j pA, D, β,t, x 0 q instead of C i,j pβtpA ¡°j N D j q diagp1 ¡ x 0 qq

The results of section 4 on the characterisation of Nash equilibria and social optima extend to a setting with an arbitrary initial contagion probability vector. The proofs below are given in this extended setting in which our main results are stated as follows 4 . and the marginal utility is non-negative. Moreover, the map Π i p¤, D ¡i q is concave on S i pA, D ¡i q. (1) One of the following alternative holds: (1) One of the following alternative holds:

Optimum if and only if for all tk, u E, one of the following alternative holds:3 Proofs for subsection 3.5Proof. [of Theorem 3.1] We know from Remark 3.2 that the sets SpAq and KpAq of admissible strategies are compact and convex, and from Lemma 4.1 that the objective function Π is concave on S i pA, D ¡i q and K i pA, D ¡i q with i N and D ¡i pS N pR qq N ¡1 . Moreover, since Π is continuous in its arguments, we therefore conclude from Rosen (1965, Theorem 1) that a Nash Equilibrium exists. where for any k, j N ,Î k,j is the N ¡ dimensional square matrix with null entries except on the k th ¡row and j th ¡column for which the entry is equal to one. This leads to Equation (A-1). Moreover, for all k, , p, q N , we compute fU i p¤, D ¡i q fd i k, fd i p,q pD i q ¡ e i , pβtq 2 exp pβtpA ¡jProof.[of proposition 4.1] For 1 ¤ i ¤ N , the optimisation programme for characterising the Nash Equilibria writesApplying the Karush-Kuhn-Tucker conditions, we obtain thatD i K i pA,D ¡i q is a solution if and only if, for any tk, u E, one of the following cases holds, assuming without loss of generality that fU k p¤,D ¡k q{fd k tk, u pD k q ¤ fU p¤,D ¡ q{fd tk, u pD q:(a) (i) ρ fU k p¤,D ¡k q{fd k tk, u pD k q andd k tk, u d tk, u a tk, u , (ii) fU k p¤,D ¡k q{fd k tk, u pD k q ρ fU p¤,D ¡ q{fd tk, u pD q andd k tk, u 0,d tk, u a tk, u , (iii) fU k p¤,D ¡k q{fd k tk, u pD k q ρ fU p¤,D ¡ q{fd tk, u pD q andd k tk, u r0, a tk, u s,d tk, u a tk, u ¡d k tk, u , (b) ρ ¡ fU p¤,D ¡ q{fd tk, u pD q andd k tk, u d tk, u 0, (c) (i) fU k p¤,D ¡k q{fd k tk, u pD k q ρ fU p¤,D ¡ q{fd tk, u pD q andd k tk, u 0,d tk, u r0, a tk, u s, (ii) fU k p¤,D ¡k q{fd k tk, u pD k q ρ fU p¤,D ¡ q{fd tk, u pD q and 0 ¤d k tk, u d tk, u ¤ a tk, u . Applying the Karush-Kuhn-Tucker conditions, we obtain thatĎ i S i pA,Ď ¡i q is a solution if and only if, for any tk, u E, one of the following cases holds:(a) (i) ρ min iN ¡ fU i p¤,Ď ¡i q{fd i tk, u pĎ i q