# Multi-Objective Optimization for 3D Placement and Resource Allocation in
OFDMA-based Multi-UAV Networks

Asad Mahmood, Thang X. Vu, Shree Krishna Sharma, Symeon Chatzinotas, Björn
Ottersten
Interdisciplinary Centre for Security, Reliability and Trust (SnT), University
of Luxembourg
Email: {asad.mahmood, thang.vu, symeon.chatzinotas<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This work considers the orthogonal frequency division multiple access (OFDMA)
technology that enables multiple unmanned aerial vehicles (multi-UAV)
communication systems to provide on-demand services. The main aim of this work
is to derive the optimal allocation of radio resources, $3D$ placement of
UAVs, and user association matrices. To achieve the desired objectives, we
decoupled the original joint optimization problem into two sub-problems: i)
$3D$ placement and user association and ii) sum-rate maximization for optimal
radio resource allocation, which are solved iteratively. The proposed
iterative algorithm is shown via numerical results to achieve fast convergence
speed after less than 10 iterations. The benefits of the proposed design are
demonstrated via superior sum-rate performance compared to existing reference
designs. Moreover, the results declared that the optimal power and sub-carrier
allocation helped mitigate the co-cell interference that directly impacts the
system’s performance.

###### Index Terms:

5G, multi UAV communication, joint optimization, system channel capacity.

##  I Introduction

###  I-A Background and Related work

The $5$G and beyond communication systems aim to provide massive connectivity,
ultra-reliable low latency communication, and ensure the end-user quality of
service. In contrast, most of the earth’s remote areas still need to be
covered by the terrestrial base stations due to the sparse human activities in
these regions [1]. Moreover, the excessive demand for the users’ resources and
connectivity represents challenging tasks to meet the objectives mentioned
earlier [2, 3, 4]. In comparison, the UAV emerges as a practical solution
because of its flexible deployment and adaptive altitude. Furthermore, the
existing UAV cases will be more beneficial by integrating the UAVs with the
base station, also known as a flying base station (FBS), to provide services
to users located in remote areas.

Besides providing ubiquitous coverage, UAVs have several limitations,
including security, privacy, flight regulations, and limited battery life [5].
The hovering time and services provided by UAVs are primarily determined by
battery life. To overcome the limited battery capacity of the UAV, a highly
energy-efficient mechanism for maintaining users’ quality of service
requirements is required [6, 7]. Similarly, optimal UAV placement is critical
for ensuring a balanced trade-off between interference, shadowing, and path
loss when multiple UAVs are used. Additionally, recent research indicates that
elevating UAVs increases the probability of line-of-sight communication and
introduces additional path loss. [1, 8]. As a result of the aforementioned
challenges, UAVs must adapt their positions in response to changes in UE
density to provide communication services as needed.

Recent research has focused on optimizing UAV placement in 3D to maximize
coverage while minimizing transmit power[9, 10, 11, 12, 13, 14]. Furthermore,
it is possible to deploy multiple UAVs without interfering with each other
while minimizing transmit power by optimizing the users association matrix, as
described in [9]. This work’s primary goal is to optimize power and trajectory
to maximize minimum secrecy. To assess the impact of altitude on interference,
the authors of [10] used multiple UAVs with directional antennas; the results
show that adjusting the UAV’s altitude helps mitigate the interference. It is
also recommended that the distance between multiple UAVs be more significant
than a threshold to avoid co-channel interference [11]. To serve as many users
as possible, the authors of [12] propose a UAV placement algorithm that uses
the least transmission power. The authors of [13] proposed a method for
reducing energy consumption by optimizing unmanned aerial vehicle trajectory
and deployment.

Aside from massive communication and ultra-reliable low latency communication,
energy efficiency and resource efficiency are important performance metrics in
$5G$ and beyond communication systems. For effective utilization of resources,
the main aim of this work is to place the minimum number of UAVs that
guarantee quality-of-service for all UEs in coverage area. In a similar vein,
the problem of minimizing the total number of UAVs has been studied recently
[15, 16, 17]. However, most of these works have considered fixed flying
altitudes or UAVs as complementary parts of existing terrestrial communication
systems during potential congestion periods. A closely related work is given
in [14] in which the author considered the concept of simultaneous wireless
information and power transfer (SWIPT), in which a multiple (fixed) number of
UAVs are deployed by an iterative algorithm based on exhaustive search without
considering the maximum serving capacity of each UAV and co-cell interference.

###  I-B Contributions

In this work, we consider multi-UAV communication systems that use orthogonal
frequency division multiple access (OFDMA) to provide heterogeneous services
in areas where terrestrial base stations are unavailable due to natural
disasters or UE congestion [18]. We propose a novel objective that minimizes
the number of deployed UAVs while maximizing the system sum rate via optimal
radio resource allocation, user association matrix optimization, and efficient
$3D$ placement of UAVs. To overcome the difficulty, we decoupled the original
optimization problem into two sub-problems using block coordinate descent
(BCD). For path loss minimization, the $3D$ placement and user association
problems are solved using quadratic constraint quadratic programming (QCQP)
and branch and bound (BnB) techniques, respectively. The sum-rate maximization
problem is then solved using the successive convex approximation (SCA)
technique. The performance of the proposed algorithm is demonstrated
numerically, with rapid convergence occurring within ten iterations and
superior sum-rate performance compared to the baseline scheme.

The following sections summarize the rest of the paper: Section II summarizes
the proposed system model and problem statement. Section III presented an
algorithm for efficient $3D$ UAV deployment and resource allocation. Likewise,
Section IV contains the simulation results. The paper is finally concluded in
Section V.

##  II System Model and Problem Statement

This work considers the down-link UAV-assisted wireless communication system
that provides heterogeneous services to users in areas where terrestrial base
stations are unavailable due to natural disasters or UE congestion. The
considered system model comprises $M$ number of available UAVs and $N$ number
of users, represented by sets
$\mathcal{M}\\!\\!\\!=\\!\\!\\!\\{1,2,\cdots{\rm{M\\}}}$ and
$\mathcal{N}\\!\\!=\\!\\!\\{1,2,\cdots{\rm{N\\}}}$, respectively. In order to
improve the system’s energy efficiency, only $L\\!\leq\\!M$ UAVs will be
activated to serve the users such that $\mathcal{L}\\!\subset\\!\mathcal{M}$.
We consider $3D\\!$ coordinates, in which the location of $l$-th UAV and the
$n$-th UE are denoted by $x^{l},y^{l},h^{l}$ and $x_{n},y_{n},0$,
respectively. Both UAVs and UEs are equipped with single omnidirectional
antennas because of their uniform radiation in all directions[19]. The UAVs
are assisted by a central controller that provides information about UE’s
location. To avoid mutual interference between connected UEs, each UAV serves
a cluster of users using OFDMA. $Q_{l}\\!$ represents users associated with
the $l$-th UAV; each user is served by only one UAV.

In the considered system model, the frequency bandwidth is distributed among
$K$ sub-channels donated by set
$\mathcal{K}\\!\\!=\\!\\!\\!\left\\{{1,\cdots,K}\right\\}$. We define
$\textbf{A}=[a_{n}^{k,l}]_{N\times K\times L}$ as the sub-channel allocation
matrix, in which $a_{n}^{k,l}\\!\\!=\\!\\!1$ indicates that sub-channel $k$
allocated to user $n$ associated with UAV $l$, and $a_{n}^{k,l}\\!\\!=\\!\\!0$
otherwise. Additionally, we refer to $p_{n}^{k,l}$ as the transmit power
transmitted from the UAV $l$ to the user $n$ via sub-channel $k$. Given that
UAV $l$ consumes power on sub-channel $k$ only when user $n$ is assigned to
that sub-channel, expressed mathematically as follows:

$\small p_{n}^{k,l}\\!\leq\\!a_{n}^{k,l}P_{t}^{Max},\vspace{-2mm}$ (1)

Whereas $P_{t}^{Max}$ represents UAV’s maximum transmits power. The new
transmit power constraint (1) not only facilitates the rate function but also
guarantees no transmit power on sub-channel $k$ unless user $k$ is assigned to
it. To avoid cross-user interference, each sub-channel in a cluster is
assigned to only one user, which imposes the following constraint.

$\small\sum\limits_{n\in\mathcal{N}}{{\rm{a}}_{n}^{k,l}}\\!\leq\\!1,\forall
k\in\mathcal{K},l\in\mathcal{L}.\vspace{-2mm}$ (2)

To model the UAVs placement, we introduce a binary vector
$\vec{I}\\!\\!=\\!\\![I_{1},I_{2},I_{3}\cdots I_{M}]$, in which
$\\!I_{m}\\!\\!=\\!1$ means the $m$-th UAV is activated, and
$\\!I_{m}\\!\\!=\\!0$ otherwise. Similarly, the user association
$\textbf{J}\\!\\!=\\!\\![{J_{n}^{l}}]{{}_{N\\!\times L}}$ is a binary matrix,
in which each entity $\\!J_{n}^{l}$ represents the connection between $l$-th
UAV and $n$-th UE, i.e., $\\!J_{n}^{l}\\!\\!=\\!1$ if user $n$ is associated
with UAV $l$, and $\\!J_{n}^{l}\\!\\!=\\!0$ otherwise. Consequently, the
following constraint must be met as one sub-channel is only allocated to a
user if it is connected to the corresponding UAV:

