3.1. Why Game Theory?

Gupta and Ranganathan [11] surveyed several optimization approaches such as Genetic Algorithms (GA), the Bayesian Search (BS) method, as well as Random Search (RS) and Greedy Allocation (GS) methodologies. These algorithms cannot be applied to the multi-crisis management problem because they do not provide individual rationality and some of the members of the population become dominant as the algorithm progresses. However, using game theory, scenarios that optimize multiple competing objectives can be modeled. Game theory presents interactions between self-interested agents and analysis as to which strategies can be designed that will maximize the benefits of an agent in a MAS. Many of the applications of game theory have been to analyze the negotiation and coordination of multiple agents. Game theory can be a useful tool for building future generations of mixed game theory and decision theory agents [3].

In a non-cooperative game, each player tries to utilize resources at minimum cost and the coordination is not enforced externally but is self-enforcing. All players optimize their decisions which maximize their payoffs in a non-cooperative game. N.E. is a solution concept for a non-cooperative game which identifies a prediction of the game outcome such that every player in the game is satisfied with respect to every other player [12]. N.E. provides a theoretical prediction of attack in a conflict situation, where individual MAS agents suffer from external attacks. The interactions between an external attacker and a response agent can be modeled as a non-cooperative game.

The Shapley value is a solution concept for cooperative games which computes the power index of an individual for cost allocation [13]. The cooperative game provides a suitable model for the design and analysis of response agent deployment, and it has been shown that the famous Shapley value rule satisfies many nice fairness properties [14]. The Shapely value also identifies a socially fair, good quality allocation for all agents. Here, the individual fairness for each player is optimal and the average fairness of the MAS is high. The social optimality property ensures that each player in the game receives the best utility for herself/himself and the complete MAS. A power index in the form of the Shapley value is applied to calculate the marginal contribution among agents and achieve a mutually agreeable division of cost for MAS deployment [2].

4.1. The External Threat Game

The first game models the interactions of an attacker (or attack) and a response agent. When an agent confronts an external attacker, both face a competitive situation. The relationships between external attacker and response agents include pure and impure conflicts, and their behaviors are non-cooperative. Thus, in the first stage, a non-cooperative game is applied to model decisions and to analyze the best responses. The two-player non-cooperative game is defined as follows:

1. (i)

   The set of players A: The first model only has two players. The attacker is player 1 and the response agent is player 2. A = {Attacker, Response agent}.

2. (ii)

   Strategy space S_i: A set of all possible strategies available to two players in a game.

3. (iii)

   Payoff π_i: The expected utility to a player as a function of the strategies chosen by an attacker or response agent.

Let G = <A, (S_i), (π_i)> be such a normal form game. Sometimes this game cannot determine a pure N.E. strategy, because there is probably no N.E. However, every finite normal form game has a mixed-strategy N.E [16]. Thus, this study can also derive another strategic game from G, called the “mixed extension” of G, in which the set of actions A_i of each player i is the set of mixed strategies in G. More generally, suppose that player i has K pure strategies: S_i = {s_i1, …, s_1K}. Then, a mixed strategy for player i has a probability distribution (p_i1, p_i2, …, p_iK), where p_iK is the probability that player i will play s_iK, for k = 1, …, K. Since p_ik is a probability, this study requires 0 ≤ p_iK ≤ 1 for k = 1, …, K and p_i1 + ⋯ + p_iK = 1, where p_i is used to denote an arbitrarily mixed strategy from the set of probability distributions over S_i, just as s_i is used to denote an arbitrary pure strategy from S_i.

Let J denote the number of pure strategies in S₁ and K indicate the number in S₂. Now, S₁ = {u₁, u₂, …, u_J} and S₂ = {d₁, d₂, …, d_K} are rewritten using u_j and d_k to denote pure arbitrary strategies from S₁ and S₂, respectively. A J × K payoff matrix is created for the external threat game based on the two players’ strategies and interactions (see Table 1).

If player 1 believes that player 2 will play the strategies {d₁, d₂, …, d_K} with the probability q = (q(d₁), q(d₂), …, q(d_K)) then player 1’s expected payoff from playing the pure strategy u_j is [Equation (1)]

and player 1’s expected payoff from playing the mixed strategy r = (r(u₁), r(u₂), …, r(u_J)) is [Equation (2)] where r(u_j), q(d_k) is the probability that player 1 plays u_j and player 2 plays d_k. Thus, 0 ≤ r(u_j), q(d_k) ≤ 1 for k = 1, …, K and j = 1, …, J; r(u₁) + r(u₂) + ⋯ + r(u_J) = 1 and q(d₁) + q(d₂) + ⋯ + q(d_K) = 1.

