# Comprehensive study of good model training for prostate segmentation in
volumetric MRI

Carlos Nácher Collado

###### Abstract

Prostate cancer was the third most common cancer in 2020 internationally,
coming after breast cancer and lung cancer. Furthermore, in recent years
prostate cancer has shown an increasing trend. According to clinical
experience, if this problem is detected and treated early, there can be a high
chance of survival for the patient. One task that helps diagnose prostate
cancer is prostate segmentation from magnetic resonance imaging. Manual
segmentation performed by clinical experts has its drawbacks such as: the high
time and concentration required from observers; and inter- and intra-observer
variability. This is why in recent years automatic approaches to segment a
prostate based on convolutional neural networks have emerged. Many of them
have novel proposed architectures. In this paper I make an exhaustive study of
several deep learning models by adjusting them to the task of prostate
prediction. I do not use novel architectures, but focus my work more on how to
train the networks. My approach is based on a ResNext101 3D encoder and a
Unet3D decoder. I provide a study of the importance of resolutions in
resampling data, something that no one else has done before.

##  1 Introduction

According to the following study by the International Agency for Research on
Cancer [SFS+21], in 2020 there were, globally, 1 414 259 new cases of prostate
cancer, being the third most common cancer (7.3%) after breast cancer (11.7%)
and lung cancer (11.3%); referring these percentages to the total number of
new cases of any cancer in 2020 internationally, about 19.3 million; producing
375 304 (3.8%) deaths in that year. Clinical experience shows that if prostate
cancer is detected early there is a high chance of survival for the patient.
If prostate cancer is identified early, there is a high probability of
survival for the patient. For this and other applications, automatic MRI
prostate segmentation is useful for clinical support. In this paper I propose
a comprehensive study of the training of several Deep Learning models.

Automatic prostate segmentation in magnetic resonance imaging (MRI) with Deep
Learning has been based since its inception on Convolutional Neural Networks
(CNN) first proposed by [Fuk75] and later improved upon by [LBBH98]. The best
known CNN for medical image segmentation is the U-Net [RFB15]. Since the
PROMISE12 competition started in 2012, there have been several proposals for
improvements: Haozhe Jia et al. [JXS+18] proposed to do Transfer Learning
[Boz20] of the VGG-19 [SZ15] network by separating the data according to
whether the patient has endorectal coil or not; their coarse-to-fine strategy
is based on atlas-based segmentation [BCDT15]. In 2018 Haozhe Jia et al.
[JSZ+18] propose an improvement their previous contribution; they change the
VGG-19 backbone [SZ15] to ResNet-50 [HZRS15] in 3D; they propose the use of
GCB blocks [PZY+17] and RRB; furthermore, they propose the use of a Generative
Adversarial Network (GAN) [GPAM+14] to discriminate the classification of each
voxel and refine the results of the encoder-decoder. In January 2019, Isensee
et al. [IKW+18] present a paper in which they claim that a well-trained basic
U-Net network can achieve great results. They start from the 3D U-Net [RFB15]
[ÇAL+16] and say that instead of focusing on the architecture of the network
and adding complex layers such as a gan, they focus on the correct training of
the network; this premise of Isensee et al. is the inspiration for my work. In
August 2019, Zhu et al. [ZDY19] propose an adaptation of the data domain with
a GAN-like discriminator. In July 2019, Haozhe Jia et al. [JXS+20] modify
their GCBs and RRBs by Py-Conv and As-Conv, to account for the anisotropy of
MRI data as well as extract features at various levels of resolution; they
also introduce CABs (attention modules) and a specialised prostate edge
decoder. In 2019, Xiangxiang Qin HJIA3dapa proposes a structure called PAM
that combines the PyConv and the CABs of HJIA3dapa into a single module; it
also proposes a decoder specialising in the edges, but in 3D. In June 2022,
and being the state of the art as of today, Haozhe Jia et al. [JCHX22] again
propose an improvement to their previous contributions [JXS+18], [JSZ+18],
[JXS+20]; they change the ResNet backbone [HZRS15] to Res2Net [GCZ+19]

State of the art proposals, in due course, have introduced new concepts such
as: the use of GANs [GPAM+14] [JSZ+18] [JXS+20]; the use of convolutions at
different scales [JXS+20] [JSH+19] [Qin19] [JCHX22]; the use of anisotropic
convolutions [JSZ+18] [JXS+20] [JSH+19] [Qin19] [JCHX22]; the use of attention
modules [JSH+19] [Qin19] [JCHX22]; the use of a specialised decoder at
prostate edges [JSH+19] [JCHX22].

However, there is one particular paper, No-New Net, by Isensee et al.
[IKW+18](more extended in Isensee et al. [IPK+19]), which hypothesises that a
”basic” network for 3D segmentation, such as the 3D-Unet [ÇAL+16], may be
sufficient to achieve state-of-the-art results. He focuses his research on how
to train the neural network, and not on the architecture itself. He has proven
to be among the top performers on several occasions with his work Isensee et
al. [IKW+18] and is currently ranked fourth on PROMISE12.

Based on this work, I propose an intensive study of the training of a basic
network (3D-Unet [ÇAL+16]), with different tests on: the choice of the
backbone used; the optimiser used and its hyperparameters; the Data
Augmentation techniques used. In addition, I propose a study on the way of
resampling the data and the choice of the common output resolution, which no
one else has proposed in their work, with which I show that there is room for
improvement in other aspects of the task of training an Artificial
Intelligence model, other than the choice of the architecture itself.

##  2 Method

###  2.1 Implementation

I use the 50 training cases provided by the contest. As preprocessing I do
MCLAHE [SBE+19]. As data augmentation I do flips in the x,y,z axis; rotations
from -15 to 15 degrees in the z axis; scaling between 0.75 and 1.5; and
BSpline deformations. All these transformations are applied online to random
patches of 192x192x32.

The loss function used was Dice 1 \+ BinaryFocalCrossentropy 2. The optimizer
used was Adam with initial learning rate of 0.006, with decay when validation
loss stopped improving and epsilon = 0.001.

All training was run on a 16GB Tesla P100 GPU graphics card.

###  2.2 Comprehensive study of training

The first thing I propose is a metric called Reconstruction Dice (rDSC).
Basically this means, resampling a segmentation to a particular resolution
different from its original resolution, resampling it, and then calculating
the Dice coefficient between the original segmentation and the reconstructed
segmentation. I do this to study the resampling of the training data to the
optimal resolution. The resolutions I propose for the 50 training cases are:

  * •

Half of the resolution of each particular segmentation.

  * •

Twice the resolution.

  * •

The median of the resolutions in the training set (0.625x0.625x3.6).

  * •

The resolution (0.625x0.625x1.5) as this is the resolution used by most of the
PROMISE12 papers.

  * •

A proposal (0.3125x0.3125x1.5).

The proposed resolution (0.3125x0.3125x1.5) was proposed because it was
observed that decreasing the resolution of a piece of data (i.e. making its
spacing larger) resulted in a worse rDSC than increasing the resolution (i.e.
making its spacing smaller). This is because reducing the resolution often
discards information that, when you want to return to the original resolution,
is not available because it was lost in the first resampling. On the other
hand, when the resolution is increased, new values are ”invented”
(interpolated), and then it is easier to return to the original image with
fewer losses.

I tested all five strategies with the 50 training cases. The results can be
seen in figure 1. With a p-value $<$ 0.05, the proposed (0.3125x0.3125x1.5)
achieves better rDSC than (0.625x0.625x1.5). Later on, I try to train the best
of my models for data with both resolutions, and show that the one using data
with resolutions (0.3125x0.3125x1.5) obtains better validation metrics. (See
7)

Figure 1: Comparison of the different resolutions in terms of rDSC. Note that
resampling each image to twice its resolution is ideal in terms of rDSC but
with 512x512xz images, this strategy would leave us with 1024x1024x2z data,
which is computationally unfeasible. The proposed strategy outperforms the
standard strategy used in PROMISE (0.625x0.625x1.5) with p-value $<$ 0.05.

Then, with the resolution (0.3125x0.3125x1.5) chosen, I make some intensive
tests to choose the data augmentation to use, the cost function, the backbone
and the decoder model, among others.

In terms of cost function, I tried 5:

  * •

Dice 1

  * •

BinaryFocalCrossEntropy 2

  * •

Tversky 3

  * •

Dice+ BinaryFocalCrossEntropy

  * •

Tversky + BinaryFocalCrossEntropy

The best one turns out to be Dice+ BinaryFocalCrossEntropy, so it is the one I
choose to train the models.

$\text{ Dice }=\frac{2|A\cap B|}{|A|+|B|}$ (1)

$CE=-\frac{1}{n}\sum_{j=1}^{n}\sum_{i=1}^{c}\left[y_{i}\log\left(p_{i}\right)+\left(1-y_{i}\right)\log\left(1-p_{i}\right)\right]$
(2)

$\mathrm{TI}=\frac{\mathrm{TP}}{\mathrm{TP}+\alpha\mathrm{FN}+\beta\mathrm{FP}}$
(3)

As backbones try several (freezing weights vs. non-freezing):

  * •

ResNet18 [HZRS15]

  * •

ResNet50 [HZRS15]

  * •

ResNext101 [GCZ+19]

A comparison of the tested backbones can be seen in figure 2. The results are
somewhat noisy, but according to the T-test, ResNext101 is better with p-value
$<$ 0.05. The general architecture of ResNext can be seen in figure 3, and a
comparison between ResNet and ResNext blocks (the latter being equivalent but
more efficient) in figure 4.

Figure 2: Comparison of backbones. The losses are a bit noisy because they are
the first epochs.  Figure 3: ResNet and ResNext architetures and shapes.
Figure 4: Comparison of ResNet vs ResNext block.

