key: cord-0840951-gcagt8gz
authors: Silva, Olivier Lindamulage De; Lasaulce, Samson; Moruarescu, Irinel-Constantin
title: On the efficiency of decentralized epidemic management and application to Covid-19
date: 2021-06-11
journal: IEEE Control Systems Letters
DOI: 10.1109/lcsys.2021.3087101
sha: 6acea79ba2975d9316840f12aae3689fd566034e
doc_id: 840951
cord_uid: gcagt8gz

In this paper, we introduce a game that allows one to assess the potential loss of efficiency induced by a decentralized control or local management of a global epidemic. Each player typically represents a region or a country which is assumed to choose its control action to implement a tradeoff between socioeconomic aspects and the health aspect. We conduct the Nash equilibrium analysis of this game. Since the analysis is not trivial in general, sufficient conditions for existence and uniqueness are provided. Then we quantify through numerical results the loss induced by decentralization, measured in terms of price of anarchy (PoA) and price of connectedness (PoC). These results allow one to clearly identify scenarios where decentralization is acceptable or not regarding to the retained global efficiency measures.

On the efficiency of decentralized epidemic management and application to Covid-19 * Olivier Lindamulage De Silva 1 , Samson Lasaulce 1 , and Irinel-Constantin Morȃrescu 1 Abstract-In this paper, we introduce a game that allows one to assess the potential loss of efficiency induced by a decentralized control or local management of a global epidemic. Each player typically represents a region or a country which is assumed to choose its control action to implement a tradeoff between socioeconomic aspects and the health aspect. We conduct the Nash equilibrium analysis of this game. Since the analysis is not trivial in general, sufficient conditions for existence and uniqueness are provided. Then we quantify through numerical results the loss induced by decentralization, measured in terms of price of anarchy (PoA) and price of connectedness (PoC). These results allow one to clearly identify scenarios where decentralization is acceptable or not regarding to the retained global efficiency measures.

Index Terms-Game theory; Nash equilibrium; Epidemic; SIR; Covid-19.

I N 2020, many governments around the world had to take drastic measures to mitigate the propagation of the SARS-Cov2 virus. Especially over the first half of 2020, similar measures were taken over large geographical areas such as countries. One major drawback from implementing such a (uniform) policy was that there has been a mismatch between the measure severity level and the local situation. Among the consequences of this mismatch we find: avoidable local economic losses, potentially avoidable psychological damages, frustration, and thus a degradation in terms of measure effectiveness. In 2021, the experience acquired on the pandemic shows that allowing regions (e.g., provinces in China, states in the USA, Länder in Germany, or regions in France) to locally adjust the decisions may be more suited. This is also true when it comes to vaccination. Consequently, different countries adopted different control strategies prioritizing aspects such as education, social welfare, economy, or health. Also within a given country the measures implemented were different for regions depending on the local situation. These measures have been aiming at achieving a certain tradeoff between socio-economic aspects and health aspects. Motivated by this observation, we propose a mathematical model to analyze the effects of decentralization on the epidemic management. In this context, each region or country is a decision-maker. The proposed model is built on existing models such as the networked epidemic models [1] , [2] , [3] , [4, Chapter 9.3] . To assess the potential efficiency loss induced by decentralizing the epidemic management, we consider a mathematical model that is relatively simple while capturing the main effects of interest. This paper considers a strategic-form game which is built from a networked Susceptible-Infected-Recovered (SIR) compartmental model [5] , [6] . Precisely, we consider a game where each player represents a geographical area which decides social-distancing rules which aim at minimizing a cost; this area may typically correspond to a country or a region of a country but it can also correspond to a metropolis or a group of countries. Each individual cost implements a given trade-off between socio-economic losses and health losses. Indeed, the value of the cost for each region not only depend on its actions but also on the actions of neighboring regions through the network structure and the epidemic dynamics. It is noteworthy that the proposed game model is a static or oneshot game model; a player chooses a control action which is fixed over a given finite time horizon. In practice, this action would need to be updated for each epidemic phase. Moreover, each region is assumed to have its own virus transmission rate (e.g., depending on local population density, weather conditions, the effectiveness level of the taken measures); the propagation among regions occurs with an intensity which is given by the cross transmission rates (e.g., depending on the geographic mobility among regions, the sanitary rules imposed by the corresponding neighbors); the population of each node recovers with a fixed recovery rate (e.g., depending on the capacity and performance of the health system [7] ). To the best of our knowledge, the game we introduce in this paper differs from existing works for several reasons. In [8] , the players are the individuals but their decision consist in controlling social distancing with others to find a balance between social interactions and the chances of being infected by the virus that spreads through a single region SIR model. The main differences between the present work and the existing results on networked epidemic games (e.g., [9] , [10] , [11] , [12] ) can be summarized as follows: we consider an SIR model while the existing game models are applied to the networked SIS model (Susceptible-Infected-Susceptible); we control the inter-regions transmission rates while the existing works consider networks described by a binary adjacency matrix; we propose a one-shot game over a finite time horizon unlike the existing works consider infinite time games with constant actions.

