## 3 Complexity of Computing a Best Response
### Model \(\mathcal{M}_{2}\)  
In model \(\mathcal{M}_{2}\), we are able to design polynomial-time algorithms to compute a best-response strategy for a player for both SumNCG and MaxNCG, as the following theorem shows. Theorem 4.1: _In \(\mathcal{M}_{2}\), the best response of a player can be computed in polynomial time for both SumNCG and MaxNCG._  
Proof: Let \(\sigma\) be a strategy profile, where \(\sigma_{u}\) denotes the current strategy of some player \(u\), and let \(T(u)\) be the shortest-path tree (rooted in \(u\)) corresponding to \(u\)'s view of the network \(G(\sigma)\). We now design a dynamic programming algorithm computing a best response \(\sigma_{u}^{x}\) for \(u\) (in polynomial-time). For SumNCG and MaxNCG, our algorithm will respectively solve a variant of the \(k\)_-median_ and the \(k\)_-center_ problem on trees. The input of the \(k\)-median (resp., \(k\)-center) problem is a graph \(H\), and the goal is that of finding a set \(S\) of exactly \(k\) vertices in \(H\) in order to minimize the sum of distances (resp. the _maximum_ distances) between each node in \(H\) and the closest node in \(S\) (Actually, the \(k\)-median problem asks to minimize the _average_ distance between the vertices of \(H\) and the closest vertex in \(S\). However, it is easy to see that this is equivalent to minimizing the sum of the above distances). By deleting \(u\) from \(T(u)\) we are left with a some forest \(F\). Let \(T_{1},\ldots,T_{h}\) be the trees in \(F\) and let \(r_{i}\) be the root of \(T_{i}\). Let \(z=|\sigma_{u}|\). We can assume (w.l.o.g.) that the trees \(T_{i}\) with \(i\leq z\) (for some value of \(z\)) are those for which \(u\) owns the edge \((u,r_{i})\) and that all edges \((u,r_{j})\) for \(j>z\) are owned by \(r_{j}\). For \(i\leq z\) and \(0\leq k<n\), we let \(A[i,k]\) be the cost of an optimal solution the instance of the \(k\)-median (resp. \(k\)-center) problem in which \(H=T_{i}\). Similarly, for \(z<i\leq h\) and \(0\leq k<n\), we let \(A[i,k]\) be the cost of an optimal solution to the instance of a _constrained version_ of the \(k\)-median (resp. \(k\)-center) problem in which \(H=T\) and we additionally require the solution to contain vertex \(r_{i}\). Whenever there is no feasible solution to the above instances (e.g., when \(k\geq|V(T_{i})|\)) we let \(A[i,k]=+\infty\). It is well known both the \(k\)-median and the \(k\)-center problem can be solved in polynomial time when the input graph \(H\) is a trees (and it is easy to see that this is still true for their constrained variants). We now consider the first \(i\) trees and, for each value of \(j\), we compute the minimum _aggregate cost_\(B[i,j]\) that can be obtained by solving \(i\) (possibly constrained) instances of \(k\)-median (resp. \(k\)-center) on the trees \(T_{1},\ldots,T_{i}\) while selecting exactly \(j\) vertices _across all such instances_. More formally, for the \(k\)-median problem, we define  
\[B[i,j]=\min_{ \begin{subarray}{c}j_{1},j_{2},\ldots,j\in\mathbb{N}\\ j_{1}+2_{2}+\cdots+j_{i}=j\end{subarray} }\ \ \sum_{\ell=1}^{i}A[\ell,\,j_{\ell}],\]  
while, for the \(k\)-center problem we define  
\[B[i,j]=\min_{ \begin{subarray}{c}j_{1},j_{2},\ldots,j_{i}\in\mathbb{N}\\ j_{1}+2_{2}+\cdots+j_{i}=j\end{subarray} }\ \ \max\Big{\{}A[\ell,\,j_{\ell}]\,:\,1\leq\ell\leq i \Big{\}}.\]  
Notice that, by definition, \(B[1,j]=A[1,j]\) for both problems. For \(i>1\), we can efficiently compute \(B[i,j]\) using the following recursive formulas. For the \(k\)-median problem we have  
\[B[i,j]=\min_{1\leq t\leq j-i+1}\{A[i,t]+B[i-1,j-t]\},\]  
while, for the \(k\)-center problem,  
\[B[i,j]=\min_{1\leq t\leq j-i+1}\max\{A[i,t],B[i-1,j-t]\}.\]To find the cost of \(u\)'s best response \(\sigma_{u}^{*}\) in SumNCG, we observe that \(n-1+B[h,j]\) is exactly the smallest usage cost incurred by \(u\) if she decides to buy exactly \(j-(h-z)\) edges (as \(h-z\) edges are already owned by the vertices \(r_{i}\) with \(z+1\leq i\leq h\)).