As decoder models I test: the U-Net 3D [RFB15] [ÇAL+16], the LinkNet 3D [CC17]
(which is identical to the U-Net with the difference of adding instead of
concatenating) and the PSP-Net [ZSQ+17]. The schematic of the three
architectures is shown in figure 5. The U-Net 3D gave me the best results.

(a) U-Net architecture.

(b) Link-Net architecture.

(c) PSP-Net architecture.

Figure 5: Comparison of decoder model architetures.

Tras esta y otras muchas pruebas que no incluyo en este paper, consigo el
mejor modelo, cuyo Dice de validación muestro en la figura 6.

Figure 6: Metrics on train and validation with the best model achieved.

For predictions I use the Sliding Windows technique with windows of size
192x192x32 and fixed stride of 48x48x8, which gives me better results than
using stride of 96x96x16.

##  3 Ablation experiments

Once I got the best model for the resolution (0.3125x0.3125x1.5), I resampled
the data again, this time to 0.625x0.625x1.5mm, and trained the best model but
now with the new data (keeping all the hyperparameters like the batch size the
same, also to occupy the same physical space I took the random patches of size
96x96x32). In figure 7 you can see how the proposed strategy improves the
validation Dice by up to one point.

Figure 7: Comparison of training the same models with data in resolution
(0.625x0.625x1.5mm) vs (0.3125x0.3125x1.5mm).

##  4 Conclusions

I have shown that good training of a basic network can contribute sufficiently
good results compared to other complex methods, just as Isensee et al.
demonstrate with [IKW+18].

I have shown that there is room for improvement of the algorithms if we focus
on the way the data is handled and not only on the architecture. Demonstrating
how the resampling resolution of the data can improve Die by up to 1 point.

I am waiting for the test results at the hands of the PROMISE12 competition.

## References

  * [BCDT15] M. Bach Cuadra, V. Duay, and J.-Ph. Thiran.  Atlas-based Segmentation, pages 221–244.  Springer US, Boston, MA, 2015.
  * [Boz20] Stevo Bozinovski.  Reminder of the first paper on transfer learning in neural networks, 1976\.  Informatica, 44, 09 2020.
  * [ÇAL+16] Özgün Çiçek, Ahmed Abdulkadir, Soeren S. Lienkamp, Thomas Brox, and Olaf Ronneberger.  3d u-net: Learning dense volumetric segmentation from sparse annotation.  CoRR, abs/1606.06650, 2016.
  * [CC17] Abhishek Chaurasia and Eugenio Culurciello.  Linknet: Exploiting encoder representations for efficient semantic segmentation.  2017 IEEE Visual Communications and Image Processing (VCIP), pages 1–4, 2017.
  * [Fuk75] K Fukushima.  Cognitron: a self-organizing multilayered neural network.  Biol Cybern, 20(3-4):121–136, November 1975.
  * [GCZ+19] Shang-Hua Gao, Ming-Ming Cheng, Kai Zhao, Xin-Yu Zhang, Ming-Hsuan Yang, and Philip Torr.  Res2net: A new multi-scale backbone architecture.  IEEE transactions on pattern analysis and machine intelligence, 43(2):652–662, 2019.
  * [GPAM+14] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * [HZRS15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  CoRR, abs/1512.03385, 2015.
  * [IKW+18] Fabian Isensee, Philipp Kickingereder, Wolfgang Wick, Martin Bendszus, and Klaus H. Maier-Hein.  No new-net.  CoRR, abs/1809.10483, 2018.
  * [IPK+19] Fabian Isensee, Jens Petersen, Simon A. A. Kohl, Paul F. Jäger, and Klaus Maier-Hein.  nnu-net: Breaking the spell on successful medical image segmentation.  ArXiv, abs/1904.08128, 2019.
  * [JCHX22] Haozhe Jia, Weidong Cai, Heng Huang, and Yong Xia.  Learning multi-scale synergic discriminative features for prostate image segmentation.  Pattern Recognition, 126:108556, 2022.
  * [JSH+19] Haozhe Jia, Yang Song, Heng Huang, Weidong (Tom) Cai, and Yong Xia.  Hd-net: Hybrid discriminative network for prostate segmentation in mr images.  In MICCAI, 2019.
  * [JSZ+18] Haozhe Jia, Yang Song, Donghao Zhang, Heng Huang, Dagan Feng, Michael J. Fulham, Yong Xia, and Weidong Cai.  3d global convolutional adversarial network\\\ for prostate MR volume segmentation.  CoRR, abs/1807.06742, 2018.
  * [JXS+18] Haozhe Jia, Yong Xia, Yang Song, Weidong Cai, Michael Fulham, and David Dagan Feng.  Atlas registration and ensemble deep convolutional neural network-based prostate segmentation using magnetic resonance imaging.  Neurocomputing, 275:1358–1369, 2018.
  * [JXS+20] Haozhe Jia, Yong Xia, Yang Song, Donghao Zhang, Heng Huang, Yanning Zhang, and Weidong Cai.  3d apa-net: 3d adversarial pyramid anisotropic convolutional network for prostate segmentation in mr images.  IEEE Transactions on Medical Imaging, 39(2):447–457, 2020.
  * [LBBH98] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [PZY+17] Chao Peng, Xiangyu Zhang, Gang Yu, Guiming Luo, and Jian Sun.  Large kernel matters - improve semantic segmentation by global convolutional network.  CoRR, abs/1703.02719, 2017.
  * [Qin19] Xiangxiang Qin.  Transfer learning with edge attention for prostate mri segmentation.  ArXiv, abs/1912.09847, 2019.
  * [RFB15] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  CoRR, abs/1505.04597, 2015.
  * [SBE+19] Vincent Stimper, Stefan Bauer, Ralph Ernstorfer, Bernhard Schölkopf, and Rui Patrick Xian.  Multidimensional contrast limited adaptive histogram equalization.  IEEE Access, 7:165437–165447, 2019.
  * [SFS+21] Hyuna Sung, Jacques Ferlay, Rebecca L. Siegel, Mathieu Laversanne, Isabelle Soerjomataram, Ahmedin Jemal, and Freddie Bray.  Global cancer statistics 2020: Globocan estimates of incidence and mortality worldwide for 36 cancers in 185 countries.  CA: A Cancer Journal for Clinicians, 71:209 – 249, 2021.
  * [SZ15] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  CoRR, abs/1409.1556, 2015.
  * [ZDY19] Qikui Zhu, Bo Du, and Pingkun Yan.  Boundary-weighted domain adaptive neural network for prostate MR image segmentation.  CoRR, abs/1902.08128, 2019.
  * [ZSQ+17] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi, Xiaogang Wang, and Jiaya Jia.  Pyramid scene parsing network, 2017.


# FEAT: Fair Coordinated Iterative
Water-Filling Algorithm

Majed Haddad1, Piotr Wiecek2, Oussama Habachi3, Samir M. Perlaza4 and Shahid
M. Shah5
1University of Avignon, France
2Wrocław University of Science and Technology, Wrocław, Poland
3University of Clermont Auvergne, France
4INRIA, Sophia Antipolis, France
5National Institute of Technology, Srinagar, India

###### Abstract

In this paper, we consider a perfect coordinated water-filling game, where
each user transmits solely on a given carrier. The main goal of the proposed
algorithm (which we call FEAT) is to get close to the optimal, while keeping a
decent level of fairness. The key idea within FEAT is to minimize the ratio
between the best and the worst utilities of the users. This is done by
ensuring that, at each iteration (channel assignment), a user is satisfied
with this assignment as long as he does not loose much more than other users
in the system. It has been shown that FEAT outperforms most related algorithms
in many aspects, especially in interference-limited systems. Indeed, with FEAT
we can ensure a near-optimal, fair and energy efficient solution with low
computational complexity. In terms of robustness, it turns out that the
balance between being nearly globally optimal and good from individual point
of view seems hard to sustain with a significant number of users. Also notice
that, in this regard, global optimality gets less affected than the individual
one, which offers hope that such an accurate water-filling algorithm can be
designed around competition in interference-limited systems.

###### Index Terms:

Rate maximization, power control, water-filing, game theory, Nash equilibrium,
disjoint carrier water-filling game, fairness, energy efficiency, robustness.

##  I Introduction

In this paper, we tackle the well-known water-filling solution which solves
the problem of maximizing the information rate between the input and the
output of a channel composed of several subchannels (such as a frequency-
selective channel, a time-varying channel) with an average power constraint at
the transmitters [1, 2]. More specifically, we consider a multiple access
channel (MAC), where $N$ transmitters wish to communicate with a common
receiver over $K$ independent channels.

The purpose of this paper is twofold: On the one hand, it provides a nearly-
optimal though low-complexity implementation in practice. To be more precise,
it provides a practical algorithm with $O(NK^{2}\log(K))$ complexity. On the
other hand, it guarantees fairness among the users by trying to assign to
every user in the system at least one good channel.

## Related Work

Power control is well-known to be useful for the information rate enhancement.
In fact, the main aim of power control is to select power levels corresponding
to fading gain such that the sum information rate is optimized. Water-filling
based power control algorithms are among the possible algorithms for power
allocation. There have been many works on water-filling, but most of them do
not consider fairness issue. They rather consider transmission rate-type
utilities [3]. Water-filling based power control policies have been widely
tied with the use of orthogonal frequency division multiplexing (OFDM) in
wireless communications to mitigate the multiple path effect. As an example,
water-filling has been used in the context of OFDM cognitive radio systems
[4], LTE systems [5] and LTE-Advanced systems [6]. Authors of [7] proposed a
Nash equilibrium based water-filling algorithm for a Multiple Input Multiple
Output (MIMO) system in underground tunnel. An iterative water-filling
algorithm was proposed for non-orthogonal multiple access (NOMA) [8]. [9]
proposed a low complexity water-filling power allocation algorithm applied to
the proportional fair scheduler for downlink NOMA systems. Authors of [10]
proposed a transmission power allocation policy for HetNets using a water-
filling algorithm. In [11], authors proposed an energy-efficient power
allocation for D2D communications underlaying cellular networks using a quasi-
water-filling approach.

In [12], authors proposed an algorithm to evaluate a water-filling solution by
considering a general water-filling formulation with multiple water-levels and
multiple constraints. [13] considered the problem of maximizing sum rate of a
multiple-antenna Gaussian broadcast channel. The problem of optimizing power
allocation in order to maximize mutual information has been solved in [14]
using the mercury water-filling principle. A generalization of the mercury
water-filling algorithm for multiple-input multiple output (MIMO) Gaussian
channels, while taking into account the interference among inputs, was given
by [15]. In [16], authors proposed a water-filling based power allocation for
Gaussian channels and approximately Gaussian inputs. In [17], authors extended
the mercury water-filling policy to the multi-user context. The key idea
behind mercury water-filling is to increase/decrease the water-levels to allow
good/bad users to transmit more often than in the case of classical water-
filling. Note that mercury water-filling enables us to design an efficient
power allocation. However, the difficulty of obtaining closed-form analytical
expressions, in the multiple users multiple channel model, often makes
computing the mercury water-filling solution challenging. The algorithm
introduced in this paper called FEAT is similar to mercury water-filling, but
the way it is done is not by changing the water-filling level, but
eliminating/adding available carriers on which users could have transmitted in
the case without FEAT.

This paper, instead of dealing with classical multi-user information rate
optimization problems resulting in significantly complicated water-filling
solutions that include multiple water-levels and multiple constraints, has
considered a different way to switch off transmission in users’ links which do
not contribute enough to the information rate to outweigh the interference
degradation caused by them to the rest of the system. This is done by
iteratively limiting the number of available carriers for each user instead of
changing the water-levels as it is done in the above-mentioned water-filling
problems.

The main goal of FEAT is to maximize the information rate, while keeping a
decent level of fairness. More specifically, FEAT has the following benefits:

  * •

It minimizes the ratio between the best and the worst utilities of the users.
We do that by ensuring that, at each iteration (channel assignment), a user is
satisfied with his assignment as long as he does not loose much more than
other users do,

  * •

It tries to give each user his best carrier (the one that gives him the
highest utility) whenever it is possible, _i.e._ , there are enough channels
for every user and this carrier is not taken by another user,

  * •

Users with the lowest utility are given more opportunity to add new carriers
to their lists in the next iteration of the algorithm.

The remainder of the paper is organized as follows: The system model is
introduced in Section II, then the game theoretic formulation is detailed in
Section III and the achievable rates in Section IV. The proposed solution is
presented in Section V, followed by properties of FEAT in Section VI.
Numerical results are shown in Section VII. Finally, concluding remarks are
drawn in Section VIII.

##  II The Multiple Access System Model

We consider an uplink communication scenario of $K$ parallel Gaussian MAC with
$N$ users in the system. These parallel channels can be treated as different
subchannels in a multi-carrier system. At the transmitter side, the signal
$x_{n}^{k}$ transmitted on the $k^{th}$ subcarrier by user $n$ to the base
station (BS) is the normalized (_i.e._ , unit-power) symbol $s_{n}^{k}$
balanced by some power coefficient $p_{n}^{k}:x_{n}^{k}=\sqrt{p_{n}^{k}}\cdot
s_{n}^{k}$, where the symbols $s_{n}^{k}$ are usually drawn from Gaussian
distribution. At the receiver side, $y^{k}$ represents the received signal on
the $k^{th}$ channel, which is the sum of the contributions received from all
users. Hence, the channel model can we written as

$\displaystyle y^{k}=\sum_{n=1}^{N}h_{n}^{k}x_{n}^{k}+z^{k},$ (1)

where $z^{k}\sim\mathcal{N}(0,\sigma^{2})$ is the additive white Gaussian
noise and $h_{n}^{k}$ is the fading channel of user $n$ transmitting on
carrier $k$ modeled as independent identically distributed (i.i.d.) variables
over the Rayleigh fading coefficients. We further assume that the overall
bandwidth $W$ can be divided into an arbitrary number of narrow-band carriers
($K\geq 2$), the subcarrier is narrow enough to undergo flat fading, and the
channel gain is quasi-static fading for which the channels are constant within
a given time slot but change independently from one slot to another. Without
the constraint of exclusive assignment of each carrier for users, we generally
formulate the problem of spectral efficiency maximization by allowing that a
carrier could be shared by all users. Accordingly, for any user
$n\in\\{1,2.\ldots,N\\}$, the instantaneous per user information rate in
bits/s/Hz, also called _spectral efficiency_ is expressed as

$u_{n}(\textbf{p})=\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m\neq n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right),$ (2)

