# temporal_vaccination_games_under_resource_constraints__53f2a269.pdf

Temporal Vaccination Games under Resource Constraints

Abhijin Adiga and Anil Vullikanti ,

Network Dynamics and Simulation Science Laboratory, Biocomplexity Institute of Virginia Tech Department of Computer Science, Virginia Tech {abhijin, akumar}@vbi.vt.edu

The decision to take vaccinations and other protective interventions for avoiding an infection is a natural game-theoretic setting. Most of the work on vaccination games has focused on decisions at the start of an epidemic. However, a lot of people defer their vaccination decisions, in practice. For example, in the case of the seasonal flu, vaccination rates gradually increase, as the epidemic rate increases. This motivates the study of temporal vaccination games, in which vaccination decisions can be made more than once. An important issue in the context of temporal decisions is that of resource limitations, which may arise due to production and distribution constraints. While there has been some work on temporal vaccination games, resource constraints have not been considered. In this paper, we study temporal vaccination games for epidemics in the SI (susceptible-infectious) model, with resource constraints in the form of a repeated game in complex social networks, with budgets on the number of vaccines that can be taken at any time. We find that the resource constraints and the vaccination and infection costs have a significant impact on the structure of Nash equilibria (NE). In general, the budget constraints can cause NE to become very inefficient, and finding efficient NE as well as the social optimum are NP-hard problems. We develop algorithms for finding NE and approximating the social optimum. We evaluate our results using simulations on different kinds of networks.

Introduction

Despite a lot of progress in medical diagnostics and pharmaceutical tools, infectious diseases remain a major challenge for governments all over the world. Even the annual influenza epidemic in the US has a significant social and economic burden, which is estimated to exceed $87.1 billion (e.g., (Molinari et al. 2007)). For many diseases, especially the annual influenza, there exist vaccines, though their efficacy might be quite variable. However, taking a vaccine has a cost (economic cost, inconvenience and health effects). Further, an individual can get protected without any intervention if enough other people he/she comes in contact with in the population are protected this is referred to as herd immunity in mathematical epidemiology, and is a natural setting for a game-theoretical analysis. This has been a very

Copyright c 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

active area of research both in epidemiology and network security, e.g. (Bauch and Earn 2004; Grossklags, Christin, and Chuang 2008; Khouzani, Sarkar, and Altman 2011; Reluga and Galvani 2011; Saha, Adiga, and Vullikanti 2014); see the related works section for a more detailed discussion. In practice, most people do not take a preventive vaccine before the start of the epidemic, and instead wait for some time. Often, the vaccination rate grows with the epidemic outbreak rate. There are many different and complex reasons for vaccination decisions being made at different times, and understanding this remains a big open problem, as well as an important public health issue. Almost all the work on vaccination games only considers vaccination decision made only at the start of the epidemic, in a simultaneous game setting. The only studies on temporal vaccination are by (Reluga and Galvani 2011; Adiga, Venkataramanan, and Vullikanti 2016). The work by (Reluga and Galvani 2011) uses a differential equation approach, which assumes simplified and homogeneous connectivity among individuals. We build on the approach of (Adiga, Venkataramanan, and Vullikanti 2016), which studies this as a repeated game on a network, in the SI (Susceptible-Infectious) model of epidemics. They characterize Nash equilibria in such games, and show that these exhibit interesting temporal structure, such as a large fraction of nodes defer their vaccination decisions. An important open question from their work is the effect of resource constraints they assume there are no bounds on the number of individuals who can get vaccinated at any time, and this is reflected in the solutions they find. In practice, there are important resource constraints of various kinds, e.g., capacity of hospitals and pharmacies in administering vaccines, or the production capacity see e.g., (CDC ; Orenstein and Schaffner 2008). In this paper, we study the temporal vaccination problem with resource constraints at different times. Our main contributions are:

1. We formalize the temporal vaccination game with resource constraints, BUDGETTEMPVACC, as a multi-stage game on a network, and study the structure of Nash equilibria (NE) in such games. There can be multiple NE even when the network of interactions is a tree, and finding one with the minimum cost is NP-complete.

2. We show that many nodes defer their vaccination deci-

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

sions, and the budget constraints lead to very significant differences from the solution of (Adiga, Venkataramanan, and Vullikanti 2016). Specifically, there exist families of instances, where small changes in the budgets (while keeping all other components of the problem fixed) lead to very high inefficiencies. Further, unlike their formulation (in which there is no need to consider more than two time steps), we find that there can be nodes that choose to vaccinate at each possible time step.

