## 2 Convergence  
### Model \(\mathcal{M}_{1}\)  
We start by observing that in \(\mathcal{M}_{1}\) a player \(u\) can only infer the existence of the edges \((x,y)\) for which \(d_{G}(u,y)=d_{G}(u,x)+1\) and no other vertex \(x^{\prime}\
eq x\) satisfies \(d_{G}(u,x)=d_{G}(u,x^{\prime})\) (this captures all the edges incident to \(u\) as the special case \(x=u\)).  
As a consequence, whenever \(u\) has at least two neighbors, _suapping_ (i.e., replacing an owned edge with another one) any of his/her edges will never be an improving response as (in \(u\)'s view) this might cause the resulting network to become disconnected. We summarize this property in the next Lemma.  
\begin{table}
\begin{tabular}{l l l} \hline \hline \multirow{2}{*}{**Convergence**} & **Best-Response** & **PoA** \\  & **Complexity** & **\(\mathcal{P}\)** \\ \hline \(\mathcal{M}_{1}\)Sum: Yes (\(\forall\)_improving_ & Sum: Open & Sum: \(\Theta(\min\{1+\alpha,n\})\) \\ response dynamics (IRD)) & Max: Polynomial & Max: \(\Theta(n)\) if \(\alpha=\Omega(1)\) \\ Max: Yes (\(\forall\) IRD) & & \(\Theta(1+\alpha n)\) if \(\alpha=\Omega(1)\) \\ \hline \(\mathcal{M}_{2}\)Sum: No (\(\exists\)_best_ response & Sum: Polynomial & Sum: \(\Theta(\min\{1+\alpha,n\})\) \\ dynamics (BRD) cycle) & Max: Polynomial & Max: \(\Theta(n)\) if \(\alpha=\Omega(1)\) \\ Max: No (\(\exists\) BRD cycle) & & \(\Theta(1+\alpha n)\) if \(\alpha=O(1)\) \\ \hline \(\mathcal{M}_{3}\)Sum: No (\(\exists\) BRD cycle) & Sum: NP-hard & Sum: \(\Theta(\min\{1+\alpha,n\})\) \\ Max: No (\(\exists\) BRD cycle) & Max: NP-hard & Max: \(\Theta(n)\) if \(\alpha=\Omega(1)\) \\ \(\Theta(1+\alpha n)\) if \\ \(\frac{1}{n-1}\leq\alpha=O(1)\) & & \(\frac{1}{n-1}\leq\alpha=O(1)\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of our results (and open problems). In the first column, convergence (and divergence) are reported w.r.t. either improving or best-response dynamics (improving response dynamics (IRD) and best response dynamics (BRD), resp.). In the second column, we report the time complexity of selecting a best-response strategy.  
**Lemma 1**.: _In both SumNCG and MaxNCG in \(\mathcal{M}_{1}\), any player \(u\) that has an improving response involving edge swaps must have degree \(1\) (and \(u\) must own its sole incident edge)._  
**Theorem 1**.: _In \(\mathcal{M}_{1}\), any improving response dynamics for SumNCG must converge to an equilibrium._  
Proof.: Consider any strategy profile in which no edge is owned by both endpoints, which can be safely assumed as this can only happen in the starting network.  
Notice that, in such a configuration, no edge can be removed by any player (as otherwise the network could become disconnected in the player's view). As the maximum number of edges is upper bounded by \(O(n^{2})\), it suffices to show that any dynamics in which only swap moves are allowed must converge.  
Consider a network \(G\) and player \(u\) that changes her strategy from \(\sigma_{u}\) to \(\sigma_{u}^{\prime}\) (with \(|\sigma_{u}|=|\sigma_{u}^{\prime}|\)) in order to improve her (worst-case) cost. As the cost of player \(u\) in the resulting network \(G^{\prime}\) must be lower than her corresponding cost in \(G\), and since the building cost of \(u\) is unchanged, we know that the usage cost of \(u\) decreases when moving from \(G\) to \(G^{\prime}\).  
In the rest of the proof we will argue that the function \(\Phi(G)=\sum_{x\in V}\sum_{v\