# Computing a Best Response against a Maximum Disruption Attack

Àlvarez, C. and Messegué, A

###### Abstract

Inspired by scenarios where the strategic network design and defense or
immunisation are of the central importance, Goyal et al. [3] defined a new
Network Formation Game with Attack and Immunisation. The authors showed that
despite the presence of attacks, the game has high social welfare properties
and even though the equilibrium networks can contain cycles, the number of
edges is strongly bounded. Subsequently, Friedrich et al. [10] provided a
polynomial time algorithm for computing a best response strategy for the
maximum carnage adversary which tries to kill as many nodes as possible, and
for the random attack adversary, but they left open the problem for the case
of maximum disruption adversary. This adversary attacks the vulnerable region
that minimises the post-attack social welfare.

In this paper we address our efforts to this question. We can show that
computing a best response strategy given a player $u$ and the strategies of
all players but $u$, is polynomial time solvable when the initial network
resulting from the given strategies is connected. Our algorithm is based on a
dynamic programming and has some reminiscence to the knapsack-problem,
although is considerably more complex and involved.

##  1 Introduction

Strategic network formation arises in settings where agents receive some
benefit from being connected to other agents, but also incur costs due to the
creation of links. We focus our attention on the network formation game with
attack and immunisation defined in [3] which is an extension of the well-known
reachability model introduced by Bala and Goyal in [2]. This extension
incorporates a strong adversary and immunisation. The adversary attacks and
destroys a node of the network and then this attack is spread virus-like to
neighboring non-immunised nodes and destroys them as well. Besides deciding
the subset of nodes to whom to buy links, each player has to decide whether
she wants to buy immunisation against eventual attacks.

The benefit of a player is defined as the expected size of her connected
component post-attack and her cost depends on the number of links bought by
the player and the cost of being immunised if it is the case.

In [3] the authors provide structural results for their model and raise the
open problem of settling the complexity of computing a best response strategy.

The existence of an efficient best response algorithm for a network formation
game is in general rare. For related network formation models, e.g. [4, 5, 6,
7, 8, 9, 1] where players strive for a central position in the network, it has
been shown that the best response problem is indeed NP-hard.

Related results. Lenzner et al. in [10] showed that the natural model defined
by Goyal et al. in [3] is one of the few examples of a tractable realistic
model for strategic network formation and thereby answer an open question by
these authors. They provided a polynomial time algorithm for computing a best
response strategy for the _maximum carnage adversary_ which tries to kill as
many nodes as possible, and for the natural variant which employs _random
attack adversary_. Settling the complexity of computing a best response
strategy against _maximum disruption adversary_ was left as an open problem in
[10]. This adversary attacks the vulnerable region that minimises the post-
attack social welfare. Notice that a naive approach to calculate the best
response for a player would consider all $2^{n}$ possible subsets of links as
well as the possibility of to be or not immunised. The algorithm presented in
[10] circumvents this combinatorial explosion computing first a potential
subset of vulnerable candidates using a dynamic programming if the node is not
immunised, or a greedy programming if the node being immunised. And second,
when immunised nodes are considered, the given network is simplified in order
to be tractable by a dynamic programming approach.

Our Contribution. We assume that the outcome network of the strategies of all
players but the one of who wants to compute a best response, is connected.
That is, the initial network after dropping any strategy for player $u$ is
connected. Our main result is to show that in that situation the best response
problem of $u$ given the strategies of all the rest of players can be computed
in polynomial time for the case of maximum disruption adversary.

The key ideas that lead us to prove it are the following:

  1. 1.

The definition of what we call _delta value_. This parameter allow us to
characterise the set of nodes attacked by the adversary. Besides this, it is
also crucial the definition of our _meta-tree_. This tree-like structure
underlying any configuration from the model conducts to a first simplification
on how can we think of a potential best response.

  2. 2.

The definition of _restricted strategy_ and the corresponding _restricted
utility_. Since we want to compute efficiently a best response for a given
player, we partition the set of potential best responses into a collection of
mutually disjoint subsets depending on different parameters whose values are
upper bounded by a polynomial of the number of players. Hence, if we know how
to find a strategy achieving the maximum restricted utility in each subset,
then we can select among them the one having the maximum utility as a best
response for the original problem. Moreover, we show that the restricted
utility in a sub-tree $T$ can be expressed in terms of the restricted
utilities of the strategies restricted to each of the its sub-trees of
$T_{1},...,T_{k}$. We also define the natural concept of restricted strategy
having the maximum possible restricted utility, named as _restricted BR-
strategy_. Analogously to the restricted utility, we can exploit the structure
of the meta-tree.

  3. 3.

Finally, two recurrence relations corresponding to the restricted BR-
strategies and their respective restricted utilities can be given using the
previous characterisations.

Since the parameters of such recurrences can take a polynomial number (in $n$,
the number of players) of possible values taking at most polynomial values (in
$n$), then we can conclude that the Best Response problem is polynomial time
computable using a dynamic programming approach.

Organisation of the paper. In Section 2 we introduce the model and we provide
some extra definitions that will be fundamental to obtain our main result. In
Section 3 we introduce the concepts of _restricted strategy_ and _restricted
utility_ and we show how to characterise recursively the restricted utility
exploiting the structure of the meta-tree, breaking the original problem into
easier sub-problems to solve. In Section 4, we consider the natural concept of
restricted strategy having the maximum possible restricted utility, which we
call _restricted BR-strategy_ and we show how to express the utility of a
restricted BR-strategy recursively. Finally, in Section 5 we define two
recurrence relations corresponding to the restricted BR-strategies and their
respective restricted utilities that allow us to solve the Best Response
problem in polynomial time using a dynamic programming approach.

##  2 Best Response Strategies against a Maximum Disruption Adversary

We start introducing the model as a strategic game following the definitions
given in [10, 2].

First of all, we consider $N=\left\\{1,...,n\right\\}$ the set of the $n$
players or agents that correspond to the nodes of the network. We use the
terms player, node or agent interchangeably. Each player then buy links at
price $\alpha>0$ to the other players and can buy immunisation at price
$\beta>0$, where $\alpha$ and $\beta$ are prefixed parameters of the model. We
denote by $s_{v}=(S_{v},i_{v})$ the _strategy_ of player $v$ where
$S_{v}\subseteq N\setminus\left\\{v\right\\}$, the _link-strategy_ , is the
subset of players to which node $v$ buys links and
$i_{v}\in\left\\{0,1\right\\}$, the _immunisation-value_ , is the value of
player $v$ that indicates whether $v$ has bought immunisation.

The _strategy profile_ , $\mathbb{s}=(s_{1},...,s_{n})$, is obtained
considering the strategies of all the players where $s_{v}=(S_{v},i_{v})$ for
each $v\in N$. Then any strategy profile $\mathbb{s}$ gives place to the
undirected graph $G(\mathbb{s})=(N,\cup_{v\in N}\cup_{w\in
S_{v}}\left\\{(v,w)\right\\})$. Notice that the immunisation-values for each
player induce a partition of the players into two sets which are
$\mathcal{I},\mathcal{U}$ the immunised and the vulnerable set of players,
respectively.

Once the network $G(\mathbb{s})$ is formed an adversary attacks a vulnerable
player according to a strategy previously known by the players and such attack
spreads through the network reaching all the vulnerable nodes that can be
reached with a path of vulnerable nodes from the node that the adversary has
attacked. The set of vulnerable nodes that the adversary can attack, the set
of _target nodes_ , is denoted as $A(\mathbb{s})$. Then,
$CC_{v}(a,\mathbb{s})$ is the connected component that can be reached from $v$
after the adversary attacks the player $a$ given that the players have adopted
the respective strategies from $\mathbb{s}$. With this notation then the
utility of a player $v$ is defined as

$U_{v}(\mathbb{s})=-\alpha|S_{v}|-i_{v}\beta+\frac{1}{|A(\mathbb{s})|}\sum_{a\in
A(\mathbb{s})}|CC_{v}(a,\mathbb{s})|$

In this way we then define the _social welfare_ as $U(\mathbb{s})=\sum_{v\in
N}U_{v}(\mathbb{s})$.

In [2] the authors propose three distinct kind of adversaries:

  1. 1.

The _maximum carnage_ adversary selects with uniform probability any of the
largest regions of contiguous vulnerable nodes and then attacks with uniform
probability any of its vulnerable nodes.

  2. 2.

The _random attack_ adversary attack with uniform probability any vulnerable
node.

  3. 3.

The _maximum disruption_ adversary attacks with uniform probability any
vulnerable node from the regions minimising the post-attack social welfare.

In this paper we deal with the maximum disruption adversary. Our aim is to
show that a _best response_ for a given player $u$ from $N$ is polynomial time
computable. Therefore, given the tuple of the strategies of all the players
except $u$, noted as $\mathbb{s}_{-u}$, we want to compute in polynomial time
a strategy $(S,i)$ for $u$ such that if $\mathbb{s}_{u}=(S,i)$ then
$U_{u}(\mathbb{s})$ has maximum value among all such possible strategies
$(S,i)$.

For this reason it is more convenient to assume that we are given
$\mathbb{s}_{-u}$ and, for any strategy $(S,i)$ for player $u$ we denote as
$G(S,i)$ the corresponding undirected network after $u$ has adopted strategy
$(S,i)$. Then, $\mathcal{U}[G(S,i)]$ and $\mathcal{I}[G(S,i)]$ are the
vulnerable and immunised nodes from $G(S,i)$, respectively.

We also define in a similar way $A(S,i)$, the set of target regions from
$G(S,i)$ that the adversary attacks and $CC_{z}(a,S,i)$ is the connected
component containing $z\in V(G(S,i))$ after the adversary attacks $a$ given
that the strategy for $u$ is $(S,i)$. Then $U(u,S,i)$ is the utility of $u$
given that the strategy for $u$ is $(S,i)$:

$U(u,S,i)=-\alpha|S|-i\cdot\beta+\frac{1}{|A(S,i)|}\sum_{a\in
A(S,i)}|CC_{u}(a,S,i)|$

Finally, it is also useful to consider the following definition. For each node
$z\in\mathcal{U}(G(S,i))$ we define the _delta value_ of $z$ with respect the
strategy $(S,i)$, noted as $\Delta(z,S,i)$, to be the sum of the squares of
the size of the distinct connected components that we obtain after removing
the node $z$ together with all vulnerable nodes connected to $z$ via a path of
vulnerable nodes in $G(S,i)$. More specifically:

$\Delta(z,S,i)=\sum_{t\in V(G)}|CC_{t}(z,S,i)|^{2}$

Then we define:

$\Delta(S,i)=\min_{z\in\mathcal{U}[G(S,i)]}\Delta(z,S,i)$

Next we provide the very first result that allow us to understand how the
maximum disruption adversary behaves. More precisely, we see that the subset
of attacked nodes by the maximum disruption adversary are precisely the
vulnerable nodes that minimise their corresponding delta value:

######  Proposition 2.1.

$A(S,i)=\left\\{a\in\mathcal{U}(G(S,i))\mid\Delta(a,S,i)=\Delta(S,i)\right\\}$

###### Proof.

Let $G=G(S,i)$, (or $G=G(\mathbb{s})$ with $\mathbb{s}_{u}=(S,i)$) and let
$A\subseteq V(G)$ with $A\neq\emptyset$ be a subset of nodes from $G$. Then:

$\frac{1}{|A|}\sum_{v\in V(G)}\sum_{a\in
A}|CC_{v}(a,S,i)|=\frac{1}{|A|}\sum_{a\in A}\sum_{v\in
V(G)}|CC_{v}(a,S,i)|=\frac{1}{|A|}\sum_{a\in A}\Delta(a,S,i)\geq\Delta(S,i)$

With equality iff
$A\subseteq\left\\{a\in\mathcal{U}[G]\mid\Delta(a,S,i)=\Delta(S,i)\right\\}$.

Therefore, the social welfare of $G=G(S,i)$, computed adding up the utilities
$U_{v}(\mathbb{s})$ for each agent $v\in V(G)$, given that the adversary
attacks the subset of nodes $A$ satisfies the next inequality:

$-\alpha|E(G)|-\beta|\mathcal{I}(G)|+\frac{1}{|A|}\sum_{v\in V(G)}\sum_{a\in
A}|CC_{v}(a,S,i)|\geq-\alpha|E(G)|-\beta|\mathcal{I}(G)|+\Delta(S,i)$

This allows us to deduce that the subset of nodes attacked by the maximum
disruption adversary is exactly the subset of vulnerable nodes $a$ from $G$
such that $\Delta(a,S,i)=\Delta(S,i)$ which is what we wanted to see. ∎

###  2.1 The meta-graph $G^{\prime}$

One of the first natural properties of a best response of a player $u$ is that
$u$ buys at most one link to a specific region of contiguous vulnerable or
immunised nodes. Let us introduce the concept of _meta-graph_ , that helps us
to prove that this is indeed true.

######  Definition 2.2.

Given a graph $G=G(S,i)$ the corresponding _meta-graph_
$G^{\prime}=G^{\prime}(S,i)$ is an undirected graph defined as follows:

(i) The set of vertices of $G^{\prime}$, called _meta-nodes_ are exactly the
maximally connected components of $\mathcal{U}[G]$ and $\mathcal{I}[G]$. More
precisely, given a node $w\in V(G)$ the corresponding meta-node containing $w$
in $G=G(S,i)$ is denoted by $W(w,S,i)$. Then, the set of immunised and
vulnerable meta-nodes are denoted by $\mathcal{I}[G^{\prime}]$ and
$\mathcal{U}[G^{\prime}]$, respectively.

