{'fraction_non_alphanumeric': 0.035691078815157616, 'fraction_numerical': 0.01039669080938872, 'mean_word_length': 4.4231198968629135, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Multi-Agent Decentralized Network Interdiction Games

In this work, we introduce decentralized network interdiction games, which model the interactions among multiple interdictors with differing objectives operating on a common network. As a starting point, we focus on decentralized shortest path interdiction (DSPI) games, where multiple interdictors try to increase the shortest path lengths of their own adversaries, who all attempt to traverse a common network. We first establish results regarding the existence of equilibria for DSPI games under both discrete and continuous interdiction strategies. To compute such an equilibrium, we present a reformulation of the DSPI games, which leads to a generalized Nash equilibrium problem (GNEP) with non-shared constraints. While such a problem is computationally challenging in general, we show that under continuous interdiction actions, a DSPI game can be formulated as a linear complementarity problem and solved by Lemke's algorithm. In addition, we present decentralized heuristic algorithms based on best response dynamics for games under both continuous and discrete interdiction strategies. Finally, we establish theoretical bounds on the worst-case efficiency loss of equilibria in DSPI games, with such loss caused by the lack of coordination among noncooperative interdictors, and use the decentralized algorithms to empirically study the average-case efficiency loss.


Introduction
In an interdiction problem, an agent attempts to limit the actions of an adversary operating on a network by intentionally disrupting certain components of the network. Such problems are usually modeled in the framework of leader-follower games and can be formulated as bilevel optimization problems. Interdiction models have been used in various military and homeland security applications such as dismantling drug traffic networks [58], preventing nuclear smuggling [39] and planning tactical air strikes [29]. Interdiction models have also found applications in other areas such as controlling the spread of pandemics [4] and defending attacks on computer communication networks [50].
Traditionally, interdiction problems have been analyzed from a centralized perspective. In other words, a single agent is assumed to analyze, compute and implement interdiction strategies. In many situations, however, it might be desirable and even necessary to consider an interdiction problem from a decentralized perspective. For instance, a supervising body, in control of multiple agents in a common system, may assign each agent to an adversary of interest. Each agent is then responsible for computing and implementing its own interdiction strategy against the designated adversary. Other situations may involve multiple independent agents, such as security agencies of different countries, trying to achieve a common goal on a shared network. Without any coordination between the agents, one might expect that a decentralized interdiction strategy may be inefficient compared to one determined by a central decision maker. This paper is focused on modeling and analyzing such settings and the inefficiencies that may arise.
In this paper, we introduce decentralized network interdiction (DNI) games, in which multiple agents with differing objectives are interested in interdicting parts of a common network. We focus on a specific class of these games, which we call decentralized shortest path interdiction (DSPI) games. We investigate various properties of equilibria in DSPI games, including their existence and uniqueness, and propose algorithms to compute equilibria of these games. Using these algorithms, we also conduct empirical studies on the efficiency loss of equilibria in the DSPI game in comparison to optimal solutions obtained through centralized decision-making.
Decentralized network interdiction games, as will be formally defined in Section 2, appear to be new. To the best of our knowledge, there has been no previous research on such games. As a result, not much is known about the inefficiency of equilibria for these games or intervention strategies to reduce such inefficiencies. There has been a considerable amount of work, however, on interdiction problems from a centralized decision-maker's perspective. As mentioned earlier, interdiction problems have been studied in the context of various military and security applications. For extensive reviews of the existing academic literature on interdiction problems, we refer the readers to Church et al. [10] and Smith and Lim [50].
There have also been many studies on the inefficiency of equilibria in other game-theoretic settings. Most of the efforts have been focused on routing games [7,43,57], in which selfish agents route traffic through a congested network, and congestion games [46], a generalization of routing games. Some examples include [5,8,9,11,13,27,47,48,51]. Several researchers have also studied the inefficiency of equilibria in network formation games, in which agents form a network subject to potentially conflicting connectivity goals [1-3, 16, 20]. The inefficiency of equilibria has been studied in other games as well, such as facility location games [54], scheduling games [36], and resource allocation games [33,34]. Almost all of the work described above study the worst-case inefficiency of a given equilibrium concept. Although a few researchers have studied the average inefficiency of equilibria, either theoretically or empirically, and have used it as a basis to design interventions to reduce the inefficiency of equilibria [12,52], research in this direction has not received much attention.
One potential reason for the lack of attention paid to decentralized network interdiction games may be that such games belong to the class of generalized Nash equilibrium problems (GNEPs), in which both the agents' objective functions as well as their feasible action spaces depend on other agents' actions. Although the conceptual framework of GNEPs can be dated to Debreu [15] and Rosen [45], rigorous theoretical and algorithmic treatments of GNEPs only began in recent years [22]. Several techniques have been proposed to solve GNEPs, including penalty-based approaches [23,28,42], variational-inequality-based approaches [41], Newton's method [19], projection-like methods [59], and relaxation approaches [37,53]. Most of the work on GNEPs has focused on games with shared constraints, mainly due to their tractability [21,30]. In such games, a set of identical constraints appear in each agent's feasible action set. However, as will be seen later, in a typical decentralized network interdiction game, the constraints involving multiple agents' actions that appear in each agent's action space are not identical. As a result, such games give rise to more challenging instances of GNEPs.
One of the major contributions of this work is that we show the GNEPs derived from DSPI games to have special mathematical structure. First, we show that a DSPI game (either under discrete or continuous interdiction) always admits a potential function (whose exact definition will be provided in Section 3.2). With this result, we are able to prove the existence of equilibria for DSPI games. Second, for continuous interdiction DSPI games, we show that each agent's optimization problem can be reformulated as a linear programming problem. As a result, the equilibrium conditions of the game can be reformulated as a linear complementarity problem with some favorable properties, allowing it to be solved by the well-known Lemke algorithm. In addition, we present decentralized algorithms for finding equilibria of DSPI games. These algorithms are based on the well-known best-response dynamics (or Gauss-Seidel iterative) approach. While such an approach is only a heuristic method (as convergence to a Nash equilibrium cannot be shown, even with the potential function property), we obtain encouraging empirical results for the performance of the method on several classes of network structures. We also use these algorithms on some instances of DSPI games to empirically quantify the average-case efficiency loss when interdicting agents behave selfishly. Such results can help central authorities design mechanisms to reduce such efficiency losses for practical instances.
The remainder of this paper is organized as follows. We begin in Section 2 with definitions and formulations of DNI games and DSPI games. In Section 3, we present the main theoretical results of the paper, including an analysis of the existence and uniqueness of equilibria in DSPI games, as well as a proof that these games admit potential functions. In Section 4 we investigate algorithms for solving DSPI games. We describe a centralized algorithm based on a linear complementarity formulation, as well as decentralized algorithms for computing equilibria of DSPI gamesi. We also give results of our computational experiments with these algorithms on instances of DSPI games. Finally, in Section 5, we provide some concluding remarks.

Formulation
Network interdiction problems involve interactions between two types of parties -adversaries and interdictors -with conflicting interests. An adversary operates on a network and attempts to optimize some objective, such as the flow between two nodes. An interdictor tries to limit an adversary's objective by changing elements of the network, such as the arc capacities. Such interactions have historically been viewed from a leader-follower-game perspective. The interdictor acts as the leader and chooses an action while anticipating the adversary's potential responses, while the adversary acts as the follower and makes a move after observing the interdictor's actions. From the interdictor's perspective, this captures the pessimistic viewpoint of guarding against the worst possible result given its actions.
In this work, we consider strategic interactions among multiple interdictors who operate on a common network. The interdictors may each have their own adversary or have a common adversary. If there are multiple adversaries, we assume there is no strategic interaction among them. We also assume that the interdictors are allies in the sense that they are not interested in deliberately impeding each other.
Formally, we have a set F = {1, . . . , F } of interdictors or agents, who operate on a network G = (V, A), where V is the set of nodes and A is the set of arcs. Each agent's actions or decisions correspond to interdicting each arc of the network with varying intensity: the decision variables of agent f ∈ F are denoted by x f ∈ X f ⊂ R |A| , where X f is an abstract set that constrains agent f 's decisions. For any agent f ∈ F, let x −f denote the collection of all the other agents' decision variables; in other words, The network obtained after every agent executes its decisions or interdiction strategies is called the aftermath network. The strategic interaction between the agents occurs due to the fact that the properties of each arc in the aftermath network are affected by the combined decisions of all the agents.
In addition to the abstract constraint set X f , we assume that each agent f ∈ F faces a total interdiction budget of b f > 0. The cost of interdicting an arc is linear in the intensity of interdiction; in particular, agent f 's cost of interdicting arc (u, v) by x f uv units is c f uv x f uv . We assume that c f uv > 0 for all (u, v) ∈ A and f ∈ F.
The optimization problem for each agent f ∈ F is: where the objective function θ f is agent f 's obstruction function, or measure of how much agent f 's adversary has been obstructed. Henceforth, we refer to the game in which each agent f ∈ F solves the above optimization problem (1) as a decentralized network interdiction (DNI) game. The obstruction function θ f can capture various types of interdiction problems. Typically θ f is the (implicit) optimal value function of the adversary's network optimization problem parametrized by the agents' decisions, which usually minimizes flow cost or path length subject to flow conservation, arc capacity and side constraints. Suppose that a central planner, with a comprehensive view of the network and the agents' objectives, could pool the agents' interdiction resources and determine an interdiction strategy that maximizes some global measure of how much the agents' adversaries have been obstructed. Let θ c (x 1 , . . . , x F ) represent the global obstruction function for a given interdiction strategy (x 1 , . . . , x F ). The central planner's problem corresponding to the DNI game (1) is then as follows: We refer to (2) as the centralized problem, and focus primarily on when the global obstruction function is utilitarian; that is, As mentioned earlier, one of the goals of this work is to quantify the inefficiency of an equilibrium of a DNI game -a decentralized solution to problem (1) -relative to a centrally planned optimal solution -an optimal solution to problem (2). A commonly used measure of such inefficiency is the price of anarchy.
Formally speaking, let N I be the set of all equilibria corresponding to a specific instance I. (In the context of DNI games, an instance consists of the network, obstruction functions, interdiction budgets, and costs.) For the same instance I, let (x 1 * , . . . , x F * ) denote a global optimal solution to the centralized problem (2). Then the price of anarchy of the instance I is defined as Let I be the set of all instances of a game. We assume implicitly that for all I ∈ I, the set N I is nonempty and a global optimal solution to the centralized problem exists. By convention, p is set to 1 if the worst equilibrium as well as the global optimal solution to the centralized problem both have zero objective value. If the worst equilibrium has a zero objective value while the global optimum is nonzero, p is set to be infinity. In addition to the price of anarchy for an instance of a game, we also define the worst-case price of anarchy over all instances of the game (denoted as w.p.o.a) as follows: w.p.o.a := sup I∈I p(I).
Since we wish to study properties of a class of games such as DNI games, rather than a particular instance of a game, we are more interested in the worst-case price of anarchy. However, there are two major difficulties associated with such an efficiency measure. First, it is well-known that the worst-case price of anarchy may be a very conservative measure of efficiency loss, since the worst case may only happen with pathological instances. Second, explicit theoretical bounds on the worst-case price of anarchy may be difficult to obtain for general classes of games. Indeed most of the related research has focused on identifying classes of games where such bounds may be derived. In this work, we show how our proposed decentralized algorithms can be used to empirically study the average-case efficiency loss (denoted by a.e.l). Let I denote a finite set such that I ⊂ I, and let |I | denote the cardinality of the the set I . Then a.e.l : In other words, the average-case efficiency loss is the average value of p(I) as defined in (3) over a set of sampled instances I ⊂ I of a game. As mentioned above, the generic form of problem (1) can be used to describe various network interdiction settings, such as maximum flow interdiction. To start with models that are both theoretically and computationally tractable, we focus on decentralized shortest-path interdiction games, which we describe in detail next.

Decentralized Shortest Path Interdiction Games
As the name suggests, decentralized shortest path interdiction (DSPI) games involve players or interdictors whose adversaries are interested in the shortest path between source-target node pairs on a network. Interdictors act in advance to increase the length of the shortest path of their respective adversaries by interdicting (in particular, lengthening) arcs on the network.
To describe these games formally, we build upon the setup for the general decentralized network interdiction game described in Section 2.1. Each agent f ∈ F has a target node t f ∈ V which it wishes to protect from an adversary at source node s f ∈ V by maximizing the length of the shortest path between the two nodes. The agents achieve this goal by committing some resources (e.g. monetary spending) to increase the individual arc lengths on the network: the decision variable x f uv represents the contribution of agent f ∈ F towards lengthening arc (u, v) ∈ A. The arc length d uv (x f , x −f ) of arc (u, v) ∈ A in the aftermath network depends on the decisions of all the agents.
We consider two types of interdiction. The first type of interdiction is continuous: in particular, ∈ A} and the arc lengths after an interdiction strategy (x 1 , . . . , x F ) has been executed are where d 0 uv > 0 is the initial length of arc (u, v). We make the positivity assumption on initial arc lengths without loss of generality, since we may always pad the arc lengths without changing the shortest paths. In this scenario, x f uv captures how much agent f extends the length of arc (u, v). The second type of interdiction is discrete: in this case, 1} ∀(u, v) ∈ A} and the arc lengths in the aftermath network are where e uv ∈ R ≥0 is the fixed extension of arc (u, v). In other words, the length of an arc is extended by a fixed amount if at least one agent decides to interdict it. The optimization problem solved by each agent f ∈ F in a DSPI game is given by (1), where where binary variable z f uv in (8) represents whether an arc (u, v) ∈ A is in the shortest s f -t f path. In other words, agent f 's optimization problem is a bilevel optimization problem, where the inner minimization problem (8) is its adversary's shortest path problem. Although the inner minimization problem is an integer program with binary variables, it is well known that the constraint matrix is totally unimodular (e.g. [49]), rendering the integer program equivalent to its linear programming relaxation. Therefore, once the interdictors' variables (x 1 , . . . , x F ) are fixed, we can use linear programming duality to transform the inner minimization problem to a maximization problem [32] and reformulate agent f 's optimization problem (1) as: maximize It is well known (see, for example, [6,35]) that at optimality, the term y f u − y f s f is equal to the length of the shortest s f -u path in the aftermath network. This fact has several important implications for problem (9). For instance, it allows us to restrict the y f variables to be integral if the underlying network data is integral, since at optimality all path lengths would also be integral. Moreover, as we show below, it also allows us to bound the y f variables.
When interdiction is continuous, the largest possible length in the aftermath network for any arc is bounded by the largest interdiction possible on that arc. Keeping the budgetary constraints in mind, the maximum interdiction possible on any arc is bounded by As a result, the maximum length of any arc (u, v) ∈ A in the aftermath network is bounded by Therefore, the lengths of every path in the aftermath network are bounded above by On the other hand, when interdiction is discrete, the length of any path in the aftermath network is bounded Since only the differences y f v − y f u across arcs (u, v) are relevant to the formulation (9), we may always replace y f u by y f u − y f s f for each u ∈ V to obtain a feasible solution with equal objective value. Therefore we can then add the constraints −M ≤ y f u ≤ M for all u ∈ V to the problem (9) to obtain an equivalent formulation of a DSPI game, where each agent f ∈ F solves the following problem.
When analyzing the DSPI game from a centralized decision-making perspective, we assume that the global obstruction function is utilitarian, i.e., the sum of the shortest s f -t f path lengths over all the agents f ∈ F. We also assume that the resources are pooled among all the agents, resulting in a common budgetary constraint. Thus the centralized problem for DSPI games can be given as follows: Since y f is bounded for all f ∈ F, a globally optimal solution of (11) exists regardless of whether x f is continuous or discrete for all f ∈ F. In the continuous case, Weierstrass's extreme value theorem applies since all the functions are continuous and the x f variables are bounded due to the non-negativity and budgetary constraints. In the discrete case, there are only a finite number of values that the x f variables can take.

