## 7 Theoretical Bounds on Closeness to Equilibrium for LocalHeur  
In this section, we prove bounds on the closeness of the LocalHeur configurations to the Nash equilibrium condition. The main theorems concern the non-deviation from equilibrium for a majority of the nodes and the worst case approximation to a Nash equilibrium. When referring to random Euclidean instances, we restrict our consideration only to points distributed uniformly at random in the two-dimensional unit square. **Theorem 7.1**. : _[Majority Non-Deviation] In any configuration induced by LocalHeur on a random Euclidean instance, with high probability at least half of the players are playing a best response._  
**Theorem 7.2**. : _[Approximation to Nash] In any configuration induced by LocalHeur on a random Euclidean instance, with high probability the worst player's cost is within \(O(\sqrt{\log n})\) of the cost of his best response._  
Before proceeding to prove the theorems, we introduce some notational convenience: Let \(H(x)\) denote the half-plane through \(x\) defined by all points \(y\) such that vector \(<x,y>\) has a positive projection onto the vector \(<x,t>\), for destination \(t\). Let \(nn_{i}(x)\) denote the \(i^{th}\) nearest neighbor of \(x\), and let \(nn_{i,H}(x)\) for function \(H\) denote the \(i^{th}\) nearest neighbor of \(x\) restricted to half-plane \(H(x)\)7. Note that, except within a negligible constant neighborhood of the destination \(t\) for which relevant results hold anyway, \(nn_{1,H}(x)\) is with high probability the neighbor to which \(x\) forwards under the LocalHeur algorithm. Thus w.l.o.g. we denote \(LocalHeur(x)=nn_{1,H}(x)\). Footnote 7: Since the border of the unit square has asymptotically negligible effect on nearest neighbor relations, we ignore border effects w.l.o.g. Finally to make appropriate game-theoretic analysis, let \(BR(x)\) denote the set of points \(y\) for which the act of \(x\) forwarding to \(y\) would constitute a best response for \(x\) given the current configuration of all other players. Since \(BR(x)\) will be a singleton with probability \(1\) for random Euclidean instances, we refer to the best response as a single point w.l.o.g.. Note that player \(x\) is playing a best response iff \(x\) is forwarding to his nearest neighbor which does not already have a path to \(x\) (in which case the forwarding would induce a cycle, giving infinite cost). Now we proceed to prove our theorems:Proof of Theorem 7.1.: It suffices to show that, for any player \(x\), the probability that \(x\) is playing a best response is at least \(\frac{1}{2}+c\) for some constant \(c>0\), as the probability distribution of players playing best response is then bounded below by an i.i.d. binomial distribution with \(p=\frac{1}{2}+c\) for which the corresponding result on biased coin flips inducing majority w.h.p. is well known8. Thus, we proceed to show that for any player \(x\), which is of course a random position in our Euclidean space, the probability that \(x\) is playing a best response is at least \(\frac{5}{8}\). Footnote 8: Note that the dependence amongst the player variables actually only acts in the direction of increasing the bias towards playing best response. Clearly, if \(nn_{1}(x)\in H(x)\) then \(x\) is trivially playing a best response. Since there is no bias induced by either half-plane, we thus have that \(Pr[LocalHeur(x)=BR(x)]\geq\frac{1}{2}\). What remains now is to demonstrate a constant bias towards choosing a best response. This is accomplished by noting just another disjoint situation, namely the situation that although \(nn_{1}(x)\
otin H(x)\), that \(nn_{2}(x)\in H(x)\) and \(x=nn_{1}(nn_{1}(x))\). If we may show that the probability of this situation is bounded below by a constant \(c>0\) then we are done, and in particular we demonstrate that the probability of this situation is bounded below by \(\frac{1}{8}\). For convenience, let us denote the relevant events as follows:  
* Let \(A\) denote the event that \(nn_{2}(x)\in H(x)\).