(ii) The set of edges of $G^{\prime}$ are exactly the pair of meta-nodes
$V_{1}V_{2}$ such that there exist nodes $v_{1},v_{2}\in V(G)$ such that
satisfy $v_{1}\in V_{1}$, $v_{2}\in V_{2}$ and $v_{1}v_{2}\in E(G)$.

Once the meta-graph has been introduced we consider the meta-node containing
$u$, $W(u,S,i)\in V(G^{\prime})$ which, depending on whether $u$ buys
immunisation, is either a meta-node from $\mathcal{I}[G^{\prime}]$ or from
$\mathcal{U}[G^{\prime}]$. Now we take a look to a property that allows to
compare the utility of distinct strategies given that there are some
similitudes in the subsets $CC_{u}(v,\cdot,i)$ and the values
$\Delta(v,\cdot,i)$ with $v\in\mathcal{U}[G]$.

######  Lemma 2.3.

Let $(S,i),(S^{\prime},i)$ be two strategies for $u$. If for every
$v\in\mathcal{U}[G]$, $CC_{u}(v,S,i)=CC_{u}(v,S^{\prime},i)$ and
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$, then
$U(u,S,i)-U(u,S^{\prime},i)=-\alpha\left(|S|-|S^{\prime}|\right)$.

###### Proof.

If $\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ for every $v\in\mathcal{U}[G]$ then
$A(S,i)=A(S^{\prime},i)$. If, moreover, $CC_{u}(v,S,i)=CC_{u}(v,S^{\prime},i)$
for every $v\in\mathcal{U}[G]$ then, in particular,
$CC_{u}(v,S,i)=CC_{u}(v,S^{\prime},i)$ for every $v\in A(S,i)=A(S^{\prime},i)$
and from here:

$\frac{1}{|A(S,i)|}\sum_{a\in
A(S,i)}|CC_{u}(a,S,i)|=\frac{1}{|A(S^{\prime},i)|}\sum_{a\in
A(S^{\prime},i)}|CC_{u}(a,S^{\prime},i)|$

Then, the conclusion is clear using the definition of the utility
$U(u,\cdot,i)$. ∎

######  Corollary 2.4.

Any potential Best Response contains at most one link to the same meta-node.

###### Proof.

Let $v_{1},v_{2}\in V(G)$ be two nodes belonging to the same meta-node and
suppose that $(S,i)$ is any strategy for $u$ with $v_{1},v_{2}\in S$. Consider
$S^{\prime}=S\setminus\left\\{v_{1}\right\\}$. Clearly,
$CC_{u}(v,S,i)=CC_{u}(v,S^{\prime},i)$ and
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ for every $v\in\mathcal{U}[G]$. Then,
by Lemma 2.3, $U(u,S,i)-U(u,S^{\prime},i)=-\alpha<0$. Therefore,
$U(u,S^{\prime},i)>U(u,S,i)$ and $(S,i)$ cannot have maximum utility. ∎

In view of this we now redefine the following concepts:

(a) Thanks to Corollary 2.4, any link-strategy $S$ considered from any
potential best response for $u$ can be assumed without loss of generality to
be a subset of $V(G^{\prime})$, meaning that $u$ is buying one link for each
meta-node from this subset and each such link is pointing to any node from $G$
inside such meta-node (it does not matter to which one).

(b) Notice that any two nodes $z_{1},z_{2}$ belonging to the same meta-node $z
\in V(G^{\prime})$ satisfy $\Delta(z_{1},S,i)=\Delta(z_{2},S,i)$ for any link-
strategy $S$ and immunisation value $i$. Therefore, it makes sense to define
$\Delta(z,S,i)$ as the sum of the squares of the size of the connected
components we obtain after the removal of all the nodes from $z$ assuming that
$u$ has adopted the link strategy $S$ and immunisation value $i$.

(c) The attacked set $A(S,i)$ can be redefined as a subset of meta-nodes from
$G^{\prime}$ instead of nodes from $V(G)$.

###  2.2 The Meta-Tree $T$

Let $(S,i)$ be a strategy for player $u$ and $G^{\prime}=G^{\prime}(S,i)$ the
corresponding meta-graph.

We define $\mathcal{U}_{1}(G^{\prime})$ to be the set of vulnerable meta-nodes
from $V(G^{\prime})$ that are not an articulation point from $V(G^{\prime})$,
that is, the set of vulnerable meta-nodes that when removed we obtain exactly
the same number of connected components, and $\mathcal{U}_{\geq
2}(G^{\prime})$ the set of vulnerable meta-nodes from $V(G^{\prime})$ that are
an articulation point in $V(G^{\prime})$, that is, the set of vulnerable meta-
nodes that when removed we obtain at least two distinct connected components
in $V(G^{\prime})$. Then, a connected sub-graph of at least two meta-nodes
that remains connected whenever we remove any vulnerable meta-node is called
to be a _$2_{\mathcal{I}}-$ vertex-connected component_ of $G^{\prime}$.

The next structure is crucial to simplify the problem of computing a Best
Response in this model. The concept follows the same idea as in [10] but we
think our definition is much more simple and clear.

######  Definition 2.5.

The _meta-tree_ of $G^{\prime}$, noted as $T=T(G^{\prime})$ is defined in the
following way:

(i) The vertices of $T$, called _meta-tree nodes_ decompose into two subsets
$V_{1}(G^{\prime})$, $V_{\geq 2}(G^{\prime})$ that consist of the maximal
$2_{\mathcal{I}}$-vertex-connected components from $G^{\prime}$ and the meta-
nodes from $\mathcal{U}_{\geq 2}(G^{\prime})$, respectively.

(ii) The edges of $T$, called _meta-tree edges_ consist of the pairs $(w,W)$
with $W\in V_{1}(G^{\prime})$ and $w\in V_{\geq 2}(G^{\prime})$ such that
$w\in W$.

Let $v\in V(T(G^{\prime}))$. We will always assume that we root $T$ on the
node containing $u$. When the context is clear we define $v_{1},...,v_{k(v)}$
the children of $v$ with respect $T$ and $T_{1}(v),...,T_{k(v)}(v)$ the
subtrees hanging from $v$. Then we also define
$T(v)=\left\\{v\right\\}\cup_{1\leq j\leq k(v)}T_{j}(v)$ and $\overline{T(v)}$
the tree we obtain when removing $T(v)$ from $T$ which is the same as the
connected component in which $W(u,S,i)$ belongs after removing $v$ from the
graph. This notation will be useful specially in the next sections.

In the forthcoming subsections the most common situations that we will be
dealing are: either working with the empty link-strategy for player $u$,
working with a general strategy $(S,i)$ for player $u$, or comparing between
two strategies $(S,i)$, $(S^{\prime},i^{\prime})$. In this last case, the most
common scenario will consist in comparing $(S,i)$ with $(S^{\prime},i)$, i.e.,
two strategies with the same immunisation value. In all these situations it is
really important to distinguish between the next three levels of abstraction:

1\. The first level of abstraction corresponds to the original network after
$u$ adopts $(S,i)$. This network is $G(S,i)$ and the nodes from this graph,
$V(G(S,i))$, constitute the most basic kind of nodes. If the context is clear
we might write $G$ instead of $G(S,i)$.

2\. The second level of abstraction corresponds to the meta-graph
$G^{\prime}(S,i)$. This is the network in which we merge connected nodes that
are neighbours having the same immunisation value into bigger nodes which we
call _meta-nodes_. If the context is clear we might write $G^{\prime}$ instead
of $G^{\prime}(S,i)$.

3\. Finally the third level of abstraction is the meta-tree that is obtained
considering the maximal $2_{\mathcal{I}}-$vertex-connected components of the
meta-graph. In most of the cases this network will be noted as
$T(G^{\prime}(S,i))$ and in this third level we talk about meta-tree nodes and
meta-tree edges. If the context is clear we might write $T$ instead of
$T(G^{\prime})$.

###  2.3 Simplifying the Set of Possible Best Responses

We continue obtaining some results that help us simplify how best responses
can be assumed to be like.

The delete-simplification. Scenario (a): Let $(S,i)$ be a strategy for player
$u$. Suppose that $v_{1},v_{2}\in S$ are meta-nodes belonging to the same
$2_{\mathcal{I}}$-vertex-connected component from $G^{\prime}(\emptyset,i)$.
Furthermore, suppose that $v_{1}\in\mathcal{I}[G^{\prime}(\emptyset,i)]$ and
let $S^{\prime}=S\setminus\left\\{v_{1}\right\\}$.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{1}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{2}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle(a)$

We now examine some properties of this scenario that allow us to simplify the
link-strategies to be considered in the forthcoming sections.

######  Lemma 2.6.

Let $v\in\mathcal{U}(G(S,i))$. Then, for any $z\in V(G)$,
$CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$ implying
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$, too.

###### Proof.

Let us define
$S_{0}=S\setminus\left(\left\\{v_{1}\right\\}\cup\left\\{v_{2}\right\\}\right)$
so that $S=S_{0}\cup\left\\{v_{1}\right\\}\cup\left\\{v_{2}\right\\}$ and
$S^{\prime}=S_{0}\cup\left\\{v_{2}\right\\}$. Consider the graph $G(S_{0},i)$.
Let $CC_{v}=W(v,S_{0},i)$ and let $CC$ be $\left\\{CC_{v}\right\\}$ together
with the collection of connected components obtained from $G(S_{0},i)$ after
disconnecting $W(v,S_{0},i)$. Then, let $CC_{u},CC_{1},CC_{2}$ the connected
components from $CC$ in which $u,v_{1},v_{2}$ belong, respectively. Since
$v_{1},v_{2}$ belong to the same maximal $2_{\mathcal{I}}-$vertex-connected
component from $G^{\prime}(\emptyset,i)$ it can only happen that
$CC_{1}=CC_{2}$. Moreover, $v_{1}\in\mathcal{I}(G(S,i))$ implies that
$CC_{1}\neq CC_{v}$. Then we distinguish only two possible cases:

$v_{1}$$v_{2}$$u$$CC_{1}=CC_{2}$$CC_{u}=CC_{v}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}Case\
1\\\
\end{array}$$v_{1}$$v_{2}$$u$$CC_{1}=CC_{2}$$CC_{v}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}Case\
2\\\ \end{array}$$CC_{u}$

(1) $CC_{u}=CC_{v}$. Then it is clear from the figure that for any $z\in
V(G)$, $CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$ because $v_{1}$ is immunised by
hypothesis, implying $\Delta(v,S^{\prime},i)=\Delta(v,S,i)$.

(2) $CC_{u}\neq CC_{v}$. Then, again, it is clear from the figure that for any
$z\in V(G)$, $CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$, implying
$\Delta(v,S^{\prime},i)=\Delta(v,S,i)$, too. ∎

The swap-simplification. We now examine some other scenarios in which we cap
apply a swap movement. Let $(S,i)$ be a strategy for player $u$. Then we
consider:

Scenario (b.i): Suppose that
$v_{1},v_{2}\in\mathcal{I}[G^{\prime}(\emptyset,i)]$. Suppose that $v_{1}\in
S$, $v_{2}\not\in S$ and consider the strategy
$S^{\prime}=S\cup\left\\{v_{2}\right\\}\setminus\left\\{v_{1}\right\\}$.
Furthermore, suppose that $v_{1},v_{2}$ are meta-nodes belonging to the same
maximal $2_{\mathcal{I}}$-vertex-connected component from
$G^{\prime}(\emptyset,i)$.

Scenario (b.ii): Suppose that
$v_{1}\in\mathcal{U}_{1}[G^{\prime}(\emptyset,i)]$ and
$v_{2}\in\mathcal{I}[G^{\prime}(\emptyset,i)]$. Suppose that $v_{1}\in S$,
$v_{2}\not\in S$ and consider the link-strategy
$S^{\prime}=S\cup\left\\{v_{2}\right\\}\setminus\left\\{v_{1}\right\\}$.
Furthermore, suppose that $v_{1},v_{2}$ are meta-nodes belonging to the same
maximal $2_{\mathcal{I}}$-vertex-connected component from
$G^{\prime}(\emptyset,i)$.

Scenario (b.iii): Suppose that $v_{1}\in\mathcal{U}_{\geq
2}[G^{\prime}(\emptyset,i)]$, $v_{2}\in\mathcal{I}[G^{\prime}(\emptyset,i)]$
and $v_{2}$ is any neighbour of $v_{1}$ in $G^{\prime}(\emptyset,i)$ contained
in any simple and connected path (in $G^{\prime}(\emptyset,i)$ which we assume
to be connected) from $v_{1}$ to $u$. Consider the strategy
$S^{\prime}=S\cup\left\\{v_{2}\right\\}\setminus\left\\{v_{1}\right\\}$.
Furthermore, suppose that $v_{1},v_{2}$ are meta-nodes belonging to the same
maximal $2_{\mathcal{I}}$-vertex-connected component from
$G^{\prime}(\emptyset,i)$.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{1}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{2}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle(b.i)$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{1}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{2}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle(b.ii)$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{1}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{2}\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle(b.iii)$

######  Lemma 2.7.

Let $v\in\mathcal{U}(G(S,i))$. Then, for any $z\in V(G)$,
$CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$ if $v\not\in W(u,S,i)$ and
$CC_{z}(v,S,i)\subseteq CC_{z}(v,S^{\prime},i)$ if $v\in W(u,S,i)$. This
implies that if $v\not\in W(u,S,i)$, then
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$. Otherwise,
$\Delta(v,S,i)\leq\Delta(v,S^{\prime},i)$.