$\small\sum\limits_{k\in{\cal
K}}{{\rm{a}}_{n}^{k,l}}\\!\leq\\!J_{n}^{l},\forall n\in{\cal N},l\in{\cal
L}.\vspace{-1.5mm}$ (3)

The quality wireless link between UAV-UE is measured in terms of the signal-
to-interference plus noise ratio (SINR), which is expressed as follows:

$\small\gamma{{}_{n}^{k,l}}\\!=\\!\frac{{p_{n}^{k,l}g_{n}^{k,l}}}{{\Phi_{n}^{k,l}+{\sigma^{2}}}}.\vspace{-1.5mm}$
(4)

In (4), $\sigma\\!$ is the Gaussian noise power, and $\Phi_{n}^{k,l}\\!$ is
the aggregated interference imposed by the UAVs on the $n$-th UE except the
$l$-th UAV, which is represented as $\Phi_{n}^{k,l}\\!=\\!\sum_{l\neq
l^{\prime}}\\!{\left({\sum_{n\neq
n^{\prime}}p_{n^{\prime}}^{k,l^{\prime}}}\right)}g_{n}^{k,l^{\prime}}$. The
UAV-UE channel gain $g_{n}^{k,l}$ is computed as
$g_{n}^{k,l}\\!\\!\\!=\\!\\!\\!\frac{\left|h_{n}^{k,l}\right|^{2}}{{PL}_{n}^{l}}$,
where $h_{n}^{k,l}\\!\sim\\!CN\\!\left(0,1\right)$ is the small-scale fading
and $PL_{n}^{l}$ is the path-loss. In this work, we consider the air-to-ground
(A2G) channel model that is composed of both line of sight (LoS) and non-line
of sight (NLoS) components. Mathematically the path loss is expressed as
follows [20]:

$\small{PL}_{n}^{l}\\!=\\!\\!K_{o}\left(d_{n}^{l}\right)^{\alpha}\left[PLos_{n}^{l}\xi_{LoS}\\!+\\!{\xi_{NLoS}}PNLos_{n}^{l}\right],\vspace{-1.5mm}$
(5)

where $K_{o}\\!\\!=\\!\\!{\left({\frac{{4\pi{f_{c}}}}{c}}\right)^{2}}$ and
$\xi_{LoS}$ and $\mu_{NLoS}$ are the attenuation factors for LoS and NLoS
link. Similarly, $f_{c}$, $\alpha$ and $c$ represent the carrier frequency,
path loss exponent and speed of light, respectively.
$PLos_{n}^{l}\\!\\!=\\!\\!\frac{1}{{b_{1}}\exp\left({-{b_{2}}(\theta_{n}^{l}-{b_{1}})}\right)}$
and $PNLos_{n}^{l}\\!\\!=\\!\\!1\\!-\\!PLos_{n}^{l}$ represent the probability
of the LoS and NLoS, respectively, where $b_{1}$ and $b_{2}$ are the constants
representing the environment condition, and $\theta_{n}^{l}$ is the angle of
elevation between the $l$-th UAV and the $n$-th UE. Thus, the achievable rate
of $n$-th UE connected to $l$-th UAV is represented as follows:

$\small{R_{n}^{l}}={B}{\sum}_{k\in\mathcal{K}}{\log_{2}}\left({1+\gamma{{}_{n}^{k,l}}}\right),\vspace{-2mm}$
(6)

where $\gamma_{n}^{k,l}$ is given in (4).

###  II-A Problem Formulation

Unlike previous works, which target only the sum-rate maximization, we also
optimize the system-wise energy usage. Therefore, this work aims to maximize
the ratio between the system sum rate and the number of active UAVs, which is
given as $\Upsilon\\!\\!=\\!\\!\frac{\sum_{n,l}R_{n}^{l}}{L}\\!$, where
$R_{n}^{l}\\!$ is calculated in (6) and $L\\!$ is the number of active UAVs.
We aim to maximize the objective function $\\!\\!\Upsilon\\!\\!$ by optimizing
the UAVs’ 3D placement, user association, power, and sub-carrier allocation.
Before going to the mathematical problem formulation, we introduce designing
variables. The 3D location of each UAV is denoted by
$\textbf{W}\\!\\!=\\!\\!\left[{{x^{l}},{y^{l}},{h^{l}}}\right]$; power
profile, user association matrix and UAVs placement vector, represented as
$\textbf{P}\\!\\!=\\!\\![{p_{n}^{k,l}}]{{}_{N\times\\!K\times L}}$, J and
$\vec{I}$, respectively; whereas sub-channel allocation matrix is represented
by A. Based on these compact variable notations, the joint optimization is
formulated as follows:

$\displaystyle\textbf{P1}:\;\;\;$
$\displaystyle\mathop{\max}\limits_{\textbf{W},\textbf{P},\textbf{J},\vec{I},\textbf{A}}\frac{\sum_{l\in\mathcal{L}}\sum_{n\in\mathcal{N}}R_{n}^{l}}{L},$
(7a) $\displaystyle\textbf{C1}:\;\;\;$ $\displaystyle{R_{n}^{l}\geq
J_{nl}R_{n}},\forall n\in\mathcal{N},l\in\mathcal{L},$ (7b)
$\displaystyle\textbf{C2}:\;\;\;$
$\displaystyle\sum\limits_{{l}\in\mathcal{L}}{J_{n}^{l}}\leq 1,,\forall
n\in\mathcal{N},$ (7c) $\displaystyle\textbf{C3}:\;\;\;$
$\displaystyle\sum\limits_{{n}\in\mathcal{N}}{{J_{n}^{l}}\leq
C^{l}_{Max}},\forall l\in\mathcal{L},$ (7d) $\displaystyle\textbf{C4}:\;\;\;$
$\displaystyle\sum\limits_{{n}\in\mathcal{N}}{{J_{n}^{l}}\geq
C^{l}_{Min}},\forall l\in\mathcal{L},$ (7e) $\displaystyle\textbf{C5}:\;\;\;$
$\displaystyle{p_{n}^{k,l}\leq a^{k,l}_{n}P_{t}^{Max}},\forall
n\in\mathcal{N},k\in\mathcal{K},l\in\mathcal{L},$ (7f)
$\displaystyle\textbf{C6}:\;\;\;$
$\displaystyle\sum\limits_{n\in\cal{N}}{\sum\limits_{k\in\mathcal{K}}{p_{n}^{k,l}\leq
P_{t}^{Max}}},\forall l\in\mathcal{L},$ (7g) $\displaystyle\textbf{C7}:\;\;\;$
$\displaystyle\sum\limits_{k\in{\cal K}}{{\rm{a}}_{n}^{k,l}}\leq
J_{n}^{l},\forall n\in{\cal N},l\in{\cal L},$ (7h)
$\displaystyle\textbf{C8}:\;\;\;$
$\displaystyle\sum\limits_{n\in\mathcal{N}}{{\rm{a}}_{n}^{k,l}}\leq 1,\forall
k\in\mathcal{K},l\in\mathcal{L},$ (7i) $\displaystyle\textbf{C9}:\;\;\;$
$\displaystyle\mathop{{\hbar_{(1\times N)}}{\bf{J}}{\mathchar
22\relax\mkern-10.0mu\lambda_{(L\times
1)}}}\limits_{\forall{\hbar_{n}},\forall{\mathchar
22\relax\mkern-10.0mu\lambda_{l}}=1}\geq\lambda N,$ (7j)
$\displaystyle\textbf{C10}:\;\;\;$
$\displaystyle\mathop{\left\|{{W^{l}}-{W^{l^{\prime}}}}\right\|}\geq{d_{{}_{o}}},{\forall
l^{\prime}\in\mathcal{L}},$ (7k) $\displaystyle\textbf{C11}:\;\;\;$
$\displaystyle\\{\mathop{\left.{{x_{l}}}\right|{x_{l}}\in\mathbb{R}}:x_{min}\leq{x_{l}}\leq{x_{\max}}\\},{\forall
l\in\mathcal{L}},$ (7l) $\displaystyle\textbf{C12}:\;\;\;$
$\displaystyle\\{\mathop{\left.{{y_{l}}}\right|{y_{l}}\in\mathbb{R}}:y_{\min}\leq{y_{l}}\leq{y_{\max}}\\},{\forall
l\in\mathcal{L}},$ (7m) $\displaystyle\textbf{C13}:\;\;\;$
$\displaystyle\\{\mathop{\left.{{h_{l}}}\right|{h_{l}}\in\mathbb{R}}:h_{\min}\leq{h_{l}}\leq{h_{\max}}\\},{\forall
l\in\mathcal{L}},$ (7n) $\displaystyle\textbf{C14}:\;\;\;$
$\displaystyle\\{\mathop{\left.{{{p_{n}^{k,l}}}}\right|{{p_{n}^{k,l}}}\in\mathbb{R}}:{p_{n}^{k,l}}\geq
0\\},{\forall{p_{n}^{k,l}}\in\textbf{P}},$ (7o)
$\displaystyle\textbf{C15}:\;\;\;$ $\displaystyle
I_{m},\\!J_{n}^{l},\\!a_{n}^{k,l}\\!\in\\{0,1\\},\\!\forall
I_{m},J_{n}^{l},a_{n}^{k,l}\in\vec{I},\textbf{J},\\!\textbf{A}.$ (7p)