where $g_{n}^{k}=|h_{n}^{k}|^{2}$ is the fading channel gain of user $n$
transmitting on carrier $k$. It follows from the above expression that the
strategy chosen by a user affects the performance of other users in the
network through multiple-access interference. Now, we can define the
optimization problem we are studying as

$\\{p_{n}^{1*},...,p_{n}^{K*}\\}=\arg{\hbox{$\underset{{p_{n}^{1},...,p_{n}^{K}}}{\max}\,$}}\,u_{n}(\textbf{p})$
(3)

subject to

$\sum_{k=1}^{K}p_{n}^{k}=\overline{P_{n}},$ (4)

where $\overline{P_{n}}$ denotes the power budget of user $n$.

##  III The game theoretic formulation

The instantaneous information rate determines the maximum achievable rate over
all fading states without a delay constraint. In this work, we allocate
transmit powers to each user (over a total power budget constraint) in order
to maximize the individual transmission rate in (2). In fact, when channel
state information is made available at the transmitters, users know their own
channel gains and thus they will adapt their transmission strategy relative to
this knowledge. The solution of the optimization problem in (3) is the well-
known _water-filling_ allocation [2] expressed
by111$(x)^{+}=\textrm{max}(0,x)$.:

$p_{n}^{k*}=\left(\frac{1}{\lambda_{0}}-\frac{\sigma^{2}+\sum_{m\neq
n}p_{m}^{k}g_{m}^{k}}{g_{n}^{k}}\right)^{+},\\\ $ (5)

where $\lambda_{0}$ is Lagrange’s multiplier corresponding to user $n$’s
average power constraint in (4).

The situation presented above can be described as an $N$-person non-
cooperative game with player utilities $u_{n}$, $n=1,\ldots,N$ and strategy
sets
$\mathcal{P}_{n}=\\{p_{n}=(p^{1}_{n},\ldots,p^{K}_{n}):\sum_{k=1}^{K}p_{n}^{k}=\overline{P_{n}}\\}$,
$n=1,\ldots,N$.

The basic solution concept used in non-cooperative game theory is that of Nash
equilibrium (NE) [18]. It is a vector of strategies (referred to hereafter and
interchangeably as actions) $\textbf{p}^{NE}=(p_{1}^{NE},\ldots,p_{N}^{NE})$,
one for each player, such that no player has an incentive to unilaterally
change his strategy, _i.e._ ,

$u_{i}(\textbf{p}^{NE})\geq
u_{i}(p_{1}^{NE},\ldots,p_{i-1}^{NE},p_{i},p_{i+1}^{NE},\ldots,p_{N}^{NE})\quad\mbox{for
every action }p_{i}\neq p_{i}^{NE}.$ (6)

If for some constant $\epsilon>0$ a weaker version of (6):

$(1+\epsilon)u_{i}(\textbf{p}^{NE})\geq
u_{i}(p_{1}^{NE},\ldots,p_{i-1}^{NE},p_{i},p_{i+1}^{NE},\ldots,p_{N}^{NE})\quad\mbox{for
every action }p_{i}\neq p_{i}^{NE}$

is satisfied, we say that $\textbf{p}^{NE}$ is an $\epsilon$-Nash equilibrium.

In [19], it has been shown that the game is an exact potential game and
possesses a unique NE in pure strategies. The following lemma describes such
equilibrium.

######  Lemma 1.

Let the power allocation profiles
$p_{1}=(p^{1}_{1},p^{2}_{1},\ldots,p^{K}_{1})\in\mathcal{P}_{1},p_{2}=(p^{1}_{2},p^{2}_{2},\ldots,p^{K}_{2})\in\mathcal{P}_{2},\ldots,p_{N}=(p^{1}_{N},p^{2}_{N},\ldots,p^{K}_{N})\in\mathcal{P}_{N}$
form a Nash equilibrium of the game. Then, for all $n\in\\{1,2,\ldots,N\\}$
and for all $k\in\\{1,2,\ldots,K\\}$, it follows that $p_{n}^{k}$ satisfies
the equality in (5).

###### Proof.

The proof follows by noticing that for all $n\in\\{1,2,\ldots,N\\}$, the power
allocation vector
$p_{n}=(p^{1}_{n},p^{2}_{n},\ldots,p^{K}_{n})\in\mathcal{P}_{n}$, such that
for all $k\in\\{1,2,\ldots,K\\}$, $p_{n}^{k}$ satisfies (5) is the best
response of player $n$ to the power allocation vectors adopted by all the
other players. ∎

##  IV Achievable rates

In order to gain deeper insights into the achievable rates of the game
theoretic scheme, we aim in this section to reveal the relationship between
the utility obtained at the NE and the fundamental limit on the individual
information transmission rate.