Player 1’s expected payoff from the mixed strategy r, given in Equation (2), is the weighted sum of the expected payoff for each of the pure strategies {u₁, u₂, …, u_J}, given in Equation (1), where the weights are the probabilities r(u₁), r(u₂), …, r(u_J). Thus, for the mixed strategy r(u₁), r(u₂), …, r(u_J) is the best response for player 1 and 2’s mixed strategy q(d_k), and it must be that r(u_j) > 0 only if [Equation (3)]

for every u_j′ in S₁. That is, for a mixed strategy to be the best response to q it must put a positive probability on a given pure strategy only if the pure strategy is itself the best response to q. Conversely, if player 1 has several pure strategies that are best responses to q, then any mixed strategy that puts all its probability on some or all of these pure-strategy best responses (and zero probability on all other pure strategies) is also the best response for player 2 to q [17].

This study computes player 2’s expected payoff when players 1 and 2 play the mixed strategies r and q, respectively. If player 2 believes that player 1 will play the strategies (u₁, u₂, …, u_J) with the probabilities (r(u₁), r(u₂), …, r(u_J)), then player 2’s expected payoff from playing the strategies (d₁, d₂, …, d_K) with the probabilities (q(d₁), q(d₂), …, q(d_K)) is [Equation (4)]

Given M₁(r, q) and M₂(r, q) this study restates the N.E. requirement that each player’s mixed strategy is the best response to the other player’s mixed strategy: for the pair of mixed strategies (r^*, q^*) to be a N.E., r^* must satisfy [Equation (5)]

for every probability distribution r over S₁, and q^* must satisfy [Equation (6)] for every probability distribution q over S₂, where r^* and q^* represent the optimal mixed strategy for the attacker and response agent respectively. A mixed strategy N.E. is similar to a stochastic state that predicts the outcome of a game and it can capture stochastic regularity. The attacker and agent have information about their payoffs from actions which were taken in the past; each player applies these payoffs to form his belief about the future behaviour of the other players, and thereby formulate his optimal mixed strategy.

In Table 1, player 2’s expected payoff is computed when players 1 and 2 play mixed strategies r and q respectively. If the game G has no pure strategy N.E., a mixed N.E. pair (r^*, q^*) exists in this game, which is an optimal strategy [18]. The mixed N.E. for the probability vector is r^* = {r^*(u₁), r^*(u₂), ..., r^*(u_J)} with actions {u₁, u₂, ..., u_J} for the external attacker and the vector q^* = {q^*(d₁), q^*(d₂), ..., q^*(d_K)} with actions {d₁, d₂, ..., d_K} for the response agent. The external attacker’s expected payoff for a N.E. (pure or mixed strategy) is defined as its external threat value. Player 1 (i.e., the external attacker) obtains the positive payoff (+), because player 1 gains a profit from player 2’s resource responses. Player 2 (i.e., the response agent) obtains a negative payoff (−), which means that player 2 pays for player 1’s attack. When the response agent (i.e., player 2) gets a low expected payoff, the external attacker (i.e., player 1) gets a high expected payoff and the threat of external attack is high. Because player 1’s expected payoff always represents a gain (+), this study defines the v_i as the ith response agent’s threat value, given by [Equation (7)]

Therefore, v_i is derived from the attacker optimal strategies’ expected payoff which represents the threat value in the first game model. The next proposed model uses the threat value v_i to compute the Shapley value of each agent within the cooperative game.

4.2. Resource Reallocation Game

In this study, it is assumed that a central planner of the Security of Center (SOC) or Emergency Operation Center (EOC) can command and control MAS resource allocation [19]. Each agent reports its degree of threat (or threat value) to the central planner. The central planner computes the Shapley value based on the threat values of all agents in order to command agents to dispatch resources. In this second game, the interactions of all response agents in the MAS response region are likened to the playing of a cooperative game. An efficient method is needed to decide the number and priority of the deployment of resources to various response events when multiple attacks occur simultaneously. The Shapley value is applied to create an optimal allocation of resources for the SOC commander during multiple attacks. We utilize the concept of the majority coalition in a party voting game to deal with MAS resource reallocation. A majority of voters can pass any bill in the majority game. The power of a voter will depend on how crucial that voter is to the formation of a winning coalition [15]. The Shapley value can provide a measure of the power of each voter, which is represented by the power index. When the sum of external threat values of some attacks passes the threshold of the majority level, the formation of a winning coalition is enabled, and the power index of each attack can be computed.