The primary objective of this work is to deploy the minimum number of UAVs
possible while maximizing the average rate per UAV, subject to certain user
and system constraints detailed in C1 to C15. The quality of service
constraint C1 requires that each UE’s rate be above the minimum threshold. C2
prevents any UE from communicating with more than one UAV. Whereas C3 and C4
indicate the UAVs’ maximum and maximum serving capacity, respectively.
Similarly, the constraint C5 indicates the power allocation over the sub-
carrier $k$. C6 specifies that the sum of power associated with each UE should
be less than the maximum allowable power. Constrained C7 guarantees that the
spectrum allocation vector of $n$th user is zero if not associated with $l$th
UAV. Whereas C8 denotes that one sub-channel is allocated to only one user to
prevent interference. Similarly, C9 states that the minimum percentage of UEs
should be served. Similarly, C10 states that the distance between two UAVs
should be greater than or equal to the minimum allowable distance. Whereas ,
C11 to C15 represents the lower and upper bounds of decision variables

##  III Proposed Iterative Algorithm

The optimization problem in (7) is mixed-integer non-linear programming
(MINLP) and NP-hard due to the integer nature of user association matrix J,
UAVs placement vector $\\!\\!\vec{I}\\!\\!$ and sub-carrier A allocation
matrix. Furthermore, it is challenging to get optimal results as it involves
non-linear, non-convex objective functions and constraints. To find the
optimal best solution, we need to calculate the minimum number of UAVs needed
to provide communication services in a wireless communication network.
Additionally, in OFDMA enabled UAV communication system, the maximum serving
capacity of each UAV depends upon the maximum number of sub-carrier in a
network. Therefore the maximum number of UE that each UAV can support is equal
to the number of sub-carriers, i.e., $C^{l}_{max}\\!\\!=\\!\\!K$. Similarly,
the number of estimated UAVs is calculated as
$L\\!\\!=\\!\\!\left\lceil{\frac{\lambda N}{{{C^{\max}}}}}\right\rceil$, Where
$\lambda$ represents the percentage of users need to be served.

Furthermore, the sum rate in (6) depends upon the probability of line of sight
and co-cell interference, which is the function of $3D$ location of the UAVs
and transmission power, respectively. For the air-to-ground channel, UE’s
experience the line of sight communication with the probability represented by
$\\!PLos_{n}^{l}$. This $\\!PLos_{n}^{l}\\!$ mainly depends on the angle of
elevation $\\!\left(\theta_{n}^{l}\right)$; as
$\\!\left(\theta_{n}^{l}\right)\\!$ increases, $\\!PLos_{n}^{l}$ increase, on
the other hand, results in additional losses as the path loss between the UAVs
and their associated UEs decreases[21]. Thus, the desired objective can be
achieved by deploying the UAVs at the point such that the probability of line-
of-sight communication is greater than the threshold value $\phi$, i.e.,
$\\!\\!PLos_{n}^{l}\\!\left(\theta_{n}^{l}\right)\\!\geq\\!\phi$ and user is
only associated with that UAV located at a distance less than
$\\!{\scriptstyle\frac{{{h_{l}}}}{{\sin\left({P{{{}_{nl}^{LoS}}^{{}^{-1}}}\left(\phi\right)}\right)}}}$.
Therefore, we decouple the original optimization problem into three
subproblems, which are solved iteratively to find the final solutions.

The UEs association problem, given the location of UAVs and UEs, can be
formulated as follows:

$\displaystyle\textbf{P2a}:$
$\displaystyle\;\mathop{\min}\limits_{\bf{J}}\sum\limits_{n=1}^{N}{\sum\limits_{l=1}^{L}{{J_{nl}}{{\left\|{{{\bf{V}}_{n}}-{{\bf{W}}_{l}}}\right\|}^{2}}}}$
(8a) s.t. Equations 7c, 7d, 7e, 7j and 7p (8b)
$\displaystyle{J_{nl}}\left\|{{{\bf{V}}_{n}}\\!\\!-{{\bf{W}}_{l}}}\right\|\leq\frac{{{h_{l}}}}{{\sin\left({P{{{}_{nl}^{LoS}}^{{}^{-1}}}\left(\phi\right)}\right)}},\forall
n,l.$ (8c)

In equation (8),
${{\bf{V}}_{n}}\\!\triangleq\\!\left({{x_{n}},{y_{n}},0}\right)$ represents
the location of UEs. The optimization problem mentioned in (8) is linear
programming (LP) and convex and can be solved easily using the Branch and
Bound (BnB) algorithm.

Given the user association matrix J calculated in the user assignment step,
the location of the UAV is updated such that the distance between the UAV and
associated UEs is minimized mathematically can be expressed as follows:

$\displaystyle\textbf{P2b}:$
$\displaystyle\mathop{\min}\limits_{\bf{W}}\sum\limits_{n=1}^{{Q_{l}}}{\left[{{{\left({{x_{n}}\\!-\\!{x_{l}}}\right)}^{2}}+{{\left({{y_{n}}\\!-\\!{y_{l}}}\right)}^{2}}+h_{l}^{2}}\right],\forall
l}$ (9a) $\displaystyle\textbf{C1}:$
$\displaystyle{\left({{x_{n}}\\!\\!-\\!\\!{x_{l}}}\right)^{2}}\\!\\!+\\!\\!{\left({{y_{n}}-{y_{l}}}\right)^{2}}\\!\\!+h_{l}^{2}\xi\leq{\rm{0,}}\forall
n\in Q_{l}$ (9b) $\displaystyle\text{\lx@cref{creftypeplural~refnum}{C10},
\lx@cref{refnum}{C11}, \lx@cref{refnum}{C12} <EMAIL_ADDRESS>(9c)

In (9), the quantity $Q_{l}$ denotes the number of UEs associated with the
$l$-th UAV. Similarly, in (9b), the square of the distance between the UAV and
associated UEs is influenced by
${\scriptstyle\xi\\!=\\!\left({1-\frac{1}{{\sin\left({P_{nl}^{Lo{S^{-1}}}\left(\phi\right)}\right)}}}\right)}$,
ensuring that the UAV is positioned at a point where the angle elevation
calculated based on its geographical location meets
$\\!PLos_{n}^{l}\left(\theta_{n}^{l}\right)\\!\geq\\!\\!\phi$. The
optimization problem in equation (9) is convex and can be efficiently solved
using quadratic constraint quadratic programming (QCQP). To obtain the optimal
$3D$ location of UAVs and their associated user matrix, the BnB and QCQP-based
algorithms iteratively minimize the path loss between UAVs and their
associated users, as detailed in Algorithm 1.

1Initialization:  $PL_{old}$, error;

2 Execution: ;

3 while  _error $>$ $\epsilon$_ do

4 Given the random location of UAV’s Solve (8) Using Branch and Bound (BnB)
algorithm to get the User association matrix J.

5 [-1pt] Based upon the User Association matrix, update the location of UAV by
solving (9)

6 [-1pt] Compute Path Loss using using (5) to obtain $PL_{*}$

7 Compute error = $|PL_{*}$-$PL_{old}|$

8 [-1pt] Update $PL_{old}$=$PL_{old}-PL_{*}$

9 end while

Algorithm 1 Iterative Algorithm to solve (8) &(9)

After determining the user association and UAV locations, we aim to minimize
co-cell interference and maximize the sum rate required to meet the quality of
service requirements through optimal sub-carrier allocation and transmit
power. The third sub-problem is expressed mathematically as follows:

$\displaystyle\textbf{P3a}:\;\;$
$\displaystyle\mathop{\max}\limits_{\textbf{P,
A}}\sum\limits_{n=1}^{N}{\sum\limits_{l=1}^{L}R_{n}^{l}}$ (10a)
$\displaystyle\textbf{C1}:\;\;$ $\displaystyle{R_{n}^{l}\geq
J_{nl}R_{n}},\forall n\in\mathcal{N},l\in\mathcal{L}$ (10b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5}, \lx@cref{refnum}{C6},
\lx@cref{refnum}{C7}, \lx@cref{refnum}{C8}, \lx@cref{refnum}{C14}
<EMAIL_ADDRESS>(10c)

The resource allocation problem in (10) is non-convex and non-linear in nature
due to the rate function $R^{l}_{n}$ and constraint (10b). To tackle this
difficulty, an auxiliary variables $\eta_{n}^{l},s_{n}^{k,l},\forall n,l$ are
introduced and reformulate (10) as

$\displaystyle\textbf{P3b}:$
$\displaystyle\;\mathop{\max}\limits_{{\bf{A}},{\bf{P}},{\bf{\eta}},{\mathfrak{s}}}\sum\limits_{n\in
N}{\sum\limits_{l\in L}{\eta_{n}^{l}}}$ (11a)
$\displaystyle\begin{split}\textbf{C1}:&\;\sum\limits_{k\in\mathcal{K}}\log\left(\Phi_{n}^{k,l}+\delta^{2}+p_{n}^{k,l}g_{n}^{k,l}\right)\geq\frac{{\log(2)\eta_{n}^{l}}}{B}\\\\[-5.0pt]
&\qquad+\sum\limits_{k\in\mathcal{K}}s_{n}^{k,l},\forall
n\in\mathcal{N},l\in\mathcal{L}\end{split}$ (11b) $\displaystyle\textbf{C2}:$
$\displaystyle\;\Phi_{n}^{k,l}+\delta^{2}\leq e^{s_{n}^{k,l}},\forall
n\in\mathcal{N},l\in\mathcal{L},k\in\mathcal{K}$ (11c)
$\displaystyle\textbf{C3}:$ $\displaystyle\;\eta^{l}_{n}\geq
J^{l}_{n}R^{l}_{n},\forall n\in\mathcal{N},l\in\mathcal{L}$ (11d)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{C5}, \lx@cref{refnum}{C6},
\lx@cref{refnum}{C7}, \lx@cref{refnum}{C8}, \lx@cref{refnum}{C14}
and~\lx@cref{refnum}{C15}},$ (11e)