Our key contributions can be summarized as follows:

• We formulate a strategic form game applied to a networked SIR model, in which: the interactions are described by a weighted adjacency matrix; a player is a node of the network that tries to minimize its own cost capturing a tradeoff between the socio-economic and health losses; the decision of each player affects the costs of his neighbors in the network; the decision of each player is constant during a finite time horizon (working phase).

• We introduce an operating regime called the Weak Interconnection Regime (WIR), that allow us to conduct the Nash equilibrium (NE) of the considered game, by ensuring existence and uniqueness. Furthermore, this analysis ensures the well-posedness of the two equilibrium efficiency measures considered in this work: the Price of Anarchy (PoA) and the Price of Connectedness (PoC).

This paper is structured as follows. In Sec. II, the considered networked SIR epidemic model is described. The proposed strategic form game model to implement the tradeoff of interest and the chosen measures of global efficiency are provided. In Sec. III, we conduct a complete analysis of the corresponding Nash equilibria (existence, uniqueness). In Sec. IV, we show how the studied game can be exploited numerically for a Covid-19-type-scenario and we discuss the effectiveness of the decentralization strategy on the decisionmaking process.

We consider a set of K > 1 interconnected regions (e.g., provinces, states, or cities) that are affected by an epidemic; the region index is denoted by k ∈ K := {1, . . . , K}. The epidemic propagation within a region is assumed to follow a SIR model. This section provides both the model that we consider for the epidemic dynamics in the presence of interconnected regions (Sec. II-A) and the game proposed to model the fact that the epidemic management is decentralized (Sec. II-B). The proposed game model intends to be simple while capturing a key feature, which is the tradeoff between socio-economic losses, and health aspects.

For Region k ∈ K, we respectively denote by β kk and γ k the virus (endogenous) transmission rate and the removal/recovery rate ( 1 γ k is called the average recovery period). For k = ℓ, the quantity β kℓ denotes the transmission rate from Region ℓ to Region k. The action of Region k on the epidemics is represented by a scalar control action denoted by

The control action u k is assumed to be constant over the time period of interest (working phase) which is the interval [0, T ], T > 0. In this paper, we restrict our attention to the study over a single phase; a phase may typically last few weeks. In practice, the action would need to be updated for each phase. This corresponds to considering a blockwise constant management strategy, which is the easiest to implement in practice. We will denote by u the control action profile or vector: u := (u 1 , . . . , u K ) ∈ U where U := U 1 × . . . × U K and we will also use the notation u −k to refer to the reduced action profile u −k := (u 1 , . . . , u k−1 , u k+1 , . . . , u K ). The fractions of susceptibles, infected, and recovered for Region k are respectively denoted by

With this notation, the continuous-time dynamics for the epidemic in Region k in presence of interconnection is assumed to be given by ∀T ∈ R ≥0 , u ∈ U:

where the initial fractions of susceptibles and infected are chosen as s 0 k > 0 and i 0 k ≥ 0. For the sake of simplicity we assume that the social distancing rules imposed in Region k (namely, u k ) affects uniformly all the infected population of each region in contact with the susceptibles of Region k, i.e., (1 − u k )β kℓ is the controlled rate at which the infected individuals of Region ℓ infects the susceptibles in Region k. In practice, it would be quite difficult to measure its value, or to assign it a prescribed value. Then, we assume policy makers of each region k would apply a social-distancing rule close enough to the abstract quantity u k .

