key: cord-0823183-hqdgho0g
authors: Amini, Hamed; Minca, Andreea
title: Epidemic Spreading and Equilibrium Social Distancing in Heterogeneous Networks
date: 2022-01-04
journal: Dyn Games Appl
DOI: 10.1007/s13235-021-00411-1
sha: b3b920913b8954ea1f241e80beb821da4975038f
doc_id: 823183
cord_uid: hqdgho0g

We study a multi-type SIR epidemic process within a heterogeneous population that interacts through a network. We base social contact on a random graph with given vertex degrees, and we give limit theorems on the fraction of infected individuals. For given social distancing individual strategies, we establish the epidemic reproduction number [Formula: see text] , which can be used to identify network vulnerability and inform vaccination policies. In the second part of the paper, we study the equilibrium of the social distancing game. Individuals choose their social distancing level according to an anticipated global infection rate, which must equal the actual infection rate following their choices. We give conditions for the existence and uniqueness of an equilibrium. In the case of random regular graphs, we show that voluntary social distancing will always be socially sub-optimal.

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 may 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 virus so

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

We will refer to Recovered/Dead as Removed, and that while the distinction between Recovered/Dead is not important for the results of this section, it will become key in Sect. 3. 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. The degree of node i is denoted by d i ∈ N, which represents the number of nodes adjacent to node i (neighbors). Individuals susceptible to the epidemic may become infected through contact with other infected neighbors.