where (11d) guarantee the QoS requirement, and (11b) and (11c) equivalently
represent $R_{n}^{l}\geq\eta_{n}^{l}$. Solving (11) is still challenging due
to the non-convex constraint (11c). Fortunately, it has a form of different-
of-convex (DC) constraint; hence we can employ the first-order approximation
to convexify the right-hand-side of (11c), which can be reformulated as
follows:

$\displaystyle\textbf{P3c}:$
$\displaystyle\;\mathop{\max}\limits_{{\bf{A}},{\bf{P}},{\bf{\eta}},{\mathfrak{s}}}\sum\limits_{n\in
N}{\sum\limits_{l\in L}{\eta_{n}^{l}}}$ (12a) $\displaystyle\textbf{C1}:$
$\displaystyle\;{\Phi_{n}^{k,l}+\delta^{2}\leq
e^{{s_{o}}_{n}^{k,l}}\left(s_{n}^{k,l}-{s_{o}}_{n}^{k,l}+1\right)},$
$\displaystyle\qquad\qquad\qquad\qquad\forall
n\in\mathcal{N},k\in\mathcal{K},l\in\mathcal{L}$ (12b)
$\displaystyle\text{\lx@cref{creftypeplural~refnum}{T2C1},
\lx@cref{refnum}{C3T2}, \lx@cref{refnum}{C5}, \lx@cref{refnum}{C6},
\lx@cref{refnum}{C7}, \lx@cref{refnum}{C8}, \lx@cref{refnum}{C14}
and~\lx@cref{refnum}{C15}},$ (12c)

Given a feasible point ${s_{o}}_{n}^{k,l}$ for constraint (11c), the objective
function being linear and all constraints being convex, problem (III) is a
convex optimization problem. Therefore, it can be efficiently solved using
standard methods such as the interior-point method. However, the solution of
(III) is dependent on the feasible point ${s_{o}}$. To tackle this, we propose
an iterative algorithm (Algorithm 2), which involves a sequence of convex
optimizations to approximate the best solution for problem (11). By
iteratively updating the feasible point, our algorithm effectively converges
to the optimal solution of the problem.

1Initialization:  $s_{o}$, $\eta_{old}$, error;

2 Execution: ;

3 while  _error $>$ $\epsilon$_ do

4 Given the location of UAVs and user association matrix form Algorithm 1,
Solve (III) to get the optimal value of $\eta_{*}$,$a_{*}$, $p_{*}$,$s_{*}$

5 Compute error = $|\eta_{*}$-$\eta_{old}|$

6 Update $\eta_{old}$=$\eta_{*}$,$s_{o}$=$s_{*}$

7 end while

Algorithm 2 Iterative Algorithm to solve (11)

##  IV Results and Discussion

This section demonstrates the effectiveness of the proposed joint algorithm
via extensive Monte-Carlo simulations. In our simulations, we assume the $N$
number of users distributed randomly over an $\\!1\\!\\!\\!$ km
$\\!\\!\times\\!\\!\\!$ $1\\!\\!\\!$ km area. Furthermore, $L$ number of UAVs
are deployed to provide communication services using the OFDMA protocol.
Whereas other simulation parameters are as follows: $f_{c}\\!\\!=\\!\\!\\!1$
GHz, $\alpha\\!\\!=\\!\\!4$, $K\\!\\!=\\!\\!8$ and
$\delta^{2}\\!\\!=\\!\\!-10$ dBm. Moreover, the effectiveness of the proposed
scheme is illustrated by considering the users’ path loss and sum rate as a
performance matrix for Algorithms 1 and 2, respectively.

Figure 1: Convergence analysis

Furthermore, the convergence of the proposed algorithms is compared with
different stimulation parameters, as shown in Fig. 1. Fig.1a represents the
convergence graph of Algorithm 1 by considering path loss as a performance
matrix. Results reveal that as the number of iterations increases, the path
loss of the network also decreases. This trend is because UAVs update their
locations and user association matrix incrementally in the number of
iterations. As a result, the distance between UAVs and associated users
decreases; hence path loss decreases. Similarly, based on the UAV’s locations
and user association matrix, we solve the sum rate maximization problem using
Algorithm 2. Results in Fig. 1b demonstrate the efficiency of the proposed
iterative algorithm.

(a) Path Loss vs Number of users

(b) Sum Rate vs Number of users

Figure 2: Comparison of Proposed scheme with some baseline schemes

After validating the convergence behaviour of Algorithms 1 and 2, the
performance of the proposed solution is exhibited by considering sum rate
(Mbps) as the performance metric. The sum rate of the UEs mainly depends on
the path loss, which is the function of $3D$ coordinates of the UAV and user
association matrix. Accordingly, the optimal deployment of UAVs and optimal
allocation of users results in the minimization of the path loss;
consequently, the sum rate of the user increases. Besides, the optimal
deployment of UAVs will result in the minimization of transmission power.
Therefore, to verify the effectiveness of the proposed scheme, we compare the
proposed design with baseline schemes named: random deployment of UAV with
optimal allocation of users and optimal deployment of UAV with random
allocation of users , as shown in Fig. 2. Fig. 2(a) represents the performance
analysis of the system by considering path loss as a performance metric across
the number of users. It is shown that the proposed scheme achieves the minimum
path loss compared to random deployement and random association solutions. As
a result, the transmission power of the UAVs decreases, which leads to
minimizing co-cell interference or helps to increase the sum rate of users.
Whereas, based on the optimal location of UAV and user association matrix, the
performance is further evaluated by solving optimization problem (III) using
Algorithm 2. Furthermore, the results of the proposed scheme is compared with
equal/random power allocation and random carrier allocation scheme. Fig. 2(b)
reveals that optimal power allocation efficiently mitigates co-cell
interference, resulting in a higher sum rate.

(a) Sum Rate vs Number of Users

(b) Path Loss vs Number of Users

Figure 3: Comparison of Proposed scheme with the probability of line of sight

In Fig. 3, we evaluate the impact of the probability of line of sight between
the UAVs and their associated users on the system performance. It is shown in
Fig. 3(a) that increasing the PLoS will result in a higher system sum rate.
This is because as the PLoS increases from $55\%$ to $95\%$, path loss between
the UAVs and associated users decreases significantly, as shown in Fig. 3(b),
resulting in the higher system sum rate.

##  V Conclusion

In this work, we have considered that the ODFMA enables multiple UAV
communication systems to provide communication services to users in remote
areas. We proposed a collaborative framework for determining the optimal UAV
deployment to minimize the UAV’s transmission power while still meeting the
users’ QoS requirements. Path loss and user sum rate are performance metrics
used to assess the proposed system’s performance. The results revealed that
optimal deployment and user association minimize path loss, which directly
impacts the sum rate of users. Additionally, the network’s performance is
evaluated across multiple PLoS. The results demonstrate that by increasing the
PLoS, the path loss decreases significantly, thereby increasing the user’s sum
rate.

##  VI Acknowledgement

This work was supported by the Luxembourg National Research Fund via project
5G-Sky, ref. FNR/C19/IS/13713801/5G-Sky, and project RUTINE,
ref.FNR/C22/IS/17220888/RUTINE.