3. Computing the social optimum turns out to be a challenging optimization problem. We show that it is NP-hard to approximate within a factor of O(nα) for any α (0, 1), without violating any budget constraints. For the special case of BUDGETTEMPVACC, with only two times at which vaccination decisions are made, we design an algorithm that approximately satisfies the budget constraints.

4. We study the characteristics of NE in different kinds of networks experimentally. We use best response strategies, and find that they usually converge to NE quickly. Corroborating our theoretical results, we find very high sensitivity of the solution cost, as well as the number of nodes that defer vaccination decisions, to the budget constraints and vaccination delays.

Some of the details, including proofs and experimental results have been omitted from this abstract, because of space limitations. They are presented the full version (Adiga and Vullikanti 2015).

Preliminaries and Model We extend the approach of (Adiga, Venkataramanan, and Vullikanti 2016) and formally define BUDGETTEMPVACC as a repeated game on an instance (G, p, T , B, C, L) in the following manner:

1. V is a set of n = |V | players, who form the nodes of a graph G = (V, E), with an edge (u, v) E if the epidemic can spread from u to v;

2. pi = Pr[source of infection is node i], with

3. T = {t0 = 0, , tk} is a set of time instants, at which the vaccination decisions will be made;

4. B = {Bt | t T } specifies the vaccination budget, where Bt is the number of vaccines allocated for time t;

5. C = {Ct v | v V, t T } is the set of vaccination costs,

6. L = {Lv | v V } is the set of infection costs.

Epidemic model and strategies. We assume nodes are in Susceptible (S) and Infectious (I) states, and the epidemic spreads according to a simple discrete time SI (Easley and Kleinberg 2010). In this model, if node v gets infected at time t, each uninfected neighbor u will be infected at time t + 1, unless it gets vaccinated. The vaccine is assumed to have 100% efficacy, and starts protecting the node immediately after taking it. A node s strategy is to decide if and when to get vaccinated. The strategy of node v at time 0 (before the source of the infection is known) is denoted by Y (v, , 0) {0, 1}, with Y (v, , 0) = 1 if v gets vaccinated at time 0. The source of the infection is known after time t = 0, and

t = 0 t = 2

vaccinated source

Figure 1: Example NE: Uniform vaccination cost C = 0.5 and infection cost L = 1 for all nodes, T = {0, 2}, p2 = 0.5, p3 = 0.5, B0 = 3, B2 = 2.

Y (v, s, t) denotes the strategy of node v at time t given that the source of infection is s. If node v gets vaccinated at time t, it incurs a cost Ct v, whereas if it gets infected at any time, it incurs a cost Lv. Throughout, we assume that Lv > Ct v for all t, so that it is always cheaper to get vaccinated, instead of getting infected. The complete strategy vector is denoted by Y ( ), and the expected cost associated with it is denoted by cost(Y ). Example. Fig. 1 shows an example where Y (1, , 0) = Y (6, , 0) = Y (7, , 0) = 1 and Y (v, , 0) = 0 for v = 2, 3, 4, 5. For t = 2, Y (4, 2, 2) = Y (5, 2, 2) = 1 and Y (v, s, 2) = 0 for all other v and s combinations. Note that if node 1 decides to become insecure, then, the cost incurred is p2L+p3C > 0.5 = C. The same holds for 6 and 7. At t = 2, if 2 is the source, then only 4 and 5 can be saved, while if 3 is the source, none can be saved. By definition no other node can be the source. Resource constraints. We assume at most Bt people can be vaccinated at time t this can capture resource constraints, e.g., due to production or distribution limits. Therefore, a strategy vector Y ( ) is feasible if for any time t: (1)

v Y (v, , 0) B0, if t = 0, and (2)

v Y (v, s, t) Bt, for any source s. Let F denote the set of all feasible strategy vectors. Stages of BUDGETTEMPVACC. This involves the following rounds:

1. At time t = 0, all the nodes play a simultaneous vaccination game to decide whether to get vaccinated or not. As mentioned earlier, the vaccination takes effect immediately. If node v gets vaccinated at this time, we denote this by Y (v, , 0) = 1. As mentioned above, at most B0 nodes can get vaccinated at this time, so that

v Y (v, , 0) B0.

2. A randomly chosen node s V is selected to be the source of the epidemic. We assume that if Y (s, , 0) = 1, it remains immune, and the infection does not spread. If Y (s, , 0) = 0, then s gets infected and the infection spreads to each uninfected neighbor in subsequent times. We also assume perfect information, so all nodes know about the source s.

