Submitted to Mathematics of Operations Research

Security Games in Network Flow Problems

arXiv:1601.07216v2 [cs.GT] 30 Jan 2016

Mathieu Dahan
Center for Computational Engineering (CCE)
Massachusetts Institute of Technology (MIT)
Cambridge, MA 02139, mdahan@mit.edu

Saurabh Amin
Department of Civil & Environmental Engineering
Massachusetts Institute of Technology (MIT)
Cambridge, MA 02139, amins@mit.edu

This article considers a two-player strategic game for network routing under link disruptions. Player 1
(defender) routes flow through a network to maximize her value of effective flow while facing transportation
costs. Player 2 (attacker) simultaneously disrupts one or more links to maximize her value of lost flow but
also faces cost of disrupting links. Linear programming duality in zero-sum games and the Max-Flow MinCut Theorem are applied to obtain properties that are satisfied in any Nash equilibrium. A characterization
of the support of the equilibrium strategies is provided using graph-theoretic arguments. Finally, conditions
under which these results extend to budget-constrained environments are also studied. These results extend
the classical minimum cost maximum flow problem and the minimum cut problem to a class of security
games on flow networks.
Key words : network security game, flow network, linear programming duality, budget-constrained game.
MSC2000 subject classification : Primary: 91A05, 91A10, 91A43; secondary: 90C46, 05C21
OR/MS subject classification : Primary: games/group decisions: noncooperative; secondary:
networks/graphs, programming: linear

1. Introduction. This article studies a class of network security games on flow networks in
which simultaneous link disruptions are caused by a strategic adversary. Our setup is motivated by
applications in transportation networks where the operator (defender) is interested in strategically
routing network flows in the face of adversarial disruptions. We introduce a realistic model of an
attacker-defender game played on a network and investigate the physical properties of the game in
equilibrium. We also relate the structure of player strategies to solutions of the classical minimum
cost maximum flow problem and the minimum cut problem.
Specifically, we study a two-player non-cooperative game over a directed network in which Player
1 (defender or operator) chooses a flow to be routed from a source node to a destination node, and
Player 2 (attacker or interdictor) chooses to disrupt one or more edges. In our model, we consider
the value of the effective flow and the transportation cost for the defender, and the value of the
lost flow and the cost of attack for the attacker. Player 1’s payoff linearly increases in the amount
of effective flow that reaches the destination node, but decreases with the cost of transporting the
initial flow chosen by her. Player 2’s payoff linearly increases in the amount of lost flow as a result
of an attack chosen by her, and decreases with the cost of conducting the attack. This two-player
game is not a zero-sum game. The payoff structures are motivated by the previous formulations
in both network interdiction problems (see Wood and Kevin [26], Cormican et al. [10], Bertsimas
et al. [9], Avenhaus and Canty [4], Neumayer et al. [21], Ball et al. [6], Ratliff et al. [22], Wollmer
[25], Sullivan and Cole Smith [23]), and network security games (see Gueye et al. [16], Szeto [24],
Baykal-Grsoy et al. [7]).
1

2

Network interdiction problems have already been widely studied in the literature. Our focus is
to extend these formulations to simultaneous game settings. Related to our approach is the article
by Washburn and Wood [3] in which the authors consider a sequential game, where the operator
(leader) chooses one s − t path and then the interdictor (follower) inspects one arc. In this sequential
game model, the objective is to maximize the probability with which the operator is detected by
the interdictor. In contrast, our simultaneous game formulation captures each player’s strategic
uncertainty about her opponent. We also account for the attacker’s cost of attack as well as the
defender’s cost of transporting flow through the network. Secondly, we allow both players to have
a much larger set of actions. The defender’s feasible flow may contain multiple s − t paths and
loops, and the attacker can simultaneously disrupt several edges.
The work by Avenhaus and Canty [4] presents several models of inspection games. One of them
considers a two-player game between a passenger of a subway system and the local transit authority.
The passenger chooses whether she pays the ticket or not, and simultaneously the transit authority
decides whether to inspect or not. This model was motivated by the practicality that inspecting
all the time the passenger is either too costly or not worthwhile. Actually, this model is analogous
to our game played on a single link (where the transit authority is an interdictor). By adjusting
the parameters, we find that these models are strategically equivalent, and our results applied to
a single link coincide with the aforementioned inspection game. Thus, our model can be viewed
as a generalization of this inspection game to a network setting, where the interdictor chooses the
probability of inspecting specific locations or links on the network.1
Another related line of work in network interdiction games is by Bertsimas et al. [8]. In this
sequential game, the operator first chooses a feasible flow, and then the interdictor disrupts a fixed
number of edges. The interdictor’s goal is to minimize the largest amount of flow that reaches the
destination node. The authors consider two different models of disruption: an arc-based formulation
where the flow can be rerouted after an attack, and a path-based formulation where the flow carried
by a disrupted edge is lost (or cannot be rerouted). Our formulation is related to the path-based
formulation. Since we model a simultaneous game, it is reasonable to assume that the flow through
disrupted edges is lost and cannot be re-routed. Although, in Bertsimas et al. [8], the interdictor
can disrupt several edges at the same time, she must always disrupt the same number of edges for
every action. In our work, we do not assume this restriction on the set of actions for the interdictor.
Our model is also related to the work of Hong and Wooders [17] and Gueye et al. [16] (also see
[19]). In these papers, the authors model simultaneous attacker-defender games, where the defender
(operator) chooses a feasible flow and the attacker (interdictor) disrupts edges of the network,
preventing the flow from reaching the destination node. The major differences with Gueye et al.
[16] is that their attacker can only disrupt one edge, and they consider an uncapacitated graph
with given supplies and demands, while we consider a capacitated graph with no constraint on the
supplies and demands.
We note that Goyal and Vigier [15], and Acemoglu et al. [1] also studied network security from
a game-theoretic perspective. Indeed, in their models, the attacker targets the nodes of a network
previously chosen by the defender. The defender chooses the network and the allocation of defense
resources and the attacker subsequently targets the nodes. The defender’s objective is to minimize
the impact of the attack, including network cascades. Since our model assumes that the flow that
was supposed to take an edge that is disrupted by an attack is simply lost, it does not consider
contagion or dynamic failure propagation through the network. Still, our results illustrate how
physical properties such as the expected transportation cost and the expected value of effective
flow vary with the attacker’s valuation of lost flow or cost of attack.
1

However, our set-up does not directly apply to the broader class of inspection games considered by Avenhaus, Von
Stengel and Zamir [5], as these games account for strategic manipulation of data by an inspectee who wants to evade
detection by a resource constrained inspector.

3

For the sake of simplicity, we restrict the class of networks we study in this article (even though
our ideas apply to a much larger class of networks). This enables us to develop a rather complete
characterization of the equilibria of our game. Our first result is that, given the characteristics
such as transportation cost and cost of attack, one can tractably compute a Nash equilibrium
that is based on minimum cost maximum flows for Player 1 and on minimum cut sets for Player
2. This result is along the lines of previous results by Avenhaus and Canty [4] and of Hong and
Wooders [17]. This solution illustrates the key factors that affect the operator’s equilibrium routing
strategies in the face of adversarial link disruptions.
We also present theoretical properties satisfied by all the mixed Nash equilibria of our game. A
most interesting property is that each player has a unique payoff value in all equilibria. We derive
analytical expressions of the values of effective and lost flow, and the costs of transportation and
attack, in terms of the parameters of the game. These characteristics, common for all equilibria,
are derived using a combination of game-theoretic and network optimization ideas, one of them
being the Max-Flow Min-Cut Theorem2, and do not need full enumeration of the equilibria.
We show that graph-theoretic properties of the network can be used to restrict the support
of the strategies that can potentially be Nash equilibria. Recall that computing Nash equilibria
of a bimatrix problem is hard. While Daskalakis et al. [11] showed that the computation of a
Nash equilibrium is PPAD-complete for a general two-player game, Von Neumann [20] showed
that, for a zero-sum two-player game, finding Nash equilibria is equivalent to solving a linear
programming problem. Our game is strategically equivalent to a zero-sum game, thus we can use
linear programming techniques to compute a Nash equilibrium efficiently. Furthermore, we give
an alternative to computing a Nash equilibrium based on a minimum cost maximum flow for the
defender and on a minimum cut set for the attacker. Thus, this equilibrium can be computed
efficiently by viewing the minimum cost maximum flow problem as a minimum cost circulation
problem (see Goldberg and Tarjan [14]). This shows how we can use and extend classical network
routing problems to adversarial environments.
Lastly, we study a generalization of the game where both players face budget constraints. Specifically, we view the transportation cost of a flow (resp. cost of an attack) as a resource that needs to
be available to the defender (resp. attacker) to send that flow (resp. lead that attack). We compute
the minimum budget that players must have to ensure that the equilibrium properties derived for
the previous game still hold for the new game defined on action sets with budget constraints. Using
the infiniteness of the defender’s set of actions, we give a tight lower bound for the defender’s budget for transporting flows. However, the attacker’s set of actions is discrete and we cannot derive
an analogous lower bound for the budget needed by the attacker to disrupt edges. We focus our
attention to mixed equilibrium strategies supported over partitions of the minimum cut sets. Then
we find the equilibrium strategies in this subset that require the lowest cost of attack. It turns out
that we can formulate this problem as an integer programming problem whose optimal solution
gives a bound (maybe not the best one) on the attacker’s budget for which our analysis holds.
The rest of the paper is organized as follows: In Section 2 we discuss the main assumptions
and present our game model. Section 3 presents our main results on the characterization of Nash
equilibria of the game and their relations with classical routing problems. Then in Section 4 we
extend our results to a budget-constrained game. Lastly, the implications of relaxing some of the
modeling assumptions are considered in Section 5, along with a brief discussion on how to extend
our results in these settings.
2. Problem formulation.
2

It is not the first time that such classical network optimization ideas are utilized in a game-theoretic context. Indeed,
Kalai and Zemel [18] used the Max-Flow Min-Cut Theorem to show that the class of totally balanced games is
isomorphic to a particular class of games called flow games.

4

2.1. Preliminaries. Consider a capacitated directed graph G = (V , E ) where V (resp. E ) represents the set of nodes (resp. the set of edges) of G . For each edge (i, j) ∈ E , let cij ∈ R+ denote its
capacity. Let s ∈ V denote the source node and t ∈ V the destination node. A flow, defined by the
function x : E → R+ , can only enter the network from s and leave from t. There is no demand or
supply at other nodes. A flow x is said to be feasible if it satisfies flow conservation at each node
and if the flow through each edge does not exceed its capacity:
X
X
∀i ∈ V\{s, t},
x(j, i) =
x(i, j)
(j,i)∈E

(i,j)∈E

∀(i, j) ∈ E , 0 ≤ x(i, j) ≤ cij .

Let F denote the set of feasible flows, and Λ the set containing all the loops and source-destination
s − t paths of the network. Let xij := x(i, j) denote the flow through the edge (i, j), and xλ the
quantity of flow of x sent through λ ∈ Λ. The edge flows xij and loop/path flows xλ satisfy:
X
∀(i, j) ∈ E , xij =
xλ .
(1)
{λ∈Λ | (i,j)∈λ}

An s − t cut is a partition {S , T } of V , such that s ∈ S and t ∈ T . The cut-set
P of {S , T } and
its capacity P
are defined as E({S , T }) = {(i, j) ∈ E | i ∈ S , j ∈ T } and C({S , T }) = (i,j)∈E({S,T }) cij .
Let F (x) = {i∈V | (i,t)∈E} xit denote the amount of flow passing from the source s to the sink t. We
recall the maximum flow problem:
(P1 ) maximize F (x)
subject to x ∈ F .
The well-known Max-Flow Min-Cut Theorem by Ford and Fulkerson [13] states that the optimal
value of the maximum flow problem is equal to the minimum capacity over all s − t cuts. We call
min-cut set a cut-set with minimum capacity. We also state the minimum cost maximum flow
problem by Edmonds and Karp [12]:
X
(P2 ) minimize
bij xij
(i,j)∈E

subject to x ∈ F

F (x) ≥ F (x′ ) , ∀x′ ∈ F ,
where for every edge (i, j) ∈ E , bij ∈ R+ denotes the cost of transporting a unit flow through (i, j).
We use Fmax (resp. Ωmax ) to denote the optimal value (resp. optimal solution set) of the max-flow
problem (P1 ). Similarly, we denote the optimal value (resp. the set of optimal solutions) of problem
(P2 ) by Tmin (resp. Ω∗ ). Note that Ω∗ ⊆ Ωmax (i.e., any min-cost max-flow is a max-flow).
2.2. Model. We define a simultaneous, semi-infinite, two-player strategic game Γ :=
h{1, 2}, (F , A), (u1 , u2 )i. Player 1 (P1) is the defender (operator) who chooses to route a flow x ∈ F
through the network, and player 2 (P2) is the attacker (interdictor) who chooses an attack µ to
disrupt a subset of edges of G . The action set for P1 (resp. P2) is given by F (resp. A := {0, 1}E ).
An attack µ is a function from E to {0, 1} defined as follows:

1 if (i, j) is disrupted,
µij := µ(i, j) =
0 otherwise.
Note that P2’s choice of an attack µ can lead to the disruption of multiple edges of the network.

5

We use the following notation to describe certain specific player actions: x0 the action of not
sending flow in the network, x∗ ∈ Ω∗ an optimal solution of (P2 ) i.e., a min-cost max-flow, µ0 the
action of not attacking any edge of the network, and µmin the action that disrupts all the edges of
a min-cut set of the network.
Since Γ is a simultaneous game, we assume that after an edge is disrupted, the flow that was
supposed to cross this edge (if there were no attack) is lost and it is not re-routed. For the sake of
simplicity, we do not consider attacks that can only result in partially disrupted edges and might
still permit some flow to pass through the attacked edges. Thus, the effective flow, denoted xµ ,
when a flow x is chosen by P1 and an attack µ is chosen by P2 can be expressed as follows:
X
∀(i, j) ∈ E , xµij =
xλ ,
µ

λ∈Λij

where Λµij := {λ ∈ Λ | (i, j) ∈ λ and ∀(i′ , j ′ ) ∈ λ, µi′ j′ = 0}. That is, the effective flow through an edge
(i, j) is the sum of all the initial path flows through edge (i, j) that do not contain any attacked
edge. The effective flow xµ can be viewed as a feasible flow in F that succesfully carries the amount
of flow from x that is not lost due to the attack µ.
In this model, the payoff of P1 is defined as the value of effective flow assessed by P1 net the
cost of transporting the initial flow:
u1 (x, µ) =

p1 F (xµ )
| {z }

−

value of effective flow

(2)

T (x)
| {z }

transportation cost

P
where p1 ∈ R+ is the marginal value of the flow for P1, and T (x) := (i,j)∈E bij xij is the cost
of transporting the initial flow x. Thus, when one additional unit of flow reaches t, P1’s payoff
increases by p1 and at the same time decreases by its transportation cost.
Similarly, the payoff of P2 is defined as the value of lost flow assessed by P2 net the cost of
executing the attack:
u2 (x, µ) = p2 F (x − xµ ) −
|
{z
}
value of lost flow

C (µ)
| {z }

(3)

cost of attack

