## 3 Preliminary Results
### Observations on the Structure of Nash Equilibria  
It is not a coincidence that the Nash equilibria examples thus far have been trees. We briefly return to consideration of general Nash, including the mixed case:  
**Remark 3.4**. : _In any connected graph \(G\), Nash equilibria always exist (guaranteed via MST), and all Nash equilibria form an acyclic spanning graph with destination \(t\) as sink. In particular every pure Nash equilibria forms a spanning tree directed towards \(t\)._  
Note that mixed Nash can be viewed as flows in \(G\) and that any non-zero flow through a cycle will have infinite cost. Now, given any Nash-induced sub-graph \(G_{S}\), denote as \(T_{t}\) the maximal acyclic subgraph in \(G_{S}\) that contains \(t\). Due to connectedness, if there are any cycles in \(G_{S}\), then there is always some node on some cycle that has a neighbor in \(T_{t}\), thus giving finite rather than infinite flow weighted  
Figure 1: Euclidean Horseshoe and its Optimal Nash. Figure 2: Euclidean Spiral. cost (an infinite flow weighted cost is still infinite), and an incentive to switch. So, there can be no cycles and \(T_{t}\) spans \(G\). And, due to the single out-degree nature of pure Nash, if \(G_{S}\) is a pure Nash then \(T_{t}\) is a spanning tree. It is without loss of generality to consider pure Nash equilibria with respect to maxima and minima of our social cost functions, for the following reason. For any branching out (_i.e._, a node forwarding in a mixed manner to more than one neighbor) that occurs in a mixed Nash, the multiple options must have identical cost to the branching node (and given that, the branching node may distribute the probability flow in any manner). Any mixed flow achieving some relevant minima or maxima (with respect to \(PoS\) or \(PoA\)) can therefore be converted into a directed tree achieving the same such minima or maxima by continuously shifting the flow to a path that induces the extreme value. Thus, from now on we discuss Nash trees without loss of generality. We may further state the following regarding the structure of Nash trees:  
**Remark 3.5**. : _In a weighted graph \(G\), if \(i\) is \(j\)'s unique nearest neighbor and \(j\) is also \(i\)'s unique nearest neighbor, then we refer to \(i\) and \(j\) as mutual nearest neighbors. Edges between mutual nearest neighbors (excluding \(t\)) are always used in some direction, in any Nash tree._  
To see this, consider a mutual nearest neighbor pair \(i,j\) and Nash tree \(T\) such that edge \((i,j)\) is _not_ used in either direction. Since the weight of this edge is minimal amongst all neighbors for both \(i\) and \(j\), the only way it cannot be present in a Nash equilibrium is if it lies on a cycle. But if directing from \(i\) to \(j\) would create a cycle, then there must already be a path from \(j\) to \(i\) in \(T\), and likewise for the opposite direction. So there must already be a cycle in \(T\), namely from \(i\) to \(j\) and back to \(i\), contradicting that \(T\) is a Nash tree. Thus, \((i,j)\) must be used in some direction in every Nash tree. As a corollary, we may also relate this to _generating_ Nash equilibria. Due to the uniqueness condition in the above definition, any set of mutual nearest neighbor edges must be an independent set. Moreover, noting that in a complete graph we may always complete a spanning tree after fixing any independent set of edges as a subgraph, we have the following:  
**Corollary 3.6**. : _In any complete graph, for every directionality of the set of mutual nearest neighbor edges (excluding \(t\)) there exists a corresponding Nash equilibrium._  
Euclidean graphs are especially relevant cases for analysis of the LMCF Game. While we have already noted that a restriction to Euclidean graphs is rich enough to generate arbitrarily bad examples, this class also has some further structural properties:  
**Remark 3.7**.