###### Proof.

Let $S_{0}=S\setminus\left\\{v_{1}\right\\}$ so that
$S=S_{0}\cup\left\\{v_{1}\right\\}$ and
$S^{\prime}=S_{0}\cup\left\\{v_{2}\right\\}$. Consider the graph $G(S_{0},i)$.
Let $CC_{v}=W(v,S_{0},i)$ and let $CC$ be $\left\\{CC_{v}\right\\}$ together
with the collection of connected components obtained from $G(S_{0},i)$ after
disconnecting $W(v,S_{0},i)$. Then, let $CC_{u},CC_{1},CC_{2}$ the connected
components from $CC$ in which $u,v_{1},v_{2}$ belong, respectively. First of
all, since $v_{2}\in\mathcal{I}(G(S,i))$ then $CC_{2}\neq CC_{v}$. Then it can
only happen the following:

$v_{1}$$v_{2}$$u$$CC_{1}=CC_{2}$$CC_{u}=CC_{v}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}Case\
1.1\\\ \\\
\end{array}$$v_{1}$$v_{2}$$u$$CC_{1}=CC_{2}$$CC_{v}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}Case\
1.2\\\ \\\
\end{array}$$CC_{u}$$v_{2}$$u$$CC_{2}=CC_{v}$$v_{1}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}Case\
2\\\ \\\ \end{array}$$CC_{v}=CC_{1}$

(1) $CC_{1}=CC_{2}$. We distinguish two subcases:

(1.1) $CC_{u}=CC_{v}$. Then it is clear from the figure that for any $z\in
V(G)$, $CC_{z}(v,S,i)\subseteq CC_{z}(v,S^{\prime},i)$. Then it happens
$\Delta(v,S,i)\leq\Delta(v,S^{\prime},i)$. Notice that in this situation it
holds $u\in W(v_{1},S,i)=W(v,S,i)$ so $v\in W(u,S,i)$.

(1.2) $CC_{u}\neq CC_{v}$. Then looking at the figure above we deduce that for
any $z\in V(G)$, $CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$. Then we clearly have
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$. Notice that in this situation it holds
$u\not\in W(v,S,i)$ so $v\not\in W(u,S,i)$.

(2) $CC_{1}\neq CC_{2}$. Then because of the restrictions regarding $u,v_{1}$
and $v_{2}$, we must have $CC_{1}=CC_{v}$ and $CC_{2}=CC_{u}$. Since
$CC_{2}\neq CC_{v}$ then it is clear from the figure that for any $z\in V(G)$,
$CC_{z}(v,S,i)\subseteq CC_{z}(v,S^{\prime},i)$ implying
$\Delta(v,S,i)\leq\Delta(v,S^{\prime},i)$, too if $i=0$ or
$CC_{z}(v,S,i)=CC_{z}(v,S^{\prime},i)$ implying
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ if $i=1$. Notice that in the situation
$i=0$ it holds $u\in W(v_{1},S,i)=W(v,S,i)$ so $v\in W(u,S,i)$ whereas when
$i=1$ then $v\not\in W(u,S,i)$.

∎

The meta-tree simplification. Finally, with the help of the previous results
we can prove that in all these four scenarios the utility for player $u$ with
strategy $(S^{\prime},i)$ is greater than or equal the one for the strategy
$(S,i)$. This allows to make a significant simplification. But before showing
the main result of this subsection consider the following observation.

If we suppose that $A(S,0)=\left\\{W(u,S,0)\right\\}$ then
$CC_{u}(\left\\{W(u,S,i)\right\\},S,0)=\emptyset$ and therefore $U(u,S,0)\leq
0$. However, $U(u,\emptyset,0)\geq 0$. Therefore:

######  Remark 2.8.

In order to compute a best response for $u$ it is enough if we consider
strategies $(S,i)$ such that $A(S,i)\neq\left\\{W(u,S,i)\right\\}$.

Then we are ready to prove the following Lemma:

######  Lemma 2.9.

In all the previous four scenarios it holds $U(u,S^{\prime},i)\geq U(u,S,i)$.

###### Proof.

We must distinguish between $u$ being vulnerable or immunised.

First of all, if $u$ is immunised then using Lemma 2.6 and Lemma 2.7 we deduce
that $\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ if $v\not\in W(u,S,i)$ implying
that $A(S^{\prime},i)=A(S,i)$. Moreover, by the same two lemmas we know that
it holds $CC_{u}(a,S^{\prime},i)=CC_{u}(a,S,i)$ for every $a\in
A(S,i)=A(S^{\prime},i)$, implying in this case $U(u,S^{\prime},i)\leq
U(u,S,i)$.

Now we address the case $u$ vulnerable:

(a) If $\Delta(S,i)=\Delta(u,S,i)$, again, by a direct consequence of Lemma
2.6 and Lemma 2.7 we know that $\Delta(S,i)\leq\Delta(S^{\prime},i)$.
Therefore we have only two sub-cases to consider.

(a.i) If $\Delta(u,S^{\prime},i)>\Delta(u,S,i)$. By Lemma 2.6 and Lemma 2.7 we
know that $\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ if $v$ is vulnerable and
$v\not\in W(u,S,i)$. But we can discard the case
$A(S,i)=\left\\{W(u,S,i)\right\\}$ due to the previous remark so $|A(S,i)|>1$.
Then $\Delta(S^{\prime},i)=\Delta(S,i)$ and combining all these results we
reach to $A(S^{\prime},i)=A(S,i)\setminus\left\\{W(u,S,i)\right\\}$. In fact,
by the same two previous lemmas we know that it holds
$CC_{u}(a,S^{\prime},i)=CC_{u}(a,S,i)$ for every $a\in
A(S,i)\setminus\left\\{W(u,S,i)\right\\}=A(S^{\prime},i)$. Moreover,
$CC_{u}(\left\\{W(u,S,i)\right\\},S,i)=\emptyset$ because by hypothesis $u$ is
vulnerable. Hence:

$\displaystyle U(u,S^{\prime},i)-U(u,S,i)=$
$\displaystyle=-\alpha|S^{\prime}|+\alpha|S|+\frac{1}{|A(S,i)|-1}\sum_{a\in
A(S,i)}|CC_{u}(a,S,i)|-\frac{1}{|A(S,i)|}\sum_{a\in A(S,i)}|CC_{u}(a,S,i)|>$
$\displaystyle>-\alpha|S^{\prime}|+\alpha|S|$

(a.ii) Otherwise, if $\Delta(u,S^{\prime},i)=\Delta(u,S,i)$ then by Lemma 2.6
and Lemma 2.7 we know that it must hold $W(u,S,i)=W(u,S^{\prime},i)$. Then,
again, by the same lemmas, $\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ if $v$ is
vulnerable and $v\not\in W(u,S,i)=W(u,S^{\prime},i)$. In conclusion
$A(S^{\prime},i)=A(S,i)$. Furthermore, by considering the same lemmas we know
that $CC_{u}(a,S,i)=CC_{u}(a,S^{\prime},i)$ for every $a \in
A(S,i)\setminus\left\\{W(u,S,i)\right\\}=A(S^{\prime},i)\setminus\left\\{W(u,S^{\prime},i)\right\\}$
and $CC_{u}(a,S,i)\subseteq CC_{u}(a,S^{\prime},i)$ for any $a\in
W(u,S,i)=W(u,S^{\prime},i)$. From here we obtain

$U(u,S^{\prime},i)-U(u,S,i)\geq-\alpha|S^{\prime}|+\alpha|S|$

(b) If $\Delta(S,i)<\Delta(u,S,i)$. By Lemma 2.6 and Lemma 2.7
$\Delta(v,S,i)=\Delta(v,S^{\prime},i)$ for any $v\not\in W(u,S,i)$ and
$\Delta(v,S,i)\leq\Delta(v,S^{\prime},i)$ if $v\in W(u,S,i)$. This implies
$A(S,i)=A(S^{\prime},i)$. Furthermore, by considering the same lemmas we know
that $CC_{u}(a,S,i)=CC_{u}(a,S^{\prime},i)$ for every $a \in
A(S,i)=A(S^{\prime},i)$. Here we obtain

$U(u,S^{\prime},i)-U(u,S,i)=-\alpha|S^{\prime}|+\alpha|S|$

Finally, the conclusion is clear because in all the four scenarios
$|S|\geq|S^{\prime}|$. ∎

Now, as a consequence of these results we reach the following corollary:

######  Corollary 2.10.

We can assume without loss of generality that any potential best response $S$
for $u$ satisfies:

\- $S$ points only to immunised meta-nodes.

\- $S$ contains at most one link to each component of $V_{1}(G^{\prime})$.

\- It does not matter towards which immunised meta-node from
$V_{1}(G^{\prime})$ $S$ is pointing to.

###### Proof.

First, in order to see that we can assume wlog that $S$ points only to
immunised meta-nodes apply Lemma 2.7 in scenarios (b.ii) and (b.iii) from the
swap-simplification subsection.

Secondly, in order to see that we can assume wlog that $S$ contains at most
one link to each component of $V_{1}(G^{\prime}(S,i))$ apply Lemma 2.6 in
scenario (a) from the delete-simplification subsection to every link from $S$.

Finally, in order to see that we can change wlog towards which immunised meta-
node is $S$ pointing to inside each component from $V_{1}(G^{\prime})$ apply
Lemma 2.7 in scenario (b.i) from the swap-simplification subsection.

∎

Consider an immunisation value $i$, and a link-strategy $S$ corresponding to
any potential best response strategy for $u$. So far, we can summarise that we
have distinguished three distinct levels of abstraction for $S$:

1\. The first level of abstraction corresponds to our starting point, writing
$S\subseteq V(G)$ meaning that $S$ consists of a collection of nodes from
$G(\emptyset,i)$.

2\. The second level of abstraction consists in thinking of $S$ as a
collection of distinct meta-nodes from $G^{\prime}(\emptyset,i)$, writing
$S\subseteq V(G^{\prime})$ meaning that $S$ consists of a collection of meta-
nodes from $G^{\prime}(\emptyset,i)$, since we know that any such link-
strategy does not contain two links to distinct nodes from the same meta-node.
We reached this level of abstraction after Corollary 2.4.

3\. In the last level of abstraction we think $S$ as a subset of meta-tree
nodes from $V_{1}(G^{\prime}(\emptyset,i))$ and we write $S\subseteq
V_{1}(G^{\prime})$ meaning that $S$ points to any immunised meta-node inside
each of the meta-tree vertices from $S$, since we can assume wlog that any
such link-strategy does not contain any link to any vulnerable meta-node from
$\mathcal{U}_{\geq 2}(G^{\prime})$ and it contains, at most, one link to any
immunised meta-node from $V_{1}(G^{\prime}(\emptyset,i))$ (it does not matter
towards which). We reached this level of abstraction after Corollary 2.10.

Taking into the account these three levels of abstraction, in the forthcoming
sections, without loss of generality, we always make the next assumption:

######  Theorem 2.11.

Any potential best response for $u$ can be assumed without loss of generality
to be a subset of $V_{1}(G^{\prime})$, meaning that the corresponding strategy
consists in selecting any immunised meta-node inside each of the components
from such subset.

Moreover, given two link-strategies $S,S^{\prime}$ we consider $S=S^{\prime}$
as an equality in the third level of abstraction although it could be that $S$
and $S^{\prime}$ point to distinct endpoints in the first or in the second
level of abstraction.

##  3 Restricted Strategies and Restricted Utility: A Top-Down
Characterisation

As stated in Theorem 2.11, we can assume without loss of generality that any
potential best response $(S,i)$ satisfies that $S\subseteq V_{1}(G^{\prime})$.
Despite of this result, there still seems to be an exponential number of
possible combinations to explore. For this reason we consider the following
idea:

Since we want to find a strategy $(S,i)$ that maximises the value $U(u,S,i)$,
we can partition the set of potential best responses into a collection of
mutually disjoint subsets depending on the possible values of $\Delta$ and
$|A|$. If we know how to find any strategy achieving the maximum restricted
utility in each subset, then among such strategies we can pick the one having
a maximum utility as a best response for the original problem.

Moreover, we will see that the best response strategy for the objective
function when restricted to a sub-tree $T(v)$ can be computed by finding the
best response strategies restricted to each of the sub-trees
$T_{1}(v),...,T_{k(v)}(v)$. In this way we can exploit the structure of the
meta-tree, breaking the original problem into easier sub-problems to solve.

###  3.1 Utility and Restricted Utility

In this subsection we introduce the partition into which we split the
collection of all potential best response strategies. The collection of
strategies that we considering corresponds to the sets of
$(\Delta_{0},m,T(v))-$strategies where:

(1) The parameter $\Delta_{0}$ corresponds to the minimum delta value any
vulnerable meta-node from the network has. Trivially, $1\leq\Delta_{0}\leq
n^{2}$.

(2) The subtree $T(v)$ from $T$ in which we are focusing our attention. Recall
that we always consider that $T$ is rooted at the node containing $u$.
Trivially $v\in V(T)$. This parameter is really useful because we want to be
able to solve the problem for a subtree $T(v)$ by solving the corresponding
sub-problems for the subtrees $T_{1}(v),...,T_{k(v)}(v)$ in which $T(v)$
decomposes.