We define y: V → R⁺ as a one-to-one function by assigning a positive real number to each element of v (i.e., external threat value) and y(0) = 0, V = {v₁, v₂, …, v_i}, i ∈ n. The majority of the attack level h_H is derived from a majority of all external threat values which represents the corresponding threshold value m_H. The allocation of the response agent resources is based on the concept of the majority of external threat values. Given the output vector of all external threat values of attacked events, the majority level is h_H, if the sum of the external threat values of attacks is greater than or equal to m_H [Equation (8)]

The external threat values of attacks can be grouped into the majority level h_H. This is divided by 2 from the maximum value v_Max to minimum value v_Min. All response agents can be modelled as an N-person game with X = {1, 2, …, N}, which includes a set of players (i.e., response agents) and each subset V ⊂ X, and where v_j ≠ 0, ∀j ∈ V is called a coalition [2]. The coalition of X response agent groups in the mth threshold of the threat level, and each subset of X (coalition), represents the observed threat pattern for different threat levels H. The aggregate value of the coalition is defined as the sum of the threat values of the response agent, y(C) = ∑_i∈c v_i and is called a coalition function. Each response agent coincides with one or another given m thresholds of the threat level. Therefore, the different priorities for the response agent deployment are derived from the thresholds. Based on the external threat for each MAS response agent with respect to others, and the effect of the threshold values on various threat levels, the Shapley value represents the relative importance of each response agent. Now let y(C) = ∑_i∈c v_i v_i ∈ V, C ⊂ X be the value of coalition C with a cardinality of c. The Shapley value of the ith element of the response agent vector is defined by [Equations (9) and (10)]

Equation (9) can be simplified to Equation (10), because the term y(C) − y(C − {i}) will always have a value of 0 or 1, taking the value 1 whenever c′ is a winning coalition. If it is not a winning coalition, the terms C − {i} and y(C) are 0 [15]. Hence, the Shapley value is ω(i), where C′ denotes the winning coalitions with ∑_i∈c v_i ≥ m_i. The Shapley value of the ith response agent output indicates the relative threat value for the thresholds m_H (i.e., threat levels). Therefore, a Shapley value vector shows the strength of all external attacks. We can use all Shapley values to compute the reallocation amount of emergency response resources of the agent. The numbers of resources of type k reallocated to the ith agent are defined by [Equation (11)]

where o_{all, k} is the total number of resource available of type k in a MAS (such as ambulances when an earthquake occurs). The reallocated numbers of the ith agent’s resources e_k(i) are derived from the Shapley value of the ith response agent ω(i) multiplied by the total number of resource available of type k o_{all, k}. Finally, the commander can reallocate any kind of agents’ resources so as to fairly deploy resources to resist attacks in multiple attack regions.

5.1. The Model Assumptions

Certain assumptions must be made when treating a multi-emergency and response management scenario as a game theory framework. The assumptions are listed below.

1. (i)

   After the deadliest quakes, emergencies will occur in different districts in a time-overlapped manner, and resource requests will be simultaneously received by the central response agent managers (see Table 2). We assume the multi-emergency event is player 1 and the district response agent is player 2. Hence, two players can use a static single step. Each player plays a non-cooperative and a zero-sum game. A response agent manages one district. Three types of earthquake emergencies (i.e., fire, house collapse, and fire and house collapse) could occur simultaneously when evaluating the value of the earthquake threat in a specific time period.

2. (ii)

   The EOC has developed a training program to improve the emergency response agents’ capabilities. As seen in Table 3, the annual emergency training gives us the time needed to perform search and rescue activities from each of the resource sites. These data are generated by the training program through annual earthquake drills or exercises.

3. (iii)

   The first model is a normal form game for capturing the interactions between two players. This model assumes complete information; that is, every player knows the available strategies of every other player. Each district has a different number of resources available. In multiple emergencies, there is also complete information regarding the resource requirements, emergency priorities and the population density of the affected district (see Tables 2 and 4).

5.2. Earthquake Damage Game

This game applied the first scheme of the proposed model, which is designed to obtain the threat value of the earthquake in each district. We assume that the multi-emergency event is player 1 and the district response agent is player 2. The interactions between multi-emergency event and response agent are modeled by a two-person game. It is assumed that both players are forming a set of non-cooperative players I = {I₁, I₂}, where I₁ generates multiple emergency events; and I₂ is the district response agent responding to allocate finite SAR resources, obtained by prioritizing the different districts. The parameters for determining the threat measures are defined in the following paragraphs.

5.3. Reallocation of SAR Resources Game