The population is heterogeneous, and individuals can be of different types (e.g., age, sex, blood type, etc.) in a certain countable (finite or infinite) 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 and a higher value of s ∈ S representing higher connectivity. 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 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 It is understood that the network is parameterized 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 their infection period, infects (makes infectious contact 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 that 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 period ρ 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 fatality probability κ t and recovers with probability 1 − κ t . The fatality probability is important for incorporating costs into the model which are key for the game theory part.

Note that if ρ = 1, it suffices to replace the infection rates β by ρβ. We will allow in Sect. 3 the fatality probability to depend on the fraction (number) of infected people during the epidemic process, as the hospital system can be overwhelmed. We assume that the infection rate depends only on the type and strategy of the susceptible party. Implicit is 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.

be a sequence of nonnegative integers (representing the degree of each individual) 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 the 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, and this is done by randomly matching them. When a half-edge of a node i is paired with a half-edge 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., [43, Proposition 7.15] and [21, Theorem 3.1.12] .

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

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 converges 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:

The fractions of initially susceptible, infective and recovered vertices converge to some α S , α I , α R ∈ [0, 1], i.e., as n → ∞,

Moreover, α S > 0. (C 2 ) The degree, type and social distancing strategy of a randomly chosen susceptible individual converges to (as n → ∞) n (s)

for some probability distribution μ 

(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 of susceptible nodes with degree d ∈ N, type t ∈ T and social distancing strategy s ∈ S satisfies (as n → ∞):

We can interpret x (s) * as the probability that a neighbor of a randomly chosen susceptible individual does not get infected during the epidemic. It is then obtained as a fixed point of Eq. (8), where f (s) (x) can be interpreted as the probability that a neighbor of a randomly chosen susceptible individual does not get infected during the epidemic, if the second-order neighbors are independently not getting infected with probability x. In order for any susceptible individual to not be infected, it must be all its neighbors are either not infected (with probability x) or are infected but did not make contact during the infection (with probability (1 − x)e −β (s) t ). If the status of the neighbors are independent, and there are d − 1 such

represents the probability not to be infected. Now consider not any node, but the neighbor of a randomly chosen susceptible individual. Either that neighbor is recovered, with probability given by the first term of Eq. (8) which is λ R λ , or she is susceptible. In the latter case, she has degree d and strategy s with size biased probability dn (s) S,t,d λ S n which converges to α S dμ (s) t,d λ as n goes to infinity. Indeed, we use size biased probability and not μ (s) t,d because we are considering a neighbor of a node and the individuals with degree d are d times more likely to be such neighbors (the likelihood scales linearly with d). We conclude that in the limit, the probability that a neighbor of a randomly chosen susceptible individual does not get infected during the epidemic is a fixed point solution x

The same intuition applies to (9) . 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) or they were removed before interaction (with probability (1−x

represents the probability that a randomly chosen individual with type t and degree d not to be infected (in the limit).

Our next theorem concerns the case with initially few infective individuals, i.e., |I(0)| = o(n) and λ I = 0. This result partly generalizes the result in [31] to the multi-type case with different infection rates depending on social distancing. (As discussed in Sect. 1, their setup is dynamic and homogeneous.) 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.

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., [31] ) to assume that the degree distribution has a finite second moment, i.e.,

which from [30] implies that the probability that G (n) is simple being bounded away from zero as n → ∞. Moreover, we conjecture that all results hold even without the second moment assumption. Indeed, [16] have recently shown results for the size of the giant component in G (n) * from the multigraph case without using the second moment assumption.

We now consider heterogeneous SIR epidemics with vaccination. We assume that vaccination is done before the outbreak and renders individuals completely immune to the disease, meaning vaccinated susceptibles can be treated as removed. The model becomes a 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 halfedges. Thus, the probability that a degree d susceptible individual is vaccinated will be

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 the highest degrees, is not possible. Edge-based vaccination is more beneficial compared to random vaccination (see e.g., [9, 31] ).

In general, the total number of vaccinated individuals 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 individuals after vaccination:

The following holds: This theorem can be obtained as a corollary of Theorem 2.2. Indeed, it suffices to augment the set of removed nodes by the set of vaccinated nodes. The assumptions (C 1 )-(C 4 ) hold with high probability with the new distribution for the susceptible nodes ω t,d 1 − μ (s) t,d . As above, R (s) ω characterizes every generation in the initial stages of the epidemic, but now some individuals have been vaccinated. The epidemic will die out if this quantity is below 1. Since R (s) ω clearly exhibits the contribution of individuals as a function of types, strategy and degree, it offers a simple way to rank these contributions and design a vaccination policy of minimal cost that ensures that the epidemic dies out.

In this section, we introduce the social distancing game and analyze its equilibrium. The game takes place over one period. At time zero, agents make their decisions, and the period ends when the epidemic ends. For simplicity, we assume that all agents keep their decisions constant over the entire period.

We now consider a network social distancing game in the presence of an epidemic risk. We assume that individual i can decide on social activity level s ∈ S := {0, 1, . . . , K } for a payoff π (s) i = π (s) t i ,d i , 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. However,

Further, in our baseline model, the government itself might impose a maximum level of activity K g ≤ K , so the activity space is S g ⊆ S. For example, all effective strategies will be capped by a level K g and the strategy becomes s ∧ K g . At time zero (the beginning of the period), individuals decide on their social activity level based on the following private and public information. Their only private information is their own state and their potential loss in case they become infected during the epidemic. The distribution of the (type-dependent) potential losses, denoted by F t , is public knowledge. Regarding the network, only statistical quantities are public knowledge. Namely, individuals do not observe who is connected to whom and not even their own neighbors, only the degree-type distribution is known. The degree-type and epidemic parameters β (s) t are common knowledge as well. Individuals do not know the exact nodes that are initially infected, but only their (asymptotic) fraction.

We assume that individual i with type t i ∈ T who become infected incur a loss (of say death or serious illness) with probability κ t i . This loss is denoted by i .

We can now define the utility of (susceptible) node i (in the network of size n) as

where

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 [22] , we capture the risk of loosing life or becoming ill together by a single function κ t (x), where t is the type and x is the network immunity parameter. We say that a social activity across susceptible individuals

Similarly, a social activity profile

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

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 the chance of death/severe illness 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

We characterize the strategy of the representative individual as a function of his potential loss (in case of infection). However, the individuals with the same type and degree are allowed to differ in loss. We can interpret the solution to the above maximization problem 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 can be related to mean field models, where the network immunity can be seen as the mean field, aggregating the strategy of all players. 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 (14) 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

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 that prefer social activity s + 1 over s is given by F t

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 of threshold type: follow the social activity level s if and only if ∈ ( 

is continuous and (strictly) decreasing in x.

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; for a fixed social distancing strategy, the loss is higher when the global network health is higher. In other words, the less the global network immunity, the more susceptible individuals follow social distancing.

We end this section by the following remark. The above model is conceived as a one period model, where the social distancing decision is made at the beginning of the period. However, one period may represent a verity of horizons (e.g., one day, one week, one month, etc.). The equilibrium (steady state) of the epidemic is understood as the end of the period. In this case, the result at ∞ represents the end of the period. Note that the network specification is consistent, and the number of links refer to the number of contacts over one period (e.g., one day, one week, etc.) The time of the epidemic is an 'interaction time' and the relation to calendar time is carefully calibrated. It does make sense that for a one period model the decision is kept constant. This is also for tractability reasons. However, it is a very interesting extension to allow for multi-period decision making. In this case, we would need to update the types, degrees and decisions after each period. The myopic optimal decision problem will remain tractable.

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 healthy 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.1, a node i with type t and degree d will choose social activity s ∈ S as long as

Hence, the actual fraction of individuals with type t and degree d following social activity s ∈ S is given by γ (s)

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 existence and uniqueness of (asymptotic) Nash equilibrium for the social distancing game.

There exists a unique asymptotic Nash equilibrium (in the above sense), which is given by the solution of the following equation:

The proof of above theorem is provided in Sect. 4.3. Assuming that n is large but finite, and all the players apply the asymptotic Nash equilibrium actions, it would be interesting to study the approximation of a Nash equilibrium in the finite network. We leave this and some other related issues for a future work.

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 = π (1) t,d − π (0) 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 Eqs. (23)- (24) can be simplified to:

where x γ * is the unique fixed point in [0, 1] of equation

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 γ * ) 1 γ F −1 t (1 − u)du is the average loss faced by the (1 − γ t,d )-fraction of individuals who are not following isolation and therefore are subject to epidemic risk.

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. Let L be a random variable with distribution F.

We use the following inverse cdf 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 γ F −1 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.

The social planner will choose a larger fraction γ of individuals following isolation than the equilibrium for any fixed payoff π and fatality rate function κ.

We now illustrate the results on the simple case of a regular homogeneous network, in which all individuals have the same type and degree. They differ in their potential loss, which is assumed to follow a half-normal distribution. We seek insights into the self isolating policy when individuals over and under-estimate the network immunity. Our results also allow us to investigate how epidemic quantities such as the reproductive number R 0 differ in the voluntary social distancing equilibrium versus the social optimum. Figure 1a varies the link payoff π. (This derives the gain from social participation and in the numerical calibration will be taken to equal the value of statistical life.) As the network immunity fixed point solution increases, 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 that the fraction of individuals who self-isolate in equilibrium is smaller than in the social optimum as long as the link payoff is sufficiently small. When the link payoff is too high, then the equilibrium and socially optimal strategy will coincide, and agree on not socially distancing.

In Fig. 1b , c, 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 fraction self-isolate, and the infection rates are higher. The difference between the two cases can be seen as a value of information that allows individuals 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.

We refer the reader to our companion paper [7] , where we calibrate our model to the Covid-19 epidemic characteristics and provide numerical results on the heterogeneous case. We moreover study how different parameters affect the existence of an epidemic, its final size, and the utilities of the players. The utility of the individuals integrates the value of statistical life: social contact gives them a utility that is proportional to the value of statistical life yearly. When types represent age groups, the application of our model to the heterogeneous case can be used to understand the social distancing strategies across age cohorts. We can then assess the gap between the utility in the social distancing equilibrium and the social optimum across cohorts and derive implications of best type-dependent policies.

Consider the heterogeneous SIR 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 (labeled) 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, μ (s)

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. The independent threshold model is defined by a given (type, degree, social distancing policy)-dependent threshold distribution p (s) t,d (θ ). For each node with type t ∈ T , social distancing strategy s ∈ S and degree d ∈ N, its threshold is drawn independently of everything else from this distribution. Starting from all initially infected nodes with threshold 0, at each step, a susceptible node i becomes infected if at least i neighbors are infected. In the following, we first extend the results of [4, 6, 35 ] on independent threshold model in configuration model, allowing for heterogeneous types and initial nodes removal. The theorem will then imply Theorem 2.1.

We denote by Bin(k, p) a binomial distribution corresponding to the number of successes of a sequence of k independent Bernoulli trials each having probability of success p.

t,d (θ ) for all susceptible individuals with type t, degree d and social distancing s, on random graph G (n)

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 the above theorem is provided in Sect. 5. We now proceed with the proof of Theorem 2.1 using the above theorem with p

In this case, using the binomial theorem, we have

which implies that

as in Theorem 2.1. 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.1, it only remains to prove that there is a unique solution x (s) * ∈ (0, 1) to the fixed point equation

is strictly increasing and continuous in x, which implies there is a unique solution x (s) * ∈ (0, 1) to the fixed point equation x = f (s) (x) . Moreover, this is a stable solution since f (s) (x) is strictly increasing.

The proof of Theorem 2.2 is based on Theorem 2.1 and a theorem by Janson [29] 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 (s) 0 < 1, then the number of susceptible individuals that ever get infected is o p (n). We prove that in the subcritical case, if λ 

Let only look at the structure of the subgraph obtained by removing all nodes with threshold higher than 1. Then, each susceptible individual with type t, social activity s and degree d will remain in the percolated graph with probability

The result of Janson [29] 

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 conjunction 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 (25) 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 a strictly increasing cdf function). Therefore, we have f γ (z 1 ) (x) > f γ (z 2 ) (x) for any x ∈ [0, 1], and

Combining with the fact that f γ (z 2 ) (0) ≥ 0 and the continuity of x → f γ (z 2 ) (x), there exists an x < g(z 1 ) such that f γ (z 2 ) (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 maximizesū social (γ ), i.e.,

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 4.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 (32) .

For θ ∈ N, let n At time zero, I(0) and R(0) contain 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 half-edges); • Delete both half-edges. If j is currently uninfected with threshold θ , and it is the θ -th deleted half-edge from j, then j becomes infected.

Let us define S (s) t,d,θ, (T ), 0 ≤ < θ, the number of susceptible individuals with type t, degree d, social activity s, threshold θ and removed half-edges (infected neighbors) at time T . We introduce the additional variables of interest:

• X S (T ): the number of (alive) susceptible half-edges belonging to susceptible individuals at time T ; • X I (T ): the number of (alive) half-edges belonging to infected individuals at time T ; • X R (T ): the number of (alive) half-edges belonging to initially recovered individuals at time T ;

• X (T ) = X S (T ) + X I (T ) + X R (T ): the total number of (alive) half-edges at time T .

Hence, by Condition (C 3 ), we have (as n → ∞)

Hence, X (0) = n i=1 d i denotes the total number of half-edges in the network and, since at each step we delete two half-edges, the number of existing (alive) half-edges at time T will be

It is easy to see that the following identities hold:

The contagion process will finish at the stopping time T * which is the first time T ∈ N where X I (T ) = 0. The final number of susceptible individual with type t, social distancing s, degree d will be

Then, there are R = R(D, L) ∈ [1, ∞) and C = C(D) ∈ (0, ∞) such that, whenever α ≥ δ min{C, L −1 } + R/n, with probability at least 1 − 2be −nα 2 /(8Cβ 2 ) , we have

where x (t) 1≤ ≤b is the unique solution to the system of differential equations

and σ = σ (ŷ 1 , . . . ,ŷ b ) ∈ [0, C] is any choice of σ ≥ 0 with the property that (t, x 1 (t), ..., x b (t)) has ∞ -distance at least 3e LC α from the boundary of D for all t ∈ [0, σ ).

We apply Lemma 5.2 to the epidemic process described in Sect. 5.1. Let us define, for 0 ≤ τ ≤ λ/2, 

and, using x = √ 1 − 2τ/λ and Eq. (43),

Since x * is the largest solution in (0, 1) to the fixed point equation

We now proceed to the proof of Theorem 4.1. We base the proof on Lemma 5.2. We first need to bound the contribution of higher-order terms in the infinite sums (44) .

Then, there exists an integer , such that

Recall that the number of susceptible vertices with type t ∈ T , social distancing s ∈ S and degree d is n 

Therefore, for n large enough, s∈S t∈T ∞ d= dn (s)

For ≥ 1, we denote

t,d,θ, (τ ) are solutions to a system (DE) of ordinary differential equations. Let

For the arbitrary constant > 0 fixed above, we define the domain D as

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 5.2 and by convergence of initial conditions, we have : 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 ,

n > λ − , which ensures thatτ n ≤ X (0)/2.

Using (45) and (46), we have, for 0 ≤ T = nτ ≤ nτ and n ≥ n 0 : 

where, by Lemma 5.1,

We obtain by Corollary 5.3 that 

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.

We have studied a heterogeneous SIR epidemic process when a network underlies social contact. For given social distancing strategies, we have established results on the amplification of the epidemic. 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 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.

In a companion paper [7] , we calibrate the model to the characteristics of the Covid-19 epidemic. The dependence of the death rates on the fraction of the population that is infected plays a significant role in the gap between Laissez-Faire equilibrium and social optimum.

Several directions emerge from our present study. When vaccines are available but in limited supply and with challenges in distribution, an important question regards the vaccination strategy. The social planner needs to maximize social utility under constraints on vaccine quantity. For a given social distancing strategy of the population, the social planner's optimization problem writes as

The main challenge remains solving a joint equilibrium problem, where agents adapt their social distancing strategy to the vaccination policy and vice versa. In this case, a moral hazard problem may then emerge.

In this paper, we have considered that the degrees are given and agents choose the social distancing strategies. As in [5] (for a different model), we can consider the connectivity choice of every individual as resulting from a network equilibrium, in the presence of contagion risk. Each individual would then choose their connectivity (given all individuals' connectivity) as follows: 

Finally, we have worked in a one-period social distancing game, where individuals keep their strategy constant. In a dynamic version of the game, agents (individuals) may change their strategies over time. We leave this for a future work.

A multi-risk sir model with optimally targeted lockdown

Testing, voluntary social distancing and the spread of an infection

Network security and contagion

Bootstrap percolation and diffusion in random graphs with given vertex degrees

A dynamic contagion risk model with recovery features

Resilience to contagion in financial networks

Cohort effects, voluntary social distancing and life insurance purchases during a pandemic

An sir epidemic model on a population with random network and household structure, and several types of individuals

Evaluation of vaccination strategies for sir epidemics on random networks incorporating household structure

Threshold behaviour and final outcome of an epidemic on a random network with household structure

Analysis of a stochastic sir epidemic on a random network incorporating household structure

Epidemics on random intersection graphs

Approximating the epidemic curve

Survival and extinction of epidemics on random graphs with general degrees

Game dynamic model of social distancing while cost of infection varies with epidemic burden

An old approach to the giant component problem

Graphs with specified degree distributions, simple epidemics, and local vaccination strategies

Epidemics and vaccination on weighted graphs

Mixing patterns between age groups in social networks

Epidemics and rumours in complex networks

Random graph dynamics. Cambridge series in statistical and probabilistic mathematics

Shimer R (2020) Internal and external effects of social distancing in a pandemic

Impact of non-pharmaceutical interventions (npis) to reduce covid19 mortality and healthcare demand

Strategies for mitigating an influenza pandemic

The economics of information security investment

Impacts of game-theoretic activation on epidemic spread over dynamical networks

Social and economic networks

Games on networks. Handbook of game theory with economic applications

On percolation in random graphs with given vertex degrees

The probability that a random multigraph is simple

Law of large numbers for the SIR epidemic on a random graph with given degrees

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

Coordination in network security games: a monotone comparative statics approach

Diffusion and cascading behavior in random networks

Incidence of 2009 pandemic influenza a h1n1 infection in England: a cross-sectional serological study

Protecting against network infections: a game theoretic perspective

Epidemic processes in complex networks

The effect of control strategies to reduce social mixing on outcomes of the covid-19 epidemic in Wuhan, China: a modelling study

Epidemic spreading on complex networks with community structures

Equilibrium social distancing. Faculty of economics

Decentralized protection strategies against sis epidemics in networks

Random graphs and complex networks

Sir dynamics in random networks with heterogeneous connectivity

On wormald's differential equation method

Differential equations for random processes and random graphs

Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations

1. B is infected, the next state is S(T + 1) = S(T ) and X R (T + 1) = X R (T ); 2. B is initially recovered. The probability of this event is X R (T ) X (0)−2T . The changes for the next state will be X R (T + 1) = X R (T ) − 1. 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 isThe changes for the next state will be4. B is uninfected of type t, degree d, social distancing strategy s, threshold θ and this is the θ -th deleted incoming edge. The probability of this event isThe changes for the next state will beLet 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 satisfieswhere 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)):with initial conditions

