## 5 Heuristics  
Given the hardness results, we seek to find an intuitive heuristic to compute Nash trees for LMCF with low Social Cost. First, we present a meta-heuristic, **LMHeur**, to compute general Nash equilibria for the LMCF Game. The main idea behind the meta-heuristic is that since equilibria are directed trees, for any Nash tree there exists a forwarding order such that, maintaining a forest of directed edges for nodes already chosen, the next chosen node forwards to its nearest neighbor that does not introduce a cycle into the forest. The choice of forwarding order may be dictated by whichever global cost function we wish to optimize, or which kind of Nash we are looking for. Figure 4: \(3\)-SAT reduction embedded in 3-dimensional Euclidian space. As we have proposed \(SC_{stretch}\) and \(SC_{md}\) as reasonable social cost functions to consider for the LMCF Game, we propose the **DeltaHeur**, a member of the LMHeur class, to compute good Nash trees. The ordering priority for DeltaHeur is based on maximal progress towards shortest path. A priority queue is kept holding the nodes that have yet to forward, sorted by the difference between the candidate node's shortest path distance to the destination and its available nearest neighbor's shortest path distance to the destination (\"available\" means not introducing a cycle within the current forest). The description is shown in Algorithm 5.1. It is straightforward to show in the Euclidean case that the ordering induced by the DeltaHeur corresponds exactly to a \"maximum projection\" heuristic, which we call **ProjHeur**, where the projection in question is that of the vector from the candidate node to its available nearest neighbor projected onto the vector from the candidate node to the destination \(t\). ```
0:Position of all the nodes is known to all other nodes; for given nodes (nummodes), \(nummodes\
eq 0\) // Q: Priority Queue initially contains indices from 1 to nummodes while Q is not empty do for all\(i=1\) to \(numnodes\)do for all\(j=1\) to \(numnodes\)-1 do if (cyclecheck(\(i,N\)\(N\)\(s\)\([i].j\)) \(\
eq 1\)) then // cyclecheck(i,j) returns 1 if Node i forwarding to Node j forms a cycle // N\(\_\)N\(\_\)s\([i].j\) refers to jth nearest neighbor of i  i.cnn \(\rightarrow\) j // i.cnn refers to the current nearest neighbor of \(i\) that does not create a cycle break endif endfor for all\(i=1\) to \(numnodes\)do  i.delta=d2d(i)-d2d(i.cnn) // d2d refers to the shortest distance to destination  update(Q) // Q is updated with the node indices(i) in decreasing order of delta endfor [Q.top()].pointTo \(\rightarrow\) Nbrs[Q.top()].cnn // pointTo refers to the node to which the node with maximum delta forwards to  Q.pop() endwhile
```  
**Algorithm 5.1** DeltaHeur  
The extension of ProjHeur to a local algorithm, **LocalHeur**, is simply that each node forwards to its nearest neighbor that is closer in the Euclidean space to the destination than itself (thus also being in the direction of the destination). The description is shown in Algorithm 5.2. Trivially, any such configuration is guaranteed to be cycle-free without need of an explicit cycle check, nor computation of shortest paths, since Euclidean metrics are used. However, unlike ProjHeur, LocalHeur does not guarantee Nash equilibrium. We provide results later on closeness of LocalHeur to Nash equilibrium. Note furthermore, that while the Euclidean power graph of power \(p=2\) is not a metric graph, it is a closely bounded approximation of the underlying Euclidean metric, particularly in random instances.