## References

  * [1] V. V. Chetlur Ravi _et al._ , “Downlink coverage probability in a finite network of unmanned aerial vehicle (UAV) base stations,” in _2016 IEEE 17th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_ , 2016, pp. 1–5.
  * [2] J. G. Andrews _et al._ , “What will 5G be?” _IEEE Journal on Selected Areas in Comm_ , vol. 32, no. 6, pp. 1065–1082, 2014.
  * [3] A. Mahmood _et al._ , “Partial offloading in energy harvested mobile edge computing: A direct search approach,” _IEEE Access_ , vol. 8, pp. 36 757–36 763, 2020.
  * [4] A. Mahmood _et al._ , “Optimal resource allocation and task segmentation in iot enabled mobile edge cloud,” _IEEE Tran. on Vehicular Technology_ , vol. 70, no. 12, pp. 13 294–13 303, 2021.
  * [5] M. Mozaffari _et al._ , “A tutorial on UAVs for wireless networks: Applications, challenges, and open problems,” _IEEE Communications Surveys Tutorials_ , vol. 21, no. 3, pp. 2334–2360, 2019.
  * [6] Y. Zeng _et al._ , “Energy-efficient UAV communication with trajectory optimization,” _IEEE Transactions on Wireless Communications_ , vol. 16, no. 6, pp. 3747–3760, 2017.
  * [7] M. Mozaffari _et al._ , “Mobile unmanned aerial vehicles (UAVs) for energy-efficient internet of things communications,” _IEEE Tran. on Wireless Comm._ , vol. 16, no. 11, pp. 7574–7589, 2017.
  * [8] M. Mozaffari _et al._ , “Drone small cells in the clouds: Design, deployment and performance analysis,” in _2015 IEEE Global Communications Conference (GLOBECOM)_ , 2015, pp. 1–6.
  * [9] S. C. Noh _et al._ , “Energy-efficient deployment of multiple UAVs using ellipse clustering to establish base stations,” _IEEE Wireless Communications Letters_ , vol. 9, no. 8, pp. 1155–1159, 2020.
  * [10] M. Mozaffari _et al._ , “Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage,” _IEEE Communications Letters_ , vol. 20, no. 8, pp. 1647–1650, 2016.
  * [11] A. A. Khuwaja _et al._ , “Optimum deployment of multiple UAVs for coverage area maximization in the presence of co-channel interference,” _IEEE Access_ , vol. 7, pp. 85 203–85 212, 2019.
  * [12] M. Alzenad _et al._ , “3-D placement of an unmanned aerial vehicle base station (UAV-bs) for energy-efficient maximal coverage,” _IEEE Wireless Comm. Letters_ , vol. 6, pp. 434–437, 2017.
  * [13] M. Mozaffari _et al._ , “Mobile internet of things: Can UAVs provide an energy-efficient mobile architecture?” in _2016 IEEE Global Communications Conference (GLOBECOM)_ , 2016, pp. 1–6.
  * [14] F. Huang _et al._ , “Multiple-UAV-assisted swipt in internet of things: User association and power allocation,” _IEEE Access_ , vol. 7, pp. 124 244–124 255, 2019.
  * [15] A. Ahmed _et al._ , “Joint optimization of sensors association and UAVs placement in iot applications with practical network constraints,” _IEEE Access_ , vol. 9, pp. 7674–7689, 2021.
  * [16] E. Kalantari _et al._ , “On the number and 3D placement of drone base stations in wireless cellular networks,” in _2016 IEEE 84th Vehicular Technology Conference (VTC-Fall)_ , 2016, pp. 1–6.
  * [17] J. Lyu _et al._ , “Placement optimization of UAV-mounted mobile base stations,” _IEEE Comm. Letters_ , vol. 21, pp. 604–607, 2017.
  * [18] X. Zhong _et al._ , “Deep q-network based dynamic movement strategy in a UAV-assisted network,” in _2020 IEEE 92nd Vehicular Technology Conference (VTC2020-Fall)_ , 2020, pp. 1–6.
  * [19] C.-m. Cheng _et al._ , “Performance measurement of 802.11a wireless links from uav to ground nodes with various antenna orientations,” in _Proceedings of 15th International Conference on Computer Communications and Networks_ , 2006, pp. 303–308.
  * [20] X. Liu _et al._ , “Trajectory design and power control for multi-UAV assisted wireless networks: A machine learning approach,” _IEEE Tran. on Vehicular Technology_ , vol. 68, pp. 7957–7969, 2019.
  * [21] A. Al-Hourani _et al._ , “Modeling air-to-ground path loss for low altitude platforms in urban environments,” in _2014 IEEE Global Communications Conference_ , 2014, pp. 2898–2904.


11institutetext: University of Amsterdam, Amsterdam, Netherlands
22institutetext: Discovery Lab, Elsevier, Amsterdam, Netherlands
22email<EMAIL_ADDRESS>22email:
<EMAIL_ADDRESS>
# Potential Factors Leading to Popularity Unfairness in Recommender Systems: A
User-Centered Analysis††thanks: BNAIC/BeNeLearn Joint International Scientific
Conferences on AI and Machine Learning, 2023

Masoud Mansoury 1122 0000-0002-9938-0212 Finn Duijvestijn 11 Imane Mourabet 11

###### Abstract

Popularity bias is a well-known issue in recommender systems where few popular
items are over-represented in the input data, while majority of other less
popular items are under-represented. This disparate representation often leads
to bias in exposure given to the items in the recommendation results.
Extensive research examined this bias from item perspective and attempted to
mitigate it by enhancing the recommendation of less popular items. However, a
recent research has revealed the impact of this bias on users. Users with
different degree of tolerance toward popular items are not fairly served by
the recommendation system: users interested in less popular items receive more
popular items in their recommendations, while users interested in popular
items are recommended what they want. This is mainly due to the popularity
bias that popular items are over-recommended. In this paper, we aim at
investigating the factors leading to this user-side unfairness of popularity
bias in recommender systems. In particular, we investigate two factors: 1) the
relationship between this unfairness and users’ interest toward items’
categories (e.g., movie genres), 2) the relationship between this unfairness
and the diversity of the popularity group in users’ profile (the degree to
which the user is interested in items with different degree of popularity).
Experiments on a movie recommendation dataset using multiple recommendation
algorithms show that these two factors are significantly correlated with the
degree of popularity unfairness in the recommendation results.

###### Keywords:

Recommender Systems Popularity bias Unfairness.

##  1 Introduction

It is well-known that recommender systems suffer from popularity bias: a few
popular items are over-represented in the rating data, while majority of other
less items are under-represented [2, 7]. Figure 1 shows the popularity
distribution of the items in MovieLens dataset. As shown, a few items with
high rating frequency dominate the entire rating history. For instance, 44
most popular items (around 1%) make up more than 10% of the interactions.

This bias, if not mitigated, leads to exposure bias [13, 12] where popular
items are over-recommended, while unpopular items are under-recommended in the
recommendation results. This unfairness in the representation of items in the
recommendation lists also leads to unfairness against suppliers who provided
those items in the system [1, 25, 15]. Also, due to the feedback loop
phenomena in which users profiles get updated over time via potentially biased
recommendations, popularity bias can be amplified over time [14, 23, 18].
Mansoury et al. in [14] showed that in long run, as users interact with the
system, amplification of popularity bias not only intensifies the unfairness,
but also degrades the performance of the recommendations.

Most existing works study the popularity bias from the aforementioned item
perspective [19, 27, 24]. Various algorithms are developed to mitigate this
bias by promoting less popular items, known as long-tail, in the
recommendation results to compensate for their under-recommendation and
increase their visibility [6, 26, 28]. For example, Zhu et al. in [28]
proposed the idea of popularity compensation as a post-processing approach
that adjusts the predicted scores for items according to their popularity:
increasing the score for less popular items to promote them in the
recommendation list; Abdollahpouri et al. in [2] proposed an in-processing
approach that mitigates the popularity bias by incorporating a regularization
term into the objective function. While these algorithms effectively mitigate
item-side popularity bias, they ignore the user-centered impact of popularity
bias.

Figure 1: Distribution of item popularity on MovieLens dataset. Items are
sorted based on the popularity from the most (left) to the least (right):
lower item rank has higher popularity. Head represents 20% of most popular
items, Tail represents 20% of least popular items, and Mid represents the rest
of 60% items.

Recent research has shown that recommendation models fail to properly follow
the users’ interest toward popular items [4, 5]. Abdollahpouri et al. in [4]
demonstrated that popularity bias can lead to unfairness among users. They
showed that users differ in their interest toward popular items: some users
have high interest to popular items (blockbuster-focused), while some users
have high interest to less popular items (niche-focused). Due to the
popularity bias in input data and over-recommendation of these items in the
recommendation results, these user groups are unfairly treated. This means
that the impact of popularity bias is not equal across users belonging to
different groups. Niche-focused users, while are interested in less popular
items, receive popular items in their recommendation list, leading to a larger
impact on these users.

The same patterns were found later by Kowald et al. [10] on the music domain
where users with a lesser interest in mainstream songs were impacted more
severely by the popularity bias. These findings showed that popularity bias
impacts different users differently and hence it is important to take users
into account when mitigating this bias. To address this issue, abdollahpouri
et al. in [5] proposed the idea of popularity calibration, a post-processing
approach, that generates the recommendations to be approximately matched or
calibrated with the interest of users toward popularity spectrum in their
profile.