(3) The parameter $m$ is the number of meta-nodes from $\mathcal{U}[T(v)]$
achieving a delta value equal to $\Delta_{0}$.

Before providing the formal definition of a $(\Delta_{0},m,T(v))-$strategy,
however, we first introduce the concept of restricted attack set.

######  Definition 3.1.

Let $S\subseteq V_{1}(G^{\prime})$, $i\in\left\\{0,1\right\\}$ and $v\in
V(T)$. We define the restricted $(\Delta_{0},T(v))-$attack set with respect
$(S,i)$, using the notation $A(S,i,\Delta_{0},T(v))$, as the subset of
vulnerable meta-nodes from $T(v)$ having a delta value equal to $\Delta_{0}$,
that is to say, the subset of vulnerable meta-nodes $z \in\mathcal{U}[T(v)]$
with $\Delta(z,S,i)=\Delta_{0}$.

Now we are ready to define what is a $(\Delta_{0},m,T(v))-$strategy.

######  Definition 3.2.

Let $S\subseteq V_{1}(G^{\prime})$, $i\in\left\\{0,1\right\\}$ and $v\in
V(T)$. We say that a strategy $(S,i)$ is a $(\Delta_{0},m,T(v))$-strategy iff

(i) $\Delta(z,S,i)\geq\Delta_{0}$ for every $z\in\mathcal{U}[G^{\prime}]\cap
T(v)$.

(ii) $m$ equals the number of nodes from $\mathcal{U}[T(v)]$ achieving a delta
value equal to $\Delta_{0}$.

Once we have a clear understanding of what is a $(\Delta_{0},m,T(v))-$strategy
let us introduce the concept of restricted utility:

######  Definition 3.3.

Let $S\subseteq V_{1}(G^{\prime})$ and $i\in\left\\{0,1\right\\}$ and suppose
that $(S,i)$ is a $(\Delta_{0},m,T(u))-$strategy. We define the restricted
$(\Delta_{0},|A|,T(v))-$utility of $u$ with respect $S$ as:

$U(u,S,\Delta_{0},|A|,T(v))=-\alpha|S|+\frac{1}{|A|}\sum_{a\in
A(S,1,\Delta_{0},T(v))}|CC_{u}(a,S,1)|$

Notice that in the definition of restricted utility we assume that the
immunisation value is $i=1$ when we consider the set $A(S,i,\Delta_{0},T(v))$
and the values $|CC_{u}(a,S,i)|$.

In the next proposition it is shown that there is an intimate relationship
between the situations $i=0$ and $i=1$.

######  Proposition 3.4.

Let $(S,i)$ be any potential best-response for player $u$. Let
$\Delta_{0}=\Delta(S,i)$ and $|A|=|A(S,1,\Delta_{0},T(u))|$.

If $\Delta(S,0)<\Delta(u,\emptyset,0)$ then $i=0$ and
$U(u,S,i)=U(u,S,\Delta_{0},|A|,T(u))$.

Else, $U(u,S,0)=U(u,S,\Delta_{0},|A|+1,T(u))$ and
$U(u,S,1)=U(u,S,\Delta_{0},|A|,T(u))-\beta$.

###### Proof.

One first should notice the following fact: by Theorem 2.11, we can assume
wlog that all the endpoints of $S$ point to immunised meta-nodes and thus
$\Delta(u,S,0)=\Delta(u,\emptyset,0)$. Therefore:

(i) If $\Delta(S,0)<\Delta(u,\emptyset,0)$, then,
$\Delta(u,S,0)=\Delta(u,\emptyset,0)> \Delta(S,0)$ meaning that the meta-node
$W(u,S,0)$ is not attacked in this scenario. Similarly, when $i=1$ the meta-
node $W(u,S,1)$ is not attacked because $u$ is immunised. Therefore, excluding
the meta-nodes $W(u,S,0)$ and $W(u,S,1)$ the corresponding meta-graphs
$G^{\prime}(S,0)$ and $G^{\prime}(S,1)$ are identical implying $A(S,0)=A(S,1)$
and $CC_{u}(a,S,0)=CC_{u}(a,S,1)$ for every $a\in A(S,0)=A(S,1)$, which leads
to $U(u,S,0)=U(u,S,1)+\beta$ implying that $(S,1)$ cannot be a best response
strategy and, therefore, $i=0$ as we wanted to see. Hence:

$\displaystyle U(u,S,0)=$
$\displaystyle-\alpha|S|+\frac{1}{|A(S,0)|}\sum_{a\in A(S,0)}|CC_{u}(a,S,0)|=$
$\displaystyle=$ $\displaystyle-\alpha|S|+\frac{1}{|A(S,1)|}\sum_{a\in
A(S,1)}|CC_{u}(a,S,1)|=U(u,S,\Delta_{0},|A|,T(u))$

(ii) If $\Delta(S,0)=\Delta(u,\emptyset,0)$, then, when $i=0$ the meta-node
$W(u,S,0)$ is attacked in this scenario whereas when $i=1$ the meta-node
$W(u,S,1)$ is not attacked because $u$ is immunised. By remark 2.8 we can
exclude the case $A(S,0)=\left\\{W(u,S,0)\right\\}$ and, then, apart from the
meta-nodes $W(u,S,0)$ and $W(u,S,1)$ the corresponding meta-graphs
$G^{\prime}(S,0)$ and $G^{\prime}(S,1)$ are identical implying in this
situation that $A(S,1)=A(S,0)\setminus\left\\{W(u,S,0)\right\\}$,
$CC_{u}(a,S,0)=CC_{u}(a,S,1)$ for every $a\in A(S,1)$ and
$CC_{u}(W(u,S,0),S,0)=\emptyset$. With these results then

$\displaystyle U(u,S,0)$
$\displaystyle=-\alpha|S|+\frac{1}{|A(S,0)|}\sum_{a\in
A(S,0)}|CC_{u}(a,S,0)|=$
$\displaystyle=-\alpha|S|+\frac{1}{|A(S,1)|+1}\sum_{a\in
A(S,1)}|CC_{u}(a,S,1)|=U(u,S,\Delta_{0},|A|+1,T(u))$

And:

$\displaystyle U(u,S,1)=$
$\displaystyle-\alpha|S|-\beta+\frac{1}{|A(S,1)|}\sum_{a\in
A(S,1)}|CC_{u}(a,S,1)|=$ $\displaystyle=$ $\displaystyle
U(u,S,\Delta_{0},|A|,T(u))-\beta$

∎

Hence, in order to compute the best response for $u$ in polynomial time, it is
enough to show that the maximum restricted utility can be computed in
polynomial time, given that we know the values of the parameters
$\Delta_{0},|A|$.

Remark: Since the restricted utility function is defined by taking the
immunisation value equal to $1$, then in the forthcoming sections we delete
the reference to the immunisation value, understanding that we are assuming
wlog that such value equals $1$. This means that we will write
$\Delta(z,S)=\Delta(z,S,1)$, $CC_{u}(a,S)=CC_{u}(a,S,1)$, $W(u,S)=W(u,S,1)$,
and so on.

###  3.2 A Formula for the Restricted Utility

The aim of this subsection is to obtain a formula for the restricted utility
$U(u,S,\Delta_{0},|A|,T(v))$ in terms of the restricted utilities
$U(u,S_{j},\Delta_{0},|A|,T(v_{j}))$ for the corresponding subtrees of $T(v)$.
To achieve the formulae given in Proposition 3.8 we first need to prove some
technical lemmas.

The following three technical lemmas relate the restricted strategies in
$T(v)$ with the restricted strategies in the subtrees $T(v_{i})$.

######  Lemma 3.5.

Let $S\subseteq V_{1}(G^{\prime})$ and $v\in V(T)$. Then
$\Delta(z,S)=\Delta(z,S\cap T(v))$ for every $z\in\mathcal{U}[G^{\prime}]\cap
T(v)$.

###### Proof.

If $v=W(u,S)$ the result is trivial. Otherwise, let $S_{v}=S\cap T(v)$ and
$\overline{S_{v}}=S\cap\overline{T(v)}$ and take
$z\in\mathcal{U}[G^{\prime}]\cap T(v)$. Since $v$ is an articulation point of
$T(v)$ then this means that all the endpoints of $S$ belonging to
$\overline{T(v)}$ must be in the connected component in which $W(u,S)$ belongs
after disconnecting $v$. Then $\Delta(z,S)=\Delta(z,S_{v})=\Delta(z,S\cap
T(v))$.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v\\\
\end{array}$$\displaystyle S_{x}$$\displaystyle\overline{S_{x}}$$\displaystyle
X$$\displaystyle\overline{X}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}z\\\
\end{array}$$z$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle X$$\displaystyle\overline{X}$$\displaystyle
S_{x}$$\displaystyle\overline{S}_{x}$

∎

######  Lemma 3.6.

Let $v\in V(T)$, let $S\subseteq V_{1}(G^{\prime})$ be a
$(\Delta_{0},m,T(v))-$strategy and let $m_{i}=|A(S,\Delta_{0},T(v_{i}))|$.
Then $S\cap T(v_{i})$ is a $(\Delta_{0},m_{i},T(v_{i}))-$strategy.

###### Proof.

First, by Lemma 3.5, $\Delta(z,S)=\Delta(z,S\cap T(v_{i}))$ for all
$z\in\mathcal{U}[G^{\prime}]\cap T(v_{i})$. Since $S$ is a
$(\Delta_{0},m,T(v))-$strategy then $\Delta(z,S)\geq\Delta_{0}$ and, from
here, $\Delta(z,S\cap T(v_{i}))=\Delta(z,S)\geq\Delta_{0}$ for every
$z\in\mathcal{U}[G^{\prime}]\cap T(v_{i})$.

Moreover, by definition, $m_{i}=|A(S,\Delta_{0},T(v_{i}))|$. Now the
conclusion is clear.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v_{i}\\\
\end{array}$$\displaystyle S$$\displaystyle T(v_{i})$$\displaystyle
T(v)$$\displaystyle\begin{array}[]{{>{\displaystyle}l}}v\\\
\end{array}$$\displaystyle S\cap T(v_{i})$

∎

######  Lemma 3.7.

Let $S\subseteq V_{1}(G^{\prime})$ be a $(\Delta_{0},m,T(v))-$strategy and
suppose that $a \in A(S,\Delta_{0},T(v_{i}))$. Then
$CC_{u}(a,S)=CC_{u}(a,S\cap T(v_{i}))$.

###### Proof.

$T$ is rooted on $W(u,S)$ and $v_{i}$ is on the path connecting $a$ with
$W(u,S)$, because we are assuming $a\in A(S,\Delta_{0},T(v_{i}))$. Therefore,
all the endpoints of $S$ that do not belong to $T(v_{i})$ are contained inside
the connected component in which $W(u,S)$ belongs when removing $a$. From here
the conclusion.

∎

For a given node $v\in V_{1}(G^{\prime})$, any vulnerable meta-node
$w\in\mathcal{U}_{1}(G^{\prime})$ from $v$ has a delta value independent of
the strategy $S$. Let $\widetilde{m}(v,\Delta_{0})$ be defined the number of
meta-nodes from $\mathcal{U}_{1}(G^{\prime})$ contained in $v$ having delta
value equal to $\Delta_{0}$ if $v\in V_{1}(G^{\prime})$ and $0$ otherwise.
Then, the following formulae will be useful later:

######  Proposition 3.8.

Let $v\in V(T)$, $S_{i}$ be $(\Delta_{0},m_{i},T(v_{i}))-$strategies for every
$i=1,...,k(v)$ and let $S=\cup_{j=1}^{k(v)}S_{j}$. If $v\in V_{\geq
2}(G^{\prime})\cap A(S,\Delta_{0},T(v))$:

$U(u,S,\Delta_{0},|A|,T(v))=\sum_{j=1}^{k(v)}U(u,S_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\left(|\overline{T(v)}|+\sum_{S_{j}\neq\emptyset}|T(v_{j})|\right)$

Otherwise,

$U(u,S,\Delta_{0},|A|,T(v))=\sum_{j=1}^{k(v)}U(u,S_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\sqrt{\Delta_{0}}\cdot\widetilde{m}(v,\Delta_{0})$

###### Proof.

On the one hand, if $a\in A(S,\Delta_{0},T(v_{i}))$ then we have
$CC_{u}(a,S)=CC_{u}(a,S_{i})$ using Lemma 3.7. On the other hand:

(i) If $v\in V_{\geq 2}(G^{\prime})$ and $a=v\in A(S,\Delta_{0},T(v))$, then
$CC_{u}(a,S)=\overline{T(v)}\cup\left(\cup_{S_{j}\neq\emptyset}T(v_{j})\right)$.

(ii) If $v\in V_{1}(G^{\prime})$, $a\in\mathcal{U}_{1}(G^{\prime})$ with $a\in
v$ and $a\in A(S,\Delta_{0},T(v))$ as well, then $|CC_{u}(a,S)|=(n-|a|)=
\sqrt{\Delta_{0}}$.

Therefore, suppose first that $v\in V_{\geq 2}(G^{\prime})\cap
A(S,\Delta_{0},T(v))$. Then:

$\displaystyle U(u,S,\Delta_{0},|A|,T(v))=-\alpha|S|+\frac{1}{|A|}\sum_{a\in
A(S,\Delta_{0},T(v))}|CC_{u}(a,S)|=$
$\displaystyle=-\alpha\sum_{i=1}^{k(v)}|S_{i}|+\frac{1}{|A|}\left(\sum_{i=1}^{k(v)}\sum_{a\in
A(S,\Delta_{0},T(v_{i}))}|CC_{u}(a,S)|\right)+\frac{1}{|A|}|CC_{u}(v,S)|=$
$\displaystyle=-\alpha\sum_{i=1}^{k(v)}|S_{i}|+\frac{1}{|A|}\left(\sum_{i=1}^{k(v)}\sum_{a\in
A(S,\Delta_{0},T(v_{i}))}|CC_{u}(a,S_{i})|\right)+\frac{1}{|A|}|CC_{u}(v,S)|=$
$\displaystyle=\sum_{j=1}^{k(v)}U(u,S_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\left(|\overline{T(v)}|+\sum_{S_{j}\neq\emptyset}|T(v_{j})|\right)$

Otherwise:

$\displaystyle U(u,S,\Delta_{0},|A|,T(v))=-\alpha|S|+\frac{1}{|A|}\sum_{a\in
A(S,\Delta_{0},T(v))}|CC_{u}(a,S)|=$
$\displaystyle=-\alpha\sum_{i=1}^{k(v)}|S_{i}|+\frac{1}{|A|}\left(\sum_{i=1}^{k(v)}\sum_{a\in
A(S,\Delta_{0},T(v_{i}))}|CC_{u}(a,S)|\right)+\sum_{a\in\mathcal{U}[v]\land\Delta(a,S)=\Delta_{0}}\frac{1}{|A|}|CC_{u}(a,S)|=$
$\displaystyle=-\alpha\sum_{i=1}^{k(v)}|S_{i}|+\frac{1}{|A|}\left(\sum_{i=1}^{k(v)}\sum_{a\in
A(S,\Delta_{0},T(v_{i}))}|CC_{u}(a,S_{i})|\right)+\frac{1}{|A|}\sqrt{\Delta_{0}}\cdot\widetilde{m}(v,\Delta_{0})=$
$\displaystyle=\sum_{j=1}^{k(v)}U(u,S_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\sqrt{\Delta_{0}}\cdot\widetilde{m}(v,\Delta_{0})$

∎

##  4 Restricted BR-Strategies: A Bottom-Up Characterisation

In this section we provide the key results in order to design a polynomial
time algorithm that computes a best response strategy for a given player $u$.
We introduce the concept of _restricted BR-strategy_ which corresponds somehow
to the natural concept of a restricted strategy having the maximum possible
restricted utility among all such restricted strategies on a certain sub-tree
$T(v)$ from the meta-tree. We show that this key concept has good properties
and it allows us to exploit the structure of the meta-tree in an efficient
way. We prove that the best response problem on the whole graph we can be
solved computing the restricted best response problems for each subtree in a
bottom-to-top approach.

###  4.1 Restricted BR-strategies on the subtrees

Recall the definition of restricted strategy. Since we refer to the subtrees
$T(v_{i})$ it will be convenient to extend such definition as follows:

######  Definition 4.1.

We say that a strategy $S\subseteq V_{1}(G^{\prime})$ for $u$ is a
$(\Delta_{0},m,\overline{m},T(v))$-strategy with
$\overline{m}=[m_{1},...,m_{k(v)}]$ iff $S$ is a
$(\Delta_{0},m,T(v))$-strategy and $m_{i}=|A(S,\Delta_{0},T(v_{i}))|$ for each
$i=1,...,k(v)$.

Let us define the restricted version of a BR-strategy.

######  Definition 4.2.

We say that a strategy $S\subseteq V_{1}(G^{\prime})$ is a
$(\Delta_{0},|A|,m,T(v))$-BR-strategy iff $S$ is a
$(\Delta_{0},m,T(v))$-strategy of maximum restricted
$(\Delta_{0},|A|,T(v))$-utility among all such
$(\Delta_{0},m,T(v))$-strategies.

######  Definition 4.3.

We say that a strategy $S\subseteq V_{1}(G^{\prime})$ is a
$(\Delta_{0},|A|,m,\overline{m},T(v))$-BR-strategy with
$\overline{m}=[m_{1},...,m_{k(v)}]$ iff $S$ is a
$(\Delta_{0},m,\overline{m},T(v))$-strategy of maximum restricted
$(\Delta_{0},|A|,T(v))$-utility over all such
$(\Delta_{0},m,\overline{m},T(v))$-strategies.

######  Definition 4.4.

Let $S\subseteq T(v)$ be a strategy for $u$. We say that a pair of meta-tree
vertices $(a,b)$ is a $(S,\Delta_{0},T(v))$-blocking pair iff $a\in
A(S,\Delta_{0},T(v))$, $b\in S$ and $b\not\in CC_{u}(a,\emptyset)$.

Notice that for a $(S,\Delta_{0},T(v))$-blocking pair $(a,b)$ since
$b\in\mathcal{I}(G^{\prime})$ and $a\in\mathcal{U}(G^{\prime})$ it follows
that we always have $a\neq b$.

######  Lemma 4.5.

Let $S\subseteq T(v_{i})$. Suppose that $\emptyset$ and $S\neq\emptyset$ are
$(\Delta_{0},m_{i},T(v_{i}))$-strategies. Then,
$A(\emptyset,\Delta_{0},T(v_{i}))=A(S,\Delta_{0},T(v_{i}))$.

###### Proof.

Since $\Delta(z,Z)\leq\Delta(z,Z^{\prime})$ whenever $Z\subseteq Z^{\prime}$,
then we know that $\Delta(z,\emptyset)\leq\Delta(z,S)$. Therefore, if
$\Delta(z,S)=\Delta_{0}$ then $\Delta(z,\emptyset)=\Delta_{0}$ and from here,
$A(S,\Delta_{0},T(v_{i}))\subseteq A(\emptyset,\Delta_{0},T(v_{i}))$. However,
by assumption,
$|A(\emptyset,\Delta_{0},T(v_{i}))|=|A(S,\Delta_{0},T(v_{i}))|=m_{i}$. Then
the conclusion follows easily.

∎

######  Lemma 4.6.

Let $S\subseteq T(v_{i})$. Suppose that $\emptyset$ and $S\neq\emptyset$ are
$(\Delta_{0},m_{i},T(v_{i}))$-strategies. Then, any subset
$S^{\prime}\subseteq S$ is a $(\Delta_{0},m_{i},T(v_{i}))$-strategy and, more
specifically, $A(S^{\prime},\Delta_{0},T(v_{i}))=A(S,\Delta_{0},T(v_{i}))$.

###### Proof.

Since $\Delta(z,Z)\leq\Delta(z,Z^{\prime})$ whenever $Z\subseteq Z^{\prime}$,
we know that $\Delta(z,\emptyset)\leq\Delta(z,S^{\prime})\leq\Delta(z,S)$ for
every $z\in\mathcal{U}[T(v_{i})]$. Therefore,
$\Delta(z,S^{\prime})\geq\Delta(z,\emptyset)\geq\Delta_{0}$ for every
$z\in\mathcal{U}[T(v_{i})]$. Moreover:

(i) If $z$ verifies $\Delta(z,S^{\prime})=\Delta_{0}$ then
$\Delta_{0}\leq\Delta(z,\emptyset)\leq\Delta(z,S^{\prime})=\Delta_{0}$
implying $z\in A(\emptyset,\Delta_{0},T(v_{i}))$. Therefore
$A(S^{\prime},\Delta_{0},T(v_{i}))\subseteq A(\emptyset,\Delta_{0},T(v_{i}))$.

(ii) If $z$ verifies $\Delta(z,S)=\Delta_{0}$ then
$\Delta_{0}\leq\Delta(z,S^{\prime})\leq\Delta(z,S)=\Delta_{0}$ implying $z\in
A(S^{\prime},\Delta_{0},T(v_{i}))$. Therefore
$A(S,\Delta_{0},T(v_{i}))\subseteq A(S^{\prime},\Delta_{0},T(v_{i}))$.

(iii) By lemma 4.5 we know that
$A(\emptyset,\Delta_{0},T(v_{i}))=A(S,\Delta_{0},T(v_{i}))$.

Using (i), (ii) and (iii) we obtain that
$A(S^{\prime},\Delta_{0},T(v_{i}))=A(\emptyset,\Delta_{0},T(v_{i}))=A(S,\Delta_{0},T(v_{i}))$.
Since $m_{i}=|A(\emptyset,\Delta_{0},T(v_{i}))|$ we conclude that
$|A(S^{\prime},\Delta_{0},T(v_{i}))|=m_{i}$ as we wanted to see.

∎

######  Lemma 4.7.

Let $S\subseteq T(v_{i})$. Suppose that $\emptyset$ and $S\neq\emptyset$ are
$(\Delta_{0},m_{i},T(v_{i}))$-strategies. Then, there cannot exist any
$(S,\Delta_{0},T(v_{i}))-$blocking pair.

###### Proof.

Suppose the contrary, then there exists at least one $a\in
A(S,\Delta_{0},T(v))$ and one $b \in S$ such that $b\not\in
CC_{u}(a,\emptyset)$. Let $S^{\prime}$ be the strategy that we obtain from $S$
after the removal of all the elements $\tilde{b}$ from $S$ that satisfy
$\tilde{b} \not\in CC_{u}(a,\emptyset)$. Then, since
$\Delta(z,Z)\leq\Delta(z,Z^{\prime})$ whenever $Z\subseteq Z^{\prime}$, we
obtain that
$\Delta_{0}=\Delta(a,\emptyset)\leq\Delta(a,S^{\prime})<\Delta(a,S)=\Delta_{0}$,
a contradiction.

∎

######  Lemma 4.8.

Let $S\subseteq T(v_{i})$. If there does not exist any
$(S,\Delta_{0},T(v_{i}))-$blocking pair then $CC_{u}(a,S)=CC_{u}(a,\emptyset)$
for any $a\in A(S,\Delta_{0},T(v_{i}))$.

###### Proof.

All the endpoints of $S$ belong to the same connected component in which $u$
belongs when removing $a$ from the network. Therefore,
$CC_{u}(a,S)=CC_{u}(a,\emptyset)$.

∎

######  Corollary 4.9.

Let $S\subseteq T(v_{i})$. Suppose that $\emptyset$ and $S\neq\emptyset$ are
$(\Delta_{0},m_{i},T(v_{i}))$-strategies. Then
$CC_{u}(a,S)=CC_{u}(a,\emptyset)$ for any $a\in A(S,\Delta_{0},T(v_{i}))$.

######  Proposition 4.10.

Let $S$ be a $(\Delta_{0},m,\overline{m},T(v))-$strategy with
$\overline{m}=[m_{1},\ldots,m_{k(v)}]$ and let $B_{i}$ be a
$(\Delta_{0},|A|,m_{i},T(v_{i}))$-BR-strategy. If $|B_{i}|>0$, then $|S\cap
T(v_{i})|>0$.

###### Proof.

Let us suppose the contrary, $|B_{i}|>0$ and $|S\cap T(v_{i})|=0$

Since $S$ is a $(\Delta_{0},m,\overline{m},T(v))-$strategy, then $(S\cap
T(v_{i}))=\emptyset$ is a $(\Delta_{0},T(v_{i}),m_{i})-$strategy by Lemma 3.6.
Therefore, we have $\emptyset$ and $B_{i}$ with $B_{i}\neq\emptyset$ are
$(\Delta_{0},m_{i},T(v_{i}))-$strategies implying:

  * (i)

$A(\emptyset,\Delta_{0},T(v_{i}))=A(B_{i},\Delta_{0},T(v_{i}))$, by Lemma 4.5.

  * (ii)

$CC_{u}(a,B_{i})=CC_{u}(a,\emptyset)$, by Corollary 4.9.

Hence, combining (i) with (ii) we have that
$U(u,\emptyset,|A|,m_{i},T(v_{i}))>U(u,B_{i},|A|,m_{i},T(v_{i}))$
contradicting the fact that $B_{i}$ is a $(\Delta_{0},|A|,m_{i},T(v_{i}))$-BR-
strategy.

∎

######  Proposition 4.11.

Let $S$ be a $(\Delta_{0},|A|,m,\overline{m},T(v))-$BR-strategy and suppose
that $B_{i}$ is a $(\Delta_{0},|A|,m_{i},T(v_{i}))$-BR-strategy. If
$|B_{i}|=0$ then $|S\cap T(v_{i})|\in\left\\{0,1\right\\}$.

###### Proof.

Suppose the contrary, that $|B_{i}|=0$ but $|S\cap T(v_{i})|\geq 2$ and we
reach a contradiction. First, since $S$ is a
$(\Delta_{0},|A|,m,\overline{m},T(v))-$strategy then $S\cap T(v_{i})$ is a
$(\Delta_{0},|A|,m_{i},T(v_{i}))$-strategy by Lemma 3.6. But $B_{i}=\emptyset$
is a $(\Delta_{0},m_{i},T(v_{i}))-$strategy as well. Let $b\in S\cap T(v_{i})$
and define $S^{\prime}=S\setminus\left\\{b\right\\}$.

  * (i)

$A(S\cap T(v_{i}),\Delta_{0},T(v_{i}))=A(S^{\prime}\cap
T(v_{i}),\Delta_{0},T(v_{i}))$, by Lemma 4.6.

  * (ii)

Even more than this, now we see that $CC_{u}(a,S^{\prime})=CC_{u}(a,S)$ for
every $a\in A(S,\Delta_{0},T(v))$:

(ii.a) If $a=v$. Then $CC_{u}(a,S)=CC_{u}(a,S^{\prime})$ because by hypothesis
$|S^{\prime}\cap T(v_{i})|\geq 1>0$ so that $S\cap T(v_{i}),S^{\prime}\cap
T(v_{i})\neq\emptyset$.

(ii.b) If $a\in A(S,\Delta_{0},T(v))\cap(T(v)\setminus(\left\\{v\right\\}\cup
T(v_{i})))$ then $CC_{u}(a,S)=CC_{u}(a,S^{\prime})$ as well, because $b\in
T(v_{i})$.

(ii.c) If $z\in A(S,\Delta_{0},T(v))\cap T(v_{i})$, then
$CC_{u}(a,S)=CC_{u}(a,S^{\prime})$ because by Lemma 4.7 there does not exist
any $(S,\Delta_{0},T(v_{i}))-$blocking pair.

Therefore
$U(u,S^{\prime},\Delta_{0},|A|,T(v))=U(u,S,\Delta_{0},|A|,T(v))+\alpha>U(u,S,\Delta_{0},|A|,T(v))$.

Finally, combining (i) with (ii) we obtain a contradiction with the hypothesis
that $S$ is a $(\Delta_{0},|A|,m,\overline{m},T(v))-$BR-strategy.

∎

###  4.2 Composing Restricted BR-Strategies

Here now we prove the main results that take advantage of the already proven
technical lemmas together with the structure of the meta-tree. Since you can
think about the meta-tree as a tree having two kind of nodes either from
$V_{1}(G^{\prime})$ or $V_{\geq 2}(G^{\prime})$, we need to make a clear
distinction between these cases.

The subproblem when $v\in V_{1}(G^{\prime})$. This is the easiest case from
the two scenarios that we must consider. Recall that
$\widetilde{m}(v,\Delta_{0})$ is the number of meta-nodes from
$\mathcal{U}_{1}(G^{\prime})$ contained in $v$ having delta value equal to
$\Delta_{0}$ if $v\in V_{1}(G^{\prime})$ and $0$ otherwise.

######  Definition 4.12.

Suppose that $B_{i}$ are $(\Delta_{0},|A|,m_{i},T(v_{i}))$-BR-strategies for
each $i=1,...,k(v)$ with $m_{1}+...+m_{k(v)}=m$. Define
$S[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]=\cup_{i\geq 1}B_{i}$.

######  Proposition 4.13.

Let $B_{j}$ be a $(\Delta_{0},m_{j},T(v_{j}))-$strategy for $j=1,...,k(v)$ and
let $m=m_{1}+...+m_{k(v)}$. Then $S=S[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$
is a $(\Delta_{0},m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))$-strategy.

###### Proof.

Since $\Delta(z,B)=\Delta(z,B\cap T(v_{i}))=\Delta(z,B_{i})$ for every
$z\in\mathcal{U}[T(v_{i})]$ we count exactly $m_{i}$ attacked meta-nodes from
$T(v_{i})$. Moreover, the delta value of the vulnerable meta-nodes from
$\mathcal{U}[v]$ does not depend on the choice of the strategy. Therefore
there are exactly $\widetilde{m}(\Delta_{0},v)$ attacked meta-nodes from $v$.
The conclusion now follows easily because of the following equality:

$|A(S,\Delta_{0},T(v))|=m_{1}+...+m_{k(v)}+\widetilde{m}(\Delta_{0},v)$

∎

Even more than this, we can show that:

######  Theorem 4.14.

Suppose that $m_{1},...,m_{k(v)}$ with $m_{1}+...+m_{k(v)}=m$ are given and
$B_{j}$ is a $(\Delta_{0},|A|,m_{j},T(v_{j}))$-BR-strategy for each
$j=1,...,k(v)$. Then, $S=S[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$ is a
$(\Delta_{0},|A|,m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))-$BR-
strategy.

###### Proof.

By Proposition 4.13 we know that $S$ is a
$(\Delta_{0},m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))$-strategy.

Now, we are going to prove that $S$ corresponds to a strategy with maximum
utility for $u$ among all such
$(\Delta_{0},m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))$-strategies. In
order to prove this we show that $U(u,S,\Delta_{0},|A|,T(v))\geq
U(u,S^{\prime},\Delta_{0},|A|,T(v))$ for any
$(\Delta_{0},m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))-$strategy
$S^{\prime}$.

Since $S^{\prime}$ is a
$(\Delta_{0},m+\widetilde{m}(\Delta_{0},v),\overline{m},T(v))-$strategy then
by Lemma 3.6 $S^{\prime}\cap T(v_{j})$ is a
$(\Delta_{0},m_{j},T(v_{j}))-$strategy and, therefore, by definition of best
response we must have $U(u,S^{\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))\leq U(u,B_{j},\Delta_{0},|A|,T(v_{j}))$ for
every $j\in\left\\{1,...,k(v)\right\\}$.

Then using this together with the formula from Proposition 3.8 we obtain the
following:

$U(u,S^{\prime},\Delta_{0},|A|,T(v))=$ $=\sum_{j=1}^{k(v)}U(u,S^{\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\Delta_{0}\cdot\widetilde{m}(\Delta_{0},v)\leq$
$\leq\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\Delta_{0}\cdot\widetilde{m}(\Delta_{0},v)|$

But by construction of $S$:

$\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\Delta_{0}\cdot\widetilde{m}(\Delta_{0},v)=$
$=\sum_{j=1}^{k(v)}U(u,S\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\Delta_{0}\cdot\widetilde{m}(\Delta_{0},v)=$
$=U(u,S,\Delta_{0},|A|,T(v))$

And now the conclusion follows easily.

∎

The subproblem when $v\in V_{\geq 2}(G^{\prime})$. In contrast to the previous
case which was easier, this scenario gets a little more involved.

######  Proposition 4.15.

For a given $v\in V_{\geq 2}(G^{\prime})$, let $S$ be a
$(\Delta_{0},|A|,m,\overline{m},T(v))-$BR-strategy and $B_{i}$ a
$(\Delta_{0},|A|,m_{i},T(v_{i}))-$BR-strategy with $B_{i}\neq\emptyset$. Then
$S^{\prime}=(S\setminus T(v_{i}))\cup B_{i}$ is a
$(\Delta_{0},|A|,m,\overline{m},T(v))-$BR-strategy as well.

###### Proof.

First, we claim that $S^{\prime}$ is a
$(\Delta_{0},m,\overline{m},T(v))-$strategy. This is because:

(i) $\Delta(z,S^{\prime})=\Delta(z,S^{\prime}\cap T(v_{i}))=\Delta(z,B_{i})$
for every $z\in\mathcal{U}[T(v_{i})]$, using Lemma 3.5. Therefore,
$|A(S^{\prime},\Delta_{0},T(v_{i}))|=|A(B_{i},\Delta_{0},T(v_{i}))|=m_{i}$,
too.

(ii) $\Delta(z,S^{\prime})=\Delta(z,S)$ for every $z\in\mathcal{U}[T(v_{j})]$
with $j\neq i$ because the subset of nodes from $S^{\prime}$ that are not
nodes from $S$ together with the set of nodes from $S$ that are not nodes from
$S^{\prime}$ are a subset of $T(v_{i})$ which clearly does not belong to
$T(v_{j})$. Therefore,
$|A(S^{\prime},\Delta_{0},T(v_{j}))|=|A(B_{j},\Delta_{0},T(v_{j}))|=m_{j}$ for
every $j\neq i$.

(iii) Finally, $\Delta(v,S^{\prime})=\Delta(v,S)$ because by hypothesis,
$B_{i}\neq\emptyset$ implying $S\cap T(v_{i})\neq\emptyset$ as well by
Proposition 4.10.

By (i)+(ii) we deduce that $A(S\cap T(v_{j}),\Delta_{0},T(v_{j}))=A(S^{\prime}
\cap T(v_{j}),\Delta_{0},T(v_{j}))$ for each $j=1,...,k(v)$ and together with
(iii) then we conclude $A(S,\Delta_{0},T(v))=A(S^{\prime},\Delta_{0},T(v))$.

Furthermore, we claim that $CC_{u}(a,S^{\prime})=CC_{u}(a,S)$ for every $a\in
A(S, \Delta_{0},T(v))\setminus A(S\cap T(v_{i}),\Delta_{0},T(v_{i}))$. First,
notice that $CC_{u}(v,S^{\prime})=CC_{u}(v,S)$ if $v\in A(S,\Delta_{0},T(v))$
because $B_{i}\neq\emptyset$ implies $S\cap T(v_{i})\neq\emptyset$ as well
using Proposition 4.10. Moreover, $CC_{u}(a,S)=CC_{u}(a,S\cap
T(v_{j}))=CC_{u}(a,S^{\prime}\cap T(v_{j}))=CC_{u}(a,S^{\prime})$ for every
$a\in A(S,\Delta_{0},T(v_{j}))$ with $j\neq i$ using Lemma 3.7. In this way:

$U(u,S^{\prime},\Delta_{0},|A|,T(v))-U(u,S,\Delta_{0},|A|,T(v))=$
$=-\alpha|S^{\prime}|+\alpha|S|+\frac{1}{|A|}\left(\sum_{a\in
A(S^{\prime},\Delta_{0},T(v))}|CC_{u}(a,S^{\prime})|-\sum_{a\in
A(S,\Delta_{0},T(v))}|CC_{u}(a,S)|\right)=$ $=-\alpha|B_{i}|+\alpha|S\cap
T(v_{i})|+\frac{1}{|A|}\left(\sum_{a\in
A(S^{\prime},\Delta_{0},T(v_{i}))}|CC_{u}(a,S^{\prime})|-\sum_{a\in
A(S,\Delta_{0},T(v_{i}))}|CC_{u}(a,S)|\right)=$
$=U(u,B_{i},\Delta_{0},|A|,T(v_{i}))-U(u,S\cap
T(v_{i}),\Delta_{0},|A|,T(v_{i}))\geq 0$

Finally, since $S$ is a $(\Delta_{0},|A|,m,\overline{m},T(v))-$BR-strategy we
conclude that
$U(u,S^{\prime},\Delta_{0},|A|,T(v))=U(u,S,\Delta_{0},|A|,T(v))$.

Therefore, $S^{\prime}$ has maximum $(\Delta_{0},|A|,T(v))-$restricted utility
over all $(\Delta_{0},m,\overline{m},T(v))-$strategies, as we wanted to see.

∎

######  Definition 4.16.

Suppose that $B_{i}$ are $(\Delta_{0},|A|,m_{i},T(v_{i}))$-BR-strategies for
each $i=1,...,k(v)$ with $m_{1}+...+m_{k(v)}=m$. Let $I\subseteq[k(v)]$ be the
subset of indices $i$ for which $B_{i}=\emptyset$ and let
$\overline{I}=[k(v)]\setminus I$.

$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle B_{1}$$\displaystyle v_{1}$$\displaystyle
B_{2}$$\displaystyle B_{3}$$\displaystyle B_{4}$$\displaystyle
v$$\displaystyle v_{2}$$\displaystyle v_{3}$$\displaystyle
v_{4}$$\displaystyle 0$$\displaystyle 0$$\displaystyle 0$$\displaystyle
1^{+}$$\displaystyle I=\\{1,2,4\\}$$\displaystyle\overline{I}=\\{3\\}$
$\displaystyle\begin{array}[]{{>{\displaystyle}l}}u\\\
\end{array}$$\displaystyle v_{1}$$\displaystyle 0/1$$\displaystyle
v$$\displaystyle v_{2}$$\displaystyle v_{3}$$\displaystyle
v_{4}$$\displaystyle 0$$\displaystyle 0$$\displaystyle 0$$\displaystyle
1^{+}$$\displaystyle 0/1$$\displaystyle 0/1$$\displaystyle=$

Let $J_{=}\subseteq I$ be such that $-\alpha|J_{=}|+\frac{1}{|A|}\sum_{j\in
J_{=}}|T(v_{j})|$ is maximum among all subsets $Z\subseteq I$ verifying:

$\Delta(v,\left(\cup_{i\in\overline{I}}B_{i}\right)\cup\left(\cup_{j\in
Z}\left\\{v_{j}\right\\}\right))=\Delta_{0}$

Similarly, let $J_{>}\subseteq I$ be such that
$-\alpha|J_{>}|+\frac{1}{|A|}\sum_{j\in J_{>}}|T(v_{j})|$ is maximum among all
subsets $Z\subseteq I$ verifying:

$\Delta(v,\left(\cup_{i\in\overline{I}}B_{i}\right)\cup\left(\cup_{j\in
Z}\left\\{v_{j}\right\\}\right))>\Delta_{0}$

Finally, define
$S_{=}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]=\left(\cup_{i\in\overline{I}}B_{i}\right)\cup\left(\cup_{j\in
J_{=}}\left\\{v_{j}\right\\}\right)$ if such subset $J_{=}$ exists and
$S_{>}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]=\left(\cup_{i\in\overline{I}}B_{i}\right)\cup\left(\cup_{j\in
J_{>}}\left\\{v_{j}\right\\}\right)$ if such subset $J_{>}$ exists.

######  Proposition 4.17.

Let $B_{j}$ be a $(\Delta_{0},m_{j},T(v_{j}))-$strategy for $j=1,...,k(v)$ and
let $m=m_{1}+...+m_{k(v)}$. Then
$S_{=}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$ is a
$(\Delta_{0},m+1,\overline{m},T(v))$-strategy and
$S_{>}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$ is a
$(\Delta_{0},m,\overline{m},T(v))-$strategy otherwise.

###### Proof.

Let $x$ denote the symbol $=$ or $>$ and let
$S=S_{x}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$. If
$i\in\overline{I}\cup(I\setminus J_{x})$ and $z\in\mathcal{U}[T(v_{i})]$, then
using Lemma 3.5 $\Delta(z,S)=\Delta(z,S\cap T(v_{i}))=\Delta(z,B_{i})$ so that
$|A(S,\Delta_{0},T(v_{i}))|=m_{i}$. Suppose now that $i\in J_{x}$. Since the
only links to $B_{i}$ that we are adding in this case is the link to the node
$v_{i}$, then it is clear, using Lemma 3.5 that $\Delta(z,S)=\Delta(z,S\cap
T(v_{i}))=\Delta(z,B_{i}\cup\left\\{v_{i}\right\\})=\Delta(z,B_{i})$ for any
$z\in\mathcal{U}[T(v_{i})\setminus\left\\{v_{i}\right\\}]$.

Furthermore, when $z\in\mathcal{U}_{1}(G^{\prime})$ is a vulnerable meta-node
from $v_{i}\in V_{1}(G^{\prime})$ with $i\in J_{x}$, then
$\Delta(z,S)=\Delta(z,\emptyset)$. Therefore, the number of vulnerable meta-
nodes from $T(v_{i})$ achieving a delta value equal to $\Delta_{0}$ is
$|A(B_{i},\Delta_{0},T(v_{i})\setminus\left\\{v_{i}\right\\})|+\widetilde{m}(v_{i},\Delta_{0})=|A(B_{i},\Delta_{0},T(v_{i}))|=m_{i}$.

Finally, by construction, the delta value of $v$ satisfies that it is equal to
$\Delta_{0}$ if $x$ equals $=$ and therefore in this case the cardinality of
the restricted attack set $A(S,\Delta_{0},T(v))$ is one unit larger than $m$
or greater than $\Delta_{0}$ otherwise and then in this case the cardinality
of the restricted attack set $A(S,\Delta_{0},T(v))$ equals exactly $m$. This
completes the proof of the result.

∎

######  Theorem 4.18.

Suppose that $m_{1},...,m_{k(v)}$ with $m_{1}+...+m_{k(v)}=m$ are given and
$B_{j}$ is a $(\Delta_{0},|A|,m_{j},T(v_{j}))$-BR-strategy for each
$j=1,...,k(v)$. Also, let $S_{x}=S_{x}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$
with $x\in\left\\{=,>\right\\}$. Then, $S_{=}$ maximises
$U(u,\cdot,\Delta_{0},|A|,m+1,T(v))$ over all
$(\Delta_{0},m+1,\overline{m},T(v))-$strategies and $S_{>}$ maximises
$U(u,\cdot,\Delta_{0},|A|,m,T(v))$ over all
$(\Delta_{0},m,\overline{m},T(v))-$strategies.

###### Proof.

We start proving the case $x$ equals $=$, the other case $x$ equals $>$ can be
proved analogously.

Let $S=S_{=}$. We show that $U(u,S,\Delta_{0},|A|,T(v))$ is the maximum
utility that any $(\Delta_{0},|A|,m+1,\overline{m},T(v))-$strategy can attain.
In order to do this let $S^{\prime}$ be a
$(\Delta_{0},|A|,m+1,\overline{m},T(v))-$BR-strategy and then we show that
$U(u,S,\Delta_{0},|A|,T(v))=U(u,S^{\prime},\Delta_{0},|A|,T(v))$.

Since $S^{\prime}$ is a $(\Delta_{0},|A|,m+1,\overline{m},T(v))$-BR-strategy,
and $B_{i}$ are $(\Delta_{0},|A|,m_{i},T(v_{i}))-$BR-strategies then
$S^{\prime\prime}=\cup_{i\in\overline{I}}B_{i}\cup(S^{\prime}\setminus\cup_{i\in\overline{I}}T(v_{i}))$
is a $(\Delta_{0},|A|,m+1,\overline{m},T(v))-$BR-strategy due to Proposition
4.15.

From this we get that:

$U(u,S^{\prime},\Delta_{0},|A|,T(v))=U(u,S^{\prime\prime},\Delta_{0},|A|,T(v))$

Therefore, it is enough if we prove that
$U(u,S,\Delta_{0},|A|,T(v))=U(u,S^{\prime\prime},\Delta_{0},|A|,T(v))$.

Now notice that the following results hold. On the one hand, we have that
$U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=U(u,B_{j},\Delta_{0},|A|,T(v_{j}))$ for
every $j\in\overline{I}$ because $S^{\prime\prime}\cap T(v_{j})=B_{j}$ and, by
construction, there is no $(S,\Delta_{0},T(v_{j}))-$blocking pair with $j\in
J_{=}$ because there exists only one element from $S$ in $T(v_{j})$ which is
$v_{j}$. On the other hand, let $j\in J^{\prime}$, where $J^{\prime}$ is the
subset of subindices $j$ from $I$ such that $S^{\prime\prime}\cap
T(v_{j})\neq\emptyset$ i.e., $|S^{\prime\prime}\cap T(v_{j})|=1$, because, for
each $i\in I$ we know by Proposition 4.11 that $|S^{\prime\prime}\cap
T(v_{i})|\leq 1$. We claim that there does not exist any
$(S^{\prime\prime},\Delta_{0},T(v_{j}))-$blocking pair with $j\in J^{\prime}$
neither. This is because of the following reasoning: If $(a,b)$ is such a
$(S^{\prime\prime},\Delta_{0},T(v_{j}))$-blocking pair, first we have that
$\Delta(a,\emptyset)<\Delta(a,S^{\prime\prime})=\Delta_{0}$, because of the
property $\Delta(z,Z)\leq\Delta(z,Z^{\prime})$ whenever $Z\subseteq
Z^{\prime}$ together with the fact that $|S^{\prime\prime}\cap T(v_{j})|=1$ by
hypothesis. In second place, since $B_{j}=\emptyset$ and $B_{j}$ is a
$(\Delta_{0},T(v_{j}),m_{j})$-strategy (in fact $B_{j}$ is a
$(\Delta_{0},|A|,T(v_{j}),m_{j})$-BR-strategy) then
$\Delta(a,\emptyset)=\Delta(a,B_{j})\geq\Delta_{0}$ for every
$a\in\mathcal{U}[T(v_{j})]$. Hence we have that
$\Delta_{0}\leq\Delta(a,\emptyset)<\Delta_{0}$, which is a contradiction.

Therefore, combining these results together with Lemma 4.8 we obtain that
$CC_{u}(a,B_{j})=CC_{u}(a,\emptyset)$ for every $a\in A(S\cap
T(v_{j}),\Delta_{0},T(v_{j}))$ with $j\in J_{=}$ and
$CC_{u}(a,S^{\prime\prime}\cap T(v_{j}))=CC_{u}(a,\emptyset)$ for every $a\in
A(S^{\prime\prime}\cap T(v_{j}),\Delta_{0},T(v_{j}))$ with $j\in J^{\prime}$.
Hence, for every $j\in J_{=}$:

$U(u,B_{j},\Delta_{0},|A|,T(v_{j}))=-\alpha+U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))$