where
p2 ∈ R+ is the marginal value of the lost flow for P2 (in general, p1 6= p2 ), and C (µ) :=
P
(i,j)∈E cij µij is the cost of the attack µ. Thus, if the disruption of an edge induces the loss of one
unit of flow, the payoff of P2 increases by p2 , and at the same time decreases by the cost of attack.
In this model, we suppose that the cost of attacking an edge is proportional to its capacity. Note
that after rescaling P2’s payoff, without loss of generality, the cost of attacking an edge becomes
equal to its capacity. Also, notice that F and T are linear forms on F , and C is a linear form on
A. However, by definition, F and A are not vector spaces.
We allow each player to randomize over her set of pure actions. Let ∆(F ) and ∆(A) denote the
mixed extensions of P1’s and P2’s pure strategies, respectively, i.e.:
)
)
(
(
X
X
2
1
2
A
1
F
σ (µ) = 1 .
σ (x) = 1 ,
∆(A) = σ ∈ [0, 1]
∆(F ) = σ ∈ [0, 1]
x∈F

µ∈A

For notational simplicity, we define σx1 := σ 1 (x) and σµ2 := σ 2 (µ). Given any function ϕ : F ×
A −→ R P
and a mixed strategy profile σ = (σ 1 , σ 2 ) ∈ ∆(F ) × ∆(A), we denote Eσ [ϕ(x, µ)] :=
P
1
2
x∈F σx
µ∈A σµ ϕ(x, µ) the expectation of ϕ with respect to σ.

6

Given a strategy profile σ = (σ 1 , σ 2 ) ∈ ∆(F ) × ∆(A), the respective player expected payoffs can
be expressed as:
U1 (σ 1 , σ 2 ) = p1 Eσ [F (xµ )] − Eσ [T (x)]
U2 (σ 1 , σ 2 ) = p2 (Eσ [F (x)] − Eσ [F (xµ )]) − Eσ [C (µ)] .

(4)
(5)

We will use the notation Ui (x, σ 2 ) = Ui (1{x} , σ 2 ) and Ui (σ 1 , µ) = Ui (σ 1 , 1{µ} ) for i ∈ {1, 2}. Thus,
the mixed extension of the game Γ is h{1, 2}, (∆(F ), ∆(A)), (U1, U2 )i.
Let us illustrate this model through an example.
Example 1. Consider the network shown in Fig. 1a. The edge labels give the capacities and
transportation costs. Both players play one shot of the game according to Fig. 1b.

2,1

1

s

1,1
1,1

xs1 = 2
µs1 = 0

1,1
t
2,1

2
(a) Example network

x1t = 1
µ1 t = 1

1
x12 = 1
µ12 = 0

s
xs2 = 1
µs2 = 1

xµ1t = 0
xµ12 = 1

s

t

xµs2 = 0

x2t = 2
µ2 t = 0

2

1

xµs1 = 1

2

t
xµ2t = 1

(c) Resulting effective flow

(b) Initial flow and attack

Figure 1. The labels of each edge in Fig. 1a correspond to its capacity (red) and its transportation cost (green).

In this example, P1 sends one unit of flow through each of the paths {s, 1, t}, {s, 1, 2, t} and
{s, 2, t}, and P2 disrupts edges (1, t) and (s, 2). Therefore, the flows through paths {s, 1, t} and
{s, 2, t} are lost and the effective flow, shown in Fig. 1c, consists of the unit flow through the path
{s, 1, 2, t}, i.e., F (xµ ) = 1. Since that each edge (i, j) has a transportation cost bij = 1, the cost of
transporting the initial flow x is T (x) = 7. Thus, P1’s payoff is u1 (x, µ) = p1 − 7.
The amount of lost flow F (x − xµ ) that results from the attack µ is equal to 2. Since P2 disrupted
2 edges of capacity 1 each, the cost of attack C (µ) = 2. Thus, P2’s payoff is u2 (x, µ) = 2p2 − 2.
2.3. Standard definitions and main assumption. We recall the following standard definitions:
The support of σ 1 ∈ ∆(F ) (resp. σ 2 ∈ ∆(A)) is supp(σ 1 ) = {x ∈ F | σx1 > 0} (resp. supp(σ 2 ) =
{µ ∈ A | σµ2 > 0}).
∗
∗
A mixed strategy profile (σ 1 , σ 2 ) ∈ ∆(F ) × ∆(A) is a Nash Equilibrium (NE) if and only if:
∗

∗

∗

∀σ 1 ∈ ∆(F ), U1 (σ 1 , σ 2 ) ≥ U1 (σ 1 , σ 2 ),
∗
∗
∗
∀σ 2 ∈ ∆(A), U2 (σ 1 , σ 2 ) ≥ U2 (σ 1 , σ 2 ).

(6)
(7)
∗

∗

∗

∗

We denote Σ the set of NE of the game Γ. Equivalently, at a NE (σ 1 , σ 2 ), σ 1 (resp. σ 2 ) is a
∗
∗
Best Response (BR) to σ 2 (resp. σ 1 ).
A two-player game is a strictly competitive game (SCG) if, when both players change their mixed
strategies, either the expected payoffs remain the same or one of the expected payoffs strictly
increases and the other strictly decreases. In particular, a zero-sum game (i.e., u1 = −u2 ) is an
SCG. Adler et al. [2] define SCG using the notion of affine variance: u1 is an affine variant of −u2
if and only if ∃ (λ, β) ∈ R∗+ × R | ∀(x, µ) ∈ F × A, u1 (x, µ) = −λu2 (x, µ) + β. The game Γ is an SCG
if and only if u1 is an affine variant of −u2 .

7

e = h{1, 2}, (F , A), (e
Consider two games Γ = h{1, 2}, (F , A), (u1 , u2 )i, Γ
u1 , u
e2 )i with:
u
e1 (x, µ) = a1 u1 (x, µ) + g(µ)
u
e2 (x, µ) = a2 u2 (x, µ) + h(x)

e are strategically equivalent (i.e.,
where (a1 , a2 ) ∈ (R∗+ )2 , g : A → R and h : F → R. Then, Γ and Γ
they have the same set of equilibria).
Our objective in this article is to develop a complete characterization of the equilibria of the
game Γ and to relate them to the solutions of classical routing problems. To facilitate this, we
restrict our attention to the class of networks that satisfy the following assumption:
P
Assumption 1. Let α := minλ∈Λpath (i,j)∈λ bij . There exists an optimal solution of (P2 ), x∗ ∈
Ω∗ , that takes s − t paths with marginal transportation cost equal to α, i.e.,
X
∃ x∗ ∈ Ω∗ s.t. ∀λ ∈ Λpath : xλ > 0 =⇒
bij = α,
(i,j)∈λ

where Λpath is the set containing all the s − t paths of the network.
This assumption, noted (A1), implies that if x∗ ∈ Ω∗ denotes a min-cost max-flow, the cost of
transporting a unit flow through each s − t path taken by x∗ is identically equal to α. By definition
of α, every other path in the network cannot have a smaller marginal transportation cost. Notice
that if such an x∗ exists, then (A1) will be satisfied for any optimal solution of (P2 ). The case when
every s − t has an identical marginal transportation cost is a special case of this assumption. In
Section 5.1, we will discuss the implications of relaxing (A1). We illustrate (A1) with an example.
Example 2. Consider the network flow problem in Fig. 2. There is a unique min-cost maxflow x∗ , which carries 1 unit of flow through paths {s, 2, 4, t}, {s, 2, 3, t} and {s, 1, t}. Thus, the
total amount of flow is equal to 3 units. In this network, α = 3, and each path taken by x∗ has
a marginal transportation cost equal to 3. Thus, the cost of transporting x∗ is equal to 9. The
remaining paths that are not taken by x∗ are {s, 4, t} with a transportation cost 4, and {s, 1, 3, t}
with a transportation cost 3. Thus, (A1) is satisfied.
4
0,1,3
s

2,2,1

2

1,1,1
1,1,1

1,1,1
3

1,1,1

t

0,1,1
1,1,1

1,1,2
1

Figure 2. Min-cost max-flow (drawn in bold blue) in a network satisfying (A1). The labels of each edge correspond
to the flow it carries (blue), its capacity (red) and its transportation cost (green).

Remark 1. (A1) implies that for all x ∈ F , T (x) ≥ α F (x) and Tmin = α Fmax . To show this,
we note bλ the cost of transporting one unit of flow through path λ ∈ Λpath , then:
∀x ∈ F , T (x) =

X
λ∈Λ

bλ xλ ≥

X

λ∈Λpath

X
(A1)
xλ = α F (x) ,
bλ xλ ≥ α
λ∈Λpath

(8)

8

and
Tmin = T (x∗ ) =

X

λ∈Λpath

X
(A1)
bλ x∗λ = α
x∗λ = α F (x∗ ) = α Fmax ,

(9)

λ∈Λpath

where we used the fact that any min-cost max-flow does not send flow in any loop.
Note that our setup can be easily extended to networks with multiple sources and multiple
destination nodes, but still satisfying (A1). For such a network, one needs to add an extra source
(resp. destination) node and connect it to every existing source (resp. destination) node with an
uncapacitated edge of cost of transportation equal to zero. This modification gives a new network
with single source and single destination. The outcome of the game defined for the original network
remains the same as that of the game defined for the new network.
Next, we focus on the NE of the game Γ, and utilize the properties of NE to relate the support
of equilibrium strategies of P1 (resp. P2) with the solutions of (P2 ) (resp. min-cut sets).
3. Properties of Nash equilibria. In this section, we present theoretical and practical
properties satisfied by the NE of the game Γ. First, we give one NE of Γ that is based on min-cost
max-flows for P1 and on min-cut sets for P2. Next, we focus on the parameter range of interest
p1 > α, p2 > 1, and derive analytical expressions of certain physical quantities of interest at any NE.
This involves a combination of game-theoretic arguments and network optimization results. Finally,
we show how we can restrict the support of the strategies that can be NE using graph-theoretic
properties of the network.
3.1. Preliminary results. The following lemma states that although Γ is not a zero-sum
game, it is strategically equivalent to a zero-sum game.
e := h{1, 2}, (F , A), (e
Lemma 1. Γ is strategically equivalent to Γ
u1 , −u
e1 )i where:
∀(x, µ) ∈ F × A, u
e1 (x, µ) = F (xµ ) −

1
1
T (x) + C (µ) .
p1
p2

(10)

Therefore, the NE of Γ can be obtained by solving the following two linear programming problems:
(LP1 ) maximize

e1 (σ 1 , µ) ≥ z, ∀µ ∈ A
subject to U

e2 (x, σ 2 ) ≥ z ′ , ∀x ∈ F
subject to U

σ 1 ∈ ∆(F )

∗

∗

†

†

z′

(LP2 ) maximize

z

σ 2 ∈ ∆(A)

∗

†

†

∗

If (σ 1 , σ 2 ) ∈ Σ and (σ 1 , σ 2 ) ∈ Σ, then (σ 1 , σ 2 ) ∈ Σ and (σ 1 , σ 2 ) ∈ Σ (interchangeability).
Furthermore, Σ is a convex set.
Proof in Appendix A.1.
The following lemma states that P1’s all strategies containing loops are strictly dominated.
Lemma 2.

Any flow containing loops is not a BR for P1.

Proof in Appendix A.1.
The intuition behind this result is that if P1 sends flow in a loop, then she will pay an extra
cost without increasing the amount of flow that can reach the terminal node. Therefore, P1 has
no incentive to send flow in any loop. Thus, Λ in (1) can be restricted to the set of s − t paths, and
F can be restricted to the set of feasible flows that do not take any loop.
Props. 1–3 below provide that, for given p1 , p2 and α (given and fixed under (A1)), the game Γ
admits qualitatively different equilibria in regions 0 < p1 < α and p2 > 0 (Region I), p1 > α and 0 <
p2 < 1 (Region II), and p1 > α and p2 > 1 (Region III). The proofs are provided in Appendix A.1.
These regions are illustrated in Fig. 3.
The following result states that no flow and no attack is the unique NE of Γ in Region I:

9

p2
I

supp(σ̃ 1 ) = {x0 , x∗ }
supp(σ̃ 2 ) = {µ0 , µmin }

∗

supp(σ 1 ) = {x0 }
1

III

∗

supp(σ 2 ) = {µ0 }

∗

supp(σ 1 ) = {x∗ }

II

∗

supp(σ 2 ) = {µ0 }
0

α

p1

Figure 3. Support of equilibrium strategies in Regions I-III.

Proposition 1 (Region I). If p1 < α, then Σ = {(x0 , µ0 )}, with u1 (x0 , µ0 ) = 0 and
u2 (x0 , µ0 ) = 0.
Intuitively, when 0 < p1 < α, the marginal value of effective flow that reaches the destination
node t is less than the marginal transportation cost for every s − t path. Therefore, P1 will face
negative utility if she sends flow through the network. Thus, in this case, her BR is not to route
any flow. Since no flow is sent by P1, P2’s BR is not to attack, otherwise she will face the cost of
attack without gaining any value from lost flow.
Next, for Region II, we obtain that min-cost max-flow and no attack is a pure NE.
Proposition 2 (Region II). If p1 > α and p2 < 1, then ∀x∗ ∈ Ω∗ , {x∗ , µ0 } ∈ Σ. The equilibrium payoffs are u1 (x∗ , µ0 ) = (p1 − α) Fmax and u2 (x∗ , µ0 ) = 0.
This result can be explained as follows: on one hand, since P2’s valuation of lost flow is small
(p2 < 1), for any attack, the utility gained from the lost flow is always lower than the cost of attack.
Therefore, P2’s BR is not to attack any edge. On the other hand, P1’s valuation of effective
flow reaching t is higher than the disutility it faces in transportation costs (p1 > α). Since P2
does not disrupt any edge, every flow sent through the network reaches t; thus, P1’s BR is to
send a maximum flow. Among the different maximum flows, a min-cost max-flow maximizes P1’s
equilibrium payoff. Note that if p1 = α and p2 < 1, then both (x0 , µ0 ) and (x∗ , µ0 ) are NE. The
equilibrium payoffs are still (0, 0).
The following Proposition 3 shows that in Region III, Γ admits a NE whose support is based
on a min-cost max-flow for P1, and on a min-cut set for P2.
Proposition 3 (Region III). If p1 > α and p2 > 1, then Γ has no pure NE. Furthermore,
∃ σ̃ = (σ̃ 1 , σ̃ 2 ) ∈ Σ such that U1 (σ̃ 1 , σ̃ 2 ) = U2 (σ̃ 1 , σ̃ 2 ) = 0, and supp(σ̃ 1 ) = {x0 , x∗ } and supp(σ̃ 2 ) =
{µ0 , µmin }. The corresponding probabilities are given by:
1
1
σ̃x10 = 1 − , σ̃x1∗ = ,
p
p2
α 2 2
α
2
σ̃µ0 = , σ̃µmin = 1 − .
p1
p1

(11)
(12)

We can now make a few useful observations. First, in contrast to Props. 1 and 2, in Region III,
both players necessarily randomize their actions in any equilibrium. Indeed, if P1’s pure strategy is
to route some flow x in the network, then P2’s BR is to disrupt some edges taken by x in order to
induce the maximum loss. Then P1 has an incentive to change her strategy and route another flow
that takes other paths not disrupted by P2. Therefore, for every pure action profile, at least one of
the players has an incentive to deviate, preventing them from reaching a pure strategy equilibrium.

10

Second, the mixed equilibrium (σ̃ 1 , σ̃ 2 ), as defined in (11) and (12), can be obtained from a
solution x∗ of problem (P2 ) and a min-cut set of the graph G . Note that (σ̃ 1 , σ̃ 2 ) has a simple
structure: P1 either sends a min-cost max-flow, or does not send any flow in the network. Similarly,
P2 either disrupts all the edges of a min-cut set, or does not attack any edge of the network.
Finally, Prop. 3 provides a game-theoretic intuition: P1’s equilibrium strategy σ̃ 1 is characterized
by p2 , and similarly, P2’s equilibrium strategy σ̃ 2 is characterized by p1 and α. This can be
explained as follows: as p2 increases, σ̃x1∗ decreases while σ̃x10 increases. When P2’s valuation of lost
flow is large, she has more incentive to attack, so any flow sent by P1 will be more likely to be
lost. Thus, P1 chooses not to send any flow with higher probability than sending x∗ . Likewise, as
p1 increases, σ̃µ2 min increases while σ̃µ2 0 decreases. Again, when the marginal valuation of effective
flow is large, P1 will prefer to send as much flow as she can. Thus, P2 will be more likely to attack
a min-cut set.
The following example applies the results of Props. 1-3:
Example 3. Consider the network in Fig. 4. We can see that α = 3, and that the mincost max-flow sends 1 unit of flow through {s, 1, 3, t}, {s, 2, 3, t} and {s, 2, 4, t}, and only takes
paths with transportation cost equal to 3. Thus, (A1) is satisfied. The min-cut set is given by
{(1, 3), (2, 3), (2, 4)}. The NE described in Props. 1-3 are illustrated in Fig. 5.

1

2,1
s

1,1

1,1
3,1

1,1

2

3

3,1

1,1

t
4

1,1

2,1

Figure 4. Example network. Edge capacities and transportation costs are labeled in red and green colors respectively.

Thanks to Props. 1-3, each player has a strategy that achieves a stable outcome for any p1 and
p2 , and any network satisfying (A1). However, P1 may be interested in an equilibrium strategy
that maximizes the expected amount of effective flow that successfully crosses the network after
attack. Similarly, P2 may be interested in an equilibrium strategy that maximizes the expected
amount of lost flow. Moreover, players may be subject to certain budget constraints. To answer
these questions, we need to further analyze the set of NE. Regions I and II do not require further
study; however, Region III hosts many useful properties which we present next.
3.2. Main theorem.
Theorem 1. If p1 > α, p2 > 1, and under (A1), then for any σ ∗ ∈ Σ:
(i) Both players’ equilibrium payoffs are equal to 0, i.e.:
∗

∗

U1 (σ 1 , σ 2 ) ≡ 0
∗
∗
U2 (σ 1 , σ 2 ) ≡ 0

(13)
(14)

(ii) The expected amount of flow sent in the network is given by:
Eσ∗ [F (x)] ≡

1 max
F
p2

(15)

1 min
T
p2

(16)

and the expected transportation cost is given by:
Eσ∗ [T (x)] ≡

11

I

s

s

1

0,1,1
0,1,1

0,1,1

3
0,1,1

0,1,1

0,1,1

1,1,1

2

2,3,1

σ̃µ2min = 1 −

3
p1

4

t
1,2,1

t

0,3,1
2

1
σ̃x∗ =
p2
1

3

1,1,1

0,1,1
2,3,1

0,3,1

1,1,1

1

1,2,1

0 < p1 < α
0 < p2

0,2,1

III

α < p1
1 < p2

4

0,2,1

II

α < p1
0 < p2 < 1
1,2,1
s

1,1,1

1

1,1,1

0,1,1
2,3,1

2

1,1,1

3

2,3,1

0,1,1

t
4

1,2,1

Figure 5. NE described in Props. 1, 2 and 3. The min-cost max-flow (resp. min-cut set attack) is in bold blue (resp.
dotted red).

(iii) The expected cost of attack is given by:
Eσ∗ [C (µ)] ≡ Fmax −

1 min
T
p1

(17)

(iv) The expected amount of effective flow (that reaches t) is given by:
Eσ∗ [F (xµ )] ≡

1
Tmin .
p1 p2

(18)

Proof in Appendix A.2.
From Thm. 1 we observe that, in any equilibrium for Region III, the expected amount of initial
and effective flow and expected transportation cost to P1, and the expected cost of attack to P2,
can be computed in closed form using the parameters p1 , p2 , Fmax , and Tmin . It is easy to check
that Thm. 1 is satisfied by (σ̃ 1 , σ̃ 2 ) defined in (11) and (12).
Interestingly, the payoffs of both players are zero for any NE (ref. (13) and (14)). Note that in
general, a game that is strategically equivalent to a zero-sum game can have different NE that lead
to different payoffs. Thus, (i) in Thm. 1 cannot be entirely derived from the equivalent zero-sum
e and requires the application of other results such as the Max-Flow Min-Cut Theorem (see
game Γ
the proof of Thm. 1). Now we further explain (ii)-(iv) in Thm. 1.
Following (15) (resp. (16)), the expected amount of initial flow (resp. the expected cost of transportation) at equilibrium is equal to some fraction of the value (resp. transporting cost) of the
min-cost max-flows, and these expectations decrease with p2 .
Following (17), the expected cost of attack at any NE is a constant. In fact, under (A1), we
know that Tmin = α Fmax (see (9)). Therefore, the expected cost of attack at equilibrium becomes
(1 − pα1 ) Fmax . Applying the Max-Flow Min-Cut Theorem, we obtain that the expected cost of

12

attack is equal to some fraction of the cost of attacking a min-cut set, and this fraction increases
with p1 .
Following (18), the expected amount of effective flow is again a constant at equilibrium. Under
(A1), this quantity becomes p1αp2 Fmax . Although the amount of effective flow depends on both
players’ strategies, in any NE, its expectation is always equal to some fraction of the amount of
max-flow. Since p1αp2 < p12 , this flow is always smaller than the expected amount of initial flow.
Interestingly, the expected amount of effective flow decreases when p1 and/or p2 increase. This
result can be explained by noting that when p1 increases, the disruption caused by P2 increases,
so there is more lost flow and the expected effective flow decreases.
Thm. 1 also enables estimation of the expected amount of lost flow and the yield of P1 in any
NE. We define yield as the ratio of the expected amount of effective flow and the expected amount
of initial flow in the network. We have the following corollary:
Corollary 1.

For any σ ∗ ∈ Σ, the expected amount of lost flow is given by:




1 min (9) 1
α
1
max
µ
=
F
− T
1−
Fmax ,
Eσ∗ [F (x − x )] ≡
p2
p1
p2
p1

(19)

and the yield is given by:
Tmin (9) α
Eσ∗ [F (xµ )]
≡
= .
Eσ∗ [F (x)]
p1 Fmax
p1

(20)

From (19), in any equilibrium, the expected amount of lost flow is equal to some fraction of the
amount of max-flow. The corresponding coefficient increases with p1 , because when p1 is large, P1
sends more flow and P2 disrupts more edges. However, the coefficient decreases when p2 increases,
because when p2 is large, P2 causes more disruption and P1 sends less flow in the network. Finally,
from (20), in any equilibrium, the yield decreases in the ratio pα1 , but it does not depend on p2 or
the maximum amount of flow Fmax . When pα1 is large, P1 has more incentive to send flow in the
network and P2 will attack more frequently, resulting in a lower yield of the network.
Thus, Thm. 1 provides many properties that are satisfied by any NE in Region III. Next, we
study the support of NE and relate it to the optimal solutions of (P2 ) and the min-cut sets.
3.3. Necessary conditions. Recall the NE in Prop. 3 which has a support based on a mincost max-flow (for P1) and on a min-cut set (for P2). We now investigate the generality of this
result to other NE. This leads to additional properties satisfied by all NE, and in many cases also
eases the computation of NE.
First, let us present a result regarding the paths taken by the flows in the support of P1’s
strategy at equilibrium.
Lemma 3. Under (A1), every flow in the support of a NE only takes paths whose marginal
transportation cost is α.
X
∗
∗
∗
∀(σ 1 , σ 2 ) ∈ Σ, ∀x ∈ supp(σ 1 ), ∀λ ∈ Λ, xλ > 0 =⇒
bij = α.
(i,j)∈λ

Proof in Appendix A.3.
In other words, the paths that induce a transportation cost strictly greater than α are not chosen
in equilibrium. Notice that this lemma implies that any max-flow that is not a min-cost max-flow
is not in the support of any NE. This lemma is useful for constructing P1’s equilibrium strategies
when the network has only a small number of paths of marginal transportation cost α. In the case
when the only paths of marginal transportation cost equal to α are the ones taken by a unique

13

min-cost max-flow x∗ , we can deduce that all the equilibrium strategies of P1 can be constructed
from x∗ (or sub-flows of x∗ ). This lemma is of limited use in the construction of P1’s equilibrium
strategies if most of the paths of the network have the same smallest transportation cost.
Secondly, the following result characterizes the support of P2’s equilibrium strategies.
Proposition 4. Every attack in the support of a NE has a cost at most equal to the cost of
attacking a min-cut set, and disrupts edges that are saturated by every min-cost max-flow:

∗
∗
∗
∀(σ 1 , σ 2 ) ∈ Σ, ∀µ ∈ supp(σ 2 ) : C (µ) ≤ C µmin = Fmax
(21)
∀(i, j) ∈ E , µij = 1 =⇒ ∀x∗ ∈ Ω∗ , x∗ij = cij .
Proof in Appendix A.3.
This result tells us that the attacks that require a cost that is strictly greater than the cost of
disrupting a min-cut set are not chosen in any equilibrium. Further, if an edge is not saturated
by at least one min-cost max-flow, then it is not disrupted in equilibrium. Recall that P2’s set of
actions is isomorphic to the power set of E , that has 2|E| elements which can be huge. Therefore,
Prop. 4 drastically restricts the set of actions that can be potentially chosen in equilibrium by P2.
However, since the edges that are part of a min-cut set are saturated by every (min-cost) maxflow, we cannot restrict the set of edges that can be potentially disrupted in equilibrium beyond
the min-cut sets. Nevertheless, one can find NE in which edges that are not part of any min-cut
set are disrupted with positive probability. The following example illustrates this point.
Example 4. Consider the network in Fig. 6. We can see that α = 3, and the min-cost max1
1,1

1,2
1,2

s

2,1

2
1,1

2,1

t

1,2
3

Figure 6. Example network in which edges outside a min-cut set are disrupted in equilibrium.

flow x∗ sends 1 unit of flow through {s, 2, t}, {s, 3, 2, t} and {s, 3, t}, and only takes paths with
transportation cost equal to 3. Thus, (A1) is satisfied. In this network, there is a unique min-cut
set given by {(2, t), (3, t)}. Let µ′ = 1{(s,2),(s,3)} the attack that disrupts edges (s, 2) and (s, 3). In
∗
the case when 3 < p1 < 4 and p2 > 1, one can see that there exists a NE (σ̃ 1 , σ 2 ) where σ̃ 1 is defined
∗
∗
∗
in (11), and σ 2 is defined by σµ2 0 = pα1 and σµ2 ′ = 1 − pα1 . However, (s, 2) and (s, 3) are not part of
the min-cut set.
Finally, since there are equilibrium strategies that disrupt at least one min-cut set (see e.g. Prop.
3), it is useful to estimate the amount of lost flow for each edge that is attacked in a min-cut set.
Similarly, the probability with which each edge of a min-cut set will be disrupted is also of interest
because it can be interpreted as the probability with which the flow routed by P1 is lost when
P2’s equilibrium strategy only involves edges belonging to a min-cut set. The following proposition
answers these questions.
Proposition 5.

Consider a min-cut set E({S , T }), then:
∗

∗

∀(σ 1 , σ 2 ) ∈ Σ, ∀(i, j) ∈ E({S , T }), Eσ∗ [xij ] =

cij
.
p2

(22)

14

Furthermore, for any NE σ ∗ ∈ Σ whose support only contains attacks that disrupt edges of
E({S , T }), we have:
∀(i, j) ∈ E({S , T }), Pσ∗ ({(i, j) is disrupted }) = 1 −

α
.
p1

(23)

Proof in Appendix A.3.
From (22), at any NE, the expected amount of flow that goes through any edge of a min-cut
set is equal to a constant fraction of its capacity. And from (23), if P2’s equilibrium strategy only
disrupts edges of one min-cut set, then the probability with which an edge is disrupted is constant
for all the edges of that min-cut set, irrespective of the capacities of these edges. We can deduce
the following corollary that directly follows from Prop. 5:
Corollary 2.
∗

∗

∗

∀(σ 1 , σ 2 ) ∈ Σ, ∀ min-cut set E({S , T }), ∀(i, j) ∈ E({S , T }), ∃ x ∈ supp(σ 1 ) s.t. xij > 0.

That is, for any NE and for any edge of a min-cut set, there exists a flow chosen with non-zero
probability that passes through that edge.
We apply the previous results to the following example.
Example 5. Consider the network in Fig. 4. The only min-cost max-flow is the flow x∗ that
sends 1 unit of flow through {s, 1, 3, t}, {s, 2, 3, t} and {s, 2, 4, t}, and the only min-cut set is
{(1, 2), (2, 3), (2, 4)}; see Fig. 7.
1,1,1
1

1,2,1

3

2,3,1

1,1,1
s

0,1,1
2,3,1

0,1,1

2

4

t
1,2,1

1,1,1
Figure 7. Min-cost max-flow (bold blue) and min-cut set attack (dotted red). The labels in the boxes represent the
edges that are saturated by the min-cost max-flow.

In this example, the s − t paths that induce the smallest transportation cost are the ones taken
by x∗ ; thus (A1) is satisfied. Lemma 3 tells us that the flows sent with positive probability in
equilibrium only take paths taken by x∗ . By combining this fact with Prop. 5, we conclude that
in any equilibrium, the expected amount of flow in each of the paths {s, 1, 3, t}, {s, 2, 3, t} and
{s, 2, 4, t} is p12 .
Besides, the only edges that are saturated by x∗ are edges (1, 3), (2, 3) and (2, 4). From Prop. 4,
we obtain that only these three edges can be disrupted with a nonzero probability in equilibrium.
∗
Hence, any P2’s equilibrium strategy σ 2 is supported over at most 23 = 8 pure actions instead
of 29 = 512 initial pure actions. These edges are exactly the min-cut set of the network in Fig. 7.
Therefore, from Prop. 5, each of these edges is disrupted with probability 1 − p31 .
In this example, we showed that the necessary conditions derived above help us restrict the pure
actions that support equilibrium strategies to a significant extent. These properties also enable us
to derive the following upper bounds on the probabilities with which actions in the support of σ̃
defined in Prop. 3 are chosen at any equilibrium.

15
∗

∗

Consider (σ 1 , σ 2 ) ∈ Σ. Then we have the following bounds:
1
∗
∗
(i) If x0 ∈ supp(σ 1 ), then σx10 ≤ 1 −
p2
1
∗
∗
(ii) If x∗ ∈ supp(σ 1 ), then σx1∗ ≤
p2
α
∗
∗
(iii) If µmin ∈ supp(σ 2 ), then σµ2 min ≤ 1 −
p1
α
0
2∗
2∗
(iv) If µ ∈ supp(σ ), then σµ0 ≤
p1
Proof in Appendix A.3.
The NE (σ̃ 1 , σ̃ 2 ) derived in Prop. 3 attains these bounds. From these upper bounds, one can
extend the game-theoretic intuition of Prop. 3 to any other NE. Specifically, when p2 is close to 1,
the probability with which x0 can be chosen is very small. In contrast, when p2 is large, x∗ can be
chosen only with small probability. Similarly, when p1 is close to α, µmin can be chosen only with
small probability, and when p1 is large, µ0 can be chosen only with a small probability.
Lastly, we present a result analogous to the well-known Minimax Theorem by Von
Neumann [20] for zero-sum games. Recall that the Minimax Theorem for a zeroe = h{1, 2}, (F , A), (e
e1 (σ 1 , σ 2 ) =
sum game Γ
u1 , −u
e1 )i states that maxσ1 ∈∆(F ) minσ2 ∈∆(A) U
∗
∗
∗
e1 (σ 1 , σ 2 ) and (σ 1 , σ 2 ) ∈ Σ
e ⇐⇒ σ 1 ∈ arg maxσ1 ∈∆(F ) minσ2 ∈∆(A) U
e1 (σ 1 , σ 2 )
minσ2 ∈∆(A) maxσ1 ∈∆(F ) U
∗
e1 (σ 1 , σ 2 ). Recall that the Minimax Theorem does not hold
and σ 2 ∈ arg minσ2 ∈∆(A) maxσ1 ∈∆(F ) U
in general for games that are strategically equivalent to a zero-sum game. Interestingly, Γ satisfies
some features of the Minimax Theorem.
Proposition 6.

Proposition 7. Each player’s payoffs for both maximinimizing and minimaximizing strategies
are equal to the payoff at NE, i.e.,
max min U1 (σ 1 , σ 2 ) = 0 = min max U1 (σ 1 , σ 2 )
σ1

σ2

σ2

σ1

1

2

σ2

σ1

σ1

σ2

max min U2 (σ , σ ) = 0 = min max U2 (σ 1 , σ 2 )
Furthermore, the set of minimaximizers is a superset of Σ, i.e., any NE is a minimaximizer.
Proof in Appendix A.3.
As in the Minimax Theorem, maximinimizing or minimaximizing each player’s payoff gives the
value of the game at equilibrium. In addition, Prop. 7 tells us that NE are minimaximizers. However,
one can find minimaximizers that are not NE, which differs from the Minimax Theorem. Finally
the proof of this proposition also implies that NE are not maximinimizers.
4. Budget-constrained game. From Thm. 1, we obtain that the expected cost of transportation (for P1) and the expected cost of attack (for P2) are constant in any NE. However, NE
might differ from each other in the maximum cost of the actions chosen with positive probability.
In this section, we view these costs as “budget expenditures” of the respective players. Recall the
NE (σ̃ 1 , σ̃ 2 ) in Prop. 3, in which P1 randomizes between x0 and x∗ , and in which P2 randomizes
between µ0 and µmin in Region III. To play the strategy σ̃ 1 (resp. σ̃ 2 ) in (11) (resp. (12)), P1
(resp. P2) needs a budget of Tmin (resp. Fmax ) for sending a min-cost max-flow (resp. attacking a
min-cut set). We study the implications of the players not having a budget high enough to perform
(σ̃ 1 , σ̃ 2 ), and more particularly we focus on computing the minimum budgets for which the results
derived in Sections 3.2 and 3.3 still hold (with minor changes).
For P1, we use the infiniteness of her set of actions to find the lowest budget for which previous
structural results hold. However, P2’s set of actions is discrete and we cannot derive the same
bound. We approach this problem by restricting our attention to a subset of P2’s equilibrium
strategies, specifically the strategies supported over the partitions of min-cut sets. Prop. 9 below

16

provides an explicit construction of such equilibrium strategies. Next, for this subset of equilibria,
we formulate a problem for computing minimum budget equilibrium strategies as an integer programming problem. This provides a useful upper bound on P2’s lowest attack budget under which
the previous results hold.
4.1. Revised model We now consider a revised game in which each player faces budget
constraints noted b1 and b2 respectively: P1 (resp. P2) can only send flows with transportation
cost less than or equal to b1 (resp. choose an attack with cost less than or equal to b2 ). In this new
game, the action sets F and A are revised to include the budget constraints b1 and b2 :
Fb1 = {x ∈ F | T (x) ≤ b1 } ,

Ab2 = {µ ∈ A | C (µ) ≤ b2 } .

The new game is defined as Γb1 ,b2 = h{1, 2}, (Fb1 , Ab2 ), (u1 , u2 )i where u1 (resp. u2 ) is given in (2)
(resp. (3)). As previously, we denote ∆(Fb1 ) and ∆(Ab2 ) the set of probability distributions over
Fb1 and Ab2 . We also denote Σb1 ,b2 the set of NE of the game Γb1 ,b2 .
We investigate the question of computing the minimum budget b∗1 and b∗2 for P1 and P2 respectively for which the properties presented in Sections 3.2 and 3.3 hold for the NE of game Γb∗1 ,b∗2 .
One way to tackle this problem is, given b1 and b2 , to find a NE of game Γ that satisfies the
budget constraints. Note that Fb1 ⊆ F and Ab2 ⊆ A. Therefore, if σ ∗ ∈ Σ ∩ (∆(Fb1 ) × ∆(Ab2 )), then
σ ∗ ∈ Σb1 ,b2 (follows from (6) and (7)). In other words, a NE of game Γ that satisfies the budget
constraints b1 and b2 is also a NE of game Γb1 ,b2 . Consequently, with a little effort, one can show
that the previous results are applicable to Γb1 ,b2 .
Note that in the case when b1 and b2 are large enough so both players can send any flow in the
network and attack any subset of edges (i.e., the budget constraints are not binding), Fb1 = F and
Ab2 = A, so Γb1 ,b2 = Γ and all the results derived in Section 3 are applicable.
We now focus on the more interesting case where the budget constraints are binding (Fb1 ( F
and Ab2 ( A). Thanks to the interchangeability of the NE, we can investigate each player’s case
independently while assuming that the other player’s budget constraint is not binding.
4.2. P1’s budget. In this subsection, we are looking to minimize the budget for transporting
flows by P1, b∗1 , such that Σb∗1 ,b2 satisfies the properties presented in Sections 3.2 and 3.3. Without
loss of generality, we assume that b2 ≥ Fmax = C (µmin ). This ensures that σ̃ 2 in (12) is an equilibrium
strategy for P2 in Γb∗1 ,b2 .
First, we argue that for Thm. 1 to hold for Γb∗1 ,b2 , we need b∗1 ≥ p12 Tmin . Indeed, if there existed
∗
∗
a NE (σ 1 , σ 2 ) ∈ Σb1 ,b2 with b1 < p12 Tmin , then we would have:
Eσ∗ [T (x)] =

X

∗

σx1 T (x) <

x∈Fb

1
1 min X 1∗
σx = Tmin ,
T
p2
p2
x∈F
b1

1

which contradicts (16). Therefore b∗1 ≥ p12 Tmin .
Secondly, given any b1 ≥ p12 Tmin , we find an equilibrium strategy of Γ for P1 that assigns positive
probability on flows with transportation cost no greater than b1 . This will ensure that b∗1 ≤ p12 Tmin .
For b1 ≥ Tmin , x∗ ∈ Fb1 so σ̃ from Prop. 3 is a NE of Γb1 ,b2 . However, for p12 Tmin ≤ b1 ≤ Tmin , then
1
x∗ ∈ Fb1 and the following proposition gives a NE of Γb1 ,b2 .
x† := Tbmin
min

Proposition 8. If p1 > α, p2 > 1, Tp2 ≤ b1 ≤ Tmin , b2 ≥ Fmax , and under (A1), then
∗
∗
∗
∗
∗
∗
∗
∃ σ ∗ = (σ 1 , σ 2 ) ∈ Σb1 ,b2 such that U1 (σ 1 , σ 2 ) = U2 (σ 1 , σ 2 ) = 0, and supp(σ 1 ) = {x0 , x† } and
∗
supp(σ 2 ) = {µ0 , µmin }. The corresponding probabilities are given by:
∗

σx10 = 1 −

Tmin
,
p2 b1

∗

σx1† =

Tmin
p2 b1

(24)

17

∗

σµ2 0 =

α
,
p1

∗

σµ2 min = 1 −

α
.
p1

(25)

Proof in Appendix B.1.
The difference between Prop. 8 and Prop. 3 is that since x∗ is too costly to send, P1 sends only
a fraction of x∗ but with higher probability (so (15) in Thm. 1 is still satisfied). This is possible
because P1 has a continuous set of actions.
Thus, Prop. 8 ensures that the previous results still hold when P1’s budget is greater than or
equal to p12 Tmin . This can be concluded by following the corresponding proofs with Prop. 8 as a
starting point instead of Prop. 3. Therefore b∗1 ≤ p12 Tmin , and we can conclude that b∗1 = p12 Tmin .
4.3. P2’s budget. Now, we are looking for the lowest budget for P2, b∗2 , such that Σb1 ,b∗2
satisfies the properties presented in Sections 3.2 and 3.3. Analogously to Section 4.2, we investigate
this case without loss of generality assuming that b1 ≥ Tmin = T (x∗ ). This ensures that σ̃ 1 in (11)
is an equilibrium strategy for P1 in Γb1 ,b∗2 .
∗
∗
Note that b∗2 ≥ Fmax − p11 Tmin . Indeed, if there existed a NE (σ 1 , σ 2 ) ∈ Σb1 ,b2 with b2 <
Fmax − p11 Tmin , then we would have:
Eσ∗ [C (µ)] =

X

µ∈Ab

2

∗
σµ2



1
1 min X 2∗
max
σµ = Fmax − Tmin ,
C (µ) < F
− T
p1
p1
µ∈A
b2

which contradicts (17). Therefore b∗2 ≥ Fmax − p11 Tmin = (1 − pα1 ) Fmax .
Unfortunately, this bound is seldom tight due to the finiteness of P2’s set of actions. For example,
consider the network given in Fig. 4. We can notice that attacking any edge incurs a cost of at least
1. Thus, if b2 = (1 − pα1 ) Fmax < 1, then Ab2 = {µ0 } (P2 cannot attack) and the desired structural
properties of NE may no longer hold.
So far, we know that b∗2 ≤ Fmax thanks to Prop. 3 (for any budget b2 ≥ Fmax , σ̃ 2 is an equilibrium
strategy for P2). We focus on computing a better upper bound on b∗2 by first considering a large
subset of equilibrium strategies supported over the partitions of the min-cut sets. Then we find, in
this subset of equilibrium strategies, the ones that require the lowest attack budget.
4.3.1. Partition-based equilibrium strategies. Throughout this subsection, we consider
a min-cut set E({S , T }). Let {e1 , . . . , eN } denote the edges that constitute the min-cut set, where
N is the number of edges in E({S , T }). Recall that µmin is the attack that disrupts all the edges
of E({S , T }).
A partition of {e1 , . . . , eN } of size n is a set {P1 , . . . , Pn } such that:
∀(i, j) ∈ J1, nK2 | i 6= j : Pi ∩ Pj = ∅, and

[

Pk = {e1 , . . . , eN }.

k∈J1,nK

Definition 1. We say that the set of attacks {µ1 , . . . , µn } is a partition of µmin if there exists
a partition {P1 , . . . , Pn } of the min-cut set {e1 , . . . , eN } of size n such that ∀k ∈ J1, nK, µk = 1Pk is
the attack that disrupts the edges of Pk , i.e.:
(
1 if (i, j) ∈ Pk ,
∀k ∈ J1, nK, µkij =
0 otherwise.
Note that

Pn

k=1

µk = µmin . The following proposition computes NE based on the partitions of µmin .

18

Proposition 9. If p1 > α, p2 > 1, and under (A1), then for any partition {µ1 , . . . , µn } of µmin
of size n, there exists a NE with support and corresponding probabilities given according to the
following two regions:
nα
(i) Region III.a: if α < p1 <
and p2 > 1, then {x0 , x∗ } and {µ1 , . . . , µn } ∪ {µ0 } are the
n
−1
∗
∗
support of a NE (σ 1 , σ 2 ) ∈ Σ defined by:
1
p2


α
α
2∗
2∗
- ∀k ∈ J1, nK, σµk = 1 − , σµ0 = 1 − n 1 −
p1
p1
nα
and p2 > 1, then {x0 , x∗ } and {µ1 , . . . , µn } ∪ {µmin } are the sup(ii) Region III.b: if p1 >
n
−
1
∗
∗
port of a NE (σ 1 , σ 2 ) ∈ Σ defined by:
∗

- σx10 = 1 −

∗

- σx10 = 1 −

1
,
p2

∗

σx1∗ =

1
,
p2

1
p2
α
,
=
p1 (n − 1)
∗

σx1∗ =

∗

- ∀k ∈ J1, nK, σµ2 k

∗

σµ2 min = 1 −

nα
p1 (n − 1)

Proof in Appendix B.2.
These NE are illustrated in Figs. 8 and 9.
p2
I

supp(σ 1 ) = {x0 , x∗ }
∗

III.a

supp(σ 1 ) = {x0 , x∗ }
∗

supp(σ 2 ) = {µ1 , . . . , µn } ∪ {µ0 }

supp(σ 2 ) = {µ1 , . . . , µn } ∪ {µmin }

∗

supp(σ 1 ) = {x0 }
∗

III.b

∗

1
supp(σ 2 ) = {µ0 }
∗

supp(σ 1 ) = {x∗ }
∗

II

supp(σ 2 ) = {µ0 }
∗

0

nα
n−1

α

p1

Figure 8. Support of partition-based equilibrium strategies in Regions I-III.

Given p1 > α and n ∈ J1, N K, let us note Σnp1 the set of P2’s equilibrium strategies described by
Prop. 9 whose support has a size equal to n + 1 (the support is based on a partition of µmin of size
n and, depending on p1 , whether includes µ0 or µmin according to Prop. 9). We denote the set of
P2’s equilibrium strategies described by Prop. 9 (for a fixed p1 ) as:
[
(26)
Σp1 :=
Σnp1 .
n∈J1,N K

Prop. 9 enables us to have an analytical expression of a large number of P2’s equilibrium
strategies. Indeed, given any partition of a min-cut set, we can find a corresponding partition-based
equilibrium strategy for P2 thanks to Prop. 9. Since there are 2N − 1 such partitions, Σp1 contains
2N − 1 equilibrium strategies for P2.
In Fig. 8, we find again Regions I and II outlined in Props. 1 and 2. For Σp1 , Prop. 9 splits
Region III into two subregions, where each subregion considers the partitions of µmin in a specific

19

Figure 9. Probability distribution of P2’s partition-based equilibrium strategies.
nα
> p1 ), an equilibrium strategy for P2 randomizes over the partition
manner. In Region III.a ( n−1
nα
{µ1 , . . . , µn } and µ0 . However, in Region III.b ( n−1
< p1 ), an equilibrium strategy for P2 randommin
izes over the same partition and µ . Intuitively, if P2 partitions µmin in too many components
nα
decreases), then she assigns positive probability to the min-cut set attack. However, if she
(i.e., n−1
partitions µmin in fewer components, then she chooses no attack action with a nonzero probability.
Remark 2. The case n = 1 corresponds to attacking the whole min-cut set (it’s a partition of
nα
−→ +∞. Therefore, if we draw Fig. 8 in the case n = 1,
size 1). When n tends to 1 from above, n−1
we find again Fig. 3 (Region III.a expands); thus, Prop. 3 is a particular case of Prop. 9.
Example 6. Let us illustrate Prop. 9 with the example in Fig. 4. Recall that the only min-cut
set is {(1, 3), (2, 3), (2, 4)} and the only min-cost max-flow sends one unit of flow through each of
the paths {s, 1, 3, t}, {s, 2, 3, t} and {s, 2, 4, t}.
Let us consider one partition {{(1, 3), (2, 3)}{(2, 4)}} of the min-cut set. From this partition, we
construct the corresponding attacks µ1 that disrupts edges (1, 3) and (2, 3), and µ2 that disrupts
edge (2, 4). Thus, {µ1 , µ2 } is a partition of µmin . The results obtained by applying Prop. 9 to this
example are presented in Fig. 10.

nα
,
n−1

p1 <

p2 > 1
1

1,2,1

s
2,3,1
1
σ =
p2
1∗
x∗

2∗

1,1,1

σµ1

3
=1−
p1

3

1,1,1

0,1,1

2

σµ22 = 1 −
∗

2,3,1
0,1,1

1,1,1
3
p1

4

III.a

t
1,2,1

nα
,
n−1

p1 >

p2 > 1
1

1,2,1

s

0,1,1

σµ21 =
∗

1,1,1

3

2,3,1
1,1,1
2
1
6
σ =
∗
p2 σµ2min = 1 −
p1

4
σµ22 =
∗

III.b
2,3,1

0,1,1

1,1,1

1∗
x∗

3
p1

t
1,2,1

3
p1

Figure 10. NE described in Prop. 9 based on the partition {µ1 , µ2 }.

Now that we can analytically compute many more NE, we can try to find the equilibrium
strategies among Σp1 that require the lowest budget.

20

4.3.2. Optimization problem. In the previous subsection, we saw that any partition of µmin
(along with µ0 , µmin ) can be used to explicitly construct a subset of equilibrium strategies for P2.
Specifically, an equilibrium based on such a partition can be mapped into one of the two regions
(III.a-b) illustrated in Fig. 8.
Without loss of generality, let us consider a unique min-cut set {e1 , . . . , eN } consisting of N edges.
With a slight abuse of notation, let us denote ck the capacity of edge ek (for all k ∈ J1, N K).
First, note the following:
σ 2 ∈ ∆(Ab2 ) ⇐⇒ ∀µ ∈ supp(σ 2 ), C (µ) ≤ b2 ⇐⇒

max

µ∈supp(σ2 )

C (µ) ≤ b2 .

That is, a strategy satisfies the budget constraint if and only if the maximum cost of conducting
an attack chosen with positive probability is no greater than the resource budget.
Therefore, we want to find a strategy in Σp1 (defined in (26)) that minimizes the maximum cost
of conducting an attack chosen with a positive probability, i.e.:
max

arg min

2∗
σ2 ∗ ∈Σp1 µ∈supp(σ )

C (µ)

(27)

The following proposition gives the answer.
Proposition 10. Among the NE listed in Prop.
o that minimizes the budget needed
nj 9, akstrategy
1
, N , and is obtained by solving the folis based on a partition of µmin of size n∗ = min p1p−α
lowing integer-programming problem:
(IP ) minimize

z

subject to z ≥

N
X

cl ylk , ∀k ∈ J1, n∗ K

l=1

∗

n
X

ylk = 1, ∀l ∈ J1, N K

k=1

ylk ∈ {0, 1}, ∀(l, k) ∈ J1, N K × J1, n∗ K.
Proof in Appendix B.2.
Given a partition {µ1 , . . . , µn } of µmin , the support of the corresponding strategy in Σp1 is this
partition along with µmin or µ0 depending on p1 . Let us note {P1 , . . . , Pn } the corresponding
partition of the min-cut set. For every k ∈ J1, nK, one may notice the following:
C µ

k



=

X

(i,j)∈Pk

cij =

N
X

cl µkel .

(28)

l=1

The cost of conducting attack µk is equal to the sum of the capacities of the edges of the min-cut
set that µk disrupts. Therefore, the more P2 partitions µmin , the less number of edges of the min-cut
nα
> p1 , P2 randomizes over the partition and
set each µk disrupts. In Prop. 9, we saw that when n−1
no attack, so the maximum attacking cost is induced by one of the elements of the partition. Thus,
nα
nα
decreases and we saw that when n−1
< p1 ,
P2 needs to increase n. However, when n increases, n−1
then µmin enters the support and the budget thatnis needed is Fmax (theocapacity
of
the
min-cut).
nj
k o
nα
1
Therefore, P2 needs to increase n until n∗ = max n ∈ J1, N K | n−1
≥ p1 = min p1p−α
,N .
min
∗
Knowing the optimal size of the partition of µ , we can find a partition of size n that minimizes
the maximum attacking cost. Thanks to (28), one can see that this is equivalent to assigning N
objects (the edges of the min-cut set) of value cl each, into n∗ bags such that the maximum value
of the bags is minimized. This is the purpose of (IP).

21

The optimal value of (IP), z ∗ , gives a new upper bound on b∗2 (the results derived in Sections 3.2
and 3.3 hold when b2 ≥ z ∗ ≥ b∗2 ≥ Fmax − p11 Tmin ). Depending on the min-cut set, z ∗ may be much
smaller than Fmax , which was the previous upper bound on b∗2 obtained thanks to Prop. 3. In
∗
, gives us the corresponding way of partitioning µmin
addition, the optimal solution of (IP), ylk
∗
(ylk
= 1 if and only if edge el is disrupted by µk ), and Prop. 9 derives the corresponding probabilities.
Let us illustrate Prop. 10 with an example.
Example 7. Once again, consider the network given in Fig. 4 and assume that p1 = 5. First,
let us enumerate all the equilibrium strategies of Σp1 in Fig. 11:
σµ21 =
∗

s

1,1

1

2,1

1,1

1,1
3,1

3

σµ2min =
∗

σµ22 =
∗

1

s

2∗

σµ2

1,1
3,1

2

3,1
s

t

1,1
1,1

2
σµ22 =
∗

(c) Partition of size 2
3
=
10 1,1

2∗

3
=
10

1

2,1

σµ2

1,1
3,1

2,1

2
5

3,1

1,1

t
4

2,1

(d) Partition of size 2
2∗
µ1

σ

s

2
5

3

1,1
3,1

2,1

4

1,1

t
4

1

2,1

1,1

1,1

3,1

(b) Partition of size 2
2
∗
σµ21 =
5 1,1

3

2
=
5

3

1,1

1,1

2

(a) Partition of size 1
2
∗
σµ21 =
1,1
5

2,1

1,1

1,1
3,1

2,1

4

2
5

s

t

1,1

1

2,1

1,1

1,1

2

3,1

2
5

3
1,1

1,1
1,1

2
σµ23 =
∗

3
10

3,1

4
σµ2min =
∗

t
2,1

1
10

(e) Partition of size 3
Figure 11. Enumeration of the equilibrium strategies in Σp1 .

Fig. 11a shows that the NE of Σ1p1 contains an attack that induces a cost of 3, while Figs. 11b,
11c, and 11d show that the NE of Σ2p1 contain attacks that induce at most a cost of 2. However,
Fig. 11e shows that the NE of Σ3p1 contains an attack that also has a cost of 3. Therefore, P2’s
equilibrium strategies
o require the lowest budget are based on a partition of size 2, which
njof Σkp1 that
5
corresponds to min 5−3 , 3 . For this example, the previous results hold when b2 ≥ 2 = z ∗ .
Thus, by combining Props. 9 and 10, we can compute a new upper bound on the lowest attack
budget for P2 to which we can apply the results derived in Sections 3.2 and 3.3.

22

5. Discussion. Let us discuss the implications of relaxing some assumptions of our model.
First, we study a network that does not satisfy (A1) to see under which circumstances our results
can still be applied. Next, we present a weaker assumption than (A1) for which the results derived
in Section 3 still hold. We also discuss our assumption regarding the cost of attack: in the model
studied in this article, we supposed that the cost of attacking an edge was proportional to its
capacity. We now present an example network with a general cost of attack to study how some of
the results derived in this article apply to such networks.
5.1. Relaxing Assumption 1. Consider the graph given in Fig. 12a and consider the game
Γ with p1 = p2 = 6. The unique min-cost max-flow sends one unit of flow through each of the paths

1,1

1

s

1,4
1,1

1,4

2

1,1
t

1,1

(a) Initial graph

1

s

1,1
2

t
1,1

(b) Subgraph

Figure 12. Removal of paths that are too costly for P1.

{s, 1, t} and {s, 2, t} whose marginal transportation cost is equal to 5. However, {s, 1, 2, t} has a
marginal transportation cost equal to 3 so (A1) does not hold. We can show that σ̃ defined in (11)
and (12) is not a NE anymore. Let us note x′ the flow that sends 1 unit through path {s, 1, 2, t},
µ1 = 1(s,1) , µ2 = 1(1,2) and µ3 = 1(2,t) . Then, one can show that there exists an equilibrium where
∗
∗
∗
∗
∗
P1’s strategy σ 1 is defined by σx1′ = 16 and σx10 = 65 , and P2’s strategy σ 2 is defined by σµ2 1 =
∗
∗
∗
σµ2 2 = σµ2 3 = 61 and σµ2 0 = 12 . We can see that this strategy does not rely on the min-cost max-flow
and the min-cut set anymore.
However, if we consider the game Γ for the parameter range 3 < p1 < 5 and p2 > 1, then we can
∗
∗
∗
∗
∗
∗
prove that (σ 1 , σ 2 ) defined by σx10 = 1 − p12 , σx1′ = p12 , and σµ2 0 = p31 , σµ2 2 = 1 − p31 is a NE. This
result looks similar to the one we derived in Prop. 3. Actually, they are related: when 3 < p1 < 5, the
marginal transportation costs of paths {s, 1, t} and {s, 2, t} are higher than the marginal value of
effective flow, so P1 has no incentive to send any flow along these paths. If we remove these paths
from the graph (as in the elimination of strictly dominated strategies), we obtain the subgraph in
Fig. 12b. It turns out this subgraph satisfies (A1) (it’s only a path). Therefore, our results apply to
this subgraph (i.e., the equilibrium we found is exactly σ̃ from Prop. 3 applied to this subgraph),
and also to the original graph.
This example indicates that our results can be extended to networks for which (A1) holds for
the reduced graph obtained after the removal of paths with transportation cost that are too large.

5.2. Transportation cost. It turns out the characterization of the NE of the game Γ (ref.
Section 3) is also valid for a larger class of networks satisfying the following weaker assumption:
Assumption 2. There exists an optimal solutionPof (P2 ) denoted x∗ ∈ Ω∗ , and there exists
a min-cut set {e1 , . . . , eN } with αk := min{λ∈Λ | ek ∈λ} (i,j)∈λ bij , ∀k ∈ J1, N K, such that for every
k ∈ J1, N K, all s − t paths taken by x∗ that go through ek have identical marginal transportation cost
αk , i.e.,
X
∃ x∗ ∈ Ω∗ , ∃ min-cut set {e1 , . . . , eN } | ∀k ∈ J1, N K, ∀λ ∈ Λ | ek ∈ λ : x∗λ > 0 =⇒
bij = αk .
(i,j)∈λ

23

In contrast to (A1), this assumption considers a class of networks whose min-cost max-flow takes
paths that have different marginal transportation cost. Note that in (A2), when α1 = · · · = αN ≡ α,
we find again (A1). Below is an instance of a network that does not satisfy (A1) but satisfies (A2).
Example 8. Consider the network flow problem in Fig. 13. There is a unique min-cost maxflow x∗ , which carries 1 unit of flow through paths {s, 2, 4, t}, {s, 2, 3, t} and {s, 1, t}. Thus, the
total amount of flow is equal to 3 units. However, these paths induce different transportation costs;
therefore (A1) is not satisfied.
Let us note e1 = (s, 1), e2 = (2, 3) and e3 = (4, t), then {e1 , e2 , e3 } is a min-cut set. One can check
that α1 = 2, α2 = 3 and α3 = 4. For k ∈ {1, 2, 3}, the paths taken by x∗ that go through ek induce a
transportation cost equal to αk . Thus, (A2) is satisfied, and with a little effort, we can check that
our results in Section 3 also apply to the game Γ defined on this network.
0,1,3

1,1,2

4
1,1,1

s

2,2,1

2

1,1,1

1,1,1

3

t

0,1,1

1,1,1
1

1,1,1

Figure 13. Min-cost max-flow (bold blue) and min-cut set (dotted red) of a network satisfying (A2).

5.3. Cost of attack. Another assumption of our model is that the cost of attacking an edge
is proportional to its capacity (ref. (3)). We investigate through an example the implications of
considering the case of a more general cost structure for executing an attack. Let us consider the
network given by Fig. 14, and once again note that σ̃ from (11) and (12) is not a NE anymore.

1,1,3

1

s
1,1,2

1,1,1
1,1,1

2

t
1,1,2

Figure 14. Network with general cost of attack. Edge capacities, transportation cost and cost of attack are denoted
in red, green and orange colored labels respectively.

Let x1 be the flow that sends 1 unit through path {s, 1, t}, x2 be the flow that sends 1 unit
through path {s, 2, t}, and µ′ = 1{(1,t),(2,t)} be the attack that disrupts edges (1, t) and (2, t). One
∗
∗
∗
∗
∗
can show that when p1 > 2 and p2 > 3, (σ 1 , σ 2 ) defined by σx10 = 1 − p32 , σx11 = p12 , σx12 = p22 and
∗
∗
σµ2 0 = p21 , σµ2 ′ = 1 − p21 is a NE.
Notice that {(1, t), (2, t)} is the cut-set of the graph that induces the smallest cost of attack.
Hence, according to this NE, we conjecture that for networks with such general attack costs, the
cut-set that induces the smallest attacking cost might form the support of an equilibrium strategy
for P2 (in contrast to the min-cut set in our article). Indeed, in our model, since the attacking cost

24

was proportional to the edge capacity, the min-cut sets were the cut-sets that induced the smallest
cost of attack.
Regarding P1’s strategy, we can see that in this case, she routes x2 twice as frequently as x1
because the cost of attacking (2, t) is twice as the cost of attacking (1, t). This result differs from
the NE we found in our model: each path taken by the min-cost max-flow was taken with the same
probability, p12 , at equilibrium.
Appendix A: Proof of properties of Nash equilibria.
A.1. Proof of preliminary results.
Proof of Lemma 1. u1 is not an affine variant of −u2 . Indeed, let us suppose the contrary:
∃ (λ, β) ∈ R∗+ × R | ∀(x, µ) ∈ F × A, u1 (x, µ) = −λu2 (x, µ) + β

Noting (2) and (3), we have the following contradiction:
0 = u1 (x0 , µ0 ) + λu2 (x0 , µ0 ) = β = u1 (x∗ , µ0 ) + λu2 (x∗ , µ0 ) 6= 0.
Therefore, u1 is not an affine variant of −u2 and Γ is not an SCG (and a fortiori not a zero-sum
game either).
However, the following transformations preserve the set of NE:
1
1
1
1
u1 (x, µ) + C (µ) = F (xµ ) − T (x) + C (µ) = u
e1
p1
p2
p1
p2
1
1
1
1
u2 (x, µ) − F (x) + T (x) = − F (xµ ) + T (x) − C (µ) = −u
e1
p2
p1
p1
p2

(29)
(30)

e and Σ = Σ,
e where Σ
e denotes the set of NE
So Γ is strategically equivalent to a zero-sum game Γ
e
of Γ.

Proof of Lemma 2. Suppose that P1 chooses a flow x containing a loop l, i.e., the flow xl > 0
stays in the loop and never reaches t. Then, if we note x − xl the flow resulting from removing the
part of x that goes through l, we obtain u1 (x, µ) < u1 (x − xl , µ) for any attack µ. Thus, any flow
containing loops is strictly dominated.

Proof of Proposition 1. Let us characterize the strategies that survive the iterated elimination of strictly dominated strategies.
(8)

∀(x, µ) ∈ F × A, u1 (x, µ) = p1 F (xµ ) − T (x) ≤ p1 F (xµ ) − α F (x) ≤ (p1 − α) F (x) ≤ 0.

If x 6= x0 , then ∀µ ∈ A, u1 (x, µ) < 0 = u1 (x0 , µ). Therefore x 6= x0 is strictly dominated and cannot
be in the support of any NE.
Since ∀µ ∈ A, u2 (x0 , µ) = p2 F (x0 − (x0 )µ ) − C (µ) = − C (µ), then, ∀µ ∈ A\{µ0 }, u2 (x0 , µ) =
− C (µ) < 0 = u2 (x0 , µ0 ). Hence, µ 6= µ0 is now strictly dominated and cannot be in the support
of any NE. Thus, (x0 , µ0 ) is the unique strategy that survives the iterated elimination of strictly
dominated strategies. We can conclude that (x0 , µ0 ) is the unique NE when p1 < α.

We need the following lemma to prove Prop. 2 and some of the subsequent results:

25

Lemma 4. The loss induced by any attack µ when a flow x is routed in the network is no greater
than the cost of the attack µ.
∀(x, µ) ∈ F × A, F (x − xµ ) ≤ C (µ) .

(31)

Furthermore, the loss induced by any attack µ that only disrupts edges of a min-cut set when a
min-cost max-flow is routed in the network is equal to the cost of the attack µ.
∀x∗ ∈ Ω∗ , ∀µ ∈ A | ∃ min-cut set E({S , T }) | ∀(i, j) ∈ E , µij = 1 =⇒ (i, j) ∈ E({S , T }) :

F (x∗ − x∗ µ ) = C (µ) .

(32)

Proof of Lemma 4 Consider a flow x ∈ F and an attack µ ∈ A. First, notice the following:
X
X
X
F (x − xµ ) = F (x) − F (xµ ) =
xλ −
xλ =
xλ ,
(33)
λ∈Λ

{λ∈Λ | ∀(i,j)∈λ, µij =0}

{λ∈Λ | ∃ (i,j)∈λ | µij =1}

because Λ = {λ ∈ Λ | ∀(i, j) ∈ λ, µij = 0} ∪ {λ ∈ Λ | ∃ (i, j) ∈ λ | µij = 1}.
Second, we have the following:
X
X
X
(1)
C (µ) =
cij ≥
xij =
{(i,j)∈E | µij =1}

=

X

xλ 1{(i,j)∈λ} =

{(i,j)∈E | µij =1} λ∈Λ

X
λ∈Λ

Notice that ∀λ ∈ Λ | ∀(i, j) ∈ λ, µij = 0, we have:
X
1{(i,j)∈λ} =
{(i,j)∈E | µij =1}

and ∀λ ∈ Λ | ∃ (i, j) ∈ λ | µij = 1, we have:
X
1{(i,j)∈λ} =
{(i,j)∈E | µij =1}

xλ

{(i,j)∈E | µij =1} {λ∈Λ | (i,j)∈λ}

{(i,j)∈E | µij =1}

X

X

xλ

X

1{(i,j)∈λ}

{(i,j)∈E | µij =1}

X

1 = 0,

X

1 ≥ 1.

{(i,j)∈λ | µij =1}

{(i,j)∈λ | µij =1}

Therefore, we obtain:
C (µ) ≥

X

xλ × 0 +

{λ∈Λ | ∀(i,j)∈λ, µij =0}

X

xλ × 1

{λ∈Λ | ∃ (i,j)∈λ | µij =1}

(33)

= F (x − xµ )

Now, consider a min-cost max-flow x∗ ∈ Ω∗ and an attack µ that disrupts only some edges of
a min-cut set. If we follow the proof given previously, we can see that the inequalities become
equalities in this case.
Indeed, ∀(i, j) ∈ E | µij = 1, cij = x∗ij because the (min-cost) max-flows saturate all the edges of
every min-cut set.
Besides, every path taken by a (min-cost) max-flow goes through only one edge of a min-cut set.
Therefore:
X
X
X
1=
x∗λ = F (x∗ − (x∗ )µ )
C (µ) =
x∗λ
{λ∈Λ | ∃ (i,j)∈λ | µij =1}

{(i,j)∈λ | µij =1}

{λ∈Λ | ∃ (i,j)∈λ | µij =1}



26



µ0
− T (x∗ ) = (p1 − α) Fmax .
First, u1 (x∗ , µ0 ) = p1 F (x∗ )
 0
(8)
Second, ∀x ∈ F , u1 (x, µ0 ) = p1 F xµ − T (x) ≤ (p1 − α) F (x) ≤ (p1 − α) Fmax . So x∗ is a BR for
P1.


0
0
Similarly, u2 (x∗ , µ0 ) = p2 F x∗ − (x∗ )µ − C (µ0 ) = 0 because (x∗ )µ = x∗ . Besides,
Proof of Proposition 2.

∀µ ∈ A, u2 (x∗ , µ) = p2 F (x∗ − (x∗ )µ ) − C (µ) ≤ F (x∗ − (x∗ )µ ) − C (µ) ≤ 0

where the first inequality follows from p2 ≤ 1 and the second inequality follows from (31). Thus,
µ0 is a BR for P2.
Therefore ∀x∗ ∈ Ω∗ , (x∗ , µ0 ) is a NE.

Proof of Proposition 3.
– First, let us show that any pure strategy is not a NE.
Let us suppose that P2 chooses an attack µ that disrupts m edges e1 , . . . , em of G (m can be
equal to 0). Now, let us suppose that P1 chooses a flow x that crosses one of the attacked edges,
for instance e1 . If we note xp the part of x that goes through e1 , then xp will be lost because of
the attack so the value of effective flow obtained by routing x is the same as if x − xp had been
routed. However, the transportation cost of x is strictly greater than the transportation cost of
x − xp . Therefore u1 (x, µ) < u1 (x − xp , µ).
Thus, a BR for P1 does not take paths containing at least one attacked edge. Let us note
G µ = (V , E\{e1 , . . . , em }). Then, P1’s BR is a feasible flow in G µ . Now, let us suppose that P1
chooses only such flows, the utility becomes u1 (x, µ) = p1 F (x) − T (x). There are two cases:
- Case 1: there is no path in G µ with marginal transportation cost less than p1 . Then, P1’s BR is
x0 (no flow). However, if P1 chooses x0 , then it’s easy to see that P2’s BR is µ0 (no attack),
which means that the initial µ is not a BR for P2 in this case. Notice that if the initial µ is
µ0 , then Case 1 is not satisfied (there are paths in G of marginal transportation cost less than
p1 , because of the definition of α).
- Case 2: there exists at least one path in G µ with marginal transportation cost less than p1 .
Then, P1’s BR is to send as much flow as she can along the paths with maginal transportation
cost less than p1 (if there are different such flows with the same value, then P1’s BR is the
one with least transportation cost). However, if P1 chooses this BR, then the initial attack µ
does not induce any loss, and P2 will have an incentive to disrupt some edges of G µ instead
(for instance we can prove that at least one edge is saturated by P1’s BR so P2 will gain
utility by attacking that edge since p2 > 1). Thus, P2’s BR is different from µ.
Therefore, every pure strategy is not a NE.
– Now let us prove that σ̃ = (σ̃ 1 , σ̃ 2 ) defined in (11) and (12) is a NE.
(4)

∀σ 1 ∈ ∆(F ), U1 (σ 1 , σ̃ 2 ) = p1

(8)
α
Eσ [F (x)] − Eσ [T (x)] ≤ αEσ [F (x)] − αEσ [F (x)] = 0.
p1

Besides, note that U1 (σ̃ 1 , σ̃ 2 ) = α
Similarly, note that

1
α
1
(9) α
F (x∗ ) − T (x∗ ) =
F (x∗ ) − F (x∗ ) = 0.
p2
p2
p2
p2
(5)

µ

∀σ 2 ∈ ∆(A), U2 (σ̃ 1 , σ 2 ) = F (x∗ ) − Eσ [F ((x∗ ) )] − Eσ [C (µ)]
(31)

= Eσ [F (x∗ − (x∗ )µ ) − C (µ)] ≤ 0,

27

Finally, thanks to the Max-Flow Min-Cut Theorem, we have



α
α
1
2
∗
∗
U2 (σ̃ , σ̃ ) = F (x ) − F (x ) − 1 −
C µmin = 0.
p1
p1

Thus, (σ̃ 1 , σ̃ 2 ) is a NE.


A.2. Proof of main theorem. We present two proofs of Thm. 1. The first proof involves
the combination of the Max-Flow Min-Cut Theorem and best response inequalities. The second
e defined in
proof combines the Max-Flow Min-Cut Theorem with linear programming duality of Γ
e
Lemma 1 (recall that Σ = Σ).
To prove Thm. 1, we need the following lemma:
Lemma 5.

∗

∗

µ

∀(σ 1 , σ 2 ) ∈ Σ, ∀x∗ ∈ Ω∗ , Eσ∗ [F ((x∗ ) )] = F (x∗ ) − Eσ∗ [C (µ)] .

(34)

Proof of Lemma 5. We can relate both players’ expected payoffs in two different ways:
p1
p1
Eσ [C (µ)] − U2 (σ 1 , σ 2 )
p2
p2
p2
p2
U2 (σ 1 , σ 2 ) = −Eσ [C (µ)] + p2 Eσ [F (x)] − Eσ [T (x)] − U1 (σ 1 , σ 2 )
p1
p1

U1 (σ 1 , σ 2 ) = p1 Eσ [F (x)] − Eσ [T (x)] −

∗

(35)
(36)

∗

Let σ ∗ = (σ 1 , σ 2 ) ∈ Σ. Since (σ̃ 1 , σ̃ 2 ) ∈ Σ (Prop. 3), we have:
(7)

∗ (5)

µ

0 = U2 (σ̃ 1 , σ̃ 2 ) ≥ U2 (σ̃ 1 , σ 2 ) = F (x∗ ) − Eσ∗ [F ((x∗ ) )] − Eσ∗ [C (µ)]
So we get the following inequality:
µ

Eσ∗ [F ((x∗ ) )] ≥ F (x∗ ) − Eσ∗ [C (µ)]
∗

(37)

∗

Now, since (σ 1 , σ 2 ) ∈ Σ:
1
∗
∗ (6)
∗ (4) p1
µ
U1 (σ 1 , σ 2 ) ≥ U1 (σ̃ 1 , σ 2 ) = Eσ∗ [F ((x∗ ) )] − T (x∗ )
p2
p2
α
(9) p1
∗
∗ µ
= Eσ∗ [F ((x ) )] − F (x )
p2
p2

(38)

By combining (7) and (35), and using σ̃ 2 (ref. (12)), we obtain the following sequence of inequalities:
∗

p1
p1
∗
∗
Eσ∗ [C (µ)] − U2 (σ 1 , σ 2 )
p2
p2
(8)
p1
p1
∗
∗
≤ (p1 − α)Eσ∗ [F (x)] − Eσ∗ [C (µ)] − U2 (σ 1 , σ 2 )
p2
p2
(7)
p1
p1
∗
≤ (p1 − α)Eσ∗ [F (x)] − Eσ∗ [C (µ)] − U2 (σ 1 , σ̃ 2 )
p2
p2
p1
(5)
=(p1 − α)Eσ∗ [F (x)] − Eσ∗ [C (µ)] − p1 Eσ∗ [F (x)]
 p2 

α p1
C µmin
+ αEσ∗ [F (x)] + 1 −
p1 p2

∗ (35)

U1 (σ 1 , σ 2 ) = p1 Eσ∗ [F (x)] − Eσ∗ [T (x)] −

28

Therefore:
∗

∗

U1 (σ 1 , σ 2 ) ≤



 α
p1
C µmin − Eσ∗ [C (µ)] − C µmin
p2
p2

(39)

Combining (38) and (39), and using the Max-Flow Min-Cut Theorem, we obtain the reverse
inequality:
µ

Eσ∗ [F ((x∗ ) )] ≤ F (x∗ ) − Eσ∗ [C (µ)]

(40)

From (37) and (40) we conclude that:
µ

Eσ∗ [F ((x∗ ) )] = F (x∗ ) − Eσ∗ [C (µ)]

Now we can prove Thm. 1.
∗
∗
First Proof of Theorem 1. Let σ ∗ = (σ 1 , σ 2 ) ∈ Σ. The first step is to show (iii) (the
expected cost of attack), but we will need a few intermediate equations before.
∗
∗
Let us prove that U1 (σ 1 , σ 2 ) ≥ 0:
∗ (6)

∗

∗

U1 (σ 1 , σ 2 ) ≥ U1 (x0 , σ 2 ) = 0

(41)

By combining (39) and (41), we obtain:



α
Eσ∗ [C (µ)] ≤ 1 −
C µmin
p1
In order to get the reverse inequality, let us consider the strategy σǫ1 defined by σx1∗ =

(42)
1+ǫ
and
p2

1+ǫ
for an ǫ small enough (we can find such an ǫ and still have a probability distribution
p2
since p2 > 1):

σx10 = 1 −

∗

∗ (6)

∗ (4)

U1 (σ 1 , σ 2 ) ≥ U1 (σǫ1 , σ 2 ) =

(9)

=

p1 (1 + ǫ)
1+ǫ
µ
Eσ∗ [F ((x∗ ) )] −
T (x∗ )
p2
p2
p1 (1 + ǫ)
α(1 + ǫ)
µ
Eσ∗ [F ((x∗ ) )] −
F (x∗ )
p2
p2

Applying (34) from Lemma 5 gives us:
∗

∗

U1 (σ 1 , σ 2 ) ≥

p1 (1 + ǫ)
α(1 + ǫ)
(F (x∗ ) − Eσ∗ [C (µ)]) −
F (x∗ )
p2
p2

(43)

Now we combine (39) and (43) to get the following inequality:
p1 ǫ
p1 ǫ
αǫ
F (x∗ ) −
Eσ∗ [C (µ)] −
F (x∗ ) ≤ 0
p2
p2
p2
which is equivalent to the desired inequality:


α
Eσ∗ [C (µ)] ≥ 1 −
F (x∗ )
p1

(44)

29

From (42), (44), and the Max-Flow Min-Cut Theorem, we obtain the expression of the expected
cost of attack in any NE σ ∗ ∈ Σ:





α
1
α
(9)
min
Eσ∗ [C (µ)] = 1 −
(45)
C µ
= 1−
Fmax = Fmax − Tmin
p1
p1
p1
We can now use this equation in order to prove that P1’s payoff is equal to 0 at equilibrium: by
combining (39) and (45), we obtain:
∗

∗

U1 (σ 1 , σ 2 ) ≤ 0

(46)

Therefore, (41) and (46) give us that P1’s equilibrium payoff is zero:
∗

∗

U1 (σ 1 , σ 2 ) = 0

(47)

Let us now prove (15) (the expected amount of initial flow). Analogously to the previous argu∗
∗
ments, we first prove that U2 (σ 1 , σ 2 ) ≥ 0:
∗

∗ (7)

∗

U2 (σ 1 , σ 2 ) ≥ U2 (σ 1 , µ0 ) = 0

(48)

From our previous results:
∗

p2
p2
∗
∗
Eσ∗ [T (x)] − U1 (σ 1 , σ 2 )
p1
p1
p2
(47)
= − Eσ∗ [C (µ)] + p2 Eσ∗ [F (x)] − Eσ∗ [T (x)]

 p1
(8)
α
≤ − Eσ∗ [C (µ)] + p2 1 −
Eσ∗ [F (x)]
p1



α
(45)
p2 Eσ∗ [F (x)] − C µmin
= 1−
p1

∗ (36)

U2 (σ 1 , σ 2 ) = − Eσ∗ [C (µ)] + p2 Eσ∗ [F (x)] −

(49)

By combining (48) and (49), we obtain:

Eσ∗ [F (x)] ≥


1
C µmin
p2

(50)

α−ǫ
To get the reverse inequality, consider the strategy σǫ2 defined by σµ2 0 =
and σµ2 min =
p1
α−ǫ
, for an ǫ small enough (we can find such an ǫ and still have a probability distribution
1−
p1
since p1 > α):
p1
p1
∗
∗
∗
∗ (35)
U1 (σ 1 , σ 2 ) = p1 Eσ∗ [F (x)] − Eσ∗ [T (x)] − Eσ∗ [C (µ)] − U2 (σ 1 , σ 2 )
p2
p2
(8)
p1
p1
∗
∗
≤ (p1 − α)Eσ∗ [F (x)] − Eσ∗ [C (µ)] − U2 (σ 1 , σ 2 )
p2
p2
(7)
p1
p1
∗
≤ (p1 − α)Eσ∗ [F (x)] − Eσ∗ [C (µ)] − U2 (σ 1 , σǫ2 )
p2
p2
p1
(5)
∗
∗
=(p1 − α)Eσ [F (x)] − Eσ [C (µ)] − p1 Eσ∗ [F (x)]
p
2


α − ǫ p1
C µmin
+ (α − ǫ)Eσ∗ [F (x)] + 1 −
p1
p2


 α−ǫ
p1
min
=
C µmin − ǫEσ∗ [F (x)]
C µ
− Eσ∗ [C (µ)] −
p2
p2


 p1

 α−ǫ
α
(45) p1
min
C µ
−
C µmin − ǫEσ∗ [F (x)]
1−
C µmin −
=
p2
p2
p1
p2

ǫ
min
− ǫEσ∗ [F (x)] ,
= C µ
p2

30

and applying (41) gives us:
0≤


ǫ
C µmin − ǫEσ∗ [F (x)]
p2

Thus, we obtain the desired inequality:

Eσ∗ [F (x)] ≤


1
C µmin
p2

(51)

From (50), (51), and the Max-Flow Min-Cut Theorem, we obtain the expression of the expected
amount of initial flow:
Eσ∗ [F (x)] =

1
1
F (x∗ ) = Fmax
p2
p2

(52)

Likewise, by combining (49) and (52), we get:
∗

∗

U2 (σ 1 , σ 2 ) ≤ 0

(53)

Equations (48) and (53) give us that P2’s equilibrium payoff is also zero:
∗

∗

U2 (σ 1 , σ 1 ) = 0
Thus, we proved (i).
Now, by combining (5), (45), (52), and (54), we easily show (iv):


α
α max (9) 1
1 max 1
µ
=
−
F
Tmin
1−
Fmax =
Eσ∗ [F (x )] = F
p2
p2
p1
p1 p2
p1 p2

(54)

(55)

Finally, by combining (4), (47), and (55), we can finish proving (ii):
Eσ∗ [T (x)] = p1

α max α max (9) 1 min
F
= F
T .
=
p1 p2
p2
p2


Second Proof of Theorem 1. We know that in a zero-sum game, each player’s payoff is
e Therefore:
constant for any NE. Prop. 3 tells us that σ̃ ∈ Σ.
∗
∗
e U
e1 (σ 1 ∗ , σ 2 ∗ ) = U
e1 (σ̃ 1 , σ̃ 2 )
∀(σ 1 , σ 2 ) ∈ Σ,



1 1
1
α
(10) 1 α
∗
max
=
F (x ) −
T (x ) +
1−
C µmin
p2p1
p2
p1
 p1 p2
α
1
max
1−
F
=
p2
p1

(56)

and this quantity is the optimal value of (LP1 ).
∗
∗
Let σ ∗ = (σ 1 , σ 2 ) ∈ Σ. First, let us prove again Lemma 5:
e then:
By interchangeability, since σ̃ ∈ Σ,


1
α
(56)
e1 (σ̃ 1 , σ̃ 2 ) = U
e1 (σ̃ 1 , σ 2 ∗ ) = 1 Eσ∗ [F ((x∗ )µ )] − α F (x∗ ) + 1 Eσ∗ [C (µ)]
1−
Fmax = U
p2
p1
p2
p1 p2
p2

which directly gives the result.
Now, we prove the equalities thanks to complementary slackness: recall that (LP2 ) is the dual
of (LP1 ) (and vice-versa), which means that ∀µ ∈ A, σµ2 is the dual variable associated with the

31

e1 (σ 1 , µ) ≥ z. Similarly, ∀x ∈ F , σx1 is the dual variable associated with the constraint
constraint U


2
e2 (x, σ ) ≥ z ′ . We know that the optimal value of (LP1 ) (resp. (LP2 )) is 1 1 − α Fmax (resp.
U
p2
p1


max
1
α
− p2 1 − p1 F ). Therefore, since NE are the optimal solutions of these LPs, complementary
∗
∗
e
slackness can be written as follows: ∀(σ 1 , σ 2 ) ∈ Σ,




α
1
max
2∗
e
1−
F
U2 (x, σ ) +
∀x ∈ F ,
=0
p2 
p1 


∗
e1 (σ 1 ∗ , µ) − 1 1 − α Fmax = 0
∀µ ∈ A, σµ2 U
p2
p1
∗
σx1

(57)
(58)

Prop. 3 tells us that µmin ∈ supp(σ̃ 2 ) (or equivalently σ̃µ2 min > 0), therefore, complementary
slackness and interchangeability imply:


1
1
α
1
(58)
e1 (σ 1 ∗ , µmin ) (10)
= − Eσ∗ [T (x)] + Fmax
1−
Fmax = U
p2
p1
p1
p2
α max (9) 1 min
⇐⇒Eσ∗ [T (x)] = F
=
T
(59)
p2
p2
Likewise, µ0 ∈ supp(σ̃ 2 ) therefore we can complete proving (ii):


1
1
α
(58)
e1 (σ 1 ∗ , µ0 ) (10)
= Eσ∗ [F (x)] − Eσ∗ [T (x)]
1−
Fmax = U
p2
p1
p1


1 max
α
α max
(59) 1
max
F
= F
1−
F
+
⇐⇒Eσ∗ [F (x)] =
p2
p1
p1 p2
p2

(60)

Similarly, x∗ ∈ supp(σ̃ 1 ) (or equivalently σ̃x1∗ > 0), therefore, complementary slackness and interchangeability imply:


1
1
α
1
(57)
µ
e2 (x∗ , σ 2 ∗ ) = −U
e1 (x∗ , σ 2 ∗ ) (10)
= −Eσ∗ [F ((x∗ ) )] + T (x∗ ) − Eσ∗ [C (µ)]
1−
Fmax = U
−
p2
p1
p1
p2
α max 1
(34)
max
= − (F
−Eσ∗ [C (µ)]) + F
− Eσ∗ [C (µ)]
p1
p2
which is equivalent to:









1
α
1
α
α
1
max
max
Eσ∗ [C (µ)] = 1 −
F
−
1−
F
= 1−
1−
Fmax
1−
p2
p1
p2
p1
p2
p1
Therefore, we obtain (iii) again:


α
1
(9)
Eσ∗ [C (µ)] = 1 −
Fmax = Fmax − Tmin
p1
p1
We can now deduce (iv):
(9)
e1 (σ 1 ∗ , σ 2 ∗ ) + 1 Eσ∗ [T (x)] − 1 Eσ∗ [C (µ)]
Eσ∗ [F (xµ )] = U
p2
 p1 


α
1
α
α max 1
(56),(59),(61) 1
max
=
F
−
1−
F
+
1−
Fmax
p2
p1
p1 p2
p2
p1
α max (9) 1
F
Tmin
=
=
p1 p2
p1 p2

(61)

32

Lastly, to show (i), we proceed as follows:




α
p1
α
p1
(56),(61) p1
max
1∗
2∗
e
1−
F
−
1−
Fmax = 0
U1 (σ , σ ) = p1 U1 (σ , σ ) − Eσ∗ [C (µ)] =
p2
p2
p1
p2
p1
∗
∗ (30)
e2 (σ 1 ∗ , σ 2 ∗ ) + p2 Eσ∗ [F (x)] − p2 Eσ∗ [T (x)]
U2 (σ 1 , σ 2 ) = p2 U
p1


α
α
(56),(59),(60)
max
max
F
+F
− Fmax = 0
=
− 1−
p1
p1
1∗

2 ∗ (29)


A.3. Proof of necessary conditions.
∗
∗
Proof of Lemma 3. Let us consider a NE σ ∗ = (σ 1 , σ 2 ) ∈ Σ. Since (σ̃ 1 , σ̃ 2 ) is also a NE
∗
(Prop. 3), then, by interchangeability, (σ 1 , σ̃ 2 ) is a NE as well. So, thanks to Thm. 1, we have
∗
∀x ∈ supp(σ 1 ), 0 = U1 (x, σ̃ 2 ) = α F (x) − T (x) where the first equality follows from (13). Therefore,
∗
∀x ∈ supp(σ 1 ), T (x) = α F (x). Since every path has a marginal transportation cost at least equal
to α, then the last equality entails that any flow in the support of a NE takes paths that induce a
marginal transportation cost equal to α.

∗
∗
∗
Proof of Proposition 4. Let us consider (σ 1 , σ 2 ) ∈ Σ. We know that (σ̃ 1 , σ 2 ) ∈ Σ too
∗
(where σ̃ 1 is defined in (11)). Then we can deduce that ∀µ ∈ supp(σ 2 ), 0 = U2 (σ̃ 1 , µ) =
F (x∗ − (x∗ )µ ) − C (µ), where the first equality is a consequence of (14). Therefore, the Max-Flow
∗
Min-Cut Theorem gives us: ∀µ ∈ supp(σ 2 ), C (µ) = F (x∗ − (x∗ )µ ) ≤ F (x∗ ) = C (µmin ).
2∗
Besides, since ∀µ ∈ supp(σ ), C (µ) = F (x∗ − (x∗ )µ ), then this means that the cost of conducting
an attack that is in the support of a NE is equal to the loss it induces to any min-cost max-flow.
Since the loss induced by an attack is never greater than the cost of the attack (see (31)), it means
that each edge disrupted by an attack in the support of a NE is saturated by every min-cost
max-flow (see the proof of Lemma 4).

Proof of Proposition 5. Consider a min-cut set E({S , T }). Given p1 > α and p2 > 1, one
†
†
†
can find a NE (σ 1 , σ 2 ) such that ∀(i, j) ∈ E({S , T }), 1{(i,j)} ∈ supp(σ 2 ).
∗
∗
∗
†
Consider a NE σ ∗ = (σ 1 , σ 2 ) ∈ Σ, we know by interchangeability that (σ 1 , σ 2 ) ∈ Σ. Therefore:



(14)
∗
∀(i, j) ∈ E({S , T }), U2 (σ 1 , 1{(i,j)} ) = 0 ⇐⇒ p2 Eσ∗ F x − x1{(i,j)} − C 1{(i,j)} = 0

 cij
⇐⇒ Eσ∗ F x − x1{(i,j)} =
p2
cij
⇐⇒ Eσ∗ [xij ] =
p2
∗

Now, suppose that σ 2 does not contain attacks that disrupt edges outside of E({S , T }). First,
notice that an edge e is disrupted if and only if it is attacked by at least one attack. Therefore:
X ∗
X
∗
Pσ∗ ({e is disrupted}) =
σµ2 1{µe =1} =
σµ2 .
µ∈A

′

′

{µ∈A | µe =1}

∗

Similarly, one can find a NE (σ 1 , σ 2 ) ∈ Σ such that ∀e ∈ E({S , T }), there is a flow xe ∈ supp(σ 1 )
that crosses E({S , T }) only at edge e and that takes paths of marginal transportation cost equal
′
∗
to α. We know by interchangeability that (σ 1 , σ 2 ) is also a NE. Therefore:
∗ (13)

∀e ∈ E({S , T }), U1 (xe , σ 2 ) = 0
µ
⇐⇒ p1 Eσ∗ [F ((xe ) )] − α F (xe ) = 0

33

⇐⇒

X

∗

µ

σµ2 F ((xe ) ) =

µ∈A

X

α
F (xe )
p1

X
α
∗
∗
µ
µ
σµ2 F ((xe ) ) +
σµ2 F ((xe ) ) = F (xe )
| {z }
| {z } p1
{µ∈A | µe =1}
{µ∈A | µe =0}
=0
=F(xe )
X
α
e
2∗
e
⇐⇒ F (x )
σµ = F (x )
p1
{µ∈A | µe =0}
X
X
α
∗
∗
=
σµ2 = 1 −
σµ2
⇐⇒
p1
{µ∈A | µe =0}
{µ∈A | µe =1}
X
α
2∗
=
σµ = Pσ∗ ({e is disrupted})
⇐⇒ 1 −
p1
⇐⇒

{µ∈A | µe =1}

Proof of Proposition 6.
for x0 :


Consider a NE σ = (σ , σ ) ∈ Σ. First, let us derive the bound

1
(15)
F (x∗ ) = Eσ∗ [F (x)] =
p2

∗

X

1∗

2∗

∗

σx1 F (x) ≤ F (x∗ )

x∈F \{x0 }

X

x∈F \{x0 }



∗
∗
σx1 = 1 − σx10 F (x∗ )

1
.
p2
Secondly, let us derive the bound for any min-cost max-flow x∗ :
∗

Therefore, σx10 ≤ 1 −

∗
1
(15)
F (x∗ ) = Eσ∗ [F (x)] = σx1∗ F (x∗ ) +
p2

X

∗

∗

σx1 F (x) ≥ σx1∗ F (x∗ )

x∈F \{x∗ }

1
.
p2
Thirdly, for any min-cut set attack µmin , we have:



 (17)
∗
α
1−
C µmin = Eσ∗ [C (µ)] = σµ2 min C µmin +
p1
∗

Therefore, σx1∗ ≤

X

∗

σµ2 C (µ)

µ∈A\{µmin }

|

{z

≥0

α
.
p1
Finally, we can derive a similar bound for µ0 :


X
 (17)
α
∗
1−
σµ2 C (µ)
C µmin = Eσ∗ [C (µ)] =
p1
µ∈A\{µ0 }
X
(21)


∗
∗
σµ2 = (1 − σµ2 0 ) C µmin
≤ C µmin
∗

Therefore, σµ2 min ≤ 1 −

}

µ∈A\{µ0 }

∗

Therefore, σµ2 0 ≤

α
.
p1



Proof of Proposition 7.
– First, let us prove that maxσ1 minσ2 U1 (σ 1 , σ 2 ) = 0 by directly exhibiting a maximinimizer.
(4)

∀(σ 1 , σ 2 ) ∈ ∆(F ) × ∆(A), U1 (σ 1 , σ 2 ) = p1 Eσ [F (xµ )] − Eσ [T (x)] ≥ −Eσ [T (x)]
| {z }
≥0

34

which is independent of σ 2 . Therefore: ∀σ 1 ∈ ∆(F ), minσ2 U1 (σ 1 , σ 2 ) ≥ −Eσ [T (x)].
Besides ∀σ 1 ∈ ∆(F ), U1 (σ 1 , µmin ) = −Eσ [T (x)]. Therefore:
∀σ 1 ∈ ∆(F ),

min U1 (σ 1 , σ 2 ) = −Eσ [T (x)] ≤ 0.

σ2 ∈∆(A)

This inequality tells us that maxσ1 minσ2 U1 (σ 1 , σ 2 ) ≤ 0. Now it is easy to see that x0 is a maximinimizer of U1 :
min U1 (σ 1 , σ 2 ) = min U1 (x0 , σ 2 ) = 0

max

σ1 ∈∆(F ) σ2 ∈∆(A)

(62)

σ2 ∈∆(A)

∗

∗

– Now, let us prove that minσ2 maxσ1 U1 (σ 1 , σ 2 ) ≤ 0 using the definition of a NE: let (σ 1 , σ 2 ) ∈ Σ,
∗
∗
∗
then: ∀σ 1 ∈ ∆(F ), 0 = U1 (σ 1 , σ 2 ) ≥ U1 (σ 1 , σ 2 ) where the equality follows from (13) and the
∗
inequality follows from (6). Therefore, maxσ1 U1 (σ 1 , σ 2 ) = 0. Then:
∗

max U1 (σ 1 , σ 2 ) ≤ max U1 (σ 1 , σ 2 ) = 0

min

σ2 ∈∆(A) σ1 ∈∆(F )

(63)

σ1 ∈∆(F )

– We can get the reverse inequality thanks to the following inequality: maxσ1 minσ2 U1 (σ 1 , σ 2 ) ≤
minσ2 maxσ1 U1 (σ 1 , σ 2 ) (inequality that is true for any function of two variables):
(62)

0 =

max

min U1 (σ 1 , σ 2 ) ≤ min

σ1 ∈∆(F ) σ2 ∈∆(A)

max U1 (σ 1 , σ 2 )

σ2 ∈∆(A) σ1 ∈∆(F )

(64)

Therefore, (63) and (64) lead to:
min

max U1 (σ 1 , σ 2 ) = 0

(65)

σ2 ∈∆(A) σ1 ∈∆(F )

– The proof for U2 is similar, but in this case µ0 is the maximinimizer of U2 .
∗
∗
– Let us prove that any NE of Γ is a minimaximizer: let (σ 1 , σ 2 ) ∈ Σ, then:
(65)

0 =

min

∗ (6)

∗

∗ (13)

max U1 (σ 1 , σ 2 ) ≤ max U1 (σ 1 , σ 2 ) = U1 (σ 1 , σ 2 ) = 0

σ2 ∈∆(A) σ1 ∈∆(F )

σ1 ∈∆(F )

∗

∗

Therefore, minσ2 maxσ1 U1 (σ 1 , σ 2 ) = maxσ1 U1 (σ 1 , σ 2 ), i.e., σ 2 is a minimaximizer of U1 .
∗
A similar argument tells us that σ 1 is a minimaximizer of U2 .

Appendix B: Proof of budget-constrained game.
B.1. Proof of P1’s budget.

Tmin
≤ b1 ≤ Tmin , b2 ≥ Fmax . Let us
Proof of Proposition 8. Suppose that p1 > α, p2 > 1,
p2
show that σ ∗ as defined in (24) and (25) is a NE.
(8)
α
Eσ [F (x)] − Eσ [T (x)] ≤ αEσ [F (x)] − αEσ [F (x)] = 0
p1




min
Tmin
b1 ∗
b1 ∗ (9) α
T
α
1∗
2∗
=
−
Besides: U1 (σ , σ ) = α
F
T
F (x∗ ) − F (x∗ ) = 0
min x
min x
p2 b1
p
b
p
p
T
T
2 1
2
2
Similarly:

µ 
 

min
∗
Tmin
b1 ∗
b1 ∗
(5) T
x
x
−
− Eσ [C (µ)]
F
F
E
∀σ 2 ∈ ∆(Ab2 ), U2 (σ 1 , σ 2 ) =
σ
b1
b1
Tmin
Tmin
∗

(4)

∀σ 1 ∈ ∆(Fb1 ), U1 (σ 1 , σ 2 ) = p1

(31)

= Eσ [F (x∗ − (x∗ )µ ) − C (µ)] ≤ 0


α
α
∗
1∗
2∗
∗
C (µmin ) = 0 thanks to the Max-Flow MinBesides: U2 (σ , σ ) = F (x ) − F (x ) − 1 −
p1
p1
∗
∗
Cut Theorem. Thus, (σ 1 , σ 2 ) is a NE.


35

B.2. Proof of P2’s budget.
nα
Proof of Proposition 9. Region III.a: if α < p1 <
and p2 > 1, then let us prove that
n−1
∗
∗
({x0 , x∗ }, {µ0 , µ1 , . . . , µn }) is the support of a NE (σ 1 , σ 2 ) where:
1
,
p2

1
p2


α
α
2∗
2∗
- ∀k ∈ J1, nK, σµk = 1 − , σµ0 = 1 − n 1 −
p1
p1
∗
∗
Let us first show (i) that σ 1 and σ 2 are probability distributions. Then let us prove (ii)
∗
∗
∗
∗
U1 (x0 , σ 2 ) = U1 (x∗ , σ 2 ) = 0 and (iii) ∀x ∈ F , U1 (x, σ 2 ) ≤ 0. Similarly we prove (iv) U2 (σ 1 , µ0 ) =
∗
∗
∗
U2 (σ 1 , µ1 ) = · · · = U2 (σ 1 , µn ) = 0 and (v) ∀µ ∈ A, U2 (σ 1 , µ) ≤ 0
∗

- σx10 = 1 −

∗

σx1∗ =

∗

∗

(i) First, let us prove that σ 1 and σ 2 are probability distributions:
∗
σ 1 is clearly a probability distribution since p2 > 1.
α
∗
- p1 > α so σµ2 k = 1 − ≥ 0
p1


nα
α
nα
p1 − np1 + nα (n − 1)( n−1 − p1 )
∗
- σµ2 0 = 1 − n 1 −
=
≥ 0 because p1 ≤
=
p1
p1
p1
n−1
X ∗
σµ2 = 1
µ∈A
∗

So σ 2 is a probability distribution.
∗
(ii) Let us prove that U1 (x0 , σ 2 ) = 0.
∗
Since ∀µ ∈ A, u1 (x0 , µ) = 0, then U1 (x0 , σ 2 ) = 0.
∗
Now, let us prove that U1 (x∗ , σ 2 ) = 0.


n 



X
α 
µk
1−
U1 (x , σ ) =
− T (x∗ )
p1 F (x∗ )
p
k=1
 

 1



α
µ0
− T (x∗ )
p1 F (x∗ )
+ 1−n 1−
p1
n


X
(9)
µk
= (p1 − α)
+ (p1 − n(p1 − α)) F (x∗ ) − α F (x∗ )
F (x∗ )
∗

2∗

k=1

We can decompose x∗ into {x1 , . . . , xN } where each xl is the part of x∗ that goes through
el of the min-cut set E({S , T }):
X
x∗λ
∀l ∈ J1, N K, ∀(i, j) ∈ E , xlij =
e

λ∈Λijl

e

where Λijl = {λ ∈ Λ | (i, j) ∈ λ and el ∈ λ} is the set of paths that go through (i, j) and el .
Therefore:


n X
n
N
 X

X
 k
k
∗ µ
l µ
=
F (x )
F x
k=1

k=1 l=1

Moreover, only one of the µk affects xl . Therefore we get:


n
X
 k

l µ
F x
= (n − 1) F xl
k=1

36

If we sum over l, we get:


n
N X
n
N
 X

X
X
µk

µk
=
F (x∗ )
F xl
= (n − 1)
F xl = (n − 1) F (x∗ )
k=1

l=1 k=1

l=1

which leads to:

∗

U1 (x∗ , σ 2 ) = (p1 − α)(n − 1) F (x∗ ) + (p1 − n(p1 − α)) F (x∗ ) − α F (x∗ ) = 0
∗

(iii) Now, let us prove that ∀x ∈ F , U1 (x, σ 2 ) ≤ 0.

n 

 k
X
∗
α 
∀x ∈ F , U1 (x, σ 2 ) =
1−
p1 F xµ − T (x)
p
k=1
 

 1

 0
α
p1 F xµ − T (x)
+ 1−n 1−
p1
n
 k
X
F xµ + (p1 − n(p1 − α)) F (x) − T (x)
= (p1 − α)
(8)

≤ (p1 − α)

k=1
n
X
k=1

Likewise:

 k
F xµ + (p1 − n(p1 − α)) F (x) − α F (x)

n
 k
X
F xµ = (n − 1) F (x). Therefore:
k=1

∗

U1 (x, σ 2 ) ≤ ((p1 − α)(n − 1) + (p1 − n(p1 − α)) − α) F (x) = 0
∗

So σ 1 is a BR for P1.
1∗
(iv) Similarly, let us prove that U2 (σ
, µ0 ) = 0.
∗
0
Since ∀x ∈ F , u2 (x, µ0 ) = p2 F x − xµ − C (µ0 ) = 0, then U2 (σ 1 , µ0 ) = 0
∗

Now, let us prove that ∀k ∈ J1, nK, U2 (σ 1 , µk ) = 0.


 (32)
∗
k
∀k ∈ J1, nK, U2 (σ 1 , µk ) = F x∗ − (x∗ )µ − C µk = 0
∗

(v) Lastly, let us prove that ∀µ ∈ A, U2 (σ 1 , µ) ≤ 0.

(31)

∗

∀µ ∈ A, U2 (σ 1 , µ) = F (x∗ − (x∗ )µ ) − C (µ) ≤ 0
∗

∗

∗

Thus, σ 2 is a BR for P2. Therefore, (σ 1 , σ 2 ) ∈ Σ.
nα
and p2 > 1, then let us prove that ({x0 , x∗ }, {µ1 , . . . , µn , µmin }) is the
n∗ − 1
∗
support of a NE (σ 1 , σ 2 ) where:
Region III.b: if p1 >

1
1
∗
, σx1∗ =
p2
p2
α
nα
∗
∗
- σµ2 k =
∀k ∈ J1, nK, σµ2 min = 1 −
p1 (n − 1)
p1 (n − 1)
∗
∗
Let us first prove (i) that σ 1 and σ 2 are probability distributions. Then let us prove (ii)
∗
∗
∗
∗
U1 (x0 , σ 2 ) = U1 (x∗ , σ 2 ) = 0 and (iii) ∀x ∈ F , U1 (x, σ 2 ) ≤ 0. Similarly we prove (iv) U2 (σ 1 , µ1 ) =
∗
∗
∗
· · · = U2 (σ 1 , µn ) = U2 (σ 1 , µmin ) = 0 and (v) ∀µ ∈ A, U2 (σ 1 , µ) ≤ 0.
∗

- σx10 = 1 −

37
∗

∗

(i) First, let us prove that σ 1 and σ 2 are probability distributions:
∗
σ 1 is clearly a probability distribution since p2 > 1.
α
∗
- σµ2 k =
≥0
p1 (n − 1)


1
nα
nα
nα
2∗
=
p1 −
≥ 0 because p1 ≥
- σµmin = 1 −
p1 (n − 1) p1
n−1
n−1
X ∗
σµ2 = 1
µ∈A
2∗

So σ is a probability distribution.
∗
(ii) Let us prove that U1 (x0 , σ 2 ) = 0.
∗
Since ∀µ ∈ A, u1 (x0 , µ) = 0, then U1 (x0 , σ 2 ) = 0.
∗
2∗
Now let us prove that U1 (x , σ ) = 0.
∗





α
µk
− T (x∗ )
p1 F (x∗ )
p1 (n − 1)
k=1






min
αn


∗ µ
+ 1−
− T (x∗ )
p1 F (x )
p1 (n − 1)
|
{z
}
=0
n
α X  ∗ µk 
(9)
=
− α F (x∗ )
F (x )
n − 1 k=1

2∗

U1 (x , σ ) =

n
X

As previously, one can show that
∗

U1 (x∗ , σ 2 ) =



k
∗ µ
= (n − 1) F (x∗ ), which leads to:
F
(x
)
k=1

Pn

α
(n − 1) F (x∗ ) − α F (x∗ ) = 0
n−1
∗

(iii) Now let us prove that ∀x ∈ F , U1 (x, σ 2 ) ≤ 0.
∗



 k
α
p1 F xµ − T (x)
p (n − 1)
k=1 1






αn


µmin
+ 1−
− T (x)
 p1 F x
p1 (n − 1)
| {z }
=0
n
α X  µk 
− T (x)
=
F x
n − 1 k=1

U1 (x, σ 2 ) =

Likewise:

n
X

n
 k
X
F xµ = (n − 1) F (x).
k=1

Therefore:

∗

(8)

U1 (x, σ 2 ) ≤
∗

α
(n − 1) F (x) − α F (x) = 0
n−1

So σ 1 is a BR for P1.
∗
(iv) Similarly, let us prove that U2 (σ 1 , µmin ) = 0.




 1 

min
∗
1
p2 × 0 − C µmin +
− C µmin
p2 F x∗ − (x∗ )µ
U2 (σ 1 , µmin ) = 1 −
p2
p2

= F (x∗ ) − C µmin = 0

38

where the last equality follows from the Max-Flow Min-Cut Theorem.
∗
Now, let us prove that ∀k ∈ J1, nK, U2 (σ 1 , µk ) = 0





 1 
k
1
1∗
k
p2 F x∗ − (x∗ )µ − C µk
p 2 × 0 − C µk +
∀k ∈ J1, nK, U2 (σ , µ ) = 1 −
p2

 p2

k (32)
∗
∗ µk
−C µ = 0
= F x − (x )
∗

∗

(v) We already proved in Region III.a that: ∀µ ∈ A, U2 (σ 1 , µ) ≤ 0. Thus σ 2 is a BR for P2.
∗
∗
Therefore, (σ 1 , σ 2 ) ∈ Σ.

Proof of Proposition 10. We want to solve the optimization problem given in (27). Notice
that this optimization problem can be written as follows:
min

max

σ2 ∗ ∈Σp1 µ∈supp(σ2 ∗ )

C (µ) = min

max

min

2∗
n∈J1,N K σ2 ∗ ∈Σn
p µ∈supp(σ )

C (µ) .

(66)

1

Let us first start by finding n∗ ∈ arg minn∈J1,N K minσ2 ∗ ∈Σnp maxµ∈supp(σ2 ∗ ) C (µ). There are two
1
cases to consider:
– Case 1: for

nα
∗
∗
< p1 , then ∀σ 2 ∈ Σnp1 , supp(σ 2 ) = {µ1 , . . . , µn } ∪ {µmin } so:
n−1

∗
∀σ 2 ∈ Σnp1 ,
max ∗ C (µ) = C µmin = Fmax .
µ∈supp(σ2 )

nα
max ∗ C (µ) = Fmax .
< p1 , then min
2 )
n−1
µ∈supp(σ
σ2 ∗ ∈Σn
p1
nα
∗
∗
≥ p1 , then ∀σ 2 ∈ Σnp1 , supp(σ 2 ) = {µ1 , . . . , µn } ∪ {µ0 } so:
– Case 2: for
n−1

∗
∀σ 2 ∈ Σnp1 ,
max ∗ C (µ) = max C µk .
Therefore, if

µ∈supp(σ2 )

k∈J1,nK

For any partition {µ1 , . . . , µn } of µmin , we note {P1 , . . . , Pn } the corresponding partition of the
min-cut set {e1 , . . . , eN } of capacities c1 , . . . , cN . Then the cost of each µk is equal to the sum of
the capacities of the edges it disrupts, i.e.:
 X
∀k ∈ J1, nK, C µk =
cl
el ∈Pk

Therefore:
∗

∀σ 2 ∈ Σnp1 ,

max

µ∈supp(σ2 ∗ )

C (µ) = max

k∈J1,nK

X

cl .

el ∈Pk

One can see that the problem is equivalent to finding a partition {P1 , . . . , Pn } of the min-cut set
such that the maximum sum of the capacities of the edges constituting each element of the partition
is minimized. n still being fixed, we want to solve the following bilevel optimization problem:
X
cl
ψ(n) := min max
{P1 ,...,Pn } k∈J1,nK

el ∈Pk

Now, let us argue that the optimal value of the previous bilevel problem, ψ(n), does not increase
when partitioning the min-cut set into more pieces, i.e., if n′ > n, then, ψ(n′ ) ≤ ψ(n).

39
∗
∗
Indeed, let us consider n ≤ N − 1, and
P let us note {P1 , . . . , Pn } an optimal partitioning of the
min-cut set of size n: ψ(n) = maxk∈J1,nK el ∈P ∗ cl .
k

Since n ≤ N − 1, then at least one of the Pk∗ contains at least two edges (Dirichlet’s principle).
Without loss of generality, let us assume that Pn∗ contains at least two edges. Let us denote ek0
one of the edges of Pn∗ .
Now, let us consider {P1 , . . . , Pn+1 } a partition of the min-cut set of size n + 1 such that ∀k ∈
J1, n − 1K, Pk = Pk∗ , Pn = Pn∗ \{ek0 } and Pn+1 = {ek0 }.
P
P
P
Notice that ck0 ≤ el ∈Pn∗ cl and el ∈Pn cl ≤ el ∈Pn∗ cl .
Thus, we constructed a partition of the min-cut set of size n + 1, such that:
X
X
cl ≤ max
cl = ψ(n)
ψ(n + 1) ≤ max
k∈J1,n+1K

k∈J1,nK

el ∈Pk

el ∈Pk∗

Therefore, ψ is a non-increasing function, which means that in (66), we need to increase n as
nα
much as possible. However, let us not forget that we are in the case where
≥ p1 .
n−1


nα
∗
Therefore, the optimal partitioning size in this case is n = max n ∈ J1, N K |
≥ p1 =
n−1
 

p1
,N .
min
p1 − α
Finally, notice that for any partition {P1 , . . . , Pn }, we have
∀k ∈ J1, nK,

X

el ∈Pk

cl ≤

N
X

cl = Fmax ,

l=1

where the equality follows from the Max-Flow Min-Cut Theorem.
This implies that ψ(n∗ ) ≤ Fmax , which is the optimal value of the original problem in Case 1.
Therefore n∗ is the optimal partitioning size.
Now that we know n∗ , we can derive an integer-programming problem that provides us with an
optimal partition of µmin .
minimize

z

subject to z ≥

N
X

cl ylk , ∀k ∈ J1, n∗ K

l=1

∗

n
X

ylk = 1, ∀l ∈ J1, N K

k=1

ylk ∈ {0, 1}, ∀(l, k) ∈ J1, N K × J1, n∗ K.
One can see that this integer-programming problem gives the optimal value ψ(n∗ ) and an optimal
way of partitioning the min-cut set thanks to the ylk . Indeed, for every
edge el , and any set Pk ,
Pn∗
ylk = 1 means that edge el goes in set Pk . Thanks to the constraint k=1 ylk = 1, ∀l ∈ J1, N K, each
edge el goes in exactly one set Pk , thus creating a partition of the min-cut set.
Then, from this partition of the min-cut set, one can partition µmin accordingly, and use Prop.
9 in order to derive the corresponding probabilities.

Acknowledgments This work was supported in part by FORCES (Foundations Of Resilient
CybEr-Physical Systems), which receives support from the National Science Foundation (NSF
award numbers CNS-1238959, CNS-1238962, CNS-1239054, CNS-1239166), NSF CAREER award
CNS-1453126, and the AFRL LABLET - Science of Secure and Resilient Cyber-Physical Systems
(Contract ID: FA8750-14-2-0180, SUB 2784-018400).

40
References
[1] Acemoglu, Daron, Azarakhsh Malekian, Asuman Ozdaglar. 2013. Network security and contagion. Working Paper 19174, National Bureau of Economic Research. doi:10.3386/w19174. URL
http://www.nber.org/papers/w19174.
[2] Adler, Ilan, Constantinos Daskalakis, Christos H. Papadimitriou. 2009. A note on strictly competitive
games. Stefano Leonardi, ed., Internet and Network Economics, 5th International Workshop, WINE
2009, Rome, Italy, December 14-18, 2009. Proceedings, Lecture Notes in Computer Science, vol. 5929.
Springer, 471–474.
[3] Alan Washburn, Kevin Wood. 1995. Two-person zero-sum games for network interdiction. Operations
Research 43(2) 243 – 251.
[4] Avenhaus, Rudolf, Morton John Canty. 2009. Inspection games. Robert A. Meyers, ed., Encyclopedia
of Complexity and Systems Science. Springer, 4855–4868. doi:10.1007/978-0-387-30440-3 287. URL
http://dx.doi.org/10.1007/978-0-387-30440-3_287.
[5] Avenhaus, Rudolf, Bernhard Von Stengel, Shmuel Zamir. 2002. Inspection games. R.J. Aumann, S. Hart,
eds., Handbook of Game Theory with Economic Applications, vol. 3, chap. 51. Elsevier, 1947–1987. URL
https://ideas.repec.org/h/eee/gamchp/3-51.html.
[6] Ball, Michael O., Bruce L. Golden, Rakesh V. Vohra. 1989. Finding the most vital arcs in a network.
Oper. Res. Lett. 8(2) 73–76.
[7] Baykal-Gürsoy, Melike, Zhe Duan, H. Vincent Poor, Andrey Garnaev. 2014. Infrastructure security
games. European Journal of Operational Research 239(2) 469–478.
[8] Bertsimas, Dimitris, Ebrahim Nasrabadi, James B. Orlin. 2013. On the power of randomization in
network interdiction. CoRR abs/1312.3478. URL http://arxiv.org/abs/1312.3478.
[9] Bertsimas, Dimitris, Ebrahim Nasrabadi, Sebastian Stiller. 2013. Robust and adaptive network flows.
Operations Research 61(5) 1218–1242.
[10] Cormican, Kelly J., David P. Morton, R. Kevin Wood. 1998. Stochastic Network Interdiction. Operations
Research 46(2).
[11] Daskalakis, Constantinos, Paul W. Goldberg, Christos H. Papadimitriou. 2009. The complexity of
computing a nash equilibrium. SIAM Journal on Computing 39(1) 195–259. doi:10.1137/070699652.
URL http://dx.doi.org/10.1137/070699652.
[12] Edmonds, Jack, Richard M. Karp. 1972.
Theoretical improvements in algorithmic efficiency
for network flow problems.
J. ACM 19(2) 248–264.
doi:10.1145/321694.321699.
URL
http://doi.acm.org/10.1145/321694.321699.
[13] Ford, L. R., D. R. Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics
8 399–404.
[14] Goldberg, Andrew V, Robert E Tarjan. 1989. Finding minimum-cost circulations by canceling negative
cycles. Journal of the ACM (JACM) 36(4) 873–886.
[15] Goyal, Sanjeev, Adrien Vigier. 2014. Attack, defence, and contagion in networks. Review of Economic
Studies 81(4) 1518–1542.
[16] Gueye, Assane, Jean C. Walrand, Venkat Anantharam. 2010. Design of network topology in an adversarial environment. Tansu Alpcan, Levente Buttyán, John S. Baras, eds., Decision and Game Theory
for Security - First International Conference, GameSec 2010, Berlin, Germany, November 22-23, 2010.
Proceedings, Lecture Notes in Computer Science, vol. 6442. Springer, 1–20.
[17] Hong, Sunghoon, Myrna Wooders. 2010. Strategic Network Interdiction. Vanderbilt University Department of Economics Working Papers 1010, Vanderbilt University Department of Economics. URL
http://ideas.repec.org/p/van/wpaper/1010.html.
[18] Kalai, Ehud, Eitan Zemel. 1982. Totally balanced games and games of flow. Mathematics of Operations
Research 7(3) 476–478. doi:10.1287/moor.7.3.476. URL http://dx.doi.org/10.1287/moor.7.3.476.
[19] Laszka, Aron, Assane Gueye. 2013. Quantifying network topology robustness under budget constraints:
General model and computational complexity. Sajal K. Das, Cristina Nita-Rotaru, Murat Kantarcioglu,

41
eds., Decision and Game Theory for Security - 4th International Conference, GameSec 2013, Fort
Worth, TX, USA, November 11-12, 2013. Proceedings, Lecture Notes in Computer Science, vol. 8252.
Springer, 154–174.
[20] Neumann, John. 1928. Zur theorie der gesellschaftsspiele. Mathematische Annalen 100(1) 295–320.
[21] Neumayer, S., G. Zussman, R. Cohen, E. Modiano. 2008. Assessing the impact of geographically
correlated network failures. Military Communications Conference, 2008. MILCOM 2008. IEEE . 1–6.
doi:10.1109/MILCOM.2008.4753111.
[22] Ratliff, H. Donald, G. Thomas Sicilia, S. H. Lubore. 1975. Finding the n most vital links
in flow networks.
Management Science 21(5) 531–539.
doi:10.1287/mnsc.21.5.531.
URL
http://dx.doi.org/10.1287/mnsc.21.5.531.
[23] Sullivan, Kelly M., J. Cole Smith. 2014. Exact algorithms for solving a euclidean maximum
flow network interdiction problem.
Networks 64(2) 109–124.
doi:10.1002/net.21561.
URL
http://dx.doi.org/10.1002/net.21561.
[24] Szeto, W.Y. 2013. Routing and scheduling hazardous material shipments: Nash game approach. Transportmetrica B: Transport Dynamics 1(3) 237–260.
[25] Wollmer, R. 1964. Removing Arcs from a Network. Operations Research 12(6) 934–940.
[26] Wood, R. Kevin. 1993. Deterministic network interdiction. Mathematical and Computer Modelling
17(2) 1 – 18.