In this paper, we base our analysis on findings in [4, 5] and aim at
investigating the potential factors that lead to user-centered unfairness of
popularity bias. We in particular investigate two factors: 1) the impact of
genre popularity on this popularity unfairness, 2) the impact of popularity
diversity, the diversity of users’ profile in terms of their interest to
various item groups (e.g., popular and unpopular), on the degree of this user-
centered popularity unfairness. Experiments on a real-world dataset show that
our identified factors are highly correlated with the degree of unfairness in
recommendation results, suggesting ideas for future research to alleviate this
unfairness against users.

##  2 The unfairness of popularity bias

Throughout the paper, we use MovieLens 1M dataset [8] for our analysis. In
this dataset, 6,040 users provided 1,209,000 ratings on 3,706 items (movies).
Each item is associated with one or more genres and there are in total 18
different genres in the dataset. Figure 1 shows the popularity distribution of
MovieLens dataset. Vertical axis shows the popularity of the items and
horizontal axis shows the items sorted by their popularity value in descending
order. It is evident that the distribution is long-tailed and the data heavily
suffers popularity bias.

In this long-tail distribution, we define popular items, also referred to as
Head items (H), as the top 20% of most popular items (items frequently
interacted in the rating data). The rest of the less popular items are often
referred to as long-tail items and can be further divided into: Tail items (T)
as the top 20% of the least popular items (items rarely interacted in the
rating data), and Mid items (M) are the ones in between that includes 60% of
the rest of the items.

Following the findings in [4], popularity bias in rating data leads to
discrimination against users: users interested to popular items are much
better served by the recommender systems than the ones interested in less
popular items. In other words, users interested in less popular items, while
expected to get unpopular items in their recommendation lists, receive more
popular items as the recommendation. In the following section, we briefly
review this issue.

###  2.1 User grouping in terms of propensity to item popularity

We group users based on their interest toward popular items. Users can be
mostly interested in either popular items, unpopular items, or items in the
middle of popularity spectrum. Hence, we define three groups of users:

  * •

Blockbuster-focused users: Users with interest to popular items.

  * •

Diverse taste users: Users with diverse interest toward both popular and less
popular items.

  * •

Niche-focused users: Users with interest to less popular items.

Given users’ profile with items they interacted with, we first derive the
ratio of H, M, and T items in their profile. For example, if a user interacted
with 7 items in H, 2 items in M, and 1 item in T, then the ratios for H, M,
and T in her profile would be 0.7, 0.2, 0.1, respectively. Then, we follow
this process for grouping the users: 1) extract 20% of the users with the
highest ratio of T items in their profile to form Niche group (i.e., sort the
users based on the ratio of T items in descending order and return top 20%),
2) extract 20% of the users with the highest ratio of H in their profile to
form Blockbuster group (i.e., sort the users based on the ratio of H items in
descending order and return top 20%), 3) and finally, extract users who are
neither in niche-focused nor in blockbuster-focused groups to form Diverse
group.

###  2.2 Evaluation metrics

For measuring the degree of popularity unfairness in the recommendation
results, we use metrics introduced in [3, 4, 5].

Popularity Lift (PL): This is a measure of popularity amplification of
recommendation list delivered to the user with respect to the popularity of
her profile. We denote $APP_{u}$ as the Average Profile Popularity of user
$u$’s profile and $ARP_{u}$ as the Average Recommendation Popularity of $u$’s
recommendations, both computed as

$APP_{u}=\frac{\sum_{i\in\mathcal{R}_{u}}{pop(i)}}{|\mathcal{R}_{u}|}\;,\;\;\;\;\;\;\;\;\;ARP_{u}=\frac{\sum_{i\in\mathcal{L}_{u}}{pop(i)}}{|\mathcal{L}_{u}|}$

where $pop(i)$ returns the popularity of item $i$ as fraction of interactions
on $i$, $\mathcal{R}_{u}$ is the items that $u$ interacted, and
$\mathcal{L}_{u}$ is the items recommended to $u$. Thus, PL of user $u$ is
computed as

$PL_{u}=\frac{ARP_{u}-APP_{u}}{APP_{u}}$ (1)

Positive value for PL signifies that the recommendation list of a user is on
average more popular than his profile, while negative value indicates that the
user’s profile is on average more popular than her recommendation list.
However, $PL_{u}=0$ means no popularity amplification or degradation which is
more desired. We further define the popularity lift for a group
$G\in\\{\text{Blockbuster},\text{Diverse},\text{Niche}\\}$ as
$PL_{G}=\frac{ARP_{G}-APP_{G}}{APP_{G}}$ where $APP_{G}=\frac{\sum_{u\in
G}{APP_{u}}}{|G|}$ and $ARP_{G}=\frac{\sum_{u\in G}{ARP_{u}}}{|G|}$.

User Popularity Deviation (UPD): This is a measure of popularity
miscalibration [5] in the recommendation results. In other words, given
$P_{u}$ and $Q_{u}$ as the ratio of each item group in $u$’s profile and
recommendation list, respectively, $UPD$ calculates the distance between
$P_{u}$ and $Q_{u}$, indicative of how well $Q_{u}$ is calibrated with respect
to $P_{u}$. For example, if a user’s profile represents the ratios of $\langle
0.7,0.2,0.1\rangle$ for $\langle H,M,T\rangle$, a recommendation list is
considered to be perfectly calibrated (i.e., $UPD=0$) if it also consists of
the same ratios. Given $C=\\{H,M,T\\}$, we calculate the propensity of each
user $u$ towards each item group $c\in C$ in her profile as:

$p_{u}(c)=\frac{\sum_{i\in\mathcal{R}_{u}}{\text{1}{}(i\in
c)}}{\sum_{c^{\prime}\in C}{\sum_{i\in\mathcal{R}_{u}}{\text{1}{}(i\in
c^{\prime})}}}$ (2)

and the ratio of each item group $c\in C$ in her recommendation as:

$q_{u}(c)=\frac{\sum_{i\in\mathcal{L}_{u}}{\text{1}{}(i\in
c)}}{\sum_{c^{\prime}\in C}{\sum_{i\in\mathcal{L}_{u}}{\text{1}{}i\in
c^{\prime}}}}$ (3)

Thus, we define $P_{u}=\\{p_{u}(H),p_{u}(M),p_{u}(T)\\}$ and
$Q_{u}=\\{q_{u}(H),\allowbreak q_{u}(M),q_{u}(T)\\}$. Now, we calculate
$UPD_{u}$ as:

$UPD_{u}=\mathcal{J}(P_{u},Q_{u})$ (4)

where $\mathcal{J}(p_{u},q_{u})$ is Jensen–Shannon divergence [11] between
$p_{u}$ and $q_{u}$ which measures the statistical distance between two
probability. Similar to $PL$, we calculate $UPD_{G}$ for a group $G$ (e.g.,
Niche) as the average $UPD$ of all users belonging to $G$.

###  2.3 Experimental setup

For experiments, we split the users’ profile in MovieLens dataset into 80% as
training set and 20% as test set. The training set is used to build the
recommendation model and generating the recommendations for each user. The
test set is used for evaluating the performance of the recommendations. We
perform the experiments using the following recommendation algorithms:
Bayesian Personalized Ranking (BPR) [20], Biased Matrix Factorization
(BiasedMF) [9], User-based Neighborhood Model (UserKNN) [21], and Item-based
Neighborhood Model (ItemKNN) [22]. We also use two non-personalized
algorithms: most popular item recommendation (Popular) and random item
recommendation (Random). We tune each algorithm by performing a grid-search
over the hyperparameter space and reporting the best-performing results in
terms of precision, recall, and ranking quality (nDCG) of the recommendations.
In recommendation generation, a recommendation list of size 10 is generated
for each user. We use Librec-Auto [17] for running our experiments.

Table 1: Performance of recommendation algorithms on MovieLens dataset in terms of accuracy metrics. algorithms | $precision@10$ | $recall@10$ | $nDCG@10$
---|---|---|---
BPR | 0.183 | 0.072 | 0.184
BiasedMF | 0.108 | 0.039 | 0.111
ItemKNN | 0.315 | 0.130 | 0.310
UserKNN | 0.243 | 0.095 | 0.243
Popular | 0.186 | 0.068 | 0.185
Random | 0.009 | 0.003 | 0.007
Figure 2: $PL$ of different recommendation algorithms across various user
groups on MovieLens dataset. Figure 3: $UPD$ of different recommendation
algorithms across various user groups on MovieLens dataset.

###  2.4 Experimental results

Table 1 presents the performance of the recommendation models based on
accuracy metrics. These results suggest that the models are accurate
(reliable) enough to be used for the rest of analysis in this paper.

Figure 2 shows the PL of the recommendation models for each group of users.
Note that the goal here is not to compare the recommendation models, but
instead to compare the performance of each recommendation model across
different groups of users. As shown, all recommendation models (except Random)
consistently reveal this pattern: $PL^{Niche}\succ PL^{Diverse}\succ
PL^{Blockbuster}$. This indicates that users in Niche-focused group are
getting worst recommendation in terms of their interest toward popular items,
and users in Blockbuster-focused group are served the best (lowest $PL$).