Each region is assumed to seek for a tradeoff between the socio-economic losses and the local health impact of the epidemic, induced by the sanitary rules. This amounts to considering a cost function that comprises three terms. Precisely, we assume that a region aims at minimizing the following composite cost:

where (a k , b k , c k ) ∈ R 3 ≥0 are constant. The reasoning behind this choice is that social-distancing strategies induce both health and socio-economic losses. In particular, we assume the socio-economic cost is a sum of linear and quadratic terms w.r.t the social distancing rules, as motivated in the related literature of optimal control applied to epidemic that spreads in a single Region (see e.g., [13] , [14, Section 2.4] ); this assumption seems to be commonly accepted in economic studies, according to [15, Eq. 8 in Section 2.2.2]. On the other hand, we consider the health losses to be proportional to the final size of the epidemic after a working phase. In particular, the decision of each node has an impact on its neighbors, through the network structure and the epidemic dynamics. The strategic form (see e.g., [16] ) of the static game under consideration is therefore given by:

in which the players (nodes of the network) are the regions of a country (or simply countries); the action space for Player k is given by

] ⊂ (0, 1); the individual cost function of Player k ∈ K is given by J k in (2). Region k ∈ K expresses its interests by setting the triple (a k , b k , c k ), whereas the set of action U k is imposed by a social planner (e.g., a country or an international organization, depending on the nature of the player). In the case where players are countries, we assume that the social planner might be a worldwide organization such as the WHO (World Health Organization). In addition, we emphasize that the theoretical results established in this paper hold for a multistage game setup in which the one-shot game is repeated at each stage (for which the parameters are updated) and different constant control actions are applied during it. In this letter we make the choice not to add a constraint on the region states. For instance, there is no constraint on i k (t, u) to account e.g., for the number of intensive care units (ICU) in a region. To treat the problem in presence of coupling constraints one would need to resort to more advanced notions such as the generalized NE, which is left as an extension of the proposed analysis. Notice that the third term of the cost functions can already be seen as a way of controlling the epidemic and the number of people requiring ICUs.

One of the main objectives of this paper is to assess the potential inefficiencies that might be induced by letting each region choose its control action. A famous and well-used measure of global efficiency is given by the Price of Anarchy (PoA) of a game [17] . Before defining the PoA, let us remind the definition of a Nash equilibrium (NE). An action profile

where U NE is the set of NE of G. The function K k=1 J k is often referred as the social cost of the game. The PoA thus compares the performance of the worst NE to the performance of the centralized solution. Implicitly, the PoA assumes that the social cost is a relevant metric to measure the global performance. In particular, when the PoA is too high the decentralization strategy will not be effective at the risk of observing selfish behavior from Players. To have a second measure of global efficiency, we also introduce the Price of Connectedness (PoC), which is defined as follows:

where J k (u k ) is the cost that Region k would obtain if they do not consider the influence of the network i.e., the crossing transmission rates β kℓ , k = ℓ, would be vanishing in (1). This therefore corresponds to the performance that Region k would expect to obtain by neglecting the interactions with the other regions while these actually exist, hence the term PoC. Such as for the other efficiency measure, we consider that when the PoC is too high Regions should take into account the network structure before taking a decision.

Since one of our main objectives is to measure efficiency at NE through the PoA and PoC in (4)-(5), it is necessary to conduct the complete equilibrium analysis of the NE. This analysis includes the study of the existence and uniqueness of the NE.

In this section, we state our main result concerning the existence of a pure NE. Notice that the existence of a mixed NE is ensured by the continuity of the cost functions J k , k ∈ K (see [16] ), but it is of no practical interest in our setting. The existence of a pure NE is strongly related to the geometrical properties of the cost functions J k , k ∈ K, such as the quasiconvexity properties. Since the dependency of the third term of J k on u k is not explicit, the quasi-convexity analysis of J k appears to be a non-trivial problem. This is the reason why we define a working regime in which it is possible to prove that J k is quasi-convex w.r.t. u k .