Let us first define the globally optimal solution, which is the set of powers
$p_{1}=(p^{1}_{1},p^{2}_{1},\ldots,p^{K}_{1})\in\mathcal{P}_{1},p_{2}=(p^{1}_{2},p^{2}_{2},\ldots,p^{K}_{2})\in\mathcal{P}_{2},\ldots,p_{N}=(p^{1}_{N},p^{2}_{N},\ldots,p^{K}_{N})\in\mathcal{P}_{N}$
that maximizes the sum information transmission rate given by

$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{\displaystyle\sum_{n=1}^{N}g_{n}^{k}p_{n}^{k}}{\sigma^{2}}\right)=\sum_{n=1}^{N}\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right),$ (7)

where the equality in (7) is proved in the Appendix (see Eq. (18)).

Then, for all $n\in\\{1,2,\ldots,N\\}$, the information transmission rate
achieved by player $n$, denoted by $R_{n}\geqslant 0$, depends on the receiver
configuration. More specifically, for all $n\in\\{1,2,\ldots,N\\}$, the
following upper-bound holds in the case of NE, in which the receiver treats
interference as noise:

$\displaystyle R_{n}$ $\displaystyle\leq$ $\displaystyle u_{n}(\textbf{p})$
(8) $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m\neq n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right).$ (9)

Alternatively, for all $n\in\\{1,2,\ldots,N\\}$, the following upper-bound
holds in the case of the fundamental limit on the individual information
transmission rate for player $n$, for the case of descending decoding order,
see for instance [2]. Here, the receiver implements a successive interference
cancellation (SIC) scheme with descending decoding order:

$\displaystyle R_{n}$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right).$ (10)

Moreover, note also that, for all $n\in\\{1,2,\ldots,N\\}$ and for all
$\textbf{p}\in\mathcal{P}_{1}\times\mathcal{P}_{2}\times\ldots\times\mathcal{P}_{N}$,

$\displaystyle
u_{n}(\textbf{p})=\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m\neq n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right)$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right).$ (11)

The inequality in (11) is proved in the Appendix (see Eq. (20)). In
particular, when the power profile p in Eq. (11) satisfies the equality in Eq.
(5), the above inequality sets an upper-bound for the individual utility of
player $n$, which turns out to be relevant for the performance analysis of the
algorithm FEAT later in the paper.

##  V Approximate solutions for the $N$-player game

This section introduces the main contribution, namely, an algorithm whose
output is the set of channel indices assigned to each transmitter. This
channel assignment is performed taking into account the following
observations:
$(a)$ When all transmitters are let to use all the available channels, the
highest information sum rate is achieved by a scheme in which transmitters are
assigned an order. Transmitter $1$ uses a power allocation obtained by using
the water-filling algorithm over all channels in the absence of interference.
For all $i\in\\{2,3,\ldots,n\\}$, Transmitter $i$ uses a power allocation
obtained by using the water-filling algorithm considering the interference of
all previous transmitters. At the Receiver, a SIC algorithm is implemented in
which transmitters are decoded in descending order. That is, Transmitter $n$
is decoded first, whereas, Transmitter $1$ is decoded in the last position.
The highest information sum rate is independent of the order given to the
transmitters, under the assumption that SIC is based on perfect decoding.
Alternatively, the individual information rate does depend on such order [20].
$(b)$ In the absence of SIC, all transmitters are subject to mutual
interference and thus, the sum information rate is severely decreased. In this
context, constraining the transmitters to use only a subset of all available
channels have been shown to be an interesting alternative [21].
$(c)$ When transmitters are constrained to use only a subset of all available
channels, e.g., $L$ channels ($L<K$), the individual rates depend on the
choice of such $L$ channels for each transmitter. More specifically, given an
order $g_{i}^{\ell_{1}}>g_{i}^{\ell_{2}}>\ldots>g_{i}^{\ell_{k}}$, for some
$i\in\\{1,2,\ldots,n\\}$ such that for all $s\in\\{1,2,\ldots,k\\}$,
$\ell_{s}\in\\{1,2,\ldots,k\\}$, a channel assignment consisting in the set
$\\{g_{i}^{\ell_{1}}$, $g_{i}^{\ell_{2}}$, $\ldots$, $g_{i}^{\ell_{L}}\\}$
leads to a higher individual information rate for Transmitter $i$ than any
other channel assignment. That is, individual rates are monotonically
increasing with the channel gains.
$(d)$ When the ratio between number of channels and number of transmitters is
small, it is likely that the best channel assignment for Transmitter $i$ and
Transmitter $j$ are sets whose intersection is not empty, which leads to
conflict.

The observations above lead to the notion of fairness when transmitters are
subject to use only disjoints subsets of channels. From observations $(c)$ and
$(d)$, it follows that assigning always the best channels to the same user is
far from fair. The proposed algorithm is based on the following arbitrary
assumption: When a channel must be assigned to a transmitter, the benefit of
such assignment can be measured by the ratio between the channel coefficient
of the assigned channel, and the highest channel coefficient available for
such transmitter. That is, the higher this ratio, the more beneficial the
allocation is.

Suppose the assignment of one channel is done according to the function
$\nu:\\{1,\ldots,N\\}\rightarrow\\{1,\ldots,K\\}$. The global benefit of this
assignment can be measured by the quantity

$\alpha(\nu):=\min_{n\leq N}\frac{g^{\nu(n)}_{n}}{\max_{l\leq K}g^{l}_{n}}.$
(12)

The main goal of the FEAT algorithm is to find channel assignments that
maximize the value of $\alpha$ every time that a channel must be assigned.

The proposed algorithm assigns a different channel to all users at each round.
This is done in such a way that $\alpha$ is maximized at the end of the round.

The FEAT algorithm has two parameters $\delta>0$ and $\beta\in(0,1)$: $\delta$
is maximum error of computing $\alpha$ so it should be small, whereas $\beta$
is the percentage of the maximum throughput below which we assume that a user
is not served well enough, thus he gets additional carriers to transmit on; it
should then be relatively big. For a vector $\pi$, $|\pi|$ denotes its length.

######  Algorithm 1.

FEAT : Fair coordinatEd iterAtive waTer-filling algorithm
We start with $M=K$, $\pi^{*}=[1,\ldots,N]$, $\pi_{0}=[1,\ldots,N]$ and
$\rho_{n}^{k}=\frac{g_{n}^{k}}{\max_{l\leq K}g_{n}^{l}}$, $n=1,\ldots,N$,
$k=1,\ldots,K$ and create empty lists $\mathcal{L}_{n}$, $n=1,\ldots,N$.
While $M>0$ do
Phase A: For $n=1,\ldots,|\pi^{*}|$, sort $\rho_{\pi^{*}(n)}^{k}$,
$k=1,\ldots,K$ from the biggest to the smallest, obtaining
$\rho_{\pi^{*}(n)}(1),\ldots,\rho_{\pi^{*}(n)}(K)$. Set
$\underline{\alpha}=0$, $\overline{\alpha}=1$ and $\alpha^{*}=0$.
Repeat the following steps until the procedure is interrupted in point A.1):

  1. A.1)

If $\overline{\alpha}-\underline{\alpha}<\delta$ stop. Otherwise take
$\alpha^{*}=\frac{\overline{\alpha}+\underline{\alpha}}{2}$ and
$\pi=\boldsymbol{0}_{1\times K}$.

  2. A.2)

For $n=1,\ldots,|\pi^{*}|$ do the following steps:
Find the smallest $\rho_{\pi^{*}(n)}(l^{*})$ such that
$\rho_{\pi^{*}(n)}(l^{*})\geq\alpha^{*}$. If $\pi(l^{*})=0$ then put
$\pi(l^{*})=\pi^{*}(n)$. Otherwise, find the biggest $l<l^{*}$ such that
$\pi(l)=0$, and put $\pi(l)=\pi^{*}(n)$. If $\pi(l)\neq 0$ for every positive
$l<l^{*}$ put $\overline{\alpha}=\alpha^{*}$ and return to point A.1).

  3. A.3)

Put $\pi^{*}=\pi$ with all the zero elements removed,
$\underline{\alpha}=\alpha^{*}$ and return to point A.1).

Phase B: $m_{0}=0$. For $n=1,\ldots,|\pi^{*}|$, do the following steps:

  1. B.1)

$k$ with the highest $\rho^{k}_{\pi^{*}(n)}$ is chosen. Let it be denoted by
$\mathcal{K}(n)$.

  2. B.2)

If
$\sum_{l\in\mathcal{L}_{\pi^{*}(n)}}\frac{1}{g^{l}_{\pi^{*}(n)}}>\frac{|\mathcal{L}_{\pi^{*}(n)}|}{g^{\mathcal{K}(n)}_{\pi^{*}(n)}}-\frac{\overline{P}_{\pi^{*}(n)}}{\sigma^{2}}$,
then $\mathcal{K}(n)$ is added to the list $\mathcal{L}_{\pi^{*}(n)}$,
$m_{0}=m_{0}+1$ and for $i=1,\ldots,N$, $\rho^{\mathcal{K}(n)}_{i}=0$. Else
$\pi^{*}(n)$ is removed from the list $\pi_{0}$.

Phase C: Set $M=M-m_{0}$ and $\pi^{*}=[]$ (empty vector).
If $|\pi_{0}|>0$ and $M>0$, do the following steps:

  1. C.1)

For $n=1,\ldots,|\pi_{0}|$ compute
$Q(n)=\sum_{k\in\mathcal{L}_{\pi_{0}(n)}}\log_{2}\left[\frac{g^{k}_{\pi_{0}(n)}}{|\mathcal{L}_{\pi_{0}(n)}|}\left(\frac{\overline{P}_{\pi_{0}(n)}}{\sigma^{2}}+\sum_{l\in\mathcal{L}_{\pi_{0}(n)}}\frac{1}{g^{l}_{\pi_{0}(n)}}\right)\right]$.
Put $Q_{\max}=\max_{n=1,\ldots,|\pi_{0}|}Q(n)$.

  2. C.2)