Figure 3 shows the performance of recommendation models in terms of $UPD$
across different groups of users. Similarly, $UPD$ of Niche-focused group is
the highest, while it is the lowest for Blockbuster-focused group (except for
Popular). This shows that the recommendation models do not consistently follow
the popularity interest of different users, indicative of the user-side
unfairness.

##  3 Profile Inconsistency: propensity for genre popularity vs. item
popularity

Figure 4: Distribution of genre popularity on MovieLens dataset.

###  3.1 Genre popularity

Figure 4 shows the distribution of genre popularity in MovieLens dataset.
Since movies are assigned multiple genres, we equally distribute the
interaction on a movie to its genres. For example, if a movie is assigned
Action and Drama genres, for computing the genre popularity, we count the
interaction on this movie for its genres as 0.5 for Action and 0.5 for Drama.
Analogous to the distribution of item popularity, the distribution of genre
popularity is long-tailed, meaning that a few genres (Comedy and Drama) make
up more than 40% of the interactions in the rating data.

We perform the same process described in section 2 for grouping the genres and
the users in terms of genre popularity. For grouping the genres, we define the
most popular genres as $Head^{Genre}$, the least popular genres as
$Tail^{Genre}$, and the rest of the genres as $Mid^{Genre}$. These genre
groups are shown in Figure 4. For grouping the users, we follow the process
described in section 2.1. We first extract 20% of users with the highest
interest to genres in $Tail^{Genre}$ to form $\textbf{Niche}^{Genre}$. Then,
among the rest of the users, we extract 20% of them with highest interest to
$Head^{Genre}$ to create $\textbf{Blockbuster}^{Genre}$. Finally, we form
group $\textbf{Diverse}^{Genre}$ with the rest of the users. To distinguish
item and genre grouping in this section, we refer to item grouping as
$Head^{Item}$, $Mid^{Item}$, and $Tail^{Item}$. We also refer to item-based
user groups (section 2.1) as $\textbf{Blockbuster}^{Item}$,
$\textbf{Diverse}^{Item}$, and $\textbf{Niche}^{Item}$.

Figure 5: The relationship between the average item popularity and the average
genre popularity of users’ profile. Colors show user groups based on item
popularity (section 2.1).

###  3.2 The relationship between the propensity to item popularity and genre
popularity

Figure 5 shows the relationship between the average item popularity and
average genre popularity of each user’s profile. Each point in the plot
represents a user, x-axis represents its average item popularity, and y-axis
represents its average genre popularity. As shown, there is no correlation
between users’ interest toward item popularity and genre popularity. This
indicates that in terms of item popularity, a user might be interested in
popular items, while in terms of genre popularity, she might be interested in
unpopular genres. Therefore, this finding gives us clue for further
investigation on utilizing genre information to alleviate the unfairness
against Niche-focused users.

###  3.3 The impact of genre popularity on disparate treatment

Given $\textbf{Blockbuster}^{Genre}$, $\textbf{Diverse}^{Genre}$, and
$\textbf{Niche}^{Genre}$ as user groups based on users interest toward genre
popularity (described in section 3.1), the goal in this section is to
reproduce the results in section 2.4 for these user groups. Figure 6 shows the
$PL$ of recommendation models for the genre-based users’ groups. Again, the
aim is not to compare the performance of recommendation models, but instead to
compare the behavior of a recommendation model across different groups of
users.

Figure 6: $PL$ of different recommendation algorithms across various genre-
based user groups on MovieLens dataset. Figure 7: $UPD$ of different
recommendation algorithms across various genre-based user groups on MovieLens
dataset.

Unlike the results obtained for item-based user groups in Figure 2, Figure 6
shows no unfairness among different groups of users. This means that niche-
focused users are equally served as blockbuster-focused users by different
recommendation models. The same pattern can also be observed in terms of $UPD$
in Figure 7.

###  3.4 Profile inconsistency

Given the finding in section 3.3, we are interested in investigating how much
the user groups created based on item popularity (section 2.1) match those
based on genre popularity (section 3.1). We define the percentage of overlap
between group $A$ and $B$ as $A\wedge B=\frac{|A\cap B|}{|A|}\times 100$ where
$A\cap B$ is the intersection of $A$ and $B$.

Figure 8 shows the percentage of overlap between item-based and genre-based
user groups. First, it shows that the main overlap happens with
$\textbf{Diverse}^{Genre}$ group which can be expected as it is the group
close to both Niche and Blockbuster. Comparing $\textbf{Niche}^{Item}$ with
genre-based users’ groups, only around 23% of users in $\textbf{Niche}^{Item}$
are also in $\textbf{Niche}^{Genre}$, but surprisingly around 25% of users in
$\textbf{Niche}^{Item}$ are in $\textbf{Blockbuster}^{Genre}$. Similarly,
comparing $\textbf{Blockbuster}^{Item}$ with genre-based user groups, it shows
that around 17% and 14% of users in $\textbf{Blockbuster}^{Item}$ are in
$\textbf{Blockbuster}^{Genre}$ and $\textbf{Niche}^{Genre}$, respectively.

Figure 8: Percentage of overlapped users in item-based and genre-based user
groups.

With observations from Figure 8, we define profile inconsistency as the degree
to which the item popularity of a user’s profile does not match its genre
popularity. Thus, we first define a binary function $inconsistent(i)$ that
returns 1 if $i$’s group is inconsistent with its genres’ groups. For example,
for $i$ in $Tail^{Item}$, we say $i$ is consistent ($inconsistent(i)=0$) if it
only belongs to $Tail^{Genre}$, otherwise we say $i$ is inconsistent
($inconsistent(i)=1$). Now, we define the profile inconsistency ($PI$) of each
user $u$ as follows:

$PI_{u}=\frac{\sum_{i\in\mathcal{R}_{u}}{inconsistent(i)}}{|\mathcal{R}_{u}|}$
(5)

$PI_{u}$ computes the ratio of the inconsistent items that user interacted
with. Lower $PI_{u}$ implies that a user’s interest toward popularity spectrum
(either popular or less popular) is stronger, meaning that the items $u$
interacted with and their genres are in the same popularity group. On the
other hand, higher $PI_{u}$ indicates that assigned group to $u$ is not
sufficiently reliable and $u$ might also have certain degree of interest
toward other groups.

Figure 9: The relationship between profile inconsistency and $PL$ of different
recommendation models for $\textbf{Niche}^{item}$ users on MovieLens dataset.
Figure 10: The relationship between profile inconsistency and $UPD$ of
different recommendation models for $\textbf{Niche}^{item}$ users on MovieLens
dataset.

Now, the question is: do the recommendation models behave fairer for
consistent users? To answer this question, among users in
$\textbf{Niche}^{Item}$, we look at the degree of unfairness for those users
who their $PI$ is lower than a threshold. Given a threshold $\alpha$, we
extract users who their $PI$ is less than $\alpha$ and then we report their
average $PL$ and $UPD$. The reason we only look at $\textbf{Niche}^{Item}$ is
that this group is the protected group in our analysis and the group
experiencing the highest disparity in the recommendation results.

Figure 9 shows the $PL$ of the recommendation models for a subset of users in
$\textbf{Niche}^{Item}$ with $PI_{u}\leq\alpha$ for $\alpha\in[0.1,0.6]$. The
results show that $PL$ of factorization models (BPR and BiasedMF) slightly
improve for more consistent users and as $\alpha$ increases (more inconsistent
users are included), $PL$ also increases (higher disparity). This pattern
cannot be observed for neighborhood models (UserKNN and ItemKNN). However,
this pattern is stronger for $UPD$ across all algorithms as shown in Figure
10. In all recommendation models (except Random), with increasing $\alpha$
(more inconsistent users), $UPD$ also increases. These results suggest ideas
for improving the fairness of the recommendations using genre information:
incorporating the genre information when generating recommendations,
particularly for users with high profile inconsistency.

Figure 11: The relationship between the popularity diversity of users’ profile
and $PL$ of their recommendations on MovieLens dataset. $\rho$ is the
correlation value of these two variables.

##  4 Popularity Diversity of users profile

The second factor that we investigate is the popularity diversity of the
users’ profile and we aim at showing how correlated this factor is with the
ability of the recommendation model to follow the users’ interest toward
popularity spectrum. Popularity diversity refers to the fact that how
interacted items in a user’s profile are from diverse item groups. For
example, a profile with items from $\langle Head,Head,Mid,Tail\rangle$ is
considered to be more diverse than a profile with items from $\langle
Head,Head,Head,Head\rangle$ as it covers more diverse sets of item groups.
Therefore, if a user’s profile has lower popularity diversity, it can be
interpreted as more focused the user is in interacting with the items. For
example, when a user only interacted with $Head$ items, it means that he/she
has high concentration on popular items and his/her profile would result in
low popularity diversity.

