## 7 Theoretical Bounds on Closeness to Equilibrium for LocalHeur
* Let \(B\) denote the event that \(nn_{1}(x)\
otin H(x)\). * Let \(C\) denote the event that \(x=nn_{1}(nn_{1}(x))\). Now we show that \(Pr[A\wedge B\wedge C]\geq\frac{1}{8}\):  
First note that \(Pr[A|B\wedge C]>\frac{1}{2}\) as the events \(B\wedge C\) serve to mark out a slightly larger area of \(\overline{H(x)}\) from consideration than the area marked out from consideration within \(H(x)\). Namely, two areas become impossible for \(nn_{2}(x)\) to lie within, one area being the circle centered at \(x\) with radius \(dist(x,nn_{1}(x))\), and the second area (not disjoint) being the circle centered at \(nn_{1}(x)\) with same radius. The first circle blots out from consideration equal sizes areas in \(H(x)\) and \(\overline{H(x)}\), but the second circle lies wholly within \(\overline{H(x)}\). Secondly, note that event \(C\), a _reciprocity_ or _mutuality_ event, is entirely independent of event \(B\). Thus, \(Pr[B\wedge C]=Pr[B]Pr[C]\). As mentioned previously, \(Pr[B]=Pr[\overline{B}]=\frac{1}{2}\). It can be shown that \(Pr[C]\geq\frac{1}{2}\). Intuitively if points are assumed to be uniformly distributed in a n-dimensional Eucledian space, their reciprocity relationship follows a geometric distribution whose expectation cannot exceed 2. The reader is referred to [17, 18] for a detailed understanding. Thus, combining via Bayes' Rule, we obtain that \(Pr[A\wedge B\wedge C]=Pr[A|B\wedge C]Pr[B\wedge C]=Pr[A|B\wedge C]Pr[B]Pr[C] \geq\frac{1}{2^{3}}\) completing our proof. Proof of Theorem 7.2.: Let \(x\) be a player. From [25] it follows that the distance \(dist(x,nn_{1}(x))=\Theta(\frac{1}{\sqrt{n}})\) with high probability 9, yielding a lower bound on the cost of the best response. Thus, if we demonstrate that \(dist(nn_{1,H}(x),x)=O(\frac{\sqrt{\log n}}{\sqrt{n}})\) w.h.p., then we are done: For some constant \(c\), consider a radius \(r=c\sqrt{\frac{\log n}{\pi n}}\) circle of area \(A=\frac{2\log n}{n}\) about point \(x\). We complete the proof by showing that the probability \(Pr_{empty}\) that the intersection of this area with \(H(x)\) is empty (excluding \(x\)) is vanishing:  
\[ \begin{array}{rl}Pr_{empty}&=(1-\frac{A}{2})^{n-1}\approx(1-\frac{\log n}{n})^ {n}\\ &=((1-\frac{\log n}{n})^{\frac{n}{\log n}})^{\log n}\\ &\approx e^{-\log n}=\frac{1}{n}\to 0\end{array} \]  
Lastly we derive corollaries to the more general case of random Euclidean power graphs, as we especially care to model such graphs of power \(p=2\) for more realistic wireless applications. From the above proofs and the observation that relative proximity relation remain unchanged upon powering the distance, as well as the result from [25] on moments of the nearest neighbor distance distributions, the following corollaries immediately follow:  
**Corollary 7.3** (following from Thm. 7.1). : _For any power \(p\), in any configuration induced by LocalHeur on a random Euclidean power \(p\) instance, with high probability at least half of the players are playing a best response._  
**Corollary 7.4** (following from Thm. 7.2). : _For any power \(p\), in any configuration induced by LocalHeur on a random Euclidean power \(p\) instance, with high probability the worst player's cost is within \(O((\log n)^{\frac{p}{2}})\) of the cost of his best response._