where x = √ 1 − 2τ/λ and 0 ≤ < θ.

Proof Let u = u(τ ) = − 1 2 ln(λ − 2τ ). Note that u(0) = − 1 2 ln(λ), u is strictly monotone and so is the inverse function τ = τ (u). We write the system of differential equations with respect to u:Then, we haveand by induction, we findBy going back to τ , we haveThen, by using the initial conditions, we find (for 0 ≤ < θ)A key idea to prove Theorem 2.1 is to approximate, following [46] , the Markov chain by the solution of a system of differential equations in the large network limit. We summarize here the main result of [46] .For a set of variables x 1 , ..., x b and for D ⊆ R b+1 , define the stopping timeLemma 5.2 [ [45,46] ] Given integers b, n ≥ 1, a bounded domain D ⊆ R b+1 , functions ( f ) 1≤ ≤b with f : D → R, and σ -fields F n,0 ⊆ F n,1 ⊆ . . . , suppose that the random variables Y n (t) 1≤ ≤b are F n,t -measurable for t ≥ 0. Furthermore, assume that, for all 0 ≤ t < T D and 1 ≤ ≤ b, the following conditions hold:(i) (Boundedness). max 1≤ ≤b |Y n (t + 1) − Y n (t)| ≤ β, (ii) (Trend-Lipschitz). |E[Y n (t + 1) − Y n (t)|F n,t ] − f (t/n, Y 1 n (t)/n, ..., Y n (t)/n)| ≤ δ, where the function ( f ) is L-Lipschitz-continuous on D, and that the following condition holds initially:(iii) (Initial condition). max 1≤ ≤b |Y n (0) −ŷ n| ≤ αn, for some 0,ŷ 1 , . . . ,ŷ b ∈ D.