## 4 Cell Selection Games
### Traditional Congestion Game  
We use the traditional congestion game (TCG) to model the CS problem with multiple picocells. In this model, congestion of a device is proportional to the total number of devices selecting the same BS, so the cost of \(\textsl{DV}_{k}\) selecting the macrocell \(\textsl{BS}_{0}\) and the cost of \(\textsl{DV}_{l}\) selecting picocell \(\textsl{BS}_{i},i\in\{1,...,M\}\) can be the inverse of the amount of resource obtained by \(\textsl{DV}_{k}\) and \(\textsl{DV}_{l}\), written as:  
\[C_{k}(\textsl{BS}_{i},p_{-k})=\frac{n_{i}}{\textsl{B}_{i}} \tag{3}\]  
\[C_{l}(\textsl{BS}_{0},p_{-l})=\frac{N_{0}-\sum_{\alpha}n_{\alpha}}{\textsl{B }_{0}} \tag{4}\]  
where \(B_{0}\) and \(B_{i}\) represent the total uplink bandwidth for \(\textsl{BS}_{0}\) and \(\textsl{BS}_{i}\), respectively. If \(\textsl{DV}_{k}\) changes the CS preference to \(\textsl{BS}_{0}\), its cost becomes:  
\[C_{k}(\textsl{BS}_{0},p_{-k})=\frac{N_{0}-\sum_{\alpha}n_{\alpha}+1}{\textsl{ B}_{0}} \tag{5}\]  
Similarly, if \(\textsl{DV}_{l}\) changes the CS preference to \(\textsl{BS}_{i}\), its cost becomes:  
\[C_{l}(\textsl{BS}_{i},p_{-l})=\frac{n_{i}+1}{\textsl{B}_{i}} \tag{6}\]  
**Theorem 1**. : _For TCG, \(\forall i\in\{1,...,M\}\), define:_  
\[g_{1}(n_{i})=n_{i}+\frac{B_{i}}{B_{0}+B_{i}}\sum_{\alpha\
eq i}n_{\alpha} \tag{7}\]  
\[A_{1,i}=\frac{B_{i}(N_{0}+1)}{\textsl{B}_{0}+B_{i}} \tag{8}\]  
_(1) if \(g_{1}(N_{i})<A_{1,i}\), \(n_{i}^{*}=N_{i}\) forms the PSNE; (2) if \(g_{1}(1)>A_{1,i}\), \(n_{i}^{*}=0\) forms the PSNE; (3) otherwise, \(n_{i}^{*}\) satisfying \(A_{1,i}-1\leq g_{1}(n_{i}^{*})\leq A_{1,i}\) forms the PSNE._  
**Proof. ** Based on Definition 1, we rewrite the conditions that \(n_{i}\) forms the PSNE as, \(\forall i\in\{1,...,M\}\):  
\[C_{k}(\textsl{BS}_{i},p_{-k})\leq C_{k}(\textsl{BS}_{0},p_{-k}) \tag{9}\]  
\[C_{l}(\textsl{BS}_{0},p_{-l})\leq C_{l}(\textsl{BS}_{i},p_{-l}) \tag{10}\]  
Equations (9) and (10) separately indicate that no device selecting the picocell \(\textsl{BS}_{i}\) and the macrocell \(\textsl{BS}_{0}\) feels like changing the CS preference. Taking Equations (3)-(6) into (9) and (10), we get:  
\[A_{1,i}-1\leq g_{1}(n_{i}^{*})\leq A_{1,i} \tag{11}\]  
To prove the existence of a PSNE based on Equation (11), we consider firstly the two-dimensional case with \(n_{1}\) and \(n_{2}\) shown in Figure 3. For \(A_{1,1}-1\leq g_{1}(n_{1})\leq A_{1,1}\), the integer points between the two parallel solid lines fit it. Since the distance between Point A and B is one and the slope coefficient of the two solid lines corresponding to the above inequation is less than \(-1\), given each \(n_{1}\), there is at least one integer solution for \(n_{2}\). Meanwhile, since the slope coefficient of the two parallel dashed lines for \(A_{1,2}-1\leq g_{1}(n_{2})\leq A_{1,2}\) is in \((-1,0)\) and the distance between Point C and D is one, at least one integer solution between the two solid lines fits for the above inequation, _i.e._, at least one solution can be found for Equation (11) with \(i=1,2\). Applying mathematical induction, \(\forall\{n_{1},n_{2},...,n_{k}\}\) as a \(k\)-dimensional point in the \(k\)-dimensional case, there is at least one integer solution for \(n_{k+1}\). Since the two parallel dashed lines in the \((k+1)\)-th dimension have a slope coefficient in \((-1,0)\), at least one integer solution fits for \(A_{1,k+1}-1\leq g_{1}(n_{k+1})\leq A_{1,k+1}\), indicating the existence of a PSNE. Since \(B\!S_{i}\) covers \(N_{i}\) devices, if \(g_{1}(N_{i})<A_{1,i}\), the PSNE corresponds to \(n_{i}^{*}=N_{i}\), indicating that all of the devices covered by \(B\!S_{i}\) select it. If \(g_{1}(1)>A_{1,i}\), the PSNE corresponds to \(n_{i}^{*}=0\). Otherwise, \(n_{i}^{*}\) satisfying Equation (11) forms the PSNE. To sum up, Theorem 1 indicates the numbers of devices selecting different picocells in the PSNE. \(g_{1}(n_{i})\) in Theorem 1 is a combination of the variables representing the numbers of devices selecting different picocells.