## 4 Hardness of Optimal Nash Equilibria  
We now provide hardness results for computing and approximating optimal Nash equilibria. **Theorem 4.1**. : _The optimal Nash equilibrium for the LMCF Game is NP-Hard to approximate to any constant factor for both the \(SC_{md}\) and \(SC_{stretch}\) social cost functions._  
Proof. : We start by showing that finding the optimal Nash equilibrium for \(SC_{md}\) is NP-hard. Following arguments from [16], a related construction then shows NP-hardness for \(SC_{stretch}\) as well as hardness of approximation for both social cost functions. The proof of Theorem 4.1 is based on the 3-SAT reduction of [16] for the minimal-stretch MST problem, modified with appropriate \"choice\" gadgets between positive and negative literals of the same variable. For the purpose of showing NP-Hardness, the constructed graph \(G\) is 3-SAT represented as the union of the clause-literal bipartite graph with edges of length \(B\), along with additional paths \(E\) between the positive and negative literals of each variable, as well as a destination \(S\) connected to every literal by edges of length \(A\leq B\). The choice gadget for \(E\) is simply a symmetric path of edges with small (meaning even the heaviest edge has small cost) decreasing cost then increasing cost. This replaces the edges of path \(E\) in [16]'s construction. Note that for every positive and negative variable nodes, say \(x\) and \(\bar{x}\), the choice gadget enforces that every Nash tree has either a path from \(x\) to \(\bar{x}\) or vice versa. This is shown in Figure 3. Since each literal is directly connected to \(S\) by an edge shorter than the edge to a clause, the literal with the incoming path from its corresponding choice gadget must necessarily then forward to \(S\) in every Nash tree as well. Moreover, each clause must choose one of its corresponding literals to forward to. Therefore, there are only two possible kinds of paths from a clause to the destination depending on the choice gadget's direction: Zigzagging \(B\to E\to A\) or bypassing \(E\) via \(B\to A\). For every pair of literals, directing \(E\) from \(\bar{x}\) to \(x\) if the corresponding 3-SAT variable assignment is true and from \(x\) to \(\bar{x}\) if it is false, we see that a clause node that directs into its chosen literal does not zigzag. Since every Nash equilibrium for \(G\) uniquely specifies the direction of all paths \(E\) between literals and vice versa, the reduction is clear: The 3-SAT instance is satisfiable if there existsa choice of all path directions for \(E\) such that no clause zigzags. For sufficiently long \(B\), zigzagging is the only way to increase the directed diameter, and so NP-hardness for optimal \(SC_{md}\) follows. For demonstrating NP-hardness for \(SC_{stretch}\) as well as hardness of approximation, the construction is augmented by an additional node \(R\) connected to \(S\) by a path of length D and to the clause nodes via edges of length W. By making \(W\) sufficiently long and \(D\) sufficiently short, we can ensure that zigzagging is the only way to increase the maximum stretch for any Nash equilibrium, from which NP-hardness for optimal \(SC_{stretch}\) follows. Finally, following the identical method as [16], we can set edge and path length to induce an arbitrary constant approximation gap, from which NP-hardness of approximation follows for both social cost functions. We refer the reader to [16] for details and Figure 3 for illustration. Note that the theorem above also holds under the restriction to complete graphs, by ensuring that any edges added to this construction are large enough not to be used in any Nash equilibrium. More specifically, we show that it is hard to compute optimal Nash equilibria even when we restrict ourselves to the 3-dimensional Euclidean case. **Theorem 4.2**. : _The social cost of the optimal Nash equilibrium for the LMCF Game on \(3\)-dimensional Euclidean graphs is NP-Hard to compute for both the \(SC_{md}\) and \(SC_{stretch}\) social cost functions._  
Proof.