Sort pairs $(\pi_{0}(n),Q(n))$, $n=1,\ldots,|\pi_{0}|$ by their second
coordinates in an increasing order, obtaining $[\pi^{*},Q^{*}]$.
If $Q^{*}(1)\leq\beta Q_{\max}$ and $m_{0}>0$, take
$k^{*}=\max\\{k\leq\min\\{M,|\pi_{0}|\\}:Q^{*}(k)\leq\beta Q_{\max}\\}$,
$\pi^{*}=\pi^{*}(1,\ldots,k^{*})$,
else $\pi^{*}=\pi^{*}(1,\ldots,\min\\{M,|\pi_{0}|\\})$;

else break.

The output of the algorithm is the partition of the spectrum
$\\{1,\ldots,K\\}$ into lists $\mathcal{L}_{1},\ldots,\mathcal{L}_{N}$. Then
the strategy for each player $n$ is obtained by applying water-filling from
Eq. (5) only to carriers from his list $\mathcal{L}_{n}$.

To understand what we do in the algorithm presented above on an intuitive
level, first note that in each iteration of its main loop, at most one carrier
is added to the list of each player. Below, we will try to explain the way
these additions are made phase by phase.

First, to understand the sense of Phase A, note that the fraction
$\rho_{n}^{k}$ appearing there can be interpreted as a measure of disutility
of player $n$ from choosing carrier $k$ instead of his best one. In the
algorithm, we aim at dividing the spectrum into separate sets of carriers with
only one user transmitting on each. So the utilities from using a given
carrier are always of the form
$\log_{2}\left(1+\frac{pg_{n}^{k}}{\sigma^{2}}\right)$ (for a while we assume
that the transmission power $p$ is fixed, rather than chosen by water-
filling). Maximizing the value of $\rho_{ik}$ is thus equivalent to choosing
the carrier with highest utility. Given this interpretation, the $\alpha^{*}$
appearing in Phase A of the algorithm can be interpreted as the maximal
disutility for any player from not choosing his carrier first, that is the
worst-case222Worst-case here means that such a big disutility will only be
possible if different users’ private ordering (from best to worst) of the
channels is similar. ratio of utility of any of the players who do not choose
their carriers first to their utility if they were the first ones to choose.
The sense of Phase A is thus finding the ordering of the players which
minimizes this disutility. It is done by putting on $i$-th coordinate of
ordering $\pi^{*}$ a player (his index), who has at least $i$ good channels to
choose from (by which we mean $i$ channels with utility better than
$\alpha^{*}$ times his best possible utility if he was a leader). $\alpha^{*}$
found by FEAT is the maximal value (computed with a $\delta$ toleration) for
which such an ordering is possible.

Next, in Phase B, players ordered in Phase A choose one by one the best
carrier (the one that gives them the highest utility) which is not yet taken
by them or one of the other users and add these carriers to the lists of
carriers where they are allowed to transmit.

Finally, in Phase C, the utility of each user when water-filling is applied to
their current lists of carriers, $Q(n)$ is computed. The players with the
lowest utility (precisely – those whose utility is smaller than $\beta$ times
the biggest utility among the users) are chosen and they are given the
opportunity to profit from additional carriers to their lists in the next
iteration of the main loop of the algorithm.

In summary, we have the following information to be exchanged between the base
station and users:

  1. 1.

Each UE $n$ sends beacons to his serving BS in order to estimate his channel
gain at the $k^{th}$ subcarrier $g_{n}^{k}$,

  2. 2.

BS computes and sends the lists $\mathcal{L}_{n}$ for each user $n$,

  3. 3.

Each UE $n$ computes his power policy using Eq. (3) by applying the water-
filling only to carriers from his list $\mathcal{L}_{n}$.

##  VI Properties of FEAT

###  VI-A Disjoint carrier water-filling game

In this section, we consider a slightly modified water-filling game, assuming
that, as before the goal of each user is to maximize his throughput, but no
two users are allowed to transmit on the same carrier. Note that such a game
is a generalized game in the sense of Debreu [22]. Equilibria in such a game
are defined as in classical noncooperative games with a slight change that the
set of actions available to a player depend on those applied by the others. We
will show that an equilibrium in such a modified water-filling game (called
disjoint carrier water-filling game in the sequel) is what we obtain as a
result of FEAT. We begin the section with a simple characterization of the set
of all equilibria of this game.

######  Proposition 1.

Suppose the vector $\textbf{p}=(p_{1},\ldots,p_{N})$ is such that
$\mathcal{L}_{i}:=\\{k\in\\{1,\ldots,K\\}:p_{i}^{k}>0\\}$, $i=1,\ldots,N$ are
disjoint subsets of $\\{1,\ldots,K\\}$ and that
$\mathcal{L}_{0}:=\\{1,\ldots,K\\}\setminus\bigcup_{i=1}^{N}\mathcal{L}_{i}$.
Then, p is a NE in the disjoint carrier water-filling game, if and only if for
each user $i$, $p_{i}$ is his water-filling allocation with the set of
available carriers reduced to $\mathcal{L}_{i}\cup\mathcal{L}_{0}$.

###### Proof.

We know that the power allocation maximizing throughput of player $i$ is
water-filling allocation [2], thus in any NE of the game each player has to
waterfill on all the available carriers. Since in the situation when other
users use allocations $p_{j}$, $j\neq i$, he is limited to the set
$\mathcal{L}_{i}\cup\mathcal{L}_{0}$ by the rules of the game, p can only be a
NE iff $i$ is water-filling on this set and if the same is true for any other
user. ∎

An immediate consequence of Proposition 1 is as follows:

######  Corollary 1.

The output of FEAT corresponds to a NE of the disjoint carrier water-filling
game.

###### Proof.

Note that whenever the output of FEAT is a partition of entire set of carriers
$\\{1\ldots,K\\}$ into disjoint sets of carriers of each player
$\mathcal{L}_{i}$, $i=1,\ldots,N$, water-filling on these sets will clearly be
a NE in the disjoint water-filling game by Proposition 1. Suppose then that
the set
$\mathcal{L}_{0}=\\{1,\ldots,K\\}\setminus\bigcup_{i=1}^{N}\mathcal{L}_{i}$ is
nonempty. In that case, FEAT can only terminate, if $|\pi_{0}|=0$. But this
means that all the users have been removed from $\pi_{0}$, because there were
no carriers left such that transmission on them could improve their utility
from water-filling. Hence, the water-filling allocation of any player $i$, if
he waterfilled on $\mathcal{L}_{i}$ would be the same as if he waterfilled on
$\mathcal{L}_{i}\cup\mathcal{L}_{0}$, which implies that the output of the
algorithm corresponds to an equilibrium in the disjoint carrier water-filling
game. ∎

###  VI-B General properties of the algorithm

In the next proposition we are giving the worst-case bounds on crucial metrics
by which we can evaluate the output of FEAT as a solution to the water-filling
game.

######  Proposition 2.

Suppose that $N\leq K$ and that the sets
$\mathcal{L}_{1},\ldots,\mathcal{L}_{N}$ are outputs of FEAT and that
$\textbf{p}=(p_{1},\ldots,p_{N})$ is such that for each $i$, $p_{i}$ is a
water-filling allocation of user $i$ limited to carriers from
$\mathcal{L}_{i}$. Let further $\alpha^{*}_{1}$ denote the value of
$\alpha^{*}$ at the end of the first iteration of the main loop of FEAT and
define the following quantities:

$\Theta_{\max}=\max_{i\in\\{1,\ldots,N\\}}\max_{k\in\\{1,\ldots,K\\}}\overline{P}_{i}g_{i}^{k},$
$\Theta_{\min}=\min_{i\in\\{1,\ldots,N\\}}\max_{k\in\\{1,\ldots,K\\}}\overline{P}_{i}g_{i}^{k},$
$\Omega=\frac{\Theta_{\max}}{\sigma^{2}\alpha^{*}_{1}\ln\left(1+\frac{\Theta_{\max}}{\sigma^{2}}\right)}+\frac{1-\alpha^{*}_{1}}{(\alpha^{*}_{1})^{2}\ln\left(1+\frac{\Theta_{\min}}{\sigma^{2}}\right)}>1.$

Then:

  1. (a)

p is an $(\Omega-1)$-NE in the water-filling game.

  2. (b)

The social welfare in the water-filling game when the strategy vector p is
used, is at most $\Omega$ times smaller than its optimal value.

  3. (c)

If all the users apply strategies p, the ratio
$\frac{\max_{i\in\\{1,\ldots,N\\}}u_{i}}{\min_{i\in\\{1,\ldots,N\\}}u_{i}}$ is
bounded above by
$\frac{\Theta_{\max}}{\sigma^{2}\log_{2}\left(1+\frac{\alpha^{*}_{1}\Theta_{\min}}{\sigma^{2}}\right)}$.

###### Proof.

(a) The biggest individual loss of utility by a player that can happen as a
consequence of using FEAT is when a player, say player $i$, is forced by the
algorithm to use only his worst carrier $k^{*}$ (the one with the lowest
$g_{i}^{k}$), while he should use all of them to maximize his utility.
Moreover, the interference on these other carriers is negligible. To bound
this loss of utility, we will assume there is no interference at all on any
carrier. Then, since the worst carrier can only be chosen by FEAT as the only
carrier to transmit on if
$\rho_{i}(k^{*})=\frac{g_{i}^{k^{*}}}{\max_{k\in\\{1,\ldots,K\\}}g_{i}^{k}}\geq\alpha^{*}_{1}$,
to maximize player $i$’s utility we should assume that
$g_{i}^{k}=\frac{g_{i}^{k^{*}}}{\alpha_{1}^{*}}$ for $k\neq k^{*}$. Then, the
utility of player $i$ from using FEAT is