Generalized Nash Equilibrium Problems
The formulation (10) gives us some insight into the structure of strategic interactions among agents in a DSPI game. Note that in formulation (10), the objective function for each agent f ∈ F only depends on variables indexed by f (in particular, y f s f and y f t f ). However, the constraint set for each agent f is parametrized by other agents' variables x −f . This is an instance of a generalized Nash equilibrium problem (GNEP).
Formally speaking, consider the following simultaneous-move game with complete information. 1 As before, let F = {1, . . . , F } denote the set of agents. Let the scalar-valued function θ f (χ f , χ −f ) be the payoff or objective function of agent f ∈ F, which is a function of the actions or decisions (χ f , χ −f ) of all the agents. The feasible action space of agent f ∈ F is a set-valued mapping Ξ f (χ −f ) with dimension n f . This dependence of an agent's feasible action space on the actions of other agents is the key feature of a GNEP; in a regular Nash equilibrium problem, each agent's feasible action space is a fixed set. Let n := f ∈F n f . Then Ξ f (·) is a mapping from R (n−n f ) to R n f . Parametrized by the other agents' decisions χ −f , each agent f ∈ F in a GNEP solves the following problem: It is straightforward to see how the DSPI game in (10) translates into a GNEP problem: for all f ∈ F, Note that χ = (χ 1 , . . . , χ F ) ∈ R n , where n = F (|V | + |A|).
To formally define a Nash equilibrium to a GNEP, we let Ω(χ) denote the Cartesian product of the feasible sets of each agent corresponding to decisions χ = (χ 1 , . . . , χ F ); that is, For a simultaenous-move GNEP with each agent solving problem (12), a generalized Nash equilibrium is defined as follows: GNEPs in general are more challenging than regular Nash equilibrium problems, both theoretically and computationally. While results on the existence of (pure-strategy) generalized Nash equilibria have been established, few results exist on uniqueness of such equilibria, largely due to the fact that few GNEPs have a unique equilibrium [22]. We will rely on both existing analytic results and the special structure of DSPI games to determine the existence of equilibria and their uniqueness in these games in later subsections. Before that, however, we first show an important property of the DSPI games; namely, DSPI games as formulated in (10) admit potential functions. This property is extremely helpful in establishing the existence of equilibria.