3. For each t = 1, 2, . . ., we have the following two steps: (a) If t T , a simultaneous vaccination game is played at time t, and each node v decides whether to get vaccinated

at this time or not this is denoted by Y (v, s, t) {0, 1}, with 1 denoting vaccination and s the source. Further, for feasibility, we have v Y (v, s, t) Bt. (b) Let It 1 denote the set of nodes which are infected at time t 1. For each node u It 1, each uninfected neighbor v N(u) will get infected at time t, (i.e., v It 1), unless v gets vaccinated at or before time t. Recall that vaccination takes precedence over infection in our model. Define set It = It 1 {v : v gets infected at time t} to be the set of all infected nodes till this time. 4. The game stops at time t if there are no more uninfected nodes that can be infected from their neighbors, and t T for all t t (i.e., there are no more vaccination games to be played). Each node v incurs cost Lv if it ever got infected, i.e., v It. It incurs cost Ct v if it got vaccinated at time t t. The overall cost for node v is the expectation over all possible choices of the source.

Cost of a feasible strategy. For every Y F, we define the cost incurred by v V (G) given strategy Y as: cost(v, Y ) = C0 v Y (v, , 0) +

T T CT v Y (v, s, T) + Lv I(v, s, Y ) , where I(s, v, Y ) = 1 if v gets infected due to s in the strategy Y . We define cost(Y ) = v cost(v, Y ). Nash equilibria and social optimum. For a strategy profile Y ( ), let Y v( ) be the strategy profile for all the remaining players. We say that a strategy Y ( ) is a Nash equilibrium (NE) (Leyton-Brown and Shoham 2008) if for each v V : cost(v, Y ) cost(v, Y ) where Y is any strategy profile such that Y v( ) = Y v( ), i.e., Y ( ) has the same strategies as Y ( ) for all other players v = v. In other words, no player v can reduce its expected cost by unilaterally changing its strategy, given that the other players strategies are fixed. We define the social optimum as a strategy Y ( ) that has the minimum cost, over the space of all possible strategies this is not necessarily (and is not usually) a pure NE. Therefore, the cost of a pure NE relative to the social cost is an important measure, and the maximum such ratio over all possible pure NE is known as the price of anarchy (Koutsoupias and Papadimitriou 1999). Source probability. For simplifying our discussion, henceforth, we will assume that the source is chosen uniformly at random, i.e., ps = 1

n for all s V . Most of our results extend to general source distributions.

Characterization of Nash Equilibria First we will define valid strategy. Definition 1. A strategy Y is valid if it satisfies the budget constraints, i.e.,

v Y (v, , 0) B0 and t T \ {0},

v Y (v, s, t) Bt. From the definition of BUDGETTEMPVACC, Y (v, s, T) = 1 implies that a vaccine is reserved for node v if s is the source. However, even if s is the source, it is possible that it is secure (i.e., Y (s, , 0) = 1) or the infection never reaches v (because of other nodes that chose to be vaccinated at time T). In both cases, v will not incur the cost of Cv/n. This notion has important implications for the structure of NE, in the