$u_{i}^{0}=\log_{2}\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}}\right)$
(13)

while the upper bound on his utility $u_{i}^{\max}$ can be computed as
follows: From the water-filling formula (5) we know that:

$p_{i}^{k^{*}}=\left(\frac{1}{\lambda_{0}^{i}}-\frac{\sigma^{2}}{g_{i}^{k^{*}}}\right)^{+},$
$p_{i}^{k}=\left(\frac{1}{\lambda_{0}^{i}}-\frac{\alpha^{*}_{1}\sigma^{2}}{g_{i}^{k^{*}}}\right)^{+}\mbox{
for }k\neq k^{*}$

with $\lambda_{0}^{i}$ satisfying

$\frac{K}{\lambda_{0}^{i}}-\frac{\sigma^{2}}{g_{i}^{k^{*}}}(1+\alpha_{1}^{*}(K-1))=\overline{P}_{i}.$

After some algebra, we thus obtain

$p_{i}^{k^{*}}=\frac{\overline{P}_{i}}{K}-\frac{(K-1)\sigma^{2}}{g_{i}^{k^{*}}K}(1-\alpha_{1}^{*}),$
$p_{i}^{k}=\frac{\overline{P}_{i}}{K}+\frac{\sigma^{2}}{g_{i}^{k^{*}}K}(1-\alpha_{1}^{*})\mbox{
for }k\neq k^{*}$

if the former is positive or

$p_{i}^{k^{*}}=0,\quad p_{i}^{k}=\frac{\overline{P}_{i}}{K-1}\mbox{ for }k\neq
k^{*}$

otherwise. We shall concentrate on the first case – all the bounds obtained
will trivially also hold for the second one.

Inputting the powers into utility, we get

$\displaystyle u_{i}^{\max}$ $\displaystyle=$
$\displaystyle(K-1)\log_{2}\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\alpha^{*}_{1}\sigma^{2}K}+\frac{1-\alpha^{*}_{1}}{\alpha^{*}_{1}K}\right)+\log_{2}\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}K}-\frac{(K-1)(1-\alpha_{1}^{*})}{K}\right)$
$\displaystyle<$ $\displaystyle
K\log_{2}\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\alpha^{*}_{1}\sigma^{2}K}+\frac{1-\alpha^{*}_{1}}{\alpha^{*}_{1}K}\right).$

Note that for any $A>0$

$\left(\frac{\log_{2}(1+Ax)}{x}\right)_{x}=\frac{\frac{Ax\ln(2)}{1+Ax}-\log_{2}(1+Ax)}{x^{2}}.$
(14)

As
$\left(\frac{Ax\ln(2)}{1+Ax}-\log_{2}(1+Ax)\right)_{x}=\ln(2)\left(\frac{A}{(1+Ax)^{2}}-\frac{A}{1+Ax}\right)=\frac{-A^{2}\ln(2)}{(1+Ax)^{2}}<0$,
the RHS of (14) is decreasing in $x$ on $(0,+\infty)$, which means that its
biggest value of 0 is obtained for $x=0$. Hence, for any positive constant
$A$, $\frac{\log_{2}(1+Ax)}{x}$ is a decreasing function of $x$ for $x>0$ and
$\lim_{x\rightarrow 0}\frac{\log_{2}(1+Ax)}{x}=\frac{A}{\ln 2}$. Applying this
to the obtained bound on $u_{i}^{\max}$ we obtain

$u_{i}^{\max}<\frac{1}{\ln
2}\left(\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\alpha^{*}_{1}\sigma^{2}}+\frac{1-\alpha^{*}_{1}}{\alpha^{*}_{1}}\right).$

Using this and (13) we thus obtain

$\frac{u_{i}^{\max}}{u_{i}^{0}}<\frac{\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\alpha^{*}_{1}\sigma^{2}}+\frac{1-\alpha^{*}_{1}}{\alpha^{*}_{1}}}{\ln\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}}\right)}=\frac{\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}}}{\alpha^{*}_{1}\ln\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}}\right)}+\frac{1-\alpha^{*}_{1}}{\alpha^{*}_{1}\ln\left(1+\frac{\overline{P}_{i}g_{i}^{k^{*}}}{\sigma^{2}}\right)}\leq\Omega,$
(15)

which implies that p is an $(\Omega-1)$-NE in the water-filling game.

(b) If we use the inequality (15) for each player, we obtain that the ratio of
the upper bound on the social welfare and the social welfare when strategy
vector p is applied can be bounded as follows:

$\frac{\sum_{i=1}^{N}u_{i}^{\max}}{\sum_{i=1}^{N}u_{i}^{0}}\leq\frac{\sum_{i=1}^{N}\Omega
u_{i}^{0}}{\sum_{i=1}^{N}u_{i}^{0}}=\Omega,$

which ends the proof of part (b) of the proposition.

(c) We know that after the first iteration of the main loop of FEAT, each user
$i$ gets one carrier, say $k_{i}$, to transmit on, such that