Weak Interconnection regime (WIR): The game G is said to be in the WIR, if ∀(k, ℓ) ∈ K 2 : ℓ = k there exists ν β,k > 0 such that β kℓ ≤ ν β,k and J k is quasi-convex w.r.t. u k on U k (i.e, ∀u −k ∈ U −k , ∀λ ∈ R, the lower level set

The motivation behind the definition of the WIR is given by the following result.

Proposition 1: In the WIR the game G has at least one pure NE.

An important practical question would be: "When is the game in the WIR?". To answer this technical question, let us introduce the following working assumption.

Assumption 1: Let ∀(k, ℓ) ∈ K 2 , ρ kℓ := β kℓ /γ ℓ . Condition (i): The matrix B whose entries are given by: B k,ℓ = β kℓ , is non-singular. Condition (ii): ∀k, ∀u, ∀T ∈ T one has that s k (t, u) > 0.

Condition (i) is ensured when B is strictly diagonally dominant (which is often the case in practice because intraregions interactions are much stronger than inter-regions ones); Condition (ii) is trivially satisfied as far as the epidemic does not affect the entire population; Condition (iii) is needed to characterize a bound for the interregions interactions i.e., to quantitatively describe the WIR with ν β,k :=

In what follows, we propose to exhibit a sufficient condition such that the game is in the WIR. To establish the corresponding result, a few notations are in order. Let T ∈ T , u ∈ U and s(T, u) = (s 1 (T, u) , . . . , s K (T, u)) ⊤ , i(T, u) = (i 1 (T, u) , . . . , i K (T, u)) ⊤ , r = (r 1 (T, u) , . . . , r K (T, u)) ⊤ . To be able to express the derivative of s k w.r.t. u k and exploit the implicit function theorem, let us introduce the two square matrices 

Using (6) and [5, Section 2], one can write the following identity: d dt [BΓ −1 (s(t, u) + i(t, u)) − ln(s(t, u))] = 0.

Therefore, by integrating (7) on [0, T ], one has that BΓ −1 (s(T, u) + i(T, u) − x 0 ) = ln(s(T, u)) − ln(s 0 ), where s 0 = s(0, ·), i 0 = i(0, ·) and x 0 = s 0 + i 0 . Let F : U × (0, 1] 2K → R K such that, for any k ∈ K, the k th -component of F is given by F k : U × (0, 1] 2K → R:

We define the set of non-monotonic players as K NM := {k ∈ K : J k is not monotone w.r.t. u k }, (i.e., k ∈ K NM if the assigned weights of socio-economic and health losses are such as J k is non-monotone w.r.t. u k ). Now that we have introduced all the notations needed to establish the main result of this letter, let us exhibit the following key Lemma that provides, ∀k ∈ K, a lower-bound on the derivative of s k w.r.t. u k .

Lemma 1: Under Assumption 1, ∀T ∈ T , ∀u ∈ U and ∀(k, ℓ) ∈ K 2 one has ∂s k ∂u ℓ (T, u) ≥ 0 and

Proof: See Appendix-B.

The following Theorem establishes the main result of this paper, by ensuring that the game G is in the WIR.

Theorem 1: Let T ∈ T . Suppose Assumption 1 holds and the less restrictive action profile u min = (U min 1 , ..., U min K ) ∈ [0, 1) K verifies that, ∀k ∈ K NM , (1 − U min k )s k (T, u min ) ≥ 1 (2ρ kk ). Then, the game G is in the WIR. Proof: See Appendix-C.

The additional condition we introduce means that if the epidemics are sufficiently controlled, then the game G is a quasi-convex game that ensures the existence of a pure NE, according to Proposition 1. In practice, that would mean that the social planner would need to track the regions at least partially (e.g., by imposing some minimum epidemic management measures).

In practice having the uniqueness of the NE may be a useful feature for a government (when players are the regions) or for an international organization (when players are countries). It is typically convenient to be able to predict the outcome of the game. If the game models the interactive situation sufficiently well, an NE can be effectively observed. If there is only one NE, the situation becomes predictable, which is not the case in the presence of multiple equilibria. It is known that uniqueness typically requires additional conditions ( [16] ). The following result establish the uniqueness property of the NE, and the convergence of the sequential best-response dynamics.

Theorem 2: Suppose that ∀k ∈ K,

Then G has a unique NE, and the sequential best-response dynamics converges to this equilibrium.

Proof: See Appendix-D.

We should note that, if the conditions of Theorem 1 hold for all k ∈ K, then J k is strictly convex w.r.t. u k that is,

Here, the additional condition of Theorem 2 requires that the dependency of the second derivative of J k w.r.t. the control actions of the other regions is sufficiently small. The latter is both useful to predict the epidemic tendency when its management is decentralized and to compute the NE (so the PoA and PoC).

Remark. If the game is not in the WIR but K NM = ∅, the costs J k are all individually quasi-convex and the existence of a pure NE is ensured. Moreover, there is a unique pure NE which lies at the extreme of the interval U, in particular whatever the values of β kℓ .

IV. NUMERICAL PERFORMANCE ANALYSIS The goal of this section is to quantify the PoA and PoC numerically for a Covid-19-type scenario. The proposed methodology can be applied to other epidemic scenarios where multiple regions are involved. Motivated by a scenario which has been studied by the French government in May 2020. We assume that France is divided in K = 5 regions and we propose to observe the influence of the inter-region virus transmission rates β kℓ on the PoA and PoC. To choose the epidemic's parameters, we have exploited the studies on Covid-19 that have been conducted in [14] , [18] , [19] . We assume that: Regions k ∈ {1, 2} have selected the weight a k , b k and c k such that only the socio-economic losses matter; Regions k ∈ {3, 4, 5} weighted the weights of each of the losses such that K NM = {3, 4, 5}; see the Table I . The time horizon of the considered epidemic phase is set to T = 30 days [20] , [21] , [22] . The coupled SIR model is implemented by using the Matlab ODE45 solver with the Runge-Kutta scheme. The action space is chosen by the social planner such as: ∀k ∈ K, U max Table 6 -8]. By applying an exhaustive search to find the NE and the social optimal, we show in Fig. 1 and 2 the interpolation of the PoA, PoC w.r.t β kℓ , ∀k = ℓ. Each curve corresponds to a scenario where all incoming transmission rates from a given region vary uniformly (i.e.,∀ℓ = k, β kℓ ∈ {0, 1 · 10 −3 , . . . , 1.2 · 10 −2 }), whereas the other transmission rates are fixed at the threshold value ν β,k . We observe that the PoA can be as large as 1.2 for crossing rates greater than 0.2%. Therefore, the outcome in this case is that the social planner should not decentralize the decision making. We emphasize that, when β kℓ ≥ ν β,k the simulation does not fit into our theoretical setup. The PoC measures the impact of ignoring the connection with other regions is even larger and reaches values as large as 3, which shows that a region has a strong interest in accounting for the crossing rates to manage the epidemic locally. u NE = Nash equilibrium strategy; u opt = optimal centralized strategy; u min = less restrictive policy.

In view of the weights a k , b k , c k given in the Table I , a natural question should be raised: "How is the epidemic spreading in the regions k ∈ {3, 4, 5}?" Fig. 3 shows the evolution over the time of i k , for k ∈ {3, 4, 5}, when different strategy is considered and ∀k = ℓ, β kℓ = ν β,k . Quantitatively we observe that: when either the NE or optimal strategy is applied, the maximum proportion of infected in Regions k ∈ {3, 4, 5} is less that 0.94%, i.e. if the population sizes in Regions k ∈ {3, 4, 5} are similar to the region "Île-de-France", then the infected proportions are upper-bounded by 112 800 cases, when policy-makers apply either NE or centralized strategy.

The conducted Nash equilibrium analysis of the proposed game largely relies on the individual quasi-convexity of the cost function of a region. Because one cannot express the state of the fraction of "susceptibles" as a function of the control actions, this analysis turns out to be non-trivial. We exhibit a regime in terms of coupling degree among the regions in which existence is guaranteed; this regime appears to be non-limiting for real scenarios. The numerical analysis allows one to clearly quantify what is lost when regions or countries decide by themselves the way to manage the epidemic locally, without coordination. The proposed approach might be improved e.g., by integrating coupled constraints, by investigating a dynamical game formulation of the problem, or by performing a deeper numerical analysis on the impact of the graph on the price of anarchy and the price of connectedness.

Since the action space of each player U k is a convex, compact and non-empty set; the costs J k are jointly continuous that is continuous w.r.t. the action profile u ∈ U; the costs J k are quasi-convex w.r.t. u k on U k . Then, the game G is a quasiconvex game. By Debreu-Fan-Glicksberg theorem for quasiconvex games [16, Theorem 50] , the existence of a pure NE is guaranteed.

Let k ∈ K, u ∈ U, T ∈ T and, X := u, s(T, u), i(T, u) ∈ U × (0, 1] K × (0, 1] K such that F (X) = 0. In what follows, we denote by: We denote by ∂s ∂u (T, u) the approximation of ∂s ∂u (T, u) at the first order of the Neumann series, such that, ∀k, ℓ, ∂s ∂u (T, u) := I K + DBΓ −1 D ∂F ∂u (X). Therefore, ∀k, ℓ, ∂s k ∂u ℓ (T, u) ≥ ∂s k ∂u ℓ (T, u) ≥ 0, since Condition (iii) of

Epidemic processes in complex networks

The role of asymptomatic individuals in the Covid-19 pandemic via complex networks

Directed-graph epidemiological models of computer viruses

Graph theoretic methods in multiagent networks

Final size of an epidemic for a two-group SIR model

On the dynamics of deterministic epidemic propagation over networks

A closed-loop framework for inference, prediction and control of SIR epidemics on networks

Contact rate epidemic control of COVID-19: an equilibrium view

Game-theoretic vaccination against networked SIS epidemics and impacts of human decision-making

Protecting against network infections: A game theoretic perspective

Complete game-theoretic characterization of SIS epidemics protection strategies

Decentralized protection strategies against SIS epidemics in networks

COVID-19 and flattening the curve: A feedback control perspective

Analysis of the tradeoff between health and economic impacts of the Covid-19 epidemic

COVID-19 pandemic control: balancing detection policy and lockdown intervention under ICU sustainability

Game theory and learning for wireless networks: fundamentals and applications

Algorithms, games, and the internet

Can the COVID-19 epidemic be controlled on the basis of daily test reports?

Estimating the burden of SARS-CoV-2 in France

Open stats coronavirus Covid-19 statistiques/France

Sortie progressive de confinement prerequis et mesures phares. Conseil scientifique Covid-19

Transport effect of COVID-19 pandemic in France

Oligopoly pricing: old ideas and new tools

Existence and uniqueness of equilibrium points for concave n-person games

Assumption 1 holds. The lower bound of ∂s k ∂u k (T, u) given in Lemma 1 corresponds to ∂s k ∂u k (T, u).

The goal of this proof is to ensure that ∀k ∈ K, J k is quasi-convex w.r.t u k ∈ U k . We know that, ∀k ∈ K \ K NM , J k quasi-convexity property holds. In what follows, we are interest in to show the convexity of costs J k for Players k ∈ K NM . Therefore, we propose to analyze in a first step the convexity of i k w.r.t u k , which allows us to discuss about the concavity of s k w.r.t u k for k ∈ K NM .Let k ∈ K NM , u ∈ U, T ∈ T and X := u, s(T, u), i(T, u) ∈ U × (0, 1] K × (0, 1] K such that F (X) = 0. By following the same reasoning as in Lemma 1, we apply the implicit function theorem to the function F :Let us write the second derivative of i k w.r.t. u k , . By combining with the lower-bound of ∂s k ∂u k given in Lemma 1, weIn view of the condition given in Theorem 1, it follows that G k (u min ) ≤ 0 u) dt, it follows from the Leibniz's rule for differentiation under the integral sign thatTo conclude this proof, ∀k ∈ K, J k is quasi-convex then by definition the game G is in the WIR.

According to [24, Section 2.5-2.6], a sufficient condition to ensure the contraction of the Best-response mapping given by, BR(·) = argmin u∈U1 J 1 (u, ·), . . . , argmin u∈UK J K (u, ·) is to verify the strict diagonal dominance condition, which yields that:Hence, according to [25, Theorem 2 and Theorem 6] , the diagonally strictly convexity (DSC) condition is verified that ensures the uniqueness of the NE. Moreover, in view of [24, Section 2.5], the sequential best-response algorithm converges to the unique Nash equilibrium of the game G.