And, similarly, for every $j\in J^{\prime}$:

$U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=-\alpha+U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))$

Furthermore, $U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))$ for
every $j\in I\setminus J^{\prime}$ and $U(u,S\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))$ for
every $j\in I\setminus J_{=}$. From all these relationships we obtain:

$\sum_{j=1}^{k(v)}U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=\sum_{j\in\overline{I}}U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))+$ $+\sum_{j\in
J^{\prime}}U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))+\sum_{j\in I\setminus
J^{\prime}}U(u,S^{\prime\prime}\cap T(v_{j}),\Delta_{0},|A|,T(v_{j}))=$
$=\sum_{j\in\overline{I}}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))+\sum_{j\in
J^{\prime}}\left(-\alpha+U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))\right)+$
$+\sum_{j\in I\setminus
J^{\prime}}U(u,\emptyset,\Delta_{0},|A|,T(v_{j}))=\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))-\alpha|J^{\prime}|$

And, similarly:

$\sum_{j=1}^{k(v)}U(u,S\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))=\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))-\alpha|J_{=}|$

Now, using the formula from Proposition 3.8, we obtain:

$U(u,S^{\prime\prime},\Delta_{0},|A|,T(v))=$
$=\sum_{j=1}^{k(v)}U(u,S^{\prime\prime}\cap
T(v_{j}),\Delta_{0},|A|,T(v_{j}))+\frac{1}{|A|}\left(|\overline{T(v)}|+\sum_{j\in\overline{I}\cup
J^{\prime}}|T(v_{j})|\right)=$
$=\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))-\alpha|J^{\prime}|+\frac{1}{|A|}\left(|\overline{T(v)}|+\sum_{j\in\overline{I}\cup
J^{\prime}}|T(v_{j})|\right)$