This game applies the second scheme of the proposed models as explained in Section 4.2. We assume that the 15 SAR districts of Taiwan are modeled as a 15-person cooperative game (see Figure 4). The threshold value m_H is generated by Equation (8). Given the m_H threshold of the majority value, we can compute the majority of coalitions which are pivotal to each district. The different priorities for response resource deployment are derived from the majority of coalitions. Based on the earthquake threat value for each district with respect to the others, and the impact of the threshold values on the majority of emergency level represents the relative importance of each district. Equations (9) and (10) are used to compute the Shapley value for each agent and the amount of reallocation of each agent’s resources in Section 4.2. According to SAR resource reallocation, the EOC mobilizes resources from all districts to assure that even rescue of victims in multiple emergency events across the whole region is possible.

Figure 4

15 Search and rescue (SAR) districts of Taiwan.

5.4. Simulation Experiments

The simulation takes advantage of the 921-earthquake data to verify the proposed model. We hypothesize that a strong earthquake occurs as it did in Jiji, Nantou County, Taiwan. The EOC deploys 15 response agents from the district (or county) in the whole region (from A1 to A15) and provides central management and monitoring for homeland security of Taiwan (see Figure 4). In the first stage, the information in Tables 2–4 is used, regarding the resource types and the availability, population density, emergency requests, emergency priorities, and time taken to reach the crisis area from each of the resource centers. Each district’s emergency resource request is derived from the number of emergency calls (i.e., 119) multiplied by the ratio of the resource requests (see Tables 2 and 6). We model the non-cooperative game and generated simulation sets of threat measures for the strong earthquake and the response agent in each district. The payoff matrix of the zero-sum earthquake damage game for each district is modeled according to Equations (12) and (13) and Table 5. Then, 15 earthquake threat values are calculated using Equations (12–14). Table 6 shows 15 earthquake threat values of the response agent derived from Nash equilibrium points by enumerating the strategies in the normal form game.

In the second stage, all earthquake threat values are utilized to compute the Shapley value for each district. Given the vector output for all the values, we use Equation (8) to compute the majority of the threat values; the threshold value (i.e., m_H) is 310. According to this threshold value 15 Shapley values of the district are calculated using Equation (10). The results obtained are shown in Table 6. Assume that all SAR resources available are unable to satisfy the requirements for all the earthquake-related emergencies occurring in Taiwan. Table 4 provides the experimental number of total available SAR resources. According to these experimental data, the number of reallocated SARs for each district can be computed using Equation (11). The results obtained are presented in Table 7.

5.5. Discussion

We analyze the application of the proposed model to determine whether the relief effort of SAR resources is improved after the 921-earthquake or not. Assume specific SAR resources for the entire Taiwan region. When the 921-earthquake occurred, the results calculated by our model guided the EOC to mobilize resources from all districts to assure even rescue of victims in multiple emergency events across the whole region (see Table 7). The number of people killed in all districts during the 921-Earthquake is revealed by the Ministry of the Interior of Taiwan statistics (see Table 7). Central Taiwan suffered major damage, particularly Nantou County and Taichung County. The majority of the casualties were concentrated in these two districts. Table 7 is interesting; because the proposed model dispatches most SAR resources to the two most severely affected districts. In addition, it shows the Average Distribution Rate (ADR) for Nantou County (i.e., 33.4%) which almost matches the death rate (i.e., 36.91%). Therefore, the proposed model is able to improve relief effort to counteract damage from external attacks.

We also evaluated the proposed division of resources by comparing the results obtained with those from the proportional division. The epicenter of the 921-earthquake was in Nantou County (i.e., agent A7) where the seismic intensity measured 7 on the Richter scale. Different magnitudes were measured at other counties in Taiwan when the 921-earthquake occurred. We assume that the higher the magnitude in a district, the more SARs resources needed. Therefore, we can use the proportional division to compute the amount of reallocation of each agent’s resources. The numbers of resources of type k reallocated to the ith agent are defined by [Equation (15)]

where o_{all, k} is the total number of SAR resources of type k; M_i indicates the seismic intensity of the ith agent in the district when a serious quake occurred. The reallocation of the ith agent’s resources in district p_k(i) is derived from the proportion of M_i/M_all multiplied by the total number of resources available of type k o_{all, k}. Table 8 shows the experimental results for 15 districts (or agents) using the proportional division of resources.

In Figure 5, it can be seen that with the Shapley value allocation approach proposed in this study, the average distribution of resource rate is closer to the death rate of each district than the proportional division of resources. The results of this comparison support the idea of the proposed model, which creates a minimum set of resource allocation costs when the MAS confronts external attacks. The EOC rapidly commands all agents and efficiently mobilizes and redistributes SAR resources for seriously affected districts.

Figure 5

Comparison of our division and proportional division.