Potential Functions and Potential Games
Potential games were first proposed by Rosenthal [46] in the context of congestion games. Roughly speaking, in a potential game, an agent's decision to unilaterally improve its utility can be translated to an ascent direction of a potential function, and any global maximum of the potential function is equivalent to a Nash equilibrium of the original game. As a result, decentralized algorithms in the form of best-or better-response dynamics 2 for potential games can be shown to converge to a Nash equilibrium under relatively general conditions. Monderer and Shapley [38] formalized the concept of potential games and introduced various subclasses of such games. Perhaps the simplest subclass consists of games possessing exact potential functions, where any unilateral change in an agent's objective function corresponds to a similar change of value in the potential function. Formally, exact potential functions for GNEPs are defined as follows.
Definition 2 ([38]). A continuous function P : R n → R is said to be an exact potential function to a GNEP if for each χ ∈ Ω(χ) we have for each agent f ∈ F.
We will now show that DSPI games do in fact admit exact potential functions. Since we only deal with exact potential functions, we will refer to them henceforth simply as potential functions.
Proposition 3. The DSPI game in (10) admits a potential function.
Proof. Consider the DSPI game in (10) formulated as a GNEP as in (13), and function P : This is simply the sum of the individual agents' objective functions. It is easy to see that for each f ∈ F, when χ −f is fixed, P and θ f differ only by a constant. Therefore we have for all f ∈ F. Thus P is a potential function for the DSPI game.