And, similarly:

$U(u,S,\Delta_{0},|A|,T(v))=$
$=\sum_{j=1}^{k(v)}U(u,B_{j},\Delta_{0},|A|,T(v_{j}))-\alpha|J_{=}|+\frac{1}{|A|}\left(|\overline{T(v)}|+\sum_{j\in\overline{I}\cup
J_{=}}|T(v_{j})|\right)$

Therefore, by construction of
$S=S_{=}[B_{1},...,B_{k(v)};m_{1},...,m_{k(v)}]$,

$U(u,S,\Delta_{0},|A|,T(v))-U(u,S^{\prime\prime},\Delta_{0},|A|,T(v))=$
$=-\alpha(|J_{=}|-|J^{\prime}|)+\frac{1}{|A|}\left(\sum_{j\in
J_{=}}|T(v_{j})|-\sum_{j\in J^{\prime}}|T(v_{j})|\right)\geq 0$

Implying
$U(u,S,\Delta_{0},|A|,T(v))=U(u,S^{\prime\prime},\Delta_{0},|A|,T(v))$, as we
wanted to see. ∎

##  5 Computing a BR in Polynomial Time

Finally, we have reached the last section in which we are ready to give the
main algorithm to compute the best response. We use a dynamic programming
approach exploiting all the main results of the previous sections. More
precisely, the main technique in our algorithm has some reminiscence to the
knapsack-problem, although is considerably more complex and involved. In order
to understand our algorithm we introduce some arrays that help us to obtain a
final solution.

###  5.1 Definition of the arrays

Let $M[v,\Delta_{0},|A|,m]$ be the maximum $(\Delta_{0},|A|,T(v))-$restricted
utility a $(\Delta_{0},m,T(v))-$strategy can attain or $-\infty$ if there does
not exist any such $(\Delta_{0},m,T(v))-$strategy. In case that
$M[v,\Delta_{0},|A|,m]\neq-\infty$ then $S[v,\Delta_{0},|A|,m]$ will be such a
$(\Delta_{0},|A|,m,T(v))-$BR-restricted strategy.

Auxiliary arrays. Let $v\in V(T)$ be a node from the meta-tree. For each
$i=1,...,k(v)$ define $T^{i}(v)=\cup_{j\geq 1}^{i}T(v_{j})$. We introduce an
auxiliary array that can help us to compute the values
$M[v,\Delta_{0},|A|,m]$:

_(a) If $v\in V_{1}(G^{\prime})$._ Let $M_{aux}[v,\Delta_{0},|A|,m,i]$ be the
maximum $(\Delta_{0},|A|,T^{i}(v))-$restricted utility a
$(\Delta_{0},m,T^{i}(v))-$strategy can attain or $-\infty$ if there does not
exist any such $(\Delta_{0},m,T^{i}(v))-$strategy. In case that
$M_{aux}[v,\Delta_{0},|A|,m,i]\neq\infty$ then $S_{aux}[v,\Delta_{0},|A|,m,i]$
will be such a $(\Delta_{0},|A|,m,T^{i}(v))-$BR-restricted strategy.

_(b) If $v\in V_{\geq 2}(G^{\prime})$_. Let
$M_{aux}[v,\Delta_{0},|A|,m,i,CC_{u},CC_{u,2},JJ]$ be the array with value in
every position to be the maximum $(\Delta_{0},|A|,T^{i}(v))-$restricted
utility a $(\Delta_{0},m,T^{i}(v))-$strategy $S\subseteq T^{i}(v)$ can attain
given that

(i) $|CC_{u}(v,S)|=|\overline{T(v)}|+\sum_{S\cap
T(v_{j})\neq\emptyset}|T(v_{j})|=CC_{u}$

(ii) $|\overline{T(v)}|^{2}+\sum_{S\cap
T(v_{j})\neq\emptyset}|T(v_{j})|^{2}=CC_{u,2}$

(iii) $-\alpha|J(S)|+\frac{1}{|A|}\sum_{j\in J(S)}|T(v_{j})|=JJ$ where $J(S)$
is the subset of indices $j$ with $1\leq j\leq i$ satisfying $S\cap
T(v_{j})=\left\\{v_{j}\right\\}$.

Or $-\infty$ if such a $(\Delta_{0},m,T^{i}(v))-$strategy does not exist. In
case that $M_{aux}[v,\Delta_{0},|A|,m,i,CC_{u},CC_{u,2},JJ]\neq-\infty$ then
$S_{aux}[v,\Delta_{0},|A|,m,i,CC_{u},CC_{u,2},JJ]$ will be such a
$(\Delta_{0},|A|,T^{i}(v),m)-$BR-restricted strategy.