sense that it does not hurt a node v to choose Y (v, s, T) = 1 if the budget constraints allow for this. We now discuss a characterization of the pure NE for BUDGETTEMPVACC for the special case where T = {0, T}. We start with some definitions. Let G[V ] be the subgraph of G induced by the set V of nodes. Let V0(Y ) = {v : Y (v, , 0) = 1} and Vs(Y ) = {v : Y (v, s, T) = 1} be the sets of nodes that are vaccinated at time 0 and time T when the source is s, respectively. Let C(v, G ) be the connected component containing node v in the graph G . For v, s V , let I(v, s, G[V V0(Y ) Vs(Y )]) = 1 if s C(v, G ), Y (v, , 0) = 0 and Y (s, , 0) = 0, i.e., I( ) is the indicator of the event v will be infected if s is the source. Let d(x, y, G) denote the distance of x from y in G. Let A(v, Y ) be the set of potential sources s for which it is still possible for node v to get vaccinated at time T, i.e. A(v, Y ) = {s | Y (v, s, T) = 0, |Vs(Y )| < BT , d(v, s, G[V V0(Y ) Vs(Y )) T, I(v, s, G[V V0(Y ) Vs(Y )]) = 1}.

Lemma 2. Consider an instance (G, p, T = {0, T}, B, C, L) of BUDGETTEMPVACC. A valid strategy Y ( ) is a pure NE iff

1. If Y (v, , 0) = 0 then either (a)

s I(v, s, G[V V0(Y ) Vs(Y )]) Lv

n Cv or (b) |V0| = B0. 2. If Y (v, , 0) = 1 then the following conditions hold: (a)

s I(v, s, G[V V0(Y ) Vs(Y ) {v}]) Lv

n > Cv, and (b) s V A(v,Y ) I(v, s, G[V V0(Y ) Vs(Y )) Lv

3. If Y (v, s, T) = 0 and Y (v, , 0) = 0 then either (a) I(v, s, G[V V0(Y ) Vs(Y )]) = 0 or (b) |Vs(Y )| = BT .

The proof is in the full version (Adiga and Vullikanti 2015).

Existence and Complexity of finding NE In this section, we first propose a best-response algorithm to compute NE (if it exists) for the special case T = {0, T}. This will be followed by results on minimum cost pure NE and the price of anarchy. Best response strategy: Consider an instance (G, p, T = {0, T}, B, C, L) of BUDGETTEMPVACC.

1. We start with a feasible strategy Y ( ) (one possibility is to start with all nodes insecure).

2. If there exists node v such that Y (v, , 0) = 0 and

s I(v, s, G[V V0(Y ) Vs(Y )]) Lv

n > Cv, then:

(a) If |V0| < B0, then switch the strategy of node v: set Y (v, , 0) = 1. Set Y (v, s, T) = 0 for all s. (b) If |V0| = B0: For each s A(v, Y ), we set Y (v, s, T) = 1.

3. If there exists node v such that Y (v, , 0) = 1 and

s V A(v,Y ) I(v, s, G[V V0(Y ) Vs(Y ) {v}]) Lv

n Cv, we switch the strategy of node v and set Y (v, , 0) = 0. Then, for s A(v, y), we set Y (v, s, T) = 1.

When there are no budget constraints a pure NE need not exist (Adiga, Venkataramanan, and Vullikanti 2016). However, for BT = 0 and uniform vaccination and infection costs, it

can be shown that the best response strategy always converges to a pure NE. The proof is based on a potential function argument by (Aspnes, Chang, and Yampolskiy 2006), where they prove the same result for the special case where B0 is unbounded. The same proof holds for B0 < n. Lemma 3. For an instance of BUDGETTEMPVACC, where (1) T = {0, T}, and (2) vaccination and infection costs are uniform for all the nodes (i.e., there exist c, L such that Cv = C and Lv = L for all v V ), and (3) BT = 0 for all t T , the above algorithm converges to a pure NE. In Experimental Results section, we discuss the performance of the best response strategy on several networks. Minimum cost NE. By a reduction from the Firefighter problem (Finbow et al. 2007), we showed that it is hard to compute the minimum cost NE. Lemma 4. Finding a minimum cost pure NE is NP-complete even on instances of BUDGETTEMPVACC where G is a tree. The proof is in the full version (Adiga and Vullikanti 2015). Price of anarchy (Po A). When there are no budget constraints, it was shown in (Adiga, Venkataramanan, and Vullikanti 2016) that the price of anarchy can be Ω(n). Clearly this holds for BUDGETTEMPVACC as well. However, with the budget constraints, the Po A is Ω(n) even for trees. Lemma 5. There exist instances I = (G, p, T , B, C, L) of BUDGETTEMPVACC, where G is a tree with root s, ps = 1 and B0 = 0 for which the price of anarchy is Ω(n).

Effect of budget constraints We now show that the budget constraints have a very significant impact on the cost of a NE, as well as on the social optimum. Lemma 6. There exist instances I = (G, p, T , B, C, L) of BUDGETTEMPVACC, for which there exist strategies Y ( ) and Y ( ) such that: 1. Y ( ) is a NE for I that satisfies the budget constraints, 2. Y ( ) is a NE for the instance I obtained by removing all the budget constraints for T = 0 in T in instance I (i.e., setting BT = for all T T , T = 0), and 3. cost(Y )/cost(Y ) = Θ(n). The proof is in the full version (Adiga and Vullikanti 2015). Extending the instance constructed in the above proof, we can see that in the absence of budget constraints, for each random source s, all nodes at distance T from s choose to get vaccinated, where T = min{t T : t > 0} is the first time in T when the vaccination decisions can be made. As a result, it suffices to consider only one time step in T at which the vaccination game needs to be played, as was observed in (Adiga, Venkataramanan, and Vullikanti 2016). In contrast, because of the budget constraints in an instance of BUDGETTEMPVACC, vaccination decisions might be made in each round. Further, nodes far away from the source might choose to get vaccinated, which might cause a large outbreak. Further, it does not help to increase the budget at time t = 0 alone, as discussed in the next lemma.

Lemma 7. There exist instances I = (G, p, T , B, C, L) of BUDGETTEMPVACC, with B0 = , for which removing the budget constraint BT (i.e., setting BT = ) can reduce the cost of NE by a factor of Θ(n).

Finding the social optimum Since BUDGETTEMPVACC generalizes the formulation studied in (Adiga, Venkataramanan, and Vullikanti 2016), it is easy to verify that finding the social optimum is NP-complete. We show that even approximating the social optimum of BUDGETTEMPVACC is very hard. This motivates bicriteria approximation algorithms, in which the budget constraints can be violated. Theorem 8. The social optimum of an instance (G, p, T , B, C, L), of BUDGETTEMPVACC cannot be approximated within a factor of nα in polynomial time for α (0, 1), unless P = NP. The proof is by a reduction from a game-theoretic version of the Fire Fighter problem studied in (Anshelevich et al. 2009) (see in the full version (Adiga and Vullikanti 2015)).

Bicriteria Approximation Algorithm Approximating the social optimum. We now discuss an approximation algorithm for computing the social optimum for the special case of T = {0, T}. Our algorithm builds on (Hayrapetyan et al. 2005), and involves a linearprogramming (LP) rounding approach. We use the following notation below: (1) x(j, s) is an indicator variable, which is 1 if node j gets infected due to source s; (2) y(j) is an indicator which is 1 if node j is vaccinated at time 0; (3) y(j, s) is an indicator which is 1 if node j is vaccinated at time T, when the source is s; (4) P d(s, j) is the set of paths from s to j of length d; (5) P <d(s, j) is the set of paths from s to j of length less than d. We now describe an integer programming formulation P for the social optimum below. Let, f(x, y) =

v C0 vy(v) + 1 n

s,v CT v y(v, s) + 1

s,j Ljx(j, s).

min y f(x, y) such that

v p y(v) 1 x(j, s), s, j, p P <T (s, j) (1)

v p y(v) + y(j, s) 1 x(j, s), s, j, p P T (s, j)

y(j) + y(j, s) x(u, s) x(j, s), u N(j), s, j (3) x(s, s) = 1 y(s)

v y(v) B0 (4)

v y(v, s) Bt, s, t (5)

y(v), y(v, s), x(i, j) {0, 1}, s, v, i, j V (6)

Constraint (1) ensures that if a node j is within T hops of a source s, if node j does not get infected due to source

s, then at least some node on every path from s to j of path length less than T has a vaccinated node. In constraint (2) for paths of length T, node j could be vaccinated at time T to ensure the same effect. Constraint (3) ensures that if j is not vaccinated at either 0 or T, then, it gets infected if any of its neighbors does. Budget constraints are captured by (4) and (5).

Lemma 9. The optimum solution (x, y) to the program P is the social optimum of the BUDGETTEMPVACC instance.

We describe an approximation algorithm based on relaxing and rounding the solution of P for the special case where B0 = 0. For A V , let N(A) = {v / A | u A, u is adjacent to v}. The algorithm involves the following steps:

1. Solve a linear relaxation PR with the constraints y(i), y(i, j), x(i, j) [0, 1], for all i, j. Let xf, yf denote the fractional solution to this relaxed program.

2. We round xf, yf to an integral solution in the following manner:

(a) For each j, s, define x (j, s) = min{2xf(j, s), 1}, y (j) = min{2yf(j), 1}, y (j, s) = min{2yf(j, s), 1}. (b) For each j, if y (j) 1 T 1, set Y (j, , 0) = 1.

(c) For each j, s, if y (j, s) 1

T , set Y (j, s, T) = 1. (d) For each s V , pick suitable rs [0, 1] (as discussed in the proof of Theorem 10) i. Let A(s, rs) = {j : x (j, s) rs} and C(s, rs) = N(A(s, rs)) A(s, rs). ii. For each j C(s, rs), define Y (j, s, T) = 1.

We show below that this randomized strategy Y ( ) satisfies the budget constraints approximately, and cost(Y ) is within a constant factor of the fractional LP value. Ensuring that all the budget constraints are satisfied is a challenging open problem.

Theorem 10. Suppose B0 = BT = B. The solution Y ( ) constructed by the above algorithm satisfies the following properties: (1)

v Y (v, , 0) (2T) B, (2) for each s,

v Y (v, s, T) (8T) B, (3) cost(Y ) (8T) f(xf, yf).

Experimental Results We now explore the structure of the NE obtained through the best response strategy. In particular, we study how it behaves with respect to the budget at time 0, B0, time T, the budget at time T, BT , and the vaccination cost C. The algorithm was applied on three synthetic graphs: Erd os-R enyi with 100 nodes and average degree 7 (ER); random power-law graph generated using the Chung-Lu model with power-law index γ = 2.5, 93 nodes and average degree 4 (CL), and a random regular graph with 100 nodes and average degree 4 (RR). We chose these networks because they are commonly used in social network analysis (see, e.g., (Newman 2003)), and together model both homogeneous and heterogeneous degree networks. Recall that the best response algorithm requires computing I(v, s, Y ) each time a node changes its strategy. For this we need to use the all-pairs shortest path

algorithm. Therefore, we study relatively small networks here. To keep the framework simple, we assumed uniform vaccination cost C < 1 and infection cost L = 1 for all nodes. We ran the best response algorithm for various values of B0, BT , T, and C. The results presented are averaged across 20 iterations, each producing a NE. Where the results are consistent across networks, plots are shown for only CL network. The remaining plots are in the full version (Adiga and Vullikanti 2015). Structure of NE with respect to B0 and BT . The results are shown in Fig. 2. We used two criteria to study the effects of B0 and BT , viz. average cost of the NE (cost(Y )) and the average number of nodes which vaccinate at time 0 (E[|V0|]). Comparing column 1 to column 3, we note that across all networks, the effect of B0 on the cost(Y ) is more pronounced than that of BT . The plots in column 2 are quite interesting in the sense that they exhibit a threshold phenomenon. We note that E[|V0|] increases steadily (possibly linearly) with B0 and then tapers off. The point at which it hits a plateau is a function of BT . Qualitatively, these plots indicate that greater the guarantee of vaccine availability at a later stage, the higher the inclination to postpone vaccination. Possible directions from here are to determine when these regime changes occur, exploring the role of network structure in this behavior. Effect of vaccination cost C. We observe that the vaccination cost has a significant influence on the average cost of the NE see Fig. 3 first plot, which shows the average cost of solution vs. B0 for different values of T and BT . We have only shown results for CL due to lack of space. Convergence time. We observed that the best response algorithm generally converges quickly and shows little variation with budget constraints (Fig. 3 second plot). However, it would be interesting to see how it performs as the network size increases. Effect of time T. From Fig. 4, we observe that the effect of T depends on BT ; higher the BT , the more sensitive is the cost to T. Note that when BT is small, even if the second stage of vaccination happens early, it is not enough to secure enough nodes from the source. A possible future direction is to quantify this effect based on network properties such as density, expansion, etc.

Related Work

There is a large literature on vaccination games, which can be broadly partitioned into differential equation based or network based models. We summarize them below. One of the earliest works on vaccination games is by (Bauch and Earn 2004), who use a differential equation based model to study vaccination decisions made at the start of the epidemic. They show that the vaccinated fraction in NE can be expressed in terms of the reproductive number, R0, which is the expected number of secondary infections caused by an infected individual. Vaccination is a special kind of behavioral change in the context of epidemics. There has been a lot of research on different kinds of game formulations arising out of epidemic

0 10 20 30 40 50

ER, C/L = .5, T = 2

0 5 10 15 20 25 30 35 40 45 50

0 10 20 30 40 50

avg. vacc. at time 0

ER, C/L = .5, T = 2

0 20 40 60 80 100

CL, C/L = .5, T = 2

0 20 40 60 80 100

avg. vacc. at time 0

CL, C/L = .5, T = 2

0 20 40 60 80 100

RR, C/L = .5, T = 2

0 5 10 15 20 25 30 35 40 45

0 20 40 60 80 100

avg. vacc. at time 0

RR, C/L = .5, T = 2

BT = 0 10 20 30 40 50

Figure 2: The effect of budget constraints on the structure of NE from the best response algorithm: Each row corresponds to a particular network. The first column is a plot of average cost of the NE vs. B0, for various values of BT . The second column corresponds to similar plots for average number of nodes vaccinating at time 0.

behaviors, e.g., (Bauch and Earn 2004; Khouzani, Sarkar, and Altman 2012; Khouzani, Altman, and Sarkar 2012; Khouzani, Sarkar, and Altman 2011; Galvani, Reluga, and Chapman 2007; Reluga 2010; Reluga and Galvani 2011; Trajanovski et al. 2015; Manfredi and D Onofrio 2013). Reluga et al. (Reluga and Galvani 2011) develop a general approach that combines population games with Markov decision process, and allows decisions at different times. There has also been work on repeated game formulations that take information and past experience into account. (Conforth et al. 2011) study the effects of vaccination decisions based on past epidemics, and find that individuals with number of contacts above a threshold get vaccinated, whereas individuals with fewer than these many contacts do not, leading to erratic flu behavior. (Bauch and Bhattacharyya 2012) use an evolutionary game theory based model to study the feedback between disease prevalence and vaccinating behavior, especially in the context of vaccine scares. A different area of research involves the use of network based models. One of the earliest works in this direction is (Aspnes, Rustagi, and Saia 2007). They formalize the network version of the vaccination game problem of (Bauch and Earn 2004), and design algorithms for computing NE and the social optimum. This turns out to be a challenging problem, and they develop an approximation algorithm for the social optimum, that is based on linear programming round-

10 20 30 40 50 60 70 80 90

0 20 40 60 80 100

CL, BT = 10, T = 2

C/L = 0.25 C/L = 0.5 C/L = 0.75

0 20 40 60 80 100

avg. convergence time

CL, C/L = .5, T = 2

BT = 0 BT = 20 BT = 40 BT = 60 BT = 80 BT = 100

Figure 3: Best response algorithm on Chung-Lu graph CL: Plot (1) corresponds to effect of C on the average cost. Plot (2) shows how average convergence time varies with respect to budget constraints.

0 10 20 30 40 50

CL, C/L = .5, BT = 10

T = 2 T = 3 T = 4

0 10 20 30 40 50

CL, C/L = .5, BT = 60

T = 2 T = 3 T = 4

Figure 4: The effect of T on the cost of NE. Plots (1) and (2) show cost vs. B0 for BT = 10 and 60 respectively.

ing. This approximation bound was improved by (Chen, David, and Kempe 2010; Kumar et al. 2010). All these approaches have assumed a simplistic model of epidemic spread, which models highly contagious diseases. There has been work on more realistic SIS (Susceptible-Infectious Susceptible) models, e.g., (Omic, Orda, and Mieghem 2009; Trajanovski et al. 2015). An alternative approach was studied by (Saha, Adiga, and Vullikanti 2014), who develop a formulation based on the spectral radius (the first eigenvalue of the network), in which the utility is based on whether or not the spectral radius is above a threshold or not. One limitation of all of these works is that they only consider vaccination decisions at the start of the epidemic, in a one-shot simultaneous game formulation. The work most closely related to our paper is by (Adiga, Venkataramanan, and Vullikanti 2016), who formalize a temporal vaccination game, in which vaccination decisions can be done at multiple times. However, there are no budget constraints in their formulation. As mentioned earlier, this has a very significant impact on both the structure and complexity of the problem.

Conclusions

In this paper, we formalize the temporal vaccination problem with resource constraints on complex networks, as a repeated game BUDGETTEMPVACC. This captures many realistic aspects of epidemic spread in real networks. The budget constraints have a very significant impact on the structure of the game solutions, as well as on the complexity of finding equilibria. A significant fraction of nodes that do get vaccinated, choose to defer their vaccination decision the specific effects depend on the network structure, the budgets, and the vaccination and infection costs. Computing prop-

erties of such repeated games becomes more challenging, compared to those of standard vaccination games. Some of the interesting open problems that arise out of our work include: (1) understanding networks in which pure NE exist and can be computed efficiently, and (2) extending our results to other epidemic models, and improving the algorithmic bounds. This work has been partially supported by the following grants: DTRA Grant HDTRA1-11-1-0016, DTRA CNIMS Contract HDTRA1-11-D-0016-0010, NSF ICES CCF-1216000, NSF NETSE Grant CNS-1011769, NIH MIDAS Grant 5U01GM070694, NSF DIBBS Grant ACI1443054.

References Adiga, A., and Vullikanti, A. K. S. 2015. Temporal vaccination games under resource constraints. http://staff.vbi.vt.edu/ abhijin/papers/aaai16 budget temporalvacc.pdf. Full version. Adiga, A.; Venkataramanan, S.; and Vullikanti, A. 2016. To delay or not: temporal vaccination games on networks. Accepted in INFOCOM. Anshelevich, E.; Chakrabarty, D.; Hate, A.; and Swamy, C. 2009. Approximation algorithms for the firefighter problem: Cuts over time and submodularity. In Dong, Y.; Du, D.-Z.; and Ibarra, O., eds., Algorithms and Computation, volume 5878 of Lecture Notes in Computer Science. Springer Berlin Heidelberg. 974 983. Aspnes, J.; Chang, K.; and Yampolskiy, A. 2006. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. J. Comput. Syst. Sci. Aspnes, J.; Rustagi, N.; and Saia, J. 2007. Worm versus alert: Who wins in a battle for control of a large-scale network? OPODIS. Bauch, C., and Bhattacharyya, S. 2012. Evolutionary game theory and social learning can determine how vaccine scares unfold. PLo S Comput Biol. Bauch, C., and Earn, D. 2004. Vaccination and the theory of game. PNAS. CDC. Vaccine shortages and delays. http://www.cdc.gov/ vaccines/vac-gen/shortages/default.htm?s cid=cs 000. Chen, P.; David, M.; and Kempe, D. 2010. Better vaccination strategies for better people. In Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), Cambridge, Massachusetts, USA, June 7-11, 2010, 179 188. Conforth, D. M.; Reluga, T. C.; Shim, E.; Bauch, C. T.; Galvani, A. P.; and Meyers, L. A. 2011. Erratic flu vaccination emerges from short-sighted behavior in contact networks. PLo S Computational Biology. Easley, D., and Kleinberg, J. 2010. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press. Finbow, S.; King, A.; Mac Gillivray, G.; and Rizzi, R. 2007. The firefighter problem for graphs of maximum degree three. Discrete Mathematics 307(16):2094 2105. Galvani, A.; Reluga, T.; and Chapman, G. 2007. Longstanding influenza vaccination policy is in accord with individual self-interest but not with the utilitarian optimum. PNAS 104(13):5692 5697.

Grossklags, J.; Christin, N.; and Chuang, J. 2008. Secure or insure? a game-theoretic analysis of information security games. In World Wide Web Conference (WWW). Hayrapetyan, A.; Kempe, D.; P al, M.; and Svitkina, Z. 2005. Unbalanced graph cuts. In Algorithms - ESA 2005, 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings, 191 202. Khouzani, M. H. R.; Altman, E.; and Sarkar, S. 2012. Optimal quarantining of wireless malware through reception gain control. IEEE Trans. Automat. Contr. 57(1):49 61. Khouzani, M. H. R.; Sarkar, S.; and Altman, E. 2011. A dynamic game solution to malware attack. In INFOCOM, 2138 2146. Khouzani, M. H. R.; Sarkar, S.; and Altman, E. 2012. Saddlepoint strategies in malware attack. IEEE Journal on Selected Areas in Communications 30(1):31 43. Koutsoupias, E., and Papadimitriou, C. H. 1999. Worst-case equilibria. In Proceedings of STACS. Kumar, V. S. A.; Rajaraman, R.; Sun, Z.; and Sundaram, R. 2010. Existence theorems and approximation algorithms for generalized network security games. In Proceedings of IEEE ICDCS. Leyton-Brown, K., and Shoham, Y. 2008. Essentials of Game Theory: A Concise, Multidisciplinary Introduction. Morgan and Claypool Publishers, 1st edition. Manfredi, P., and D Onofrio, A. 2013. Modeling the Interplay Between Human Behavior and the Spread of Infectious Diseases. Springer. Molinari, N.-A. M.; Ortega-Sanchez, I. R.; Messonnier, M. L.; Thompson, W. W.; Wortley, P. M.; Weintraub, E.; and Bridge, C. B. 2007. The annual impact of seasonal influenza in the US: Measuring disease burden and costs. Vaccine 25(27):5086 5096. Newman, M. 2003. The structure and function of complex networks. SIAM Review 45. Omic, J.; Orda, A.; and Mieghem, P. V. 2009. Protecting against network infections a game theoretic perspective. In INFOCOM. Orenstein, W. A., and Schaffner, W. 2008. Lessons learned: Role of influenza vaccine production, distribution, supply, and demandwhat it means for the provider. The American Journal of Medicine S22 S27. Reluga, T., and Galvani, A. 2011. A general approach to population games with application to vaccination. Mathematical Biosciences. Reluga, T. 2010. Game theory of social distancing in response to an epidemic. PLOS Computational Biology 6(5). e1000793. Saha, S.; Adiga, A.; and Vullikanti, A. K. S. 2014. Equilibria in epidemic containment games. In The 28th AAAI Conference on Artificial Intelligence (AAAI). Trajanovski, S.; Hayel, Y.; Altman, E.; Wang, H.; and Van Mieghem, P. 2015. Decentralized protection strategies against SIS epidemics in networks. Control of Network Systems, IEEE Transactions on PP(99):1 1.