## 3 Complexity of Computing a Best Response
### Model \(\mathcal{M}_{1}\)  
In this section, we design a polynomial-time dynamic programming algorithm that computes a best response of a player for MaxNCG in \(\mathcal{M}_{1}\). Fix a strategy profile \(\sigma\) and a player \(u\), and let \(\ell\) be the eccentricity of \(u\) in \(G(\sigma)\). We will use \(\mathcal{G}\) to refer to the set of all graphs that are compatible with \(u\)'s view in \(\sigma\). Furthermore, we will use the set \(\mathcal{G}^{\prime}\) consisting of all graphs that can be obtained by removing the edges incident to \(u\) from some graph in \(\mathcal{G}\). For \(i=0,\ldots,\ell\), let \(L_{i}\) be the set of vertices at distance exactly \(i\) from \(u\) in \(G(\sigma)\). Finally, for \(X,Y\subseteq V\) and a graph \(G\) having \(V\) as its vertex set, we define \(d_{G}(X,Y)=\max_{y\in Y}\min_{x\in X}d_{G}(x,y)\) and \(\delta(X,Y)=\max_{G\in\mathcal{G}^{\prime}}d_{G}(X,Y)\). With a slight abuse of notation we will write \(\delta(X,y)\) in place of \(\delta(X,\{y\})\) whenever \(y\in V\). Our dynamic programming algorithm will exploit the structural properties of best-response strategies in the worst-case graph that are summarized in the following lemmata. **Lemma 2**: _Let \(\mathcal{O}\subsetneq L^{\prime}_{i}\subsetneq L_{i}\) and \(y\in L_{j}\), with \(i,j>0\). If there exists an index \(0<t\leq\min\{i,j\}\) such that \(|L_{t}|=1\), then let \(h\) be the maximum such index \(t\); otherwise, let \(h=\bot\). Then,_  
\[\delta(L^{\prime}_{i},y)= \begin{cases}j+i-2h&\text{if }h\
eq\bot;\\ +\infty&\text{if }h=\bot.\end{cases} \]  
Proof. : We start by considering the case \(h\
eq\bot\). Let the sole vertex in \(L_{h}\) be \(z\). It is not hard to see that \(\delta(L^{\prime}_{i},y)\leq j+i-2h\) as any \(G\in\mathcal{G}^{\prime}\) must contain (i) some path of length \(i-h\) from \(z\) to each of the vertices in \(L_{i}\), and (ii) a path from \(z\) to \(y\) having a length of \(j-h\). Consider now any tree \(T\in\mathcal{G}\) in which the lowest common ancestor between \(y\) and each vertex in \(L^{\prime}_{i}\) is \(z\) (notice that it is always possible to find such a tree \(T\)). For every \(x\in L^{\prime}_{i}\) we have \(d_{T}(x,y)=j+i-2h\), implying \(\delta(x,y)\geq d_{T}(x,y)=i+i-2h\). We now turn our attention to the case \(h=\bot\). Pick any graph \(G\in\mathcal{G}^{\prime}\) such that (i) \(G\) is disconnected, (ii) all the vertices in \(L_{i}\) belong to the same connected component \(\mathcal{C}\) of \(G\), and (iii) \(y\) is not among the vertices in \(\mathcal{C}\) (again, it is always possible to find that such a graph \(G\)). Then, \(\delta(L^{\prime}_{i},y)=\infty\). **Lemma 3**: _Let \(y\in L_{j}\), with \(j>0\). If there exists an index \(0<t\leq j\) such that \(|L_{t}|=1\), then let \(h\) be the maximum such index; otherwise, let \(h=\bot\). Then, the following holds \(\forall i=1,\ldots,\ell\),_  
\[\delta(L_{i},y)= \begin{cases}j-i&\text{if }i\leq j;\\ j+i-2h&\text{if }h\
eq\bot\text{ and }i>j;\\ +\infty&\text{if }h=\bot\text{ and }i>j;\end{cases} \]  
Proof. : The case \(h=\bot\) and \(i>j\) has already been handled in the proof of Lemma 2, we therefore focus on the two remaining cases. When \(i\leq j\), we have that \(d_{G}(L_{i},y)=j-i\) for all graphs \(G\in\mathcal{G}\), thus \(\delta(L_{i},y)=j-i\). When \(i>j\) and \(h\
eq\bot\), we can consider any tree \(T\in\mathcal{G}\) in which the lowest common ancestor between \(x\in L_{i}\) and \(y\) is the solve vertex \(z\) in \(L_{h}\). Then we have \(d_{T}(x,y)=j+i-2h\) for every \(x\in L_{i}\), which implies that \(\delta(x,y)=j+i-2h\). Define \(S=\{v\in L_{1}:u\in\sigma_{v}\}\) as the set of players \(v\) that have bought the edge \((v,u)\) towards \(u\) in the strategy profile \(\sigma\). We can show the following. Lemma 4: _There exists a best-response strategy \(\sigma_{u}^{*}\) for \(u\) such that, for every \(i=2,\ldots,\ell\), either \(L_{i}\cap\sigma_{u}^{*}=\emptyset\) or \(L_{i}\subseteq\sigma_{u}^{*}\).