## 3 Complexity of Computing a Best Response
### Model \(\mathcal{M}_{3}\)  
As far as model \(\mathcal{M}_{3}\) is concerned, the problem of computing a best response is NP-hard for both SumNCG and MaxNCG, as shown by the following results:  
Theorem 3.2: _Computing a best response for a player in \(\mathcal{M}_{3}\) for SumNCG is NP-hard._  
Proof: We probe the claim by providing a polynomial-time reduction from the (decision version of) the _Minimum Dominating Set problem_ (MDSP) on bipartite graphs to the problem of computing a best response in \(\mathcal{M}_{3}\), similarly to that used in [1]. An instance of MDSP is a pair \(\langle G,k\rangle\) where \(G\) is a graph and \(k\) is a positive integer. The problem is that of deciding whether there exists a subset \(D\) of vertices of \(H\) such that (i) each vertex \(v\in V^{\prime}\) is either in \(D\) or is adjacent to a vertex in \(D\), and (ii) \(|D|\leq k\). It is well-known that MDSP is hard even when \(H\) is bipartite [23]. Let \(\langle H,k\rangle\) be an instance of MDSP where \(H=(U^{\prime}\cup V^{\prime},E^{\prime})\) is a bipartite graph. Fix any value of \(\alpha\in(1,2)\) and let \(G\) be the graph obtained from \(H\) by adding an additional vertex (player) \(u\) along with all the edges in \(\{u\}\times U^{\prime}\). Consider any strategy profile \(\sigma\) such that \(G(\sigma)=G\) and all edges incident to \(u\) are bought solely by \(u\). Notice that each edge \(e\in E^{\prime}\) belongs to at least one shortest path from \(u\) in \(G\) and therefore the view of \(u\) coincides with \(G\) itself. Let \(\sigma_{u}^{*}\) be a best response strategy for \(u\) and notice that the eccentricity of \(u\) in \(G(\sigma_{-u},\sigma_{u}^{*})\) must be at most \(2\). Indeed, if a vertex \(v\) was at a distance of at least \(3\) from \(u\) in \(G(\sigma_{-u},\sigma_{u}^{*})\), then \(u\) could improve her cost by playing \(\sigma_{u}^{*}\cup\{u\}\) instead of \(\sigma_{u}^{*}\) (thus decreasing the distance to \(v\) by at least \(2\) while increasing her building cost by \(\alpha<2\)). It follows that \(\sigma_{u}^{*}\) must be a dominating set of \(H\). We now argue that \(\sigma_{u}^{*}\) must be a minimum dominating set of \(H\). Indeed, given any strategy \(\sigma_{u}^{\prime}\) of player \(u\) for which the eccentricity of \(u\) in \(G(\sigma_{-u},\sigma_{u})\) is at most \(2\), we have that  
\[C_{u}(\sigma_{-u},\sigma_{u}^{\prime}) =\alpha|\sigma_{u}^{\prime}|+\sum_{v\in V^{\prime}}d_{G((\sigma_{- u},\sigma_{u}^{\prime}))}(u,v)\] \[=\alpha|\sigma_{u}^{\prime}|+\sum_{v\in\sigma_{u}^{\prime}}d_{G(( \sigma_{-u},\sigma_{u}^{\prime}))}(u,v)+\sum_{v\in V^{\prime}\setminus\sigma_{ u}^{\prime}}d_{G((\sigma_{-u},\sigma_{u}^{\prime}))}(u,v)\] \[=\alpha|\sigma_{u}^{\prime}|+|\sigma_{u}^{\prime}|+2(|V^{\prime }|-|\sigma_{u}^{\prime}|)=(\alpha-1)|\sigma_{u}^{\prime}|+2|V^{\prime}|,\]  
which is minimized when \(|\sigma_{u}^{\prime}|\) is minimized. The above discussion implies that \(H\) admits a dominating set \(D\) with \(|D|\leq k\) vertices if \(|\sigma^{*}|\leq k\) and concludes the proof. Theorem 4.2: _Computing a best response for a player in \(\mathcal{M}_{3}\) for MaxNCG is NP-hard._  
Proof: As in the proof of Theorem 4.2, we prove the claim through a reduction (similar to than in [3]), from the _Minimum Dominating Set problem_ (MDSP) on bipartite graphs [23]. Given an instance \(\langle H,k\rangle\) of (the decision version) of MDSP on bipartite graphs, we further assume w.l.o.g. that \(H=(U^{\prime}\cup V^{\prime},E^{\prime})\) admits a dominating set \(D^{*}\) of size smaller than \(\frac{|U^{\prime}\cup V^{\prime}|}{2}\) (If this is not the case, then it suffices to consider the graph \(\overline{H}\) obtained from the disjoint union of \(H\) with a star on \(|U^{\prime}\cup V^{\prime}|+2\) vertices centered in some vertex \(v\). \(H^{\prime}\) has \(2|U^{\prime}\cup V^{\prime}|+2\) vertices and admits a minimum dominating set of cardinality at most \(|U^{\prime}\cup V^{\prime}|+1\).