## 3 Complexity of Computing a Best Response
### Model \(\mathcal{M}_{1}\)
Moreover, at least one of the following two conditions holds: \(|L_{1}|=1\) or \(L_{1}\subseteq(\sigma_{u}^{*}\cup S)\)._  
Proof: We start by noticing that when \(|L_{1}|\geq 2\) and \(L_{1}\
ot\subseteq(\sigma_{u}^{*}\cup S)\) we can find a network \(G\in\mathcal{G}\) that becomes disconnected when player \(u\) changes her strategy from \(\sigma\) to \(\sigma^{*}\). This implies that \(\sigma_{u}^{*}\) cannot be a best response for \(u\) and proves the second part of our claim. Given a possible strategy \(\sigma_{u}^{\prime}\) for \(u\), define \(f(\sigma_{u}^{\prime})=|\{i\in\{2,\ldots,\ell\}\text{ s.t. }\sigma_{u}^{\prime}\cap L_{i}\
eq\emptyset\text{ and }L_{i} \
ot\subseteq\sigma_{u}^{\prime}\}|\). In other words, \(f(\sigma_{u}^{\prime})\) is the number of levels \(L_{i}\) with \(i\geq 2\) for which \(u\) is buying some but not all edges towards the vertices in \(L_{i}\), according to strategy \(\sigma_{u}^{\prime}\). We prove that if \(\sigma_{u}^{\prime}\) is a strategy for which \(f(\sigma_{u}^{\prime\prime})>0\), then there exists another strategy \(\sigma_{u}^{\prime\prime}\) for \(u\) such that \(f(\sigma_{u}^{\prime\prime})<f(\sigma_{u}^{\prime})\) and \(\Delta(\sigma_{u},\sigma_{u}^{\prime\prime})\geq\Delta(\sigma_{u},\sigma_{u}^ {\prime\prime})\). As \(f(\sigma_{u}^{\prime})>0\) we are always able to find an index \(i\) for which neither \(L_{i}\cap\sigma_{u}^{\prime}=\emptyset\) nor \(L_{i}\subseteq\sigma_{u}^{\prime}\). Define \(L_{i}^{\prime}=L_{i}\cap\sigma_{u}^{\prime}\) and let \(j\in\{1,2,\ldots,i-1\}\) be the maximum index for which \(|L_{j}|=1\), if any. If such an index exists, we let \(\sigma_{u}^{\prime\prime}=(\sigma_{u}^{\prime}\setminus L_{i}^{\prime})\cup L _{j}\); otherwise (if \(j\) does not exist), we let \(\sigma_{u}^{\prime\prime}=\sigma_{u}^{\prime}\setminus L_{i}^{\prime}\). By our choice of \(\sigma_{u}^{\prime\prime}\), we must have both \(f(\sigma_{u}^{\prime\prime})<f(\sigma_{u}^{\prime})\) and \(|\sigma_{u}^{\prime\prime}|\leq|\sigma_{u}^{\prime}|\). Moreover, invoking Lemmas 2 and 3, we obtain \(\delta(L_{j},V)\leq\delta(L_{i}^{\prime},V)\). It follows that \(\delta(\sigma_{u}^{\prime\prime},V)\leq\delta(\sigma_{u}^{\prime},V)\) and hence, for every \(G\in\mathcal{G}\):  
\[C_{u}((\sigma_{-u},\sigma_{u}^{\prime\prime}),G)=\alpha\cdot|\sigma_{u}^{ \prime\prime}|+\delta(\sigma_{u}^{\prime\prime},V)\leq\alpha\cdot|\sigma_{u}^ {\prime}|+\delta(\sigma_{u}^{\prime},V)=C_{u}((\sigma_{-u},\sigma_{u}^{ \prime}),G),\]  
thus showing that \(\Delta(\sigma_{u},\sigma_{u}^{\prime})\geq\Delta(\sigma_{u},\sigma_{u}^{ \prime\prime})\). We can now design a polynomial-time algorithm to compute a best-response in \(\mathcal{M}_{1}\):  
Theorem 5: _In \(\mathcal{M}_{1}\) the best response of a player can be computed in polynomial time for MaxNCG._  
Proof: We will design a dynamic programming algorithm that computes a best-response strategy satisfying the conditions of Lemma 4. For \(i=0,\ldots,\ell\) and \(\eta=0,\ldots,n-2\), we denote by \(A[i,\eta]\) the minimum criminality of a set of vertices \(X\) such that \(L_{i}\subseteq X\) and \(\delta\big{(}X,\bigcup_{h=1,\ldots,i}L_{h}\big{)}\leq\eta-2\). The idea is that \(A[i,\eta]\) will be (proportional to) the minimum building cost needed to ensure that the distance between \(u\) and all the vertices in \(\bigcup_{h=1,\ldots,i}L_{h}\) will not exceed \(\eta+1\) with the restriction that \(u\) can only buy edges towards sets of vertices \(X\) for which \(L_{i}\subseteq X\subseteq\bigcup_{h=1,\ldots,i}L_{h}\). For technical simplicity (and with a small abuse of notation) we will consider \(L_{0}\) to be the empty set. Moreover, we define \(g(i,\eta)\) as the smallest index for which \(0\leq g(i,\eta)\leq i\) and \(\delta(L_{g(i,\eta)}\cup L_{i},\bigcup_{h=g(i,\eta),\ldots,i}L_{h})\leq\eta\).