## 4 Game Analysis
23) that transforms LDP into a nonnegative constrained least-square problem (NNLS) using a dual method. The NNLS problem can then be easily solved using any software package such as MATLAB. **Theorem 3**. : _Consider the least distance problem with lower bounds_  
\[\underset{\textbf{y}}{\text{minimize}}\|\textbf{y}\|_{2}\ \ \text{subject to:}\ \textbf{\tilde{1}}\leq\textbf{\tilde{M}}\textbf{y}, \tag{12}\]  
_where \(\textbf{y}\in\mathbb{R}^{n}\) and \(\textbf{\tilde{M}}\in\mathbb{R}^{m\times n}\). Let \(\textbf{q}\in\mathbb{R}^{m}\) be the solution to the nonnegativity constrained problem_  
\[\underset{\textbf{q}}{\text{minimize}}\|\textbf{Eq}-\textbf{e}\|^{2}\ \ \text{subject to:}\ \textbf{q}\geq 0, \tag{13}\]  
_where \(\textbf{E}=\left( \begin{array}{c}\textbf{\tilde{M}}^{T}\\ \textbf{\tilde{1}}^{T}\end{array} \right),\ \ \textbf{e}=\left( \begin{array}{c} \textbf{0}\\ 1\end{array} \right)\)._  
_Let the residual corresponding to the solution be_  
\[\textbf{r}=(r_{1},r_{2},...,r_{n+1})^{T}=\textbf{Eq}-\textbf{e}, \tag{14}\]  
_and put \(\sigma=\|\textbf{r}\|_{2}\). if \(\sigma=0\); then, the constraints \(\textbf{\tilde{1}}\leq\textbf{\tilde{M}}\textbf{y}\) are inconsistent and (12) has no solution. If \(\sigma\
eq 0\), then the vector **y** defined by \(\textbf{y}=(y_{1},y_{2},...,y_{n})^{T}\), where \(y_{j}=\frac{-r_{j}}{r_{n+1}},\forall\ j=1,...,n\) is the unique solution to (12)._  
For proof of the theorem, the reader is encouraged to refer to ([24], Chap. 23). Algorithm (1) summarizes the steps for calculating the best response of each cell (i.e., player). This algorithm is applied iteratively in each cell until they all converge to the Nash equilibrium. ```
1:Given: \(\mathbf{A}\), \(\mathbf{C}\), \(\mathbf{I}\), \(\mathbf{u}\)
2:initial value of \(\mathbf{b}=\left[ \begin{array}{c}\Gamma_{n}^{d}\frac{\sigma_{n}^{2}}{\sigma_{n }^{2}}\\ \Gamma_{n}^{u}\frac{\sigma_{n}^{2}}{\sigma_{n}^{2}}\end{array} \right]\), assuming intercell interference is zero. 3:\(t=0\); Start iteration:
4:while\(l=1\)do
5:\(t=t+1\)
6:\([\mathbf{Q}\ \mathbf{R}]=qr\{\mathbf{A}\}\)\(\triangleright\) Using QR factorization
7:\(\tilde{\mathbf{b}}=\mathbf{Q}^{T}\mathbf{b}\)
8:\(\mathbf{M}=\mathbf{CR}^{-1}\)
9:\(\tilde{\mathbf{I}}=\mathbf{I}-\mathbf{M}\tilde{\mathbf{b}}\)
10:\(\tilde{\mathbf{u}}=\mathbf{u}-\mathbf{M}\tilde{\mathbf{b}}\)
11:\(\tilde{\mathbf{I}}=[-\tilde{\mathbf{u}}^{T}\ \tilde{\mathbf{I}}^{T}]^{T}\)
12:\(\tilde{\mathbf{M}}=\left( \begin{array}{c}-\mathbf{M}\\ \mathbf{M}\end{array} \right)\)
13: Apply Theorem 3 to find \(\mathbf{y}\)
14:\(\mathbf{p}_{n}(t)=\mathbf{R}^{-1}\left(\mathbf{y}+\tilde{\mathbf{b}}\right)\)\(\triangleright\) This is the best response of cell \(n\). 15: Measure the amount of interference and find \(\mathbf{b}\) to be used for next iteration. 16:if\(|\mathbf{p}_{n}(t-1)-\mathbf{p}_{n}(t)|\leq\epsilon\)then\(l=0\)\(\triangleright\) If this condition is satisfied then NE is achieved, where \(\epsilon\) is sufficiently small. 17:endif
18:endwhile
```  
**Algorithm 1** Equilibrium Achieving Algorithm  
It is worth mentioning that the proposed algorithm is completely distributed. Thus, each player will act upon local information collected at the BS and its associated UE. Each UE has to send the gain of the desired channel as well as the measured interference to its home BS since all computation should be performed at the BS for powerful computing capability and large memory capacity.