$\rho_{i}(k_{i})=\frac{g_{i}^{k_{i}}}{\max_{\\{k\in\\{1,\ldots,K\\}}g_{i}^{k}}\geq\alpha^{*}_{1}.$

This obviously implies that his utility corresponding to the vector of
strategies p (that is – at the end of the algorithm), is not smaller than

$u_{i}^{\min}=\log_{2}\left(1+\frac{\overline{P}_{i}\alpha_{1}^{*}\max_{\\{k\in\\{1,\ldots,K\\}}g_{i}^{k}}{\sigma^{2}}\right)\geq\log_{2}\left(1+\frac{\Theta_{\min}}{\sigma^{2}}\right).$

On the other hand, the maximal utility that any user $i$ can obtain when he
gets no interference from other users is (here the vector $p^{WF}_{i}$ denotes
the water-filling allocation of player $i$)

$\displaystyle u_{i}^{\mbox{WF}}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{p^{WF,k}_{i}g_{i}^{k}}{\sigma^{2}}\right)<\sum_{k=1}^{K}\frac{p^{WF,k}_{i}g_{i}^{k}}{\sigma^{2}}$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\frac{p^{WF,k}_{i}\max_{l\in\\{1,\ldots,K\\}}g_{i}^{l}}{\sigma^{2}}=\frac{\overline{P}_{i}\max_{l\in\\{1,\ldots,K\\}}g_{i}^{l}}{\sigma^{2}}\leq\frac{\Theta_{\max}}{\sigma^{2}}.$

Dividing (VI-B) side by side by (VI-B), we obtain the desired inequality. ∎

######  Remark 1.

The value of $\Omega$ does not directly depend on $K$, so it suggests that the
quality of the solution obtained by FEAT (by which we may mean the ‘distance’
from the social optimum or individually optimal solution described by a NE)
does not depend on $K$ at all. Note however that the constants
$\alpha^{*}_{1}$, $\Theta_{\max}$ and $\Theta_{\min}$ all depend on the values
of $g_{i}^{k}$s which are in fact i.i.d. exponential variables. From
simulations we can infer that $\Omega$ depends on $K$ sublinearly.

######  Remark 2.

The bounds given by parts (a) and (b) of Proposition 2 are tight in the sense
that we can get arbitrarily close to these bounds when $K$ is large and
channels are strongly correlated across users. Moreover, the qualities of most
carriers are not good, so at least one of the users ends up assigned to some
of his bad carriers whatever the value of $K$ is.

As for the bound given in part (c) of the proposition, it only takes into
account what happens during the first iteration of the main loop of FEAT, so
the bound is rather loose. Note, that one of the main goals of the algorithm
is to minimize the ratio between the best and the worst utilities of the
users. The way it is done is however rather difficult to quantify.

######  Remark 3.

Note that the situation described in Remark 2, which is used to prove (a) and
(b) of Proposition 2, although theoretically possible, is rather unlikely to
happen if the CQIs are i.i.d. exponential variables. In fact, what we should
expect in a typical case is that the second term in the bound of
$\frac{u_{i}^{\max}}{u_{i}^{0}}$ given by (15) will disappear when $K$ becomes
large, as $\alpha^{*}_{1}\rightarrow 1$ and the denominator of this part will
grow with $K$ going to infinity. On the other hand, the denominator of the
first term when $K>N$ can be replaced by the total utility from using all the
carriers assigned to user $i$ by FEAT, which will grow at a similar rate as
the numerator with increase of $K$ (as additional carriers are added to
$\mathcal{L}_{i}$). We are thus convinced, that the expected quality of the
solutions found by FEAT will in fact tend to a constant for any given $N$ as
$K\rightarrow\infty$, which is much better than the Proposition 2 suggests.
Quantifying these expected values is again however much more difficult than
obtaining the worst-case estimates given there.

###  VI-C Complexity of the algorithm

It is easy to see that the complexity of Phase A of FEAT is $O(NK\log(K))$,
that of Phase B is (note that the number of iterations of the loop inside it
is bounded by a number depending only on $\delta$) $O(NK)$, while that of
Phase C is $O(N\log(N))$. Since on each iteration of the main loop of the
algorithm at least one carrier is assigned to a user or (in case none were
assigned) the list of users who are still available for further assignments is
shrunk, the total number of iterations of the main loop of the algorithm is
bounded above by $N+K$. Finally, note that by assumption, FEAT is applied only
in case $N\leq K$. Putting all this information together, we can conclude the
following:

######  Proposition 3.

The complexity of FEAT is $O(NK^{2}\log(K))$.

##  VII Numerical results

In this section, simulation results are presented to verify the performances
of the proposed algorithm FEAT. For comparison purpose, we exemplify our
general analysis by investigating the following algorithms:

  * •

_the Nash strategy_ : which is the strategy of the non-cooperative game
theoretic problem whose solution is defined in Section III. Then, the utility
is computed by using (2), treating the interference as noise at the receiver
side.

  * •

_the optimal strategy_ : which corresponds to the fundamental limit on the
individual information transmission rate obtained when all users waterfill
considering all other users as interference as expressed in Eq. (5). Then, the
utility is computed using the right hand side of (10) by applying SIC at the
receiver side, _i.e._ , by considering only predecessors as interference (see
Section IV).

This will thus serve as the optimal social welfare solution for the sum rate
maximization problem in order to demonstrate how much gain may theoretically
be exploited through considering such a global optimal solution with respect
to the other schemes. It is noteworthy that, as already mentioned in Section
IV, the optimal solution requires to implement a SIC scheme at the receiver
side, whereas Nash and FEAT do not.

  * •

_the spectrum pooling strategy_ : which is throughput-based-utility [23, 24].
This is done by overlaying users into a common pool. The spectrum pooling
behavior is assumed to allow only one user to simultaneously transmit over the
same sub-band.

## Transmission rate

Figure 1: The average utility as function of $K$ for SNR $=-10$ dB and $N=20$.
Figure 2: The average utility as function of $K$ for SNR $=10$ dB and $N=20$.
Figure 3: The average utility as function of $N$ for different $K$ at SNR =
$10$ dB.

Figure 4: The average utility as function of SNR for $K=40$ and $N=20$.

Figure 5: The average utility as function of $N$ for SNR $=10$ dB and $K=40$.
Figure 6: The average utility as function of $N$ for SNR $=10$ dB and $K=10$.

Fig. 1 and Fig. 2 depict the average spectral efficiency as function of the
number of carriers $K$ for $N=20$ and SNR $=-10$ dB, respectively SNR $=10$
dB. At high SNR regime, users have less opportunities to transmit. So even
though FEAT tries to assign at least one good channel to every user, some
users may end up with average channels. This is responsible for the fact that
the slope of social welfare tends to saturate much faster with decrease of $K$
in Fig. 3. In general, FEAT is better than Pooling and worse than Nash only if
SNR is low (see Fig. 1). This is understandable, as in that case there are
very good opportunities (in terms of spectral efficiency) to transmit. In such
a situation, strictly avoiding interference (as we do in FEAT) is no more the
most profitable thing to do. However, we emphasize that the range of SNR (see
Fig. 5) which gives upper hand to Nash is much smaller than that for FEAT. In
general, notice that the average spectral efficiency at the NE is always
surpassed by the optimal strategy, as already proved in Eq. (11).

In Fig. 5, we see that for low $N$, FEAT is very close to the optimal solution
for a low number of users. As the number of users $N$ increases, the
opportunities to transmit becomes scarce giving rise to an interference-
limited system. In that situation, FEAT outperforms Nash again, but the gap
with the optimal strategy becomes high. This behavior confirms our theoretical
claims in Section IV, where we showed that the utility in (2) is always
bounded above by the fundamental limit on the individual information
transmission rate.

Let us now look at the situation where the number of carriers $K$ decreases.
In Fig. 6, we plot the average spectral efficiency as function of the number
of users $N$ for SNR $=10$ dB and $K=10$. We notice that, as long as $K>N$,
social welfare keeps increasing with $N$. Then, the social welfare does not
grow above some threshold, but remains constant, contrary to Nash where
spectral efficiency decreases as $N$ increases. Pooling gives all resources to
first users in the queue, whereas in FEAT we try to share resources among all
users in the system. In Pooling, when the number of users increases, all
resources have been taken by first users in the queue and there is no addition
in social welfare. In FEAT, even when we increase $N$, the social welfare
keeps increasing because we give resources to users who will use them best and
thus increase social welfare. As we can see from Fig. 7, there are slight
changes of slope when $K$ is a multiple of $N$. What we observe here is that,
as long as $N\leq K$, social welfare increases at higher speed. This can be
explained by the fact that FEAT starts by trying to allocate one good channel
to each user. The channels it allocates to users afterwards are substantially
worse, resulting in slower increase in social welfare. This can be clearly
observed when $K=N=20$.

Figure 7: The average utility as function of $K$ for different SNR for $N=20$.

## Energy efficiency

To study how energy efficient FEAT is, let us consider the following energy
efficiency function that has bits per joule as units, and which perfectly
captures the trade-off between throughput and battery life [25] :

$EE_{n}(\mathbf{p_{1}},\ldots,\mathbf{p_{n}})=\frac{\displaystyle
R_{n}\cdot\sum_{k=1}^{K}f(\gamma_{n}^{k})}{\displaystyle\sum_{k=1}^{K}p_{n}^{k}},$
(16)

where $\mathbf{p_{n}}$ is the power control vector of user $n$ over all his
carriers, _i.e._ , $\mathbf{p_{n}}=(p_{n}^{1},\ldots,p_{n}^{K})$, $R_{n}$
stands for the transmission rate of user $n$ and $f(\cdot)$ is an S-shaped
function, which measures the packet success rate. In Fig. 8, we plot the
energy efficiency as function of $N$ for $K=10$ and a rate $R_{n}=1$ Mbps for
each user $n$. As expected, it is shown that for low $N$, there will be little
interference, so energy is used quite efficiently. This explains why Nash is
close to FEAT in this region. Bigger $N$ gives rise to high interference,
resulting in FEAT performing better in comparison to Nash. As the number of
carriers $K$ increases (see Fig. 9), interference is no more an issue and Nash
performs better, but remains less energy efficient than FEAT, especially for
high number of users. Notice also that Pooling scheme is not energy efficient
in general. The main rationale behind these results is the way how FEAT deals
with interference mitigation. As mentioned earlier, FEAT is more (spectral)
efficient in situations where interference is an issue, as it turns off links
which do not contribute enough information rate to outweigh the interference
degradation caused by them to the rest of the system. We will see next that
FEAT further ensures fairness among users by guaranteeing that every user in
the system is assigned at least one good channel to every user in the system,
as long as there are enough channels for every user.

Figure 8: The average energy efficiency as function of $N$ for $K=10$. Figure
9: The average energy efficiency as function of $N$ for $K=40$.

## Fairness

So far, we have addressed the system performances of FEAT. To go further with
the analysis and to show how fair FEAT is, we resort to user performance.
Specifically, we plot in Fig. 10 the ratio between individual utility of the
worst user and the best user in each of the schemes for $K=40$. As intuition
would suggest, all curves decrease as $N$ increases, as there are less
opportunities for users to pick their best channel. Clearly, FEAT is the best,
whereas Nash and the optimal strategies become not fair for increasing number
of users.

For a low number of users, the ratio between individual utility of the worst
user and the best user increases as the number of carriers increases (see Fig.
11). Here we remark that, when $K<N$, some users are not served by FEAT
(although the algorithm works well for $K<N$), but once we reach the point
where $K=N$, FEAT immediately starts to outperform all other schemes. We
further see in Fig. 11 that there are peaks anytime $K$ is divisible by $N$
because in that case each user will typically be assigned to the same number
of carriers.

Figure 10: The ratio between individual utility of worst user and best user as
function of $N$ for $K=40$. Figure 11: The ratio between individual utility of
worst user and best user as function of $K$ for $N=10$. Figure 12: The
probability to be served for FEAT as function of $N$ for different $K$.

Fig. 12 captures the probability to be served as function of $N$ for different
$K$: it is equal to 0.5 (_i.e._ , half of users are allocated at least one
carrier to transmit on) when $\frac{K}{N}=0.5$. In fact, as long as
$\frac{K}{N}\geq 1$ the probability to be served equals $1$, otherwise it is
equal to $\frac{K}{N}$. As expected, the probability to be served increases
with $K$ and decreases with $N$. We emphasize that there is no possibility of
lack of transmission whenever333Notice that this is not a restriction of the
proposed scheme. In fact, FEAT always produces some output even for $K<N$.
$K>N$. Then, each user transmits on at least one carrier and the sets of
carriers they transmit on are orthogonal (as we can see from Fig. 13).

Figure 13: The probability of no coordination as function of $N$ for $K=10$.

## Robustness

In order to get good intuition on the robustness of FEAT against individual
incentive to deviate, we resort to compute the ratio between the utility of a
random user if he sticks to the output of FEAT and his utility when he
waterfills on all the channels. This will tell us how much incentive may a
random user have to deflect from the output of FEAT, which in fact corresponds
to the measure of the ”distance” between the players’ joint strategy profile
using FEAT and a Nash equilibrium. Accordingly, a ratio close to $1$ means
that users cannot deviate from FEAT and gain, whereas getting further away
from $1$ corresponds to a situation with a bigger gain from individual
deviation. So the closer the ratio gets to $1$ the better it is. This is done
in Fig. 14 for different $K$, because Prop. 2 and corollaries after it are
talking about dependence of this ”distance” from the social optimum and from
NE as a function of $K$. The results seem to confirm our expectations. What we
observe for $K\leq N$ is that users have the same incentive to deviate and
that the decrease of the ratio is rather fast. The explanation of this is
simple: When $K<N$, FEAT only assigns first $K$ users to channels – all the
remaining ones remain unassigned, which means that with probability
$\frac{N-K}{N}$ they can increase their utility from 0 to some positive value,
while with remaining probability the maximum increase in their utility is
limited. For $K\geq N$, we observe that the distance from Nash is almost
constant and dependent (in a decreasing manner) on $N$. The stabilization of
it is what we expected, as explained in Remark 3. The dependence on $N$ can be
explained by a similar dependence of $\alpha^{*}_{1}$ (appearing in the
denominator of the bound given in Prop. 2) on the number of users. This is
rather expected as the degree of freedom grows with $N$ and/or $K$, resulting
in increasing the users’ opportunity to deviate by taking advantage of the
multiuser diversity gain. To sum it up, what we remark here is that fairness
does not imply _a fortiori_ little incentive to deviate.

Figure 14: The ratio between individual utility without and with deflection
from FEAT as function of $K$ for different $N$.

##  VIII Conclusion

We have addressed the information rate maximization problem of Gaussian
sources by proposing a joint channel selection and power allocation scheme
based on the water-filling algorithm. Contrary to classical water filling
solutions in the literature, the way we have done this is by
eliminating/adding channels on which we could have transmitted in the case
without FEAT. In this aspect, FEAT is similar to mercury water-filling, but
the way it is done is not by changing the water-filling level (as it is done
with mercury water-filling), but by limiting the available carriers for each
user. While maximizing the information rate, FEAT also guarantees fairness
among users by trying to assign at least one good channel to every user in the
system, as long as there are enough channels for every user. It has been shown
that FEAT outperforms all other algorithms, especially in interference-limited
systems. With FEAT, we can notably ensure a near-optimal solution with low
computational complexity. In particular, FEAT does not require to implement a
SIC scheme at the receiver side, as the optimal scheme does.

##  IX appendix

Given a power allocation strategy profile $\textbf{p}\in\mathbb{R}^{N\times
K}$, for all achievable rates $\left\\{R_{1},R_{2},\ldots,R_{N}\right\\}$, the
following inequality holds for the fundamental limit on the sum information
transmission rate [2]:

$\displaystyle\sum_{n=1}^{N}R_{n}$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{\displaystyle\sum_{n=1}^{N}g_{n}^{k}p_{n}^{k}}{\sigma^{2}}\right)$
(17)

