# Multicell Interference Management in Device to Device Underlay Cellular Networks
## 4 RB Allocation  
### RB Problem Formulation and Solution  
In this subsection we describe the first stage of our proposed approach which concerns the RB allocation. It is assumed that every user of the cell (either cellular or D2D) has a fixed transmission power value. Thus the problem, expressed in Equation (2), may be simplified and take the following form  
\[\underset{S}{\text{minimize}} \sum_{i=1}^{E}I_{i}\] (5) subject to \[\sum_{k=1}^{K}s_{i}(u,k)=1,\forall u\in V_{i},\forall i\in E \tag{5a}\] \[\sum_{u\in V_{i}}s_{i}(u,k)=1,\forall k\in K,\forall i\in E\] (5b) \[\gamma_{u}\geq\gamma_{u}^{tar},\forall u\in V_{i},\forall i\in E \tag{5c}\]  
where \(I_{i}\) is defined as in Equation (3) and \(P_{v}\) has been assumed a fixed value for every \(v\in V_{j}\) and \(j\in E\). The above problem is a combinatorial optimization problem since the decision variables of the problem i.e., the assignment matrices of each cell are integer. In the literature, efficient algorithms for the exact solution of this type of problems do not exist. For this reason, we search for approximation algorithms which provide suboptimal solutions in a time efficient manner. For this problem, our idea is to model it, as an exact potential game. The players of this game will be the cells--either physical or virtual (D2D)--of the system and the strategies will be the assignment matrices of the cells. Formally, we define the game  
\[G=\{N,S,U\} \tag{6}\]  
where  
* \(N\) is the set of the players of the game \(G\), \(N=E\), i.e., the set of the receivers in the system--either the eNBs or the D2D receivers,
* \(S\) denotes the set of the strategies of the players, \(S=\{s_{i}\}_{i=1,\ldots,|N|}\) i.e., the set of the assignment matrices of each cell-receiver, \(s_{i}\), defined in Equation (4) and
* \(U\) denotes the set of the utility functions of the players of the game \(G\). The utility function \(U_{i}\) of the player \(i\) is defined as follows:  
\[U_{i}(s_{i},s_{-i})=-I_{i}(s_{i},s_{-i})-I_{i}^{c}(s_{i},s_{-i}) \tag{7}\]  
where \(I_{i}(s_{i},s_{-i})\) is defined in Equation (3) and repeated here for clarity reasons  
\[I_{i}=\sum_{u\in V_{i}}\sum_{k=1}^{K}s_{i}(u,k)\sum_{j\
eq i}\sum_{v\in V_{j}}s _{j}(v,k)\cdot P_{v}\cdot G_{v}^{i,k}+\sigma^{2}\]  
\(I_{i}^{c}(s_{i},s_{-i})\) is defined as follows  
\[I_{i}^{c}(s_{i},s_{-i})=\sum_{u\in V_{i}}\sum_{k=1}^{K}s_{i}(u,k)\cdot P_{u} \sum_{j\
eq i}\sum_{v\in V_{j}}s_{j}(v,k)\cdot G_{u}^{j,k}+\sigma^{2} \tag{8}\]\(I_{i}^{c}(s_{i},s_{-i})\) denotes the total interference caused by all users of cell \(i\) to all other cells using at least one common RB with cell \(i\). **Theorem 1**: _Game \(G\) is a bilateral symmetric interaction game [32]._  
**Proof of Theorem 1. ** A bilateral symmetric interaction game has the following form \(B=\{N,S,U\}\), where  
\[U_{i}(s_{i},s_{-i})=\sum\limits_{j\
eq i}w_{i,j}(s_{i},s_{j}),\forall i\in N \tag{9}\]  
and  
\[w_{i,j}(s_{i},s_{j})=w_{j,j}(s_{j},s_{i}),\ \forall i\
eq j \tag{10}\]  
where \(w_{i,j}:S_{i}\times S_{j}\rightarrow\mathbb{R}\). The utility function of the player \(i\) of the game \(G\), defined in Equation (7), can be mapped to the utility function defined in Equation (9), if \(w_{i,j}(s_{i},s_{j})=-\sum\limits_{u\in V_{i}}\sum\limits_{k=1}^{K}s_{i}(u,k) \sum\limits_{v\in V_{j}}s_{j}(v,k)(P_{v}G_{v}^{i,k}+P_{u}G_{u}^{j,k})+\sigma^{2}\). It is observed that the bilateral symmetric property of Equation (10) also holds. \(\square\)  
Bilateral symmetric interaction games exhibit certain desirable properties since they are exact potential games. The potential function of the game \(G\) according to [32] is the following:  
\[\sum_{k=1}^{K}s_{i}(u,k)=1,\forall u\in V_{i},\forall i\in E \tag{5a}\]0 \[\sum_{k=1}^{K}s_{i}(u,k)=1,\forall u\in V_{i},\forall i\in E \tag{5a}\]1 (12a) \[\sum_{k=1}^{K}s_{i}(u,k)=1,\forall u\in V_{i},\forall i\in E \tag{5a}\]2  
where  
\[\sum_{k=1}^{K}s_{i}(u,k)=1,\forall u\in V_{i},\forall i\in E \tag{5a}\]3  
and \(u\in V_{i}\).