Existence of Equilibria
We first consider the existence of equilibria in the DSPI game when interdiction decisions are continuous. In this case each interdictor's optimization problem (10), with the arc length function d uv (·) defined as in (6), is a linear program. The following result regarding general convex GNEPs can therefore be applied here.
Theorem 4 (Ichiishi [31]). Given a simultaneous-move GNEP with each agent f ∈ F solving (12), assume that the following conditions hold: (i) There exist nonempty, convex and compact sets K f ⊆ R n f for each agent f ∈ F such that for every is nonempty, closed and convex. In addition, is both upper and lower semicontinuous as a point-to-set map.
Then a (pure-strategy) generalized Nash equilibrium exists.
To apply Theorem 4, the following result will be useful.
Theorem 5 (Rockafellar and Wets [44]). For every f ∈ F, suppose We now use these results to show the existence of equilibria for the DSPI game. Proposition 6. Under continuous interdiction, a generalized Nash equilibrium exists for the DSPI game (10).
Proof. Recall the representation of a DSPI game as a GNEP in (13). We show that conditions (i) and (ii) in Theorem 4 hold. First, condition (ii) in Theorem 4 is immediately apparent from (10) and (13) since the objective functions are linear.
To show condition (i) holds, we define the set K f for each f ∈ F as follows: Clearly K f is nonempty for all f ∈ F as it contains the zero vector. It is also easy to see that Ξ f (x −f , y −f ) ⊆ K f and is a polyhedron, and therefore closed and convex for any given ( is also nonempty, since we can construct a feasible solution by setting x f uv = 0 for all (u, v) ∈ A and y f u to be the length of the shortest path from s f to u for all u ∈ V . Now all that remains to be shown for condition (i) in Theorem 4 to hold are the continuity properties of the point-to-set mapping Ξ f (·).
To do so we use Theorem 5. We assume without loss of generality that the arc lengths d 0 uv are positive, since we may always add a fixed constant to all of the arc lengths to achieve this without changing the shortest paths. Under these assumptions it is easily seen that setting all the x f uv and y f u variables to 0 will result in the required strict interior point. Note that the point (x f , y f ) = 0 is a strict interior point to the set irrespective of the value of (x −f , y −f ). Combined with the linearity of the constraints, this then allows us to directly apply Theorem 5 to claim the continuity of the point-to-set mapping Ξ f (·) in some neighborhood of (x −f , y −f ), which certainly implies its continuity at (x −f , y −f ). Since this property holds at any (x −f , y −f ), the mapping Ξ f (·) is both lower and upper semi-continuous on its domain.
For discrete interdiction, the main difficulty is that the formulation (10) has both discrete and continuous variables. As a result it has a discontinuous objective function with an uncountable action space, which makes analysis difficult. However it is possible to work around this issue by noting that if the input data (in particular, the initial arc lengths d 0 uv and the arc extension lengths e uv for all (u, v) ∈ A) are integral (or rational), then we may assume that the variables y f are integral (rational) at equilibrium without loss of generality. This then allows us to use the potential function (16) to show existence of a generalized Nash equilibrium.
Proposition 7. If the initial arc lengths and the arc extension lengths for the DSPI game (10) are integral, then there exists a generalized Nash equilibrium under discrete interdiction.
Proof. We claim that solving (10) under discrete interdiction is equivalent to solving the following problem: In problem (10), once the x f variables are fixed, the y f u variables represent the shortest s-u path lengths on the aftermath network. Therefore if the initial arc lengths d 0 uv and the arc extension lengths e uv are integral for all (u, v) ∈ A, then there exists an optimal solution to (10) under discrete interdiction in which y f u variables must also be integral. Thus problem (10) under discrete interdiction and problem (18) are equivalent in this sense.
A game with each agent solving problem (18) is a GNEP with a finite action space since both decision variables x f and y f are now integral and the feasible set is bounded; in other words, Ξ f (x −f , y −f ) is a finite set. We refer to this game as the discrete DSPI game. It is easy to see that the function P (·) defined in (16) is also a potential function for the discrete DSPI game.
Denote byX the set of all combinations of feasible decisions among the agents in F in the discrete DSPI game; in other words,X Note that in the discrete DSPI game,X is also a finite set. Therefore the function P (χ) achieves a maximum over the setX. Suppose the maximum is achieved atχ. We claim thatχ is in fact an equilibrium to the discrete DSPI game. Indeed for each agent f ∈ F we have that The equality follows since P (·) is an exact potential function and the inequality follows sinceχ maximizes P overX. Therefore,χ must be a GNE for the discrete DSPI game, and hence a GNE for the DSPI game under discrete interdiction.
Note that although any solution that maximizes the potential function over the setX is an equilibrium to the original DSPI game, the reverse is not true; that is, an equilibrium to the DSPI game is not necessarily a maximizer of the potential function.

Uniqueness of equilibria
Establishing conditions under which a DSPI game has a unique equilibrium is quite difficult. However, it is easy to show that there exist simple instances of DSPI games for which multiple equilibria exist. We give several such examples below.
Example 1. Consider the following instance, based on the network in Figure 1. There are 2 agents: agent 1 has an adversary with source node 1 and target node 5; agent 2 has an adversary with source node 1 and target node 6. The initial arc lengths are 0, interdiction is continuous, and the interdiction costs are the same for both agents and are given in the arc labels in Figure 1. Both agents have a budget of 1. Consider the case when = 2. One generalized Nash equilibrium occurs when agent 1 interdicts the arcs (1, 4) and (2, 5) by 1/2 each, and agent 2 interdicts arcs (1, 4) and (2, 5) by 1/6, and arc (3, 6) by 2/3. In this case both agents end up with a shortest path length of 2/3. It is easy to see that any unilateral deviation will result in a smaller shortest path length for the deviating agent. In fact, it is straightforward to see that the source-target path lengths for each agent must be equal at an equilibrium: if the path lengths are unequal, an agent could improve its objective function by equalizing the path lengths. Therefore, in this example, any combination of decision variables that results in a shortest path length of 2/3 for each agent will be a generalized Nash equilibrium, and there is a continuum of such decision variable combinations.
Example 2. A variant of this instance under discrete interdiction exhibits some interesting properties. Consider the same instance, except under discrete interdiction, with all of the arc extension lengths are equal to 1, and the budget for each agent equal to 1 + where is an integer that is at least 1. One possible equilibrium is for agent 1 to interdict the arc (1, 4) and for agent 2 to interdict the arc (1, 2). If = 1, then this will result in a shortest path length of 1 for each agent. In addition, this solution corresponds to the solution that maximizes the potential function P in (16) used in the proof of Proposition 7. Note that agent 1 does not use its entire budget. A similar equilibrium occurs when agent 1 interdicts arcs (1, 4) and (2, 5) and agent 2 interdicts arc (3,6). In this case agent 2 ends up with unused budget.
Example 3. A more interesting situation occurs when = 0 and the budget is 1. In this case, the 2 agents can interdict at most 1 arc each. Agent 1 interdicting arc (1, 4) and agent 2 interdicting arc (1, 2) results in an equilibrium in which both agents have shortest path lengths of 1. The potential function value for this equilibrium is 2.
However, there exist other equilibria in which one agent is worse off than the other. For instance, suppose agent 1 interdicts the arc (5, 6) and agent 2 interdicts (3, 6): agent 1's shortest path length is 0, and agent 2's shortest path length is 1. Although agent 1's shortest path length is now 0, it has no incentive to deviate since there is no possible unilateral deviation that would allow it to increase its shortest path length. A similar situation occurs when agent 1 interdicts (2, 5) and agent 2 interdicts (4,5). Note that the potential function P in (16) has a value of 1 for the latter two equilibria, which is strictly less than the value of 2 for the equilibrium described in the previous paragraph. It is also interesting to note that in this game, zero interdiction by both agents is also a generalized Nash equilibrium with a potential function value of 0.

Computing a Nash Equilibirum
In this section we focus on algorithms to compute equilibria of DSPI games. As discussed above, a DSPI game is a special case of a generalized Nash equilibrium problem. Computational methods to find an equilib-rium for GNEPs include reformulations as quasi-variational inequalities [42], optimization reformulations using the Nikaido-Isoda function [18,55,56], direct methods using KKT systems [17] and penalty methods [23,24], among others. We refer to the above methods as centralized algorithms, as they all attempt to find an equilibrium by tackling the game as a whole: for instance, by solving an equivalent variational inequality or complementarity problem. Such methods are usually computationally intensive.
Motivated by the observation that DSPI games admit potential functions, we also present decentralized algorithms based on best-response dynamics. Such decentralized algorithms have several advantages over centralized algorithms. First, the computational burden at each iteration is much smaller than with centralized algorithms, since only a single agent's optimization problem is solved with others agents' decisions fixed. Second, a decentralized algorithm may provide insight into how an equilibrium is achieved among agents' strategic interactions. Such insight is particularly useful when multiple equilibria exist, as is the case for many GNEPs. It is well-known (for example, [40]) that a game may possess unintuitive Nash equilibria that would never realistically be the outcome of the game. A centralized algorithm would not be able to distinguish between a meaningful and a meaningless equilibrium, and may end up computing such unintuitive equilibria. A decentralized algorithm, on the other hand, depicts how an equilibrium is achieved from a particular starting point through iterative interactions among agents, should the algorithm converge. Third, decentralized algorithms naturally lead to multithreaded implementations that can take advantage of a high performance computing environment. In addition, different threads in a multithreaded implementation may be able to find different equilibria of a game, making such an algorithm particularly suitable for computationally quantifying the average efficiency loss of decentralized strategies. Nevertheless, despite these favorable properties, best-response based algorithms suffer from a major drawback: it is difficult to theoretically prove these algorithms converge to equilibria for general classes of GNEPs.
In the following discussion, we propose solving the continuous DSPI game using a linear complementarity problem (LCP) reformulation. The reformulation is constructed using the Karush-Kuhn-Tucker (KKT) optimality conditions for each agent's optimization problem. We show that the resulting LCP has favorable properties, allowing the use of Lemke's pivoting algorithm.

Linear Complementarity Formulation
Before presenting the LCP formulation for the DSPI game, we introduce some basic notation and definitions. Formally, given a vector q ∈ R d and a matrix M ∈ R d×d , a linear complementarity problem LCP(q, M ) consists of finding a decision variable vector w ∈ R d such that The LCP(q, M ) is said to be feasible if there exists a w ∈ R d that satisfies (20) and (21). Any w satisfying (22) is called complementary. If w is both feasible and complementary, it is called a solution of the LCP. In this case, we say w ∈ SOL(q, M ) to denote that w is in the solution set for the LCP. The LCP is said to be solvable if it has a solution. A thorough exposition of the theory underlying LCPs and various algorithmic techniques to solve such problems can be found in [14]. Consider now the DSPI game with continuous interdiction, introduced in Section 2.1.1. We restate the formulation (9) for the optimization problem of agent f ∈ F as follows: As observed earlier in Section 2.1.1, the y f variables are essentially free variables. In order to simplify analysis, we restrict these variables to be non-negative while ignoring the bounds added in the formulation (10). As we shall see later, it is possible to construct a solution to (23) given a solution to (10). When the interdiction decisions of the agents f = f are fixed, agent f 's optimization problem (23) is a linear program (LP). In this case, the KKT conditions are both necessary and sufficient for a given feasible solution to be optimal. We introduce the following notation to present the KKT conditions for the LP (23) compactly. Let |V | = n and |A| = m. Denote by G the arc-node incidence matrix of the graph G. Further let I denote an identity matrix, and 0 be vectors or matrices of all zeros, of appropriate dimensions, respectively. The objective coefficients for the LP (23), denoted by o f ∈ R m+n can be given as follows: The right hand sides for the constraints in (23) are denoted using the vector r f (x −f ) ∈ R m+1 : The constraint matrix itself, denoted as A f ∈ R (m+1)×(m+n) , is Using this notation, the LP (23) can be restated as follows: x f y f ≥ 0.

(24)
Let the dual variables for the LP (23) be (λ f , β f , υ f ), where λ f are the multipliers for the arc potential constraints, β f the multiplier for the budgetary constraint and υ f the multipliers for the non-negativity constraints. The KKT conditions for (24) are given by the following system. (25) The KKT system (25) can be rewritten in the following form: In this form, it is easy to recognize that for a fixed value of x −f , the KKT system is equivalent to the The decision variable vector for the LCP is the vector of combined decision variables Each agent's KKT system (26) is parametrized by the collective decisions of other agents. As mentioned earlier, the optimization problem (23) is completely equivalent to the KKT system (26). In other words, given (x −f , y −f ), an agent's decisions (x f , y f ) is optimal if and only if it satisfies the system (26). Using this fact, it is straightforward to show that a candidate point (χ 1 , χ 2 , . . . , χ F ), where χ f = (x f , y f ), is an equilibrium to the DSPI game where each agent solves (23) if and only if it solves the KKT systems (26) for each player f ∈ F. As a consequence, the equilibrium problem for the DSPI game under consideration is equivalent to the complementarity problem obtained by stacking the F systems of (26) for f ∈ F. In this case the decision variable is the combined set of primal and dual variables for each agent, denoted by (w 1 , w 2 , . . . , w F ).
With some algebraic manipulation, it can be shown that the complementarity system obtained by stacking the F KKT systems is itself an LCP. Consider the following system obtained from (26) by expanding The interactions between the agent f 's decision variables (x f , y f ) and the KKT system of any other agent f = f can be represented using the matrixM f given below.
Here, the vector q is given by and the matrix M is given by Methods for solving LCPs fall broadly into two categories: (i) pivotal methods such as Lemke's algorithm and (ii) iterative methods such as splitting schemes and interior point methods. The former class of methods are finite when applicable, while the latter class converge to solutions in the limit. In general, the applicability of these algorithms depends on the structural properties of the matrix M . In the following analysis, we show that LCP(q, M ) for the DSPI game, as defined in (31) and (32), possesses two properties that allow us to use Lemke's pivotal algorithm: (i) the matrix M is a copositive matrix, and (ii) q ∈ (SOL(0, M )) * . Here, given a set K ∈ R d , the set K * is the dual cone of K, i.e. K * = {y ∈ R d : y T x ≥ 0 ∀x ∈ K}.
We first show that M is copositive. Recall that a matrix M ∈ R d×d is said to be copositive if x T M x ≥ 0 for all x ∈ R d + .
Lemma 8. Let the vector q and the matrix M be as defined in (31) and (32) respectively. Then the matrix M is copositive.
Proof. Let w ∈ R 2m+n+1 + . Using the block structure of M given in (32), w T M w can be decomposed as follows.
We analyze the terms under the two summations separately. First consider w f T M f w f for any agent f . Let the dual variables (λ f , β f ) be collectively denoted by δ f .
Now consider any term of the form w f TM f w f .
Proof. Consider any w ∈ SOL(0, M ). Clearly then, w f must solve the system (29) for f = 1, . . . , F , with o f , d 0 and b f taking zero values. In this case, considering the primal feasibility of w f to this system, we obtain the following.
Recall that c f a ≥ 0 for all a ∈ A and f = 1, . . . , F by assumption. Therefore, (37) implies that x f = 0 for any player f . It is easy to see that in this case, we must have The inner-product q T w can be decomposed as follows.
Since w ∈ (SOL(0, M )), Thus it only remains to verify that the objective function terms are non-negative. Consider any s f − t f path P f . By assumption, there must be at least one such path for each player f . By summing up the inequalities (38) over the arcs in the path P f , we obtain the desired result. In other words, We have thus shown thatq f T w f ≥ 0 for f = 1, . . . , F . Summing up over the players, the proof is completed.
Using the Lemmas 8 and 9, we can now state the following result about Lemke's method as it applies to LCP(q, M ).
Theorem 10 ( [14]). If M is copositive and q ∈ (SOL(q, M )) * , then Lemke's method will always compute a solution, if the problem is nondegenerate 3 In contrast to the LCP approach for solving DSPI games under continuous interdiction, we have not found a simple or efficient reformulation to solve DSPI games under discrete interdiction (in a centralized manner). In this context, we note that the two-player DSPI game with discrete interdiction may be formulated as a bimatrix game. It is well known that the mixed strategy Nash equilibria to a bimatrix game can be found by solving an LCP. However, for general DSPI games with more than two players, there is no equivalent bimatrix-like game formulation. An integer programming approach to solve the DSPI game under discrete interdiction is provided by the potential function maximization problem used in the proof of Proposition 7. However, the feasible setX is implicitly defined. Constructing a polyhedral representation of such a set poses severe challenges. Motivated by these difficulties, we also explore decentralized approaches to solve DSPI games, which we describe in the next section.

Gauss-Seidel Algorithm
We first present the simplest form of a best-response-based algorithm. The idea is simple: starting with a particular feasible decision variable vector for each agent χ 0 = (χ 1 0 , χ 2 0 , . . . , χ F 0 ), solve the optimization problem of a particular agent, say, agent 1, with all of the other agents' actions fixed. Assume an optimal solution exists to this optimization problem, and denote it as χ 1 * . The next agent, say, agent 2, solves its own optimization problem, with the other agents' actions fixed as well, but with χ 1 0 replaced by χ 1 * . Such an approach is often referred to as a diagonalization scheme or the Gauss-Seidel iteration, and for the remainder of this paper we use the latter name to refer to this simple best-response approach.
Consider applying the Gauss-Seidel iteration to a GNEP, with each agent solving the optimization problem (12). We will refer to agent f 's individual's problem as P(χ −f ). The Gauss-Seidel iterative procedure is presented in Algorithm 1 below.
The Gauss-Seidel algorithm can be directly applied to compute an equilibrium of a DSPI game with discrete interdiction. For finite termination, we fix a tolerance parameter and use the following stopping criterion: Since the variables χ k are integral for discrete interdiction problems, choosing < 1 will ensure that the algorithm terminates only when successive outer iterates are equal.
Proof. Since Algorithm 1 terminates with χ k , it satisfies (41), which implies that χ k−1 = χ k . This also implies that χ −f k−1,f = χ −f k for f = 1, . . . , F . By construction of χ k , we must then have Clearly, χ k must then be an equilibrium.
Proposition 11 establishes Algorithm 1 as a heuristic to solve the DSPI game with discrete interdiction. However, there is no guarantee that the algorithm will in fact converge, despite the fact that the DSPI game possesses a potential function. While general results on convergence of best response dynamics for potential games have been well-established in literature, the difficulty here in showing convergence lies in the fact that we are dealing with a GNEP, in which each agent's feasible region is affected by other agents' actions, and such coupling constraints do not have the same functional form for each agent. As a result, any intermediate points resulting from an agent's best responses need not be feasible in the other agents' problems.
We note however that it is possible to detect when the algorithm fails to converge. Recall that Ξ f (χ −f ) ⊆ K f for each agent f ∈ F, where K f is defined in (17). Moreover, the set F f =1 K f is finite. Any intermediate point χ k generated by Algorithm 1 must certainly satisfy the budgetary constraints on x f k and the bound constraints on y f k for each agent f . Therefore χ k ∈ F f =1 K f . In other words, the set of possible points χ k generated by Algorithm 1 lies in a finite set. This means that if the algorithm fails to converge, it must generate a sequence that contains at least one cycle. The existence of such cycles in non-convergent iterate paths can then be used to detect situations in which the algorithm might fail to converge.
For DSPI games with continuous interdiction, establishing the convergence result for a best-response type algorithm is more involved. Even for typical Nash equilibrium problems with no constraint interactions, the simple implementation of the Gauss-Seidel algorithm described in Algorithm 1 may not work. To obtain better convergence properties, we need a regularization scheme, as shown next.

Regularized Gauss-Seidel Algorithm
It can be shown that the basic diagonalization scheme of solving individual agent problems in sequence and updating agent decision variables at each step may not converge to an equilibrium even for GNEPs with favorable properties such as continuously differentiable and convex objective functions. However, Facchinei et al. [25] showed that under certain assumptions, we can overcome this issue by adding a regularization term to the individual agent's problem solved in a Gauss-Seidel iteration.
The regularized version of the optimization problem for agent f ∈ F is where τ is a positive constant. Here the regularization term is evaluated in relation to a candidate point χ f . Note that the point χ f and the other agents' decision variables χ −f are fixed when the problem (42) is solved in a regularized Gauss-Seidel iteration. For ease of notation, we will refer to problem (42) as R(χ −f , χ f ).
The regularized Gauss-Seidel procedure is given in Algorithm 2. As the name indicates, the agents' optimization problems contain a regularization term, and are solved in sequence. The regularization term ensures that problem (42) has a unique optimal solution so that the algorithm is well defined. The algorithm is set to terminate when the outer iterates become sufficiently close to each other; in other words, the termination condition is given in (41).
This version of the algorithm was originally presented in [25] to solve potential GNEPs with shared constraints. Since DSPI games are GNEPs of non-shared constraints, we use Algorithm 2 as a heuristic algorithm to solve DSPI games under continuous interdiction.

Proposition 12.
Let {χ k } be the sequence generated by applying Algorithm 2 to the DSPI problem under continuous interdiction, wherein each agent solves (10). Suppose {χ k } converges toχ. Thenχ is an equilibrium to the DSPI problem.
The proof of this theorem, though a straightforward adaptation of Theorem 4.3 in Facchinei et al. [25] does differ in one key aspect. We assume that the entire sequence {χ k } converges toχ. This is a strong assumption in the sense that it also requires that all the intermediate points χ k,f to converge toχ, a fact key to proving thatχ is indeed an equilibrium. In contrast, for GNEPs with shared constraints, the feasibility of the intermediate points ensures their convergence even to cluster points of the sequence generated by the algorithm. The complete proof of Proposition 12 is given in Appendix A.

Numerical Results
We use the algorithms presented in the previous section to study several instances of DSPI games. The decentralized algorithms were implemented in MATLAB R2010a with CPLEX v12.2 as the optimization solver. The LCP formulation for the DSPI game with continuous interdiction was solved using the MATLAB interface for the complementarity solver PATH [26]. Computational experiments were carried out on a desktop workstation with a quad-core Intel Core i7 processor and 16 GHz of memory running Windows 7.
For DSPI games with discrete interdiction, we used Algorithm 1. For DSPI games with continuous interdiction, we applied a combination of Algorithm 1 and Algorithm 2. In particular, we first tried Algorithm 1, and then used Algorithm 2 if Algorithm 1 failed to converge to an equilibrium. We pursued this strategy since the number of outer iterations until Algorithm 2 converged was found to be quite sensitive to the regularization parameter τ , typically resulting in slow convergence rates for the algorithm. Since the running time for Algorithm 1, especially with the outer iterations restricted to a maximum of 1000, was quite short relative to the running time for Algorithm 2, it seemed reasonable to try using Algorithm 1 first, and use Algorithm 2 only as necessary.

Computing Equilibria
First, we applied the algorithm to Example 2 in Section 3.3.1, which is a DSPI game with continuous interdiction. In particular, the network is given in Figure 1 and there are 2 agents: agent 1 has an adversary with source node 1 and target node 5, and agent 2 has an adversary with source node 1 and target node 6. Both agents have an interdiction budget of 1. The initial arc lengths are 0, and the interdiction costs are equal for both agents and are given as the arc labels in Figure 1, with = 2. We set the regularization parameter τ = 0.01. We were able to obtain a solution within an accuracy of 10 −6 in 3 outer iterations.
Furthermore, we obtained multiple Nash equilibria by varying the starting point of the algorithm. All the equilibria obtained resulted in the same shortest path lengths for each agent. Some of the equilibria obtained are given in Table 1. The column x 0 represents the starting interdiction vector for each agent; while x 1 N and x 2 N give the equilibrium interdiction vectors for agents 1 and 2, respectively. The seven components in the vectors of x 0 , x 1 N and x 2 N represent the interdiction actions at each of the seven arcs in Figure 1, with the arcs being ordered as follows: first, the top horizontal arcs (1, 2) and (2, 3), then the vertical arcs (1, 4), (2,5) and (3,6), and finally the bottom horizontal arcs (4,5) and (5,6). The remaining two columns in Table 1 , p 1 and p 2 , give the shortest path lengths for agents 1 and 2 respectively, at the equilibrium χ N .  Example 4. To test the algorithm on problems with larger scale, we expanded the network in Example 2 with varying graph sizes and numbers of agents. For F agents, the graph contains 2(F + 1) vertices with the edges as shown in Figure 2. The source vertex for all agents is a 1 . The target vertex for a given agent  f is b f +1 . The initial arc lengths are all assumed to be zero. The interdiction costs are the same for all the players and are given as the arc labels in Figure 2. All the agents are have an interdiction budget of 1. The cost parameter is chosen as 2. For discrete interdiction on these graphs, arc extensions are assumed to be by a length of 1.
The running time and iterations required to compute equilibria for these instances are summarized in Table 2 and Table 3. Table 2 gives the number of outer iterations and runtime for Algorithm 1 over these instances with continuous interdiction. For an empirical comparison between the decentralized and centralized approaches, the performance of Lemke's method for the LCP formulation is given in the last column of the table. The results indicate that the running time for the centralized method increases monotonically with the problem size. However, the running time for the decentralized method depends not just on the problem size but also on the number of outer iterations. In general, there is no correlation between these two parameters. Indeed the algorithm is observed to converge in relatively few iterations even for some large problem instances. This is in stark contrast to the rapid increase in running time observed for the LCP approach as problem size increases.
It must be noted that the order in which the individual agent problems are solved in Algorithm 1 plays an important role. Indeed it was found that the algorithm could fail to converge for certain agent orders, while succeeding to find equilibria quickly for the same instance with a different ordering of agents. For instance, for a network of size 25, solving the agent problems in their natural order {1, 2, . . . , 25} resulted in the failure of Algorithm 1 to converge even after 1000 outer iterations. However, with a randomized agent order, the algorithm converged in as few as 13 iterations. It is encouraging to note that for the same agent order that resulted in the failure of Algorithm 1, the regularized method Algorithm 2 converged to a GNE within 394 outer-iterations with a runtime of 28 wall-clock seconds.

Computation of Efficiency Losses
Using the decentralized algorithm and its potential to find multiple equilibria by starting at different points, we empirically study the efficiency loss of decentralized interdiction strategies in DSPI games. We focus first on Example 4, with the underlying network represented in Figure 2. Before computing the average efficiency losses empirically using our algorithms, we first establish a theoretical bound on the worst-case price of anarchy, for the purpose of comparison.
Recall that there are F agents and the source-target pair for agent f is (a 1 , b f +1 ). Noting that all paths for all agents contain either the arc (a 1 , a 2 ) or the arc (a 1 , b 1 ), one feasible solution to the centralized problem is for each agent to interdict both these arcs by 1/(2 + ) for a total cost of 1. In this case the length of both arcs become n/(2 + ), giving a shortest path length of n/(2 + ) for each agent. Note that this is not an equilibrium solution as agent 1 can deviate unilaterally to interdict arcs (a 1 , b 1 ) and (a 2 , b 2 ) by 1/2 to obtain a shortest path length of (n + /2)/(2 + ).  A Nash equilibrium to this problem is given by the following solution. Agent f interdicts the vertical arcs (a 1 , b 1 ), . . . , (a f , b f ) by 1/(f (f + 1)) and the arc (a f +1 , b f +1 ) by f /(f + 1). Each agent then has a shortest path length of n/(n + 1). Note that all the s f -t f paths are of equal length for every agent. Therefore diverting any of the budget to any vertical arc will result in unequal path lengths and a shorter shortest path for any agent. Obviously, diverting the budget to interdict any of the horizontal arcs is cost inefficient because of their higher interdiction cost 1 + . Thus no agent has an incentive to deviate from this solution.
We now have a feasible solution to the centralized problem that has an objective value of n/(2 + ) for each agent, and a Nash equilibrium that has an objective value of n/(n + 1) for each agent. Therefore, the worst-case price of anarchy for the DSPI game depicted in Figure 2 must be at least (n + 1)/(2 + ).
Using the regularized Gauss-Seidel algorithm we also compute lower bounds on the worst-case price of anarchy and average efficiency losses for the same network topology with varying number of agents. The instances we consider are obtained by varying uniformly in the range of (1.5, 10). For purposes of comparison, the numerical results are plotted in Figure 3 below. Note that the average-case efficiency loss is much lower than the worst-case price of anarchy. For the particular graph structure under consideration, we observe that the average efficiency loss grows at a much lower rate than the worst-case efficiency loss. However this observation cannot be generalized to other graph structures and such patterns may only be discernible by applying the computational framework we presented.
Example 5. We further tested the decentralized algorithms for continuous interdiction on random graphs to study average efficiency losses of equilibria of DSPI games on networks with different topologies. To generate random graphs, we took the number of vertices and the density of the graph -the number of arcs in the random graph divided by the maximum possible number of arcs -as inputs. The number of agents was chosen randomly from the interval (0, |V |/2); one agent set size was chosen per vertex set size. Source-target pairs were chosen at random for each interdictor. Fixing the vertex set, we populated the arc set by successively generating source-target paths for the players until the desired density was reached. We thus ensured connectivity between the source-target pairs for each player. Costs, initial arc lengths and interdiction budgets were chosen from continuous uniform distributions. Arc interdiction costs were assigned uniformly in the range [1,5]. The budget for each agent was chosen uniformly from the interval [b f /10, b f /2], where b f = a∈A c f a . The initial length of each arc was chosen uniformly from [1,5]. For each combination of vertex set size, agent set size and graph density, we generated 25 random instances by drawing values from the uniform distributions described above for the various network parameters. For each instance, we used 10 different random permutations of the agents to run the decentralized algorithms in an attempt to compute multiple equilibria. The lower bound on the price of anarchy for the game was computed as the worst case efficiency loss over these 25 instances. The average efficiency loss over these instances was also computed. The results are summarized in Table 4. Our experiments indicate that the average efficiency loss and the worst-case price of anarchy tend to grow as the number of vertices and number of agents increases; on the other hand, these measures of efficiency loss sometimes do not appear to be monotonically increasing or decreasing in the density of the underlying network.

Conclusions and Future Work
In this work, we introduced decentralized network interdiction (DNI) games and gave formulations for one such class of games -decentralized shortest path interdiction (DSPI) games. We analyzed the theoretical properties of DSPI games: in particular, we gave conditions for the existence of equilibria and examples where multiple equilibria exist. We also showed that DSPI games belong to a special class of games called potential games. This property was key in establishing several of the theoretical results we presented. We showed that the DSPI game under continuous interdiction is equivalent to a linear complementarity problem, which can be solved by the Lemke's algorithm. This constitutes a convergent centralized method to solve such problems. We also presented decentralized heuristic algorithms to solve DSPI games under both continuous and discrete interdiction. Finally, we used these algorithms to empirically evaluate the worst case and average efficiency loss of DSPI games.
There are other classes of network interdiction games that can be studied using the same framework we have developed, where the agents' obstruction functions are related to the maximum flow or minimum cost flow in the network. Establishing theoretical results and studying the applicability of the decentralized algorithms to other classes of decentralized network interdiction games are natural and interesting extensions of this work.
In our study of DSPI games, we also made the assumption in this paper that the games have complete information; that is, the normal form of the game -the set of agents, agents' feasible action spaces, and their utility functions -is assumed to be common knowledge to all agents. In addition, we made the implicit assumption that all input data are deterministic. However, data uncertainty and lack of observability of other agents' preferences or actions are prevalent in real-world situations. For such settings, we need to extend our work to accommodate games with exogenous uncertainties and incomplete information.
One might also be interested in designing interventions to reduce the loss of efficiency resulting from decentralized control. This leads to the topic of mechanism design. Such a line of work also defines a very important and interesting future research direction.