On the other hand, we have that

$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right)$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{1}^{k}p_{1}^{k}}{\sigma^{2}}\right)+\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{2}^{k}p_{2}^{k}}{\sigma^{2}+\displaystyle
g_{1}^{k}p_{1}^{k}}\right)+\cdots$
$\displaystyle+\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{N}^{k}p_{N}^{k}}{\sigma^{2}+\displaystyle\sum_{m=1}^{N-1}g_{m}^{k}p_{m}^{k}}\right),$

which gives after some simplifications

$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right)$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\log_{2}\left(1+\frac{\displaystyle\sum_{n=1}^{N}g_{n}^{k}p_{n}^{k}}{\sigma^{2}}\right).$
(18)

Now, combining Eq. (17) and Eq. (18), we obtain the following inequality on
the fundamental limit on the sum information transmission rate, namely

$\displaystyle\sum_{n=1}^{N}R_{n}$ $\displaystyle\leq$
$\displaystyle\sum_{n=1}^{N}\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right).$ (19)

Then, the following inequality holds on the fundamental limit on the
individual information transmission rate, namely

$u_{n}(\textbf{p})=\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m\neq
n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right)\leq\sum_{k=1}^{K}\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right),$ (20)

because for all
$(n,k)\in\left\\{1,2,\ldots,N\right\\}\times\left\\{1,2,\ldots,K\right\\}$

$\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m\neq
n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right)\leq\log_{2}\left(1+\frac{g_{n}^{k}p_{n}^{k}}{\sigma^{2}+\displaystyle\sum_{\begin{subarray}{c}m=1\\\
m<n\end{subarray}}^{N}g_{m}^{k}p_{m}^{k}}\right).$ (21)

## References

  * [1] R. G. Gallager, _Information Theory and Reliable Communication_. New York: Wiley, 1968.
  * [2] T. M. Cover and J. A. Thomas, _Elements of Information Theory_. United States: John Wiley & Sons, 1991.
  * [3] P. He, L. Zhao, S. Zhou, and Z. Niu, “Water-filling: A geometric approach and its application to solve generalized radio resource allocation problems,” _IEEE Transactions on Wireless Communications_ , vol. 12, no. 7, pp. 3637–3647, 2013.
  * [4] Q. Qi, A. Minturn, and Y. Yang, “An efficient water-filling algorithm for power allocation in OFDM-based cognitive radio systems,” in _2012 International Conference on Systems and Informatics (ICSAI2012)_ , 2012, pp. 2069–2073.
  * [5] X. Zhang, X. S. Shen, and L. Xie, “Joint Subcarrier and Power Allocation for Cooperative Communications in LTE-Advanced Networks,” _IEEE Transactions on Wireless Communications_ , vol. 13, no. 2, pp. 658–668, 2014.
  * [6] ——, “Uplink Achievable Rate and Power Allocation in Cooperative LTE-Advanced Networks,” _IEEE Transactions on Vehicular Technology_ , vol. 65, no. 4, pp. 2196–2207, 2016.
  * [7] M. S. Hasan, M. M. Rana, and A. Abdelhadi, “A Nash Equilibrium Based Effective Water-Filling Algorithm for MIMO Systems in Underground Tunnel: Performance Analysis,” in _IEEE 10th International Conference on Electronics Information and Emergency Communication (ICEIEC)_ , 2020.
  * [8] W. Cai, C. Chen, L. Bai, Y. Jin, and J. Choi, “Subcarrier and power allocation scheme for downlink OFDM-NOMA systems,” _IET Signal Processing_ , vol. 11, no. 1, pp. 51–58, 2017.
  * [9] M. Youssef, J. Farah, C. Nour, and C. Douillard, “Waterfilling-based resource allocation techniques in downlink Non-Orthogonal Multiple Access (NOMA) with Single-User MIMO,” in _IEEE Symposium on Computers and Communications (ISCC)_ , Los Alamitos, CA, USA, 2017.
  * [10] B. Gu, M. Dong, Z. Liu, C. Zhang, and Y. Tanaka, “Water-filling power allocation algorithm for joint utility optimization in femtocell networks,” in _IEEE Global Communications Conference (Globecom)_ , 2017.
  * [11] S. Fengfeng, R. Chen, H. Shen, J. Wang, and C. Zhao, “Energy-efficient power allocation for D2D communication underlaying cellular networks,” _Mobile Networks and Applications_ , Jan. 2021.
  * [12] D. P. Palomar and J. R. Fonollosa, “Practical algorithms for a family of waterfilling solutions,” _IEEE Transactions on Signal Processing_ , vol. 53, no. 2, pp. 686–695, 2005.
  * [13] N. Jindal, Wonjong Rhee, S. Vishwanath, S. A. Jafar, and A. Goldsmith, “Sum power iterative water-filling for multi-antenna gaussian broadcast channels,” _IEEE Transactions on Information Theory_ , vol. 51, no. 4, pp. 1570–1580, 2005.
  * [14] A. Lozano, A. M. Tulino, and S. Verdu, “Optimum power allocation for parallel gaussian channels with arbitrary input distributions,” _IEEE Transactions on Information Theory_ , vol. 52, no. 7, pp. 3033–3051, 2006.
  * [15] O. Perez-cruz, M. R. D. Rodrigues, and S. Verdu, “MIMO Gaussian channels with arbitrary inputs: Optimal precoding and power allocation,” _IEEE Trans. Inf. Theory_ , pp. 1070–1084, 2010.
  * [16] W. Cao, A. Dytso, M. Fau, G. Feng, and H. V. Poor, “Robust power allocation for parallel gaussian channels with approximately gaussian input distributions,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 6, pp. 3685–3699, 2020.
  * [17] G. He, S. Gault, M. Debbah, and E. Altman, “Iterative mercury/waterfilling for parallel multiple access channels,” in _IEEE International Conference on Communications_ , 2008.
  * [18] J. F. Nash, “Equilibrium points in n-person games,” in _Proceedings of the National Academy of Sciences of the United States of America_ , 1950.
  * [19] S. M. Perlaza, S. Lasaulce, and M. Debbah, “Equilibria of channel selection games in parallel multiple access channels,” _EURASIP Journal on Wireless Communications and Networking_ , vol. 15, 2013.
  * [20] P. Viswanath, D. Tse, and V. Anantharam, “Asymptotically optimal water-filling in vector multiple-access channels,” _IEEE Transactions on Information Theory_ , vol. 47, no. 1, pp. 241–267, Jan 2001.
  * [21] S. M. Perlaza, M. Debbah, S. Lasaulce, and H. Bogucka, “On the benefits of bandwidth limiting in decentralized vector multiple access channels,” in _Proc. 4th Intl. Conf. on Cognitive Radio Oriented Wireless Networks and Comm. (CROWNCOM)_ , May 2009.
  * [22] G. Debreu, “A social equilibrium existence theorem,” _Proceedings of the National Academy of Sciences_ , vol. 38, no. 10, pp. 886–893, 1952.
  * [23] T. Weiss and F. Jondral, “Spectrum pooling: an innovative strategy for the enhancement of spectrum efficiency,” _Communications Magazine, IEEE_ , vol. 42, no. 3, pp. 8–14, Mar 2004.
  * [24] M. Haddad, A. M. Hayar, and M. Debbah, “Spectral efficiency for spectrum pooling systems,” _IET Special Issue on Cognitive Spectrum Access_ , vol. 2, no. 6, pp. 733–741, July 2008.
  * [25] F. Meshkati, M. Chiang, H. V. Poor, and S. C. Schwartz, “A game-theoretic approach to energy-efficient power control in multicarrier CDMA systems,” _IEEE JSAC_ , vol. 24, no. 6, pp. 1115–1129, 2006.