--- title: "A Quantitative Game-theoretical Study on Externalities of Long-lasting Humanitarian Relief Operations in Conflict Areas" authors: - "Kaiming Xiao" - "Haiwen Chen" - "Hongbin Huang" - "Lihua Liu" - "Jibing Wu" doi: "10.24963/ijcai.2023/696" url: "https://ijcai.org/proceedings/2023/696" pdf: "https://ijcai.org/proceedings/2023/0696.pdf" venue: "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence" year: 2023 pages: "6272-6280" track: "AI for Good" keywords: - "AI for Good: Planning and Scheduling" - "AI for Good: Humans and AI" - "AI for Good: Uncertainty in AI" - "AI for Good: Agent-based and Multi-agent Systems" --- # A Quantitative Game-theoretical Study on Externalities of Long-lasting Humanitarian Relief Operations in Conflict Areas Kaiming Xiao, Haiwen Chen, Hongbin Huang, Lihua Liu, Jibing Wu *Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence*, pages 6272-6280. DOI: [10.24963/ijcai.2023/696](https://doi.org/10.24963/ijcai.2023/696) ## Abstract Humanitarian relief operations are often accompanied by regional conflicts around the globe, at risk of deliberate, persistent and unpredictable attacks. However, the long-term channeling of aid resources into conflict areas may influence subsequent patterns of violence and expose local communities to new risks. In this paper, we quantitatively analyze the potential externalities associated with long-lasting humanitarian relief operations based on game-theoretical modeling and online planning approaches. Specifically, we first model the problem of long-lasting humanitarian relief operations in conflict areas as an online multi-stage rescuer-and-attacker interdiction game in which aid demands are revealed in an online fashion. Both models of single-source and multiple-source relief supply policy are established respectively, and two corresponding near-optimal online algorithms are proposed. In conjunction with a real case of anti-Ebola practice in conflict areas of DR Congo, we find that 1) long-lasting humanitarian relief operations aiming alleviation of crises in conflict areas can lead to indirect funding of local rebel groups; 2) the operations can activate the rebel groups to some extent, as evidenced by the scope expansion of their activities. Furthermore, the impacts of humanitarian aid intensity, frequency and supply policies on the above externalities are quantitatively analyzed, which will provide enlightening decision-making support for the implementation of related operations in the future. ## Full text ## 1 Introduction In recent years, natural disasters and regional conflicts are on the rise, and often deeply intertwined, leading to an exacerbation of poverty, famine, plague and many other critical issues globally. These disasters and conflicts including the 2023 earthquake in Turkey and Syria, the COVID-19 pandemic across the world, as well as the ongoing regional conflicts in the Middle East and Africa have taken millions of lives and resulted in huge economic losses. According to the statistics of United Nations Office for the Coordination of Humanitarian Affairs (OCHA), 274 million people need humanitarian assistance and protection in 2022, which is the highest figure in decades [OCHA, 2022]. Fueled by the soaring need of mitigating the miserable effects of these natural or manmade disasters, humanitarian relief operations have received increasing attention from both international organizations and researchers [Modgil et al., 2020; Ekici and ¨Ozener, 2020; Agarwal et al., 2022; V¨ayrynen, 2023]. Every year, billions of dollars worth of humanitarian aid allocations flow into conflict-affected countries and regions through bilateral or multilateral channels [Wood and Molfino, 2016], which plays a vital role in sustaining vulnerable populations. However, the involvement of humanitarian relief operations in conflict areas can not only play a positive role in alleviating the local humanitarian crisis, but also bring negative externalities. Humanitarian relief organizations such as the International Committee of the Red Cross (ICRC) and the International Crisis Group (ICG) have increasingly advocated to remain neutral and impartial during conflict [Terry, 2011]; however, the long-lasting presence of them can affect the relationships between insurgents, counter-insurgents, and civilians [Narang and Stanton, 2017]. Multiple statistical analyses shows that the long-term channeling of aid resources into conflict areas may influence subsequent patterns of violence, more specifically increase the rebel violence against civilians [Wood and Sullivan, 2015]. Evidence from violence in Afghanistan indicates that specific violence from insurgents targeting humanitarian aid workers is likely to emerge in conflict areas, as their services may strengthen government support from a rebel perspective [Narang and Stanton, 2017]. In some extreme cases, such as 1983 Ethiopian famine, humanitarian aid were misused to further war efforts, which inevitably facilitated and prolonged conflict [Prine, 2020]. To the best of our knowledge, the analysis of the externalities of humanitarian relief operations is mainly based on qual- focus on the quantitative analysis based on the integration of game-theoretical behavioral models and empirical data. In this work, we address the challenge of quantitatively analyze the potential externalities associated with long-lasting humanitarian relief operations. Different from existing studies, which only focus on empirical findings and qualitative policy analysis of externalities, the behavioral models of the two main players (i.e., rescuer and attacker) in long-lasting humanitarian relief operations are built to investigate their interactions in a game-theoretical framework. In this game, irrevocable relief decisions should be made by the rescuer in real time, while attackers can operate to hinder the relief operations by taking armed control of some roads and towns. By integrating the empirical data of real-time geo-located aid demands and rebel group distribution with the game model, this paper explores the relationship between the rescuer's policy choice and the scale of externalities quantitatively for the first time. The main contributions of this paper are as follows: - (1) We first model the problem of long-lasting humanitarian relief operations in conflict areas as an online multistage rescuer-and-attacker interdiction game in which aid demands are revealed in an online fashion. - (2) Both models of single-source and multiple-source relief supply policy are established respectively, and two corresponding near-optimal online algorithms are proposed. - (3) In conjunction with a real case of anti-Ebola practice in conflict areas of DR Congo, the externalities of financing the rebel groups passively and expanding the range of violent activities are found. The impacts of humanitarian aid intensity, frequency and supply policies on the above externalities are quantitatively analyzed. ## 2 RelatedWorks ## 2.1 Externalities of Humanitarian Aid The negative externality of humanitarian aid is a longstanding concern of the academic community [Bryer and Cairns, 1997; de Montclos, 2009; Elayah and Ahmed, 2022]. A empirical study with geo-located data on twenty subSaharan African countries during the post-Cold War era shows that humanitarian aid increases the frequency of subsequent violent engagements between rebel and government forces in the aid-concentrated areas [Wood and Molfino, 2016]. Findley [2018] conducted a survey of arguments connecting aid to the onset, dynamics, and recurrence of civil wars, and discussed the challenge of causal effect analysis posed by under-theorization of aid allocation. Empirical analysis of the situation in Yemen indicates that humanitarian assistance is being used as a weapon of war for power and financial gain, thus becoming a contributing factor to the continuation of the conflict [Elayah et al., 2021] and augmenting the crisis of sovereignty [Elayah and Ahmed, 2022]. Unfortunately, the quantitative relationship between humanitarian relief policy choice and the corresponding externalities is scarcely explored. ## 2.2 Game Theory Applications in Humanitarian Operations Game theory, as a tool for modeling systems with multiple decision-makers, tends to be a promising choice for the context of humanitarian relief operations with several interest-intertwined players involved in conflict areas [Muggy and L. Heier Stamm, 2014]. A Generalized Nash Equilibrium network model for post-disaster humanitarian relief by nongovernmental organizations (NGOs) was developed where disaster relief NGOs competing for financial donations [Nagurney et al., 2016]. To explore the coordination mechanism between the private sector and humanitarian organization, evolutionary game models concerning traditional and trust mechanisms were developed [Fathalikhani et al., 2018] Considering both financial and logistical aspects of humanitarian organizations, a game theory model for disaster relief is constructed so as to reflect the interaction of operations taking by different organizations, as well as the final equilibrium [Nagurney et al., 2019]. To model the location-routing-inventory decision-making problem in humanitarian relief chain, a cooperative game theory approach was proposed for the four-echelon multi-objective, multicommodities and multi-period disaster relief chain [Ghasemi et al., 2022]. Most researchers focus on games between humanitarian organizations from the perspective of cooperation, and only a few have explored the game between rescuers and regional armed forces [Yang et al., 2022]. ## 2.3 Network Interdiction Game Network interdiction problem is a kind of Stackelberg game which models the interaction between an attacker and a defender who executes actions or plans on a network. As a quantitative decision-making approach, it has been widely applied to security decision-making scenarios relating to operations on networks, involving military operations, humanitarian relief, transportation and logistics [Sinha et al., 2018; Smith and Song, 2020]. After the classical models of network flow interdiction [Wood, 1993] and shortest-path interdiction [Fulkerson and Harding, 1977; Israeli and Wood, 2002] were proposed, different variants of interdiction models with new features have received considerable attentions recently, including goal recognition assistance [Xu et al., 2017], incomplete information [Borrero et al., 2019], dynamic or adaptive interdiction [Xiao et al., 2018; Zhang et al., 2019], network interdependence [Yan et al., 2020; Xie and Aros-Vera, 2022], and asymmetric cost uncertainty [Nguyen and Smith, 2022] etc. However, few studies have applied the interdiction game approach to humanitarian relief context with the online decision-making requirement. ## 3 Multi-Stage Humanitarian Relief Interdiction Game In this section, we first model the problem of long-lasting humanitarian relief operations as a sequence of stage-based interdiction games between the rescuer and attacker, i.e., multistage humanitarian relief interdiction game (MHRIG). Different from the optimization goal of transportation cost in the previous study [Yang et al., 2022], this paper takes both the transportation cost and the actual delivery of relief resources as the goal of the game between the two sides. Then, the omniscient offline versions of MHRIG under single-source and multiple-source relief supply policy choices are proposed. ## 3.1 The Simultaneous Game at Each Stage of MHRIG At each stage of the MHRIG, there is a simultaneous rescuerand-attacker interdiction game. The scene of the game is on a road network G = (V,E) consisting a set of nodes V representing intersections (cities,towns, etc.) and a set of edges E representing roads. If the rescuer at stage t decides to meet the relief demand wt from the resource base city ot to the city of demand gt, she needs to plan a road path in the network within the constraint of a given transportation time frame. Her goal is to maximize actual quantity of arrived relief supplies and minimize the cost on transport. The attacker, on the other hand, has several armed forces distributed at different nodes of the network with the aim of mobilizing them to interdict the rescuer thereby levying taxes or outright robbing under the constraint of mobility. ## The Attacker Problem The attacker problem is implementing his armed forces distributed in the network to control some selected nodes so as to interdicting the relief routing of the rescuer. Denote by ht = (hjt)j∈V ∈ {0, 1}|V | the distribution vector of the armed forces, and hjt = 1 if there is an arm force stationed at node j at stage t. The strategy of the attacker is made up of |I| vectors, denoted by zit = (zijt)j∈V ∈ {0, 1}|V | , and zijt = 1 if the armed force i is decided to reach and control node j at stage t. Also, the actions of attacker are restricted by movement constraints, i.e., the movement cost of each armed force i ∈ I should not exceed the budget fit at stage t (vector form ft). Then, the set of all feasible strategies for the attacker can be denoted by where 1 denotes the all 1 vectors, and the first constraint illustrates that one armed force can only be deployed once in each stage. Denote by Vh the set of nodes which are controlled by the rebel groups at stage t, and Ft = [ftft · · · ft]T ∈ R|V |×|Vh| + . We introduce Ht = (h′ij )i∈V,j∈Vh where h′i j = 1 indicates that nodes i is selected to reach and control by the rebel group located in node j. Let L = (lj ′ j)j ′ ,j∈V ∈ R|V |×|V | + represent the cost of implementing the stationed force from node j to node j ′ , which can be estimated by the attacker using road transport information. Hence, the second constraint makes the deployment of armed forces not exceed the attacker's mobility limits. ## The Rescuer Problem The rescuer problem is planning a routing path through the network from ot to gt which can be modeled as a path-finding problem. Denote by yt = (ykt)k∈E ∈ {0, 1}|E| the decision variables of the rescuer representing a path in the network, and ykt = 1 if she selects the edge k to traverse. Let FS(i) and RS(i) represent the set of edges directed from/into node i. Then, the strategy space of the rescuer is constrained by the following flow conversation constraints: Then the set of all feasible strategies of the rescuer is ## The Utility Function The utility for both players is consist of two parts, i.e., the actual quantity of relief supplies that arrive in time and the transporting cost of this operation. The rescuer aims to maximize the quantity of arrived relief supplies and minimize the cost on transport by selecting the path traversed, while the attacker interdicts the relief routing from the opposing perspective. If the rescuer selects an attacker-controlled edge to traverse at one stage, the transported relief resources wt will suffer a loss of being levied or robbed. The amount of loss at edge k depends on the levy rate q = (qk)k∈E ∈ (0, 1)|E| of armed forces the rescuer encountered. Then, the total loss of relief supplies at stage t is wt ∑k∈E z′kt qkykt given the decision pair (Zt, yt) from the rescuer and attacker. Denote by ut (vector form u) the left relief supplies at stage t which can be successfully transported to the city or town in need, we have which is bi-linear and made up of both players' decision variables. Meanwhile, we consider the timeliness requirements of emergency relief demands. Denote by at the actual transporting cost on roads when attacks may happen, we have where ck (vector form c) denotes the time cost of traversing edge k, and dk (vector form d) represents the additional cost of passing through edge k which is controlled by the attacker with an armed force. z′kt denotes an intermediate decision variable, and z′kt = 1 if the edge k is under control of the attacker at stage t. Specifically, we suppose that all edges directing out of a force garrisoned node are under control, i.e., To optimize the above two goals ut and at at the same time, we integrate them with a pair of weight coefficient (θ, δ) indicating the importance of ut and at to the rescuer respectively. Hence, we propose the utility function as follows: where the weight coefficients can be determined by assessing their value in the humanitarian operations. Finally, denote by P = {attacker, rescuer} the set of players. Then, the simultaneous game of MHRIG at each stage can be expressed as a tuple Gt = (P,Zt,Yt,Ut). The final quantity of arrived relief supplies ut (vector form u) in this game is defined as the mixed Nash equilibrium of game Gt. In this work, we assume that parameters from the demand side, i.e., demand cities gt and the amount of relief needed wt, are generated i.i.d. from an unknown distribution respectively, as well as those from the attack side, i.e., mobility budget ft and distribution ht. ## 3.2 Omniscient Offline Versions of MHRIG Based on results of game Gt at each stage, we can construct offline versions of MHRIG by assuming that all data and parameters are known in advance. Specifically, this section considers two offline versions of multi-stage humanitarian relief operations with single-source relief supply policy (OFFMHRIGS) and multiple-source relief supply policy (OFFMHRIGM). ## Offline Version With Single-Source Relief Supply We first suppose that there is a single, integrated, and largescale relief supply site throughout the entire humanitarian relief operations. Due to the general shortage of relief supplies, the rescuer has to make decisions at each stage whether to meet the relief demand of a certain city. Denote by n the number of stages of MHRIG, and N = {1, 2 · · · , n} the set of stages. Let x = (xt)t∈N ∈ {0, 1}n represent the decision variables of the rescuer, and xt = 1 if she decides to meet the demand wt at stage t. To meet this demand, the rescuer has to pay a cost of at on transportation and can cover a certain amount of demand ut as a kind of revenue at this stage. Hence, as a long-term revenue seeker, the rescuer aims to maximize the total amount of demand satisfaction under the limitation on total amount of relief resources b1 and transportation budget b2. In OFFMHRIGS, there is only one choice for the provisioning site, i.e., ot is a fixed source site at each stage. All online data ut and at are solving from Gt given that ot is a fixed relief supply site. When assuming ut and at are known in advance, we can formulate OFFMHRIGS to a binary linear integer programming (BLIP) as follows: where x ∈ {0, 1}n , vectors u, w, a ∈ Rn+, and denote by b the vector [b1, b2]T . In this way, [P-OFFMHRIGS] can be solved using BLIP techniques and ¯x∗ denotes the optimal solution of it. ## Offline Version With Multiple-Source Relief Supply In actual humanitarian operation practice, relief resources are often supplied from more than one site. That is, the rescuer can select one site from the set of available sites as the source site to fulfill the relief demand at a given stage. Hence, we then proposed the extended version OFFMHRIGM. Denote by m the number of available source sites. For any site number j ∈ M = {1, 2, · · · ,m}, let ut = (utj)j∈M and at = (atj)j∈M present the results by solving Gt given that site j is selected to be the supply for all stages. Denote by xt = (xtj)j∈M the decision variables which indicate when site j is chosen during the multi-stage process, we formulate OFFMHRIGM to a multi-dimensional extension of the BLIP in [P-OFFMHRIGS] as follows: In this problem, the rescuer only selects one site j as the source to fulfill the relief demand at stage t. Similarly, [POFFMHRIGM] can be solved when all online revealed data uj and aj are known in advance. ## 4 Online Humanitarian Relief Policies Since both rescue demands and the distribution of rebels are revealed in an online manner, the results from game G served as the core parameters of the offline problems cannot be known in advance. Accordingly, online decisionmaking approaches are needed. Previous studies on online linear programming provide a series of theoretically guaranteed algorithms for long-term revenue in sequential decision making [Buchbinder and Naor, 2009; Balseiro et al., 2020; Li et al., 2020], which is instructive for problems in this work. We next give the explicit online models of multi-stage humanitarian relief operations single-source relief supply policy (ONMHRIGS) and multiple-source relief supply policy (ONMHRIGM), and then provide corresponding online algorithms respectively. ## 4.1 Online Versions of MHRIG ## Online Model With Single-Source Relief Supply In the online version of MHRIG, the parameter ut and at are revealed to the rescuer based on the Nash equilibrium results of the stage game Gt at each stage t. Simultaneously, the rescuer needs to make a decision on xt in real time. Unlike the setting in OFFMHRIGS, rescuer only knows the history information Ht = {ui, wi, ai, xi}t-1 i=1 . Hence, the online decision policy of rescuer can be presented as a function ϕ of the history and the observed parameters at the current stage t: Before designing the function ϕ, the distribution features of online revealed parameters are first analyzed. Denote by N the Nash equilibrium mapping from the parameters (gt, wt, ft, ht) in game Gt to parameters rt and at, i.e., Since (gt, wt, ft, ht) in game Gt are generated i.i.d. from an unknown distribution, it can be proved that (ut, at) is i.i.d. sampled from an unknown distribution P in Theorem 1. Theorem 1. The coefficient pair (ut, at) are generated i.i.d. from unknown distribution, if parameters (gt, wt, ft, ht) are generated i.i.d. from unknown distribution. (Proof in Appendix) ## Online Model With Multiple-Source Relief Supply The difference between ONMHRIGM and ONMHRIGS is the number of available relief source sites, resulting additional decision variables about how to choose a site. We denote the history information of the rescuer as Ht = {(uij )j∈M , wi, (aij )j∈M , xi}t-1 i=1 , and then the online decision policy at stage t can be presented as for any j ∈ {1, 2, · · · ,m}. Similarly, we can prove that for any site j, (utj, atj) are generated i.i.d. from an unknown distribution 1 . ## 4.2 Online Algorithms It is clear that ONMHRIGS is a degenerated version of ONMHRIGM when m = 1; hence, we here only focus on the analysis and online algorithm design of [P-ONMHRIGM]. Before given the online learning algorithm to ONMHRIGM, we present the linear programming relaxation of [P-OFFMHRIGM] as follows: s.t. Constraints (10), Then, the linear dual problem of it can be formulated as where the dual decision variables are p ∈ R2 and s ∈ Rn . Denote by x∗t , p∗n , and s∗ the optimal solutions of problem LP-OFFMHRIGM and DLP-OFFMHRIGM. From the complementary slackness conditions, we have for all t ∈ {1, 2, · · · , n} where ej is the unit vector with 1 at the j-th entry and 0 otherwise. According to Equation (18), if the optimal value of p∗n can be estimated properly during the online decision-making process, it is possible to make online decisions achieving a nearoptimal performance. Using the theoretical results of online linear programming technique [Li et al., 2020], we give the following online algorithm for [P-ONMHRIGM] shown in Algorithm 1 2 . The step learning rate γt is set as 1 √n at each stage t. 1 Since it is a simple extension of Theorem 1, we omit it here. 2 It is easy to degenerate it for solving ONMHRIGS by setting m = 1; hence we omit it. ## Algorithm 1 Online learning algorithm for ONMHRIGM Input: n, online revealed coefficient pair (ut,w, at) Parameter: learning rate γt = 1 √n Output: a sequence of online decisions xt - 1: Let e = bn - 2: Initialize p1 = 0 3: for t = 1, 2, · · · , n do - 5: if vt > 0 then - 8: else - 9: Set xt = 0 - 12: end for - 13: return (xt)t∈N The performance of the online learning algorithm is evaluated by introducing the performance measure - regret- which is a common metric of online learning approach [Balseiro and Gur, 2019]. Denote by R∗n = ∑nt=1 uTt x∗t the optimal objective value of the online problem ONMHRIGM, and Rn = ∑nt=1 uTt xt the actual objective value under the online learning strategy (xt)t∈N. The expected optimality gap between them is Denote by Ξ the family of distribution P, then the definition of regret is formally given as According to Corollary 1, when the number of stages n → ∞, we have the average regret ∆n n → 0, which theoretically illustrates the priority of Algorithm 1. Corollary 1. If the step learning rate γt = 1 √n for t ∈ N, then Algorithm 1 achieves O( 1 √n ) average regret of problem ONMHRIGM. (Proof in Appendix) ## 5 Case Study on Externalities of Anti-Ebola Humanitarian Practice in DR Congo In conjunction with a real case of anti-Ebola practice in conflict areas of the DR Congo, we quantitatively analyze the externalities of humanitarian relief operations as a case study in this section. The humanitarian rescuer and the rebel group interact with each other in this empirical case. The rescuer plans to pass through the conflict area in order to transport supplies to the city affected severely by the epidemic, while the rebel group as an attacker aims to gain payoff by controlling some routes. ## 5.1 The Ebola Epidemic and Rebel Conflicts The second largest DR Congo Ebola outbreak in December 2019 has been a humanitarian crisis that originated in an active conflict area, which has severely affected the ability of relief efforts and vaccination [Schwartz, 2020]. In the major epidemic area, i.e., the Eastern DR Congo including NordKivu and Sud-Kivu province, more than 10 active armed rebel groups are scattered [Usanov et al., 2013]. These armed groups actively operate in the regions of Ebola virus relief, controlling the routes in and out of the regions, levying taxes on households and transport, and attacking healthcare and relief workers [Schwartz, 2020]. As a result, humanitarian relief operations in the region face huge risks and uncertainties from those rebel groups. Figure 1: The Situation of Ebola Epidemic and Rebel Conflicts in Nord-Kivu and Sud-Kivu Province of DR Congo. ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000000_f63e6a169113b0d576b34f738f97dff37267d60bb6a725f49199cca5f93d1514.png) We collect the statistical data of DR Congo including Ebola outbreak data, conflict statistics and road network data in Nord-Kivu and Sud-Kivu province. The Ebola outbreak data in the same period reported by the World Health Organization is visualized as the map in Figure 1(a) [WHO, 2020]. The conflict data from 31 December 2018 to 5 January 2020 in the same area is shown in Figure 1(b), which is offered by the Armed Conflict Location & Event Data Project [Clionadh et al., 2010; ACLED, 2020]. The road network of Nord-Kivu and Sud-Kivu province contains 810 vertices (i.e., cities and towns) and 2,188 arcs (i.e., major and other roads). Assuming that a city's relief demands are positively correlated with the number of new Ebola cases in that city, we can obtain statistics on urban relief demands over time, as shown in the Figure 2. The areas most affected by Ebola, such as Katwa and Beni in Nord-Kivu, were in huge need of emergency humanitarian relief. Unfortunately, the road network from non-infected areas (e.g., Bukavu in Sud-Kivu province) to those demand cities is under the control or influence sphere of rebel groups to a large extent. In this case, the city Bukavu, Kitchanga, Walikale, Goma, Osso are set as the potential bases of relief resources, and the demand cities include Beni, Butembo, Katwa, Kalunguta, Mabalako and Oicha. Specifically, the traversing cost c is set as the length of the actual road between cities. The added cost of transporting d is assumed to be uniformly distributed on [1, ¯c], where ¯c denotes the average value of c. The movement cost ft is supposed to be uniformly distributed on [1, v ¯L], where ¯L denotes the average distance between relief sites and demand cities, and v represents the maximum cost coefficient. Denote by W = ∑nt=1 wt the total demand during this period, and C Figure 2: Statistics on Urban Relief Demand over Time in NordKivu and Sud-Kivu province of DR Congo. ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000001_b7ebe8f8c86040b51bb228e3ad16fba60b03c19798979fea5c7a2f8b25c48a72.png) the total transporting cost of satisfying all demands over the period. Let the relief resource budget b1 = αW, the transportation budget b2 = βC. ## 5.2 Externality Analysis of Humanitarian Relief Operations We quantitatively analyze the Externalities of humanitarian relief operations against the Ebola epidemic in DR Congo, including the externality of financing the rebel groups and expanding the range of their activities. Also, we analyze the optimality performance of Algorithm 1 3 . ## Externality I: Financing the Rebel Groups Passively As mentioned above, the attacker may levy taxes on or outright rob the relief resources, thereby passively financing rebel groups. According to the notations in game Gt, the total loss of relief supplies at stage t will become a kind of external income for rebel groups, and the total quantity I lost supplies is In empirical case of anti-Ebola humanitarian operations, we have found that long-lasting medical and relief operations targeting epidemic outbreak sites can lead to indirect funding of local insurgent groups, which is denoted by Externality I for simplicity. Furthermore, increasing the intensity and frequency of humanitarian aid may exacerbate this negative externality though alleviating shortages in outbreak regions. As shown in Figure 3, the negative impact of Externality I gradually becomes more pronounced as the budget for relief supplies increases 4 . As the proportion of relief resource budgets α increases from 0.1 to 0.9, more relief demands will be met, but at the cost of a rise in the amount looted by rebel groups (from 4.1 to 89.2). Moreover, the ratio of robbed to actual arrived relief supplies increased from 12.9% to 39.0%, indicating that the effect of Externality I has been significantly intensified. On the other hand, we analyze the impact of humanitarian relief supply policies, i.e, single- and multiple-source policy, on this negative externality. It is found that multiplesource policy can significantly alleviate Externality I compared to the single-source policy. Comparatively speaking, multiple-source policy tends to greatly reduce the loss of relief resources caused by rebel groups robbery while increasing the ratio of meeting relief demands, thereby reducing passive funding for insurgent activities. The quantity of relief resources robbed by attackers decreases from 38.0 to 12.4 while the quantity delivered to civilians in need grows from 144.0 to 169.6 as shown in Figure 4. 3 Experimental results in Appendix 4 The impact of transportation budget on Externality I is analyzed in Appendix. Figure 3: Externality I under Different Ratio of Relief Resources Budget (n = 50, b2 = 0.5C, v = 0.1) ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000002_598da0e3df792d6c4bcb6aa1baa089845f94feac791d151fda4d930069d8c379.png) ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000003_2fe35b0d00a82ea49ab245777a250b733b6be46e98633ac63c49c944e4953c14.png) Figure 5: Externality II under Different Ratio of Relief Resources Budget (n = 50, b2 = 0.5C, v = 0.1) ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000004_4abd5b47eba52431a478f96700f643f45923d54dc63006c9e243b2716d5c8466.png) Figure 4: Externality I under Different Policies of Relief Supply (n = 50, b1 = 0.5W, b2 = 0.5C, v = 0.1) ![Image](https://ijcai.org/proceedings/2023/fulltext/696/image_000005_11503b4a1dd826d5db65ccfaa738566805ad43b0d7c87f2607b02068b61ba414.png) ## Externality II: Expanding the Range of Rebel Activities The presence of humanitarian relief supplies in conflict areas is likely to attract the attack targeting aid workers from armed rebel groups around [Schwartz, 2020]. As a result, the range of armed rebel activities will be altered and may be expanded due to the impact of humanitarian operations. We here give the definition of Scope Expansion Ratio of rebel activities denoted by where Vc denotes the initial node set controlled by rebel groups and Vch represents the set of controlled nodes after the implementation of a series of humanitarian relief operations. We find that humanitarian relief operations in conflict areas can increase the activity of insurgent groups to some extent, as evidenced by the scope expansion of their activities in an attempt to loot more relief supplies, hereinafter referred to as Externality II. As shown in Figure 5, with the increase in α, the scope expansion ratio becomes more than doubled from 38.9% of the initial range of activities, reporting an surge of 108.9%. This will significantly increase the scope of the conflict and potentially involve more innocent civilians in conflict and risk. Similarly, we analyze the impact of humanitarian relief supply policies on Externality II. It can be observed that there has been no significant change in the average ratio of the scope expansion of conflict activities when the multisource relief policy is applied as shown in Figure 6. This suggests that the multi-source relief policy does not intensify the Externality II as intuitively as expected, though the scope of humanitarian activities has expanded under this policy. Figure 6: Externality II under Different Policies of Relief Supply (n = 50, b1 = 0.5W, b2 = 0.5C, v = 0.1) ## 6 Conclusion In this paper, we quantitatively analyze the potential externalities associated with long-lasting humanitarian relief operations based on game-theoretical modeling and online planning approaches. In conjunction with a real case of anti-Ebola practice in conflict areas of DR Congo, two kinds of externalities are found in the ase study, i.e, Externality I: longlasting humanitarian relief operations targeting alleviation of crises in conflict areas can lead to indirect funding of local rebel groups; Externality II: these operations in conflict areas can increase the activities of insurgent groups to some extent, as evidenced by the scope expansion of their activities in an attempt to loot more relief supplies. Furthermore, the impacts of humanitarian aid intensity, frequency and supply policies on the above externalities are quantitatively analyzed, which will provide enlightening decision-making support for the implementation of related operations in the future. This work might inspire more efforts in the field of AI on realistic data-driven humanitarian operations research, especially AI assisted policy design and externality analysis of humanitarian operations, for the good of those civilians suffering from both disasters and conflicts. ## Ethical Statement There are no ethical issues. ## References 1. [ACLED, 2020] ACLED. Conflict data in nord-kivu and sud-kivu province of dr congo. https://acleddata.com/ about-acled/, 2020. Accessed: 2023-06-16. 2. [Agarwal et al., 2022] Sachin Agarwal, Ravi Kant, and Ravi Shankar. Humanitarian supply chain management: Mod- eling the pre and post-disaster relief operations. Interna- tional Journal of Disaster Resilience in the built environ- ment, 13(4):421-439, 2022. 3. [Balseiro and Gur, 2019] Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Re- gret minimization and equilibrium. Management Science, 65(9):3952-3968, 2019. 4. [Balseiro et al., 2020] Santiago Balseiro, Haihao Lu, and Va- hab Mirrokni. Dual mirror descent for online allocation problems. In International Conference on Machine Learn- ing, pages 613-628. PMLR, 2020. 5. [Borrero et al., 2019] Juan Sebastian Borrero, Oleg A Prokopyev, and Denis Sauré. Sequential interdiction with incomplete information and learning. Operations Re- search, 67(1):72-89, 2019. 6. [Bryer and Cairns, 1997] David Bryer and Edmund Cairns. For better? for worse? humanitarian aid in conflict1. De- velopment in Practice, 7(4):363-374, 1997. 7. [Buchbinder and Naor, 2009] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for covering and packing. Mathematics of Operations Research, 34(2):270- 286, 2009. 8. [Clionadh et al., 2010] Raleigh Clionadh, Andrew Linke, Håvard Hegre, and Joakim Karlsen. Introducing acled- armed conflict location and event data. Journal of Peace Research, 47(5):651-660, 2010. 9. [de Montclos, 2009] MA Pérouse de Montclos. Humanitar- ian aid and the biafra war: lessons not learned. Africa Development, 34(1), 2009. 10. [Ekici and Özener, 2020] Ali Ekici and Okan Örsan Özener. Inventory routing for the last mile delivery of humanitarian relief supplies. Springer Berlin Heidelberg, 2020. 11. [Elayah and Ahmed, 2022] Moosa Elayah and Noman Ahmed. Humanitarian aid in yemen: A crisis of sovereignty and inevitable harm. In Reconciliation, Heritage and Social Inclusion in the Middle East and North Africa, pages 173-191. Springer, 2022. 12. [Elayah et al., 2021] Moosa Elayah, Matilda Fenttiman, et al. Humanitarian aid and war economies: The case of yemen. Economics of Peace and Security Journal, 16(1):52-65, 2021. 13. [Fathalikhani et al., 2018] Somaye Fathalikhani, Ashkan Hafezalkotob, and Roya Soltani. Cooperation and coope- tition among humanitarian organizations: A game theory approach. Kybernetes, 47(8):1642-1663, 2018. 14. [Findley, 2018] Michael G Findley. Does foreign aid build peace? Annual Review of Political Science, 21:359-384, 2018. 15. [Fulkerson and Harding, 1977] D Ray Fulkerson and Gary C Harding. Maximizing the minimum source-sink path sub- ject to a budget constraint. Mathematical Programming, 13(1):116-118, 1977. 16. [Ghasemi et al., 2022] Peiman Ghasemi, Fariba Goodarzian, Jesús Muñuzuri, and Ajith Abraham. A cooperative game theory approach for location-routing-inventory decisions in humanitarian relief chain incorporating stochastic plan- ning. Applied Mathematical Modelling, 104:750-781, 2022. 17. [Israeli and Wood, 2002] Eitan Israeli and R. Kevin Wood. Shortest-Path Network Interdiction. Networks, 40(2):97- 111, sep 2002. 18. [Li et al., 2020] Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online lin- ear programming. arXiv preprint arXiv:2003.02513, 2020. 19. [Modgil et al., 2020] Sachin Modgil, Rohit Kumar Singh, and Cyril Foropon. Quality management in humanitarian operations and disaster relief management: A review and future research directions. Annals of operations research, pages 1-54, 2020. 20. [Muggy and L. Heier Stamm, 2014] Luke Muggy and Jes- sica L. Heier Stamm. Game theory applications in hu- manitarian operations: a review. Journal of Humanitar- ian Logistics and Supply Chain Management, 4(1):4-23, 2014. 21. [Nagurney et al., 2016] Anna Nagurney, Emilio Alvarez Flores, and Ceren Soylu. A generalized nash equilib- rium network model for post-disaster humanitarian relief. Transportation research part E: logistics and transporta- tion review, 95:1-18, 2016. 22. [Nagurney et al., 2019] Anna Nagurney, Mojtaba Salarpour, and Patrizia Daniele. An integrated financial and logistical game theory model for humanitarian organizations with purchasing costs, multiple freight service providers, and budget, capacity, and demand constraints. International Journal of Production Economics, 212:212-226, 2019. 23. [Narang and Stanton, 2017] Neil Narang and Jessica A Stan- ton. A strategic logic of attacking aid workers: Evidence from violence in afghanistan. International Studies Quar- terly, 61(1):38-51, 2017. 24. [Nguyen and Smith, 2022] Di H Nguyen and J Cole Smith. Network interdiction with asymmetric cost uncertainty. European Journal of Operational Research, 297(1):239- 251, 2022. [OCHA, 2022] OCHA. Global humanitarian overview 2022. https://www.unocha.org/sites/unocha/files/ GlobalHumanitarianOverview2022.pdf, 2022. Accessed: 2023-06-16. 25. [Prine, 2020] Mia Prine. Hunger Games: An Analysis of How the Humanitarian Response to the 1983 Ethiopian Famine Enabled Aid Misuse and Prolonged Conflict. Bachelor's thesis, Claremont McKenna College, Columbia Avenue Claremont, CA, 2020. 26. [Schwartz, 2020] David A. Schwartz. Being Pregnant during the Kivu Ebola Virus Outbreak in DR Congo: The rVSV- ZEBOV Vaccine and Its Accessibility by Mothers and In- fants during Humanitarian Crises and in Conflict Areas. Vaccines, 8(1):38, jan 2020. 27. [Sinha et al., 2018] Arunesh Sinha, Fei Fang, Bo An, Christopher Kiekintveld, and Milind Tambe. Stackelberg security games: Looking beyond a decade of success. IJ- CAI, 2018. 28. [Smith and Song, 2020] J. Cole Smith and Yongjia Song. A survey of network interdiction models and algorithms. Eu- ropean Journal of Operational Research, 283(3):797-811, 2020. 29. [Terry, 2011] Fiona Terry. The international committee of the red cross in afghanistan: reasserting the neutrality of humanitarian action. International Review of the Red Cross, 93(881):173-188, 2011. 30. [Usanov et al., 2013] Artur Usanov, Marjolein Ridder, Willem L. Auping, Stephanie Lingemann, Luis A Tercero Espinoza, Magnus Ericcson, Masuma Farooki, Sievers Henrike, and Liedtke Maren. Coltan, Congo & Conflict. 2013. 31. [Väyrynen, 2023] Raimo Väyrynen. Complex humanitarian emergencies: Concepts and issues. Raimo Väyrynen: A Pi- oneer in International Relations, Scholarship and Policy- Making: With a Foreword by Olli Rehn and a Preface by Allan Rosas, pages 301-343, 2023. 32. [WHO, 2020] WHO. Ebola virus disease -democratic republic of the congo. https://www.who.int/csr/don/ 16-january-2020-ebola-drc/en/, 2020. Accessed: 2023- 06-16. 33. [Wood and Molfino, 2016] Reed M Wood and Emily Molfino. Aiding victims, abetting violence: The influence of humanitarian aid on violence patterns during civil conflict. Journal of global security studies, 1(3):186-203, 2016. 34. [Wood and Sullivan, 2015] Reed M Wood and Christopher Sullivan. Doing harm by doing good? the negative exter- nalities of humanitarian aid provision during civil conflict. The Journal of Politics, 77(3):736-748, 2015. 35. [Wood, 1993] R Kevin Wood. Deterministic network inter- diction. Mathematical and Computer Modelling, 17(2):1- 18, 1993. 36. [Xiao et al., 2018] Kaiming Xiao, Cheng Zhu, Junjie Xie, Yun Zhou, Xianqiang Zhu, and Weiming Zhang. Dynamic defense strategy against stealth malware propagation in cyber-physical systems. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications, pages 1790- 1798. IEEE, 2018. 37. [Xie and Aros-Vera, 2022] Xiaodan Xie and Felipe Aros- Vera. An interdependent network interdiction model for disrupting sex trafficking networks. Production and Oper- ations Management, 31(6):2695-2713, 2022. 38. [Xu et al., 2017] Kai Xu, Kaiming Xiao, Quanjun Yin, Yabing Zha, and Cheng Zhu. Bridging the gap between observation and decision making: Goal recognition and flexible resource allocation in dynamic network interdic- tion. In Twenty-Sixth International Joint Conference on Artificial Intelligence, pages 4477-4483, 2017. 39. [Yan et al., 2020] Jingwen Yan, Kaiming Xiao, Cheng Zhu, Jun Wu, Guoli Yang, and Weiming Zhang. Bi-layer shortest-path network interdiction game for internet of things. Sensors, 20(20):5943, 2020. 40. [Yang et al., 2022] Haoyu Yang, Kaiming Xiao, Lihua Liu, Hongbin Huang, and Weiming Zhang. An online learn- ing approach towards far-sighted emergency relief plan- ning under intentional attacks in conflict areas. In Lud De Raedt, editor, Proceedings of the Thirty-First Interna- tional Joint Conference on Artificial Intelligence, IJCAI- 22, pages 4679-4685. International Joint Conferences on Artificial Intelligence Organization, 7 2022. 41. [Zhang et al., 2019] Youzhi Zhang, Qingyu Guo, Bo An, Long Tran-Thanh, and Nicholas R Jennings. Optimal in- terdiction of urban criminals with the aid of real-time in- formation. In Proceedings of the AAAI Conference on Ar- tificial Intelligence, volume 33, pages 1262-1269, 2019.