The first wave of the coronavirus crisis has seen an unprecedented scale of lockdown measures, imposed worldwide and in many cases very strictly in order to mitigate the public health threat. Unarguably, the economic and social impact has been devastating. The path to reopening the economy remains uncertain, and outbreaks are expected to re-emerge as soon as measures are relaxed. While lockdown measures have been shown to have saved a tremendous number of lives, there is little disagreement that they cannot be maintained in the long run. With a disease so contagious and widespread, the long run will indeed be measured in years rather than months. The path forward, at least until vaccines are proven effective to some extent, is more likely to rely on proper guidelines from the governments, targeted quarantines, combined with the transparent information for the public rather than strict and un-targeted lockdowns.
Despite that the public adherence to guidelines -even if those were optimal-is the driving force in the post-lockdown world, few epidemic models incorporate individuals' decision-making. One notable exception is [Jones et al., 2020] , who integrate individual decision making in a Susceptible -Infectious -Recovered (SIR) model of contagion. This paper is closest in spirit to ours, and they demonstrate using U.S. micro-data that individuals started to socially distance earlier than the governments mandated to do so. They also investigate the optimal social distancing policy, and show that this policy should be mandated for as long as possible until an effective vaccine is available. Other works focusing specifically on Susceptible -Infectious -Recovered/Dead (SIRD) modeling in the context of this public health crisis, e.g., [Acemoglu et al., 2020] , suggest an agenda to make epidemiological models more realistic, and in particular to address multiple sources of heterogeneity. First, it is clear that the disease treats people very differently, and, while no age group is spared, the elderly have significantly worse outcomes. At the same time, the contact pattern is nowhere close to the homogenous mixing of the classical SIR model. [Acemoglu et al., 2020] solve the social planner's problem for a multi-type (multi-risk) SIR model and leave for further research the case where interaction occurs according to a social graph structure.
In this paper, we set up a heterogeneous SIRD model on a random graph that underlies the social contact structure. Individuals have different types and death risk if they contract the disease. Moreover, types derive the connectedness profiles across the population. For this underlying model of contagion, we study the decision problem for each individualparametrized by her type. Like in [Alvarez et al., 2020] , we use the value of statistical life (VSL) as the basis for the individual decision. VSL incorporates all elements that an individual deems worth for her and is determined on the basis of how much the individual is willing to pay in order to decrease her risk of death by a small amount, e.g., a tenth of a percent. This fits precisely into the analysis of how individuals perceive the risk of death due to contracting COVID-19. The average risk of death, conditional on contracting the disease, is of the order of percentage point. The decision to socially distance is precisely in order to mitigate the risk of death. In such an event, the loss to the individual is her VSL. In balance stands the cost to the individual from socially distancing, and we define this as a fraction of the yearly value of statistical life (VSLY). VSLY is, roughly, VSL divided by the remaining life expectancy. A free parameter quantifies how much of VSLY depends on the interactions over the time horizon of the decision. Clearly, the dependence of the decision on the individual type (age) comes through a plethora of sources: VSL and VSLY themselves, the risk of death, the connectivity profile.
The risk to contract the disease depends on the fraction of potentially healthy linkages to the total number of linkages in the system. We will call this the global network immunity. When the network immunity is high, the risk to contract the disease is low for all types. The network immunity depends on the social distancing decision of all individuals and it is obtained as a fixed point, which is our notion of voluntary social distancing (Laissez-Faire) equilibrium. Individuals hypothesize a level of global network immunity. Based on the implied risk to contract the disease, their death risk if they do contract the disease, their value of statistical life and their types, they decide on the social distancing strategy. Then an actual network immunity emerges as the contagion spreads, albeit in our model the spread is instantaneous. The actual network immunity must match the hypothesized network immunity in equilibrium. To account for the increase of the risk of death -for all types-should the hospital system be overwhelmed, the risk of death depends on the network immunity in addition to the individual type, and our results are robust to various specifications of this dependence.
Our first set of results is concerned with the size of the epidemic for a given social distancing strategy profile across individuals and for a given network underlying the social interactions (that we call interaction graph). An infection matrix is obtained from the adjacency matrix and the type dependent rates with which susceptible individuals seek social contact. Based on the spectrum of the infection matrix, we characterize the amplification of the epidemic, namely the ratio between the fraction of infected individuals during the contagion process and the size of the initial seed. In particular, we show that if the largest singular value of the infection matrix is smaller than one, then the expected amplification is of the order O( √ n) in the size of the network n. This represents a testable condition whether a given interaction graph is prone to contagion and can guide governments where to focus an eventual vaccine or identify potential infection hotspots. In the same spirit, we extend our analysis to the case of random graphs underlying the social interaction. We impose mild conditions on the degree distribution of the susceptible population, whereas infectious and recovered individuals' degree distribution can be more arbitrary. There is a maximum degree condition, which allows for degrees that grow sub-linearly with the network size. Our results are in this case asymptotic, and for large networks we establish the network immunity as the unique fixed point of an analytic function depending on the degree distributions and the initial seed size. We then establish the asymptotic limit for the fraction of susceptible individuals. Moreover, we establish the basic reproduction number of the epidemic R 0 in the context of our model, defined as the expected number of links Related literature. Our work is part of the vast literature on SIR epidemics on random networks, to name just a few [Ball and Sirl, 2016 , Stegehuis et al., 2016 , Janson et al., 2014 , Pastor-Satorras et al., 2015 , Ball et al., 2009 , Kiss et al., 2017 , Ball et al., 2010 , Ball et al., 2014 , Barbour et al., 2013 , Britton et al., 2007 , Draief and Massouli, 2010 . We continue on the same line as [Janson et al., 2014] who studies the SIR epidemics dynamics in the configuration model. We partly extend his work (which on the other hand allows for time dynamics) to allow for different individual types. Our proof also is quite different and we allow for the more general class of epidemics represented by the independent threshold model with differentiated types. This may be of interest in itself.
The second related strand of literature is on economics of information security for homogeneous networks, see e.g. [Gordon and Loeb, 2002 , Lelarge, 2012a , Acemoglu et al., 2016 and on games on network [Jackson, 2010, Jackson and Zenou, 2015] . In [Gordon and Loeb, 2002] , the authors consider a simple one-period economic model for a single individual who takes into account a monetary loss should infection occur and a probability depending on security investment to become infected. The security investment choice is analogous to the social distancing. [Lelarge, 2012a] gives a a sufficient condition for monotone investment which guarantees that when network vulnerability is higher individuals invest more. We make the equivalent assumption here that there is less social distancing when network immunity is higher. In particular, more closely related to our paper, [Acemoglu et al., 2016 , Lelarge, 2012a analyze the network security game (strong versus weak protection) for contact process in random networks. We generalize their results by allowing more social distancing levels, moreover type dependent.
Following the health emergency, several papers study the equilibrium social distancing for COVID-19, see e.g., [Acemoglu et al., 2020 , Farboodi et al., 2020 , Jones et al., 2020 , Ferguson et al., 2006 , Ferguson et al., 2020 , Del Valle et al., 2007 , Prem et al., 2020 , Miller et al., 2010 , Prem et al., 2017 , Mossong et al., 2008 , Toxvaerd, 2020 . Our paper is to our best knowledge the first to allow for a network underlying social contacts and heterogeneity.
Outline. The paper is structured as follows. In Section 2 we provide the modeling framework for heterogeneous SIRD epidemics and state our main results regarding the final outcome of the epidemic on given networks and random networks underlying the social contacts. In Section 3 we consider the network social distancing game. In Section 4, we illustrate how our model can be applied to the Covid-19 public health crisis and calibrate the parameters. Section 5 concludes and the Appendix A contains all the proofs.
In this section we introduce the epidemic model and state the main results, for a given individuals social distancing strategies profile across individuals, when contact takes place on general networks and respectively on random networks with given vertex degrees.
We consider a heterogeneous stochastic SIR epidemic process with a possibility of death, i.e., a SIRD (Susceptible → Infectious → Recovered/Dead) model, which is a Markovian model for spreading a disease or virus in a finite population. Our population is assumed to interact via a network G (n) . The set of nodes [n] := {1, 2, . . . , n} represents individuals or households, and the edges represent (potential) connections between individuals. Connections can stem from various sources, and the network is understood to aggregate all these sources. Individuals susceptible to the epidemic may become infected through contact with other infected neighboring individuals.
The population is heterogeneous, individuals can be of different types (e.g., age, sex, blood type, etc.) in a certain type space T , large enough to classify all individuals to the available information. We use the notations t = (t 1 , t 2 , . . . , t n ) to denote the type profiles of all individuals.
Moreover, we consider a finite ensemble of social distancing strategies S = {0, 1, 2, . . . , K}, with 0 representing complete isolation. We use the notations s = (s 1 , s 2 , . . . , s n ) and s −i = (s 1 , . . . , s i−1 , s i+1 , . . . , s n ) to denote the social distancing profiles of all individuals and all individuals other than i respectively.
We assume that at time t = 0, all individuals have only partial information about the network characteristics, the epidemic parameters and the initial conditions. An individual of type t will get utility u (s) t by choosing social distancing strategy s ∈ S. The social distancing equilibrium will be discussed in Section 3.
Let us denote by n (s) t the number of individuals of type t ∈ T with social distancing strategy s ∈ S so that t∈T s∈S n (s)
It is understood that the network is parametrized by its size (and indeed all quantities we define depend on n, which we leave out from the notation for simplicity). We seek to understand the outcomes of a major outbreak as the size of the network becomes large. The following condition is standard: for all t ∈ T and s ∈ S,
We let µ t := s∈S µ (s) t be the (asymptotic) fraction of individuals with type t.
The initial condition of the epidemic is given by the set of initially infected individuals I(0), the set of initially removed individuals R(0) and the set of susceptible individuals S(0). The set of initially removed individuals could be interpreted as a set of immune or non-susceptible individuals. In the later stages of the epidemic, the set of removed nodes will grow with the recovered or dead individuals. Note that S(0) ∪ I(0) ∪ R(0) = [n] and the initial conditions may also depend on the type of each individual.
Each infected individual, throughout its infection period, infects (makes infectious con-6 tact with) any susceptible neighbor individual with type t and social distancing strategy s at the points of a Poisson process with rate β (s) t > 0. We assume there is no latent period so that the contacted susceptible individuals are immediately infected and are able to infect other individuals.
To simplify the analysis, we assume that the infection time ρ is constant and, without loss of generality, we scale the time to make the constant ρ = 1. The infected individual with type t dies after time ρ with probability κ t and recovers with probability 1 − κ t . Note that if ρ = 1, it suffices to replace the infection rates β by ρβ.
We will allow in Section 3 the fatality probability to depend on the fraction (number) of infected people during the epidemic process, as the hospital system can be overwhelmed. In our baseline model an infected individual knows that he is infected and from this moment he is indifferent (the social activity doesn't depend on type for infected individuals) regarding his social activity. The assumption that the infection rate depends only on the type and strategy of the susceptible party is implicitly assuming a conservative setting in which the effort to avoid infection comes from the susceptibles. One could make additional assumptions on the infectives, on whom we could impose quarantine or we could model additional elements in their utility functions to entail concern for their family and friends. Here we leave these considerations aside, in order to focus on the individual's decision when the utility includes only her own value of life.
We also assume that the recovered individuals are no longer infectious, and moreover immune to further infections. Note that this remains a point of active research for Covid-19. The epidemic process continues until there are no infective individuals present in the population. Each alive individual is then either still susceptible, or else they have been infected and have recovered.
We assume that there are initially n S , n I and n R susceptible, infective and removed (recovered or dead) individuals, respectively. Moreover, for each type t ∈ T , there are respectively n S,t , n I,t and n R,t of these individuals with type t. Hence, we have |S(0)| = n S , |I(0)| = n I , |R(0)| = n R , n S = t∈T n S,t , n I = t∈T n I,t , n R = t∈T n R,t and n S + n I + n R = n.
We are then interested in S (s) (∞) and R (s) (∞) the final set of susceptible and removed individuals, respectively, when the individuals follow the social distancing strategy s. Similarly, S (s) t,d (∞) denotes the final set of susceptible individuals with type t, degree d and social distancing strategy s.
In this section we state some general conditions on the adjacency matrix of the interaction graph and epidemics parameters for the size of the epidemics to be small compared to the size of the network. 7 Let A denote the adjacency matrix of the social contact graph. The probability that an infected individual makes infectious contact with any susceptible neighbor with type t and social activity s is given by 1 − e −β (s) t . Given the social distancing profile s, we define the infection matrix B (s) as B (s)
for all i, j ∈ [n]. Note that the infection rates are not necessarily symmetric and, in general, the matrix B (s) might not be symmetric even (if) the adjacency matrix A is symmetric. We first give a condition on the maximum row sum of the matrix B, which gives us an upper bound for the expected amplification of infected individuals (|R (s) (∞)|−|R(0)|)/|I(0)|.
The set of removed nodes at infinity R (s) (∞) \ R(0) is the set of recovered or dead during the epidemic and is same set of all individuals who have ever been infected starting from the initial seed.
which in particular implies that for all k > 0,
We now consider the L 2 norm of the matrix B. Let λ max (B) = ||B|| 2 be the largest singular value of B, which is the square root of the largest eigenvalue of the positivesemidefinite matrix B T B. The following proposition shows that the expected amplification is O( √ n) whenever the largest singular value is smaller than 1.
which in particular implies that for all k > 0,
For n ∈ N, let d (n) = (d i ) n i=1 be a sequence of non-negative integers such that n i=1 d i is even. We now consider a configuration model for the underlying network. We endow the set of individuals [n] := {1, 2, . . . , n} with a sequence of degrees d (n) . We define a random multigraph with given degree sequence (d i ) n 1 as follows. To each node i, we associate d i labeled half-edges. All half-edges need to be paired to construct the graph, this is done by randomly matching them. When a half-edge of a node i is paired with a halfedge of a node j, we interpret this as an edge between i and j. We denote the resulting random graph by G (n) and we write (i, j) ∈ G (n) for the event that there is an edge between i and j. It is easy to see that conditional on the multigraph being simple graph, we obtain a uniformly distributed random graph with these given degree sequences; see e.g. [van der Hofstad, 2016 , Durrett, 2007 .
We consider asymptotics as n → ∞ for the SIRD model on the configuration model. In the remainder of the paper we will use the notation o p and p −→ in a standard way. Let {X n } n∈U be a sequence of real-valued random variables on a probability space (Ω, P). If c ∈ R is a constant, we write X n p −→ c to denote that X n converges in probability to c. That is, for any > 0, we have P(|X n − c| > ) → 0 as n → ∞. Let {a n } n∈N be a sequence of real numbers that tends to infinity as n → ∞. We write X n = o p (a n ), if |X n |/a n converges to 0 in probability. If E n is a measurable subset of Ω, for any n ∈ N, we say that the sequence {E n } n∈N occurs with high probability (w.h.p.) if P(E n ) = 1 − o(1), as n → ∞.
We assume that there are initially n (s) S,t,d susceptible individuals with social distancing strategy s ∈ S, type t ∈ T and degree d ∈ N. Further, there are n I,d and n R,d infective and recovered individuals with degree d ∈ N, respectively. Hence, we have
and n S + n I + n R = n.
For the initially infected or removed individuals we do not need to know their distribution across types, and only their total number of links (infected linkages) matters for the epidemic dynamics. We only need to know that their initial fraction of converge as the network becomes large. Similarly, we need convergence of the fraction of infected linkages. The type, degree and social distancing strategy distribution only matters for the susceptible individuals.
We now describe the regularity assumptions on individual degrees under individuals type profile t (n) = (t 1 , t 2 , . . . , t n ) and social distancing strategy profile s (n) = (s 1 , s 2 , . . . , s n ) . We assume that the sequence (s, t, d) and the set of initially susceptible, infective and recovered individuals satisfies the following regularity conditions:
(C 1 ) The fractions of initially susceptible, infective and recovered vertices converge to some α S , α I , α R ∈ (0, 1), i.e.
Moreover, α S > 0.
(C 2 ) The degree, type and social distancing strategy of a randomly chosen susceptible individual converges to n (s)
for some probability distribution µ (s) t,d s∈S,t∈T ,d∈N . Moreover, this limiting distribution has a finite and positive mean
and the average degree of a randomly chosen susceptible individual converges to µ S as n → ∞, i.e.
(C 3 ) The average degree over all individuals converges to some λ ∈ (0, ∞), i.e. as n → ∞
and, in more detail, for some λ S , λ I , λ R , the average degrees over susceptible, infective and recovered individuals converge:
(C 4 ) The maximum degree of all individuals is not too large:
Our first theorem concerns the case where λ I > 0 and the initially infective population is macroscopic:
Moreover, the final fraction (probability) of susceptible nodes with degree d ∈ N, type t ∈ T and social distancing strategy s ∈ S satisfies:
We can interpret x (s) * as the probability that a neighbor of a randomly chosen susceptible individual does not get infected during the epidemic. The intuition behind equation (11) is the following: either that neighbor is recovered, with probability given by the first term λ R λ or she is susceptible. In the latter case she has degree d and strategy s with probability proportional to the number of links of these nodes:
as n goes to infinity. To be consistent with the susceptible status of this neighbour, it must be that all its other d − 1 neighbors are susceptible (with probability x (s) * ) or they were removed before interaction (with probability (1 − x
The same intuition applies to (12). To be consistent with the susceptible status of an individual of degree d, type t and strategy s, it must be that all its d neighbors are either susceptible (with probability x (s) * ) or they were removed before interaction (with probability
Our next theorem concerns the case with initially few infective individual, i.e. |I(0)| = o(n) and λ I = 0. Let
This quantity represents the expected number of infective links in the second generation of the epidemic, i.e., the number of linkages of those infected by the initial seed (other than the link from the initial seed). It is these linkages that could propagate the epidemic. Susceptible individuals are reached by the initial seed according to the size biased distribution α S dµ (s) t,d λ that we have seen above, and they are infected with probability 1 − e −β (s) t . In fact, when the initial fraction of susceptible individuals is macroscopic, R (s) 0 characterizes not only the second generation of the epidemic, but every generation in the initial stages of the epidemic. Initially, the contagion process behaves like a branching process, which could either die out or explode. The following theorem states that if R (s) 0 is below 1 then the epidemic will die out and otherwise a positive fraction of the population will become infected.
Theorem 2.4. Suppose that (C 1 ) − (C 4 ) hold and λ I = α I = 0. The followings hold:
0 > 1, , then there exists δ > 0 such that at least δn susceptible individuals get infected with probability bounded away zero.
We end this section by the following remark. Our results in this paper are all stated for the random multigraph G (n) . However, they could be transferred by conditioning on the multigraph being a simple graph (without loop and multiples edges). The resulting random graph, denoted by G (n) * , will be uniformly distributed among all graphs with the same degrees sequence. In order to transfer the results, we would need (see e.g., [Janson et al., 2014] ) to assume that the degree distribution has a finite second moment, i.e.
which from [Janson, 2009b] implies that the probability that G (n) is simple being bounded 11 away from zero as n → ∞. Moreoer, as this is also stated in [Janson et al., 2014] , we suspect that all results hold even without the second moment assumption. [Bollobás and Riordan, 2015] have recently shown results for the size of the giant component in G (n) * from the multigraph case without using the second moment assumption; they prove that even with the small probability that the multigraph is simple, the error probabilities are even smaller.
We now consider heterogeneous SIRD epidemics in percolated random graph G (n) where we first generate the random graph G (n) (by the configuration model) and then vaccinate (remove) individuals at random. Given a probability function ω :
denote the random graph obtained by randomly and independently deleting each individual of type t ∈ T and degree d ∈ N with probability ω t,d . In particular (as an example), for edge-wise vaccination, one vaccinates the end point of each susceptible half edge with some fixed probability ν independently of all the other half-edges. Thus the probability that a degree d susceptible individual is vaccinated will be ω t,
Note that in the case where the social planner does not have information on the types and degrees, degree vaccination, where we vaccinate the nodes with highest degrees, is not possible. Edge-based vaccination is more beneficial compared to random vaccination (see e.g. [Ball and Sirl, 2016, Janson et al., 2014] ).
In general, the total number of individuals vaccinated will satisfy
Since vaccinating an individual would be equivalent to changing its type from susceptible to recovered, our results apply to the number of infected individual after vaccination:
Theorem 2.5. Consider heterogeneous SIRD epidemics in percolated (vaccinated) random graph G (n) . Suppose that (C 1 ) − (C 4 ) hold. Suppose further that each initially susceptible individual with type t ∈ T and degree k ∈ N is vaccinated with probability ω t,d ∈ [0, 1) independently of the others, and let λ I = α I = 0. Let
The following hold:
ω > 1, then there exists δ > 0 such that at least δn susceptible individuals get infected with probability bounded away zero.
In this section we introduce the social distancing game and analyse its equilibrium.
We now consider a network social distancing game in presence of an epidemic risk. We assume that individual i can decide on social activity level s ∈ S := {0, 1, . . . , K} for a payoff π
ti,di , and faces a potential loss i in case it becomes infected. Clearly, deciding in a higher social activity increases the payoff, i.e., π (s) i is strictly increasing in s.
Further, in our baseline model, the government itself might imposes a maximum level of activity K g , so the activity space is S g . For example, all effective strategies will be capped by a level K g and the strategy becomes s ∧ K g . The timeline is as follows: individuals learn their potential loss in case they become infected. This is private information, but the distribution of (type-dependent) losses, denoted by F t , is common knowledge. Individuals then decide on their social activity level. We assume that at time t = 0, all individuals have only partial information about the network. Namely, they do not observe who is connected to whom. The degree-type and epidemic parameter β (s) t are common knowledge. Similarly, they do not know the exact nodes that are initially infected, but only their (asymptotic) fraction.
In the network of size n, we write the utility of (susceptible) node i as
where I (s) (∞) = R (s) (∞)/R(0) denotes the final set of all cumulative infection starting from initial infected seed I 0 and P n (i ∈ I (s) (∞)) is over the distribution of the random graph G (n) of size n, given all nodes' degrees, losses and social activity vector s. As in [Farboodi et al., 2020] , we capture the risk of loosing life or becoming ill together by a single function κ. We refer to κ ti as the fatality probability for an infected individual. Given the loss of life or illness, there is a random loss denoted by i , whose distribution might depend on t i . We say that a social activity across susceptible individuals
Similarly, a social activity profile s * = (s * 1 , s * 2 , . . . , s * n ) is a social optimum if for all
We call parameter x * the global network immunity, because it represents the probability that a susceptible neighbor of a randomly chosen node does not get infected. Then, for a given random network with immunity x, a representative susceptible individual with type t, degree d and social activity s will get infected and face losses with (asymptotic) probability (see Theorem 2.3)
An individual of type t and degree d will get utility u (s) t,d (x) by choosing social distancing strategy s ∈ S. More precisely, her utility is decomposed into the utility from activity, denoted by π (s) t,d and a cost of life loss or path to recovery modeled by a loss random variable (following distribution F t ) and fatality probability κ t . We also assume that κ t = κ t (x * ) depends on network immunity x * . This captures the fact that recovery is impacted by the performance of the health system, which in turn depends on the network immunity and the size of infected population. Note that the utility from social activity depends on the choice of the susceptible individual and also on the overall fraction of individuals choosing to interact.
Given the global network immunity x ∈ [0, 1], the (representative) individual with type t and degree d maximization problem is thus
This can be interpreted as an asymptotic Nash equilibrium when the global network immunity x summarizes the impact of all individuals optimal social activity levels s * t,d . This is a fixed point problem that will be described in the following. Indeed, this is an asymptotic Nash equilibrium because under partial information the limit of P n (i ∈ I (s) (∞)) in (17) depends on the strategies of all other players only through the global network immunity. Therefore, the strategy of each individual will be given by the strategy of the representative individual of her degree and type.
In particular, given global network immunity x, the representative individual prefers the social activity level s over higher social activity level s + 1 if and only if
Let us define for s = 0, 1, . . . , K − 1, the threshold loss functions
14 Note that
are strictly increasing in s and x ∈ (0, 1) makes the denominator positive.
Hence, the representative individual prefers the social activity level s over higher social activity level s + 1 if and only if > (s) t,d (x). In other words, since the loss function follows distribution F t , the fraction of susceptible individuals with type t and degree d which prefer social activity s + 1 over s is given by F t (s) t,d (x) .
(A 1 ) We assume in the following that
Note that the above assumption is only needed if there are more than two social activity levels, i.e. K > 2. Under this condition, the optimal individual's social activity is thresholdtype: follow the social activity level s if and only if ∈ (
(A 2 ) We assume in the following that
The first assumption states that the level of loss where individuals choose to socially isolate is higher than the level of loss where individuals choose activity level 1, and so on for the higher activity levels. The second assumption states that the level of loss where individuals choose to socially isolate is higher when the network immunity is higher. Same holds for all levels of activity. The less the global network immunity, the more susceptible individuals follow social distancing.
We are now ready to describe the asymptotic Nash equilibrium as a fixed point problem.
In the previous section we described the representative individuals' choice given the global network immunity.
Let x e denote the expected global immunity in the random network (expected ratio of infected edges among all the edges). Hence, the representative individual with degree d and type t would choose social activity level s if and only if
So the fraction of individuals with degree d, type t and following social activity level
and we set F t ( (−1) ) = F t (∞) = 1. So we have
On the other hand, given the probability distributionsγ : T × N → P(S), following Theorem 2.3, a node i with type t and degree d will choose social activity s ∈ S as long as
where xγ * is the smallest fixed point in (0, 1) 
Hence, the actual fraction of individuals with type t and degree d following social activity s ∈ S is given by γ
Following the above analysis, for any z ∈ [0, 1], t ∈ T , d ∈ N and s ∈ S, we define
where we set
In the following theorem, we show the uniqueness of (asymptotic) Nash equilibrium for the social distancing game.
Theorem 3.1. Consider a random graph G (n) n satisfying (C 1 ) − (C 4 ). Assume that (A 1 ) − (A 2 ) holds. We have at most one equilibrium, which is given by the solution of the following equation:
The proof of above theorem is provided in Section A.5.
In this section, we assume S = {0, 1} and consider the (extreme) case where a susceptible individual following social distancing s = 0 isolates and cannot get infected at all, i.e., β (0) t = 0 and β (1) t = β t for all t ∈ T . Namely, s i = 1 if node i does not quarantine and s i = 0 if node i quarantines and isolate from the network. Hence, given the network (expected) global immunity x and setting π t,d = π
t,d , a susceptible individual i with type t and degree d will quarantine (isolate) from the network if and only if
In this case, all individuals following the quarantine can be removed from the network and the epidemic goes through all other individuals. This is also equivalent to the individual vaccination (site percolation) model. Let γ t,d denote the fraction of susceptible individuals (in equilibrium) with type t and degree d following quarantine.
Hence, in this case (A 1 )−(A 2 ) are automatically verified and the equilibrium fixed point equations (26)-(27) can be simplified to:
where x γ * is the smallest fixed point in [0, 1] of equation
In Section 4 we will investigate the solution to this equation and give the application to Covid-19 for various network parameters. Let us assume π (0) t,d = 0 ("no joy in isolation"). In this case, the social utility averaged over the population converges to
where, for individuals with type t and degree d, π t,d (1 − γ t,d ) is the total payoff from social activity and κ t (x γ * )
In this section, we consider the previous isolation setup in the case of random regular graphs, where d i = d and t i = t for all nodes i ∈ [n]. Hence, µ t,d = 1, λ = d, λ R = α R d, and we simplify the notations to κ t = κ, β t = β, π t,d = π and F t = F . We use the value at risk notation for the loss distribution
which represents the minimum amount of loss in 100(1 − γ)% worst-case scenarios. The equilibrium fixed point equations are simplified to
where x γ * is the smallest fixed point in [0, 1] of equation
Let us assume again π (0) = 0 and π (1) = π. The social utility averaged over the population converges to
where π(1 − γ) is the total payoff from social activity and κ(x γ * ) 1 γ VaR 1−u (L)du is the average loss faced by the (1 − γ)-fraction of individuals who are not following isolation and therefore are subject to epidemic risk.
The following theorem compares the fraction of self-isolating individuals in the voluntary social distancing equilibrium and the optimum reached by a social planner.
Theorem 3.2. The social planner will choose a larger fraction γ of individuals following isolation than the market equilibrium for any fixed payoff π and fatality rate function κ. Figure 1a varies the link payoff π (this derives the gain form social participation and in the numerical calibration will be taken to equal the value of statistical life). As the network immunity fixed point solution decreases, the final fraction of infected individuals decreases. This is intuitive: all else fixed, as the link payoff becomes larger, less people choose to socially distance and this results into a large scale epidemic. Note the gap between the fraction of individuals who self-isolate in equilibrium versus the social optimum.
In Figures 1b-1c individuals may (1%) overestimate the network immunity as they compute their optimal decision. We plot the final fraction of infected individuals and individuals choosing to self isolate when they have perfect observation of the global network immunity versus when they overestimate the network immunity. Under over-estimation, a lower frac- for ≥ 0 and σ = 100. tion self-isolate and the infection rates are higher. The difference between the two cases can be seen as a value of information that allows people to optimally choose social distancing. Even when payoffs from the linkages are low, an error on the estimated network risk can lead to a large scale epidemics. Remark that around π = 0, and when the immunity is equal to 1, a small fraction of individuals can choose not to self isolate because their impact on overall immunity is small enough and with their over-estimation error, they still believe that the network is fully immune. Indeed, in the case when π = 0 and expected network immunity is one, because all individuals are indifferent, there are infinitely many equilibria. This marks the beginning of the epidemic. Figure 2 shows that, as expected, R 0 is larger in the voluntary social distancing equilibrium (Laissez-Faire equilibrium). We note a strong dependence of the vaccination needs (in order to bring R 0 below 1) on the link payoff. 
In this section we illustrate how our model can be applied to the Covid-19 public health crisis, to model for example a policy response without a strict lockdown, as for example in Sweden or some U.S. states where lockdowns were released early. Note that our voluntary social distancing equilibrium is one in which the population is fully informed or the global contagion probability and decides to socially distance according to their utility. To assess the equilibrium choice in realistic settings we set the parameters of the model to Covid-19 data. In reality, there is enormous uncertainty around the estimation of these parameters and in particular of the infection fatality ratios relevant to our model; Table 1 . We focus on adults, over 20 years old, and study their social distancing decisions. It remains contentious whether children or very young adults act as spreaders. For simplicity, we exclude them, but they can be included as an exogenous fraction of the population with prescribed behavior. The reason why they would be exogenous is that we cannot expect the same decision making process as for adults, and we would have to prescribe their behaviour. Following other studies on Covid-19 and its various policy analyses [Greenstone and Nigam, 2020], we use the U.S. Government value of a statistical life, age-adjusted, [Murphy and Topel, 2006 , Aldy and Viscusi, 2008 , Aldy and Viscusi, 2007 . The idea is to define based on the amount of U.S. dollars that one individual would pay in order to decrease her death probability by 0.1%. This gives a variety of ways to put an amount of utility units for the "inestimable life", and this is how much the individual values her own life rather than output estimates. For example, how much would one invest in safety car features would go into this direction: "Valuation of a statistical life is concerned with valuation of changes in the level of risk exposure rather than the valuation of the life of a specific individual" [de Blaeij et al., 2003] . Note that for the individual decision in our model, the exact VSL is not relevant, but only the change across age groups. Since the VSL encompasses all elements of life utility to a person, then we set π to be a fraction of value of year of statistical life. This fraction, for which we will have a free parameter, represents the part of the VSL that is due to interactions with other people and participation in social life. The following table gives VSL across age groups, assuming $ 6.3 Million statistical life [Murphy and Topel, 2006] . In exercises where the social utility needs to be reported, we will scale the results by 1.5 to the more current (in 2017 U.S. Dollars) VSL of $ 10 Million assumed by the U.S. Government, see [Kniesner and Viscusi, 2019] . Note that assuming that VSL is exogenous, even if we use U.S. Government values, has its limits. VSL does include the economic component, which is impacted by social distancing. It is beyond the scope of our model to capture the economic impact of social distancing. In order to compute the yearly value of statistical life, we set an interest rate r = 3% and we put VSLY = rVSL 1−(1+r) −L , where L is the remaining life expectancy. As Table 2 shows, VSLY is not constant across age groups and VSL has a non-monotonous shape with a peak in the 30 − 39 age group.
For simplicity, we have aggregated across gender and the remaining life expectancy represents an average. We have 7 types in the model, represented by the age groups, as this is the primary factor driving the fatality rates reported in Table 1 . As more information is learned on Covid-19, the types can be made more granular. We consider two social distancing level levels, S = {0, 1}. The yearly value of a statistical life, which we denote VSLY t is the basis for calibration of the payoff π (s) i = π (s) t,d . Namely, we set a free parameter ι, called value of social contact. The part 1 − ι represents the fraction of her yearly value of a statistical life independent on social contact. The part ι that is dependent of social contact is assumed to scale linearly with the number of contacts. Namely, we set the daily gain as
For the loss distribution of type t we choose the lognormal distribution, with typedependent mean parameter m t and constant standard deviation σ, i.e. with density function
, such that the mean satisfies
where we set σ = 3.
Recall that in our model, real time is replaced by interaction time. The relevant quantity is the probability that the constant recovery is longer than the exponential between the arrivals of the Poisson process driving interactions. The other implicit notion of time comes in the decision of the individuals: they balance the risk of loss of life against the short term effects of social distancing. The short term horizon is fixed, assumed to be one day (and with scaling any fixed term horizon). It would be interesting to the short term horizon random, driven for example by the arrival of a cure and the individuals' beliefs over its timing.
Recall that in our analysis, we assumed that the infection time ρ is constant and equal (normalized) to 1. The infected individual with type t dies after time ρ with probability κ t and recovers with probability 1 − κ t . The fatality probabilities given infection are given in table 1. Since the infection time ρ = 1, we replace the infection rates β by ρβ. As in [Alvarez et al., 2020] , we set ρ = 18 reflecting that on average the illness lasts for 18 days. Consistent with estimates in the literature of the average number of people who will contact an infected person R 0 ≈ 4, see [Ferguson et al., 2020] , we set β such that the infected individual has on average 4 contaminations, i.e., we set λ 1 − e −ρβ = 4 =⇒ ρβ = − log(1 − 4/λ) and we leave the distribution of β across types free, such that its average matchesβ.
We will take the degree distribution as power law (Pareto) distribution, with a different shape and scale parameters for each type. Namely, we set
where α t is the shape parameter for type t and δ t is the scale parameter (minimum degree) for type t and C t is the normalization constant for type t. We calibrate this distribution to have the mean m t and variance σ 2 t given in Table 3 , i.e.,
In figure 3 we plot the fraction of individuals who voluntary self-isolate in equilibrium for varying levels of the parameter ι and across age groups. As the social contact as a Figure 3 : Voluntary social distancing equilibrium fraction of individuals following isolation by varying the social contact parameter ι: Here α R = 0, α I = 0.1, α S = 0.9 and κ t (x) = κ t as in Table 1. promotion of value of statistical life increases, and all the rest constant, less people practice social distancing. This is true for all age groups, but the decrease is much more significant for the younger age groups.
We next plot in Figure 4 the fraction of individuals socially distancing, as a function of their hypothesized network immunity. In this exercise, the mortality rates are independent of the epidemic. In green is the equilibrium network immunity, so one can easily read the fractions who socially distance for each age group, ranging from 25% among the 20 − 29 to 73 in the +80 age group. This is close to the social optimum, which results in higher network immunity. Figure 5 illustrates the gap in utility between the social optimum and the voluntary social distancing equilibrium. The utility is expressed in 1.5 million $ / year (accounting for the 1.5 factor, see Table 2 ). The highest gains are for the 30 − 39, 40 − 49 and 70 − 79.
In the next set of results, illustrated in Figures 6 and 7 , we repeat the previous exercise, but with survival rates decreasing as the network immunity decreases, and for example the healthcare system is overwhelmed. The absolute gains in utility are one magnitude larger than before, with the highest absolute gains for the younger cohorts. The equilibrium network immunity is significantly different. However, the relative utility gains are highest for the oldest. of individuals following isolation as a function of expected network immunity: Here α R = 0, α I = 0.1, α S = 0.9, ι = 0.5 and κ t (x) = κ t as in Table 1 . Table 1 . (c) The average utility gain vs. (d) relative utility gain for a representative individual by following social optimal policy vs. voluntary social distancing over different age groups. Here α R = 0, α I = 0.1, α S = 0.9, ι = 0.5 and κ t (x) = exp(1 − x)κ t , so that κ t (1) = κ t is given in Table 1 . (c) The average utility gain vs. (d) relative utility gain for a representative individual by following social optimal policy vs. voluntary social distancing over different age groups. Here α R = 0, α I = 0.1, α S = 0.9, ι = 0.5 and κ t (x) = 8 (1+x) 3 κ t , so that κ t (1) = κ t is given in Table 1 . (c) The average utility gain vs. (d) relative utility gain for a representative individual by following social optimal policy vs. voluntary social distancing over different age groups.
We have studied a heterogeneous SIRD epidemic process when a network underlies social contact. For given social distancing strategies, we have established results on the amplification of the epidemic. Based on the network and the epidemic characteristics we have defined a relevant infection matrix. The network structure -captured by the singular value of the infection matrix -characterizes the amplification effects of the epidemic from the initially infected set to a final set of infected individuals. Quantities such as the epidemic reproduction number R 0 are established and can be used as a warning signal to identify for example parts of the networks that are highly vulnerable. Vaccination and targeted social distancing can be applied in accordance in such areas to make R 0 smaller than one. Next, we have studied the equilibrium of the social distancing game. Our theoretical results establish that the voluntary social distancing will always fall short of the social optimum. The social optimum itself is of course dependent on the type. We calibrate the model to the characteristics of the Covid-19 epidemic, as current in the literature. We note that the gap between the utility in the social distancing equilibrium and the social optimum is due for its most part to the fact that deaths rates given infection have a significant dependence on what fraction of the population is infected, for instance because hospital capacity reach. [Verity et al., 2020] Verity, R., Okell, L. C., Dorigatti, I., Winskill, P., Whittaker, C., Imai, N., Cuomo-Dannenburg, G., Thompson, H., Walker, P. G., Fu, H., et al. (2020) . Estimates of the severity of coronavirus disease 2019: a model-based analysis. The Lancet infectious diseases.
[Warnke, 2019] Warnke, L. (2019). On wormald's differential equation method. Available at https: // arxiv. org/ abs/ 1905. 08928 .
[ Wormald, 1995 ] Wormald, N. (1995 . Differential equations for random processes and random graphs. Annals of Applied Probability, 5(4):1217-1235.
This appendix contains the proofs of all propositions and theorems in the main text.
A.1 Proof of Proposition 2.1
Let p i = P(i ∈ R(∞)/R(0)). Hence, p i = 1 if i ∈ I(0) and otherwise p i ≤ n j=1 B (s) ji p j , which writes for all i = 1, 2, . . . , n as
We thus obtain
The second statement follows using the Markov inequality. Namely, for any k > 0 we have
by the Markov inequality.
Recall that from (39) we have
Let p = [p 1 , p 2 , . . . , p n ] denote the vector with components p i , 1 be the vector with all components equal to 1 and 1 I(0) be the vector with component 1 for i ∈ I(0) and 0 for i / ∈ I(0). By Equation (39), we have
Denoting by || · || the Euclidean norm, we have ||p|| ≤ ||1 I(0) + Bp|| ≤ ||1 I(0) || + ||Bp|| ≤ |I(0)| + λ max (B (s) )||p||.
We thus have for λ max (B (s) ) < 1 that ||p|| ≤ √ |I(0)| 1−λmax(B s) ) . Furthermore by the Cauchx-Schwarz inequality,
We conclude (if λ max (B (s) ) < 1)
n|I(0)|, and the second statement follows using the Markov inequality.
Consider the heterogeneous SIRD epidemics spreading on G (n) satisfying (C 1 ) − (C 4 ). In what follows, instead of taking a graph at random and then analyzing the epidemics, we use a standard coupling argument which allows us to study epidemics and the graph at the same time, revealing its edges dynamically while the epidemic spreads. Consider a vertex i with type t i and d i (labelled) free (not yet paired) half-edges. We call a half-edge type (s, t)-susceptible, infective or removed according to the type of vertex it belongs to. A key step in the proof will be to decide from the beginning on the (random) infection threshold of each susceptible individual, denoted by Θ i for individual i, defined as the (minimum) number of infected neighbor each individual can tolerate before it becomes infected.
Since the (normalized) infection last ρ = 1 days and the meeting happens at rate β (s) t over all edges for a susceptible individual with type t, degree d and following social activity s, it is easy to see that
for θ = 1, 2, . . . , d. Hence, µ
t,d (θ) will be the asymptotic fraction of susceptible individuals with type d, degree d, following social activity s and getting infected after exactly θ infected neighbors. We see that the model is equivalent to (type-dependent) independent threshold model for configuration model.
In the following, we first extend the results of [Amini, 2010 , Amini et al., 2013 , Lelarge, 2012b ] on independent threshold model in configuration model, allowing for heterogeneous types and initial nodes removal. The theorem will then imply Theorem 2.3.
Theorem A.1. Consider the type-dependent independent threshold model with threshold distribution p (s) t,d (θ) for all susceptible individuals with type t, degree d and social distancing s, on random graph G (n) n satisfying (C 1 ) − (C 4 ). Let x (s) * be the largest fixed point solution
We have for all > 0 w.h.p.
and, the final fraction (probability) of susceptible nodes with degree d ∈ N, type t ∈ T and social distancing strategy s ∈ S satisfies:
The proof of above theorem is provided in Appendix B. We now proceed with the proof of Theorem 2.3 using the above theorem with p 
which implies that
as in Theorem 2.3. Moreover, the final fraction (probability) of susceptible nodes with degree d ∈ N, type t ∈ T and social distancing strategy s ∈ S satisfies:
Hence, to prove Theorem 2.3, it only remains to prove there is a unique solution x (s) * ∈ (0, 1) to the fixed point equation x = f (s) (x) which is a stable solution. Note that f (s) (0) > 0 since α S > 0 and f (s) (1) = λ R /λ + λ S /λ = 1 − λ I < 1. Moreover, f (s) (x) is strictly increasing in x which implies there is a unique solution x (s) * ∈ (0, 1) to the fixed point equation x = f (s) (x) and this is a stable solution (since f (s) (x) is strictly increasing).
The proof of Theorem 2.4 is based on Theorem 2.3 and a theorem by Janson [Janson, 2009a] on percolation in random graphs with given vertex degrees. Suppose that (C 1 ) − (C 4 ) hold and λ I = α I = 0. We first show that if R graph have threshold 1, the infection of any individual in the giant component will trigger the infection to whole component which implies Theorem 2.4.
A.5 Proof of Theorem 3.1
We define a function g : [0, 1] → [0, 1] via the following,
It can be easily seen that f γ(z) (0) > 0, f γ(z) (1) < 1. In conjugation with the continuity of x → f γ(z) (x), we conclude that for any z ∈ [0, 1], the set {x : f γ(z) (x) = x} is nonempty and closed, and hence g(z) ∈ (0, 1) is well-defined. Now we show that z → g(z) is decreasing in z, which implies that (28) has at most one solution. Suppose we have 0 < z 1 < z 2 < 1.
We have (set F t
Hence, by using (A 1 ) − (A 2 ), f γ(z) (x) is strictly increasing in x and strictly decreasing function of z (since F is strictly increasing cdf function). So that we have f γ(z1) (x) > f γ(z2) (x) for any x ∈ [0, 1], and f γ(z2) (g(z 1 )) − g(z 1 ) < f γ(z1) (g(z 1 )) − g(z 1 ) = 0.
Combing with the fact that f γ(z2) (0) ≥ 0 and the continuity of x → f γ(z2) (x), there exists an x < g(z 1 ) such that f γ(z2) (x) = x, which implies that g(z 2 ) < g(z 1 ).
Recall that γ e (the equilibrium without social planner) is such that
while the social planner chooses γ s which maximisezū social (γ), i.e. γ s = arg max
Since x γ * is increasing in γ and κ(.) is a decreasing function, κ(x γ * ) is a decreasing function of γ and we havē
and the theorem follows.
In this section we present the proof of Theorem A.1.
We first describe the dynamics of the (independent threshold) epidemic on G (n) as a Markov chain, which is perfectly tailored for asymptotic study. At time 0 the threshold of each susceptible individual is distributed randomly, according to (type dependent) distribution 40. For θ ∈ N, let n At time zero, I(0) and R(0) contains respectively the initial set of infected and recovered individuals. Hence, by (C 1 ), we know |I(0)|/n → α I and |R(0)|/n → α R as n → ∞.
At each step we have one interaction only between two individuals, yielding at least one infected. Our processes at each step is as follows :
• Choose a half-edge of an infected individual i;
• Identify its partner j (i.e. by construction of the random graph in the configuration model, the partner is given by choosing a half-edge randomly among all available 3. B is uninfected of type t, degree d, social distancing strategy s, threshold θ and this is the ( + 1)-th deleted half-edge with + 1 < θ. The probability of this event is Let ∆ T be the difference operator: ∆ T X := X(T + 1) − X(T ). We obtain the following equations for the expectation states variables, conditional on F T (the pairing generated by time T ), by averaging over the possible transitions: 
The initial condition satisfies t,d,θ, (T * ), where T * is the first time that X I (T * ) = 0. In case T * < X(0), the Markov chain can still be well defined for t ∈ [T * , X(0)) by the same transition probabilities. However, after T * it will no longer be related to the epidemic process and the value X I (T ), representing for t ≤ T * the number of alive half-edges belonging to infected individuals, becomes negative. We consider from now on that the above transition probabilities hold for T < X(0).
We will show next that the trajectory of these variables throughout the algorithm is a.a.s. (asymptotically almost surely, as n → ∞ ) close to the solution of the deterministic differential equations suggested by these equations.
Consider the following system of differential equations (denoted by (DE)):
x R (τ ) = − Recall that the number of susceptible vertices with type t ∈ T , social distancing s ∈ S and degree d is n For the arbitrary constant > 0 fixed above, we define the domain D as D = { τ, y K ∈ R b(K )+1 : − < τ < λ/2 − , − < x R (τ ) < λ, − < s (s) t,d,θ, (τ ) < 1}.
The domain D is a bounded open set which contains the support of all initial values of the variables. Each variable is bounded by a constant times n (C 0 = 1). By the definition of our process, the Boundedness condition is satisfied with β = 1. The second condition of the theorem is satisfied by some δ n = O(1/n). Finally the Lipschitz property is also satisfied since λ − 2τ is bounded away from zero. Then by Lemma B.2 and by convergence of initial conditions, we have :
Corollary B.3. For a sufficiently large constant C, we have P(∀t ≤ nσ H (n), Y K n (t) = ny K (t/n) + O(n 3/4 )) = 1 − O(b(K )n −1/4 exp(−n −1/4 )) (56)
uniformly for all t ≤ nσ H (n) where σ H (n) = sup{τ ≥ 0, d(y K (τ ), ∂D ) ≥ Cn −1/4 }.
When the solution reaches the boundary of D , it violates the first constraint, determined byτ = λ/2 − . By convergence of X(0) n to λ, there is a value n 0 such that ∀n ≥ n 0 , 44 X(0) n > λ − , which ensures thatτ n ≤ X(0)/2.
Using (53) and (54) 
where, by Lemma B.1, 
We now study the stopping time T n and the size of the epidemic |R s) (∞)/R(0)|. Consider x * = 1 − 2τ * /λ is a stable fixed point of f (s) (x). Then by definition of x * and by using the fact that f (s) (1) ≤ 1, we have f (s) (x) > x for some interval (x * −x, x * ). Then
is negative in an interval (τ * , τ * +τ ). Let such that 2 < − inf τ ∈(τ * ,τ * +τ ) x I (τ ) and denotê σ the first iteration at which it reaches the minimum. Since x I (σ) < −2 it follows that with high probability X I (σn)/n < 0, so T n /n = τ * + O( ) + o L (1). The conclusion follows by taking the limit → 0.