###  5.2 Recurrence relations

We have seen in the previous sections how a restricted BR-strategy for a node
$v\in V(T)$ can be obtained in terms of the restricted BR-strategies for the
corresponding subtrees $T(v_{1}),...,T(v_{k(v)})$. This is what we are going
to exploit in the next results.

The arrays $M,S$ in terms of the arrays $M_{aux},S_{aux}$.

First, we see how can we compute the corresponding values from $M,S$ assuming
that we have previously computed the corresponding values from
$M_{aux},S_{aux}$, and distinguishing between the two cases $v\in
V_{1}(G^{\prime})$ and $v\in V_{\geq 2}(G^{\prime})$.

These results follow easily from the definitions of the arrays:

_(a) Suppose that $v\in V_{1}(G^{\prime})$._ Then:

$M[v,\Delta_{0},|A|,m]=M_{aux}[v,\Delta_{0},|A|,m-\widetilde{m}(v,\Delta_{0}),k(v)]$

And if $M[v,\Delta_{0},|A|,m]\neq-\infty$ then:

$S[v,\Delta_{0},|A|,m]=S_{aux}[v,\Delta_{0},|A|,m-\widetilde{m}(v,\Delta_{0}),k(v)]$

_(b) Suppose that $v\in V_{\geq 2}(G^{\prime})$._ Then notice first of all the
next result.

For any strategy $S$:

$\Delta(v,S)=\Delta(v,\emptyset)-\left(|\overline{T(v)}|^{2}+\sum_{S\cap
T(v_{j})\neq\emptyset}|T(v_{j})|^{2}\right)+|CC_{u}(v,S)|^{2}$

Therefore, given the parameters $\Delta_{0}$, $CC_{u,2}$ and $CC_{u}$ the next
value indicates whether $v$ is attacked in the BR-strategy we are building (or
$-\infty$ if there is no such BR-strategy):

$\epsilon(v,\Delta_{0},CC_{u},CC_{u,2})=\begin{cases}0&\text{if
$\Delta_{0}<\Delta(v,\emptyset)-CC_{u,2}+CC_{u}^{2}$}\\\ 1&\text{if
$\Delta_{0}=\Delta(v,\emptyset)-CC_{u,2}+CC_{u}^{2}$}\\\ -\infty&\text{
otherwise}\end{cases}$

Then:

$M[v,\Delta_{0},|A|,m]=$ $=\max_{\begin{subarray}{c}CC_{u},CC_{u,2},JJ\\\
\epsilon(v,\Delta_{0},CC_{u},CC_{u,2})\neq-\infty\end{subarray}}M_{aux}[v,\Delta_{0},|A|,m-\epsilon(v,\Delta_{0},CC_{u},CC_{u,2}),k(v),CC_{u},CC_{u,2},JJ]$

If $M_{aux}[v,\Delta_{0},|A|,m]\neq-\infty$ consider

$CC_{u}^{*},CC_{u,2}^{*},JJ^{*}=$
$=\arg\max_{\begin{subarray}{c}CC_{u},CC_{u,2},JJ\\\
\epsilon(v,\Delta_{0},CC_{u},CC_{u,2})\neq-\infty\end{subarray}}M_{aux}[v,\Delta_{0},|A|,m-\epsilon(v,\Delta_{0},CC_{u},CC_{u,2}),k(v),CC_{u},CC_{u,2},JJ]$

Finally we we set
$S[v,\Delta_{0},|A|,m]=S_{aux}[v,\Delta_{0},|A|,m,i,CC_{u}^{*},CC_{u,2}^{*},JJ^{*}]$.

The arrays $M_{aux},S_{aux}$ in terms of the arrays $M,S,M_{aux},S_{aux}$.

Here comes a trickier part. As before, we need to distinguish between the two
scenarios $v\in V_{1}(G^{\prime})$ and $v\in V_{\geq 2}(G^{\prime})$.

_(a) Suppose that $v\in V_{1}(G^{\prime})$._

In this scenario we distinguish the main recurrence (the case $i>0$) and the
corresponding initialization of the array (the case $i=0$).

  * •

If $i>0$. We know by Theorem 4.14 that by the disjoint union of the restricted
BR-strategies from $T(v_{i})$ with $1\leq i\leq k(v)$ we obtain a restrict BR-
strategy for $T(v)$ with no need of buying more links. In view of this we set:

$M_{aux}[v,\Delta_{0},|A|,m,i]=\max_{0\leq m_{i}\leq
m}\left\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1]+M[v_{i},\Delta_{0},|A|,m_{i}]\right\\}$

And if $M_{aux}[v,\Delta_{0},|A|,m,i]\neq-\infty$ consider

$m_{i}^{*}=\operatorname*{arg\,max}_{0\leq m_{i}\leq
m}\left\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1]+M[v_{i},\Delta_{0},|A|,m_{i}]\right\\}$

Then in such case we can set
$S_{aux}[v,\Delta_{0},|A|,m,i]=S_{aux}[v,\Delta_{0},|A|,m-m_{i}^{*},i-1]\cup
S[v_{i},\Delta_{0},|A|,m_{i}^{*}]$.

  * •

Otherwise, if $i=0$, then $M_{aux}[v,\Delta_{0},|A|,m,i]=-\infty$ if $m\neq 0$
and $M_{aux}[v,\Delta_{0},|A|,m,i]=0$ and
$S_{aux}[v,\Delta_{0},|A|,m_{i}]=\emptyset$ otherwise.

_(b) Suppose that $v\in V_{\geq 2}(G^{\prime})$._

As before, we distinguish the main recurrence (the case $i>0$) and the
corresponding initialization of the array (the case $i=0$).

  * •

If $i>0$, let $B_{i}$ be the restricted BR-strategy corresponding to the
subtree $T(v_{i})$. We distinguish between three situations:

Scenario 1: if $B_{i}\neq\emptyset$, then $u$ does not need to buy any link to
$T(v_{i})$ using Theorem 4.18.

Scenario 2: if $B_{i}=\emptyset$. Then, again by Theorem 4.18 $u$ buys at most
one link to $B_{i}$ so there are two possible cases:

Case 2.1: $u$ buys one link towards $\left\\{v_{i}\right\\}$.

Case 2.2: $u$ buys no link towards $T(v_{i})$. Therefore:

$M_{aux}[v,\Delta_{0},|A|,m,i,CC_{u},CC_{u,2},JJ]=\max(M_{1},M_{2},M_{3})$

Where $M_{1},M_{2},M_{3}$ correspond to scenario 1 and scenario 2 cases 2.1
and 2.2, respectively:

$M_{1}=\max_{0\leq m_{i}\leq
m}\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1,CC_{u}-|T(v_{i})|,CC_{u,2}-|T(v_{i})|^{2},JJ]+$
$+M[v_{i},\Delta_{0},|A|,m_{i}]+\frac{1}{|A|}|T(v_{i})|\\}$ $M_{2}=\max_{0\leq
m_{i}\leq
m}\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1,CC_{u}-|T(v_{i})|,CC_{u,2}-|T(v_{i})|^{2},JJ-\alpha+\frac{|T(v_{i})|}{|A|}]+$
$+M[v_{i},\Delta_{0},|A|,m_{i}]+\frac{1}{|A|}|T(v_{i})|\\}$ $M_{3}=\max_{0\leq
m_{i}\leq
m}\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1,CC_{u},CC_{u,2},JJ]+M[v_{i},\Delta_{0},|A|,m_{i}]\\}$

If $M_{1}\neq-\infty$ let

$m_{i,1}^{*}=\operatorname*{arg\,max}_{0\leq m_{i}\leq
m}\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1,CC_{u}-|T(v_{i})|,CC_{u,2}-|T(v_{i})|^{2},JJ]+$
$+M[v_{i},\Delta_{0},|A|,m_{i}]+\frac{1}{|A|}|T(v_{i})|\\}$

Then let
$S_{1}=S_{aux}[v,\Delta_{0},|A|,m-m_{i,1}^{*},i-1,CC_{u}-|T(v_{i})|,CC_{u,2}-|T(v_{i})|^{2},JJ]\cup
S[v_{i},\Delta_{0},|A|,m_{i,1}^{*}]$.

If $M_{2}\neq-\infty$ let

$m_{i,2}^{*}=\operatorname*{arg\,max}_{0\leq m_{i}\leq
m}\left\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1]+M[v_{i},\Delta_{0},|A|,m_{i}]\right\\}$

Then let $S_{2}=\left\\{v_{i}\right\\}\cup
S_{aux}[v,\Delta_{0},|A|,m-m_{i,2}^{*},i-1,CC_{u}-|T(v_{i})|,CC_{u,2}-|T(v_{i})|^{2},JJ]\cup
S[v_{i},\Delta_{0},|A|,m_{i,2}^{*}]$.

If $M_{3}\neq-\infty$ let

$m_{i,3}^{*}=\operatorname*{arg\,max}_{0\leq m_{i}\leq
m}\\{M_{aux}[v,\Delta_{0},|A|,m-m_{i},i-1,CC_{u},CC_{u,2},JJ]+M[v_{i},\Delta_{0},|A|,m_{i}]\\}$

Then let
$S_{3}=S_{aux}[v,\Delta_{0},|A|,m-m_{i,3}^{*},i-1,CC_{u},CC_{u,2},JJ]\cup
S[v_{i},\Delta_{0},|A|,m_{i,3}^{*}]$.

Then if $\max(M_{1},M_{2},M_{3})\neq-\infty$ we set
$S_{aux}[v,\Delta_{0},|A|,m,i]=S_{j^{*}}$ where
$j^{*}=\operatorname*{arg\,max}_{1\leq j\leq 3}\\{M_{j}\\}$.

  * •

Otherwise, if $i=0$, then:

$M_{aux}[v,\Delta_{0},|A|,m,0,CC_{u},CC_{u,2},JJ]=-\infty$

If $m\neq 0$, $CC_{u}\neq 0$, $CC_{u,2}\neq 0$ or $JJ\neq 0$. Otherwise:

$M_{aux}[v,\Delta_{0},|A|,0,0,0,0,0]=0$
$S_{aux}[v,\Delta_{0},|A|,0,0,0,0,0]=\emptyset$

###  5.3 Final recurrence

Let

$\Delta_{1}^{*},|A|_{1}^{*}=\operatorname*{arg\,max}_{\Delta_{0},|A|}M[u,\Delta_{0},|A|,|A|]$

And

$\Delta_{2}^{*},|A|_{2}^{*}=\operatorname*{arg\,max}_{\Delta_{0},|A|}M[u,\Delta_{0},|A|+1,|A|]$

Then, by Proposition 3.4 we can pick as a best response
$(S[u,\Delta_{1}^{*},|A|_{1}^{*},|A|_{1}^{*}],1)$ if
$M[u,\Delta_{1}*,|A|_{1}^{*},|A|_{1}^{*}]-\beta>M[u,\Delta_{2}^{*},|A|_{2}^{*}+1,|A|_{2}^{*}]$
or $(S[u,\Delta_{2}^{*},|A|_{2}^{*}+1,|A|_{2}^{*}],0)$ otherwise.

Furthermore, notice that there are a polynomial (in $n$) number of possible
values taking at most polynomial values (again, with respect $n$) for the
distinct parameters of the array, then our algorithm can be computed in
polynomial time, which is what the conjecture in this particular case claims.

Even though our algorithm solves the best response problem considering that
the initial graph resulting from the strategies of all players but $u$, is
connected, we believe that our techniques can be adapted to solve the problem
in the general case.

## References

  * [1] C. Àlvarez, M. J. Blesa, A. Duch, A. Messegué, and M.J. Serna. _Celebrity Games_. Theor. Comput. Sci. 648: 56–71, 2016.
  * [2] V. Bala and S. Goyal. _A Noncooperative Model of Network Formation. Econometrica_ , 68(5):1181–1229, 2000.
  * [3] S. Goyal, S. Jabbari, M. Kearns, S. Khana, and J. Morgenstern. _Strategic Network Formation with Attack and Immunization_. In: WINE 2016, pp. 429–443, 2016.
  * [4] D. Biló, L. Gualà, S. Leucci, and G. Proietti. _Locality-Based Network Creation Games_.In: SPAA 2014, pp. 277—286, 2014.
  * [5] D. Biló, L. Gualà, and G. Proietti. _Bounded-distance Network Creation Games_. ACM TEAC, 3 (3): 16:1–16:20, 2015.
  * [6] A. Chauhan, P. Lenzner, A. Melnichenko, and M. Münn. _On Selfish Creation of Robust Networks_. In: SAGT 2016, pp. 141–152, 2016.
  * [7] A. Cord-Landwehr and P. Lenzner. _Network Creatio Games: Think global-Act local_. In: MFCS 2015, pp. 248–260, 2015.
  * [8] S. Ehsani, S. S. Fadaee, M. Fazli, A. Mehrabian, S. S. Sadeghabad, M. A. Safari, and M. Saghafian. _A Bounded Budget Network Creation Game_. ACM Transactions on Algorithms, 11(4):34:1–34:25, 2015.
  * [9] A. Fabrikant, A. Luthra, E.N Maneva, C. H. Papadimitriou, and S. Shenker. _On a Network Creation Game_. In: PODC 2003, pp. 347–351, 2003.
  * [10] Friedrich, T., Ihde, S., Keßler, C., Lenzner, P., Neubert, S., Schumann, D.: _Efficient best response computation for strategic network formation under attack_. In: SAGT 2017, pp. 199–211 (2017).