For computing the popularity diversity of a user’s profile, we first extract
the item groups corresponding to the interacted items and then, we compute
entropy on the vector of extracted item groups. This way, a profile where
every interacted item belongs to one item group would result in the lowest
entropy and consequently the lowest popularity diversity. And vice versa, a
profile where interacted items belong to various item groups would represent
higher popularity diversity.

Figure 12: The relationship between the popularity diversity of users’ profile
and $UPD$ of their recommendations on MovieLens dataset. $\rho$ is the
correlation value of these two variables.

Figure 11 shows the relationship between the popularity diversity and $PL$ of
users’ profile on each recommendation model. The horizontal axis is popularity
diversity and vertical axis is $PL$. On each plot, the value $\rho$ shows the
correlation between two variables. As shown, there is a positive correlation
between popularity diversity and $PL$ of the users’ profile. This correlation
is higher on BPR, BiasedMF, UserKNN, and Popular. Analogously, Figure 12 shows
the relationship between the popularity diversity and $UPD$ of the users’
profile on recommendation models. The same pattern can also be observed here,
but the correlation is even higher (except for Random).

While Figures 11 and 12 confirm that $PL$ and $UPD$ are correlated with
popularity diversity of the users’ profile, another pattern in these results
is the popularity diversity across different user groups. It shows that
blockbuster-focused group has the lowest popularity diversity, while niche-
focused group has the highest popularity diversity. Possible explanation for
this result is that blockbuster-focused users mainly interact with popular
items, while niche-focused users interact with a combination of popular and
unpopular items.

Our last analysis reveals the relationship between the users’ profile size and
users’ interest toward popular items. This analysis ensures that the
correlation between our identified factors and the degree of unfairness is not
due to some other hidden influential factors. The size of users’ profile is an
important factor that has been shown to affect the performance of
recommendations (larger profile size leads to more accurate recommendation)
[16].

Figure 13 shows the relationship between average popularity and size of the
users’ profile for different groups of users. It is evident that Blockbuster
users have smaller profile (less interacted items), while Niche users have
larger profile size (more interacted items). With profile size being a factor
affecting the quality of the recommendation for a user, the expectation is
that the recommendations delivered to Niche users better match their interest.
However, our experimental results do not show this pattern. This confirms that
our identified factors are not affected by users’ profile size.

Figure 13: The relationship between users’ profile size and the average
popularity of their profile.

##  5 Conclusion

In this paper, we studied the user-centered unfairness of popularity bias in
recommender systems. In particular, we investigated two factors leading to
this unfairness. One factor was profile inconsistency which refers to the
degree of inconsistency of a user’s profile in terms of her interest to item
popularity and genre popularity (e.g., the inconsistency is high when a user
is interested in popular items, but also interested in less popular genres).
Another factor was popularity diversity of users’ profile which refers to how
diverse a user’s profile is in terms of interacted item groups. Experiments on
a movie recommendation dataset using six different recommendation algorithms
showed that the introduced factors are highly correlated with the degree of
unfairness in recommendation results. An interesting future direction is to
investigate possible ways of utilizing the identified factors in this paper to
improve the fairness of the recommendation models.

## References

  * [1] Abdollahpouri, H., Burke, R., Mansoury, M.: Unfair exposure of artists in music recommendation. arXiv preprint arXiv:2003.11634 (2020)
  * [2] Abdollahpouri, H., Burke, R., Mobasher, B.: Controlling popularity bias in learning-to-rank recommendation. In: Proceedings of the eleventh ACM conference on recommender systems. pp. 42–46 (2017)
  * [3] Abdollahpouri, H., Mansoury, M.: Multi-sided exposure bias in recommendation. ACM KDD Workshop on Industrial Recommendation Systems 2020 (2020)
  * [4] Abdollahpouri, H., Mansoury, M., Burke, R., Mobasher, B.: The unfairness of popularity bias in recommendation. RecSys Workshop on Recommendation in Multistakeholder Environments (RMSE) (2019)
  * [5] Abdollahpouri, H., Mansoury, M., Burke, R., Mobasher, B., Malthouse, E.: User-centered evaluation of popularity bias in recommender systems. In: Proceedings of the 29th ACM Conference on User Modeling, Adaptation and Personalization. pp. 119–129 (2021)
  * [6] Beutel, A., Chen, J., Doshi, T., Qian, H., Wei, L., Wu, Y., Heldt, L., Zhao, Z., Hong, L., Chi, E.H., et al.: Fairness in recommendation ranking through pairwise comparisons. In: Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. pp. 2212–2220 (2019)
  * [7] Ciampaglia, G.L., Nematzadeh, A., Menczer, F., Flammini, A.: How algorithmic popularity bias hinders or promotes quality. Scientific reports 8(1), 15951 (2018)
  * [8] Harper, F.M., Konstan, J.A.: The movielens datasets: History and context. ACM Transactions on interactive intelligent systems (tiis) 5(4), 1–19 (2015)
  * [9] Koren, Y., Bell, R., Volinsky, C.: Matrix factorization techniques for recommender systems. Computer 42(8), 30–37 (2009)
  * [10] Kowald, D., Schedl, M., Lex, E.: The unfairness of popularity bias in music recommendation: A reproducibility study. In: Advances in Information Retrieval: 42nd European Conference on IR Research, ECIR 2020, Lisbon, Portugal, April 14–17, 2020, Proceedings, Part II 42. pp. 35–42. Springer (2020)
  * [11] Lin, J.: Divergence measures based on the shannon entropy. IEEE Transactions on Information theory 37(1), 145–151 (1991)
  * [12] Mansoury, M.: Fairness-aware recommendation in multi-sided platforms. In: Proceedings of the 14th ACM International Conference on Web Search and Data Mining. pp. 1117–1118 (2021)
  * [13] Mansoury, M.: Understanding and mitigating multi-sided exposure bias in recommender systems. PhD Dissertation, (Eindhoven University of Technology) (2021)
  * [14] Mansoury, M., Abdollahpouri, H., Pechenizkiy, M., Mobasher, B., Burke, R.: Feedback loop and bias amplification in recommender systems. In: Proceedings of the 29th ACM international conference on information & knowledge management. pp. 2145–2148 (2020)
  * [15] Mansoury, M., Abdollahpouri, H., Pechenizkiy, M., Mobasher, B., Burke, R.: A graph-based approach for mitigating multi-sided exposure bias in recommender systems. ACM Transactions on Information Systems (TOIS) 40(2), 1–31 (2021)
  * [16] Mansoury, M., Abdollahpouri, H., Smith, J., Dehpanah, A., Pechenizkiy, M., Mobasher, B.: Investigating potential factors associated with gender discrimination in collaborative recommender systems. The 33nd International FLAIRS Conference in Cooperation with AAAI (2020)
  * [17] Mansoury, M., Burke, R.: Algorithm selection with librec-auto. In: AMIR@ECIR. pp. 11–17 (2019)
  * [18] Mansoury, M., Mobasher, B.: Fairness of exposure in dynamic recommendation. CONSEQUENCE’23 Workshop on Causality, Counterfactuals, and Sequential Decision-Making in conjunction with ACM RecSys 2023 (2023)
  * [19] Rastegarpanah, B., Gummadi, K.P., Crovella, M.: Fighting fire with fire: Using antidote data to improve polarization and fairness of recommender systems. In: Proceedings of the twelfth ACM international conference on web search and data mining. pp. 231–239 (2019)
  * [20] Rendle, S., Freudenthaler, C., Gantner, Z., Schmidt-Thieme, L.: Bpr: Bayesian personalized ranking from implicit feedback. In: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence. pp. 452–461 (2009)
  * [21] Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., Riedl, J.: Grouplens: An open architecture for collaborative filtering of netnews. In: Proceedings of the 1994 ACM conference on Computer supported cooperative work. pp. 175–186 (1994)
  * [22] Sarwar, B., Karypis, G., Konstan, J., Riedl, J.: Item-based collaborative filtering recommendation algorithms. In: Proceedings of the 10th international conference on World Wide Web. pp. 285–295 (2001)
  * [23] Sinha, A., Gleich, D.F., Ramani, K.: Deconvolving feedback loops in recommender systems. Advances in neural information processing systems 29 (2016)
  * [24] Steck, H.: Collaborative filtering via high-dimensional regression. arXiv e-prints pp. arXiv–1904 (2019)
  * [25] Sürer, Ö., Burke, R., Malthouse, E.C.: Multistakeholder recommendation with provider constraints. In: Proceedings of the 12th ACM Conference on Recommender Systems. pp. 54–62 (2018)
  * [26] Yao, S., Huang, B.: Beyond parity: Fairness objectives for collaborative filtering. Advances in neural information processing systems 30 (2017)
  * [27] Zhu, Z., He, Y., Zhao, X., Caverlee, J.: Popularity bias in dynamic recommendation. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. pp. 2439–2449 (2021)
  * [28] Zhu, Z., He, Y., Zhao, X., Zhang, Y., Wang, J., Caverlee, J.: Popularity-opportunity bias in collaborative filtering. In: Proceedings of the 14th ACM International Conference on Web Search and Data Mining. pp. 85–93 (2021)